How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement an in-memory SQL-like table | OpenAI Coding Question

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.

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

Loading coding console...

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.

Input: ["SET r1 city seattle", "SET r2 city seattle", "SET r2 score 9", "SELECT city seattle score", "SET r1 score 10", "SET r2 city boston", "SELECT city seattle score", "GET r2 city"]

Expected Output: ["r1 r2", "r1", "boston"]

Explanation: In the first SELECT, both rows match city=seattle. r1 is missing score, so its sort value is "", which comes before "9". After updating r2.city to boston, only r1 still matches city=seattle. The final GET returns boston.

Input: ["SET b role dev", "SET a role dev", "SET b rank mid", "SET a rank mid", "SELECT role dev rank"]

Expected Output: ["a b"]

Explanation: Both rows match role=dev and both have the same rank value "mid", so the tie is broken by rowKey ascending: a before b.

Input: ["SET r1 color red", "SET r1 color blue", "GET r1 color", "SELECT color red color", "SELECT color blue color"]

Expected Output: ["blue", "", "r1"]

Explanation: The second SET overwrites the old value red with blue. GET returns blue, SELECT for red finds no rows, and SELECT for blue returns r1.

Input: []

Expected Output: []

Explanation: With no commands, there are no outputs.

Solution

def solution(commands):
    table = {}
    index = {}
    outputs = []

    for command in commands:
        parts = command.split()
        op = parts[0]

        if op == "SET":
            row_key, col_key, value = parts[1], parts[2], parts[3]
            row = table.setdefault(row_key, {})

            if col_key in row:
                old_value = row[col_key]
                if old_value != value:
                    bucket = index[(col_key, old_value)]
                    bucket.remove(row_key)
                    if not bucket:
                        del index[(col_key, old_value)]

                    row[col_key] = value
                    index.setdefault((col_key, value), set()).add(row_key)
            else:
                row[col_key] = value
                index.setdefault((col_key, value), set()).add(row_key)

        elif op == "GET":
            row_key, col_key = parts[1], parts[2]
            value = table.get(row_key, {}).get(col_key)
            outputs.append(value if value is not None else "NULL")

        elif op == "SELECT":
            where_col, where_value, order_by_col = parts[1], parts[2], parts[3]
            matches = index.get((where_col, where_value))

            if not matches:
                outputs.append("")
            else:
                ordered_rows = sorted(
                    matches,
                    key=lambda row_key: (table[row_key].get(order_by_col, ""), row_key)
                )
                outputs.append(" ".join(ordered_rows))

    return outputs

Time complexity: SET/GET: O(1) average time. SELECT: O(k log k), where k is the number of rows matching (whereCol, whereValue).. Space complexity: O(c), where c is the number of currently stored cells, counting both the table storage and the exact-match index..

Quick Overview

Implement an in-memory SQL-like table

Constraints

Examples

Solution

Hints