Indexed Vector as a Linked List with Checkpoints Every k Nodes

Implement a simplified vector: an ordered, dynamically sized sequence of strings accessed by integer position. "Vector" here means a vector in the sense of C++ std::vector or Java ArrayList, not a vector database of embeddings. It supports two operations:

• add(index, val): insert the string val at position index. The element previously at index and every element after it move one position to the right.
• get(index): return the string at position index.

v.add(0, "a") # ["a"]
v.add(1, "c") # ["a", "c"]
v.add(1, "b") # ["a", "b", "c"]
v.add(0, "z") # ["z", "a", "b", "c"]
v.get(2) # returns "b"

The interview moved in two steps: a simple first design was judged not efficient enough, and the interviewer then asked for a specific structure, a linked list with checkpoints.

Clarifying Questions

• Is add allowed at index == size, appending at the end? What should happen for an index outside the valid range of add or get?
• Is the checkpoint interval k a fixed parameter, or should the structure choose it and adapt it as the sequence grows?
• Are deletions or in-place updates needed, or only add and get?
• Which operation dominates the expected workload?

Part 1 — A plain linked list and its cost

Implement add and get on a plain singly linked list and state the worst-case cost of each. Explain why this design was judged not efficient enough, and how its costs compare with those of an array-backed sequence.

What This Part Should Cover

• Correct add and get, including insertion at the front and at the end
• The worst-case cost of each operation, and why reading by position is the bottleneck
• The opposite trade-off of an array-backed sequence

Part 2 — Linked list with checkpoints

In addition to the list, store a pointer to every k-th node, called a checkpoint. get(index) first jumps to the checkpoint at or before index and then walks forward, so a read costs O(k) instead of O(n).

Implement add and get on this structure. The core difficulty is keeping the checkpoints correct after an insertion: an insertion at the front or in the middle changes which node every later checkpoint should point to, and as the sequence grows, new checkpoints may be needed.

Clarifying Questions for this Part

• Must checkpoint j always point at exactly position j * k, or may checkpoints drift as long as get stays bounded?

What This Part Should Cover

• A precise checkpoint invariant and how get uses it
• How insertions at the front, in the middle and at the end update the checkpoints, and what that costs
• When a new checkpoint is created as the sequence grows
• The resulting costs of add and get in terms of n and k, and how to choose k