2408. Design SQL

DifficultyMedium

Description

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.

Solutions

Solution 1: Hash Table

Thinking

Each table needs a stable row id, a column count, and a way to drop a row without renumbering the others. At most \(2000\) insertions and deletions occur, so a relational engine is unnecessary.

A dense list indexed by \(rowId-1\) still returns a deleted cell, and \(\textit{exp}\) would keep that row. Ids also keep increasing after a removal, so a freed slot cannot be reused.

Map each table name to the cells keyed by row id, and store the column count together with the next id.

\(\textit{ins}\) appends a row only when the table exists and the width matches. \(\textit{rmv}\) drops that id. \(\textit{sel}\) returns \(\texttt{<null>}\) when the table, row, or column is missing. \(\textit{exp}\) walks the surviving ids in order and joins each row with its id.

Record the column count of each table, and store live rows in a hash map keyed by row id. Simulate \(\textit{ins}\), \(\textit{rmv}\), \(\textit{sel}\), and \(\textit{exp}\) directly.

Insertion, deletion, and selection are \(O(1)\) on average. Exporting a table scans the rows that are still present. The space is proportional to the number of inserted cells.

Python3JavaC++Go

class SQL:
    def __init__(self, names: List[str], columns: List[int]):
        self.cols = dict(zip(names, columns))
        self.rows = {name: {} for name in names}
        self.nxt = {name: 1 for name in names}

    def ins(self, name: str, row: List[str]) -> bool:
        if name not in self.cols or len(row) != self.cols[name]:
            return False
        i = self.nxt[name]
        self.rows[name][i] = row
        self.nxt[name] = i + 1
        return True

    def rmv(self, name: str, rowId: int) -> None:
        if name in self.rows:
            self.rows[name].pop(rowId, None)

    def sel(self, name: str, rowId: int, columnId: int) -> str:
        row = self.rows.get(name, {}).get(rowId)
        if row is None or columnId < 1 or columnId > len(row):
            return '<null>'
        return row[columnId - 1]

    def exp(self, name: str) -> List[str]:
        if name not in self.rows:
            return []
        return [
            ','.join([str(i), *self.rows[name][i]]) for i in sorted(self.rows[name])
        ]


# Your SQL object will be instantiated and called as such:
# obj = SQL(names, columns)
# param_1 = obj.ins(name,row)
# obj.rmv(name,rowId)
# param_3 = obj.sel(name,rowId,columnId)
# param_4 = obj.exp(name)

class SQL {
    private final Map<String, Integer> cols = new HashMap<>();
    private final Map<String, Map<Integer, List<String>>> rows = new HashMap<>();
    private final Map<String, Integer> nxt = new HashMap<>();

    public SQL(String[] names, int[] columns) {
        for (int i = 0; i < names.length; ++i) {
            cols.put(names[i], columns[i]);
            rows.put(names[i], new HashMap<>());
            nxt.put(names[i], 1);
        }
    }

    public boolean ins(String name, String[] row) {
        if (!cols.containsKey(name) || row.length != cols.get(name)) {
            return false;
        }
        int id = nxt.get(name);
        rows.get(name).put(id, Arrays.asList(row));
        nxt.put(name, id + 1);
        return true;
    }

    public void rmv(String name, int rowId) {
        Map<Integer, List<String>> table = rows.get(name);
        if (table != null) {
            table.remove(rowId);
        }
    }

    public String sel(String name, int rowId, int columnId) {
        Map<Integer, List<String>> table = rows.get(name);
        if (table == null || !table.containsKey(rowId)) {
            return "<null>";
        }
        List<String> row = table.get(rowId);
        if (columnId < 1 || columnId > row.size()) {
            return "<null>";
        }
        return row.get(columnId - 1);
    }

    public String[] exp(String name) {
        Map<Integer, List<String>> table = rows.get(name);
        if (table == null) {
            return new String[0];
        }
        List<Integer> ids = new ArrayList<>(table.keySet());
        Collections.sort(ids);
        String[] ans = new String[ids.size()];
        for (int i = 0; i < ids.size(); ++i) {
            int id = ids.get(i);
            ans[i] = id + "," + String.join(",", table.get(id));
        }
        return ans;
    }
}

/**
 * Your SQL object will be instantiated and called as such:
 * SQL obj = new SQL(names, columns);
 * boolean param_1 = obj.ins(name,row);
 * obj.rmv(name,rowId);
 * String param_3 = obj.sel(name,rowId,columnId);
 * String[] param_4 = obj.exp(name);
 */

class SQL {
public:
    unordered_map<string, int> cols;
    unordered_map<string, map<int, vector<string>>> rows;
    unordered_map<string, int> nxt;

    SQL(vector<string>& names, vector<int>& columns) {
        for (int i = 0; i < (int) names.size(); ++i) {
            cols[names[i]] = columns[i];
            nxt[names[i]] = 1;
        }
    }

    bool ins(string name, vector<string> row) {
        if (!cols.count(name) || (int) row.size() != cols[name]) {
            return false;
        }
        int id = nxt[name]++;
        rows[name][id] = std::move(row);
        return true;
    }

    void rmv(string name, int rowId) {
        if (rows.count(name)) {
            rows[name].erase(rowId);
        }
    }

    string sel(string name, int rowId, int columnId) {
        if (!rows.count(name) || !rows[name].count(rowId)) {
            return "<null>";
        }
        auto& row = rows[name][rowId];
        if (columnId < 1 || columnId > (int) row.size()) {
            return "<null>";
        }
        return row[columnId - 1];
    }

    vector<string> exp(string name) {
        vector<string> ans;
        if (!rows.count(name)) {
            return ans;
        }
        for (auto& [id, row] : rows[name]) {
            string s = to_string(id);
            for (auto& cell : row) {
                s += "," + cell;
            }
            ans.push_back(s);
        }
        return ans;
    }
};

/**
 * Your SQL object will be instantiated and called as such:
 * SQL* obj = new SQL(names, columns);
 * bool param_1 = obj->ins(name,row);
 * obj->rmv(name,rowId);
 * string param_3 = obj->sel(name,rowId,columnId);
 * vector<string> param_4 = obj->exp(name);
 */

type SQL struct {
    cols   map[string]int
    rows   map[string]map[int][]string
    nextId map[string]int
}

func Constructor(names []string, columns []int) SQL {
    cols := map[string]int{}
    rows := map[string]map[int][]string{}
    nextId := map[string]int{}
    for i, name := range names {
        cols[name] = columns[i]
        rows[name] = map[int][]string{}
        nextId[name] = 1
    }
    return SQL{cols, rows, nextId}
}

func (this *SQL) Ins(name string, row []string) bool {
    c, ok := this.cols[name]
    if !ok || len(row) != c {
        return false
    }
    id := this.nextId[name]
    this.nextId[name] = id + 1
    cp := append([]string(nil), row...)
    this.rows[name][id] = cp
    return true
}

func (this *SQL) Rmv(name string, rowId int) {
    if table, ok := this.rows[name]; ok {
        delete(table, rowId)
    }
}

func (this *SQL) Sel(name string, rowId int, columnId int) string {
    table, ok := this.rows[name]
    if !ok {
        return "<null>"
    }
    row, ok := table[rowId]
    if !ok || columnId < 1 || columnId > len(row) {
        return "<null>"
    }
    return row[columnId-1]
}

func (this *SQL) Exp(name string) []string {
    table, ok := this.rows[name]
    if !ok || len(table) == 0 {
        return []string{}
    }
    ids := make([]int, 0, len(table))
    for id := range table {
        ids = append(ids, id)
    }
    sort.Ints(ids)
    ans := make([]string, 0, len(ids))
    for _, id := range ids {
        s := strconv.Itoa(id)
        for _, cell := range table[id] {
            s += "," + cell
        }
        ans = append(ans, s)
    }
    return ans
}

/**
 * Your SQL object will be instantiated and called as such:
 * obj := Constructor(names, columns);
 * param_1 := obj.Ins(name,row);
 * obj.Rmv(name,rowId);
 * param_3 := obj.Sel(name,rowId,columnId);
 * param_4 := obj.Exp(name);
 */

2408. Design SQL

Description

Solutions

Solution 1: Hash Table

Comments