Interview prompt
Explain arrays and linked lists: cost follows access pattern to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
An array stores elements in contiguous indexed positions. This makes locating element i a direct address calculation and often keeps nearby values close in cache. A linked list stores each value alongside a reference to another node, which makes traversal follow pointers instead of predictable offsets.
Inserting into the middle of a packed array shifts later values, while inserting a node into a linked list can update a constant number of references once the insertion point is already known. Finding that point still requires traversal. Dynamic arrays balance capacity and memory use by occasionally allocating a larger block and copying elements.
A complete answer also calls out the assumptions that control correctness. Constant-time indexing does not imply constant-time insertion, and constant-time pointer rewiring does not imply constant-time list operations overall. Linked structures add allocation and pointer-chasing costs. Arrays may reserve unused capacity, but their locality often makes them faster for scans than a theoretically similar pointer-based structure.
Close by describing one representative test or measurement. Choose a representation for a queue with frequent append, front removal, and occasional iteration. State which operations dominate and what guarantees your implementation needs.
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.