Java coding questions: HashMap from scratch, top-k frequent and seat booking 3 questions in 3 chapters
Build your own collections
A hash map from scratch, then a frequency count with a heap.
1.1 How do you implement your own HashMap? Hard 4 min
I'd use an array of buckets, where each bucket is a linked list of nodes holding the key, its hash and the value. To find a bucket I mix the hash code's high bits into the low bits and mask with the array length, which is a power of two. Put either updates a matching key or adds a node. When size passes three quarters of the capacity, I double the array and rehash. Lookups are constant time on average.
Read the full answer1.2 How do you return the k most frequent numbers, with the larger number first on a tie? Medium 3 min
First I count with a HashMap from number to frequency. Then I keep a min-heap of size k, ordered by frequency, and on a tie by the smaller number, so the root is always the weakest of the current top k. For each entry I add it, and if the heap grows past k I remove the root. Finally I pop the heap into the result from the back. That's O(n log k) time and O(n) space.
Read the full answer
Concurrency in coding rounds
Making one check-and-set atomic, first in memory and then across servers.
2.1 Two people book the same seat at the same moment. How do you make sure only one gets it? Medium 3 min
The bug is check-then-act: both threads see the seat as free, then both book it. In one JVM I make the check and the write a single atomic step with ConcurrentHashMap.putIfAbsent, so exactly one caller gets null back. With several servers I push that atomic step into the database: a unique constraint on event and seat, or a conditional UPDATE where the seat is still free. The loser gets zero rows or a constraint error and I return "already taken".
Read the full answer
Sources
- HashMap Javadoc (Java 21)
- OpenJDK 21 source: HashMap.java
- Object.hashCode and equals contract (Java 21))
- LeetCode 347: Top K Frequent Elements
- PriorityQueue Javadoc (Java 21)
- ConcurrentHashMap Javadoc (Java 21)
- PostgreSQL 17 docs: Read Committed isolation level
- PostgreSQL 17 docs: Constraints (unique constraints)