Collision Handling Using Open Addressing Linear Probing in DSA Typescript - 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 into an empty hash table of size 7 using linear probing?

DSA Typescript

class HashTable {
  size: number;
  table: (number | null)[];

  constructor(size: number) {
    this.size = size;
    this.table = Array(size).fill(null);
  }

  hash(key: number): number {
    return key % this.size;
  }

  insert(key: number): void {
    let idx = this.hash(key);
    while (this.table[idx] !== null) {
      idx = (idx + 1) % this.size;
    }
    this.table[idx] = key;
  }
}

const ht = new HashTable(7);
[10, 22, 31, 4, 15].forEach(k => ht.insert(k));
console.log(ht.table);

A [10, 22, 31, 4, 15, null, null]

B [null, 22, 15, 10, 31, 4, null]

C [10, null, 22, 31, 4, 15, null]

D [null, null, 10, 22, 31, 4, 15]

💡 Hint

Remember to compute the hash index and then probe linearly until an empty slot is found.

Each key is inserted at its hash index (key % 7). If occupied, linear probing moves to the next slot.

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

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

31 % 7 = 3 → slot 3 occupied (10), move to 4 → empty → insert 31 at index 4.

4 % 7 = 4 → slot 4 occupied (31), move to 5 → empty → insert 4 at index 5.

15 % 7 = 1 → slot 1 occupied (22), move to 2 → empty → insert 15 at index 2.

Final table: [null, 22, 15, 10, 31, 4, null]

❓ Predict Output

intermediate

Result of Searching in Linear Probing Hash Table

Given a hash table of size 5 with keys inserted using linear probing: [null, 12, 22, 32, 42], what will be the output of searching for key 42?

DSA Typescript

class HashTable {
  size: number;
  table: (number | null)[];

  constructor(size: number) {
    this.size = size;
    this.table = Array(size).fill(null);
  }

  hash(key: number): number {
    return key % this.size;
  }

  search(key: number): number {
    let idx = this.hash(key);
    let start = idx;
    while (this.table[idx] !== null) {
      if (this.table[idx] === key) return idx;
      idx = (idx + 1) % this.size;
      if (idx === start) break;
    }
    return -1;
  }
}

const ht = new HashTable(5);
ht.table = [null, 12, 22, 32, 42];
console.log(ht.search(42));

A 3

B 0

C -1

D 4

💡 Hint

Check the hash index and probe until you find the key or return -1.

Hash of 42 is 42 % 5 = 2.

Check index 2: 22 (not 42), move to 3: 32 (not 42), move to 4: 42 (found).

Return index 4.

🔧 Debug

advanced

Identify the Bug in Linear Probing Insert Method

What error will occur when running this insert method for linear probing in a hash table of fixed size?

DSA Typescript

insert(key: number): void {
  let idx = this.hash(key);
  while (this.table[idx] !== null) {
    idx = (idx + 1) % this.size;
  }
  this.table[idx] = key;
}

// Assume this.table is full and insert is called.

A No error, key inserted successfully

B Index out of bounds error

C Infinite loop

D TypeError

💡 Hint

What happens if the table is full and no empty slot is found?

If the table is full, the while loop cycles through all indices endlessly because no null slot is found.

This causes an infinite loop.

🧠 Conceptual

advanced

Why Use Linear Probing in Open Addressing?

Which of the following best explains the main advantage of linear probing in open addressing hash tables?

A It is simple and uses sequential slots to resolve collisions

B It uses linked lists to handle collisions efficiently

C It reduces clustering by spreading keys evenly

D It guarantees no collisions will occur

💡 Hint

Think about how linear probing finds the next slot.

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

This simplicity is its main advantage.

🚀 Application

expert

Final Hash Table State After Mixed Operations

Given a hash table of size 5 using linear probing, starting empty, perform these operations in order: insert 7, insert 12, insert 17, delete 12, insert 22. What is the final state of the table?

DSA Typescript

class HashTable {
  size: number;
  table: (number | 'DELETED' | null)[];

  constructor(size: number) {
    this.size = size;
    this.table = Array(size).fill(null);
  }

  hash(key: number): number {
    return key % this.size;
  }

  insert(key: number): void {
    let idx = this.hash(key);
    while (this.table[idx] !== null && this.table[idx] !== 'DELETED') {
      idx = (idx + 1) % this.size;
    }
    this.table[idx] = key;
  }

  delete(key: number): void {
    let idx = this.hash(key);
    let start = idx;
    while (this.table[idx] !== null) {
      if (this.table[idx] === key) {
        this.table[idx] = 'DELETED';
        return;
      }
      idx = (idx + 1) % this.size;
      if (idx === start) break;
    }
  }
}

const ht = new HashTable(5);
ht.insert(7);
ht.insert(12);
ht.insert(17);
ht.delete(12);
ht.insert(22);
console.log(ht.table);

A [null, null, 7, 22, 17]

B [7, 22, 17, null, 'DELETED']

C [7, 22, 17, 'DELETED', null]

D [7, null, 17, 22, 'DELETED']

💡 Hint

Remember that deleted slots can be reused for insertion but are marked as 'DELETED'.

Insert 7: 7 % 5 = 2 → slot 2 empty → insert at 2.

Insert 12: 12 % 5 = 2 → slot 2 occupied, move to 3 → empty → insert at 3.

Insert 17: 17 % 5 = 2 → slots 2 and 3 occupied, move to 4 → empty → insert at 4.

Delete 12: search from 2 → 2(7 no), 3(12 yes) → mark 3 as 'DELETED'.

Insert 22: 22 % 5 = 2 → 2 occupied, 3 'DELETED' → reuse 3 for 22.

Final table: [null, null, 7, 22, 17]

Practice

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

easy

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

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

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

D. Replace the existing value at the collided slot with the new value.

Solution

1. Step 1: Understand collision handling

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain linear probing method

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

3. Final Answer:

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

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
• Replacing existing values on collision

2. Which of the following TypeScript code snippets correctly implements the linear probing step to find the next index after a collision in a hash table of size size?

easy

A. let nextIndex = currentIndex % size;

B. let nextIndex = (currentIndex * 2) % size;

C. let nextIndex = (currentIndex - 1) % size;

D. let nextIndex = (currentIndex + 1) % size;

Solution

1. Step 1: Understand linear probing index calculation

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

2. Step 2: Check code correctness

   let nextIndex = (currentIndex + 1) % size; correctly calculates nextIndex as (currentIndex + 1) % size, ensuring wrap-around.

3. Final Answer:

   let nextIndex = (currentIndex + 1) % size; -> Option D

4. Quick Check:

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

Hint: Add 1 and mod by size for next slot [OK]

Common Mistakes:

• Multiplying index instead of adding
• Subtracting index causing negative values
• Not using modulo for wrap-around

3. Consider a hash table of size 5 using linear probing. The hash function is h(key) = key % 5. Insert keys in this order: 7, 12, 17. What is the final state of the hash table (index: value)?

medium

A. {0: null, 1: null, 2: 7, 3: 12, 4: 17}

B. {0: 17, 1: 7, 2: 12, 3: null, 4: null}

C. {0: 12, 1: 17, 2: 7, 3: null, 4: null}

D. {0: null, 1: 7, 2: null, 3: 12, 4: 17}

Solution

1. Step 1: Calculate initial hash indices

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys hash to index 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is occupied, try 3 (empty), insert 12. For 17, indices 2 and 3 occupied, try 4 (empty), insert 17.

3. Final Answer:

   {0: null, 1: null, 2: 7, 3: 12, 4: 17} -> Option A

4. Quick Check:

   All keys start at 2, linear probe fills next slots [OK]

Hint: All keys hash same, fill next slots sequentially [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Not wrapping around the table
• Misplacing keys at wrong indices

4. The following TypeScript code tries to insert keys into a hash table using linear probing. What is the bug that causes an infinite loop?

const size = 5;
const table = new Array(size).fill(null);
function hash(key: number) { return key % size; }
function insert(key: number) {
  let index = hash(key);
  while (table[index] !== null) {
    index = (index + 1) % size;
  }
  table[index] = key;
}
insert(5);
insert(10);
insert(15);
insert(20);
insert(25);
insert(30);

medium

A. No check for full table causing infinite loop when table is full.

B. Hash function is incorrect and returns negative indices.

C. Array initialization with null is wrong; should use undefined.

D. Insert function does not update index inside the loop.

Solution

1. Step 1: Analyze insert loop behavior

   The while loop keeps moving index until an empty slot is found.

2. Step 2: Identify missing full table check

   If the table is full, the loop cycles endlessly without exit condition.

3. Final Answer:

   No check for full table causing infinite loop when table is full. -> Option A

4. Quick Check:

   Full table without exit causes infinite loop [OK]

Hint: Add full table check to avoid infinite loop [OK]

Common Mistakes:

• Assuming hash function returns negative
• Thinking null vs undefined causes loop
• Forgetting to update index inside loop

5. You have a hash table of size 7 using linear probing. The hash function is h(key) = key % 7. You insert keys: 14, 21, 28, 35, 42. Then you delete key 21. What is the correct way to handle deletion to avoid search errors in linear probing?

hard

A. Set the slot to null immediately to free it for new insertions.

B. Mark the slot as a special 'deleted' marker instead of null to continue probing.

C. Rehash the entire table after deletion to fix collisions.

D. Do nothing; deletion is not needed in linear probing.

Solution

1. Step 1: Understand deletion problem in linear probing

   Setting slot to null breaks the probe chain, causing search failures for keys after deleted slot.

2. Step 2: Use special 'deleted' marker

   Marking slot as 'deleted' allows probing to continue while allowing new insertions.

3. Final Answer:

   Mark the slot as a special 'deleted' marker instead of null to continue probing. -> Option B

4. Quick Check:

   Deleted marker keeps probe chain intact [OK]

Hint: Use 'deleted' marker slot, not null, after deletion [OK]

Common Mistakes:

• Setting slot to null breaks search chain
• Rehashing entire table unnecessarily
• Ignoring deletion impact on probing