Adjacency List Representation in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after running this Go code that adds edges to a graph?

DSA Go

package main
import "fmt"
func main() {
    graph := make(map[int][]int)
    graph[1] = append(graph[1], 2)
    graph[1] = append(graph[1], 3)
    graph[2] = append(graph[2], 4)
    graph[3] = append(graph[3], 4)
    fmt.Println(graph)
}

A map[1:[2 3] 2:[4] 3:[]]

B map[1:[3 2] 2:[4] 3:[4]]

C map[1:[2 3] 2:[4] 3:[4]]

D map[1:[2 3] 2:[] 3:[4]]

💡 Hint

Remember append adds elements to the slice in order.

The code appends 2 and 3 to graph[1], then 4 to graph[2] and graph[3]. So graph[1] has [2 3], graph[2] has [4], and graph[3] has [4].

❓ Predict Output

intermediate

Resulting adjacency list after removing an edge

What is the adjacency list printed after removing edge 2->4 from this graph?

DSA Go

package main
import "fmt"
func main() {
    graph := map[int][]int{
        1: {2, 3},
        2: {4},
        3: {4},
    }
    // Remove edge 2->4
    neighbors := graph[2]
    newNeighbors := []int{}
    for _, n := range neighbors {
        if n != 4 {
            newNeighbors = append(newNeighbors, n)
        }
    }
    graph[2] = newNeighbors
    fmt.Println(graph)
}

A map[1:[3 2] 2:[] 3:[4]]

B map[1:[2 3] 2:[4] 3:[4]]

C map[1:[2 3] 2:[3] 3:[4]]

D map[1:[2 3] 2:[] 3:[4]]

💡 Hint

Check how the new slice excludes 4 from graph[2].

The code removes 4 from graph[2]'s neighbors by filtering it out, so graph[2] becomes empty slice [].

🔧 Debug

advanced

Identify the error in adjacency list initialization

What error does this Go code produce when trying to add an edge to an uninitialized adjacency list?

DSA Go

package main
func main() {
    var graph map[int][]int
    graph[1] = append(graph[1], 2)
}

A panic: assignment to entry in nil map

B runtime error: index out of range

C compile error: undefined variable graph

D no error, runs fine

💡 Hint

Maps must be initialized before use.

The map graph is declared but not initialized, so writing to it causes a runtime panic.

❓ Predict Output

advanced

Output after adding duplicate edges in adjacency list

What is the adjacency list after adding duplicate edges 1->2 twice?

DSA Go

package main
import "fmt"
func main() {
    graph := make(map[int][]int)
    graph[1] = append(graph[1], 2)
    graph[1] = append(graph[1], 2)
    fmt.Println(graph)
}

A map[1:[2 2]]

B map[1:[2]]

C map[1:[]]

D map[1:[2 1]]

💡 Hint

Appending twice adds both elements.

Appending 2 twice results in slice [2 2] for graph[1].

🧠 Conceptual

expert

Memory complexity of adjacency list for sparse graph

What is the memory complexity of an adjacency list representation for a graph with V vertices and E edges?

A O(V * V)

B O(V + E)

C O(E * E)

D O(V)

💡 Hint

Adjacency list stores each vertex and its edges.

Adjacency list stores each vertex and its edges, so memory is proportional to vertices plus edges.

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