Question 1

What is a hash collision and how is it resolved?

Accepted Answer

Lead with inevitability — that is the most important part of the answer: "A collision is two different keys landing on the same bucket index, and by the pigeonhole principle it is unavoidable: the key space is always larger than the bucket count." Then one sentence per strategy: separate chaining — each bucket holds a list and a colliding entry is appended to it; open addressing — each bucket holds one entry and, if taken, probing looks for the next free slot. State the trade-off concretely: chaining makes deletion easy and allows a load factor above 1, at the cost of pointer memory and poor cache locality. Open addressing is cache-friendlier and saves memory, but deletion needs tombstones and the load factor cannot exceed 1. Close with: "Java/Kotlin HashMap uses chaining and tree-ifies long buckets; Python's dict chose open addressing instead."

Question 2

Why is deleting an entry from a hash table that uses open addressing difficult?

Accepted Answer

This question demands a concrete example — a dry explanation does not land. "Say A landed in slot 5. B hashes to 5 too, and since the slot is taken, probing places it in slot 6. If I now delete A and blank slot 5, then a lookup for B reaches slot 5, sees it empty, and stops with 'not found'. But B is one step away — the probe chain was broken." Then give the fix: the deleted slot is marked as a tombstone, not empty — "something was here, keep going". Lookups walk past a tombstone, and a new entry can reuse that space. Always add the cost, because that is what separates a strong candidate: as tombstones pile up every lookup gets longer and the effective complexity drifts from O(1), so real implementations periodically rebuild the table to purge them.

Question 3

What is the difference between linear and quadratic probing? When would you pick each?

Accepted Answer

Start from the mechanism: linear probing steps +1, +2, +3... past occupied slots; quadratic probing steps +1², +2², +3²... — the stride grows quickly. Explain why that matters: with linear probing, consecutively filled slots create primary clustering — large occupied blocks form, and every new key landing in one must walk the whole block. Quadratic probing leaves gaps between probes and so breaks those clusters up. Then give the honest trade-off: linear probing is better for the cache because it reads neighbouring memory — in practice that can outweigh the theoretical advantage. Quadratic probing, if the capacity is chosen poorly, may never visit some slots; that is why capacity is typically a power of two with a specific probe sequence. The choice: "For small to moderately loaded tables I prefer linear probing for its simplicity and cache behaviour; if a high load factor is expected, quadratic probing or double hashing is more stable."

Question 4

What is a hash flooding attack and how do systems defend against it?

Accepted Answer

Explain the logic of the attack: if the attacker knows the hash function in use, they can craft keys that all land in one bucket. If, say, a request's query parameters or JSON keys are collected into a map on the server, sending thousands of such keys turns the map into one long chain. Each insert becomes O(n), the total work rises to O(n²), and a handful of requests can take the server down — a classic DoS vector. List the defences: (1) hash randomization — a random seed chosen at process start salts the hash, so the attacker cannot precompute which keys collide; (2) attack-resistant functions such as SipHash; (3) tree-ification as in Java 8 — a long bucket becomes a tree and the worst case is O(log n); (4) capping the number of keys accepted from an external source. This is asked at senior level to see whether you can view a data structure's performance characteristic as a security concern. Name that connection yourself at the end of your answer.

Question 5

Which collision strategy does JavaScript's Map use?

Accepted Answer

This question is really an honesty test. The correct answer: "The ECMAScript spec does not mandate an internal strategy — it only describes behaviour (insertion order is preserved, lookup must be sublinear on average). The concrete solution is engine-dependent; V8 has its own internal implementation and it can change between versions." Then add the facts you do know: Map decides key equality by SameValueZero — object keys compare by reference, and NaN counts as equal to itself. Insertion order is guaranteed and iteration follows it. Offer contrast from runtimes you do know: "Java's HashMap strategy is documented openly — chaining plus tree-ification; Python's dict uses open addressing. JS gives no such guarantee." Inventing details here is the worst option. Saying "the spec leaves this to the engine, but the principle is the same" is a perfectly acceptable and strong answer.

Runtime	Actual behaviour	Worth knowing
JavaScript `Map`	An engine (V8) internal; insertion order is guaranteed	The spec does not mandate a strategy — "engine-dependent" is the correct thing to say
Kotlin / Java `HashMap`	Separate chaining; past 8 entries a bucket's linked list becomes a balanced tree	This lowers the worst case from O(n) to O(log n) (Java 8+)
Dart `HashMap`	A VM-internal solution; relies on the `==` / `hashCode` pair	`LinkedHashMap` (the default `{}` literal) preserves insertion order
Python `dict`	Open addressing plus a compact internal layout	A useful contrast — not every language picks the same route

Collision resolution