2408. Design SQL

Problem¶

Implement SQL with named tables and fixed column counts. Valid inserts receive increasing, never-reused row IDs; removal leaves IDs unchanged. Selection returns a cell or "<null>", and export returns surviving rows as CSV strings in ID order.

SQL(["t"], [1])
ins("t", ["a"]) -> True          # ID 1
rmv("t", 1)
ins("t", ["b"]) -> True          # ID 2
exp("t") -> ["2,b"]

class SQL:
    def __init__(self, names: list[str], columns: list[int]):
        pass

    def ins(self, name: str, row: list[str]) -> bool:
        pass

    def rmv(self, name: str, rowId: int) -> None:
        pass

    def sel(self, name: str, rowId: int, columnId: int) -> str:
        pass

    def exp(self, name: str) -> list[str]:
        pass

Key trick¶

Keep each table's next ID separate from its surviving rows. A dictionary stores rows by ID without retaining deleted slots.

Trap¶

Column IDs are 1-based, and neither deletion nor a failed insert should change the next ID.

Why is it interesting?¶

It tests whether you separate an identifier's history from the records currently stored. A dictionary also handles the follow-up's sparse-table case efficiently.

Python solution¶

class SQL:
    def __init__(self, names: list[str], columns: list[int]):
        self.tables = {
            name: {"columns": cnt, "next_id": 1, "rows": {}}
            for name, cnt in zip(names, columns)
        }

    def ins(self, name: str, row: list[str]) -> bool:
        table = self.tables.get(name)
        if table is None or len(row) != table["columns"]:
            return False

        row_id = table["next_id"]
        table["rows"][row_id] = tuple(row)
        table["next_id"] += 1
        return True

    def rmv(self, name: str, rowId: int) -> None:
        table = self.tables.get(name)
        if table is not None:
            table["rows"].pop(rowId, None)

    def sel(self, name: str, rowId: int, columnId: int) -> str:
        table = self.tables.get(name)
        if table is None or not 1 <= columnId <= table["columns"]:
            return "<null>"

        row = table["rows"].get(rowId)
        return "<null>" if row is None else row[columnId - 1]

    def exp(self, name: str) -> list[str]:
        table = self.tables.get(name)
        if table is None:
            return []

        # IDs increase on insertion, so dictionary iteration is in ID order.
        return [
            ",".join((str(row_id), *row))
            for row_id, row in table["rows"].items()
        ]

With \(c\) columns and \(r\) surviving rows in the requested table, initialization takes \(O(n)\) time. Insert takes \(O(c)\) time; removal and selection take \(O(1)\) average time; export takes \(O(rc)\) time and output space. Stored rows use \(O(\sum c)\) space over surviving rows.

Comment on my solution¶

Your data structure and insert logic are sound. Two indexing mistakes cause the failures:

rmv deletes the entire "rows" entry; it should delete only rows[rowId].
sel treats columnId as 0-based. Validate it from 1 through the column count, then access row[columnId - 1].

Your export relies on dictionary insertion order, which is appropriate here because inserted IDs always increase.

# WRONG
class SQL:

    def __init__(self, names: list[str], columns: list[int]):
        self.tables = {}
        for name, cnt in zip(names, columns):
            self.tables[name] = {"id": 0, "cols_cnt": cnt, "rows": {}}


    def ins(self, name: str, row: list[str]) -> bool:
        if name not in self.tables or len(row) != self.tables[name]["cols_cnt"]:
            return False
        self.tables[name]["id"] += 1
        row_id = self.tables[name]["id"]
        self.tables[name]["rows"][row_id] = row
        return True


    def rmv(self, name: str, rowId: int) -> None:
        if name not in self.tables or rowId not in self.tables[name]["rows"]:
            return
        del self.tables[name]["rows"]


    def sel(self, name: str, rowId: int, columnId: int) -> str:
        if name not in self.tables or rowId not in self.tables[name]["rows"] or not (0 <= columnId < self.tables[name]["cols_cnt"]):
            return "<null>"
        return self.tables[name]["rows"][rowId][columnId]


    def exp(self, name: str) -> list[str]:
        if name not in self.tables:
            return []
        res = []
        for row_id, row in self.tables[name]["rows"].items():
            res.append(",".join((str(row_id), *row)))
        return res


# WORKS
# Written after reading AI comments
class SQL:

    def __init__(self, names: list[str], columns: list[int]):
        self.tables = {}
        for name, cnt in zip(names, columns):
            self.tables[name] = {"id": 0, "cols_cnt": cnt, "rows": {}}


    def ins(self, name: str, row: list[str]) -> bool:
        if name not in self.tables or len(row) != self.tables[name]["cols_cnt"]:
            return False
        self.tables[name]["id"] += 1
        row_id = self.tables[name]["id"]
        self.tables[name]["rows"][row_id] = row
        return True


    def rmv(self, name: str, rowId: int) -> None:
        if name not in self.tables or rowId not in self.tables[name]["rows"]:
            return
        del self.tables[name]["rows"][rowId]


    def sel(self, name: str, rowId: int, columnId: int) -> str:
        if name not in self.tables or rowId not in self.tables[name]["rows"] or not (1 <= columnId <= self.tables[name]["cols_cnt"]):
            return "<null>"
        return self.tables[name]["rows"][rowId][columnId - 1]


    def exp(self, name: str) -> list[str]:
        if name not in self.tables:
            return []
        res = []
        for row_id, row in self.tables[name]["rows"].items():
            res.append(",".join((str(row_id), *row)))
        return res

Extra¶

columnId is 1-based¶

Where in the problem description could I've seen that columnId is 1-based?

The clearest clue is Example 1: sel("two", 1, 3) returns "third" from a three-column row. That only works if columnId is 1-based. The statement does not explicitly say so.