Practice
1. You need to find the cheapest route from a source city to a destination city with at most K stops in between. The graph edges represent flights with costs, and you want the minimum total cost under the stop constraint. Which algorithmic approach guarantees finding the optimal solution efficiently?
easy
Solution
Step 1: Understand the problem constraints
The problem requires the cheapest path with at most K stops, so we must track both cost and stops.Step 2: Identify suitable algorithm
Dijkstra's algorithm can be adapted to track stops as a state parameter, ensuring paths exceeding K stops are not considered, guaranteeing optimality efficiently.Final Answer:
Option D -> Option DQuick Check:
Modified Dijkstra tracks stops and cost simultaneously [OK]
Hint: Track stops in Dijkstra to enforce constraints [OK]
Common Mistakes:
- Assuming greedy cheapest next flight always works
- Using DFS without pruning leads to TLE
- Ignoring stops count in shortest path
2. You are given a list of edges representing an undirected graph with
n nodes labeled from 0 to n-1. You need to determine if the graph forms a valid tree. Which algorithmic approach guarantees an optimal solution to check both connectivity and absence of cycles efficiently?easy
Solution
Step 1: Understand problem requirements
The problem requires checking if the graph is connected and contains no cycles, which defines a tree.Step 2: Identify suitable algorithm
BFS or DFS traversal can detect cycles by tracking visited nodes and parent relationships, and also verify connectivity by ensuring all nodes are visited.Final Answer:
Option D -> Option DQuick Check:
BFS/DFS simultaneously checks connectivity and cycles efficiently [OK]
Hint: Trees have n-1 edges and no cycles [OK]
Common Mistakes:
- Assuming greedy edge addition ensures connectivity
- Using DP which is unrelated here
3. What is the time complexity of the optimal Dijkstra-based algorithm for finding the cheapest flight within K stops, given n cities and E flights? Assume the graph is represented as adjacency lists and a min-heap is used.
A) O(n^2) because we may visit all nodes multiple times.
B) O(E log E) because each edge can be pushed into the heap once.
C) O(n log n) because Dijkstra runs in that time on sparse graphs.
D) O(K * E) because we relax edges up to K times.
medium
Solution
Step 1: Identify heap operations
Each edge can be pushed into the heap at most once per stops count, but stops ≤ K limits pushes. The heap size is bounded by O(E).Step 2: Analyze complexity
Each push/pop operation costs O(log E), so total time is O(E log E). The stops constraint prevents exponential blowup.Final Answer:
Option C -> Option CQuick Check:
Heap operations dominate; stops limit expansions [OK]
Hint: Heap operations on edges dominate complexity [OK]
Common Mistakes:
- Assuming O(n^2) from classic Dijkstra on adjacency matrix
- Ignoring that stops limit expansions
- Confusing Bellman-Ford complexity with this approach
4. Examine the following buggy code for the Keys and Rooms problem:
def canVisitAllRooms(rooms):
n = len(rooms)
visited = [false] * n
count = 0
def dfs(room):
if visited[room]:
return
for key in rooms[room]:
dfs(key)
visited[room] = true
nonlocal count
count += 1
dfs(0)
return count == n
medium
Solution
Step 1: Analyze visited marking position
Visited is marked after recursive calls, so the same room can be visited multiple times during recursion.Step 2: Identify consequence of bug
This causes repeated visits and potentially infinite recursion or incorrect count.Final Answer:
Option A -> Option AQuick Check:
Visited must be marked before recursion to avoid revisits [OK]
Hint: Mark visited before recursion to prevent repeated visits [OK]
Common Mistakes:
- Marking visited after recursion leads to infinite loops
- Incrementing count before visited marking
- Incorrect initialization of visited array
5. The following BFS code attempts to find the max area of an island in a grid. Identify the line that contains a subtle bug that can cause incorrect area calculation or runtime errors.
from collections import deque
def maxAreaOfIsland(grid):
rows, cols = len(grid), len(grid[0])
visited = set()
max_area = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in visited:
queue = deque([(r, c)])
area = 0
while queue:
row, col = queue.popleft()
# Bug: Missing visited check here
visited.add((row, col))
area += 1
for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
if grid[nr][nc] == 1 and (nr, nc) not in visited:
queue.append((nr, nc))
max_area = max(max_area, area)
return max_area
medium
Solution
Step 1: Check neighbor addition line
The code adds neighbors without verifying if nr, nc are within grid boundaries, risking index out of range errors.Step 2: Confirm other lines are correct
Visited check before adding to queue is present, queue initialization and max_area update are correct.Final Answer:
Option A -> Option AQuick Check:
Boundary checks missing cause runtime errors [OK]
Hint: Always check grid boundaries before accessing neighbors [OK]
Common Mistakes:
- Forgetting boundary checks
- Not checking visited before adding to queue
- Adding visited check after popping queue