Implement an in-memory SQL-like table
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
Implement a simple in-memory database for **one table**. All values are **strings**.
Each row is identified by a `rowKey` (string). Each row contains **columns** identified by `colKey` (string).
You must process a sequence of commands and output results for read/query commands.
### Supported commands
1. `SET rowKey colKey value`
- Set `table[rowKey][colKey] = value`.
2. `GET rowKey colKey`
- Output the value if present, otherwise output `NULL`.
3. `SELECT whereCol whereValue orderByCol`
- Return **all rowKeys** for rows where `table[rowKey][whereCol] == whereValue`.
- Sort the matching rows by the value of `orderByCol` in **ascending lexicographic order**.
- If a row is missing `orderByCol`, treat its sort value as an empty string `""`.
- If multiple rows have the same `orderByCol` value, break ties by `rowKey` ascending.
- Output the resulting `rowKey`s joined by a single space (or output an empty line if none).
### Input/Output format
- Input: list of commands (one per line).
- Output:
- For each `GET`, print a single line.
- For each `SELECT`, print a single line.
### Constraints (assume)
- Up to \(2 \times 10^5\) commands.
- Total length of all strings is within reasonable memory limits.
Quick Answer: This question evaluates implementation skills for an in-memory SQL-like table, focusing on data modeling with nested key-value structures, string handling, efficient lookups, and lexicographic sorting with tie-breaking.
Implement a simple in-memory database for one table. All stored values are strings.
Each row is identified by a string rowKey, and each row contains columns identified by string colKey values.
You must process a list of commands and return the outputs produced by read/query commands.
Supported commands:
1. SET rowKey colKey value
- Set table[rowKey][colKey] = value.
- If that cell already exists, overwrite its old value.
2. GET rowKey colKey
- Output the value if present, otherwise output NULL.
3. SELECT whereCol whereValue orderByCol
- Find all rows where table[rowKey][whereCol] == whereValue.
- Sort the matching rowKeys by the value of orderByCol in ascending lexicographic order.
- If a row does not have orderByCol, treat its sort value as the empty string "".
- If multiple rows have the same sort value, break ties by rowKey ascending.
- Output the matching rowKeys joined by a single space.
- If no rows match, output an empty string.
For this function-based version, return a list of output strings, one for each GET or SELECT command, in order.
Constraints
- 0 <= len(commands) <= 2 * 10^5
- rowKey, colKey, whereCol, whereValue, orderByCol, and value are strings without spaces
- All comparisons and sorting are lexicographic string operations
- A SET command overwrites the previous value of the same cell, if any
Examples
Input: ["SET r1 name bob", "SET r1 age 2", "SET r2 name bob", "SET r2 age 10", "GET r1 name", "SELECT name bob age"]
Expected Output: ["bob", "r2 r1"]
Explanation: GET returns the stored value "bob". For SELECT, both rows match name=bob, and they are sorted by age as strings: "10" comes before "2" lexicographically, so r2 appears before r1.
Input: ["GET missing name", "SELECT status active score"]
Expected Output: ["NULL", ""]
Explanation: The table is empty. GET returns NULL, and SELECT has no matching rows so it returns an empty string.
Hints
- Use a nested dictionary for the actual table: rowKey -> {colKey: value}.
- To avoid scanning every row for SELECT, keep an index from (colKey, value) to the set of rowKeys that currently match that exact value.