Java Hashing
The single most useful tool in a coding round, and the one whose worst case interviewers like to probe.
2 concepts · 6 interview questions
What this topic covers
Every concept in hashing, and the questions each one gets asked as. Where a question links, it has a full write-up.
Maps and sets as a technique
Trading memory for a constant-time membership test converts a great many quadratic scans into a single pass.
- Two sum, unsorted, in one pass.
- Find the first non-repeating character in a string.
- Group anagrams together.
When hashing degrades
Constant time assumes a good hash. Collisions, mutable keys and adversarial input each break the assumption in a different way.
- What is the worst case of a HashMap lookup, and when does it happen?
- What happens if you mutate a key after inserting it?
- How would you design a hash function for a custom key?