Design SQL - Solution & Explanation

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

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

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

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

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

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

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

MediumPremiumFree on FleetCodeArray Hash Table String Design8 min readAsked at: Amazon, Openai

Practice this problem

Problem Statement

You are given two string arrays, names and columns, both of size n. The i^th 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 n tables.
bool ins(String name, String[] row)
- Inserts row into the table name and returns true.
- If row.length does not match the expected number of columns, or name is not a valid table, returns false without any insertion.
void rmv(String name, int rowId)
- Removes the row rowId from the table name.
- If name is not a valid table or there is no row with id rowId, no removal is performed.
String sel(String name, int rowId, int columnId)
- Returns the value of the cell at the specified rowId and columnId in the table name.
- If name is not a valid table, or the cell (rowId, columnId) is invalid, returns "<null>".
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 ",".

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.length
1 <= n <= 10⁴
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.
At most 10⁴ calls will be made to sel.
At most 500 calls will be made to exp.

Follow-up: Which approach would you choose if the table might become sparse due to many deletions, and why? Consider the impact on memory usage and performance.

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

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Detailed 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

Video Solution

2408. Design SQL (Leetcode Medium) • Programming Live with Larry • 1,151 views views

Watch 1 more video solutions →

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.

Ready to solve this problem?

Practice Design SQL with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance63.9%

Approaches1

Reading time8 min

Asked at

Amazon Openai