Quick Overview

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 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.

Overview: 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.

Read the full OpenAI Software Engineer interview experience this question came from

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

  1. Use a nested dictionary for the actual table: rowKey -> {colKey: value}.
  2. To avoid scanning every row for SELECT, keep an index from (colKey, value) to the set of rowKeys that currently match that exact value.

Loading coding console...

Show the approach

Approach

The solution maintains two dictionaries that stay in sync as commands run.

Storage — table maps rowKey -> {colKey -> value}, the literal table. This alone answers GET directly: table.get(row_key, {}).get(col_key), returning "NULL" when the cell is absent.

Secondary index — index maps (colKey, value) -> set of rowKeys, i.e. an inverted index of every cell's value. This is the key idea: it lets SELECT whereCol whereValue ... find all matching rows in O(1) via index.get((where_col, where_value)), instead of scanning the whole table.

Keeping the index consistent on SET:

  • New cell (col_key not in row): write the value and add row_key to the (col_key, value) bucket.
  • Overwrite with the same value: do nothing — index is already correct.
  • Overwrite with a different value: pull row_key out of the old (col_key, old_value) bucket (and del the bucket if it becomes empty, so it never reports stale matches), then add it to the new bucket. This is why test 3/5 correctly stop matching a row after its filter column changes.

SELECT ordering — the matched rowKeys are sorted with key (table[row_key].get(order_by_col, ""), row_key). Missing orderByCol defaults to "", and ties on the sort value fall back to rowKey — exactly the spec's tie-break. Results are space-joined; an empty/None match set yields "".

It's correct because the index is mutated on every value change, so it always reflects current cell values, and Python's sorted is stable with an explicit secondary key for deterministic ordering.

Space complexity:
O(c), where c is the number of currently stored cells. Both `table` and the inverted `index` hold one entry per live cell; empty index buckets are deleted, so no stale memory accumulates. The `outputs` list adds O(q) for q read/query commands.