Technical interview guide

Advanced Graphs

Weighted shortest paths and connectivity beyond plain BFS/DFS — Dijkstra, Union-Find, and minimum spanning trees.

Read: 46 min
Practice MCQs: 25
Interview QA: 25
Edition: v7
Editorial status: Reviewed
Relevant for: AI EngineerBackend EngineerBlockchain DeveloperComputational BiologistData ScientistEmbedded Systems EngineerFrontend EngineerFull-Stack DeveloperMachine Learning EngineerQuantum Software EngineerRobotics EngineerSoftware Engineer

Scope: Language-neutral, with implementation notes referring to CPython 3.14 containers.

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-05 · Written: 2026-10-05 · Reviewed: 2026-10-03

QA-1

Explain minimum spanning trees and how it changes a production decision.

QA-2

How would you reason about kruskal versus Prim in a system you own?

QA-3

Walk through union-find with path compression, including where engineers most often get it wrong.

QA-4

What does strongly connected components guarantee, and what does it deliberately leave open?

QA-5

Describe the condensation graph and the evidence you would collect before relying on it.

QA-6

A teammate proposes a design that hinges on bridges and articulation points. How do you evaluate it?

QA-7

Where does all-pairs shortest paths matter, and where is it irrelevant?

QA-8

Teach choosing between all-pairs approaches to an engineer who has only seen it as a rule of thumb.

QA-9

Walk me through computing strongly connected components with Tarjan's algorithm, then contrast it with Kosaraju's — where does each one actually win?

QA-10

What makes an A-star heuristic admissible and consistent, and what happens to the search when either property fails?

QA-11

When does a problem reduce to maximum flow, and what does the min cut tell you that the flow value alone does not?

QA-12

How does bipartite matching as flow change if the workload grows by two orders of magnitude?

QA-13

Compare Edmonds-Karp and Dinic's algorithm for maximum flow: state the running time of each and say when you would choose one over the other.

QA-14

When would you refuse a design because of eulerian paths?

QA-15

How would you explain hamiltonian paths and hardness without using the usual slogan?

QA-16

How do you solve the Travelling Salesperson Problem using dynamic programming with bit manipulation, and what is its time and space complexity?

QA-17

How do you determine if a graph is bipartite using BFS or DFS, and at what threshold does graph coloring become NP-complete?

QA-18

How does the 2-approximation algorithm for Metric TSP work, and why does the triangle inequality guarantee its bound?

QA-19

How do you find the single-source shortest path and longest path in a directed acyclic graph in O(V + E) time, and why does this approach allow negative edge weights?

QA-20

What trade-off does the second-shortest path force that a junior answer usually skips?

QA-21

How do graph processing frameworks partition and traverse graphs that exceed single-machine memory?

QA-22

What is the smallest experiment that would change your mind about dynamic connectivity?

QA-23

How does problem reductions interact with rollback, and where do people ignore that?

QA-24

What would you ask a candidate who recites verifying graph algorithms but cannot apply it?

QA-25