Katkat
Back

Solve three C++ algorithmic tasks

Akuna CapitalSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.