Citi·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Citi technical phone screen for a software engineer role, pretty deep on graph algorithms. One question, but they really wanted the full picture, not just pseudocode.

Questions Asked (1)

Design and implement bidirectional Dijkstra to find the shortest path between a source and target node in a weighted directed or undirected graph. Cover the data structures for both search directions, when to stop, how to compute the correct shortest distance when the two frontiers meet, how to reconstruct the path, time and space complexity compared to standard Dijkstra, and edge cases like disconnected graphs or ties.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one went longer than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by explaining the core idea of bidirectional Dijkstra: run two simultaneous searches from source and target, expanding the node with the smallest tentative distance from either frontier. Then detail the data structures, stopping condition, and how to combine distances to get the shortest path. Finally, discuss complexity, edge cases, and trade-offs compared to standard Dijkstra.

Pro tip: Emphasize that the stopping condition is when the sum of the minimum keys from both priority queues is greater than or equal to the best found meeting distance, not when the frontiers first meet. This subtlety often trips up candidates and shows deep understanding.

1. Explain the algorithm overview

Describe how bidirectional Dijkstra runs two Dijkstra searches: one from source (forward) and one from target (backward on reversed edges). Alternate expanding the node with the smallest tentative distance from either search.

2. Detail data structures

For each direction, maintain a priority queue (min-heap) of (distance, node), a distance map, and a predecessor map for path reconstruction. Also keep a variable for the best meeting distance and meeting node.

3. Define stopping condition and meeting logic

Stop when the sum of the minimum distances from both priority queues is >= the best meeting distance found so far. When a node is settled in one direction, check if it has been visited in the other; if so, compute the total distance and update the best if smaller.

4. Path reconstruction

Once the best meeting node is found, reconstruct the path by following predecessors from the meeting node back to the source in the forward search, and from the meeting node to the target in the backward search (reversing the backward path).

5. Complexity and edge cases

Analyze time and space complexity: O((V+E) log V) time and O(V) space, but with a smaller search space than standard Dijkstra. Discuss edge cases: disconnected graphs (no path), ties in distances, and graphs with zero-weight edges.

Key Points to Mention

Use two priority queues and distance maps, one for forward search from source and one for backward search from target (on reversed edges).
Stopping condition: terminate when the sum of the minimum keys from both queues is >= the best meeting distance found so far.
When a node is settled in one direction, check if it has been settled in the other; if so, update the best meeting distance and node.
Path reconstruction: combine the forward path from source to meeting node and the backward path from meeting node to target.
Time complexity: O((V+E) log V) worst-case, but often explores fewer nodes than standard Dijkstra; space complexity O(V).
Edge cases: disconnected graphs (return infinity or no path), ties (any shortest path is acceptable), and zero-weight edges (Dijkstra still works).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.