Solve three C++ algorithmic tasks
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Solve the following three C++ algorithmic tasks. For each, implement an efficient function and state time and space complexity.
a) Diminishing prices revenue: Given an array inventory where inventory[i] is the initial sale price for type i, each time you sell one unit of a type, the next sale price for that type decreases by 1 down to 0. You must perform exactly orders sales across all types to maximize total revenue. Return revenue modulo 1_000_000_007. Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better.
b) Count subarrays with fixed bounds: Given an integer array nums and two integers minVal and maxVal (minVal <= maxVal), count the number of subarrays whose minimum equals minVal and whose maximum equals maxVal. Constraints: 1 <= nums.size() <= 2e5, -1e9 <= nums[i] <= 1e9. Target: O(n) time, O(
1) extra space.
c) Binary matrix row-equivalence under column flips: Given a binary matrix A with n rows and m columns (toggling a column flips that bit in every row), two rows are equivalent if one can be transformed into the other by flipping any subset of columns. Count the number of unordered pairs of equivalent rows. Return a 64-bit integer. Constraints: 1 <= n <= 1e5, 1 <= m <= 30. Target: O(n * m /
64) or better using hashing/bitmasks.
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 Solve three C++ algorithmic tasks states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Diminishing Prices Revenue (Maximize Sales Revenue)
Given an array `inventory` where `inventory[i]` is the initial sale price for color/type `i`, each time you sell one unit of a type the next sale price for that type decreases by 1 (down to a minimum of 0). You must perform exactly `orders` sales across all types to maximize total revenue. Return the maximum total revenue modulo 1_000_000_007.
Greedy idea: always sell from the currently most-expensive type. Sort the prices descending and process them in horizontal 'bands'. With `width` types currently at price >= the next distinct level, you can sell whole rectangular blocks (an arithmetic series of prices) at once instead of one unit at a time, giving O(n log n) overall.
Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better.
Example: inventory = [2,8,4,10,6], orders = 20 -> 110.
Constraints
- 1 <= inventory.size() <= 2e5
- 1 <= orders <= 1e13 (must fit in a 64-bit integer)
- 1 <= inventory[i] <= 1e9
- Return the answer modulo 1_000_000_007
Examples
Input: ([2, 5], 4)
Expected Output: 14
Explanation: Sell 5,4,3,2 from the type starting at 5 -> 5+4+3+2 = 14.
Input: ([3, 5], 6)
Expected Output: 19
Explanation: Sell 5,4 then both types at 3 (3,3), then 2 -> 5+4+3+3+2 = ... greedy max = 19.
Hints
- Always sell the most expensive unit available; sort prices descending and peel off the top band.
- When `width` types all sit above the next distinct price level, the prices you collect form an arithmetic series — sum it in O(1) with n*(top+bot)/2 instead of looping unit by unit.
- Watch the partial last band: full_rows = remaining // width complete rows, then `remaining % width` extra columns each sell one more unit at price (cur - full_rows).
- Take the modulo only at the end of each block sum; `orders` up to 1e13 needs a 64-bit type.
Count Subarrays With Fixed Bounds
Given an integer array `nums` and two integers `minVal` and `maxVal` (minVal <= maxVal), count the number of (contiguous) subarrays in which the minimum element equals exactly `minVal` and the maximum element equals exactly `maxVal`.
A single linear scan suffices. Track the most recent index where you saw `minVal`, the most recent index where you saw `maxVal`, and the most recent index of an out-of-range value (a value < minVal or > maxVal) which acts as a hard left boundary. For each right endpoint `i`, the number of valid subarrays ending at `i` is `min(lastMin, lastMax) - leftBound` when both have been seen since the last boundary, else 0.
Constraints: 1 <= nums.size() <= 2e5, -1e9 <= nums[i] <= 1e9. Target: O(n) time, O(1) extra space.
Example: nums = [1,3,5,2,7,5], minVal = 1, maxVal = 5 -> 2.
Constraints
- 1 <= nums.size() <= 2e5
- -1e9 <= nums[i] <= 1e9
- minVal <= maxVal
- The count can exceed 32-bit range; use a 64-bit accumulator
Examples
Input: ([1, 3, 5, 2, 7, 5], 1, 5)
Expected Output: 2
Explanation: Valid subarrays are [1,3,5] and [1,3,5,2] (each has min 1 and max 5).
Input: ([1, 1, 1, 1], 1, 1)
Expected Output: 10
Explanation: Every one of the 4*5/2 = 10 subarrays has min == max == 1.
Hints
- Any value outside [minVal, maxVal] can never be part of a valid subarray — treat its index as a fresh left boundary and reset state.
- For a subarray to qualify, it must contain at least one minVal and at least one maxVal; track the latest index of each.
- Subarrays ending at i are valid only if they start after the boundary and include both the latest minVal and latest maxVal, so the count is min(lastMin, lastMax) - leftBound.
- When minVal == maxVal, the same element satisfies both conditions simultaneously.
Binary Matrix Row Equivalence Under Column Flips
Given a binary matrix `A` with `n` rows and `m` columns, toggling a column flips that bit in every row. Two rows are considered equivalent if one can be transformed into the other by flipping any subset of columns. Count the number of unordered pairs of equivalent rows.
Key observation: flipping a subset of columns is the same as XOR-ing both rows by the same mask. A row r1 can become r2 iff r1 XOR r2 is achievable by some column mask — which it always is, for the mask equal to r1 XOR r2. But the SAME mask must apply to both rows being compared, so the real equivalence is: r1 and r2 are equivalent iff they are identical OR exact bitwise complements. Normalize every row by flipping the whole row when its first bit is 1 (forcing the leading bit to 0); identical and complementary rows collapse to the same canonical form. Group rows by canonical form and sum c*(c-1)/2 over each group.
Constraints: 1 <= n <= 1e5, 1 <= m <= 30. Return a 64-bit integer. Target: O(n*m) (or O(n*m/64) with bitmask packing).
Example: A = [[0,1,0],[1,0,1],[0,0,0]] -> 1 (rows 0 and 1 are complements).
Constraints
- 1 <= n <= 1e5
- 1 <= m <= 30 (a row fits in a 32-bit mask)
- Every entry of A is 0 or 1
- Return a 64-bit integer (up to ~n^2/2 pairs)
Examples
Input: ([[0, 1, 0], [1, 0, 1], [0, 0, 0]],)
Expected Output: 1
Explanation: Rows [0,1,0] and [1,0,1] are complements (equivalent); [0,0,0] is alone. One pair.
Input: ([[0, 0], [0, 0], [0, 0]],)
Expected Output: 3
Explanation: All three rows are identical: 3*2/2 = 3 pairs.
Hints
- Flipping a column XORs the same bit across all rows; two rows are reachable from each other only if they are identical or exact complements.
- Canonicalize each row by XOR-ing it with its own first bit, forcing the leading bit to 0 — identical and complementary rows then map to the same key.
- Pack the m <= 30 bits into a single integer mask so each row's canonical form is one hashable key.
- Within each equivalence group of size c, the number of unordered pairs is c*(c-1)/2; sum across groups using a 64-bit accumulator.