Collision Handling Using Open Addressing Linear Probing in DSA C - 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 5, 15, 25 into an empty table of size 10 using linear probing with hash function h(k) = k % 10?

DSA C

int table[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int keys[] = {5, 15, 25};
for(int i=0; i<3; i++) {
    int key = keys[i];
    int idx = key % 10;
    while(table[idx] != -1) {
        idx = (idx + 1) % 10;
    }
    table[idx] = key;
}
// Print table contents

A [ -1, -1, -1, -1, -1, 5, -1, -1, 15, 25 ]

B [ -1, -1, -1, -1, -1, 5, -1, 15, 25, -1 ]

C [ -1, -1, -1, -1, -1, 5, 15, -1, 25, -1 ]

D [ -1, -1, -1, -1, -1, 5, 15, 25, -1, -1 ]

💡 Hint

Remember linear probing moves to the next index if the current is occupied.

Each key hashes to index 5 (5 % 10 = 5, 15 % 10 = 5, 25 % 10 = 5). The first key 5 is placed at index 5. The next key 15 finds index 5 occupied, so it moves to index 6. The key 25 finds indices 5 and 6 occupied, so it moves to index 7.

❓ 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 index returned when searching for key 24 if the table contains keys [10, 3, 17, 24] inserted in that order?

DSA C

int table[7] = {-1,-1,-1,-1,-1,-1,-1};
int keys[] = {10, 3, 17, 24};
for(int i=0; i<4; i++) {
    int key = keys[i];
    int idx = key % 7;
    while(table[idx] != -1) {
        idx = (idx + 1) % 7;
    }
    table[idx] = key;
}
// Search for 24
int search_key = 24;
int idx = search_key % 7;
int start = idx;
while(table[idx] != search_key) {
    idx = (idx + 1) % 7;
    if(idx == start) {
        idx = -1; // not found
        break;
    }
}
// idx is the result

A 6

B 3

C 5

D -1

💡 Hint

Trace the insertion positions first, then search accordingly.

Keys inserted: 10 at index 3 (10 % 7 = 3), 3 at index 3 occupied, so index 4, 17 at index 3 and 4 occupied, so index 5, 24 at index 3,4,5 occupied, so index 6. Searching 24 starts at index 3, moves to 4, 5, then finds 24 at index 6.

🔧 Debug

advanced

Identify the Bug in Linear Probing Insertion

What error will occur when running this code snippet for linear probing insertion in a hash table of size 5?

DSA C

int table[5] = {-1,-1,-1,-1,-1};
int key = 12;
int idx = key % 5;
while(table[idx] != -1) {
    idx = (idx + 1) % 5;
}
table[idx] = key;
// Insert keys 12, 7, 2, 17, 22, 27 sequentially using this logic

A Infinite loop occurs when table is full

B Segmentation fault due to invalid memory access

C Array index out of bounds error

D Runs successfully, table stores all keys

💡 Hint

What happens when the table is full and you keep probing?

The code does not check if the table is full before probing. When all slots are occupied, the while loop cycles endlessly, causing an infinite loop.

🧠 Conceptual

advanced

Effect of Table Size on Linear Probing Performance

Which statement best explains why choosing a prime number as the hash table size improves linear probing performance?

A Prime table size reduces the number of collisions to zero

B Prime table size guarantees that every slot is visited during probing

C Prime table size ensures uniform distribution and avoids clustering

D Prime table size allows the hash function to run faster

💡 Hint

Think about how modulo with prime numbers affects key distribution.

Using a prime number as table size helps distribute keys more uniformly and reduces clustering during linear probing, improving performance.

🚀 Application

expert

Final Hash Table State After Mixed Operations

Given an empty hash table of size 7 and hash function h(k) = k % 7, perform these operations in order using linear probing:
Insert 10, Insert 3, Insert 17, Delete 3, Insert 24, Insert 31.
What is the final state of the table? Use -1 for empty slots and -2 for deleted slots.

DSA C

int table[7] = {-1,-1,-1,-1,-1,-1,-1};
// Insert 10
// Insert 3
// Insert 17
// Delete 3
// Insert 24
// Insert 31
// Use linear probing for collisions
// -1 empty, -2 deleted

A [ -1, 31, -1, 10, 17, 24, -2 ]

B [ -1, -1, -1, 10, 24, 17, 31 ]

C [ -1, 31, -2, 10, 17, 24, -1 ]

D [ -1, -2, 31, 10, -2, 24, -1 ]

💡 Hint

Remember to mark deleted slots as -2 and continue probing correctly during insertions.

Insert 10 at index 3 (10 % 7 = 3), insert 3 at index 3 occupied, so index 4, insert 17 at index 5, delete 3 at index 4 (mark -2), insert 24 at index 3,4 occupied (4 is deleted but can be reused), so 24 goes to index 4, insert 31 at index 3,4,5 occupied, so index 6.