Hash Maps, Indexes, And Mutable State Modeling

What's being tested

These problems test hash-map indexing, mutable state modeling, and choosing auxiliary structures that preserve required ordering while supporting fast updates, deletes, and lookups. You must explain invariants, complexity, ownership of state, and edge-case semantics rather than merely selecting containers.

Patterns & templates

• Use a hash map for direct identity lookup: symbol/order ID → record; target average O(1) lookup, update, and deletion.

• Combine a map with a queue or ordered container when identity lookup and arrival/order semantics must coexist.

• For latest-value conflation, map each key to one mutable node and remove stale nodes without scanning; define duplicate-key ordering explicitly.

• For order books, separate price levels from individual orders: price → aggregate quantity plus FIFO orders, and order ID → order record.

• Track counts or frequencies in maps for array intersection; choose set semantics versus multiplicity semantics before coding.

• Explain hash-map behavior: bucket layout, collision resolution, load factor, resizing, tombstones, and expected O(1) versus worst-case O(n).

• For weighted sampling, maintain cumulative weights with a Fenwick tree: updates and samples cost O(log n), using a uniform target in [0, totalWeight).

Common pitfalls

Pitfall: Mutating a map while iterating can invalidate iterators or skip entries; collect removals or use an iterator-safe deletion strategy.

Pitfall: Treating a sentinel such as -1 as “missing” fails when prices or quantities may legitimately be negative; use presence checks or an explicit variant.

Pitfall: Claiming O(1) without stating average-case hashing, collision assumptions, resizing costs, and the extra memory required by auxiliary indexes.

Practice these

The practice cards below cover the canonical variants—solve all of them and time yourself.