← Akuna Capital Interview Insights

Akuna Capital·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Akuna Capital quant engineer interview, got a graph-based sorting problem that looked like a plain array question until you actually read it carefully. The duplicate handling is where things get interesting and where I suspect most people slip up.

Questions Asked (1)

Q1

Given an array of integers that may contain duplicates, find the minimum number of swaps needed to sort it in non-decreasing order.

Algorithms & Data Structures
Author's notes

My first instinct was to just think about inversions and I was completely off base.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First clarify that the array may contain duplicates and that we need the minimum number of swaps to sort it. Then explain that the problem reduces to finding cycles in a permutation, but with duplicates we must group equal elements and match them to their sorted positions to minimize swaps. Finally, describe an algorithm that counts the number of elements already in their correct group and computes swaps as (number of misplaced elements) - (number of cycles among misplaced elements).

Pro tip: Mention that duplicates make the problem trickier because multiple valid sorted arrays exist; the key is to map each element to its correct group in the sorted array and then count cycles only among misplaced elements. Also, note that the answer is not simply n minus the number of cycles in the full permutation when duplicates are present.

1. Clarify the problem and constraints

Confirm that the array can have duplicates, that we need the minimum number of swaps to achieve non-decreasing order, and discuss edge cases like already sorted or all elements equal.

2. Create a sorted copy and map positions

Sort a copy of the array to get the target order. For each element, determine its correct group (range of indices) in the sorted array, handling duplicates by grouping equal values.

3. Identify misplaced elements and build a graph

Mark elements that are not in their correct group. Build a directed graph where each misplaced element points to the position it should occupy in the sorted array, considering duplicates.

4. Count cycles among misplaced elements

Traverse the graph to count the number of cycles formed by misplaced elements. Each cycle of length k requires k-1 swaps to resolve.

5. Compute minimum swaps and verify with examples

The minimum swaps is the total number of misplaced elements minus the number of cycles. Walk through a small example with duplicates to confirm the logic.

Key Points to Mention

  • The problem is a variant of the minimum swaps to sort array problem, complicated by duplicates.
  • Duplicates mean multiple valid sorted arrays; we must map each element to its correct group in the sorted array.
  • Misplaced elements form cycles; each cycle of length k requires k-1 swaps.
  • The answer is (number of misplaced elements) - (number of cycles among misplaced elements).
  • Time complexity: O(n log n) due to sorting, and O(n) for cycle detection.
  • Edge cases: already sorted array (0 swaps), all elements equal (0 swaps), and arrays with many duplicates.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.