Collision Handling Using Open Addressing Linear Probing in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Probing Insertions

What is the state of the hash table after inserting keys 10, 22, 31, 4, 15 into a hash table of size 10 using linear probing with hash function h(k) = k % 10?

DSA Python

class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None:
            idx = (idx + 1) % self.size
            if idx == start_idx:
                return False  # Table full
        self.table[idx] = key
        return True

ht = LinearProbingHashTable(10)
for key in [10, 22, 31, 4, 15]:
    ht.insert(key)
print(ht.table)

A [10, 31, 22, null, 4, 15, null, null, null, null]

B [10, null, null, null, 4, 15, null, null, null, 31]

C [10, 22, 31, 4, 15, null, null, null, null, null]

D [10, 22, null, 31, 4, 15, null, null, null, null]

💡 Hint

Remember to check the next slot if the calculated index is already occupied.

The hash function is key % 10. Insert 10 at index 0, 22 at index 2 (since 2 is free), 31 at index 1 (since 1 is free), 4 at index 4, and 15 at index 5.

❓ Predict Output

intermediate

Result of Searching in Linear Probing Hash Table

Given a hash table of size 7 with keys inserted using linear probing and hash function h(k) = k % 7, what is the output of searching for key 20 after inserting keys 10, 20, 15, 7?

DSA Python

class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None:
            idx = (idx + 1) % self.size
            if idx == start_idx:
                return False
        self.table[idx] = key
        return True

    def search(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None:
            if self.table[idx] == key:
                return idx
            idx = (idx + 1) % self.size
            if idx == start_idx:
                break
        return -1

ht = LinearProbingHashTable(7)
for key in [10, 20, 15, 7]:
    ht.insert(key)
print(ht.search(20))

A 1

B 6

C -1

D 5

💡 Hint

Check where 20 is inserted after collisions.

20 hashes to index 6 (20 % 7 = 6). Since index 6 is free, 20 is inserted there. So search returns 6.

❓ Predict Output

advanced

State of Hash Table After Deletions Using Linear Probing

What is the state of the hash table after inserting keys 5, 12, 14, 23 into a size 10 table using linear probing and then deleting key 12?

DSA Python

class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        self.deleted = object()

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None and self.table[idx] != self.deleted:
            idx = (idx + 1) % self.size
            if idx == start_idx:
                return False
        self.table[idx] = key
        return True

    def delete(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None:
            if self.table[idx] == key:
                self.table[idx] = self.deleted
                return True
            idx = (idx + 1) % self.size
            if idx == start_idx:
                break
        return False

ht = LinearProbingHashTable(10)
for key in [5, 12, 14, 23]:
    ht.insert(key)
ht.delete(12)
print(ht.table)

A [null, null, null, null, null, 5, 12, 14, 23, null]

B [null, null, <deleted>, null, 23, 5, null, null, null, null]

C [null, null, null, null, null, 5, null, 14, 23, null]

D [null, null, <deleted>, 23, 14, 5, null, null, null, null]

💡 Hint

Deleted slots are marked specially to avoid breaking search chains.

5 hashes to index 5, 12 to 2, 14 to 4 (free), 23 to 3 (free). After deletion, index 2 is marked as .

🧠 Conceptual

advanced

Why Use a Deleted Marker in Linear Probing?

Why do we use a special 'deleted' marker instead of setting a slot to None when deleting a key in linear probing?

A To save memory by reusing the slot immediately for new insertions.

B To avoid the need for rehashing the entire table after deletion.

C To prevent breaking the search chain so that other keys inserted after collisions can still be found.

D To speed up insertion by skipping deleted slots during probing.

💡 Hint

Think about what happens if a search encounters an empty slot.

If a slot is set to None on deletion, searches for keys inserted after that slot would stop early, missing keys. Using a deleted marker keeps the search chain intact.

❓ Predict Output

expert

Final Hash Table After Complex Insertions and Deletions

Given a hash table of size 7 using linear probing with hash function h(k) = k % 7, after inserting keys [10, 20, 15, 7, 14] and deleting keys [20, 7], what is the final state of the table?

DSA Python

class LinearProbingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
        self.deleted = object()

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None and self.table[idx] != self.deleted:
            idx = (idx + 1) % self.size
            if idx == start_idx:
                return False
        self.table[idx] = key
        return True

    def delete(self, key):
        idx = self.hash(key)
        start_idx = idx
        while self.table[idx] is not None:
            if self.table[idx] == key:
                self.table[idx] = self.deleted
                return True
            idx = (idx + 1) % self.size
            if idx == start_idx:
                break
        return False

ht = LinearProbingHashTable(7)
for key in [10, 20, 15, 7, 14]:
    ht.insert(key)
for key in [20, 7]:
    ht.delete(key)
print(ht.table)

A [<deleted>, 15, 14, 10, null, null, <deleted>]

B [null, 15, 14, <deleted>, 10, <deleted>, null]

C [null, 15, 14, null, 10, null, <deleted>]

D [null, 15, 14, <deleted>, 10, null, <deleted>]

💡 Hint

Trace each insertion and deletion carefully, noting the deleted markers.

Insertions: 10 at 3, 20 at 6, 15 at 1, 7 at 0, 14 at 2 (0 and 1 occupied). Deletions: 20 at 6 and 7 at 0 marked deleted. Final table: at 0 and 6, 15 at 1, 14 at 2, 10 at 3, null elsewhere.

Practice

1. What is the main idea behind linear probing in collision handling for hash tables?

easy

A. Double the size of the hash table when a collision occurs.

B. If a slot is occupied, check the next slot sequentially until an empty one is found.

C. Use a linked list at each slot to store multiple elements.

D. Rehash all elements using a new hash function.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in order if the original slot is taken.

2. Step 2: Compare with other methods

   Other methods like chaining use linked lists, resizing, or rehashing, which are different from linear probing.

3. Final Answer:

   If a slot is occupied, check the next slot sequentially until an empty one is found. -> Option B

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot until free [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing resizes the table
• Assuming rehashing is part of linear probing

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size m when a collision occurs at index i?

easy

A. (i + 2) % m

B. (i * 2) % m

C. (i + 1) % m

D. (i - 1) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and taking modulo with table size.

2. Step 2: Apply modulo for wrap-around

   Using modulo ensures the index wraps around to the start if it reaches the end of the table.

3. Final Answer:

   (i + 1) % m -> Option C

4. Quick Check:

   Next index = (current + 1) mod size [OK]

Hint: Next slot = (current index + 1) mod table size [OK]

Common Mistakes:

• Adding 2 instead of 1 for next index
• Multiplying index instead of adding
• Not using modulo for wrap-around

3. Consider a hash table of size 5 using linear probing. The hash function is h(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table?

medium

A. [None, None, 7, 12, 17]

B. [7, 12, 17, None, None]

C. [None, 7, 12, 17, None]

D. [7, None, 12, 17, None]

Solution

1. Step 1: Calculate initial positions

   h(7) = 7 % 5 = 2, h(12) = 12 % 5 = 2, h(17) = 17 % 5 = 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is taken, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are taken, so insert at index 4.

3. Final Answer:

   [None, None, 7, 12, 17] -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with linear probing [OK]

Hint: Check hash index, then next free slot sequentially [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not probing to next slot after collision
• Miscomputing hash values

4. The following code snippet tries to insert keys into a hash table using linear probing. What is the bug?

def insert(table, key):
    m = len(table)
    index = key % m
    while table[index] is not None:
        index = (index + 1) % m
    table[index] = key

hash_table = [None]*5
insert(hash_table, 5)
insert(hash_table, 10)
insert(hash_table, 15)
insert(hash_table, 20)
insert(hash_table, 25)
insert(hash_table, 30)

medium

A. Infinite loop if table is full because no stop condition in while loop.

B. No bug; code works correctly for all insertions.

C. Wrong hash function used; should be key // m.

D. Table size should be dynamic, not fixed.

Solution

1. Step 1: Analyze insertion loop

   The while loop continues probing until it finds an empty slot but has no check for full table.

2. Step 2: Identify problem when table is full

   If all slots are occupied, the loop cycles endlessly, causing infinite loop.

3. Final Answer:

   Infinite loop if table is full because no stop condition in while loop. -> Option A

4. Quick Check:

   Full table causes infinite loop without exit [OK]

Hint: Check for full table to avoid infinite loop [OK]

Common Mistakes:

• Assuming hash function is wrong
• Ignoring infinite loop possibility
• Thinking dynamic size fixes this bug

5. You have a hash table of size 7 using linear probing. Insert keys [14, 21, 28, 35, 42] using hash function h(k) = k % 7. After all insertions, what is the index of key 42 in the table?

hard

A. 5

B. 0

C. 6

D. 4

Solution

1. Step 1: Calculate initial hash indices

   h(14)=0, h(21)=0, h(28)=0, h(35)=0, h(42)=0 (all keys hash to index 0).

2. Step 2: Insert keys using linear probing

   Insert 14 at 0. For 21, index 0 taken, try 1. Insert 21 at 1. For 28, indices 0 and 1 taken, insert at 2. For 35, insert at 3. For 42, insert at 4.

3. Step 3: Find index of key 42

   Key 42 is at index 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   42 placed at first free slot after collisions [OK]

Hint: All keys collide; count steps from initial index [OK]

Common Mistakes:

• Assuming key stays at initial hash index
• Not probing sequentially after collisions
• Miscounting index after multiple collisions