2408. Design SQL
Asked at OpenAI
Difficulty
Medium
Time
O(1) for ins and rmv, O(k) for s
Space
O(total stored cells)
Pattern
Array
Companies
1
Problem
You must build a small in-memory database that behaves like a simplified SQL engine. The constructor receives two arrays of the same length: names and columns. For each index i, you create a table called names[i] that has exactly columns[i] columns. Table names are unique.
Your class must support four operations. ins(name, row) adds a row to that table and returns true. Each row gets an auto-increment id: the first inserted row gets id 1, and every later row gets an id one bigger than the previous row's id — even if that previous row was deleted. If name is not a known table, or row.length does not equal the table's column count, do nothing and return false. rmv(name, rowId) deletes the row with that id; if the table or the row does not exist, nothing happens. sel(name, rowId, columnId) returns the value in that cell, or the string "<null>" if the table or the cell is invalid. exp(name) returns all remaining rows as strings, each cell (including the id) joined by commas, in increasing id order; an unknown table gives an empty array.
Note that column ids in sel are 1-based, and that deleting a row must never change the id counter. The follow-up asks how you would store data if many deletions make a table sparse — a hash map keyed by row id avoids keeping empty slots, while a list keeps export simple but wastes space.
Tables, rows and auto-increment ids
Constraints
- ●
n == names.length == columns.length - ●
1 <= n <= 10^4 - ●
1 <= names[i].length, row[i].length, name.length <= 10 - ●
names[i], row[i], and name consist only of lowercase English letters - ●
1 <= columns[i] <= 10 - ●
1 <= row.length <= 10 - ●
All names[i] are distinct - ●
At most 2000 calls will be made to ins and rmv
Examples
["SQL","ins","sel","ins","exp","rmv","sel","exp"]
[[["one","two","three"],[2,3,1]],["two",["first","second","third"]],["two",1,3],["two",["fourth","fifth","sixth"]],["two"],["two",1],["two",2,2],["two[null,true,"third",true,["1,first,second,third","2,fourth,fifth,sixth"],null,"fifth",["2,fourth,fifth,sixth"]]["SQL","ins","sel","rmv","sel","ins","ins"]
[[["one","two","three"],[2,3,1]],["two",["first","second","third"]],["two",1,3],["two",1],["two",1,2],["two",["fourth","fifth"]],["two",["fourth","fifth","s[null,true,"third",null,"<null>",false,true]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
Core data structure: use a hash map of tables. Each table maps to an ordered list of column names and a list of rows. Each row is a list of values. tables["name"] = {columns: [...], rows: [[...], ...]}.
Parsing the select query: the format is select(table, columns, rowId). Look up the column indices from the column names list. Filter rows where the first column (id) equals rowId. Return the requested columns.
Insert is straightforward: push a new row to the table's row list. Create just initializes the table structure. Select needs to map column names to indices and extract values.
Edge cases: inserting into a non-existent table (the problem guarantees it exists), selecting columns that don't exist (also guaranteed to exist), selecting with no matching rowId (return empty list).
Optimal Approach
Step 1: Maintain a hash map tables mapping table name to {columns: List[str], rows: List[List[int]]}.
Step 2: createTable(name, columns) -> store {columns: columns, rows: []} in tables[name].
Step 3: insertRow(name, values) -> append values to tables[name].rows.
Step 4: select(table, columns, rowId) -> find column indices for the requested columns. Filter rows where rows[i][0] == rowId. For each matching row, extract the requested columns.
Walkthrough: createTable("t", ["id", "val"]) -> tables["t"] = {columns: ["id", "val"], rows: []}
insertRow("t", [1, 10]) -> tables["t"].rows = [[1, 10]]
insertRow("t", [2, 20]) -> tables["t"].rows = [[1, 10], [2, 20]]
select("t", ["val"], 2) -> id is column 0. Find row where row[0]==2 -> [2, 20]. Extract column 1 -> [20]. Result: [[20]].
Time: createTable O(1), insertRow O(1), select O(n) where n is rows in table. Space: O(total rows across all tables).
Hash map of tables, each with a row map
What Trips People Up in Real Interviews
Not mapping column names to indices during select. If a table has columns ["id", "name", "age"] and you want ["name"], you need to know that "name" is at index 1. Store the column-name-to-index mapping for O(1) lookup.
Confusing rowId with array index. The rowId is the value in the first column (the id column), not the index in the rows array. If ids are [1, 5, 3], selecting rowId=5 means finding the row where column 0 is 5, not array index 5.
Not maintaining column order. When returning results from select, the columns should appear in the same order as the input columns parameter, not the table's column order.
Forgetting that each table has its own column schema. Two tables can have different columns. Don't assume all tables share the same structure.
Not handling the case where select returns no rows. Return an empty list, not null or an error. The problem expects an empty result set.
Solution Code
O(1) for ins and rmv, O(k) for s timeclass SQL:
def __init__(self):
self.tables = {}
def createTable(self, name: str, columns: list[str]) -> None:
self.tables[name] = {"columns": columns, "rows": []}
def insertRow(self, name: str, values: list[int]) -> None:
self.tables[name]["rows"].append(values)
def select(self, table: str, columns: list[str], rowId: int) -> list[list[int]]:
t = self.tables[table]
col_indices = [t["columns"].index(c) for c in columns]
result = []
for row in t["rows"]:
if row[0] == rowId:
result.append([row[i] for i in col_indices])
return resultFrequently Asked Questions
What is the Design SQL problem?
Design a SQL-like database that supports three operations: createTable, insertRow, and select. The database stores rows in tables with named columns. This is a design problem that tests your ability to implement data structures and parse simple queries.
How do you solve Design SQL?
The optimal approach runs in O(1) for ins and rmv, O(k) for s time and O(total stored cells) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design SQL?
Design SQL is asked at OpenAI. It is a medium difficulty problem.
What are common mistakes on Design SQL?
- Not mapping column names to indices during select. If a table has columns ["id", "name", "age"] and you want ["name"], you need to know that "name" is at index 1. Store the column-name-to-index mapping for `O(1)` lookup.
- Confusing rowId with array index. The rowId is the value in the first column (the id column), not the index in the rows array. If ids are [1, 5, 3], selecting rowId=5 means finding the row where column 0 is 5, not array index 5.
- Not maintaining column order. When returning results from select, the columns should appear in the same order as the input `columns` parameter, not the table's column order.
- Forgetting that each table has its own column schema. Two tables can have different columns. Don't assume all tables share the same structure.
- Not handling the case where select returns no rows. Return an empty list, not null or an error. The problem expects an empty result set.