Skip to content
Hari KharelStudy

Aggregation, grouping and reporting

coreCommon atStripeMetaAmazonAnthropicRead firstHash mapsSortingPractise in the Sandbox →

Most reports are three moves: group rows by a key into a hash map of accumulators, fold each row into its bucket (count, sum, max), then order and cut with a complete sort key, ties included. One pass to group is O(n); ordering g groups is O(g log g). “Top N per group” is the same thing with a second key: partition, sort inside each partition, take N.

The idea in plain words

Section titled “The idea in plain words”

Picture a pile of receipts and a row of labelled envelopes. You pick up each receipt once, read its region, and drop it in the right envelope, creating a new envelope the first time you see a region. You don’t need to keep the receipts, only a running tally on each envelope: how many, how much in total, the biggest one.

That’s GROUP BY. The envelope label is the key. The tally is the accumulator. Folding one receipt into a tally is O(1), so the whole pile is O(n).

Then the report: “regions by total, highest first”. That’s a sort of the envelopes, not the receipts. And as soon as two envelopes have the same total, someone will ask which comes first. The answer must be in your sort key, not left to chance.

Term Meaning
Group key What you bucket by. Can be a tuple: (region, month).
Aggregate A summary of a bucket: COUNT, SUM, MIN, MAX, AVG.
Decomposable aggregate Can be built from partial results: sum of sums, max of maxes. AVG is not, but (sum, count) is.
Tie-break The extra sort key that makes the order total (then name ascending).
Window function SQL that computes per-row values over a partition without collapsing rows: ROW_NUMBER() OVER (PARTITION BY region ORDER BY amount DESC).

See it

Section titled “See it”

Step through the fold: each row lights up its bucket and updates the running aggregate. Change the key or the aggregate and replay. Then switch the view to window: top N per group and edit amounts to create ties: watch ROW_NUMBER, RANK and DENSE_RANK disagree, and see which rows survive the filter.

Group, aggregate, rank
edit amounts
idregionrepproductamount
1EUanapen
2USbobink
3EUchenink
4APACdevpad
5EUanacap
6USbobpen
7EUchenpad
8APACdevink
9USanacap
regionSUM(amount)
(no buckets yet)
GROUP BY region: one pass over the rows, one accumulator per distinct region. Accumulators hold count, sum and max, enough for every aggregate (avg = sum / count).
1 / 11

When to reach for it

Section titled “When to reach for it”
The problem says… What fits
“total / count / average per customer, merchant, day…” Hash map from key to accumulator, one pass.
“top N overall, sorted by X descending, then by name” Aggregate, then sort with a tuple key, then slice. Or a size-N heap if N ≪ groups.
“top N in each category” Partition by category, rank inside each partition. In SQL, ROW_NUMBER() OVER (PARTITION BY …).
“only groups with more than 3 orders” Filter after aggregating: SQL HAVING, not WHERE.
“running total”, “change since previous day” Window functions (SUM() OVER (ORDER BY day), LAG), or prefix sums in code.
“per hour / per day buckets” The key is a time bucket: ts - ts % 3600. See time handling.
“frequent queries over changing data” Maintain aggregates incrementally on each write instead of recomputing.

How it works

Section titled “How it works”

Group and aggregate

Section titled “Group and aggregate”
  1. Create a map from key to accumulator. Make an accumulator the first time a key appears.
  2. One pass: for each row, find its bucket and fold the row in (count += 1, total += amount, max = max(…)).
  3. Order the output explicitly. Hash maps give insertion order (Python, JS Map) or no promised order at all (C# Dictionary).
by_region.py
from collections import defaultdict
from dataclasses import dataclass




@dataclass(frozen=True)
class Sale:
    region: str
    product: str
    cents: int




@dataclass
class Stats:
    count: int = 0
    total: int = 0
    max: int = 0




def by_region(sales: list[Sale]) -> dict[str, Stats]:
    groups: dict[str, Stats] = defaultdict(Stats)   # 1. one accumulator per key, made on first sight
    for s in sales:                                  # 2. one pass: fold each row into its bucket
        g = groups[s.region]
        g.count += 1
        g.total += s.cents
        g.max = max(g.max, s.cents)
    return dict(sorted(groups.items()))              # 3. sort keys: dict order is insertion order




if __name__ == "__main__":
    sales = [Sale("EU", "pen", 300), Sale("US", "ink", 1200), Sale("EU", "ink", 900), Sale("EU", "pen", 300)]
    stats = by_region(sales)
    assert list(stats) == ["EU", "US"]
    assert (stats["EU"].count, stats["EU"].total, stats["EU"].max) == (3, 1500, 900)
    assert stats["EU"].total // stats["EU"].count == 500   # average from sum and count, exact ints
    assert by_region([]) == {}                              # empty input -> no groups, not a zero row
    print("ok")

Language notes worth knowing:

  • Python: collections.defaultdict and Counter cover most cases. itertools.groupby only groups adjacent equal keys, so it needs sorted input; it’s a classic bug to use it on unsorted rows.
  • TypeScript: Map with get ?? init. ES2024 added Object.groupBy and Map.groupBy (Node 21+), which build arrays of rows per key; you still fold them yourself.
  • C#: LINQ GroupBy yields groups in first-seen order of keys, each an IGrouping<TKey, T>. ToLookup is the eager version. .NET 9 adds CountBy and AggregateBy that fold without materializing groups.

Top N per group

Section titled “Top N per group”
  1. Aggregate to the grain you rank at, e.g. revenue per (region, product).
  2. Regroup by the partition key (region).
  3. In each partition, sort by the full key (-revenue, then product), then take the first N.
top_n_per_group.py
from collections import defaultdict




def top_n_per_group(rows: list[tuple[str, str, int]], n: int) -> dict[str, list[tuple[str, int]]]:
    """Top n products by revenue in each region. Ties: product name ascending."""
    revenue: dict[tuple[str, str], int] = defaultdict(int)
    for region, product, cents in rows:            # 1. aggregate to (group, item) totals first
        revenue[(region, product)] += cents
    per_group: dict[str, list[tuple[str, int]]] = defaultdict(list)
    for (region, product), total in revenue.items():  # 2. regroup by the partition key
        per_group[region].append((product, total))
    return {
        region: sorted(items, key=lambda it: (-it[1], it[0]))[:n]  # 3. full sort key, then cut
        for region, items in sorted(per_group.items())
    }




if __name__ == "__main__":
    rows = [("EU", "pen", 300), ("EU", "ink", 500), ("EU", "cap", 500), ("EU", "pen", 300),
            ("US", "ink", 1200), ("US", "pad", 100)]
    top = top_n_per_group(rows, 2)
    assert top["EU"] == [("pen", 600), ("cap", 500)]  # cap beats ink on the name tie-break
    assert top["US"] == [("ink", 1200), ("pad", 100)]
    assert top_n_per_group(rows, 0) == {"EU": [], "US": []}
    print("ok")

The same in SQL

Section titled “The same in SQL”
-- Totals per region, only regions with more than 2 sales.
SELECT region, COUNT(*) AS n, SUM(amount) AS total, MAX(amount) AS biggest
FROM sales
WHERE amount > 0              -- filters rows, before grouping
GROUP BY region
HAVING COUNT(*) > 2           -- filters groups, after aggregating
ORDER BY total DESC, region;  -- explicit order, including the tie-break
-- Top 2 products by revenue in each region.
WITH revenue AS (
  SELECT region, product, SUM(amount) AS total
  FROM sales
  GROUP BY region, product
),
ranked AS (
  SELECT region, product, total,
         ROW_NUMBER() OVER (PARTITION BY region ORDER BY total DESC, product) AS rn
  FROM revenue
)
SELECT region, product, total
FROM ranked
WHERE rn <= 2                 -- window results can't be filtered in the same SELECT's WHERE
ORDER BY region, rn;

Swap ROW_NUMBER for RANK if tied rows should all be kept (“top 2, including ties”), or DENSE_RANK for “the top 2 distinct values”.

-- Running total per region and change from the previous sale.
SELECT region, sold_at, amount,
       SUM(amount) OVER (PARTITION BY region ORDER BY sold_at
                         ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running,
       amount - LAG(amount) OVER (PARTITION BY region ORDER BY sold_at) AS delta
FROM sales;

What it costs

Section titled “What it costs”
Step Time Space Why
Group + fold (hash map) O(n) average O(g) One O(1) update per row; g = number of distinct keys.
Group by sorting first O(n log n) O(1) to O(n) Sort, then scan runs of equal keys. Useful when data doesn’t fit a map, or is already sorted.
Order the groups O(g log g) O(g) Sort the summaries, not the raw rows.
Top N of g with a heap O(g log N) O(N) Keep the N best; Python heapq.nlargest(n, items, key=...).
Top N per group, p partitions O(Σ gᵢ log gᵢ) ≤ O(g log g) O(g) Sort inside each partition independently.
Recompute on every query vs maintain O(n) per query vs O(1) per write O(g) Keep running accumulators when reads are frequent.

Decomposable aggregates (sum, count, min, max) also let you split work: aggregate each shard, then combine the partial results. That’s how databases parallelize GROUP BY and how MapReduce combiners work. AVG and MEDIAN need care: carry (sum, count) for the average; a median needs the values (or a sketch).

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Multi-level keys. (merchant, day) or nested maps merchant → day → total. Tuples are simpler; nested maps make “everything for one merchant” cheap.
  • Include empty groups. “Every account, with 0 if no activity” means you seed the map with all known keys first. SQL: LEFT JOIN from the dimension table plus COALESCE(SUM(x), 0).
  • Distinct counts. COUNT(DISTINCT customer): a set per bucket, or HyperLogLog at scale.
  • Gaps and islands. Group consecutive rows with the same state: ROW_NUMBER() OVER (ORDER BY ts) - ROW_NUMBER() OVER (PARTITION BY state ORDER BY ts) is constant within each island: the classic SQL trick.
  • Sessionization. A new group starts when the gap since the previous event exceeds a threshold: LAG + running SUM of “is new session” flags.
  • Rollups. GROUP BY ROLLUP(region, product) adds subtotal rows.

Pitfalls

Section titled “Pitfalls”
  • No explicit order. Neither SQL nor C# Dictionary promises one. Always sort the output, with a tie-break.
  • WHERE vs HAVING. Filtering on an aggregate in WHERE is an error. Row filters belong in WHERE, so rows are dropped before the grouping work, not after.
  • Average of averages. The mean of per-day averages isn’t the overall average unless days have equal counts. Carry sums and counts.
  • Integer division. SUM(cents) / COUNT(*) truncates in SQL on integers and in C# on long. Decide the rounding (see money).
  • NULLs. COUNT(col) skips NULLs, COUNT(*) doesn’t. SUM of no rows is NULL, not 0.
  • itertools.groupby on unsorted input produces repeated groups.
  • Locale-sensitive string sorts. localeCompare and culture-aware CompareTo order "a" and "B" differently from code-point order. Use ordinal comparison when the spec says “codepoint order”.
  • Ranking with ROW_NUMBER when ties should be kept. Pick the ranking function on purpose.

In the interview

Section titled “In the interview”
  • Ask: what exactly is the key? What’s the tie-break? Are groups with nothing included? Is n larger than the number of groups? Can amounts be zero or negative?
  • Ask whether the report is computed once or queried after every update. That decides recompute vs maintain.
  • Say out loud: “One pass into a map of accumulators, O(n). Then sort the g summaries by (-total, name), O(g log g). I won’t rely on map order.”
  • For SQL rounds: name the grain first (“one row per region per product”), then the window: PARTITION BY what, ORDER BY what, which ranking function, and why.
  • Expect follow-ups: top N over a sliding time window, incremental updates, sharded data (combine partial aggregates), percentile instead of average.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
Two reps are tied for first place in a region. You want both returned when asking for 'the top 1 per region'. Which ranking function?
Check yourself
pick one
Day 1 has 1 sale of 100. Day 2 has 3 sales of 10. What is the overall average sale, and what is the average of daily averages?
Check yourself
pick one
You use Python's itertools.groupby(rows, key=region) on rows in arrival order: EU, US, EU. How many groups come out?

Practice on your own

Section titled “Practice on your own”

Classic exercises, not gym questions:

  • Word frequencies in a text, top 10 with alphabetical tie-break.
  • Second-highest salary per department (SQL, with ties handled two ways).
  • Monthly active users from a login log: distinct users per calendar month.
  • Longest streak of consecutive days with a sale per store (gaps and islands).

Go deeper

Section titled “Go deeper”
Section titled “Related”
Hash mapsThe bucket store behind every group-by.
HeapsTop N without sorting everything.
CountingFrequency maps, the simplest aggregate.
SortingStable sorts and composite keys.