MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA) Module 11

Graphs: modelling, traversal and connectivity interview questions

Interview questions on “Graphs: modelling, traversal and connectivity”: warm-ups, then what each harder question tests and how a good answer starts.

33 questions: 6 warm-ups and 27 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    find(x) returned 4 a minute ago and returns 9 now, although nothing touched x itself. Is that a bug?

    Answered in the lesson Union-find (disjoint set union)

  2. Fresher to mid

    In a state-space search, what must a state hold, and what goes wrong if it leaves something out?

    A state holds everything that decides which moves are possible next and whether the goal is met, and nothing else. For a knight that is its square; for a robot that pays for turns, the square and the heading; for a maze with keys, the square and the keys held. If the state leaves something out, two different situations share one visited mark: the search reaches a square without the key, marks it, and later turns away the same square with the key, so a real route is cut off and the answer comes out too long, or -1. If it holds more than it needs, such as the route so far, equal situations look different and the states multiply. Their count, the product of the sizes of the parts, is the cost of the search.

    From the lesson Implicit graphs, state-space search and 0-1 BFS

  3. Fresher

    Why does BFS mark a vertex when it is put in the queue rather than when it is taken out?

    Answered in the lesson Breadth-first search and unweighted shortest paths

  4. Fresher to mid

    Why does a topological order exist only for a directed acyclic graph, and what does Kahn's algorithm do when there is a cycle?

    Answered in the lesson Topological sorting of DAGs

  5. Fresher to mid

    Why is the condensation of a directed graph, one vertex per strongly connected component, always acyclic?

    Answered in the lesson Strongly connected components

  6. Fresher to mid

    One route must drive every street of a town exactly once, another must stop at every junction exactly once. Which is the Euler problem, and why is the other much harder?

    Answered in the lesson Euler paths and circuits

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Mid to senior

    A network monitor receives 20 million "link up" events among 4 million devices, and links never go down. After each event it must answer up to five "can A reach B?" questions in about a microsecond each. Which structure do you use, how much memory does it need, and what is the worst case of a single question?

    What it tests
    Choosing union-find over a search per question, sizing its arrays, and telling the amortised cost from the worst case of one operation.
    First step
    Price the obvious design first: a search per question over a graph that grows to 20 million links can visit every device, millions of steps, against a budget of a microsecond. The questions only ask about group membership and links only arrive, so groups only merge, which is exactly what union-find keeps.
    Follow-ups

    From the lesson Union-find (disjoint set union)

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  2. Mid to senior

    A deduplication job built on union-find has run for months. On one customer's file of 300,000 records it now crashes with a stack overflow, yet every test passes. What is the likely cause, how do you reproduce it in a test, and what do you change?

    What it tests
    Linking order and tree height, recursion limits, and turning a production crash into a small failing test.
    First step
    A stack overflow in union-find points at a recursive find walking a tall tree, and a tall tree means unions with no size or rank rule. Ask how this customer's records are ordered: input sorted so that each record is matched to the one before it builds exactly such a chain.
    Follow-ups

    From the lesson Union-find (disjoint set union)

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  3. Mid to staff

    A matcher emits 30 million "same product" pairs over 8 million listings, and every listing needs a group id. A colleague stores the pairs as a graph and runs breadth-first search. Compare that with union-find in time, in memory, and when new pairs keep arriving every minute.

    What it tests
    Weighing a one-off search against incremental merging, with memory estimates, and knowing what neither design can undo.
    First step
    For one batch both are close to linear, so compare what each must hold. The search needs every pair stored twice in adjacency lists before it starts; union-find needs two arrays of 8 million entries and can read the pairs as a stream. Then ask what one new pair costs each design.
    Follow-ups

    From the lesson Union-find (disjoint set union)

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  4. Mid to senior

    Your BFS for the fewest knight moves passes every test on boards up to 1,000 × 1,000. A new version must answer on boards of 100,000 × 100,000 within a second. What breaks first, and how do you still give the exact answer?

    What it tests
    Sizing a state space before searching it, and replacing most of a search by a shortcut that is tested against the full search.
    First step
    Count the states first: 10¹⁰ squares, so the distance array alone would need 40 GB as 32-bit integers, and a full search would take minutes even in compiled code. Searching the whole board is out, so ask which part of a route really needs a search.
    Follow-ups

    From the lesson Implicit graphs, state-space search and 0-1 BFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  5. Mid to senior

    A robot arm has 4 joints, each set to one of 36 angles. A move turns one joint by one notch either way, and 5 % of all settings make the arm hit its frame. How many states are there, what does BFS between two settings cost, and how much does searching from both ends save?

    What it tests
    Counting states as a product, estimating the work of BFS, and predicting the saving of a two-ended search from how the states grow with distance.
    First step
    The state is the four angles: 36⁴ = 1,679,616 settings, about 1.6 million of them allowed, each with up to 8 moves. A full search is about 13 million move checks, which is small. For the saving, ask how the number of settings within d moves of one setting grows with d.
    Follow-ups

    From the lesson Implicit graphs, state-space search and 0-1 BFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Mid to senior

    A route planner for warehouse robots returns routes through the fewest cells, but operations wants the fewest turns, and turning around counts as two. Model the states and the costs, choose the search, and estimate its work and memory on a 2,000 × 2,000 grid.

    What it tests
    Adding the heading to the state, recognising moves that cost 0 or 1, and sizing the search before running it.
    First step
    Turns depend on the heading, so a cell alone is not a state: use (row, column, heading), 4 × 4 million = 16 million states. Driving straight on costs no turn and each quarter turn costs one, so every move costs 0 or 1, which is the case for a deque instead of a heap.
    Follow-ups

    From the lesson Implicit graphs, state-space search and 0-1 BFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  7. Mid to senior

    A community app stores, for each of its 2 million accounts, the list of accounts that follow it. Most accounts have under 200 followers, a few have 800,000. A feed service asks "does u follow v?" 100,000 times a second. Estimate what scanning the lists costs, and redesign the storage.

    What it tests
    Seeing that skewed degrees break a scan of one list, estimating comparisons, and choosing a structure per vertex and per direction.
    First step
    Price the scan: a question about a popular v reads up to 800,000 entries, so a few thousand such questions a second cost more than all the others together. Then notice that u's own list of accounts it follows is usually short, so the direction you scan matters as much as the structure.
    Follow-ups

    From the lesson Adjacency lists, matrices and edge lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  8. Mid to senior

    A navigation app must load a road network of 2 million junctions and 5 million one-way road segments, each with a travel time, onto phones with 300 MB of free memory. Estimate the memory of one object per segment against a compressed sparse row layout, and choose.

    What it tests
    Estimating per-entry overheads, knowing the compressed sparse row layout, and trading the cost of updates for compactness.
    First step
    Count the data first: 5 million segments, each a target and a travel time, plus a little per junction. Then estimate what an object per segment adds on top of its two numbers: a header, padding and a reference to it, and what a list per junction adds.
    Follow-ups

    From the lesson Adjacency lists, matrices and edge lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  9. Fresher to mid

    Your graph solution passes every sample, but the judge reports a runtime error on hidden test 7, and on test 12 the answer is exactly one too large. Both tests number the vertices from 1 to n. What do you suspect, and how do you find it quickly?

    What it tests
    Linking symptoms to input-reading bugs, such as labels from 1 and phantom vertices, and building tiny inputs that reproduce them.
    First step
    Read how the code stores vertices. A crash on some tests and an answer one too large both point at the labels: an index n when only n lists exist, and a phantom vertex 0 counted as a component or an isolated vertex. Make a three-vertex input with an edge that touches vertex n.
    Follow-ups

    From the lesson Adjacency lists, matrices and edge lists

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  10. Mid to senior

    A city has 2 million road junctions and 300 ambulance stations. Every night, dispatch needs each junction's nearest station in road segments. A teammate proposes one BFS per station. Estimate that plan and propose a better one.

    What it tests
    Recognising multi-source BFS, estimating repeated searches, and noticing direction and the point where segment counts stop being the right distance.
    First step
    Price the proposal: each BFS can touch every junction and segment, and 300 of them cost 300 times that. Then put all 300 stations in the queue at distance 0 and run one search: every junction is reached first from its nearest station, in a single pass.
    Follow-ups

    From the lesson Breadth-first search and unweighted shortest paths

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  11. Fresher to mid

    Your route planner runs BFS over the road graph and returns the routes with the fewest road segments. Users complain that some routes take far longer than an alternative. Explain why, and say when a BFS-like search is still correct on a weighted graph.

    What it tests
    Knowing that BFS ignores weights, and the cases where a queue-based search still works: equal weights, weights of 0 and 1, small integer weights.
    First step
    BFS counts edges, so a 5-minute lane and a 20-minute stretch of highway look the same to it. Build the smallest counterexample, two segments of 20 minutes against three of 5, then ask what must be true of the weights for the order of a queue to still match the order of distances.
    Follow-ups

    From the lesson Breadth-first search and unweighted shortest paths

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  12. Mid to senior

    You must find a shortest route through a 10,000 × 10,000 grid maze, read from a file of 10⁸ characters, on a machine with 1 GB of free memory, in Python. Estimate the memory of a straightforward BFS, then redesign it to fit.

    What it tests
    Estimating Python object overheads, choosing compact arrays for walls, marks and the queue, and rebuilding the route from a few bits per cell.
    First step
    Estimate the obvious version: a dictionary of parents keyed by (row, column) tuples costs well over 100 bytes a cell, about 10 GB for 10⁸ cells. Then count bytes per cell for flat arrays: walls in bits or bytes, one small value per cell for the search, and a queue of 4-byte cell numbers.
    Follow-ups

    From the lesson Breadth-first search and unweighted shortest paths

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  13. Mid to senior

    A scanned map is a 20,000 × 20,000 black-and-white image, 4 × 10⁸ pixels, and you must count its connected black regions on a machine with 2 GB of memory. A recursive flood fill crashes. Design a version that fits, and estimate its memory.

    What it tests
    Bounding the explicit stack of a flood fill, packing pixels into bits, and knowing the row-by-row labelling method with union-find.
    First step
    Size the input first: 4 × 10⁸ pixels are 400 MB as bytes but 50 MB as bits. A flood fill needs a visited mark per pixel and a stack whose worst case is every black pixel at once, so estimate that worst case before choosing a design.
    Follow-ups

    From the lesson Depth-first search, components and timestamps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  14. Mid to senior

    A platform has 5,000 services and 40,000 "depends on" arcs. When one service fails, a dashboard must list every service that can break because of it, within 10 milliseconds per click. Compare a search per click with precomputing every answer, with numbers.

    What it tests
    Searching the reversed graph for "who depends on me", comparing a search per query with a closure stored as bits, and handling cycles.
    First step
    Turn the question around: the services that break when S fails are those with a path to S along "depends on" arcs, so search from S over the reversed arcs. One such search touches at most 5,000 services and 40,000 arcs, about 45,000 steps; compare that with the budget before precomputing anything.
    Follow-ups

    From the lesson Depth-first search, components and timestamps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  15. Fresher to senior

    An HR system stores a reporting tree of 300,000 employees and must answer 2 million questions a day of the form "does B manage A, directly or through others?", each in constant time after a nightly preparation. How do you prepare, and what does each answer cost?

    What it tests
    Using discovery and finish times as an interval test for ancestry, computing them without recursion, and handling several separate trees.
    First step
    Run one DFS from the top of the tree and record each employee's discovery and finish times. B manages A exactly when B's interval contains A's: d(B) < d(A) and f(A) < f(B). That is two comparisons per question after an O(n) preparation.
    Follow-ups

    From the lesson Depth-first search, components and timestamps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  16. Mid to senior

    A monorepo of 12,000 modules and 90,000 imports must be checked for circular imports on every commit, in under a second, and the report must show a cycle a developer can fix. How do you find one, and how do you keep the reported cycle short?

    What it tests
    Three-colour DFS with an explicit stack, reading the cycle off the parent pointers, and shortening it with BFS.
    First step
    One iterative three-colour DFS over 12,000 modules and 90,000 arcs, about 10⁵ steps, finds a cycle or proves there is none: when an arc reaches a grey module, the parent pointers give the cycle. Then ask which cycle a developer can act on: usually the shortest one through the modules involved.
    Follow-ups

    From the lesson Cycle detection and bipartite graphs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  17. Fresher to mid

    A clinic must put each of 400 nurses on a day shift or a night shift so that no two nurses who must not work together share a shift; there are 3,000 such pairs. Decide whether it is possible, and when it is not, what you show the manager.

    What it tests
    Modelling conflicts as a graph, two-colouring it by BFS, returning an odd cycle as the reason, and knowing what becomes hard with three shifts.
    First step
    Nurses are vertices and forbidden pairs are edges. Two shifts with no forbidden pair inside either is a split into two sides, so the question is whether the graph is bipartite. BFS colouring answers it in O(V + E), about 3,400 steps here, and a clash gives an odd cycle to show.
    Follow-ups

    From the lesson Cycle detection and bipartite graphs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  18. Mid to senior

    A network team lays 50,000 cables one at a time between 20,000 sites and wants an alert the moment a new cable closes a loop. Compare running a DFS after every cable with union-find, with numbers, and say what each can report.

    What it tests
    Online cycle detection with union-find, the total cost of repeated searches, and what union-find alone cannot tell you.
    First step
    Price the repeated search: after cable k the graph has k edges, so one DFS costs up to 20,000 + k steps, and over 50,000 cables that adds up to about 2 × 10⁹ steps. Union-find answers each cable with two finds and one union.
    Follow-ups

    From the lesson Cycle detection and bipartite graphs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  19. Mid to senior

    A build has 2,000 targets with known compile times and 9,000 dependencies. With unlimited cores, how long does it take at least, and how do you schedule it on 8 cores? Explain the algorithm and its cost.

    What it tests
    The longest path of a DAG by one pass in topological order, list scheduling with a ready queue, and lower bounds that show how good a schedule is.
    First step
    With unlimited cores only the dependencies limit the build, so the minimum time is the longest chain of compile times: one pass in topological order gives each target its earliest finish, the latest finish among its prerequisites plus its own time. For 8 cores, keep the ready targets in a priority queue and start the most urgent first.
    Follow-ups

    From the lesson Topological sorting of DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  20. Mid to staff

    A planner must fit 60 required courses with prerequisites into the fewest semesters, at most 5 courses a semester. A colleague proposes Kahn's algorithm, taking any 5 ready courses each semester. Is that optimal? What would you build, and what would you promise?

    What it tests
    Seeing that a capacity limit breaks the batch argument, producing a counterexample, knowing the hardness result, and pairing a heuristic with lower bounds.
    First step
    Look for the smallest failure: with a cap, which ready courses you take matters, because a course with a long chain ahead of it should start early. Then state the lower bounds any plan must respect: the longest chain of prerequisites, and 60 / 5 = 12 semesters.
    Follow-ups

    From the lesson Topological sorting of DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  21. Fresher to senior

    Given a list of "A before B" rules for 100,000 tasks, decide in O(V + E) whether exactly one order satisfies all of them. How do you check it, and what does a unique order tell you about the rules?

    What it tests
    Kahn's algorithm with a check on the queue, the link between a unique order and a path through every task, and finding the missing rule when it is not unique.
    First step
    Run Kahn's algorithm and watch the queue. If it ever holds two tasks at once, either could come next, so at least two orders exist. If it never does and every task comes out, each step was forced and the order is unique.
    Follow-ups

    From the lesson Topological sorting of DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  22. Mid to senior

    A financial model has 40,000 formula cells and 300,000 references, and its engine refuses to calculate while any circular reference exists. Users need every group of cells caught in a circle, and an estimate of the work to untangle each. What do you compute, how long does it take, and how do you rank the groups?

    What it tests
    Recognising circular references as strongly connected components, running in linear time, and estimating the work of untangling each group.
    First step
    Every circle of references lies inside one strongly connected component, and every component with two or more cells, or a cell that refers to itself, contains a circle. So compute the components: one linear pass over 340,000 cells and references, well under a second. Each component of two or more cells is one group to report.
    Follow-ups

    From the lesson Strongly connected components

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  23. Mid to senior

    A link-analysis job finds strongly connected components with a recursive Tarjan in Python. It works on every test graph but crashes on the production link graph of 3 million pages. What is going on, and what are your options?

    What it tests
    Recursion depth against path length, converting Tarjan to an explicit stack correctly, and the memory of large graphs in Python.
    First step
    Recursion in depth-first search is as deep as the longest path the search follows, and a link graph of 3 million pages easily holds chains of tens of thousands, far past CPython's default limit of 1,000 frames. Ask what the error was: a RecursionError, or the process dying after someone raised the limit.
    Follow-ups

    From the lesson Strongly connected components

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  24. Mid to staff

    A crawler must reach every page of a site whose link graph has 2 million pages, starting from as few seed pages as possible. How many seeds do you need, how do you choose them, and what changes when new pages and links appear every hour?

    What it tests
    Turning a reachability question into one about components, and handling a graph that keeps growing.
    First step
    A seed reaches everything its own component reaches, so think in components and in the condensation, which is a DAG. Then ask which components a seed outside them could never reach.
    Follow-ups

    From the lesson Strongly connected components

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  25. Mid to senior

    A city wants a street-sweeping route that drives each of its 3,800 street segments and returns to the depot, with as little driving twice as possible. How do you decide whether a route without repeats exists, build it, and plan the repeats when it does not?

    What it tests
    The degree test with connectivity, Hierholzer's algorithm, and planning the fewest repeated segments when the test fails.
    First step
    Model junctions as vertices and segments as edges, then count the odd junctions. If there are none and the segments are connected, an Euler circuit exists and Hierholzer's algorithm builds it from the depot. If there are odd junctions, some segments must be driven twice, and the work is choosing which.
    Follow-ups

    From the lesson Euler paths and circuits

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  26. Senior to staff

    You receive 50,000 overlapping 8-character fragments of an unknown text, each 8-character window exactly once and in no order. How do you rebuild the text, how fast is it, and when can you not be sure that your answer is the original?

    What it tests
    Choosing what the vertices and edges of a graph should be, a linear-time construction, and recognising when several texts fit.
    First step
    Look at what two consecutive windows of the text share: 7 characters. Decide what should be a vertex and what an edge, so that reading the text once from left to right uses every fragment exactly once.
    Follow-ups

    From the lesson Euler paths and circuits

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  27. Mid to senior

    A recursive Hierholzer passes every unit test but crashes on a graph with 300,000 edges. A colleague's loop-based rewrite no longer crashes, but the route validator rejects its output on some inputs. Explain both failures and what the correct loop must do.

    What it tests
    Recursion depth in Hierholzer's algorithm, when a vertex joins the route, and validating a route against the edges.
    First step
    The recursion in Hierholzer's algorithm is as deep as the longest walk it follows before it gets stuck, which on a large cycle is every edge. For the rewrite, look at when it writes a vertex into the route: on the way in, or when the vertex has no unused edge left.
    Follow-ups

    From the lesson Euler paths and circuits

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track