Graphs, Trees and Search
One reported problem blends breadth-first search with binary search; another is a tree problem in the family of placing cameras to cover a tree. Graphs turn up in these assessments in two forms: explicitly, and disguised as something else. The second is worth more attention, because the disguise is where candidates lose the problem entirely.
Three traversals, three jobs
Breadth-first search visits by distance, so it answers shortest path in an unweighted graph and nothing else does it more cheaply. Queue, visited set, mark on enqueue rather than on dequeue. Marking on dequeue is the standard bug: a node reachable from three others is queued three times and the work multiplies.
Depth-first search goes deep and unwinds, which makes it the tool for anything defined recursively over structure: connected components, cycle detection, topological order, and every tree recurrence below. In Python, recursion depth is capped around a thousand by default, so a path graph of nodes overflows the stack. Either raise the limit or write the explicit stack, and know which you did before the interviewer asks.
The rest of this lesson is for subscribers
Unlock every lesson in Programming for Quantitative Developers, and every other premium course.
Subscribe to continueTest your knowledge
Keep reading Programming for Quantitative Developers
25 lessons in this course, and every other premium course, on one subscription.
- Every lesson in every course, with the worked examples and interactive simulators
- Graded questions on every lesson, with explanations for the wrong answers as well as the right one
- The trainers, timed assessments and brainteaser library that go with them