Floyd-Warshall and Subset Sum Interview Questions: 10 Worked Answers

Knowing an algorithm's name is not enough in an interview. You need to define its state, derive its transition, trace real values, defend the loop order and adapt when the constraints change. These ten worked questions cover Floyd-Warshall and Subset Sum with the follow-ups that naturally grow from the first answer. Here, Floyd means Floyd-Warshall for all-pairs shortest paths, not Floyd's cycle-detection algorithm. Use the wider Coding & DSA collection when you want to place these ideas beside other core algorithms.

1. Question 1: When should you choose Floyd-Warshall?

Choose Floyd-Warshall when you need the shortest distance between every ordered pair of vertices and an O(V^3) dynamic programme is acceptable. It uses O(V^2) distance-table space. Negative edges are allowed, but shortest paths are undefined for pairs that can exploit a reachable negative cycle.

Match the algorithm to the request. One unweighted source suggests BFS. One source with non-negative weighted edges suggests Dijkstra. All pairs on a small or dense graph is a natural Floyd-Warshall case. The BFS, DFS and Dijkstra comparison helps separate those request shapes.

Define D^(k)[i][j] as the shortest i -> j distance whose intermediate vertices may come from the first k vertices. Then:

D^(k)[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])

The two choices are simple: do not use vertex k, or route through k.

2. Questions 2 and 3: Initialise and trace Floyd-Warshall

Question 2: How is the table initialised?

Use vertex order A, B, C, D. Put 0 on the diagonal, each direct edge weight in its cell and ∞ where no edge exists. For edges A->B=3, A->D=7, B->A=8, B->C=2, C->A=5, C->D=1 and D->A=2, the initial rows and every later stage are:

Question 3: Which updates should you explain aloud?

With C allowed, A->D improves from 7 to A->C + C->D = 5 + 1 = 6. With D allowed, B->A improves from 7 to B->D + D->A = 3 + 2 = 5. The final A->D route is A->B->C->D, costing 3 + 2 + 1 = 6.

3. Questions 4 and 5: Defend loop order, paths and negative cycles

Question 4: Why must k be the outer loop?

After iteration k, every stored distance may use intermediates only from {A,...,k}. Keeping k outermost preserves that invariant during the in-place update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). An arbitrary i-outer or j-outer order loses this clean DP guarantee. If ∞ is represented by a large integer, guard the addition so ∞ + x cannot overflow.

To recover paths, set next[i][j] = j for a direct edge. When a route through k improves a distance, assign next[i][j] = next[i][k]. Repeatedly following next reconstructs A->B->C->D for cost 6.

Question 5: What about negative weights and cycles?

Negative edges are valid. After Floyd-Warshall, dist[v][v] < 0 reveals a reachable negative cycle in that computed region. Adding D->B = -4 creates B->C->D->B with cost 2 + 1 - 4 = -1, so a cycle vertex gets a negative diagonal. Do not report a finite shortest route for any pair that can use this cycle.

4. Questions 6 and 7: Derive Subset Sum and solve an instance

Question 6: What is the DP state and recurrence?

For non-negative values, define dp[i][s] as true when a subset of the first i items sums to s. Set dp[0][0] = true and dp[0][s] = false for s > 0. If the current item is x:

dp[i][s] = dp[i-1][s] || dp[i-1][s-x] when s >= x.

This is exclude versus include. It costs O(nT) time and O(nT) space, reducible to O(T) for a yes/no answer. The habit to define the state before writing code prevents most recurrence errors.

Question 7: Does [3,34,4,12,5,2] contain a subset summing to 9?

Track only sums 0 through 9:

The answer is true. The witness {4,5} gives 4 + 5 = 9. Items 34 and 12 exceed the target, so neither changes this bounded table. To reconstruct a witness, retain the 2D table or predecessor choices and walk backwards from (i,9). A one-row boolean array proves existence but forgets which items were chosen.

5. Question 8: Why does one-dimensional Subset Sum update backwards?

Use descending sums:

dp[0] = true
for each item x:
    for s from T down to x:
        dp[s] = dp[s] || dp[s-x]

The right-hand value then still represents the row before item x, so that item is used at most once. With one item 3 and target 9, an ascending loop sets dp[3] from dp[0], then dp[6] from the new dp[3], then dp[9] from the new dp[6]. It reuses one 3 three times and solves an unbounded problem. Thus [3] cannot make 6, while [3,3] can because the two positions are separate items.

6. Question 9: How should the solution change with the constraints?

For example, [7,-3,2] reaches 4 through {7,-3}. A table indexed only from 0 to T cannot directly represent every intermediate sum, and the standard s >= x recurrence assumes non-negative x.

Keep nearby variants separate. Decision Subset Sum asks whether T is reachable. Equal partition first needs an even total, then targets half. 0/1 knapsack maximises value under a capacity instead of returning only reachability.

7. Question 10: What answer traps should you catch?

For Floyd-Warshall, check that the diagonal starts at 0, ∞ is preserved safely, k is outermost, negative edges are allowed and negative cycles are not assigned finite shortest paths. For Subset Sum, set dp[0] true, update a 1D row downwards, distinguish a subset from a contiguous subarray and remember that O(nT) is pseudo-polynomial, not polynomial in the bit-length of an arbitrarily large T.

A strong 30-second answer names the state, transition, base case, loop order, complexity and one limitation. Your numerical checksums are A->D = 6 through A->B->C->D, and target 9 is true through {4,5}.

For answer-choice practice, solve the Floyd-Warshall and Subset Sum MCQs. Continue with DSA using Java for a structured algorithms path, or Coding for Placements for broader interview preparation.