Katkat
Back

Design an editable sequence with marker

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question evaluates understanding of mutable ordered sequence data structures, marker semantics and invariants, API and data model design, and algorithmic time-complexity trade-offs for insert, delete, and move operations.

Design a mutable ordered sequence of elements together with a marker that points to one element in the sequence.

Support the following operations:

  • Insert or remove a contiguous block of elements at a given position.
  • Move a contiguous block of elements from one position to another.
  • Set the marker to a new position.

Explain the API, data model, and how the marker should behave when edits happen before it, after it, or when the marked element is inside a moved or deleted block. Discuss reasonable implementation choices and their time-complexity tradeoffs.