Akuna Capital·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Akuna Capital software engineer interview with a pretty meaty algorithms question. The kind of problem where knowing the brute force isn't enough and they want to see if you can reason through the efficient solution too.

Questions Asked (1)

Given the array [5, 7, 9, 2, 3, 12, 8, 4], count the number of inversion pairs where an earlier element is greater than a later one. Walk through both a naive quadratic solution and an O(n log n) divide-and-conquer approach, and explain the complexity of each.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The brute force part was fine, nested loops, check every pair, count when arr[i] > arr[j].

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining an inversion pair and then walk through the naive O(n^2) approach, counting pairs by comparing each element with all subsequent elements. Then introduce the divide-and-conquer merge sort based approach that counts inversions during the merge step, achieving O(n log n) time. Finally, compare the complexities and discuss trade-offs.

Pro tip: Emphasize that the divide-and-conquer approach modifies merge sort to count inversions in O(n log n) time, which is optimal for comparison-based sorting. Mention that this is a common interview question at Akuna Capital, so be prepared to code it.

1. Define inversion and naive approach

Explain that an inversion is a pair (i, j) where i < j and arr[i] > arr[j]. For the naive approach, use nested loops to compare each element with all subsequent elements, incrementing a counter when an inversion is found.

2. Walk through naive example

For the given array, manually count inversions or explain the process: for each element, count how many later elements are smaller. Sum these counts to get the total inversions.

3. Introduce divide-and-conquer approach

Describe the modified merge sort: recursively split the array into halves, count inversions in each half, and count cross inversions during the merge step. When merging, if an element from the right half is smaller than an element from the left half, it forms inversions with all remaining elements in the left half.

4. Explain merge step counting

During merge, maintain two pointers for left and right halves. When the right element is smaller, increment inversion count by the number of remaining elements in the left half. Then merge the elements in sorted order.

5. Analyze complexities

Naive approach: O(n^2) time, O(1) extra space. Divide-and-conquer: O(n log n) time, O(n) extra space due to temporary arrays. Discuss trade-offs and when each might be appropriate.

Key Points to Mention

Definition of inversion pair: i < j and arr[i] > arr[j].
Naive approach uses two nested loops, resulting in O(n^2) time complexity.
Divide-and-conquer approach modifies merge sort to count inversions during merge.
In merge step, when an element from the right half is placed before an element from the left half, it forms inversions with all remaining elements in the left half.
Time complexity of divide-and-conquer is O(n log n), space complexity O(n).
Trade-offs: naive is simpler and uses less memory, but inefficient for large arrays; divide-and-conquer is efficient but uses extra space.

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