Hash Tables and Collision Handling in Interviews

Hash table questions test order lookup, deduplication and frequency tracking, plus what a collision strategy costs at low latency.

Hash table questions in trading interviews test two things together: the standard technique for using a map to solve a problem in one pass, and the harder question of what happens when the map itself has to run inside a system where a collision or a resize cannot be allowed to cost microseconds it does not have. Order id lookup, trade deduplication, top-traded symbol tracking and offsetting-pair detection are the four shapes that come up most, each solvable with a hash map in the first pass and then pushed further by a systems-flavored follow-up.

State the problem precisely: given an order id, locate the order's current state, price and size in constant time so it can be cancelled or amended, rather than scanning the book to find it. A hash map from order id to a pointer or index into the underlying storage answers this directly in O(1) average time, and the interviewer expects the candidate to state that the guarantee is average case, not worst case, because a hash table's worst case degrades to O(n) under enough collisions.

The follow-up asks how collisions are handled and why the choice matters at low latency. Chaining, where each bucket holds a linked list of entries that hash to it, is simple and tolerates a high load factor gracefully, but every lookup can chase pointers scattered across memory. Open addressing with linear or quadratic probing keeps entries inside one contiguous array, which is far friendlier to the cache and is why low-latency systems, order books among them, tend to prefer it despite the extra care its resize and deletion logic requires.

State the problem precisely: the same trade can arrive twice, once from a direct exchange feed and once from a drop-copy feed, and the system must recognize the duplicate and discard it rather than double-count the fill. A hash set keyed on a composite of trade id, price, size and timestamp answers the exact-duplicate case in O(1) average time per check, inserting the key on first sight and rejecting any repeat.

The follow-up asks what happens when the two copies of the same trade can arrive with a slightly different timestamp because the two feeds are not perfectly synchronized, which breaks an exact-match key. The candidate is expected to propose a key that excludes timestamp and instead bounds the acceptable arrival gap with a small time window, trading a tiny risk of collapsing two genuinely distinct trades for tolerance of clock skew between feeds.