← 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 pretty involved algorithmic problem that felt more like a software engineering screen than anything data-science-y. The question was well-defined but had enough layers that I had to think carefully before writing a single line of pseudocode.

Questions Asked (1)

Q1

Given an array of n integers representing net profit per item and a threshold T, find the maximum number of disjoint pairs (i, j) such that profits[i] + profits[j] >= T. Design an O(n log n) solution using sorting and two pointers, prove it correct, analyze complexity, and handle edge cases like odd n, negative values, and extreme values of T.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one took me a minute to even parse.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by sorting the array, then use two pointers from both ends to greedily pair the smallest available element with the largest. If their sum meets the threshold, count the pair and move both pointers inward; otherwise, discard the smallest element by moving the left pointer. This yields the maximum number of disjoint pairs in O(n log n) time.

Pro tip: Emphasize that the greedy choice is safe because pairing the smallest element with the largest possible partner never reduces the number of future pairs—this is the key exchange argument that proves optimality.

1. Clarify and Sort

Confirm the problem constraints (disjoint pairs, threshold T) and sort the array in ascending order. Sorting is the first step of the O(n log n) algorithm.

2. Two-Pointer Greedy Scan

Initialize left = 0, right = n-1, count = 0. While left < right, if profits[left] + profits[right] >= T, increment count and move both pointers inward; else move left forward. This greedily forms pairs.

3. Prove Correctness

Use an exchange argument: if an optimal solution pairs the smallest element with some element other than the largest possible, swapping to pair it with the largest cannot decrease the number of pairs. Thus the greedy choice is safe.

4. Analyze Complexity

Sorting takes O(n log n) time, and the two-pointer scan takes O(n) time, so overall O(n log n) time. Space is O(1) extra if sorting in place, or O(n) if a copy is used.

5. Handle Edge Cases

Discuss odd n (one element left unpaired), negative values (sums can be negative, but the greedy still works), extreme T (T very large yields 0 pairs; T very small yields floor(n/2) pairs), and empty array.

Key Points to Mention

  • Sorting the array first is essential for the two-pointer approach and ensures O(n log n) time.
  • The greedy strategy: pair the smallest available element with the largest if their sum meets T; otherwise, the smallest cannot be paired with anyone, so discard it.
  • Correctness proof via exchange argument: swapping partners to match the greedy choice never reduces the number of pairs.
  • Time complexity: O(n log n) due to sorting; space complexity: O(1) extra if in-place sort, O(n) if a copy is made.
  • Edge cases: odd n leaves one unpaired; negative values are handled naturally; extreme T values (very large or very small) produce 0 or floor(n/2) pairs respectively.
  • The algorithm maximizes the number of disjoint pairs, not the sum of profits, so it's a counting problem.

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