How do you choose a data structure?

Direct answer

What a strong answer covers

How it works

Pick the structure from the operations the code performs most and the invariants it must hold. A hash map gives constant average lookup by key with no order; a sorted structure such as a balanced tree or a sorted array gives range queries and ordered iteration at logarithmic cost; a queue or deque gives cheap insertion at the ends; a heap gives the minimum or maximum quickly; a set enforces uniqueness. Memory layout matters as much as asymptotics in practice: a contiguous array beats a linked list for iteration even when the theory says otherwise, because of cache behaviour.

Example

A rate limiter needs to find the count for a client and expire old entries; a hash map keyed by client plus a min-heap ordered by expiry time supports both operations in logarithmic time. A leaderboard that needs the top ten and rank queries uses a sorted structure rather than re-sorting an array of a million players on every read.

Common mistakes

• Defaulting to a list and scanning it for every lookup.
• Choosing a linked list for insert-in-the-middle without measuring that it is actually faster than an array.
• Ignoring concurrency requirements and wrapping an unsafe structure in an afterthought lock.

A useful answer structure

Answer from your own work.

Do not memorise a script: use only examples you can explain honestly in follow-up questions.