In-memory SQL table with filtering and multi-key sorting

This is a staged object-design problem more than an algorithm problem. Interviewers grade how cleanly the code grows from "create and insert" to "filter and sort". Keep three pieces separate from the first part, because every later part builds on them:

1. Storage. A Table holds its column names, a col -> position map, the inferred type of each column, and its rows as a list of lists in insertion order. Insertion order is the default result order and the final tie-break for sorting.
2. Type inference. Each inserted value is a string. If it matches an optional sign followed by digits, it is an int; otherwise it is a str. A column has no type until it receives its first value. That value fixes the type, and a later value of the other type is rejected. If you reject the whole row before writing anything, a bad insert leaves the table unchanged.
3. Query pipeline. select runs the same three steps as SQL: filter (WHERE) → sort (ORDER BY) → project (pick the requested columns). Projection comes last because a query can sort or filter on a column that it does not return.

Brute force is the right answer here. Without indexes, every select scans the whole table, which is O(n) for the filter plus O(k log k) to sort the k matches. Say this out loud, then mention indexes as a follow-up. Do not build them before the interviewer asks.

Filtering. Each condition is (column, op, literal). Convert the literal to the column's type once per query, not once per row. Then map op to a function from operator (=, !=, <, <=, >, >=). All conditions must hold (AND). Comparing an int column with "abc" is a type error. Raise it; do not silently return no rows.

Multi-key sorting with mixed directions. Python's sort is stable. So sort by the least significant key first and the most significant key last, passing reverse=True for DESC keys. Rows that tie on every key keep insertion order. This avoids negating strings, which a single composite key would need for DESC on a text column.

Invariants:

• Every row has exactly len(columns) values.
• Every non-None value in a column has that column's type.
• select never changes stored rows. It returns new lists.

from __future__ import annotations

import operator
import re
from typing import Any, Callable, Optional, Sequence

INT_RE = re.compile(r"[+-]?\d+")
OPS: dict[str, Callable[[Any, Any], bool]] = {
    "=": operator.eq, "!=": operator.ne,
    "<": operator.lt, "<=": operator.le,
    ">": operator.gt, ">=": operator.ge,
}


def infer(raw: str) -> int | str:
    return int(raw) if INT_RE.fullmatch(raw) else raw


class Table:
    def __init__(self, columns: Sequence[str]) -> None:
        if len(set(columns)) != len(columns):
            raise ValueError("duplicate column name")
        self.columns = list(columns)
        self.pos = {c: i for i, c in enumerate(columns)}
        self.types: list[Optional[type]] = [None] * len(columns)
        self.rows: list[list[int | str]] = []

    def index(self, col: str) -> int:
        if col not in self.pos:
            raise KeyError(f"unknown column {col!r}")
        return self.pos[col]

    def insert(self, raw_values: Sequence[str]) -> None:
        if len(raw_values) != len(self.columns):
            raise ValueError("wrong number of values")
        values = [infer(v) for v in raw_values]
        # Validate the whole row before mutating anything (atomic insert).
        for i, v in enumerate(values):
            t = self.types[i]
            if t is not None and type(v) is not t:
                raise TypeError(f"column {self.columns[i]!r} expects {t.__name__}")
        for i, v in enumerate(values):
            self.types[i] = self.types[i] or type(v)
        self.rows.append(values)

    def coerce(self, i: int, literal: str) -> int | str:
        v, t = infer(literal), self.types[i]
        if t is str:
            return literal          # "007" stays a string in a text column
        if t is int and not isinstance(v, int):
            raise TypeError(f"column {self.columns[i]!r} is int, got {literal!r}")
        return v


class SQLManager:
    def __init__(self) -> None:
        self.tables: dict[str, Table] = {}

    def create_table(self, name: str, columns: list[str]) -> None:
        if name in self.tables:
            raise ValueError(f"table {name!r} exists")
        self.tables[name] = Table(columns)

    def insert(self, name: str, values: list[str]) -> None:
        self._table(name).insert(values)

    def select(
        self,
        name: str,
        columns: Optional[list[str]] = None,                    # None means *
        where: Optional[list[tuple[str, str, str]]] = None,     # ANDed
        order_by: Optional[list[tuple[str, str]]] = None,       # (col, ASC|DESC)
    ) -> list[list[int | str]]:
        t = self._table(name)
        preds = []
        for col, op, lit in where or []:
            if op not in OPS:
                raise ValueError(f"unsupported operator {op!r}")
            i = t.index(col)
            preds.append((i, OPS[op], t.coerce(i, lit)))
        rows = [r for r in t.rows if all(f(r[i], v) for i, f, v in preds)]

        # Stable multi-key sort: least significant key first.
        for col, direction in reversed(order_by or []):
            d = direction.upper()
            if d not in ("ASC", "DESC"):
                raise ValueError(f"bad direction {direction!r}")
            i = t.index(col)
            rows.sort(key=lambda r: r[i], reverse=(d == "DESC"))

        idx = [t.index(c) for c in columns] if columns else range(len(t.columns))
        return [[r[i] for i in idx] for r in rows]

    def _table(self, name: str) -> Table:
        if name not in self.tables:
            raise KeyError(f"unknown table {name!r}")
        return self.tables[name]

Let n be the rows in the table, c the columns, w the WHERE conditions, s the ORDER BY keys, and k the matching rows.

• create_table: O(c) time and space.
• insert: O(c) time. Storage is O(c) per row, so O(n·c) in total.
• select: O(n·w) to filter, O(s·k log k) to sort, and O(k·p) to project p columns. Extra space is O(k·p) for the result plus O(k) for the filtered row list.

• Setup: create_table("users", ["id", "name", "age"]), then insert ["1","ann","30"], ["2","bob","25"], ["3","cat","30"], ["4","dan","41"].
• select("users") returns all four rows in insertion order, with id and age as ints.
• select("users", ["name"], [("age", ">=", "30")]) → [["ann"], ["cat"], ["dan"]].
• select("users", ["name"], [("age", "=", "30"), ("id", ">", "1")]) → [["cat"]] (AND).
• select("users", ["name","age"], order_by=[("age","DESC"),("name","ASC")]) → [["dan",41],["ann",30],["cat",30],["bob",25]].
• Integer ordering is numeric, not lexicographic: after inserting ["5","eve","100"], order_by=[("age","ASC")] puts 100 last.
• Ties keep insertion order: order_by=[("age","ASC")] returns ann before cat.
• Projection of a column that only the sort uses: select("users", ["name"], order_by=[("id","DESC")]) → [["dan"],["cat"],["bob"],["ann"]].
• Type lock: insert("users", ["x","eve","20"]) raises TypeError, and the row count does not change.
• Wrong arity: insert("users", ["6","fay"]) raises ValueError.
• Negative ints: "-5" infers as -5. "5.0" and "12a" stay strings.
• Unknown table or column raises KeyError. A filter value of "abc" on an int column raises TypeError.
• Empty table: select returns [] for any filter or sort.

1. OR and nested conditions. Replace the flat list with a small expression tree: Cond(col, op, val), And([...]), Or([...]), Not(x). Compile it once into a closure row -> bool, so the per-row cost does not include tree dispatch. Ask whether the input stays structured or arrives as a string. If it arrives as a string, write a tiny recursive-descent parser with precedence NOT > AND > OR.
2. Indexes for equality and range filters. Keep a per-column dict[value, list[row_id]] for equality, or a sorted list of (value, row_id) with bisect for ranges. Pick the most selective indexed condition, fetch its candidates, then check the remaining conditions on those rows only. Inserts now cost O(log n) per indexed column. Mention when an index is not worth it: low-cardinality columns, or tables with heavy writes.
3. UPDATE and DELETE with WHERE. Reuse the filter. For delete, use tombstones (a deleted flag or a free-list) or compact the table, and keep indexes in sync. Row ids must stay stable if indexes store them.
4. NULLs and missing values. Allow None and decide the comparison semantics: SQL three-valued logic makes NULL = x unknown. Choose where NULLs sort (NULLS FIRST/LAST). In Python, sort with a key like (v is None, v) so the sort never compares None with a value.
5. LIMIT/OFFSET, aggregates, multiple tables. For ORDER BY ... LIMIT k, use heapq.nsmallest, which takes O(n log k) instead of a full sort. For GROUP BY with COUNT/SUM/MIN/MAX, keep a dict of accumulators. A simple join is a hash join: build a dict on the smaller table's join key, then probe it with the other table.

Mid-level (L4)

• Working create, insert and select with a single-condition filter and a single-column sort, finished on time.
• Correct int vs string inference, including that integers sort numerically.
• Reasonable errors for an unknown table or column.

Senior (L5)

• Clean separation between Table and SQLManager and a filter → sort → project pipeline, so each new part is a small change.
• Multi-key ORDER BY with mixed directions, done with a stable sort or an equivalent comparator. Atomic inserts and literals coerced once per query.
• States the complexity of each operation without being asked and names the indexing trade-off.

Staff (L6+)

• Drives the requirement questions early: type locking, NULL semantics, tie order, and whether input is structured or SQL text.
• Designs the WHERE representation so OR, NOT and nesting fit later without a rewrite. Sketches the plan for choosing which index to use.
• Discusses how the design would change for UPDATE/DELETE with indexes and for concurrent readers and writers (copy-on-write snapshots or a table-level RW lock), and stays honest about what is out of scope.