Build a Database class with the operations below.

Required Methods

class Database:
    def __init__(self):
        """Initialize the database"""
        pass

    def create_table(self, table_name: str, columns: List[str]):
        """Create a new table with specified columns"""
        pass

    def insert(self, table_name: str, row: Dict[str, Any]):
        """Insert a row into the specified table"""
        pass

    def query(self, table_name: str, columns: List[str]) -> List[Dict[str, Any]]:
        """
        Query specific columns from a table (projection).
        Returns all rows but only with the specified columns.
        """
        pass

Example Usage

db = Database()
db.create_table("users", ["id", "name", "birthday"])

db.insert("users", {"id": "1", "name": "Alice", "birthday": "1990-05-15"})
db.insert("users", {"id": "2", "name": "Bob", "birthday": "1985-08-20"})
db.insert("users", {"id": "3", "name": "Charlie", "birthday": "1992-03-10"})

# Query all users, returning only id and name
result = db.query("users", ["id", "name"])
# Expected: [
# {"id": "1", "name": "Alice"},
# {"id": "2", "name": "Bob"},
# {"id": "3", "name": "Charlie"}
# ]

# Query all users, returning only name
result = db.query("users", ["name"])
# Expected: [
# {"name": "Alice"},
# {"name": "Bob"},
# {"name": "Charlie"}
# ]

The first query retains only each user's id and name, while the second projects the table down to name alone.

Test Cases to Consider

• Creating more than one table
• Adding several rows
• Selecting one column
• Selecting several columns
• Selecting every column
• Edge cases such as an empty table and columns that do not exist

Enhance query so callers may optionally supply one predicate to decide which rows are included.

Updated Method Signature

def query(self,
          table_name: str,
          columns: List[str],
          where: Optional[Callable[[Dict], bool]] = None) -> List[Dict[str, Any]]:
    """
    Query with optional WHERE condition.

    Args:
        table_name: Name of the table to query
        columns: List of column names to return
        where: Optional filter function that takes a row dict and returns bool
    """
    pass

Example Usage

db = Database()
db.create_table("users", ["id", "name", "birthday"])

db.insert("users", {"id": "1", "name": "Alice", "birthday": "1990-05-15"})
db.insert("users", {"id": "2", "name": "Bob", "birthday": "1985-08-20"})
db.insert("users", {"id": "3", "name": "Charlie", "birthday": "1992-03-10"})

# Query users born after 1990-01-01
result = db.query(
    "users",
    ["name", "birthday"],
    where=lambda row: row["birthday"] > "1990-01-01"
)
# Expected: [
# {"name": "Alice", "birthday": "1990-05-15"},
# {"name": "Charlie", "birthday": "1992-03-10"}
# ]

# Query users with id greater than 1
result = db.query(
    "users",
    ["id", "name"],
    where=lambda row: int(row["id"]) > 1
)
# Expected: [
# {"id": "2", "name": "Bob"},
# {"id": "3", "name": "Charlie"}
# ]

The first result includes the two birthdays later than 1990-01-01; the second includes the rows whose numeric IDs exceed 1.

Test Cases to Consider

• Omitting WHERE and preserving Part 1 behavior
• Comparing numeric values
• Comparing strings
• Comparing dates or timestamps
• A predicate that matches no rows
• A predicate that matches every row

Expand filtering so several conditions can be evaluated together with AND semantics.

Example Usage - Option 1: Lambda with Multiple Conditions

# Query users with id > 1 AND name starting with 'C'
result = db.query(
    "users",
    ["id", "name"],
    where=lambda row: int(row["id"]) > 1 and row["name"].startswith("C")
)
# Expected: [{"id": "3", "name": "Charlie"}]

Only Charlie satisfies both the ID condition and the name-prefix condition.

Example Usage - Option 2: List of Conditions (Alternative API)

You may instead define the interface to receive a collection of condition tuples:

def query(self,
          table_name: str,
          columns: List[str],
          where: Optional[List[Tuple[str, str, Any]]] = None) -> List[Dict[str, Any]]:
    """
    Args:
        where: List of conditions [(column, operator, value),...]
               All conditions are combined with AND
               Operators: "=", ">", "<", ">=", "<=", "!="
    """
    pass

# Query users with id > 1 AND name = "Charlie"
result = db.query(
    "users",
    ["id", "name"],
    where=[("id", ">", "1"), ("name", "=", "Charlie")]
)
# Expected: [{"id": "3", "name": "Charlie"}]

This tuple-list representation is an optional Part 3 API rather than a required replacement. The reference implementation described later accepts both a callable filter such as where=lambda row:... and a tuple-list filter such as where=[("col", "op", value),...].

Test Cases to Consider

• Several conditions that are all true
• Several conditions that produce no match
• A mixture of numeric and string predicates
• An empty condition list, which should return every row

Add optional sorting to query.

Updated Method Signature

The interface should leave room for the multi-column ordering introduced in Part 5. You may begin with order_by: Optional[str] and revise it later, which is simpler but breaks backward compatibility, or adopt order_by: Optional[Union[str, Tuple[List[str], bool]]] immediately, which is more extensible but more involved.

For the basic form, the signature can be:

def query(self,
          table_name: str,
          columns: List[str],
          where: Optional[Callable[[Dict], bool]] = None,
          order_by: Optional[str] = None) -> List[Dict[str, Any]]:
    """
    Query with optional WHERE and ORDER BY.

    Args:
        order_by: Column name to sort by (ascending order)
    """
    pass

The reference implementation uses the extensible Part 5 representation from the beginning, so it does not need to change the interface later.

Example Usage

db = Database()
db.create_table("users", ["id", "name", "age"])

db.insert("users", {"id": "1", "name": "Alice", "age": "30"})
db.insert("users", {"id": "2", "name": "Bob", "age": "25"})
db.insert("users", {"id": "3", "name": "Charlie", "age": "35"})

# Query users ordered by name (using simple string)
result = db.query("users", ["name", "age"], order_by="name")
# Expected: [
# {"name": "Alice", "age": "30"},
# {"name": "Bob", "age": "25"},
# {"name": "Charlie", "age": "35"}
# ]

# Alternatively, if using Part 5's format from the start:
result = db.query("users", ["name", "age"], order_by=(["name"], True))

# Query users with WHERE and ORDER BY
result = db.query(
    "users",
    ["name", "age"],
    where=lambda row: int(row["age"]) > 28,
    order_by="name" # or order_by=(["name"], True)
)
# Expected: [
# {"name": "Alice", "age": "30"},
# {"name": "Charlie", "age": "35"}
# ]

The first ordered result is alphabetical by name. In the final query, Bob is removed by the predicate, and the remaining names are returned alphabetically.

Test Cases to Consider

• Ordering string-valued columns
• Ordering numeric-valued columns, including consideration of string-to-number conversion
• Applying both WHERE and ORDER BY
• Ordering without a WHERE condition
• Preserving order when sort keys are equal

Extend ordering to accept multiple sort keys and one common direction for all of them.

Updated Method Signature

def query(self,
          table_name: str,
          columns: List[str],
          where: Optional[Callable[[Dict], bool]] = None,
          order_by: Optional[Tuple[List[str], bool]] = None) -> List[Dict[str, Any]]:
    """
    Query with optional WHERE and ORDER BY.

    Args:
        order_by: Tuple of (column_list, is_ascending)
                  Example: (["age", "name"], True) sorts by age then name, both ascending
                  Example: (["age", "name"], False) sorts by age then name, both descending
                  Note: All columns use the same sort direction in this simplified version
    """
    pass

Example Usage

db = Database()
db.create_table("users", ["id", "name", "birthday"])

db.insert("users", {"id": "1", "name": "Ada", "birthday": "1815-12-10"})
db.insert("users", {"id": "2", "name": "Charles", "birthday": "1791-12-26"})
db.insert("users", {"id": "3", "name": "Charles", "birthday": "1903-06-23"})

# Sort by name descending, then birthday descending
result = db.query(
    "users",
    ["id", "name", "birthday"],
    order_by=(["name", "birthday"], False)
)
# Expected: [
# {"id": "3", "name": "Charles", "birthday": "1903-06-23"},
# {"id": "2", "name": "Charles", "birthday": "1791-12-26"},
# {"id": "1", "name": "Ada", "birthday": "1815-12-10"}
# ]

# With WHERE clause
result = db.query(
    "users",
    ["id"],
    where=lambda row: row["name"] == "Charles",
    order_by=(["birthday"], False)
)
# Expected: [{"id": "3"}, {"id": "2"}]

The first query places the two Charles rows before Ada and uses birthday to break their tie, all in descending order. The second query keeps only Charles and orders those two rows by descending birthday.

Alternative Design: Per-Column Sort Direction

A more advanced API could assign a direction independently to each key:

order_by: Optional[List[Tuple[str, str]]] = None
# Example: [("name", "ASC"), ("birthday", "DESC")]

That design supports mixed directions, but it makes the implementation more complicated. The simpler all-columns-share-one-direction model above is sufficient for this interview exercise.

Test Cases to Consider

• Multiple ascending keys
• Multiple descending keys
• Mixed directions, if you choose to support them
• Cases requiring a tie-breaker
• A single key together with a direction

This part is generally a design discussion rather than an implementation task.

The interviewer may ask: “How would you improve query performance by adding indexes?”

Key Points to Discuss

1. Inverted Index for WHERE Clauses

   • Use a structure such as {column_name: {value: [row_indices]}}.
   • For example, {"name": {"Alice": [0], "Bob": [1, 3]}} maps each value to the rows containing it.
   • Equality lookups can improve from O(n) scanning to O(1) plus O(k), where k is the number of returned rows.

2. B-Tree Index for Range Queries

   • B-trees are useful for >, <, >=, and <= predicates.
   • They retain sorted order so range scans can be performed efficiently.
   • The trade-off is slower insertion in exchange for faster queries.

3. Composite Index

   • An index over multiple columns can help with WHERE clauses containing multiple conditions.
   • One example is an index on (age, name) for queries that filter on both fields.

4. Index Maintenance

   • INSERT operations must update the relevant indexes.
   • Indexes trade faster reads for slower writes.
   • Consider when indexes should be constructed, such as after bulk inserts instead of during every insert.

5. Query Optimization Strategy

   • Use the WHERE index first to reduce the candidate rows.
   • Perform column projection after filtering.
   • Sort only after the filtered result has been produced.

Example Index Implementation (Conceptual)

class Database:
    def __init__(self):
        self.tables = {}
        self.schemas = {}
        self.indexes = {} # {table_name: {column_name: {value: [row_indices]}}}

    def create_index(self, table_name: str, column_name: str):
        """Build inverted index on column"""
        if table_name not in self.indexes:
            self.indexes[table_name] = {}

        index = {}
        for i, row in enumerate(self.tables[table_name]):
            value = row[column_name]
            if value not in index:
                index[value] = []
            index[value].append(i)

        self.indexes[table_name][column_name] = index