You have thirty minutes to write a hash table from scratch. What do you get to skip, and what will the interviewer not let you skip?
Use separate chaining and skip iterators, shrinking, thread safety and null keys, saying so aloud. You cannot skip a non-negative bucket index, an equality check after the hash matches, overwriting an existing key, unlinking the head of a chain, or a resize that rehashes every entry against the new capacity.
Answer
Short answer
Pick separate chaining, because it makes removal a plain list unlink. Skip iterators, shrinking, thread safety and null keys, and say each one out loud as a choice. The interviewer will not let you skip five things: a bucket index that is never negative, an equality check after the hash narrows the bucket, overwriting an existing key, removing the first node of a chain, and a resize that recomputes every entry's bucket. Then state the complexity of your hash table precisely.
Was this answer helpful?
Likely follow-ups
- Switch this to open addressing with linear probing. What does remove have to do that chaining did not?
- Your capacity is a power of two and every key's hashCode is a multiple of 64. What happens to the chains, and what do you add?
- The interviewer asks for an iterator. What should happen if the table is modified halfway through iterating?
- How would you size the table up front if the caller tells you it will hold a million keys?
Related questions
- You are given a paragraph of requirements, not a problem statement. What do you write first, and what do you deliberately not build?mediumSame kind of round: coding5 min
- Your Collectors.toMap call passed every test and threw in production. What did the code assume, and what are your options?mediumSame kind of round: coding4 min
- Given everyone's busy calendar, find the slots when all of them are free. What do you sort, and what breaks at the boundaries?mediumSame kind of round: coding5 min
- The interviewer hands you working production code with a few deliberate changes that break it. You have 45 minutes. What do you do before you read line one?mediumSame kind of round: coding5 min