Compare cords and check whether one contains another
Filed under Google
Free read 1 of 3Equality means same character sequence, regardless of how the tree is split. Contains means the needle appears as a contiguous substring of the haystack. Ask about size limits, case sensitivity and whether an empty needle counts as contained (normally yes).
The question
Using the rope (cord) data structure from the earlier round, implement equals(a, b) to check whether two cords represent the same string, and contains(a, b) to check whether cord b occurs as a substring of cord a. The two ropes may have very different tree shapes.
Constraints
- Two ropes can hold equal text with different tree shapes.
- Prefer lazy traversal over flattening when an early exit is possible.
- Assume characters are comparable one at a time.
Approach
Equality means same character sequence, regardless of how the tree is split. Contains means the needle appears as a contiguous substring of the haystack. Ask about size limits, case sensitivity and whether an empty needle counts as contained (normally yes).
Flatten both ropes to strings with an in-order walk, then use ==, and the language's substring search for contains. That is O(n + m) time and space and is a fine first answer to state before optimising.
First compare lengths. If equal, walk both ropes with leaf-chunk iterators and compare overlapping slices chunk by chunk, stopping at the first mismatch. No full flatten is needed.
Stream the haystack characters through KMP, or a rolling hash with verification, built from the needle. State carries across leaf boundaries, so memory is O(m) for the needle plus the iterator stack.
Empty ropes, needle longer than haystack, matches straddling two leaves, repeated-character patterns that punish naive search, and very deep ropes where an iterative traversal avoids recursion limits.
Tips
- What they are testing: Whether you separate the logical string from the physical tree shape, and whether you avoid unnecessarily flattening large ropes.
- Common mistake: Comparing the trees node by node, which fails when two equal strings are split differently, or missing matches that cross a leaf boundary.
Related Google questions
Collected from public candidate posts and coding forums. Updated Nov 2026.