Range + Category Lookup Store

If you sit a Susquehanna software round, expect one problem in some costume. It is a store of records, each carrying a category and a year, that has to answer two questions fast. Give me everything in a category. Give me everything whose year falls in a range. It shows up as a "movie database" in the onsite and as a CSV of movies to speed up in the phone screen. In finance clothes, it becomes an instrument store keyed by sector and maturity. Same problem every time.

It looks harder than it is. The word "range" makes strong candidates reach for a segment tree or a balanced BST, and then they burn the round building one. The interviewer is watching for the opposite instinct: index the data up front so each query touches only the records it needs, never the whole collection. The tool is a hashmap, sometimes two. This lesson builds the store the way SIG wants it built, then handles the phone-screen twist where you are handed a slow version and told to make it fast.

How SIG frames it

The classic statement is almost verbatim across candidate reports. You are given a list of movies, each an object with a name, a genre, and a year. Write a class that returns all movies in a given genre in O(1), and all movies between two years, say 2011 to 2014, also in O(1). Candidates who have seen range queries before immediately think segment tree, and every report ends the same way: the interviewer says it is simpler than that and points at a hashmap.

Take the "O(1)" as shorthand, not a literal bound. What the interviewer means is do not scan all N records on every query. A category lookup genuinely is O(1): store one list per category and hand back the list. A year range cannot be truly O(1) for an arbitrary span, but it can be made independent of N. Years live in a tiny, bounded domain (a few decades of releases, a fixed set of maturities). Bucketing by year and walking only the requested span costs on the order of the span plus the results returned. The number of records held never enters the cost. That distinction, cost tied to the answer rather than to the whole store, is the signal they are grading.

The two indexes to build

Everything in this problem comes down to building two dictionaries as the records load, and then answering each query straight out of them. One maps a category to the records in it. One maps a single year to the records from that year. Nothing more exotic is needed.

by_category = {}      # category -> [record, ...]
by_year = {}          # single year -> [record, ...]
for name, category, year in records:
    by_category.setdefault(category, []).append(name)   # O(1) insert
    by_year.setdefault(year, []).append(name)           # O(1) insert
# category query: hand back the list, O(1)
by_category.get("Action", [])
# year-range query: touch only the years in the span, not all N records
[name for y in range(low, high + 1) for name in by_year.get(y, [])]

The category query is a single dictionary read. The range query walks the years from low to high and concatenates each year's bucket, so its cost is the width of the span plus the number of names it returns. Release years span a few decades, so that width is a small constant in practice. A store with a million records answers a five-year range in the same handful of steps as a store with a thousand. That is the whole trick, and it is why the interviewer keeps steering you back to the hashmap.

Asked at Susquehanna

Build the store first, exactly as the onsite asks it. Then do the phone-screen version, where the queries combine a category and a year range and the starting code is a naive scan you have to speed up. Get both automatic and you have covered the way this problem gets asked.

1

Range + Category Lookup Store: Two Hashmaps

MediumSignature problem

Problem

You are given a list of records. Each record is [name, category, year]. Build a class that answers two kinds of query as fast as possible:

- by_category(category) returns the names of all records in that category.
- by_year_range(low_year, high_year) returns the names of all records whose year is between low_year and high_year, inclusive of both ends.

Neither query may scan the full list of records. A category lookup should be O(1); a range lookup should cost on the order of the span of years plus the number of names it returns, independent of how many records the store holds.

Return the category query's names in the order the records were inserted. Return the range query's names in ascending year order, and within a single year in insertion order.

Input: store built from 8 movies; by_category("Action"), then by_year_range(2011, 2014)

Output: ["Drive","John Wick","Baby Driver"], then ["Drive","Bridesmaids","Whiplash","John Wick"]

The category read returns the Action list directly. The range read walks years 2011..2014: 2011 holds Drive then Bridesmaids, 2014 holds Whiplash then John Wick.

How this uses the pattern

Build two dictionaries as the records load: category -> names and year -> names. Answer a category query with one dictionary read, and a range query by walking only the years in the span.

Range + Category Lookup Store: Two Hashmaps

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["RangeLookupStore", [[["Michael Clayton", "Drama", 2007], ["Superbad", "Comedy", 2007], ["Drive", "Action", 2011], ["Bridesmaids", "Comedy", 2011], ["Whiplash", "Drama", 2014], ["John Wick", "Action", 2014], ["La La Land", "Drama", 2016], ["Baby Driver", "Action", 2017]]]], ["by_category", ["Action"]], ["by_category", ["Comedy"]], ["by_year_range", [2011, 2014]], ["by_year_range", [2016, 2020]], ["by_category", ["Horror"]], ["by_year_range", [1990, 2000]]]Expected: [null, ["Drive", "John Wick", "Baby Driver"], ["Superbad", "Bridesmaids"], ["Drive", "Bridesmaids", "Whiplash", "John Wick"], ["La La Land", "Baby Driver"], [], []]

Input: [["RangeLookupStore", [[["Alpha", "Action", 2010], ["Bravo", "Action", 2010], ["Cielo", "Drama", 2012]]]], ["by_year_range", [2010, 2010]], ["by_category", ["Action"]], ["by_year_range", [2010, 2012]]]Expected: [null, ["Alpha", "Bravo"], ["Alpha", "Bravo"], ["Alpha", "Bravo", "Cielo"]]

Input: [["RangeLookupStore", [[["Solo", "Action", 2005]]]], ["by_category", ["Action"]], ["by_year_range", [2005, 2005]], ["by_year_range", [2006, 2010]]]Expected: [null, ["Solo"], ["Solo"], []]

Need a hint? (3 available)

The Susquehanna angle

This is the single most-reported Susquehanna software problem, and the interviewer is specifically watching whether you overbuild. Candidates reach for segment trees or sorted arrays with binary search; the wanted answer is two hashmaps built once at load time. The "O(1)" in the prompt is a hint to index, not a literal bound on the range query. Say out loud that a range over a bounded year domain costs the span plus the results and stays independent of N, and you have given the signal they grade.

Take it further

The common next step is a count instead of a list: how many records fall in a year range, answered in true O(1)? A prefix-sum array over the year axis does it, turning any range count into a single subtraction. It is worked through in the solution below.

Show solution & walkthrough

2

Category + Year Range at Scale: Index Once, Binary-Search Each Query

MediumFrequently asked

Problem

This is the phone-screen version. You are handed working but slow code: a list of records, each [name, category, year], and a batch of queries, each [category, low_year, high_year]. The starting search loops over every record for every query, checking the category and the year window. With many records and many queries that is O(Q x N), and you are asked to make it fast.

For each query, return the names of the records that match the category and fall in the inclusive year range. Return them in ascending year order, and within a year in the order the records were given.

Return one list of names per query, in the same order as the queries.

Input: 6 records; query ["Action", 2011, 2015]

Output: ["Drive","John Wick"]

Of the Action records (2011, 2014, 2017), only 2011 and 2014 fall in [2011, 2015]. Baby Driver at 2017 is outside the window.

How this uses the pattern

Build the category index once, but store each category's records sorted by year. Then a query is a binary search for the year window inside that one category's list, not a scan of everything.

Category + Year Range at Scale: Index Once, Binary-Search Each Query

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[["Drive", "Action", 2011], ["John Wick", "Action", 2014], ["Baby Driver", "Action", 2017], ["Superbad", "Comedy", 2007], ["Bridesmaids", "Comedy", 2011], ["Whiplash", "Drama", 2014]], [["Action", 2011, 2015], ["Comedy", 2010, 2025], ["Drama", 2000, 2010], ["Action", 2017, 2017], ["Sci-Fi", 2000, 2020]]]Expected: [["Drive", "John Wick"], ["Bridesmaids"], [], ["Baby Driver"], []]

Input: [[["Zed", "Tech", 2000], ["Ann", "Tech", 2000], ["Moe", "Tech", 2001]], [["Tech", 2000, 2000], ["Tech", 2000, 2001], ["Tech", 2002, 2005]]]Expected: [["Zed", "Ann"], ["Zed", "Ann", "Moe"], []]

Need a hint? (3 available)

The Susquehanna angle

SIG's technical round is often an "optimize this" round rather than a blank page, and this is that round distilled. The naive code rescans all records per query; the graded answer is to build an index once and let every query ride it. Candidates often report an extra turn after that: the combined filter, with category and range together at batch scale. Sorting each category's list by year once lets you binary-search the window, so a query costs the log of the category's size plus the matches, never the whole store.

Take it further

A natural push, and a fast one to answer, is to return only the count of matches per query rather than the names. The same sorted lists give it: two binary searches bound the window and their difference is the count, so you skip building the result slice entirely. It is worked through below.

Show solution & walkthrough