Design SQL

Design SQL

What is this problem about?

The Design SQL interview question asks you to simulate a simple relational database. You are given table names and the number of columns each table has. You need to implement insertRow, deleteRow, and selectCell operations. Each row is assigned an auto-incrementing ID starting from 1.

Why is this asked in interviews?

OpenAI and Amazon use this to test a candidate's ability to organize data efficiently for specific access patterns. It’s a test of "Mapping" skills. It evaluations whether you can choose the right container (like a Map of Maps or a Map of Lists) to represent tables and rows, ensuring that lookups are $O(1)$.

Algorithmic pattern used

This problem follows the Hash Table design pattern.

1. A Map<String, Table> stores tables by their names.
2. Each Table object contains a Map<Integer, List<String>> where the key is the row ID and the value is the list of column values.
3. Each Table also maintains an internal nextId counter.

Example explanation

1. createTable("Users", columns=2): Creates an empty table entry.
2. insertRow("Users", ["Alice", "NY"]): Assigns ID 1. Data: {1: ["Alice", "NY"]}.
3. insertRow("Users", ["Bob", "SF"]): Assigns ID 2. Data: {1: ["Alice", "NY"], 2: ["Bob", "SF"]}.
4. selectCell("Users", 2, 1): Returns "Bob" (row 2, column 1).

Common mistakes candidates make

• List vs Map for Rows: Using a list to store rows can make deleteRow and selectCell inefficient ($O(N)$) because you have to search for the ID. A Map from ID to Row is $O(1)$.
• ID Management: Forgetting that IDs are per-table, not global.
• Column Indexing: Confusion between 1-based indexing (often used in SQL) and 0-based indexing used in programming languages.

Interview preparation tip

This is a straightforward implementation task. The key is to keep your classes modular. Have a Table class that handles its own IDs and row storage, and a SQL class that manages the tables. This demonstrates clean architectural practices.