Why is insertion/deletion in the middle of an array O(n)?

0-2 years experience

1. 1Suppose you have a dynamic array of user IDs and need to insert a new ID at index 5. Walk me through what the runtime will be and why.
2. 2If you delete the element at position 3 of an array of size N, what steps does the runtime perform?
3. 3What would you observe if you repeatedly insert at the front of a JavaScript array in a loop of 10,000 iterations?

2-5 years experience

1. 1We have a feature that maintains a sorted list of timestamps in an array and inserts new events in order. The insertion is causing latency spikes. How would you investigate and what alternatives might you consider?
2. 2During a code review you notice a bug where deleting an element from the middle of a large array sometimes leaves a duplicate at the end. Explain why this could happen and how to fix it.
3. 3Our service uses a slice of a Go []int to represent a queue, and we frequently remove from the middle. Explain the performance impact and propose a refactor.

5-8 years experience

1. 1Design a component that needs to support high‑throughput insertions and deletions at arbitrary positions. Compare using a dynamic array vs a linked list vs a balanced tree, and justify your choice for a 10‑million‑record in‑memory cache.
2. 2We need to migrate a legacy C++ module that uses raw arrays for a real‑time physics engine to a more flexible container. Discuss the trade‑offs of switching to std::vector versus a custom linked structure given the O(n) middle operations.
3. 3Our analytics pipeline stores events in a contiguous buffer for cache efficiency, but occasional mid‑stream deletions are required. How would you redesign to keep O(1) amortized deletion while preserving locality?

8+ years experience

1. 1Across multiple services we have a shared data model stored as JSON arrays that are frequently patched in the middle. At scale, the O(n) cost is becoming a bottleneck. Propose an architectural migration path, including data format changes, backward compatibility, and impact on downstream teams.
2. 2Your organization is planning a platform‑wide shift from array‑based storage to a columnar store to improve write performance. Explain how the middle‑insertion cost influences this decision and outline a phased rollout strategy.
3. 3We have a legacy system that serializes large arrays over the network, and clients need to delete arbitrary elements. How would you redesign the API and underlying storage to avoid O(n) costs while minimizing breaking changes?