Collision Handling Using Chaining in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the hash table with empty chains.

DSA Go

hashTable := make([][]int, [1])

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

A10

B5

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 creates no chains, so no place to store data.

Using 1 creates only one chain, which defeats chaining benefits.

The hash table size is set to 5 to create 5 chains (buckets) for collision handling.

2fill in blank

medium

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

DSA Go

index := key [1] len(hashTable)

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

A/

B*

C+

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Using * or + changes the index unpredictably.

Using / gives a float, which is invalid for indexing.

The modulo operator (%) ensures the index fits within the hash table size.

3fill in blank

hard

Fix the error in the code to append a key to the correct chain.

DSA Go

hashTable[index] = append(hashTable[[1]], key)

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

Aindex

Bkey

ChashTable

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using the key as index causes runtime errors.

Using the whole hashTable as index is invalid.

We append the key to the chain at position 'index' in the hash table.

4fill in blank

hard

Fill both blanks to check if a key exists in the chain.

DSA Go

for _, v := range hashTable[[1]] {
    if v [2] key {
        return true
    }
}

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

Aindex

B==

C!=

Dkey

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' reverses the logic and never finds the key.

Using 'key' as index causes errors.

We loop over the chain at 'index' and check if any value equals the key.

5fill in blank

hard

Fill all three blanks to remove a key from the chain correctly.

DSA Go

chain := hashTable[[1]]
for i, v := range chain {
    if v [2] key {
        hashTable[[3]] = append(chain[:i], chain[i+1:]...)
        break
    }
}

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

Aindex

B==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' causes the wrong element to be removed.

Using wrong index in assignment breaks the chain.

We find the key in the chain at 'index' and remove it by slicing out the element.

Practice

1. What is the main idea behind collision handling using chaining in hash tables?

easy

A. Use open addressing to find another empty slot

B. Resize the hash table to avoid collisions

C. Store multiple elements in a linked list at the same index when collisions occur

D. Ignore collisions and overwrite existing data

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index.

3. Final Answer:

   Store multiple elements in a linked list at the same index when collisions occur -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked lists at each index [OK]

Common Mistakes:

• Thinking chaining resizes the table
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following is the correct way to declare a hash table with chaining in Go using slices of linked lists?

easy

A. var table [10]*Node

B. var table = make([]*Node, 10)

C. var table = make(map[int]*Node)

D. var table = [10]Node{}

Solution

1. Step 1: Understand Go slice declaration for chaining

   Chaining uses a slice of pointers to linked list nodes for dynamic size.

2. Step 2: Identify correct syntax

   Using make([]*Node, 10) creates a slice of 10 pointers to Node, suitable for chaining.

3. Final Answer:

   var table = make([]*Node, 10) -> Option B

4. Quick Check:

   Slice of pointers = make([]*Node, size) [OK]

Hint: Use make([]*Node, size) for chaining table [OK]

Common Mistakes:

• Using arrays instead of slices limits flexibility
• Using map instead of slice for chaining
• Declaring slice without make causes nil slice

3. Consider the following Go code snippet for inserting keys into a hash table with chaining. What will be the output after inserting keys 5 and 15 if the hash function is key % 10?

type Node struct {
    key  int
    next *Node
}

func insert(table []*Node, key int) {
    index := key % 10
    newNode := &Node{key: key}
    newNode.next = table[index]
    table[index] = newNode
}

func printTable(table []*Node) {
    for i, node := range table {
        print(i, ": ")
        for n := node; n != nil; n = n.next {
            print(n.key, " -> ")
        }
        println("nil")
    }
}

func main() {
    table := make([]*Node, 10)
    insert(table, 5)
    insert(table, 15)
    printTable(table)
}

medium

A. 15 -> 5 -> nil at index 5

B. 15 -> nil at index 5 and 5 -> nil at index 5

C. 5 -> nil at index 5 and 15 -> nil at index 5

D. 5 -> 15 -> nil at index 5

Solution

1. Step 1: Calculate hash index for keys 5 and 15

   Both 5 % 10 and 15 % 10 equal 5, so both keys go to index 5.

2. Step 2: Trace insertion order in chaining

   First insert 5 at index 5, then insert 15 which becomes new head pointing to 5.

3. Final Answer:

   15 -> 5 -> nil at index 5 -> Option A

4. Quick Check:

   New nodes added at head = 15 first [OK]

Hint: New nodes go to head of list in chaining [OK]

Common Mistakes:

• Assuming insertion appends at tail
• Mixing up hash index calculation
• Printing nodes in wrong order

4. The following Go code tries to insert keys into a hash table with chaining but causes a runtime panic. What is the error?

type Node struct {
    key  int
    next *Node
}

func insert(table []*Node, key int) {
    index := key % len(table)
    if table[index] == nil {
        table[index].key = key
    } else {
        newNode := &Node{key: key, next: table[index]}
        table[index] = newNode
    }
}

func main() {
    table := make([]*Node, 10)
    insert(table, 7)
}

medium

A. Nil pointer dereference when assigning to table[index].key

B. Index out of range error due to wrong hash calculation

C. Infinite loop in insert function

D. Compilation error due to missing return statement

Solution

1. Step 1: Analyze the nil check and assignment

   If table[index] is nil, trying to assign table[index].key causes nil pointer dereference.

2. Step 2: Understand pointer initialization requirement

   Must create a new Node and assign pointer to table[index] before setting key.

3. Final Answer:

   Nil pointer dereference when assigning to table[index].key -> Option A

4. Quick Check:

   Assigning field on nil pointer causes panic [OK]

Hint: Initialize pointer before assigning fields [OK]

Common Mistakes:

• Ignoring nil pointer before field assignment
• Assuming slice elements auto-initialize
• Confusing compile error with runtime panic

5. You want to implement a hash table with chaining in Go that supports deletion of keys. Which approach correctly removes a key from the chain at the hashed index?

hard

A. Replace the key with zero but keep the node in the list

B. Set the entire linked list at the index to nil to remove the key

C. Resize the hash table and rehash all keys except the one to delete

D. Traverse the linked list at the index, keep track of previous node, and adjust pointers to skip the node with the key

Solution

1. Step 1: Understand deletion in chaining

   To delete a key, find it in the linked list and remove its node by adjusting pointers.

2. Step 2: Why other options fail

   Setting entire list to nil removes all keys, replacing key with zero keeps node, resizing is inefficient.

3. Final Answer:

   Traverse the linked list at the index, keep track of previous node, and adjust pointers to skip the node with the key -> Option D

4. Quick Check:

   Proper deletion adjusts pointers in linked list [OK]

Hint: Delete by pointer adjustment in linked list [OK]

Common Mistakes:

• Removing entire chain instead of one key
• Leaving empty nodes with zero keys
• Rehashing unnecessarily on deletion