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.