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.

Practice

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

easy

A. If a collision occurs, check the next slot sequentially until an empty slot is found.

B. Use a linked list to store multiple elements at the same index.

C. Double the size of the hash table when a collision happens.

D. Rehash all elements using a new hash function when a collision occurs.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in the array sequentially when the desired slot is occupied.

2. Step 2: Compare options with definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes this sequential checking. Other options describe different collision handling methods.

3. Final Answer:

   If a collision occurs, check the next slot sequentially until an empty slot is found. -> Option A

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking rehashing happens on every collision
• Assuming table size doubles automatically

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 current index is i?

easy

A. next_index = (i + 3) % m

B. next_index = (i * 2) % m

C. next_index = (i - 1) % m

D. next_index = (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: Match formula with options

   next_index = (i + 1) % m matches this formula: (i + 1) % m. Other options use incorrect increments.

3. Final Answer:

   next_index = (i + 1) % m -> Option D

4. Quick Check:

   Linear probing next index = (i + 1) mod m [OK]

Hint: Linear probing adds 1 to index modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Subtracting instead of adding
• Adding a number other than 1

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. [7, 12, 17, null, null]

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

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

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

Solution

1. Step 1: Calculate initial positions using hash function

   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 occupied, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are occupied, so insert at index 4.

3. Final Answer:

   [null, null, 7, 12, 17] -> Option C

4. Quick Check:

   Keys placed at 2, 3, 4 sequentially [OK]

Hint: Check hash index, then next slots if occupied [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not wrapping around table size
• Misplacing keys at wrong indices

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

int hash(int key, int size) { return key % size; }
void insert(int table[], int size, int key) {
  int index = hash(key, size);
  while (table[index] != -1) {
    index = (index + 1) % size;
  }
  table[index] = key;
}

medium

A. The index update should subtract 1 instead of adding 1.

B. The table is not initialized with -1 for empty slots.

C. The while loop condition should check for table[index] == -1.

D. The hash function should use multiplication instead of modulo.

Solution

1. Step 1: Analyze the insert function logic

   The function checks for empty slots by comparing with -1, so the table must be initialized with -1 to mark empty slots.

2. Step 2: Identify missing initialization

   If the table is not initialized with -1, the condition table[index] != -1 may fail incorrectly, causing wrong insertions or infinite loops.

3. Final Answer:

   The table is not initialized with -1 for empty slots. -> Option B

4. Quick Check:

   Empty slots must be marked -1 [OK]

Hint: Initialize table slots with -1 before insertion [OK]

Common Mistakes:

• Ignoring table initialization
• Wrong loop condition in while
• Incorrect hash function usage

5. You have a hash table of size 7 using linear probing. Insert keys 10, 20, 15, 7, 32 in order using hash function h(k) = k % 7. After all insertions, what is the content of the table?

hard

A. [7, 15, null, 10, 32, null, 20]

B. [null, 15, 32, 10, null, 20, 7]

C. [null, 15, 32, 10, 20, 7, null]

D. [null, 15, 32, 10, 20, null, 7]

Solution

1. Step 1: Calculate initial indices for each key

   h(10)=3, h(20)=6, h(15)=1, h(7)=0, h(32)=4.

2. Step 2: Insert keys using linear probing

   Insert 10 at index 3. Insert 20 at index 6. Insert 15 at index 1. Insert 7 at index 0. Insert 32 at index 4 (empty). Final table: [7, 15, null, 10, 32, null, 20].

3. Step 3: Match with options

   [7, 15, null, 10, 32, null, 20] matches the correct order. Nulls at indices 2 and 5.

4. Final Answer:

   [7, 15, null, 10, 32, null, 20] -> Option A

5. Quick Check:

   Keys placed at their hash or next free slot [OK]

Hint: Calculate hash, insert or probe next free slot [OK]

Common Mistakes:

• Not probing when slot is occupied
• Misplacing keys at wrong indices
• Ignoring table size wrap-around