Final Table After Inserting Keys With Linear Probing and h(x) = (3x + 4) mod 7
Company: BNY Mellon
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: easy
Interview Round: Online Assessment
A multiple-choice question describes a hash table with 7 slots, numbered 0 to 6, and the hash function `h(x) = (3x + 4) mod 7`. Collisions are resolved with linear probing: if slot `h(x)` is occupied, try the next slot, then the one after it, and so on, wrapping from slot 6 back to slot 0. Starting from an empty table, the keys 1, 3, 8 and 10 are inserted in that order. What does the table look like at the end? Show the probe sequence for each key.
```hint Compute first, place second
Work out the home slot of all four keys before placing any of them, and notice which keys share a home slot.
```
```hint Wrap around
When a probe passes the last slot it continues at slot 0, and keys already sitting there count as occupied too.
```
### Clarifying Questions
- Does linear probing move one slot at a time and wrap around modulo 7?
- Are the slots numbered from 0, and should the answer list all seven slots with empty ones marked?
- Is the hash computed on the whole expression, so the result is always a valid slot from 0 to 6?
### What a Strong Answer Covers
- The correct home slot of each key from the hash function
- The correct probe sequence for each colliding key, including the wrap-around past the last slot
- The final table with every slot shown and empty slots marked
- Why exactly these keys collide, tied to the hash function and the table size
### Follow-up Questions
- Key 8 is deleted and then key 10 is looked up. What goes wrong if the deleted slot is simply emptied, and how do tombstones fix it?
- What would the table look like with quadratic probing, or with separate chaining?
- Which future keys would land in their home slot without probing, and what does the cluster formed here mean for later inserts?
Overview: A data structures question that inserts the keys 1, 3, 8 and 10 into a seven-slot hash table with hash function (3x + 4) mod 7 and linear probing. It asks for the final table and tests computing home slots, following probe sequences with wrap-around, and explaining why the keys collide.
Read the full BNY Mellon Software Engineer interview experience this question came from