How should I practice Nested Set Structural Equivalence?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Pinterest phone screen and onsite interview problems in FastPrep.

Is Nested Set Structural Equivalence associated with Pinterest?

FastPrep tags this as a Pinterest phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · String

Nested Set Structural Equivalence

Learn this problem

● Medium

PinterestFULLTIMEPHONE SCREENONSITE INTERVIEW

Problem statement

You are given two valid strings, left and right, that encode nested mathematical sets. An encoded set follows this grammar:

set     := "{" [element ("," element)*] "}"
element := integer | set

An integer is a signed decimal integer. The encoding contains no whitespace. The empty set {} is valid.

Two encoded sets are equal when they contain the same distinct elements. The order of elements does not matter at any nesting level, and repeated equal elements at the same level collapse according to mathematical set semantics. Integer atoms compare by value, while nested sets compare recursively. An integer and a set are always different, so 1 is not equal to {1}.

Return true if left and right encode equal nested sets; otherwise, return false.

Function

nestedSetsEqual(left: String, right: String) → boolean

Examples

Example 1

left = "{1,{2,3},4}"right = "{{3,2},4,1}"return = true

Both top-level sets contain the integers 1 and 4 plus a nested set containing 2 and 3. Permuting either level does not change the set.

Example 2

left = "{1,{2,3}}"right = "{{1,2},3}"return = false

The nesting hierarchy differs. In left, 1 is a top-level atom and 3 is nested; in right, those roles are reversed.

Example 3

left = "{1,1,{},{{2},2}}"right = "{{},1,{2,{2}}}"return = true

The repeated top-level 1 collapses. Both sides then contain 1, the empty set, and a nested set whose elements are the atom 2 and the set {2}.

Constraints

2 <= left.length, right.length <= 20000
Each input is a valid encoding generated by the stated grammar and contains no whitespace.
Every integer is in [-10^9, 10^9] and uses ordinary decimal notation.
The maximum nesting depth is at most 300.
Repeated recursively equal elements at one set level represent one mathematical set element.