Katkat
Back

Solve swaps, graph paths, and movie DP

Akuna CapitalSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.
  1. 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.
  1. 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.