Explain Open Addressing. (Linear Probing, Quadratic Probing, Double Hashing)

0-2 years experience

1. 1Suppose you need to implement a hash map for a small in‑memory cache using open addressing with linear probing. How would you handle inserting a new key when the initial slot is already occupied?
2. 2If you use quadratic probing and the table size is a prime number, what could happen when the load factor reaches 0.9? How would you detect and resolve it?
3. 3What happens if you try to delete a key in a hash table that uses linear probing without any special handling? Explain the issue.

2-5 years experience

1. 1Your team added a feature that stores user sessions in a hash table using double hashing. After a deployment, you notice a spike in lookup latency. Walk me through how you would debug the probing sequence to find the root cause.
2. 2When choosing between linear probing and quadratic probing for a hash table that will store up to 1 million entries, what trade‑offs would you consider regarding clustering and cache performance?
3. 3During a load test, the hash table's load factor exceeds 0.75 and insertions start failing. How would you modify the open addressing implementation to handle this gracefully?

5-8 years experience

1. 1Design a high‑throughput in‑memory key‑value store that uses open addressing. How would you decide which probing strategy to use, and what mechanisms would you add to keep performance stable under an 80% load factor?
2. 2Explain how you would implement safe deletions in a hash table that uses double hashing in a multi‑threaded environment, ensuring no lost keys and minimal contention.
3. 3Your service must support hot‑key skew where a few keys are accessed millions of times per second. How does open addressing affect this pattern, and what mitigations would you apply?

8+ years experience

1. 1Our legacy system uses linear probing and is being migrated to a distributed cache. What architectural considerations would you evaluate when deciding whether to keep open addressing locally or replace it with a different data structure across nodes?
2. 2When scaling a global hash table that uses double hashing, how would you handle rehashing and probing across rolling upgrades without downtime?
3. 3Discuss the long‑term maintenance implications of using open addressing in a codebase that must support multiple languages and platforms. How would you standardize the implementation to avoid subtle bugs?