โ† Google questions
Low-Level DesignReported in a candidate post, Sep 2024

Compare cords and check whether one contains another

Filed under Google

Free read 1 of 3

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).

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

  1. 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).

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.