BST vs Hash Map Trade-offs for Ordered Data in DSA Go - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a key into a binary search tree (BST).

DSA Go

func insert(root *Node, key int) *Node {
    if root == nil {
        return &Node{key: key}
    }
    if key [1] root.key {
        root.left = insert(root.left, key)
    } else {
        root.right = insert(root.right, key)
    }
    return root
}

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

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causes wrong tree structure.

In a BST, keys less than the current node go to the left subtree.

2fill in blank

medium

Complete the code to check if a key exists in a hash map.

DSA Go

func containsKey(m map[int]string, key int) bool {
    _, ok := m[1]key
    return ok
}

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

A[

B(

C{

D<-

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses causes syntax errors.

In Go, map keys are accessed using square brackets.

3fill in blank

hard

Fix the error in the BST search function to correctly find a key.

DSA Go

func search(root *Node, key int) bool {
    if root == nil {
        return false
    }
    if key == root.key {
        return true
    } else if key [1] root.key {
        return search(root.left, key)
    } else {
        return search(root.right, key)
    }
}

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

A>

B!=

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' causes search to go wrong subtree.

To search in BST, go left if key is less than current node's key.

4fill in blank

hard

Fill both blanks to create a map from keys to their values only if the key is greater than 10.

DSA Go

filtered := map[int]string{}
for k, v := range data {
    if k [1] 10 {
        filtered[k] = [2]
    }
}

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

A>

Bv

Ck

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' includes wrong keys.

Assigning key instead of value.

We check if key is greater than 10, then assign the value to filtered map.

5fill in blank

hard

Fill all three blanks to create a BST in-order traversal that collects keys greater than 5.

DSA Go

func inorder(root *Node, result *[]int) {
    if root == nil {
        return
    }
    inorder(root.left, result)
    if root.key [1] 5 {
        *result = append(*result, [2])
    }
    inorder(root.right, [3])
}

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

A>

Broot.key

Cresult

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' includes wrong keys.

Appending wrong variable.

Not passing result pointer in recursion.

Check if key is greater than 5, append key to result slice, and continue traversal.

Practice

1. Which data structure is best suited when you need to maintain elements in sorted order and perform range queries efficiently?

easy

A. Hash Map

B. Binary Search Tree (BST)

C. Stack

D. Queue

Solution

1. Step 1: Understand the requirement for sorted order

   Maintaining sorted order means elements must be kept in a sequence where each element is greater or smaller than its neighbors.

2. Step 2: Identify data structure supporting range queries

   BSTs keep elements sorted and allow efficient range queries, while hash maps do not maintain order.

3. Final Answer:

   Binary Search Tree (BST) -> Option B

4. Quick Check:

   Sorted order + range queries = BST [OK]

Hint: Sorted order needs BST, hash maps don't keep order [OK]

Common Mistakes:

• Thinking hash maps keep elements sorted
• Confusing stack or queue with ordered data structures

2. Which of the following is the correct way to declare a hash map in Go that maps strings to integers?

easy

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

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

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

D. var m map[string]int = new(map[string]int)

Solution

1. Step 1: Understand Go map declaration syntax

   In Go, maps are declared with 'make' to allocate memory, e.g., make(map[keyType]valueType).

2. Step 2: Check each option for correctness

   var m map[string]int = make(map[string]int) correctly declares and initializes a map from string to int. var m map[int]string = make(map[string]int) has mismatched types. var m map[string]int = new(map[string]int) uses 'new' which returns a pointer, not a map. var m map[string]int = map[string]int declares but does not initialize the map properly.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use make() to initialize maps, not new() [OK]

Common Mistakes:

• Using new() instead of make() for maps
• Mismatching key and value types
• Declaring map without initialization

3. Consider the following Go code using a BST and a hash map. What will be the output?

package main
import "fmt"
type Node struct {
    val   int
    left  *Node
    right *Node
}
func insert(root *Node, val int) *Node {
    if root == nil {
        return &Node{val: val}
    }
    if val < root.val {
        root.left = insert(root.left, val)
    } else {
        root.right = insert(root.right, val)
    }
    return root
}
func inorder(root *Node) {
    if root != nil {
        inorder(root.left)
        fmt.Print(root.val, " ")
        inorder(root.right)
    }
}
func main() {
    root := (*Node)(nil)
    values := []int{5, 3, 7, 2, 4}
    for _, v := range values {
        root = insert(root, v)
    }
    inorder(root)
    fmt.Println()
    m := make(map[int]string)
    m[5] = "five"
    m[3] = "three"
    m[7] = "seven"
    fmt.Println(m[3])
}

medium

A. 2 3 4 5 7
three

B. 5 3 7 2 4
three

C. 2 3 4 5 7
five

D. 3 4 2 5 7
seven

Solution

1. Step 1: Trace BST insertion and inorder traversal

   Inserting 5,3,7,2,4 into BST and then inorder traversal prints sorted order: 2 3 4 5 7.

2. Step 2: Check hash map access

   Map m has key 3 with value "three", so printing m[3] outputs "three".

3. Final Answer:

   2 3 4 5 7 three -> Option A

4. Quick Check:

   BST inorder = sorted; map lookup by key = value [OK]

Hint: BST inorder prints sorted; map key lookup returns stored value [OK]

Common Mistakes:

• Assuming map keys print in order
• Confusing preorder with inorder traversal
• Mixing up map values for keys

4. The following Go code attempts to use a hash map to store integer keys and string values. It has a bug. What is the bug?

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

medium

A. Map m is declared but not initialized, causing a runtime panic

B. Key type int is invalid for maps in Go

C. String values cannot be stored in maps

D. fmt.Println cannot print map values directly

Solution

1. Step 1: Analyze map declaration and initialization

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

2. Step 2: Understand consequences of nil map assignment

   Assigning to a nil map causes a runtime panic: assignment to entry in nil map.

3. Final Answer:

   Map m is declared but not initialized, causing a runtime panic -> Option A

4. Quick Check:

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

Hint: Always initialize maps with make() before adding entries [OK]

Common Mistakes:

• Assuming declaration alone creates usable map
• Thinking key types are restricted to strings
• Believing fmt.Println can't print map values

5. You need to store a large dataset of user IDs (integers) with their last login timestamps and frequently perform these operations: fast lookup by user ID, and queries to find all users who logged in within a certain time range. Which data structure combination is best to optimize both operations?

hard

A. Use a queue to store user IDs and timestamps in order

B. Use only a hash map keyed by user ID storing timestamps

C. Use only a BST keyed by user ID storing timestamps

D. Use a hash map for user ID to timestamp, and a balanced BST keyed by timestamp for range queries

Solution

1. Step 1: Identify requirements for fast lookup and range queries

   Fast lookup by user ID suggests hash map keyed by user ID. Range queries by timestamp suggest BST keyed by timestamp.

2. Step 2: Combine data structures to optimize both operations

   Using both a hash map (for O(1) lookup) and a balanced BST (for ordered range queries) meets both needs efficiently.

3. Final Answer:

   Use a hash map for user ID to timestamp, and a balanced BST keyed by timestamp for range queries -> Option D

4. Quick Check:

   Hash map + BST combo optimizes lookup and range queries [OK]

Hint: Combine hash map for lookup and BST for ordered range queries [OK]

Common Mistakes:

• Using only one data structure and missing efficiency
• Using queue which doesn't support fast lookup or range queries
• Confusing keys for lookup and range queries