Katkat
Back

Implement an In-Memory Database

Two SigmaSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates competence in implementing in-memory relational data structures, parsing tokenized database-like commands, and evaluating compound predicates with comparison operators.

Implement a simple in-memory relational database that processes a sequence of tokenized commands.

You are given commands: List[List[str]], where each command is already split into tokens. Process the commands in order and return the result of every select command.

Support the following operations:

  1. create table <table_name> ( <col1> <col2> ... <colN> )
  • Create a table with the given column names.
  1. insert into <table_name> ( <v1> <v2> ... <vN> )
  • Insert one row into the table.
  • All stored values are integers.
  1. select from <table_name> where ( <fieldA> <op1> <valueA> AND <fieldB> <op2> <valueB> )
  • Return all rows that satisfy both conditions.
  • Only AND needs to be supported.
  • Comparison operators may include =, >=, <=, >, and <.

Additional notes:

  • Column names are strings.
  • Rows should be returned in insertion order.
  • You may assume the token structure of each command is syntactically valid, but your implementation should handle invalid table names, invalid column names, or mismatched row lengths reasonably.
  • A reasonable return format for a select query is a list of matching rows, where each row is represented as a list of integers.

The main challenge is parsing the select ... where (...) clause and evaluating both predicates correctly.