Build an In-Memory Query Engine over JSON Tables with WHERE and ORDER BY

Implement query functionality similar to a relational database over data given as a JSON dictionary. The report says only that the data is a JSON dictionary and that the follow-ups asked how to support WHERE, ORDER BY and similar clauses, so confirm the data shape and the query interface with the interviewer before coding. A natural starting assumption, used below: the dictionary maps each table name to a list of rows, and each row maps column names to scalar values (string, number, boolean or null). ```json { "users": [ {"id": 1, "name": "Ana", "age": 31, "city": "Lisbon"}, {"id": 2, "name": "Ben", "age": 25, "city": "Austin"}, {"id": 3, "name": "Chen", "age": 31, "city": "Austin"}, {"id": 4, "name": "Dee", "age": null, "city": "Lisbon"} ] } ``` ### Clarifying Questions - Is the data shaped as tables of row objects, as above, or in another way, such as a dictionary keyed by row id? - Should queries be expressed as method calls or a structured object, or as SQL-like strings that you parse? - What should happen when a row lacks a column, or when a selected column exists in no row of the table? - Are values limited to scalars, or can they be nested objects and arrays? - Should results be new row dictionaries, or references to the stored rows? ### Part 1 — Select columns from a table Implement a query that returns chosen columns, or all columns, for every row of a named table, with a clear error for an unknown table. ```hint Shape for growth Before writing the first query, think about how filtering and sorting will plug into it later without a rewrite. ``` #### What This Part Should Cover - A small, extensible interface, such as an engine object and a query object - Projection that copies rows rather than exposing the stored data - Defined behavior for unknown tables and missing columns ### Part 2 — Support WHERE Extend the query so that it returns only the rows matching a condition built from comparisons (`=`, `!=`, `<`, `<=`, `>`, `>=`) between a column and a value, combined with AND and OR, for example `city = 'Austin' OR age > 30`. ```hint Evaluate one row at a time Think about how a condition such as `a OR (b AND c)` could be checked against a single row, and how the same structure could later come from a parsed string. ``` #### Clarifying Questions for this Part - How should a comparison treat a null or missing value, and a value of a different type from the literal? - Is NOT needed? #### What This Part Should Cover - A condition representation that composes AND and OR to any depth and that a parser could produce - SQL-like handling of null and missing values and of type mismatches - Filtering on columns that are not selected ### Part 3 — Support ORDER BY Extend the query to sort its result by one or more columns, each ascending or descending, for example by `age` descending and then by `name` ascending. ```hint Several keys, several directions Consider how to sort by one key descending and another ascending when one of the keys is a string, which cannot be negated. ``` #### What This Part Should Cover - Multi-key sorting with a direction per key and a deterministic order for ties - Where nulls go, and how mixed types in a sort column are handled - The logical order of filtering, sorting and projection, including sorting by a column that is not selected ### What a Strong Answer Covers - A clean design that grows from projection to filtering to sorting without rewrites - Semantics for nulls, missing columns, types and ties, stated up front and implemented consistently - The complexity of each stage, and where indexes would help - Tests for each clause and their combinations, including the edge cases above ### Follow-up Questions - How would you add LIMIT and OFFSET, and how could LIMIT avoid sorting the whole table? - How would you add GROUP BY with COUNT, SUM and AVG? - How would you join two tables on a column, and what makes that faster than comparing every pair of rows? - An equality filter on one column runs on every request against a large table. How would an index help, and what does it cost on writes?