PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Pinterest
  • Coding & Algorithms
  • Software Engineer

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.

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

  1. Order and duplicates inside a set shouldn't matter; what built-in collection ignores both? In Python that points at frozenset.
  2. 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 ==.
  3. 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • First Word Matching Each Prefix Query - Pinterest (medium)
  • Hierarchical Access Control for an Advertising Platform - Pinterest (medium)
  • Maximize Boxes Stored Through One Entrance - Pinterest (medium)
  • Solve Multiple Coding Interview Problems - Pinterest (medium)
  • Implement a Sparse Matrix Class - Pinterest (medium)