FastPrepQuery JSON Records with WHERE and ORDER BY

Query JSON Records with WHERE and ORDER BY

GitHub logoGitHub● MediumFULLTIMEONSITE INTERVIEW

Problem statement

A JSON dictionary has been flattened into one table. fields[i] is the name of column i and types[i] is its type, "int" or "string". Each record in records lists its values as text, in field order.

Run one query and return the matching records. A query has this form, with single spaces between parts:

SELECT <select list> [WHERE <condition> [AND <condition>]...] [ORDER BY <key>[, <key>]...]
  • The select list is * for every field in field order, or field names separated by , (a comma and a space).
  • A condition is field op literal, where op is one of =, !=, <, <=, >, >=. For an int field the literal is an integer, such as -3; for a string field it is text in single quotes, such as 'new york'. A record matches only if every condition holds.
  • A key is a field name, optionally followed by ASC or DESC; ASC is the default. Records are sorted by the first key, ties by the second key, and so on. Records that tie on every key, or all records when there is no ORDER BY, keep their input order.

Int fields compare as numbers. String fields compare character by character by character code, so a shorter string that is a prefix of a longer one comes first.

Return one row per matching record, holding the selected fields' values in select-list order, exactly as they appear in records.

Function

runQuery(fields: String[], types: String[], records: String[][], query: String) → String[][]

Examples

Example 1

fields = ["id","name","age","city"]types = ["int","string","int","string"]records = [["1","ana","34","nyc"],["2","ben","27","sf"],["3","cy","34","sf"],["4","dee","41","nyc"],["5","eli","27","la"]]query = "SELECT name, age WHERE age >= 30 ORDER BY age DESC"return = [["dee","41"],["ana","34"],["cy","34"]]

Three records have age of at least 30: ana (34), cy (34), and dee (41). Sorting by age from high to low puts dee first. ana and cy tie at 34, so they keep their input order.

Example 2

fields = ["id","name","age","city"]types = ["int","string","int","string"]records = [["1","ana","34","nyc"],["2","ben","27","sf"],["3","cy","34","sf"],["4","dee","41","nyc"],["5","eli","27","la"]]query = "SELECT * WHERE city = 'sf' AND id != 3"return = [["2","ben","27","sf"]]

Only ben and cy live in sf, and the second condition removes cy, whose id is 3. With no ORDER BY, the result keeps input order, and * returns every field in field order.

Example 3

fields = ["id","name","age","city"]types = ["int","string","int","string"]records = [["1","ana","34","nyc"],["2","ben","27","sf"],["3","cy","34","sf"],["4","dee","41","nyc"],["5","eli","27","la"]]query = "SELECT city, name ORDER BY city, age DESC"return = [["la","eli"],["nyc","dee"],["nyc","ana"],["sf","cy"],["sf","ben"]]

There is no WHERE, so all five records match. Cities sort as text: la, then nyc, then sf. Inside nyc, dee (41) comes before ana (34); inside sf, cy (34) comes before ben (27). Fields come out in the order the query lists them.

Constraints

  • 1 <= fields.length <= 6
  • types.length == fields.length
  • 1 <= fields[i].length <= 10
  • 0 <= records.length <= 200
  • 1 <= query.length <= 300
  • Field names use lowercase letters, digits, and _, do not start with a digit, and are distinct. Each types[i] is "int" or "string".
  • Every record has exactly fields.length values. An int value is a decimal integer from -10^9 to 10^9 with no leading zeros; a string value has at most 12 characters, each a lowercase letter, a digit, or a space.
  • query follows the grammar above, names only existing fields, repeats no field in the select list or in ORDER BY, and each literal has its field's type and follows the value rules.
See GitHub hiring insights
Saved
public String[][] runQuery(String[] fields, String[] types, String[][] records, String query) {
    // Write your code here.
}
Checking account…