PracHub
QuestionsCoachesLearningGuidesInterview Prep

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 Solve three C++ algorithmic tasks states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

  • Medium
  • Akuna Capital
  • Coding & Algorithms
  • Software Engineer

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.

Input: ([2, 8, 4, 10, 6], 20)

Expected Output: 110

Explanation: Classic LC1648 example; greedy top-down sales total 110.

Input: ([1000000000], 1)

Expected Output: 1000000000

Explanation: Single sale at the max price; no modulo wrap needed.

Input: ([1], 1)

Expected Output: 1

Explanation: One unit at price 1.

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

Expected Output: 6

Explanation: Three types each at 2; sell one unit from each -> 2+2+2 = 6.

Hints

  1. Always sell the most expensive unit available; sort prices descending and peel off the top band.
  2. 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.
  3. 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).
  4. 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.

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

Expected Output: 0

Explanation: 5 never appears, so no subarray qualifies.

Input: ([5], 5, 5)

Expected Output: 1

Explanation: The single-element subarray [5] has min == max == 5.

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

Expected Output: 4

Explanation: [2,1,4], [1,4], [1,4,3], [2,1,4,3] all have min 1 and max 4.

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

Expected Output: 1

Explanation: Only the full array spans both extreme bounds.

Hints

  1. Any value outside [minVal, maxVal] can never be part of a valid subarray — treat its index as a fresh left boundary and reset state.
  2. For a subarray to qualify, it must contain at least one minVal and at least one maxVal; track the latest index of each.
  3. 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.
  4. 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.

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

Expected Output: 2

Explanation: [1,0]~[0,1] (complements) and [1,1]~[0,0] (complements): 1 + 1 = 2 pairs.

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

Expected Output: 0

Explanation: A single row forms no pairs.

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

Expected Output: 6

Explanation: All four rows collapse to one equivalence class: 4*3/2 = 6 pairs.

Input: ([],)

Expected Output: 0

Explanation: Empty matrix has no rows and no pairs.

Hints

  1. 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.
  2. 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.
  3. Pack the m <= 30 bits into a single integer mask so each row's canonical form is one hashable key.
  4. 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Graph Spread and Portfolio Trades - Akuna Capital (medium)
  • Find minimum swaps to sort array with duplicates - Akuna Capital (hard)
  • Break a palindrome to smallest non-palindrome - Akuna Capital (Medium)
  • Heapify an array into a max-heap - Akuna Capital (Medium)
  • Compute max profit across dated stock quotes - Akuna Capital (Medium)