Checkpointed Dynamic Sequence

Maintain a dynamic sequence of strings. The sequence starts empty and is represented by a linked list plus checkpoint references spaced every checkpointInterval positions.
Process operations in order. Each operation has one of these forms:
["ADD", index, value]: insert value immediately before the current element at the zero-based index. When index equals the current size, append the value. This operation produces no output.
["GET", index]: return the value at the zero-based index.
The index and interval fields are decimal strings. All operations are valid when they are processed. Return the GET results in operation order.

Examples
Example 1
checkpointInterval = 3
operations = [["ADD","0","A"],["ADD","1","C"],["ADD","1","B"],["GET","0"],["GET","1"],["GET","2"]]
return = ["A","B","C"]
The middle insertion places B before C. The three reads then return the sequence in index order.

Here's the reduction. Every ADD inserts before position index, and every GET reads position index. A plain array or list gives you both, and it passes the sample. The checkpoint idea is the optimization. Keep a reference to every checkpointInterval-th node, so you jump to the nearest checkpoint at or before the index, then walk at most interval-1 steps. The pitfall is maintenance. An insert shifts every later element by one position, so checkpoints after the insertion point are now off. Rebuild them from the insertion point forward, or rebuild lazily before the next GET. Also parse the strings to ints first, and handle index equal to size as an append. Don't forget the empty-list case. If the constraints are small, a simple list wins. If they're large, do the checkpoints. StealthCoder is the hedge if the rebuild logic tangles under the clock.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.