PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Akuna Capital
  • Coding & Algorithms
  • Software Engineer

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.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 0

Explanation: Already strictly descending -> 0 swaps.

Input: ([],)

Expected Output: 0

Explanation: Empty array needs no swaps.

Input: ([7],)

Expected Output: 0

Explanation: Single element is trivially sorted.

Input: ([2, 1],)

Expected Output: 0

Explanation: [2,1] is already descending.

Input: ([1, 2],)

Expected Output: 1

Explanation: Swap the two elements to get [2,1].

Input: ([-3, -1, -2, 0, 5],)

Expected Output: 3

Explanation: Descending target [5,0,-1,-2,-3]; permutation splits into a 2-cycle and a 3-cycle -> 1 + 2 = 3 swaps.

Input: ([10, 30, 20, 40],)

Expected Output: 1

Explanation: Target [40,30,20,10]; 10 and 40 form one 2-cycle, 30 and 20 are already placed -> 1 swap.

Hints

  1. Sorting descending tells you where every element must end up; the problem reduces to sorting a permutation by swaps.
  2. 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.
  3. 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.

Input: (3, [[0, 1], [1, 2]], 0, 2)

Expected Output: 1

Explanation: Only the chain 0-1-2 connects 0 to 2.

Input: (3, [], 0, 2)

Expected Output: 0

Explanation: No edges means s and t are disconnected.

Input: (1, [], 0, 0)

Expected Output: 1

Explanation: s == t: the trivial empty path counts as one.

Input: (4, [[0, 1], [1, 2], [2, 3], [0, 3], [0, 2]], 0, 3)

Expected Output: 3

Explanation: Paths: 0-3, 0-2-3, and 0-1-2-3.

Input: (5, [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4], [1, 4]], 0, 4)

Expected Output: 4

Explanation: Paths: 0-1-4, 0-1-2-3-4, 0-2-1-4, 0-2-3-4.

Input: (3, [[0, 1]], 0, 2)

Expected Output: 0

Explanation: Vertex 2 is isolated, so there is no path from 0 to 2.

Hints

  1. Build an adjacency list first; then DFS from s, recursing only into neighbors not on the current path.
  2. Use a boolean visited array: set it true before recursing into a neighbor and reset it to false afterward (classic backtracking).
  3. 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.

Input: ([[0, 10, 100]],)

Expected Output: 100

Explanation: A single movie is always chosen.

Input: ([[1, 2, 10], [2, 3, 10], [3, 4, 10]],)

Expected Output: 30

Explanation: All three touch only at endpoints, so all can be taken -> 30.

Input: ([[1, 4, 50], [2, 3, 10], [3, 5, 10]],)

Expected Output: 50

Explanation: The single high-rated [1,4,50] beats any combination of the smaller overlapping movies.

Input: ([[1, 3, 20], [3, 5, 20], [1, 5, 30]],)

Expected Output: 40

Explanation: [1,3,20] + [3,5,20] = 40 beats the single [1,5,30].

Input: ([[1, 100, 1], [1, 2, 5], [2, 3, 5], [3, 4, 5]],)

Expected Output: 15

Explanation: Three short non-overlapping movies (5+5+5) beat the long low-rated one.

Input: ([[5, 6, 3], [1, 2, 3], [3, 4, 3], [2, 3, 3], [4, 5, 3]],)

Expected Output: 15

Explanation: All five chain endpoint-to-endpoint with no overlap -> 5 * 3 = 15.

Hints

  1. Sort the movies by end time so that when you process movie i, every compatible earlier movie has already been considered.
  2. For each movie, binary-search the end-time array to find p(i): the last movie ending at or before this movie's start.
  3. DP recurrence: dp[i] = max(skip this movie = dp[i-1], take it = rating_i + dp[p(i)]). The answer is dp[m].
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Graph Spread and Portfolio Trades - Akuna Capital (medium)
  • Find minimum swaps to sort array with duplicates - Akuna Capital (hard)
  • Break a palindrome to smallest non-palindrome - Akuna Capital (Medium)
  • Compute min operations to transform integers - Akuna Capital (Medium)
  • Compute max profit across dated stock quotes - Akuna Capital (Medium)