Revenue Referral Aggregation And Ranking

What's being tested

These problems test efficient aggregation of event streams into per-customer totals, plus selection/update of the k smallest totals under dynamic inputs. Interviewers probe algorithmic choices (selection vs. streaming top-k), data structures for incremental updates, and correctness under referral/tree propagation.

Patterns & templates

• Hash map for accumulator state: map customer -> total, O(1) amortized updates, size O(N); watch memory when N → millions.

• Max-heap of size k to maintain k smallest totals: push O(log k), keep heap size k, overall O(n log k) for one-pass selection.

• Quickselect for one-shot smallest-k selection: average O(n) time, O(1) extra space, unstable under frequent updates.

• Indexed priority queue / balanced BST for dynamic insert/update/delete with O(log n) per update when reads interleave writes.

• Euler tour + Fenwick tree (BIT) / segment tree to support subtree-sum updates and ancestor queries in O(log n) for referral-propagation problems.

• DFS/BFS to traverse referral graph for initial build or validation; detect cycles with white/gray/black visitation to enforce acyclic referrals.

• Stable tie-breaking: include deterministic secondary key (creation timestamp or id) to ensure reproducible ordering on equal revenues.

Common pitfalls

Pitfall: Using a simple sort for repeated queries — O(n log n) per query blows up when queries are frequent or state is streaming.

Pitfall: Not handling referral cycles — assume DAG only after explicitly validating inputs to avoid infinite propagation.

Pitfall: Updating all ancestors naively on every event — O(depth) per event can be O(n) worst-case; use subtree-indexed structures for scale.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.