DSA: Graph Traversals (Dijkstra, Bellman-Ford) & Dynamic Programming Patterns
Standard algorithms, time/space complexity derivations, and standard DP paradigms (0/1 Knapsack, LCS, LIS) tested in technical rounds.
In-Depth Interview Questions & Model Solutions
Q1Compare Dijkstra’s Algorithm and Bellman-Ford Algorithm. Why does Dijkstra fail on negative weight cycles?
Dijkstra solves Single Source Shortest Path for graphs with non-negative edge weights using a Greedy approach with a Priority Queue (Time: O((V + E) log V)). It assumes that once a node is extracted from the priority queue with minimal distance, its shortest distance is finalized. With negative edges, this greedy assumption breaks. Bellman-Ford relaxes all E edges (V - 1) times using Dynamic Programming (Time: O(V * E)) and can detect negative weight cycles if an edge can still be relaxed on the V-th iteration.
- Dijkstra: Greedy, requires non-negative weights, O((V+E) log V).
- Bellman-Ford: DP, handles negative weights, detects negative cycles, O(V*E).
- Floyd-Warshall solves All-Pairs Shortest Path in O(V^3).
Q2Explain the 0/1 Knapsack Problem and formulate its recurrence relation.
Given N items with weights W[i] and values V[i], and a knapsack of capacity C, maximize total value without exceeding capacity. Recurrence: `dp[i][w] = max(dp[i-1][w], V[i-1] + dp[i-1][w - W[i-1]])` if `W[i-1] <= w`, else `dp[i-1][w]`. Time Complexity is O(N * C) and Space is O(N * C) reducible to O(C) using 1D rolling array traversed backwards.
- Pseudo-polynomial time complexity dependent on capacity C.
- Fractional Knapsack is solved in O(N log N) using Greedy method.
- Backwards traversal in 1D array prevents reusing the same item multiple times.
Technical Panel Interview Strategy Tips
- In board interviews, state both the brute force recursive approach and the memoized/tabulated DP approach.
- Always discuss Big-O, Big-Omega, and Big-Theta space/time trade-offs.