Collision Handling Using Open Addressing Linear Probing in DSA Go - 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 using linear probing with a table size of 7?

DSA Go

package main
import "fmt"
func main() {
  size := 7
  table := make([]int, size)
  for i := range table {
    table[i] = -1
  }
  keys := []int{10, 22, 31, 4, 15}
  for _, key := range keys {
    index := key % size
    for table[index] != -1 {
      index = (index + 1) % size
    }
    table[index] = key
  }
  fmt.Println(table)
}

A [-1, 22, 15, 10, 31, 4, -1]

B [-1, 10, 22, 31, 4, 15, -1]

C [10, -1, 22, 31, 4, 15, -1]

D [10, 22, 31, 4, 15, -1, -1]

💡 Hint

Remember to check for collisions and move to the next empty slot.

Each key is inserted at index = key % size. If occupied, move to next index until empty.

10 % 7 = 3 → slot 3 empty → insert 10 at 3

22 % 7 = 1 → slot 1 empty → insert 22 at 1

31 % 7 = 3 → slot 3 occupied → move to 4 empty → insert 31 at 4

4 % 7 = 4 → slot 4 occupied → move to 5 empty → insert 4 at 5

15 % 7 = 1 → slot 1 occupied → move to 2 empty → insert 15 at 2

🧠 Conceptual

intermediate

Understanding Linear Probing Collision Resolution

Why does linear probing cause clustering in a hash table?

A Because it rehashes keys with a different hash function.

B Because it uses a random slot for collisions, spreading keys evenly.

C Because it places collided keys in the next available slot, causing groups of filled slots.

D Because it deletes collided keys to avoid clustering.

💡 Hint

Think about how keys are placed when collisions happen.

Linear probing places collided keys in the next free slot, which can create long runs of occupied slots called clustering.

🔧 Debug

advanced

Find the Bug in Linear Probing Insert Function

What error will this Go code produce when inserting keys into a hash table using linear probing?

DSA Go

package main
import "fmt"
func insert(table []int, key int) {
  size := len(table)
  index := key % size
  for table[index] != -1 {
    index = (index + 1) % size
  }
  table[index] = key
}
func main() {
  table := []int{-1, -1, -1}
  insert(table, 1)
  insert(table, 4)
  insert(table, 7)
  insert(table, 10)
  fmt.Println(table)
}

A Infinite loop

B Runtime error: index out of range

C [1 4 7]

D [1 4 7 10]

💡 Hint

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

The insert function loops until it finds an empty slot. If the table is full, it loops forever causing an infinite loop.

❓ Predict Output

advanced

Result of Deletion in Linear Probing Hash Table

Given a linear probing hash table with size 5 and keys inserted: 1, 6, 11. After deleting key 6, what is the state of the table?

DSA Go

package main
import "fmt"
func main() {
  size := 5
  table := make([]int, size)
  for i := range table {
    table[i] = -1
  }
  keys := []int{1, 6, 11}
  for _, key := range keys {
    index := key % size
    for table[index] != -1 {
      index = (index + 1) % size
    }
    table[index] = key
  }
  // Delete key 6
  for i := 0; i < size; i++ {
    if table[i] == 6 {
      table[i] = -2 // mark deleted
      break
    }
  }
  fmt.Println(table)
}

A [-1, 1, 6, 11, -1]

B [-1, 1, -2, 11, -1]

C [-1, 1, -1, 11, -1]

D [-1, -2, 1, 11, -1]

💡 Hint

Deleted slots are marked differently to distinguish from empty slots.

Key 1 at index 1, key 6 at index 2, key 11 at index 3.

Deleting 6 marks index 2 as -2 (deleted).

🧠 Conceptual

expert

Why Use a Special Marker for Deleted Slots in Linear Probing?

Why do we mark deleted slots with a special value (like -2) instead of setting them to empty (-1) in linear probing hash tables?

A To speed up the insertion by skipping deleted slots.

B To free memory immediately after deletion.

C To prevent any further insertions in that slot.

D To ensure search continues past deleted slots to find keys inserted later.

💡 Hint

Think about how searching works in linear probing after deletions.

Marking deleted slots differently allows the search to continue probing past deleted slots to find keys that may be further down the line.

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 at each slot to store multiple elements.

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

D. Replace the existing element in the slot with the new one.

Solution

1. Step 1: Understand collision handling

   When two keys hash to the same slot, a collision occurs and must be resolved.

2. Step 2: Explain linear probing method

   Linear probing resolves collisions by checking the next slot in order until an empty one is found.

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 checks next slots one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing replaces existing elements
• Assuming table size doubles on collision

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. (i + 1) % m

B. (i + 3) % m

C. (i - 1) % m

D. (i * 2) % m

Solution

1. Step 1: Understand linear probing index calculation

   Linear probing moves to the next slot by adding 1 to the current index.

2. Step 2: Apply modulo to wrap around

   To stay within table bounds, use modulo with table size: (i + 1) % m.

3. Final Answer:

   (i + 1) % m -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo causing out-of-bound errors
• Subtracting instead of adding for next slot

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

medium

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

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

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

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

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 check index 3 (empty), insert 12. For 17, indexes 2 and 3 taken, check index 4 (empty), insert 17.

3. Final Answer:

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

4. Quick Check:

   All keys placed sequentially after collision [OK]

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

Common Mistakes:

• Placing keys at wrong indices ignoring collisions
• Not applying modulo for hash function
• Assuming keys overwrite existing ones

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

func insert(table []int, key int) {
    m := len(table)
    index := key % m
    for table[index] != -1 {
        index = (index + 1) % m
    }
    table[index] = key
}

// Initial table: [-1, -1, -1, -1, -1]
// Insert keys: 3, 8, 13

medium

A. The loop condition should check for zero instead of -1.

B. The code does not handle the case when the table is full, causing an infinite loop.

C. The initial table should be initialized with zeros, not -1.

D. The modulo operation should be done with key, not m.

Solution

1. Step 1: Analyze loop condition and termination

   The loop continues while the slot is occupied (not -1). If the table is full, the loop never ends.

2. Step 2: Identify missing full table check

   There is no check to stop after probing all slots, so infinite loop can occur if table is full.

3. Final Answer:

   The code does not handle the case when the table is full, causing an infinite loop. -> Option B

4. Quick Check:

   Missing full table check causes infinite loop [OK]

Hint: Always check for full table to avoid infinite loops [OK]

Common Mistakes:

• Ignoring full table condition
• Confusing initial empty slot value
• Misusing modulo operation

5. You have a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. You insert keys 10, 20, 15, 7, 32 in this order. After these insertions, you want to insert key 24. Which index will key 24 be placed at?

hard

A. Index 3

B. Index 4

C. Index 5

D. Index 6

Solution

1. Step 1: Insert keys and find their positions

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

2. Step 2: Find position for key 24

   h(24)=3, but index 3 occupied by 10. Check next index 4 (occupied by 32), then 5 (empty), so insert at 5.

3. Final Answer:

   Index 5 -> Option C

4. Quick Check:

   Linear probe from 3 to 5 for key 24 [OK]

Hint: Probe next slots until empty found [OK]

Common Mistakes:

• Stopping at first collision without probing
• Not applying modulo for wrap-around
• Misplacing keys ignoring occupied slots