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
n
tables.
- Creates the
bool ins(String name, String[] row)
- Inserts
row
into the tablename
and returnstrue
. - If
row.length
does not match the expected number of columns, orname
is not a valid table, returnsfalse
without any insertion.
- Inserts
void rmv(String name, int rowId)
- Removes the row
rowId
from the tablename
. - If
name
is 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
rowId
andcolumnId
in the tablename
. - If
name
is 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
Examples
Example 1:
|
|
Example 2:
|
|
Constraints:
n == names.length == columns.length
1 <= n <= 10^4
1 <= names[i].length, row[i].length, name.length <= 10
names[i]
,row[i]
, andname
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 toins
andrmv
. - At most
104
calls will be made tosel
. - At most
500
calls will be made toexp
.
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.
Solution
Method 1 – Hash Maps and List for Table Storage
Intuition
We use a hash map to store each table’s schema and data. Each table keeps a list of rows (with auto-incremented ids) and a counter for the next id. This allows efficient insert, remove, select, and export operations.
Approach
- Store tables in a hash map: each table has a column count, a list of rows (id + data), and a next id counter.
- For
ins(name, row)
, check if the table exists and the row length matches. If so, append the row with the next id and increment the id counter. - For
rmv(name, rowId)
, remove the row with the given id if it exists. - For
sel(name, rowId, columnId)
, return the value if the table, row, and column exist; otherwise, return"<null>"
. - For
exp(name)
, return all rows as CSV strings (id first), or an empty array if the table does not exist.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(1)
for insert,O(n)
for remove/select/export (where n is the number of rows in the table). - 🧺 Space complexity:
O(T + R*C)
, where T is the number of tables, R is the total number of rows, and C is the number of columns.