How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Akuna Capital.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Akuna Capital during technical interviews.

Maximize profitable pairs | Akuna Capital Coding Question

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 Maximize profitable pairs states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Maximize profitable pairs

Company: Akuna Capital

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an array profits of n integers representing net profit per item and an integer threshold T. You may form disjoint pairs (i, j). What is the maximum number of pairs such that profits[i] + profits[j] >= T? Describe an O(n log n) algorithm using sorting and a left/right pointer strategy, prove correctness, analyze complexity, and discuss edge cases (odd n, negative values, very large or very small T). Provide pseudocode.

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 Maximize profitable pairs states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given an array `profits` of `n` integers representing the net profit per item, and an integer threshold `T`. You may form disjoint pairs `(i, j)` (each index used in at most one pair). Return the maximum number of pairs you can form such that `profits[i] + profits[j] >= T`. Use an O(n log n) approach: sort the array, then use a left/right two-pointer scan. If the smallest and largest available values already sum to at least `T`, pair them and move both pointers inward; otherwise the smallest value cannot reach `T` even with the largest partner, so discard it (advance the left pointer). Example 1: Input: profits = [1, 2, 3, 4, 5], T = 6 Output: 2 Explanation: Pair (5,1) -> sum 6, and pair (4,2) -> sum 6. The 3 is left unpaired. 2 pairs. Example 2: Input: profits = [1, 1, 1, 1], T = 10 Output: 0 Explanation: No two values sum to at least 10. Example 3: Input: profits = [10, -10, 3, 3], T = 0 Output: 2 Explanation: Pair (10,-10) -> 0, pair (3,3) -> 6. 2 pairs.

Constraints

0 <= n <= 10^5
-10^9 <= profits[i] <= 10^9
-10^9 <= T <= 10^9
Each index may be used in at most one pair (pairs are disjoint).

Examples

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

Expected Output: 2

Explanation: Pairs (5,1) and (4,2) each sum to 6; 3 is left over.

Input: ([5, 5, 5, 5], 10)

Expected Output: 2

Explanation: Two pairs of (5,5), each summing to 10.

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

Expected Output: 0

Explanation: No pair reaches 10.

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

Expected Output: 2

Explanation: Sorted [-3,-2,4,5]: (-3,5)=2>=1 and (-2,4)=2>=1, so 2 pairs.

Input: ([], 5)

Expected Output: 0

Explanation: Empty array: no pairs.

Input: ([7], 3)

Expected Output: 0

Explanation: A single element cannot form a pair.

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

Expected Output: 1

Explanation: Pair (0,0)=0>=0; the third 0 is unpaired (odd n).

Input: ([10, -10, 3, 3], 0)

Expected Output: 2

Explanation: (10,-10)=0 and (3,3)=6, both >= 0.

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

Expected Output: 3

Explanation: Threshold is very small, so every value pairs: 3 pairs from 6 elements.

Input: ([2, 2, 2, 2], 5)

Expected Output: 0

Explanation: Max pair sum is 4 < 5, so no pairs.

Hints

Sort the array first. After sorting, the optimal strategy can be decided greedily from the two ends.
Use two pointers: left at the smallest value, right at the largest. If their sum >= T, this is a valid pair — count it and move both inward.
If profits[left] + profits[right] < T, then profits[left] cannot meet the threshold with ANY available partner (right is the largest left). Discard left (advance it) and try again.
Greedy exchange argument: pairing the current smallest unpairable-or-pairable value with the largest never loses an achievable pairing, so this maximizes the count.

Quick Overview