Solve swaps, graph paths, and movie DP
Overview
This question evaluates algorithmic problem-solving across array permutation and swap reasoning, graph traversal and simple-path enumeration, and optimization via weighted interval scheduling, emphasizing correctness arguments, complexity analysis, and solution reconstruction.
Akuna Capital
Aug 8, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
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.