How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Citi.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citi during technical interviews.

Implement bidirectional Dijkstra for shortest paths

Quick Overview

This question evaluates proficiency in graph algorithms and algorithm engineering, specifically understanding and implementing bidirectional shortest-path search with appropriate data structures, termination conditions, path reconstruction, and time/space complexity analysis.

Company: Citi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given a directed or undirected graph with non‑negative edge weights, design and implement bidirectional Dijkstra (“double Dijkstra”) to find the shortest path between a single source s and target t. Specify the data structures for the forward and reverse searches, the termination condition, how to compute the correct shortest distance when the frontiers meet, and how to reconstruct the full path. Analyze time and space complexity versus standard Dijkstra, and discuss edge cases such as disconnected graphs and multiple shortest paths.

Quick Answer: This question evaluates proficiency in graph algorithms and algorithm engineering, specifically understanding and implementing bidirectional shortest-path search with appropriate data structures, termination conditions, path reconstruction, and time/space complexity analysis.

Given a graph with non-negative edge weights, compute the length of the shortest path from a single source `s` to a target `t` using **bidirectional Dijkstra** ("double Dijkstra"). You are given: - `n` — the number of nodes, labeled `0 .. n-1`. - `edges` — a list of `[u, v, w]` triples meaning there is an edge from `u` to `v` with non-negative weight `w`. - `s` — the source node. - `t` — the target node. - `directed` — a boolean. If `true`, each edge goes only from `u` to `v`. If `false`, each edge is traversable in both directions. Return the total weight of the shortest path from `s` to `t`. If `t` is unreachable from `s`, return `-1`. If `s == t`, return `0`. **Bidirectional Dijkstra** runs two simultaneous Dijkstra searches: a *forward* search from `s` over the graph, and a *reverse* search from `t` over the graph with every edge reversed. Maintain a forward distance array `dist_f` and a reverse distance array `dist_r`, plus a min-heap (priority queue) for each frontier. Repeatedly expand whichever frontier currently has the smaller top key. Whenever you relax an edge `(u, v, w)` and the *other* search has already reached `v`, update a running `best = min(best, dist_f[u] + w + dist_r[v])`. **Termination:** stop once the sum of the two heaps' minimum keys is `>= best` — no remaining path can beat the best meeting point already found. Then `best` is the true shortest distance. This explores roughly two half-radius balls instead of one full-radius ball, which can be dramatically faster on large sparse graphs (intuitively `O(b^{d/2})` vs `O(b^d)` frontier growth) while keeping the same `O((V + E) log V)` worst-case bound and `O(V + E)` space.

Constraints

1 <= n <= 10^5
0 <= u, v < n
0 <= w <= 10^6 (edge weights are non-negative)
0 <= s, t < n
The graph may be disconnected; return -1 when t is unreachable from s.
Parallel edges (multiple edges between the same pair) and self-loops may appear.

Examples

Input: (5, [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], 0, 3, True)

Expected Output: 4

Explanation: Directed graph. The path 0->2->1->3 costs 1+2+1=4, which beats 0->1->3 (4+1=5) and 0->2->3 (1+5=6). The two frontiers meet at node 1; best = dist_f[1]=3 plus dist_r[1]=1 gives 4.

Input: (4, [[0,1,1],[1,2,1],[2,3,1]], 0, 3, True)

Expected Output: 3

Explanation: A simple directed chain 0->1->2->3 of three unit edges. Shortest distance is 3.

Input: (3, [[0,1,2],[2,1,3]], 0, 2, True)

Expected Output: -1

Explanation: Directed graph where node 2 has only an outgoing edge to 1 and no path leads into 2 from 0. The reverse search from 2 cannot reach 0, so t is unreachable -> -1.

Input: (1, [], 0, 0, True)

Expected Output: 0

Explanation: Source equals target with a single node and no edges. The distance is 0 by definition.

Input: (4, [[0,1,10],[1,2,10],[0,3,1],[3,2,1]], 0, 2, False)

Expected Output: 2

Explanation: Undirected graph. The detour 0-3-2 costs 1+1=2, far cheaper than 0-1-2 (10+10=20). Edges are usable in both directions.

Input: (6, [[0,1,7],[0,2,9],[0,5,14],[1,2,10],[1,3,15],[2,3,11],[2,5,2],[3,4,6],[5,4,9]], 0, 4, False)

Expected Output: 20

Explanation: Classic undirected Dijkstra example. Shortest 0->4 is 0-2-5-4 = 9+2+9 = 20 (better than 0-2-3-4 = 9+11+6 = 26).

Input: (2, [[0,1,5]], 0, 1, False)

Expected Output: 5

Explanation: A single undirected edge of weight 5 between source and target.

Input: (3, [[0,1,1],[0,1,4],[1,2,2]], 0, 2, True)

Expected Output: 3

Explanation: Parallel edges 0->1 of weights 1 and 4; Dijkstra picks the cheaper (1), then 1->2 (2), total 3. Confirms duplicate edges are handled.

Hints

Run two Dijkstra searches at once: a forward one from s on the original graph and a reverse one from t on the edge-reversed graph. Keep separate distance arrays dist_f and dist_r and a min-heap for each.
Each time you relax an edge into a node v that the OTHER search has already reached, update best = min(best, dist_f[u] + w + dist_r[v]). Do not assume the answer is found the instant the frontiers first touch — that touching node is not always on the shortest path.
Correct termination: stop when (top key of forward heap) + (top key of reverse heap) >= best. At that point no unexplored path can be shorter than the best meeting value already recorded. For unreachable targets one heap empties first; return -1.
Handle s == t up front (answer 0), and for undirected graphs add each edge to both the forward and the reverse adjacency lists in both directions.

Quick Overview