Design and implement solutions for three tasks derived from a HackerRank-style assessment.
-
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.
-
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.
-
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.