Determine equality of arbitrarily nested sets
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
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.
Input: ([], [])
Expected Output: True
Explanation: Two empty sets are equal.
Input: ([1], [1,1])
Expected Output: True
Explanation: Duplicate encodings collapse: [1,1] denotes the same single-element set {1}.
Input: ([1,[2,[3,[4]]]], [1,[2,[3,4]]])
Expected Output: False
Explanation: Deep nesting: {3,{4}} (a 3 plus the set {4}) is not the same as {3,4} (two integers).
Input: ([1,[2,[3,[4]]]], [[2,[[4],3]],1])
Expected Output: True
Explanation: Deep nesting with reordering: [[4],3] == {3,{4}}, so [2,[[4],3]] == {2,{3,{4}}}; both whole sets equal {1, {2,{3,{4}}}}.
Input: ([1,2,3], [3,2,1])
Expected Output: True
Explanation: Flat set, reversed order; sets are unordered.
Input: ([[]], [])
Expected Output: False
Explanation: A set containing the empty set, {{}}, is not the empty set {}.
Input: ([1,[2,3]], [1,[2,3],4])
Expected Output: False
Explanation: Strict subset: the second set has an extra element 4.
Input: ([-1,[0,-2]], [[-2,0],-1])
Expected Output: True
Explanation: Negative integers and reordering at both levels still compare equal.
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.