← Akuna Capital Interview Insights

Akuna Capital·Data Scientist·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Interviewed for a Data Scientist role at Akuna Capital and got hit with a sorting/swaps problem that looks deceptively simple until duplicates enter the picture. Algorithmic round, pretty focused on correctness and edge case handling.

Questions Asked (1)

Q1

Given an integer array that may contain duplicates, what is the minimum number of swaps needed to sort it in non-decreasing order? You can swap any two indices at any time.

Algorithms & Data Structures
Author's notes

The duplicate part is what got me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding cycles in a permutation that maps the current array to its sorted version, then sum the minimum swaps per cycle. For duplicates, handle them by assigning stable ranks to equal elements so the mapping is well-defined.

Pro tip: Emphasize that the minimum swaps equals n minus the number of cycles in the permutation, and that duplicates are resolved by stable sorting to avoid ambiguity.

1. Sort and map

Create a sorted copy of the array and map each element to its target position, using stable sorting to assign consistent ranks to duplicates.

2. Build permutation

Construct a permutation array where each index points to the target index of the element currently at that position.

3. Find cycles

Traverse the permutation to identify cycles; each cycle of length k requires k-1 swaps to resolve.

4. Sum swaps

Sum (k-1) over all cycles to get the total minimum number of swaps.

5. Complexity analysis

State that the algorithm runs in O(n log n) time due to sorting, with O(n) additional space for the permutation and visited array.

Key Points to Mention

  • Minimum swaps equals n minus the number of cycles in the permutation.
  • Duplicates require stable sorting to assign unique target positions.
  • Cycle detection can be done with a visited array or in-place marking.
  • Time complexity is dominated by sorting: O(n log n).
  • Space complexity is O(n) for the permutation and visited tracking.
  • The approach works for any permutation-based sorting problem.

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