Adjacency List Representation in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an adjacency list as a map of slices.

DSA Go

adjList := make(map[int][1])

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

Aint

B[]int

Cmap[int]int

Dstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using int instead of []int for the map value type.

Using map[int]int which is not suitable for adjacency lists.

The adjacency list stores neighbors as slices of integers, so the map value type should be []int.

2fill in blank

medium

Complete the code to add an edge from node 1 to node 2 in the adjacency list.

DSA Go

adjList[1] = append(adjList[1], [1])

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

A0

B3

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Appending the wrong node number.

Appending to the wrong key in the map.

To add an edge from node 1 to node 2, append 2 to the slice at adjList[1].

3fill in blank

hard

Fix the error in the code to correctly initialize the adjacency list for 3 nodes.

DSA Go

adjList := make(map[int][1])
for i := 1; i <= 3; i++ {
    adjList[i] = [2]{}
}

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

Aint

B[]int

Cmap[int]int

Dstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using int or map[int]int as map value type.

Initializing adjacency lists with nil or wrong types.

The map values must be slices of int ([]int). Initialize each node's adjacency slice as an empty []int.

4fill in blank

hard

Fill both blanks to add edges from node 2 to nodes 1 and 3.

DSA Go

adjList[2] = append(adjList[2], [1])
adjList[2] = append(adjList[2], [2])

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

A1

B2

C3

D4

Attempts:

3 left

💡 Hint

Common Mistakes

Appending incorrect node numbers.

Appending the same node twice.

To add edges from node 2 to nodes 1 and 3, append 1 and 3 to adjList[2].

5fill in blank

hard

Fill all three blanks to print all neighbors of node 1 using a for loop.

DSA Go

for _, [1] := range adjList[1] {
    fmt.[2]([3])
}

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

Aneighbor

BPrintln

DPrint

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable names.

Using fmt.Print instead of fmt.Println.

Printing the wrong variable.

Use 'neighbor' as the variable name, fmt.Println to print, and print the neighbor variable.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A matrix showing distances between nodes

B. A list where each node stores its connected neighbors

C. A list of all nodes without connections

D. A stack of nodes visited during traversal

Solution

1. Step 1: Understand adjacency list concept and compare options

   An adjacency list stores each node with a list of its neighbors, showing direct connections. Only the description "A list where each node stores its connected neighbors" correctly describes this structure; others describe different concepts.

2. Final Answer:

   A list where each node stores its connected neighbors -> Option B

3. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors per node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing adjacency list with traversal order

2. Which Go syntax correctly declares an adjacency list for a graph with integer nodes?

easy

A. var graph map[int][]int = make(map[int][]int)

B. var graph []int = make([]int, 0)

C. var graph map[int]int = make(map[int]int)

D. var graph [][]int = make([][]int, 0)

Solution

1. Step 1: Identify adjacency list type in Go and check options for correct syntax

   An adjacency list maps each node (int) to a slice of connected nodes ([]int), so map[int][]int is correct. var graph map[int][]int = make(map[int][]int) uses map[int][]int with make, which is correct. Others use wrong types or slices without mapping.

2. Final Answer:

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

3. Quick Check:

   Adjacency list = map node to slice [OK]

Hint: Adjacency list in Go = map[node][]neighbors [OK]

Common Mistakes:

• Using slice of ints instead of map for adjacency list
• Declaring map[int]int which stores single int, not neighbors
• Confusing slice of slices with map

3. Given the following Go code, what is the printed adjacency list?

graph := make(map[int][]int)
graph[1] = []int{2, 3}
graph[2] = []int{1}
graph[3] = []int{1, 4}
graph[4] = []int{3}

for node, neighbors := range graph {
    fmt.Printf("%d -> %v\n", node, neighbors)
}

medium

A. 1 -> [2 3]
2 -> [1]
3 -> [1 4]
4 -> [3]

B. 1 -> [1 4]
2 -> [2 3]
3 -> [3]
4 -> [4]

C. 1 -> [2]
2 -> [3]
3 -> [4]
4 -> [1]

D. 1 -> []
2 -> []
3 -> []
4 -> []

Solution

1. Step 1: Analyze graph assignments and match printed output

   Node 1 connects to 2 and 3, node 2 connects to 1, node 3 connects to 1 and 4, node 4 connects to 3. Output prints each node with its neighbors slice exactly as assigned, matching 1 -> [2 3]\n2 -> [1]\n3 -> [1 4]\n4 -> [3].

2. Final Answer:

   1 -> [2 3] 2 -> [1] 3 -> [1 4] 4 -> [3] -> Option A

3. Quick Check:

   Print adjacency list as assigned [OK]

Hint: Print adjacency list shows node and its neighbors slice [OK]

Common Mistakes:

• Mixing neighbors between nodes
• Confusing slice contents order
• Assuming empty neighbors incorrectly

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u int, v int) {
    graph[u] = append(graph[u], v)
    graph[v] = append(graph[u], v)
}

medium

A. append cannot be used with slices

B. Function does not return the updated graph

C. map[int][]int cannot be modified inside function

D. Second append uses graph[u] instead of graph[v]

Solution

1. Step 1: Review append calls for edges and identify correct usage

   First append adds v to graph[u], correct. Second append should add u to graph[v], but uses graph[u] mistakenly. Second append must be graph[v] = append(graph[v], u) to add reverse edge for undirected graph.

2. Final Answer:

   Second append uses graph[u] instead of graph[v] -> Option D

3. Quick Check:

   Append neighbors to correct node slice [OK]

Hint: Append neighbors to correct node slice for undirected edges [OK]

Common Mistakes:

• Appending to wrong slice causing incorrect graph
• Thinking map cannot be modified inside function
• Misunderstanding append usage in Go

5. You have a graph represented by an adjacency list in Go as map[int][]int. How would you efficiently check if an edge exists between nodes u and v?

hard

A. Iterate over graph[u] slice to find v; return true if found, else false

B. Check if graph[u][v] exists directly using indexing

C. Use a map[int]bool inside graph[u] for constant time lookup

D. Sort graph[u] slice and use binary search to find v

Solution

1. Step 1: Understand adjacency list lookup and optimize lookup with map

   graph[u] is a slice, so direct indexing by v is invalid (Check if graph[u][v] exists directly using indexing wrong). Iteration (Iterate over graph[u] slice to find v; return true if found, else false) is linear time. Using map[int]bool inside graph[u] allows constant time check if v is neighbor (Use a map[int]bool inside graph[u] for constant time lookup). Sorting and binary search (Sort graph[u] slice and use binary search to find v) adds overhead.

2. Final Answer:

   Use a map[int]bool inside graph[u] for constant time lookup -> Option C

3. Quick Check:

   Map lookup faster than slice iteration [OK]

Hint: Use map for neighbors to check edges fast [OK]

Common Mistakes:

• Trying to index slice by node value directly
• Ignoring performance of linear search
• Overcomplicating with sorting when map is simpler