Collision Handling Using Open Addressing Linear Probing in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the hash index for a given key.

DSA C++

int hashFunction(int key, int size) {
    return key [1] size;
}

Drag options to blanks, or click blank then click option'

A+

B/

C*

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Using division (/) instead of modulo (%) causes wrong index calculation.

The modulo operator (%) is used to ensure the hash index stays within the table size.

2fill in blank

medium

Complete the code to perform linear probing by moving to the next index.

DSA C++

int linearProbe(int index, int size) {
    return (index [1] 1) % size;
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting 1 moves backward, which is incorrect for linear probing.

Adding 1 moves to the next slot; modulo keeps it within table size.

3fill in blank

hard

Fix the error in the insertion loop to correctly handle collisions using linear probing.

DSA C++

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction causes infinite loops or wrong probing sequence.

We add 1 to index to move to the next slot during collision resolution.

4fill in blank

hard

Fill both blanks to complete the search function using linear probing.

DSA C++

int search(int table[], int size, int key) {
    int index = hashFunction(key, size);
    int start = index;
    while (table[index] != key) {
        index = (index [1] 1) % size;
        if (index == [2]) return -1;
    }
    return index;
}

Drag options to blanks, or click blank then click option'

A+

B-

Cstart

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing index to size instead of start causes incorrect termination.

We increment index by 1 and check if we returned to the start index to stop searching.

5fill in blank

hard

Fill all three blanks to complete the deletion function using linear probing.

DSA C++

void deleteKey(int table[], int size, int key) {
    int index = hashFunction(key, size);
    int start = index;
    while (table[index] != key) {
        index = (index [1] 1) % size;
        if (index == [2]) return; // Key not found
    }
    table[index] = [3]; // Mark slot as empty
}

Drag options to blanks, or click blank then click option'

A+

Bstart

C-1

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong sentinel value instead of -1 causes search errors.

Increment index by 1, stop if back to start, and mark slot as -1 to indicate empty.

Practice

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

easy

A. Rehash all elements to a new table when a collision occurs.

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. If a collision occurs, check the next slot sequentially until an empty slot is found.

Solution

1. Step 1: Understand linear probing concept

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

2. Step 2: Compare with other methods

   Other options describe chaining or resizing, not linear probing.

3. Final Answer:

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

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 collision means resizing immediately
• Assuming random slot 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 current index is i?

easy

A. (i * 2) % m

B. (i + 1) % m

C. (i - 1) % m

D. (i + 3) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index, wrapping around using modulo.

2. Step 2: Verify modulo usage

   Modulo with table size m ensures index stays within bounds.

3. Final Answer:

   (i + 1) % m -> Option B

4. Quick Check:

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

Hint: Next slot in linear probing is (i+1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo to wrap index
• Subtracting instead of adding

3. Consider a hash table of size 7 using linear probing. The hash function is h(k) = k % 7. Insert keys 10, 20, 15 in order. What is the final state of the table (index: value)?

medium

A. 0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20

B. 0: null, 1: null, 2: 15, 3: 10, 4: 20, 5: null, 6: null

C. 0: null, 1: null, 2: 10, 3: 20, 4: 15, 5: null, 6: null

D. 0: null, 1: null, 2: 10, 3: 15, 4: 20, 5: null, 6: null

Solution

1. Step 1: Compute hashes and insert 10

   h(10) = 10 % 7 = 3, index 3 empty, insert 10 at 3.

2. Step 2: Insert 20

   h(20) = 20 % 7 = 6, index 6 empty, insert 20 at 6.

3. Step 3: Insert 15

   h(15) = 15 % 7 = 1, index 1 empty, insert 15 at 1.

4. Final Answer:

   0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20 -> Option A

5. Quick Check:

   Positions 1:15, 3:10, 6:20 [OK]

Hint: Calculate hash, insert keys, probe next if occupied [OK]

Common Mistakes:

• Miscomputing hash values
• Not applying modulo correctly
• Placing keys at wrong indices

4. The following code snippet attempts to insert keys into a hash table using linear probing. Identify the bug:

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;
}

int main() {
  int size = 5;
  int table[5] = {-1, -1, -1, -1, -1};
  insert(table, size, 5);
  insert(table, size, 10);
  insert(table, size, 15);
  insert(table, size, 20);
  insert(table, size, 25);
  insert(table, size, 30);
  return 0;
}

medium

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

B. Hash function is incorrect; should use (key + 1) % size.

C. No bug, code works correctly for all insertions.

D. Array initialization with -1 is invalid in C++.

Solution

1. Step 1: Analyze insertion loop

   The while loop probes next index until an empty slot (-1) is found.

2. Step 2: Check for full table scenario

   If the table is full, the loop will cycle endlessly without a stop condition.

3. Step 3: Confirm other options

   Hash function is correct modulo. Array initialization with -1 is valid. So only infinite loop is the bug.

4. Final Answer:

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

5. Quick Check:

   Full table causes infinite loop in linear probing [OK]

Hint: Check if loop stops when table is full [OK]

Common Mistakes:

• Ignoring full table infinite loop
• Thinking hash function is wrong
• Assuming array init with -1 is invalid

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5, 6. You want to insert key 12 where h(k) = k % 10. If index 2 is occupied, what sequence of indices will be checked before insertion? What index will key 12 be inserted at if indices 2 to 6 are occupied but index 7 is free?

hard

A. Check indices 2, 4, 6, 8; insert at 8

B. Check indices 2, 3, 4; insert at 4

C. Check indices 2, 3, 4, 5, 6, 7; insert at 7

D. Check indices 2, 3, 4, 5, 6; insert at 2

Solution

1. Step 1: Calculate initial index for key 12

   h(12) = 12 % 10 = 2, so start checking at index 2.

2. Step 2: Apply linear probing sequence

   Since indices 2, 3, 4, 5, 6 are occupied, check next indices sequentially: 2, 3, 4, 5, 6, then 7.

3. Step 3: Find first free slot

   Index 7 is free, so insert key 12 at index 7.

4. Final Answer:

   Check indices 2, 3, 4, 5, 6, 7; insert at 7 -> Option C

5. Quick Check:

   Linear probe checks sequential slots until free [OK]

Hint: Probe sequentially until free slot found [OK]

Common Mistakes:

• Skipping indices in probing
• Inserting at first occupied slot
• Not wrapping index with modulo