Choosing Data Structures at Scale

Context

At companies like Dropbox or Netflix, handling large datasets efficiently depends less on a single “best” structure and more on matching the structure to the workload.

Question

What data structures are most effective for handling large datasets? In your answer, explain:

1. How to choose between arrays, hash tables, trees, and heaps for large-scale workloads.
2. What trade-offs matter most, including lookup speed, insertion/deletion cost, memory overhead, and ordering.
3. How access patterns such as sequential scans, random lookups, range queries, and top-k retrieval affect the choice.

Scope Guidance

The interviewer expects a practical systems-oriented explanation rather than a proof-heavy theory answer. Discuss common structures, their complexity, when they break down at scale, and how you would justify a choice for a specific workload.