Determine equality of arbitrarily nested sets
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that determines whether two arbitrarily nested sets are equal. Sets are unordered and contain no duplicates; elements can be integers or other sets. Inputs are given as nested arrays representing sets (e.g., [1,[2,3],4]). Your solution must handle unlimited nesting depth. Choose and justify suitable data structures, describe the algorithm, and analyze time/space complexity. Include unit tests for the following cases: set1=[1,[2,3],4], set2=[1,[3,4],2] -> false; set1=[1,[2,3],4], set2=[1,4,[2,3]] -> true. Discuss trade-offs such as canonicalization vs. hashing vs. recursion with memoization, and cover edge cases (empty sets, duplicates in input encoding, very deep nesting).
Quick Answer: This question evaluates understanding of nested data structures and set semantics, including canonicalization, hashing, recursion, handling of edge cases, unit-test design, and time/space complexity analysis.
Implement a function that decides whether two arbitrarily nested sets are equal. Sets are unordered and contain no duplicates; an element may be an integer or another set. The inputs are given as nested arrays that represent these sets (for example, [1,[2,3],4] represents the set {1, {2,3}, 4}). Nesting depth is unbounded.
Because sets are unordered, order within any array is irrelevant, and a repeated encoding of the same element (e.g. [1,1]) denotes the same single-element set. An integer is never equal to a set, even when the set wraps that integer ([1] is not equal to 1, and [[]] is not equal to []).
Return true if the two inputs denote the same set, and false otherwise.
Approach: canonicalize recursively. Map each integer to a tagged leaf and each array to the (order-independent, duplicate-collapsing) set of its canonicalized elements — a frozenset in Python. Two inputs are equal exactly when their canonical forms are equal. This is equivalent to recursive structural comparison and avoids the subtle bugs of naive index-by-index comparison. Alternatives include sorting a canonical key at each level (works but needs a total order over mixed int/set keys) or hashing; the frozenset approach gets both order-independence and duplicate-collapsing for free.
Examples:
- set1 = [1,[2,3],4], set2 = [1,[3,4],2] -> false (the inner sets {2,3} and {3,4} differ, and 2/4 don't reconcile at the top level)
- set1 = [1,[2,3],4], set2 = [1,4,[2,3]] -> true (same elements, different order)
Constraints
- Each input is a (possibly empty) nested list whose leaves are integers.
- Nesting depth is unbounded; the solution must not assume a fixed maximum depth.
- Within any set, order is irrelevant and repeated encodings of the same element collapse to one (e.g. [1,1] == [1]).
- An integer is never equal to a set: [1] != 1 and [[]] != [] (a one-element set containing the empty set differs from the empty set).
Examples
Input: ([1,[2,3],4], [1,[3,4],2])
Expected Output: False
Explanation: Prompt case: the inner sets {2,3} and {3,4} differ, so the two sets are not equal.
Input: ([1,[2,3],4], [1,4,[2,3]])
Expected Output: True
Explanation: Prompt case: identical elements {1, {2,3}, 4}; element order is irrelevant.
Hints
- Order and duplicates inside a set shouldn't matter; what built-in collection ignores both? In Python that points at frozenset.
- Recurse: canonicalize every element first (an int stays an int, a sub-array becomes a frozenset of canonical elements), then compare the two canonical forms with ==.
- Tag leaves vs sets so that an integer can never accidentally equal a set wrapping it — compare ('int', v) against ('set', frozenset(...)), never a bare value.