Graphs interview questions
Grids and networks as graphs: BFS and DFS, multi-source BFS, topological order, union-find, Dijkstra and minimum spanning trees, with the costs you need to state.
– interview-ready · 22 questions in this topic
– of 22 tried
Saved on this device. Interview-ready means you got it right on two different days. Guesses and hints count for less.
Questions
- Count the separate patches of land on a mapPredict
- Can every task finish, given its prerequisites?Pick the fix
- Minutes until every item on a shelf spoilsFill the blank
- How many separate groups does a network have?Predict
- Fewest hops between two stationsPick the fix
- Fastest delivery time to every depotPredict
- The earliest valid task orderPredict
- Seat guests at two tables with no feud at eitherPick the fix
- Which cable closes a loop?Predict
- Area of the biggest patch of landPredict
- Repaint the connected region of a picturePick the fix
- Fewest one-letter changes between two code wordsPredict
- Does a dependency graph contain a loop?Pick the fix
- Cheapest way to cable every office togetherOrder the steps
- Cells whose rain reaches both coastsPick the fix
- Fill in the water that does not touch the edgePredict
- Adjacency list, adjacency matrix or edge list?Predict
- BFS or DFS: which one to usePick the fix
- Mark visited when you push or when you pop?Predict
- Why Dijkstra fails with negative weightsPick the fix
- Union-find: how it works and when to reach for itPredict
- Grids are graphs: neighbours, bounds and costsPredict
Practise this topic
Flashcards · 33
Flip, then say if you knew it. Needs JavaScript; every answer is also on its question page.
Quick quiz · 22 questions
One exercise per question, checked as you go. Needs JavaScript.
Mock interview · 4 sets
Timed, out loud, then tick what you covered. Needs JavaScript.
Quick facts
Recall the answer first, then tap Show to check.
Adjacency list size
An adjacency list stores V lists holding E entries in total (2E for undirected graphs): O(V + E) memory, against O(V²) for a matrix.
heapqis a min-heapheapq.heappushandheappopkeep the smallest item at index 0; push (distance, node) tuples for Dijkstra.Kotlin
PriorityQueuejava.util.PriorityQueuewithcompareBy { it.first }gives a min-heap of pairs for Dijkstra in Kotlin.Dijkstra cost
Dijkstra with a binary heap runs in O((V + E) log V) and requires non-negative edge weights.
Union-find cost
With path compression and union by size, a sequence of m union-find operations costs O(m α(n)), where α grows so slowly it is below 5 for any practical n.
Printable cheat sheet · Review your weak spots in this topic
Share your progress
Sources: Topic outline informed by the Tech Interview Handbook by Yangshun Tay and the NeetCode 150 pattern grouping by neetcode-gh, both MIT licensed. Every problem, solution and explanation is written by Best Latest Apps. Credits and license