HashMap Implementation from Scratch in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the map field in the HashMap struct.

DSA Go

type HashMap struct {
    buckets map[int][]KeyValue
}

type KeyValue struct {
    key string
    value string
}

func NewHashMap() *HashMap {
    return &HashMap{
        buckets: [1],
    }
}

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

A[]KeyValue{}

Bmap[int][]KeyValue{}

Cmake(map[int][]KeyValue)

Dmake([]KeyValue, 0)

Attempts:

3 left

💡 Hint

Common Mistakes

Using a slice instead of a map for buckets.

Not initializing the map with make.

Using map literal without make in constructor.

We use make to initialize the map field properly in Go.

2fill in blank

medium

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

DSA Go

func (h *HashMap) hash(key string) int {
    var hash int
    for _, ch := range key {
        hash += int(ch)
    }
    return hash [1] len(h.buckets)
}

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.

Using multiplication which increases the number.

Adding length instead of modulo.

We use modulo operator % to keep the hash index within bucket size.

3fill in blank

hard

Fix the error in the Put method to update the value if key exists or append if not.

DSA Go

func (h *HashMap) Put(key, value string) {
    index := h.hash(key)
    bucket := h.buckets[index]
    for i, kv := range bucket {
        if kv.key == key {
            bucket[i].value = [1]
            h.buckets[index] = bucket
            return
        }
    }
    h.buckets[index] = append(bucket, KeyValue{key, value})
}

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

Akey

Bvalue

Cindex

Dbucket

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning key instead of value.

Assigning index or bucket which are wrong types.

Not updating the map after change.

We assign the new value to the existing key's value field.

4fill in blank

hard

Fill both blanks to complete the Get method that returns the value and a boolean if found.

DSA Go

func (h *HashMap) Get(key string) (string, bool) {
    index := h.hash(key)
    bucket := h.buckets[[1]]
    for _, kv := range bucket {
        if kv.key == [2] {
            return kv.value, true
        }
    }
    return "", false
}

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

Aindex

Bkey

Ch.hash(key)

Dh.buckets

Attempts:

3 left

💡 Hint

Common Mistakes

Using h.hash(key) directly as bucket index in code instead of variable.

Comparing with index instead of key.

Accessing h.buckets incorrectly.

We use index to access the bucket and key to compare keys inside the bucket.

5fill in blank

hard

Fill all three blanks to complete the Remove method that deletes a key from the map.

DSA Go

func (h *HashMap) Remove(key string) {
    index := h.hash(key)
    bucket := h.buckets[index]
    for i, kv := range bucket {
        if kv.key == [1] {
            bucket = append(bucket[:[2]], bucket[[3]:]...)
            h.buckets[index] = bucket
            return
        }
    }
}

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

Akey

Bi

Ci + 1

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Using index instead of i for slicing.

Using i instead of key for comparison.

Incorrect slice indices causing runtime errors.

We compare with key, remove element at index i by slicing before and after i.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store key-value pairs for fast data retrieval

B. To store elements in a sorted order

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand the role of HashMap

   A HashMap stores data as key-value pairs, allowing quick access to values using keys.

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option A

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Confusing HashMap with arrays or lists
• Thinking HashMap stores data in order
• Assuming HashMap is for mathematical operations

2. Which of the following is the correct way to declare a HashMap in Go?

easy

A. var m = make(map[string]int)

B. var m map[string]int = map[string]int

C. var m = map[string]int()

D. var m map[string]int

Solution

1. Step 1: Understand Go map declaration

   In Go, maps are created using make function: make(map[keyType]valueType).

2. Step 2: Check each option

   A declares a nil map which cannot be used for assignments. B has invalid syntax (cannot assign type as value). C has incorrect syntax (cannot call map type as function). D uses make correctly.

3. Final Answer:

   var m = make(map[string]int) -> Option A

4. Quick Check:

   Use make() to create maps in Go [OK]

Hint: Use make(map[key]value) to create HashMap in Go [OK]

Common Mistakes:

• Declaring without initializing (nil map)
• Using map type without literal or make
• Trying to call map as a function

3. What will be the output of the following Go code snippet implementing a simple HashMap?

package main
import "fmt"
func main() {
  m := make(map[string]int)
  m["apple"] = 5
  m["banana"] = 3
  m["apple"] = 7
  fmt.Println(m["apple"])
}

medium

A. 5

B. Compilation error

C. 0

D. 7

Solution

1. Step 1: Analyze map insertions

   Initially, "apple" is set to 5, then updated to 7, so the last value is 7.

2. Step 2: Print the value for key "apple"

   Printing m["apple"] outputs the updated value 7.

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Last assigned value for key is returned [OK]

Hint: Last value assigned to key is stored [OK]

Common Mistakes:

• Assuming first value remains after update
• Confusing zero value with stored value
• Expecting compilation error due to reassignment

4. Identify the error in this Go code implementing a HashMap:

package main
import "fmt"
func main() {
  var m map[string]int
  m["key"] = 10
  fmt.Println(m["key"])
}

medium

A. Key type is incorrect

B. Map is not initialized before use

C. Value type is incorrect

D. Print statement syntax error

Solution

1. Step 1: Check map initialization

   The map variable m is declared but not initialized with make(), so it is nil.

2. Step 2: Understand assignment to nil map

   Assigning to a nil map causes runtime panic because map is not ready to store data.

3. Final Answer:

   Map is not initialized before use -> Option B

4. Quick Check:

   Maps must be initialized with make() before assignment [OK]

Hint: Always initialize map with make() before adding keys [OK]

Common Mistakes:

• Forgetting to initialize map before use
• Assuming declaration alone creates map
• Confusing map initialization with slice

5. You want to implement a HashMap from scratch in Go without using built-in maps. Which of the following is the best approach to handle collisions?

hard

A. Ignore collisions and store only one key-value pair per bucket

B. Overwrite existing key-value pair without checking

C. Use a linked list at each bucket to store multiple key-value pairs

D. Use an array of fixed size without hashing keys

Solution

1. Step 1: Understand collision in HashMap

   When two keys hash to the same bucket, collision occurs and must be handled to store both pairs.

2. Step 2: Evaluate collision handling methods

   Using a linked list at each bucket allows storing multiple pairs safely. Overwriting loses data, ignoring collisions loses data, and fixed arrays without hashing lose efficiency.

3. Final Answer:

   Use a linked list at each bucket to store multiple key-value pairs -> Option C

4. Quick Check:

   Separate chaining with linked lists handles collisions [OK]

Hint: Use linked lists per bucket to handle collisions [OK]

Common Mistakes:

• Overwriting values on collision
• Ignoring collisions causing data loss
• Not using hashing for key distribution