map / coding / data-structures

Coding · principle 2 of 6

Core data structures

Hash maps, heaps, and tries each trade memory and ordering for a specific fast operation; pick the structure by the operation you need most.

01 · Why it’s true

Each data structure makes some operations cheap by organizing data in a particular way, which makes other operations more expensive. A hash map finds a key in constant time on average but keeps no order; a heap always gives you the smallest (or largest) item quickly but can’t search; a sorted structure supports ranges but costs more per insert.

So the right choice comes from the operations you need most. Name the operations first, then pick the structure that makes them cheap.

02 · Picture it

STRUCTUREFAST ATSLOW AT / MISSINGSRE EXAMPLEHash maplookup, insert,delete by key — O(1)avgordering, rangescount requests perIPHeapget min/max O(1),insert O(log n)searching for anarbitrary itemtop-K slowestendpointsSorted treelookups and rangesO(log n)slower than a hashmap for plain lookupevents in a timewindowQueue / dequeadd and remove atends O(1)lookup in the middlesliding-window ratecountsTrieprefix lookupsmemory overheadrouting by pathprefix
Hash mapFAST ATlookup, insert, delete by key — O(1)avgSLOW AT / MISSINGordering, rangesSRE EXAMPLEcount requests per IPHeapFAST ATget min/max O(1), insert O(log n)SLOW AT / MISSINGsearching for an arbitrary itemSRE EXAMPLEtop-K slowest endpointsSorted treeFAST ATlookups and ranges O(log n)SLOW AT / MISSINGslower than a hash map for plain lookupSRE EXAMPLEevents in a time windowQueue / dequeFAST ATadd and remove at ends O(1)SLOW AT / MISSINGlookup in the middleSRE EXAMPLEsliding-window rate countsTrieFAST ATprefix lookupsSLOW AT / MISSINGmemory overheadSRE EXAMPLErouting by path prefix
Pick the structure from the operations you need.

03 · In the interview

  • Practical coding rounds: counting, top-K, sliding windows, and dedupe.
  • Explaining why you chose a structure, not just using one.
  • Talking through memory use for large inputs.

04 · Practice question

“From a stream of request logs, report the 10 slowest endpoints by average latency. Which data structures do you use?”

A strong answer covers

  1. A hash map from endpoint to running (total latency, count) — one O(1) update per line.
  2. At the end, compute averages and use a min-heap of size 10 to keep the top 10: O(m log 10) for m endpoints.
  3. Or simply sort the endpoints if m is small; say so.
  4. Mention edge cases: endpoints with very few requests, and parameters in paths that should be normalized (/users/123 → /users/:id).