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 hash(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 multiplication (*) instead of modulo (%) causes index out of bounds.

Using addition (+) or subtraction (-) does not limit the index properly.

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

2fill in blank

medium

Complete the code to find the next index using linear probing.

DSA C

int next_index(int current, int size) {
    return (current [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 causes backward probing which is not standard.

Multiplying or dividing the index is incorrect for linear probing.

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

3fill in blank

hard

Fix the error in the insertion loop to handle collisions correctly.

DSA C

while (table[index] != -1) {
    index = (index [1] 1) % size;
}

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.

Multiplication or division is not suitable for linear probing.

To resolve collisions, we move forward by adding 1 to the index and wrap around.

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 = key [1] size;
    int start = index;
    while (table[index] != key) {
        index = (index [2] 1) % size;
        if (index == start) return -1;
    }
    return index;
}

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

A%

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction for probing causes wrong search path.

Using multiplication or division breaks index calculation.

Hash index is calculated using modulo (%), and linear probing moves forward by adding 1 (+).

5fill in blank

hard

Fill both blanks to complete the insertion function with linear probing collision handling.

DSA C

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

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

A%

B+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication in index calculation.

Adding operators when assigning key causes syntax errors.

Index is calculated with modulo (%), linear probing adds 1 (+), and key is assigned directly without extra operators.

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