Bird
Raised Fist0

Design an In-Memory SQL Database - Table, Row, Column, Query Parser, Indexing

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design an In-Memory SQL Database
40 min · hard
hard

Design an in-memory SQL database that supports multiple tables with rows and columns, a query parser for SELECT statements, and indexing for fast lookups.

Given Info
  • Tables contain multiple Rows; each Row contains multiple Columns with typed values.
  • The system must support concurrent read and write operations on tables.
  • Query parser should parse simple SELECT queries with WHERE clauses on columns.
  • Indexes should be maintained for columns to speed up query filtering.
  • The design should allow adding new column types and query operations without modifying existing classes.
📋
Guided Steps
1/5
Step 1
Design Table, Row, and Column Classes
Define classes for Table, Row, and Column capturing their relationships and state. Decide how to represent column data types.
💡 Hint
Use composition for Table->Row and Row->Column relationships. Use enum for column data types to ensure type safety.
Key Decision
Use composition for Table contains List<Row> and Row contains Map<String, Column>. Use enum ColumnType to represent data types, preventing runtime string typos.
Interviewer Expectation
Mid: Names composition relationships clearly. Senior: Explains why enum ColumnType prevents runtime bugs compared to String and how composition lifecycle ensures Rows cannot exist without Table.
⚠️Common Wrong Answer
Using String for column data types leads to runtime typo bugs and no compile-time exhaustive checks.
Step 2
Implement Query Parser for SELECT Statements
Design a QueryParser class to parse SELECT queries with WHERE clauses into an internal representation.
💡 Hint
Use an abstract syntax tree (AST) with classes representing expressions. Use abstract classes for expressions with shared state.
Key Decision
Use abstract class Expression with subclasses for ColumnExpression, LiteralExpression, and BinaryExpression to hold parsing state; interface cannot hold state in Java.
Interviewer Expectation
Mid: Identifies use of abstract class for shared state in expressions. Senior: Explains why interface cannot hold parsing state and how abstract class enables code reuse.
⚠️Common Wrong Answer
Using interfaces for expressions forces duplicating parsing state in each implementation, violating DRY and causing maintenance issues.
Step 3
Design Indexing Mechanism for Fast Lookups
Design an Index class to maintain mappings from column values to rows for fast filtering.
💡 Hint
Use ConcurrentHashMap for thread-safe index updates. Use volatile for index reference to ensure visibility.
Key Decision
Use ConcurrentHashMap<Object, Set<Row>> inside Index for thread-safe concurrent updates. Mark index reference volatile to ensure visibility across threads.
Interviewer Expectation
Mid: Names ConcurrentHashMap for concurrency. Senior: Explains how volatile ensures visibility of index updates and prevents stale reads in concurrent queries.
⚠️Common Wrong Answer
Using HashMap without synchronization causes race conditions leading to corrupted index state and inconsistent query results.
Step 4
Ensure Thread-Safe Table Operations
Design thread-safe methods for inserting and querying rows in Table.
💡 Hint
Use synchronized methods or locks to atomically update rows and indexes. Avoid coarse locking to maintain concurrency.
Key Decision
Use public synchronized boolean insertRow(Row row) to atomically add row and update indexes. Use volatile for indexes to ensure visibility. Avoid deadlocks by locking in consistent order.
Interviewer Expectation
Mid: Names synchronized for atomic insertRow. Senior: Traces thread interleaving where Thread 1 inserts row and updates index, Thread 2 reads index; volatile ensures Thread 2 sees updated index state.
⚠️Common Wrong Answer
Not synchronizing insertRow leads to race conditions where multiple threads corrupt rows list or indexes causing lost updates.
Step 5
Design for Extensibility of Column Types and Query Operations
Design the system to allow adding new column data types and query operations without modifying existing classes.
💡 Hint
Use abstract classes and interfaces with default methods. Apply Open-Closed Principle using inheritance and polymorphism.
Key Decision
Use abstract class Column with abstract method Object getValue(). New column types extend Column. Use interface QueryOperation with default methods for extensibility.
Interviewer Expectation
Mid: Identifies Open-Closed Principle application. Senior: Explains why abstract class Column is needed for shared state and behavior, interface alone cannot hold state in Java.
⚠️Common Wrong Answer
Using concrete classes for all column types forces modifying existing code to add new types, violating Open-Closed Principle.
🔌
API Design Challenge
Design a clean and extensible API for clients to create tables, insert rows, and execute SELECT queries with WHERE filters.
Hints
  • Provide methods to create tables with specified column schemas.
  • Allow insertion of rows with type-checked column values.
  • Support query execution returning matching rows efficiently using indexes.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Composition relationships with lifecycle ownership between Table, Row, and Column
  • Use of enum for ColumnType to ensure type safety
  • Abstract class Expression for query parsing AST nodes with shared state
  • ConcurrentHashMap and volatile for thread-safe indexing
  • Synchronized methods for atomic row insertion
  • Open-Closed Principle applied for extensibility
Good to Have - 30%
  • Detailed thread interleaving explanation for concurrency correctness
  • Use of Map<String, Column> in Row for efficient column access
  • Default methods in interfaces for query operation extensibility
  • Avoidance of deadlocks by consistent locking order
Bonus - 10%
  • Support for multiple query types beyond SELECT
  • Support for composite indexes
  • Use of Java 8+ features like Streams for query execution
Anti-patterns to Avoid
Using String for column types leads to runtime typo bugs and no compile-time checks, causing unexpected failures during query execution.
Using HashMap without synchronization causes race conditions corrupting index state, leading to inconsistent query results and data corruption.
Using interfaces alone for Expression nodes forces duplicating parsing state violating DRY, increasing maintenance burden and bugs.
Not synchronizing insertRow leads to lost updates and inconsistent table state due to concurrent modifications.
Concrete classes for all column types force modifying existing code violating Open-Closed Principle, reducing extensibility and increasing risk of bugs.
✅
Model Answer
▼ Reveal

The design uses composition to model Table containing Rows and Rows containing Columns, enforcing lifecycle ownership. Column types are represented by an enum to ensure type safety. Query parsing uses an abstract class Expression to hold parsing state and enable code reuse. Indexing uses ConcurrentHashMap with volatile references to ensure thread-safe updates and visibility. Table operations like insertRow are synchronized to prevent race conditions. The design applies the Open-Closed Principle by using abstract classes and interfaces to allow extensibility without modifying existing code.

Key Decisions
  • Use composition for Table->Row and Row->Column to enforce lifecycle ownership
  • Use enum ColumnType to prevent runtime string typos and enable exhaustive checks
  • Use abstract class Expression to hold parsing state in query AST nodes
  • Use ConcurrentHashMap and volatile for thread-safe indexing and visibility
  • Synchronize insertRow method to atomically update rows and indexes
  • Apply Open-Closed Principle with abstract Column class and QueryOperation interface for extensibility
  • Use composition for Table->Row and Row->Column relationships to enforce lifecycle ownership; Rows cannot exist without Table.
  • Use enum ColumnType to represent column data types, preventing runtime string typos and enabling exhaustive switch statements.
  • Use abstract class Expression for query AST nodes to hold parsing state; interfaces cannot hold instance fields in Java.
  • Use ConcurrentHashMap in Index for thread-safe concurrent updates to index mappings.
  • Mark index references volatile to ensure visibility of updates across threads.
  • Use synchronized methods in Table for atomic insertRow operations to prevent race conditions.
  • Apply Open-Closed Principle by using abstract class Column and interface QueryOperation for extensibility without modifying existing code.
  • Avoid coarse locking by synchronizing only critical sections to maintain concurrency performance.
  • Trace thread interleavings to demonstrate how volatile and synchronized prevent stale reads and lost updates.
  • Use Map<String, Column> in Row for fast column lookup by name.

Practice

(1/5)
1. In designing the traffic light system, should Vehicle be an abstract class or an interface, considering vehicles have state like speed and direction? Why?
easy
A. Vehicle should be an interface because it only defines behavior without state
B. Vehicle should be an interface with default methods to hold state
C. Vehicle should be an abstract class to encapsulate shared state and behavior
D. Vehicle should be a final class to prevent subclassing and ensure immutability

Solution

  1. Step 1: Analyze state vs behavior requirements

    Vehicles have shared state (speed, direction) and behavior; interfaces cannot hold instance state, so interface alone is insufficient.

  2. Step 2: Abstract class encapsulates shared state and common methods

    Abstract class allows shared fields and partial implementation, enabling subclasses to extend and customize behavior.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful base class -> abstract class, not interface [check]
Hint: Stateful base class -> abstract class, stateless -> interface [check]
Common Mistakes:
2. In designing a Vehicle abstraction for a parking system, should Vehicle be an abstract class or an interface if it needs to hold state like licensePlate and provide default behavior for getSize()? Why?
easy
A. Abstract class, because it can hold shared state and provide default method implementations.
B. Interface, because it allows multiple inheritance and enforces method contracts without state.
C. Interface, because Java 8+ interfaces can have default methods and fields for state.
D. Abstract class, because it forces all subclasses to implement all methods explicitly.

Solution

  1. Step 1: Analyze state and behavior requirements

    Vehicle needs to hold state (licensePlate) and provide default behavior (getSize), which interfaces cannot hold as fields.

  2. Step 2: Choose abstraction supporting state and default behavior

    Abstract classes support instance variables and method implementations; interfaces cannot hold instance state.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Abstract class supports state and default behavior -> correct choice [check]
Hint: State needs abstract class; interfaces can't hold instance fields [check]
Common Mistakes:
3. To add a WeekendFeeStrategy for weekend bookings in the Airline Reservation System, which minimal change respects SOLID principles?
medium
A. Create a new WeekendFeeStrategy class implementing FeeStrategy and inject it without changing existing classes.
B. Add a boolean flag isWeekend to the Booking class and handle fees there.
C. Modify the existing FeeCalculator class to add weekend fee logic inside the calculate method.
D. Extend the FeeCalculator class with a subclass that overrides fee calculation for weekends.

Solution

  1. Step 1: Identify SOLID principle involved

    The Open-Closed Principle (OCP) requires that existing classes remain unchanged when adding new behavior.

  2. Step 2: Evaluate options for OCP compliance

    Add a boolean flag isWeekend to the Booking class and handle fees there. adds a flag and handles fees in Booking, violating SRP and mixing concerns. Create a new WeekendFeeStrategy class implementing FeeStrategy and inject it without changing existing classes. cleanly adds a new strategy class without modifying existing code, respecting OCP and DIP.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    New FeeStrategy class -> no existing class modification -> OCP respected [check]
Hint: New strategy class -> no existing code change -> OCP [check]
Common Mistakes:
4. In the OrderBook class, the placeOrder() method checks if the order slot is available and then books it. Without synchronization on placeOrder(), which exact sequence of thread interleaving causes double-booking of the same slot?
medium
A. Thread 1 reads slot as occupied, Thread 2 reads slot as free, both proceed to book.
B. Thread 1 checks slot availability -> free, context switch before booking; Thread 2 checks slot availability -> free, both book same slot.
C. Thread 1 books slot, Thread 2 waits for lock and then books the same slot after release.
D. Thread 1 and Thread 2 both crash before booking, leaving slot unbooked.

Solution

  1. Step 1: Identify the check-then-act race condition

    Without synchronization, Thread 1 reads slot as free but is preempted before booking; Thread 2 also reads free and proceeds to book.

  2. Step 2: Why this causes double-booking

    Both threads believe the slot is free and book it concurrently, causing inconsistent state and double-booking.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Check-then-act gap without lock -> double-booking [check]
Hint: Check slot free -> context switch -> both book same slot [check]
Common Mistakes:
5. You need to add support for ElectricCar and ChargingSpot in the existing parking system using the command pattern. What is the minimum change to the current design to support this without modifying existing classes?
hard
A. Create a new ElectricCarCommand class that extends existing commands and override methods to handle charging spots
B. Modify Vehicle class to add isElectric flag and add logic in existing commands to handle charging spots
C. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar extends Vehicle, and update SpotCompatibility.COMPATIBILITY_MAP accordingly
D. Add charging logic inside existing ParkingLot class and modify commands to check for electric cars

Solution

  1. Step 1: Identify extensibility requirements

    Adding new vehicle and spot types without modifying existing classes enforces OCP and avoids class explosion.

  2. Step 2: Evaluate options for minimal invasive change

    Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar extends Vehicle, and update SpotCompatibility.COMPATIBILITY_MAP accordingly adds new enum values and new class, updating compatibility map without changing existing classes. Options B, C, D modify existing classes or add complex logic violating OCP.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    New enums and class added, existing classes unchanged [check]
Hint: Add enums and classes, avoid modifying existing code [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard