Design SQL
Asked at OpenAI
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.
Asked At
| 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: [[...], ...]}.
Visual walkthrough: createTable("users", ["id", "name", "age"])
-> tables["users"] = {columns: ["id", "name", "age"], rows: []}
insertRow("users", [1, "Alice", 30])
-> tables["users"].rows = [[1, "Alice", 30]]
select("users", ["name"], 1)
-> column index for "name" is 1. Return rows where column 0 == 1. Result: [["Alice"]].
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).
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.