Implement flat_map and design wealth redistribution
Company: Qube Research & Technologies
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Part 1 — Implement a flat_map: Design and implement an associative container flat_map backed by a sorted dynamic array of (Key, Value) pairs. Support APIs: constructor(s), size/empty, clear, find, count, contains, at, operator[], lower_bound/upper_bound, insert (single and range), emplace, erase (by key/iterator/range), iteration in sorted key order, copy/move semantics, and equality comparison. Enforce unique keys. Achieve O(log n) lookup via binary search and amortized O(n) insertion with minimal reallocations. Implement a conforming bidirectional iterator (and const_iterator) with correct validity/invalidations on insert/erase, and ensure iterator arithmetic/relational operators behave as specified. Provide unit tests for edge cases (empty container, duplicates, key and value types with non-trivial moves, iterator invalidation, const-correctness). Explain your design choices and complexity trade-offs versus tree-based maps.
Part 2 — Redistribute wealth: Given an integer array representing individuals’ wealth (values may be negative, zero, or positive), design an algorithm to redistribute wealth via integer transfers between indices so that final wealths are as equal as possible while preserving the total sum. a) State and justify a precise objective (e.g., minimize maximum absolute deviation from the target, or minimize total absolute deviation). b) Determine the optimal target wealth value(s) under your objective when only integer amounts are allowed. c) Output a sequence of transfers (i, j, amount) that transforms the initial array to the final array, along with the final wealths. d) Prove correctness and analyze time and space complexity. Discuss alternative objectives and how they change the algorithm.
Quick Answer: This question evaluates low-level data structure implementation skills (designing an associative flat_map with sorted dynamic array storage, unique-key semantics, iterator correctness and amortized complexity) alongside algorithmic optimization and proof-based reasoning for integer-constrained wealth redistribution.
You are given an integer array `wealth` where `wealth[i]` is the money held by individual `i` (values may be negative, zero, or positive). You may move integer amounts of money between individuals. The total sum must be preserved. Make the final wealths as equal as possible.
Because the sum may not divide evenly by `n`, perfect equality is usually impossible. Under the standard objective of minimizing the total absolute deviation from the mean (equivalently minimizing the total amount of money that has to be moved), the optimal final array consists only of the two values `floor(sum/n)` and `ceil(sum/n)`: exactly `r = sum mod n` people end up with `ceil(sum/n)` and the rest with `floor(sum/n)` (using floored division so this holds for negative sums too).
Return a tuple `(min_moved, final)` where:
- `min_moved` is the minimum total amount of money that must be transferred to reach an optimal final distribution, and
- `final` is the resulting wealth array (same length as input, same order as the input indices).
To minimize the money moved, assign the higher target value `ceil(sum/n)` to the individuals who currently hold the most. `min_moved` then equals the sum over all `i` of `max(0, wealth[i] - final[i])` (total surplus pushed out), which also equals the total deficit pulled in.
Note on Part 1 (from the original interview): the question also asked to implement a C++ `flat_map` (a sorted-vector-backed associative container with binary-search lookup, amortized O(n) insert, and a conforming bidirectional iterator). That part is an API-design exercise judged on container conformance, not a single function, so it is not part of this runnable console.
Constraints
- 1 <= n <= 10^5 (n == 0 returns (0, []))
- -10^9 <= wealth[i] <= 10^9
- The total sum must be preserved by the redistribution.
- Only integer transfer amounts are allowed.
- Objective: minimize total amount of money moved (equivalently, minimize total absolute deviation from the mean).
Examples
Input: ([1, 0, 0, 0, 0],)
Expected Output: (0, [1, 0, 0, 0, 0])
Explanation: Sum 1, n 5: base=0, r=1, so one person keeps 1 and the rest 0. Already optimal, nothing to move.
Input: ([1, 2, 3, 4, 5],)
Expected Output: (3, [3, 3, 3, 3, 3])
Explanation: Sum 15 divides evenly: everyone becomes 3. The two richest push out (4->3)=1 and (5->3)=2, total 3 moved.
Input: ([5, 5, 5],)
Expected Output: (0, [5, 5, 5])
Explanation: Already equal; no transfers needed.
Input: ([0, 0, 7],)
Expected Output: (4, [2, 2, 3])
Explanation: Sum 7, n 3: base=2, r=1. The richest (7) gets the ceil slot 3, others get 2. Moved = 7-3 = 4.
Input: ([-3, 0, 9],)
Expected Output: (7, [2, 2, 2])
Explanation: Negative wealth supported. Sum 6, n 3: everyone becomes 2. Only positive surplus is 9->2 = 7 moved (it covers both deficits).
Input: ([10],)
Expected Output: (0, [10])
Explanation: Single individual: already fully equal.
Input: ([],)
Expected Output: (0, [])
Explanation: Empty array edge case: nothing to redistribute.
Input: ([-1, -1, -1, -1],)
Expected Output: (0, [-1, -1, -1, -1])
Explanation: All-negative and already equal: no transfers.
Input: ([4, 1, 7, 2, 1],)
Expected Output: (5, [3, 3, 3, 3, 3])
Explanation: Sum 15, n 5: target 3 each. Surpluses 4->3=1 and 7->3=4 total 5 moved; deficits are filled by them.
Hints
- Perfect equality needs sum(wealth) divisible by n. Otherwise the fairest integer distribution uses only floor(avg) and ceil(avg).
- Exactly r = sum mod n people get ceil(avg) and the other n-r get floor(avg). Use floored division/mod so this also works when the sum is negative.
- The minimum money moved equals the total surplus above target, i.e. sum of max(0, wealth[i] - final[i]). Give the ceil slots to the currently-richest indices to keep both the moved amount and per-index movement minimal.