Design SQL solution and explanation
The problem
You are given two string arrays, names and columns, both of size n. The ith table is represented by the name names[i] and contains columns[i] number of columns.
You need to implement a class that supports the following operations:
- Insert a row in a specific table with an id assigned using an auto-increment method, where the id of the first inserted row is 1, and the id of each new row inserted into the same table is one greater than the id of the last inserted row, even if the last row was removed.
- Remove a row from a specific table. Removing a row does not affect the id of the next inserted row.
- Select a specific cell from any table and return its value.
- Export all rows from any table in csv format.
Implement the SQL class:
SQL(String[] names, int[] columns)- Creates the
ntables.
- Creates the
bool ins(String name, String[] row)- Inserts
rowinto the tablenameand returnstrue. - If
row.lengthdoes not match the expected number of columns, ornameis not a valid table, returnsfalsewithout any insertion.
- Inserts
void rmv(String name, int rowId)- Removes the row
rowIdfrom the tablename. - If
nameis not a valid table or there is no row with idrowId, no removal is performed.
- Removes the row
String sel(String name, int rowId, int columnId)- Returns the value of the cell at the specified
rowIdandcolumnIdin the tablename. - If
nameis not a valid table, or the cell(rowId, columnId)is invalid, returns"<null>".
- Returns the value of the cell at the specified
String[] exp(String name)- Returns the rows present in the table
name. - If name is not a valid table, returns an empty array. Each row is represented as a string, with each cell value (including the row's id) separated by a
",".
- Returns the rows present in the table
Example 1:
Input:
["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"]]
Output:
[null,true,"third",true,["1,first,second,third","2,fourth,fifth,sixth"],null,"fifth",["2,fourth,fifth,sixth"]]
Explanation:
// Creates three tables.
SQL sql = new SQL(["one", "two", "three"], [2, 3, 1]);
// Adds a row to the table "two" with id 1. Returns True.
sql.ins("two", ["first", "second", "third"]);
// Returns the value "third" from the third column
// in the row with id 1 of the table "two".
sql.sel("two", 1, 3);
// Adds another row to the table "two" with id 2. Returns True.
sql.ins("two", ["fourth", "fifth", "sixth"]);
// Exports the rows of the table "two".
// Currently, the table has 2 rows with ids 1 and 2.
sql.exp("two");
// Removes the first row of the table "two". Note that the second row
// will still have the id 2.
sql.rmv("two", 1);
// Returns the value "fifth" from the second column
// in the row with id 2 of the table "two".
sql.sel("two", 2, 2);
// Exports the rows of the table "two".
// Currently, the table has 1 row with id 2.
sql.exp("two");
Example 2:
Input:
["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","sixth"]]]
Output:
[null,true,"third",null,"<null>",false,true]
Explanation:
// Creates three tables.
SQL sQL = new SQL(["one", "two", "three"], [2, 3, 1]);
// Adds a row to the table "two" with id 1. Returns True.
sQL.ins("two", ["first", "second", "third"]);
// Returns the value "third" from the third column
// in the row with id 1 of the table "two".
sQL.sel("two", 1, 3);
// Removes the first row of the table "two".
sQL.rmv("two", 1);
// Returns "<null>" as the cell with id 1
// has been removed from table "two".
sQL.sel("two", 1, 2);
// Returns False as number of columns are not correct.
sQL.ins("two", ["fourth", "fifth"]);
// Adds a row to the table "two" with id 2. Returns True.
sQL.ins("two", ["fourth", "fifth", "sixth"]);
Constraints:
n == names.length == columns.length1 <= n <= 1041 <= names[i].length, row[i].length, name.length <= 10names[i],row[i], andnameconsist only of lowercase English letters.1 <= columns[i] <= 101 <= row.length <= 10- All
names[i]are distinct. - At most
2000calls will be made toinsandrmv. - At most
104calls will be made tosel. - At most
500calls will be made toexp.
Approach overview
Problem Overview: You need to design a lightweight SQL-like system that manages multiple tables. Each table supports three operations: insertRow, deleteRow, and selectCell. The goal is to store rows efficiently while allowing constant‑time access to any cell using a table name, row ID, and column ID.
Approach 1: Hash Table + Row Storage (O(1) per operation)
The most practical design uses a hash table to map table names to their internal data structure. Each table stores two things: the number of columns and a mapping of rowId → row data. When insertRow is called, increment a running row counter for that table and store the row values (typically an array or list of strings) in the map under that row ID. This makes insertion constant time since it’s just a hash insertion.
deleteRow simply removes the row ID from the table’s row map. No shifting or compaction is required, which avoids expensive operations common in array‑based storage. Deleting becomes an O(1) hash removal. Because row IDs are unique and monotonically increasing, there is no risk of collisions or the need to reuse IDs.
selectCell performs two quick lookups. First, use the table name to find the table object through a hash lookup. Then retrieve the row array using the row ID and return the value at columnId - 1 (columns are usually 1-indexed in the problem). Each lookup is constant time, so the total operation remains O(1).
This design works well because the workload is dominated by direct lookups rather than complex queries. A hash table provides constant‑time access to tables and rows, while an array or list keeps column access efficient. The structure also matches the problem constraints: rows are independent records and deletions don’t require reordering.
Another advantage is simplicity. Each table maintains:
nextRowId – the next ID to assign
rows – a map of rowId → array of column values
All operations remain straightforward dictionary operations with predictable performance.
Recommended for interviews: Interviewers expect the hash table design because it directly models the operations required by the problem. Explaining why row IDs should be monotonic and why rows should be stored in a hash map demonstrates strong understanding of system design style problems. Brute‑force array shifting or linear scans technically work but lead to O(n) operations, which scale poorly compared to the constant‑time hash map solution.
Solution
Create a hash table tables to store the mapping of table names to table data rows. Directly simulate the operations in the problem.
The time complexity of each operation is O(1), and the space complexity is O(n).
class SQL:
def __init__(self, names: List[str], columns: List[int]):
self.tables = defaultdict(list)
def insertRow(self, name: str, row: List[str]) -> None:
self.tables[name].append(row)
def deleteRow(self, name: str, rowId: int) -> None:
pass
def selectCell(self, name: str, rowId: int, columnId: int) -> str:
return self.tables[name][rowId - 1][columnId - 1]
# Your SQL object will be instantiated and called as such:
# obj = SQL(names, columns)
# obj.insertRow(name,row)
# obj.deleteRow(name,rowId)
# param_3 = obj.selectCell(name,rowId,columnId)class SQL {
private Map<String, List<List<String>>> tables;
public SQL(List<String> names, List<Integer> columns) {
tables = new HashMap<>(names.size());
}
public void insertRow(String name, List<String> row) {
tables.computeIfAbsent(name, k -> new ArrayList<>()).add(row);
}
public void deleteRow(String name, int rowId) {
}
public String selectCell(String name, int rowId, int columnId) {
return tables.get(name).get(rowId - 1).get(columnId - 1);
}
}
/**
* Your SQL object will be instantiated and called as such:
* SQL obj = new SQL(names, columns);
* obj.insertRow(name,row);
* obj.deleteRow(name,rowId);
* String param_3 = obj.selectCell(name,rowId,columnId);
*/class SQL {
public:
unordered_map<string, vector<vector<string>>> tables;
SQL(vector<string>& names, vector<int>& columns) {
}
void insertRow(string name, vector<string> row) {
tables[name].push_back(row);
}
void deleteRow(string name, int rowId) {
}
string selectCell(string name, int rowId, int columnId) {
return tables[name][rowId - 1][columnId - 1];
}
};
/**
* Your SQL object will be instantiated and called as such:
* SQL* obj = new SQL(names, columns);
* obj->insertRow(name,row);
* obj->deleteRow(name,rowId);
* string param_3 = obj->selectCell(name,rowId,columnId);
*/type SQL struct {
tables map[string][][]string
}
func Constructor(names []string, columns []int) SQL {
return SQL{map[string][][]string{}}
}
func (this *SQL) InsertRow(name string, row []string) {
this.tables[name] = append(this.tables[name], row)
}
func (this *SQL) DeleteRow(name string, rowId int) {
}
func (this *SQL) SelectCell(name string, rowId int, columnId int) string {
return this.tables[name][rowId-1][columnId-1]
}
/**
* Your SQL object will be instantiated and called as such:
* obj := Constructor(names, columns);
* obj.InsertRow(name,row);
* obj.DeleteRow(name,rowId);
* param_3 := obj.SelectCell(name,rowId,columnId);
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array List with Row Shifting | Insert: O(1), Delete: O(n), Select: O(1) | O(n * m) | Simple prototype where deletions are rare |
| Hash Table for Rows (Optimal) | O(1) per operation | O(n * m) | General case with frequent inserts, deletes, and lookups |
| Hash Table with Sparse Row Storage | O(1) | O(k) | When many rows are deleted and sparse storage saves memory |
Frequently asked questions
Is Design SQL easy or hard?
Design SQL is generally considered a medium difficulty problem. The logic is straightforward once you recognize that hash maps provide the best structure for constant-time table and row lookups. The challenge lies in designing the internal representation of tables and rows cleanly.
Design SQL Python/Java solution
A typical Python or Java solution creates a class SQL where tables are stored in a dictionary or HashMap. Each table tracks the next row ID and a map of rows. insertRow adds a row, deleteRow removes it, and selectCell retrieves the specific column value using constant-time lookups.
How to solve Design SQL in O(1)?
Store tables in a hash map keyed by table name. Each table maintains a rowId counter and a map from rowId to the row array. insertRow increments the counter and stores the row, deleteRow removes the rowId from the map, and selectCell returns the value from the stored array using columnId - 1.
What is the best approach for Design SQL?
The best approach uses a hash table to map table names to table objects, and another hash map inside each table to store rowId → row values. This allows insertRow, deleteRow, and selectCell to run in O(1) average time. Row values are typically stored as arrays or lists for constant-time column access.
Is Design SQL asked at Google/Amazon/Meta?
Design-style data structure problems like Design SQL commonly appear in interviews at large tech companies including Amazon, Google, and Meta. They test your ability to design efficient APIs and choose the right data structures such as hash maps and arrays for constant-time operations.
What data structure is used in Design SQL?
The core data structure is a hash table. One hash map stores table names and their metadata, while another hash map inside each table maps row IDs to arrays of column values. Arrays provide fast column access and hash maps provide constant-time row lookup.
What is the time complexity of Design SQL?
Using a hash table design, all main operations run in O(1) average time. insertRow performs a hash insertion, deleteRow removes a key from the map, and selectCell performs two constant-time lookups. Space complexity is O(n * m) where n is the number of rows and m is the number of columns.