Solve swaps, graph paths, and movie DP
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Design and implement solutions for three tasks derived from a HackerRank-style assessment.
1) Minimum swaps to reverse sort an array:
- Input: an integer array A of length n with distinct values. Allowed operation: swap any two indices i and j; each swap costs 1.
- Output: the minimum number of swaps needed to reorder A into strictly descending order.
- Requirements: Provide an O(n log n) approach (e.g., sort with index mapping and cycle decomposition/greedy). Prove correctness and analyze time/space. Briefly note how you would adapt if duplicates can appear.
2) Enumerate simple paths in a graph via backtracking:
- Input: an undirected graph G = (V, E) with vertices labeled 0..n-1, and two vertices s and t.
- Task: return all simple paths from s to t (no vertex repeats) using backtracking. If the number of paths is huge, return the count and support streaming/yielding paths.
- Requirements: Prevent cycles with visited sets, discuss pruning heuristics (e.g., degree bounds, early exits), and analyze worst-case time/space complexity.
3) Movie ratings scheduling using bottom-up DP (weighted interval scheduling):
- Input: m movies; each movie i has start time s_i, end time e_i (e_i > s_i), and rating w_i.
- Task: choose a subset of non-overlapping movies maximizing total rating.
- Requirements: Provide an O(m log m) bottom-up DP: sort by end time, compute p(i) (the rightmost movie that finishes before s_i), define DP[i] = max(DP[i-1], DP[p(i)] + w_i), reconstruct one optimal set, and analyze complexity. Explain why naive backtracking is exponential and would time out.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve swaps, graph paths, and movie DP states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Minimum Swaps to Sort Descending
You are given an integer array `A` of length `n` with all-distinct values. In one operation you may swap the elements at any two indices `i` and `j` (cost 1 per swap). Return the minimum number of swaps needed to reorder `A` into strictly descending order.
Use an O(n log n) approach: build the target (descending-sorted) array, map each value to its target index, and decompose the permutation into cycles. A cycle of length `k` needs exactly `k - 1` swaps, so the answer is `n - (number of cycles)`.
Example: `A = [4, 3, 1, 2]`. Descending target is `[4, 3, 2, 1]`. Only the values `1` and `2` are out of place (one 2-cycle), so one swap suffices -> answer `1`.
Constraints
- 0 <= n <= 10^5
- All values in A are distinct
- Values fit in a 64-bit signed integer
- If duplicates were allowed, ties must be broken by a stable rule (e.g. original index) before building the target permutation.
Examples
Input: ([4, 3, 1, 2],)
Expected Output: 1
Explanation: Target is [4,3,2,1]; only 1 and 2 are swapped (one 2-cycle) -> 1 swap.
Input: ([1, 2, 3, 4, 5],)
Expected Output: 2
Explanation: Reversing 1..5 forms two 2-cycles (1<->5, 2<->4); the middle is fixed -> 2 swaps.
Hints
- Sorting descending tells you where every element must end up; the problem reduces to sorting a permutation by swaps.
- Minimum swaps to fix a permutation = (number of elements out of place) - (number of cycles among them). Equivalently each cycle of length k costs k-1 swaps.
- Walk each unvisited index, follow the chain i -> target_position(A[i]) until you return to the start, and add (cycle_length - 1).
Count Simple Paths in an Undirected Graph
You are given an undirected graph with `n` vertices labeled `0..n-1`, an edge list `edges` (each edge is a pair `[u, v]`), and two vertices `s` and `t`. Return the number of distinct simple paths from `s` to `t` (a simple path visits no vertex more than once).
Use backtracking with a visited set: mark `s`, recurse into each unvisited neighbor, and count a path every time the recursion reaches `t`. Unmark on the way back so other branches can reuse the vertex. If `s == t`, the empty path counts as one.
Example: a 4-cycle `0-1-3` and `0-2-3` gives exactly two simple paths from `0` to `3`.
Constraints
- 1 <= n <= 20 (enumeration is exponential; small graphs only)
- 0 <= u, v < n, edges are undirected and may be assumed simple (no self-loops / parallel edges)
- 0 <= s, t < n
- When s == t the count includes the trivial zero-length path (1).
Examples
Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]], 0, 3)
Expected Output: 2
Explanation: The two routes 0-1-3 and 0-2-3 are the only simple paths.
Input: (2, [[0, 1]], 0, 1)
Expected Output: 1
Explanation: A single edge gives exactly one path.
Hints
- Build an adjacency list first; then DFS from s, recursing only into neighbors not on the current path.
- Use a boolean visited array: set it true before recursing into a neighbor and reset it to false afterward (classic backtracking).
- Increment the counter exactly when the current vertex equals t, then return without exploring further from t.
Movie Ratings Scheduling (Weighted Interval Scheduling)
You are given `m` movies; each movie is `[start, end, rating]` with `end > start`. Two movies overlap only if their open intervals intersect (movies that merely touch at an endpoint, e.g. `[1,2]` and `[2,3]`, do NOT overlap). Choose a subset of pairwise non-overlapping movies that maximizes the total rating, and return that maximum total.
Use an O(m log m) bottom-up DP. Sort movies by end time. For movie `i`, let `p(i)` be the rightmost movie that finishes at or before `start_i` (found by binary search on end times). Then `DP[i] = max(DP[i-1], rating_i + DP[p(i)])`. The answer is `DP[m]`.
Naive backtracking over every include/exclude choice is O(2^m) and times out; the DP collapses overlapping subproblems.
Constraints
- 0 <= m <= 10^5
- Each movie is [start, end, rating] with end > start
- rating >= 0
- Movies sharing an endpoint (one ends exactly when another starts) are NOT considered overlapping.
Examples
Input: ([[1, 3, 5], [2, 5, 6], [4, 6, 5], [6, 7, 4]],)
Expected Output: 14
Explanation: Pick [1,3,5] + [4,6,5] + [6,7,4] = 14; they are pairwise non-overlapping.
Input: ([],)
Expected Output: 0
Explanation: No movies -> total rating 0.
Hints
- Sort the movies by end time so that when you process movie i, every compatible earlier movie has already been considered.
- For each movie, binary-search the end-time array to find p(i): the last movie ending at or before this movie's start.
- DP recurrence: dp[i] = max(skip this movie = dp[i-1], take it = rating_i + dp[p(i)]). The answer is dp[m].