Final Table After Inserting Keys With Linear Probing and h(x) = (3x + 4) mod 7

Quick 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.

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

BNY Mellon logo
BNY Mellon
Oct 29, 2026
easySoftware EngineerOnline AssessmentSoftware Engineering Fundamentals
0
0

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.

Clarifying Questions Guidance

  • 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 Guidance

  • 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 Guidance

  • 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?