Coding Interview: Implement a Snapshot Array

Problem and Applicable Context

Implement a fixed-length array that starts with zero at every index and supports three operations:

• set(index, value) changes one element in the current, not-yet-snapshotted version.
• snap() saves the current version and returns its ID. IDs start at 0 and increase by one.
• get(index, snapId) returns the value at index when snapshot snapId was taken.

Assume 1 <= length <= 50,000, 0 <= value <= 10^9, indices and snapshot IDs are valid, and at most 50,000 calls are made across all operations. A solution should explain both the API behavior and why its stored state is sufficient for every historical query.

This is a coding and data-structure question. The public prompt appears in current interview-practice collections, and the useful signal is whether a candidate can replace full snapshots with immutable change records, then find the correct historical record with a predecessor query.

What the Interviewer Is Evaluating

The first signal is cost modeling. Copying all length values on every snap is easy to reason about, but it costs O(length) time and space per snapshot even when one index changed. With 50,000 elements and 50,000 operations, that worst-case direction is unnecessarily large.

The second signal is choosing an index that matches the query. get always supplies an array index, so store a sorted change history per index. A history entry [s, v] means that value v became effective starting at snapshot ID s. The answer is the entry with the greatest s <= snapId, which is a standard predecessor search.

The third signal is snapshot semantics. Several set calls to the same index before the next snap belong to one version; only the last value should remain. Appending duplicate entries with the same snapshot ID wastes space and can make the history invariant harder to state. Coalescing them keeps IDs strictly increasing.

Finally, a strong answer states an invariant, proves the binary search, and tests time boundaries: initial zero, multiple writes before a snapshot, writes after a snapshot, untouched indices, and queries between sparse changes.

Clarifying Questions Before Answering

• Does snap() return the ID before or after advancing it? It returns the current ID, then advances to the next

working version.

• Can set be called several times before snap? Yes. The last write to an index in that version wins.
• Can get read the current unsnapped state? No. It receives a valid ID returned by an earlier snap().
• Are the length and index range fixed? Yes. There is no insertion, deletion, or resizing.
• Can snapshot IDs be skipped? An index may have no change in many consecutive snapshots, although global IDs

remain consecutive.

• Do we need thread safety? No for this in-memory interview contract. Concurrent mutation would require external

synchronization around set and snap.

• What should an untouched index return? Zero for every snapshot.
• Is persistence across process restarts required? No. That would add serialization and durability requirements

outside this data-structure problem.

30-Second Answer Framework

“I would keep a sorted history for each array index instead of copying the whole array. Initialize every history with [0, 0]. The current snapshot ID starts at zero. On set, overwrite the last entry if it already belongs to the current ID; otherwise append [currentId, value]. On snap, return currentId and increment it. On get, binary-search that index's history for the first entry whose ID is greater than snapId, then return the preceding value. Histories have strictly increasing IDs, and the sentinel guarantees a predecessor. Construction is O(length), set and snap are amortized O(1), get is O(log h), and space is O(length + u) for u retained changes.”

Step-by-Step Deep Dive

Step 1: Reject full copies after quantifying them.

A direct implementation keeps a mutable array and copies all of it into a list on every snap. It gives O(1) set and get, but snap costs O(length) and each snapshot stores length values. This pays for unchanged indices.

A single global event log avoids copies, but get(index, snapId) may scan backward across updates for unrelated indices. The query already names an index, so partitioning history by index removes irrelevant events.

Step 2: Define what one history entry means.

For one index, suppose its retained history is:

[[0, 0], [2, 7], [5, 4]]

The value is 0 for snapshots 0 and 1, 7 for snapshots 2 through 4, and 4 from snapshot 5 onward. Each entry is a change point, not a copy for one snapshot. The desired record for snapshot t is therefore the rightmost record whose ID is at most t.

Initialize every index with [0, 0]. This sentinel expresses the initial value and guarantees that every valid snapshot query has a predecessor, so get needs no empty-history branch.

Step 3: Coalesce writes inside the current version.

Before the first snap, the current ID is 0. If set(3, 5) is followed by set(3, 8), snapshot 0 must contain 8. The second call overwrites [0, 5] with [0, 8]. After snap() advances the current ID, the next write appends a new record.

This maintains the invariant that snapshot IDs in every history are strictly increasing and each history contains at most one record for any ID. The number of retained changes is no greater than the number of set calls.

Step 4: Implement upper-bound predecessor search.

type Version = [snapId: number, value: number];

class SnapshotArray {
  private readonly histories: Version[][];
  private currentSnapId = 0;

  constructor(length: number) {
    this.histories = Array.from({ length }, () => [[0, 0]]);
  }

  set(index: number, value: number): void {
    const history = this.histories[index];
    const latest = history[history.length - 1];

    if (latest[0] === this.currentSnapId) {
      latest[1] = value;
    } else {
      history.push([this.currentSnapId, value]);
    }
  }

  snap(): number {
    return this.currentSnapId++;
  }

  get(index: number, snapId: number): number {
    const history = this.histories[index];
    let left = 0;
    let right = history.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);
      if (history[middle][0] <= snapId) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return history[left - 1][1];
  }
}

The search uses the half-open interval [left, right). At termination, left is the first position with an ID greater than snapId. Its predecessor is the rightmost entry with an ID at most snapId. This is the same upper-bound partition documented by standard bisection libraries.

Step 5: Prove correctness from the invariant.

For each index, records have strictly increasing IDs. A record [s, v] is created or finalized before snapshot s is taken and remains the effective value until the next record for that index. Therefore, among records whose IDs do not exceed a requested snapshot, the one with the greatest ID is exactly the last write visible to that snapshot.

The binary search returns the first record after that eligible prefix, so left - 1 selects its greatest ID. The sentinel [0, 0] makes the eligible prefix nonempty for every valid snapshot ID. Thus get returns the required value.

Step 6: Analyze complexity and verify boundaries.

Creating the histories costs O(length) time and space. set reads or appends the tail of one history in amortized O(1) time. snap is O(1). If an index has h retained records, get costs O(log h). Across the object, space is O(length + u), where u is the number of retained non-sentinel change records and u is at most the number of set calls.

At minimum, test:

A randomized differential test can compare this structure against the full-copy baseline. The baseline is too costly for production constraints but is a simple and trustworthy test oracle.

High-Quality Sample Answer

“The key query is historical lookup for one known index, so I would keep an ordered change history per index. Every history starts with [0, 0]; a pair [s, v] means v is effective from snapshot s until the next pair.

The current ID begins at zero. set looks only at the last pair. If that pair already uses the current ID, it replaces the value because the last write before a snapshot wins. Otherwise it appends a new pair. snap returns the current ID and increments it.

For get(index, snapId), I run an upper-bound search on that index's history: find the first pair with ID greater than the requested ID and return the previous pair's value. The per-index IDs are strictly increasing, and the initial sentinel guarantees that the predecessor exists. This predecessor is precisely the last value written no later than the requested snapshot.

Construction costs O(length). set and snap are amortized O(1), get is O(log h) for that index's h change records, and total space is O(length + u). I would test initial zeros, repeated sets before one snapshot, sparse changes across several snapshots, past reads after later writes, untouched indices, and randomized traces against a full-copy oracle.”

Common Mistakes

• Copying the entire array on every snapshot → time and space scale with all indices, including unchanged ones → store only per-index change points.
• Keeping one global update log → a read may scan unrelated indices → partition histories by the index supplied in every query.
• Appending every set → repeated writes in one version create duplicate IDs and wasted records → overwrite the tail when it has the current ID.
• Searching for an exact snapshot ID → an index may not change in that snapshot → find the greatest recorded ID less than or equal to the request.
• Using lower bound and returning it directly → it may point to a later change → upper-bound the request and return the predecessor.
• Starting histories empty → untouched indices need special cases → seed each history with [0, 0].
• Incrementing before returning from snap → the first returned ID becomes 1 and records shift versions → return the current ID, then increment.
• Claiming get is O(log length) → it searches change records for one index → state O(log h) and define h.
• Testing only the published example → same-version overwrites and sparse histories remain unverified → add boundary cases and a differential oracle.

Follow-Up Questions and Responses

Follow-up 1: Can snap() be O(1) if a snapshot must be immutable?

Yes. Immutability is logical: after an ID is returned, future writes append under a larger ID and never mutate records belonging to older IDs. snap() only advances the version boundary; it does not need to materialize a full copy.

Follow-up 2: Why use a history per index instead of a map per snapshot?

A map per snapshot makes a point lookup search backward across snapshots until it finds that index. Per-index histories organize records by the first query key, so get searches only relevant changes. A snapshot-oriented map can be useful when the main query is “enumerate everything changed in snapshot s,” which is a different contract.

Follow-up 3: Could get use a standard-library binary search?

Yes when the language exposes the exact upper-bound contract for a key. For example, a right-bisection position is the insertion point after existing IDs equal to snapId; subtracting one yields the predecessor. Confirm key extraction and concurrency behavior in the library documentation rather than assuming all binary-search helpers return the same bound.

Follow-up 4: What changes if snapshots can be deleted?

First define whether deleting one ID also makes later snapshots inaccessible or whether IDs remain stable. Stable IDs usually require reference counting or compaction that preserves every value still reachable by a retained snapshot. Deleting one record blindly can change the value inherited by later snapshots.

Follow-up 5: How would you persist the structure?

Store append-only change records keyed by (arrayid, index, snapid) and publish a durable snapshot boundary only after all preceding writes commit. Reads need a predecessor index on (arrayid, index, snapid). Recovery, transactions, and compaction then become storage-system concerns beyond the in-memory interview implementation.

Follow-up 6: What if reads greatly outnumber writes for a small fixed array?

Full copies may become reasonable if the array is small and O(1) reads matter more than snapshot cost. Compare actual length, snapshot count, read rate, and memory budget. The change-history design optimizes sparse writes and snapshot creation; it is not automatically best for every workload.