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
▶
Class Trace
Step 1/4
Column abstract class

Column is an abstract class holding state (name, type) and synchronized getters, showing shared state and behavior.

🎯 Tests whether candidate understands abstract class is chosen over interface because Column holds instance state (fields) which interfaces cannot hold in Java.
public abstract class Column {
    private final String name;
    private final String type;
    public Column(String name, String type) {
        this.name = name;
        this.type = type;
    }
    public synchronized String getName() { return name; }
    public synchronized String getType() { return type; }
}
Table composition with Columns and Rows

Table composes Columns and Rows with strong lifecycle ownership (composition), managing them internally with synchronized methods.

🎯 Tests if candidate knows composition means Table controls lifecycle of Columns and Rows, and synchronized methods ensure thread-safe mutation of internal lists.
public class Table {
    private final List<Column> columns = new ArrayList<>();
    private final List<Row> rows = new ArrayList<>();
    public synchronized void addRow(Row row) { rows.add(row); }
    public synchronized List<Row> getRows() { return new ArrayList<>(rows); }
}
Index interface and HashIndex realization

Index is an interface defining add and search methods; HashIndex implements Index, showing interface realization for extensibility (OCP).

🎯 Tests whether candidate understands interface is used here to allow multiple indexing strategies without modifying Table, enforcing Open-Closed Principle.
public interface Index {
    void add(Row row);
    List<Row> search(Object key);
}
public class HashIndex implements Index {
    private final Map<Object, List<Row>> indexMap = new HashMap<>();
    public void add(Row row) { /* implementation */ }
    public List<Row> search(Object key) { /* implementation */ return null; }
}
QueryParser association with Query hierarchy

QueryParser associates with Query and its subclass SelectQuery, showing parsing responsibility separated from query execution.

🎯 Tests if candidate recognizes association means QueryParser does not own Query lifecycle, and inheritance models query types with polymorphic execute method.
public class QueryParser {
    public Query parse(String sql) {
        // parse and return SelectQuery or other Query subclass
        return new SelectQuery();
    }
}
public abstract class Query {
    public abstract List<Row> execute();
}
public class SelectQuery extends Query {
    private Table table;
    private List<Column> columns;
    public synchronized List<Row> execute() {
        // execute select logic
        return null;
    }
}
📐
Class Diagram
Class Diagram
       +----------------+
       |   <<Abstract>> |
       |     Column     |
       +----------------+
       | -name: String  |
       | -type: String  |
       +----------------+
       | +getName():String [sync] |
       | +getType():String [sync] |
       +----------------+
              ▲
              │
       +----------------+
       |      Row       |
       +----------------+
       | -values: Map<Col,Object> |
       +----------------+
       | +getValue(Col):Object [sync] |
       | +setValue(Col,Object):void [sync] |
       +----------------+
              ▲
              │
       +----------------+
       |     Table      |
       +----------------+
       | -cols: List<Col> ◆ |
       | -rows: List<Row> ◆ |
       | -index: Index      |
       +----------------+
       | +addRow(Row):void [sync] |
       | +getRows():List<Row> [sync] |
       +----------------+
              │
              │ association
              │
       +----------------+
       |    <<Interface>>|
       |      Index      |
       +----------------+
       | +add(Row):void  |
       | +search(Object):List<Row> |
       +----------------+
              ▲
              │ realization
       +----------------+
       |    HashIndex   |
       +----------------+
       | -indexMap: Map<Object,List<Row>> |
       +----------------+
       | +add(Row):void  |
       | +search(Object):List<Row> |
       +----------------+
              ▲
              │ association
       +----------------+
       |   QueryParser  |
       +----------------+
       | +parse(String):Query |
       +----------------+
              ▲
              │ inheritance
       +----------------+
       |    Query       |
       +----------------+
       | +execute():List<Row> |
       +----------------+
              ▲
              │ inheritance
       +----------------+
       |  SelectQuery   |
       +----------------+
       | -table: Table  |
       | -cols: List<Col> |
       +----------------+
       | +execute():List<Row> [sync] |
       +----------------+
Design Rationale

This class diagram illustrates key Java design decisions for an in-memory SQL database. Column is an abstract class because it holds state (name, type) and synchronized methods to ensure thread-safe access, which interfaces cannot provide. Table composes Columns and Rows, enforcing strong lifecycle ownership and uses synchronized methods to protect concurrent modifications. The Index interface enables multiple indexing strategies, such as HashIndex, following the Open-Closed Principle by allowing extension without modification. QueryParser associates with the Query hierarchy, separating parsing from execution and using inheritance to model different query types. These decisions leverage Java-specific constructs like abstract classes for shared state, synchronized methods for concurrency, and interfaces for extensibility.

Primary Focus

✓ Abstract class vs Interface + Composition lifecycle + Interface realization + Indexing strategy

Practice

(1/5)
1. In designing the Airline Reservation System, should the Seat entity be modeled as an abstract class or an interface, and why?
easy
A. Abstract class, because seats share common state like seat number and class, and behavior like availability checks.
B. Interface, because it allows multiple inheritance and flexible seat type combinations.
C. Interface, because seats only define behavior without any shared state or implementation.
D. Abstract class, because interfaces cannot enforce method signatures for seat operations.

Solution

  1. Step 1: Analyze seat characteristics

    Seats have shared state (seat number, class) and common behavior (availability, booking), which suggests code reuse.

  2. Step 2: Abstract class vs interface

    Abstract class allows shared state and default behavior implementation, while interface cannot hold state and only defines method signatures.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Shared state + behavior -> abstract class [check]
Hint: Shared state needs abstract class, interfaces lack fields [check]
Common Mistakes:
2. A class SecureImageProxy controls access to RealImage by checking user permissions before loading the image data lazily. Which design pattern is this an example of, and why is it the correct choice here?
easy
A. Proxy pattern, because it controls access and delays expensive object creation until needed.
B. Decorator pattern, because it adds responsibilities dynamically without changing the original object.
C. Adapter pattern, because it converts the interface of RealImage to a different one.
D. Facade pattern, because it provides a simplified interface to a complex subsystem.

Solution

  1. Step 1: Identify the role of SecureImageProxy

    This class controls access to RealImage and delays loading until necessary, matching Proxy's intent.

  2. Step 2: Eliminate other patterns

    Decorator adds behavior without access control; Adapter changes interface; Facade simplifies interface but doesn't control access or lazy load.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Proxy controls access and lazy loads expensive objects [check]
Hint: Proxy controls access and lazy loads objects [check]
Common Mistakes:
3. In a parking system, parkVehicle() checks if a spot is available and then marks it occupied. Without synchronized, which exact thread interleaving causes double-booking?
medium
A. Thread 1 marks spot occupied, Thread 2 waits until spot is free, then parks
B. Thread 1 checks isAvailable() -> true, context switch before marking occupied; Thread 2 checks isAvailable() -> true, both mark occupied
C. Thread 1 parks vehicle, Thread 2 parks vehicle after Thread 1 completes
D. Thread 1 and Thread 2 both wait on a lock, preventing double-booking

Solution

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

    Without synchronization, Thread 1 reads spot as available but is preempted before marking it occupied. Thread 2 also reads available and proceeds to mark occupied.

  2. Step 2: Confirm double-booking scenario

    Both threads believe the spot is free and mark it occupied, causing double-booking due to the race between check and set.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Check-then-act gap without synchronization -> double-booking [check]
Hint: Check-then-act without lock -> race condition double-booking [check]
Common Mistakes:
4. You need to add support for ElectricCar and ChargingSpot in the existing parking system using Decorator pattern. What is the minimum change to support this without modifying existing classes and avoiding class explosion?
hard
A. Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar extending Vehicle, and update SpotCompatibility.COMPATIBILITY_MAP accordingly.
B. Modify Vehicle and Spot classes to include electric-specific fields and logic.
C. Create separate parallel class hierarchy for electric vehicles and spots, duplicating existing logic.
D. Add boolean isElectric flag to Vehicle and Spot and handle logic with conditionals.

Solution

  1. Step 1: Identify extensibility requirements

    Adding ElectricCar and ChargingSpot should not modify existing classes to respect OCP and avoid class explosion.

  2. Step 2: Evaluate options for minimal change

    Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar extending Vehicle, and update SpotCompatibility.COMPATIBILITY_MAP accordingly. adds new enum values and a subclass, updating compatibility map without changing existing classes, adhering to OCP. Modify Vehicle and Spot classes to include electric-specific fields and logic. modifies existing classes, violating OCP. Create separate parallel class hierarchy for electric vehicles and spots, duplicating existing logic. duplicates logic, causing class explosion. Add boolean isElectric flag to Vehicle and Spot and handle logic with conditionals. adds flags and conditionals, increasing complexity and violating SRP.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    New enums and subclass added; existing classes unchanged [check]
Hint: Add enums and subclass; avoid modifying existing classes [check]
Common Mistakes:
5. The messaging system needs to support ElectricCar users who require ChargingSpot delivery locations. What is the minimum change to the current design to support this without modifying existing classes?
hard
A. Modify Vehicle and Spot classes to add electric-specific fields and methods for charging compatibility.
B. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally.
C. Create a new ElectricCar class and ChargingSpot class, then modify existing delivery logic to handle them.
D. Add a boolean isElectric field to Vehicle and a chargingAvailable field to Spot, updating logic accordingly.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and subclasses allows extension without changing existing class code, preserving OCP.

  2. Step 2: Understand how to update compatibility externally

    Updating SpotCompatibility.COMPATIBILITY_MAP externally supports new types without modifying existing logic inside classes.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Extend enums + subclasses + external map update -> minimal change [check]
Hint: Extend enums and subclasses, update compatibility map externally [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