Quick Overview

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

Implement an In-Memory Database

Company: Two Sigma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

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. 2. `insert into <table_name> ( <v1> <v2> ... <vN> )` - Insert one row into the table. - All stored values are integers. 3. `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.

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

You are given a list of tokenized SQL-like queries. Implement a tiny in-memory database that executes the queries in order. Supported commands: 1. CREATE TABLE table_name ( col1 col2 col3 ... ) 2. INSERT INTO table_name ( value1 value2 value3 ... ) 3. SELECT FROM table_name WHERE ( field1 op1 value1 AND field2 op2 value2 AND ... ) Rules: - All stored values are integers. - A SELECT query returns full rows, in the original insertion order. - Only the AND operator is supported between conditions. - Supported comparison operators are: =, !=, <, <=, >, >=. - If a CREATE or INSERT query is invalid, ignore it and continue. - If a SELECT query is invalid, or references a missing table/column, its result should be an empty list. - Creating a table with an existing name should be ignored. - Inserting into a missing table, using the wrong number of values, or providing a non-integer value should be ignored. Return the results of all SELECT queries, in the order they appear.

Constraints

  • 0 <= len(queries) <= 10^4
  • The total number of inserted rows across all tables is at most 10^5
  • Table and column names are strings without spaces
  • Only the operators '=', '!=', '<', '<=', '>', '>=' appear in valid WHERE clauses
  • All valid integer values fit in 32-bit signed integer range

Examples

Input: ([["CREATE", "TABLE", "students", "(", "id", "age", "score", ")"], ["INSERT", "INTO", "students", "(", "1", "20", "90", ")"], ["INSERT", "INTO", "students", "(", "2", "19", "95", ")"], ["INSERT", "INTO", "students", "(", "3", "20", "88", ")"], ["SELECT", "FROM", "students", "WHERE", "(", "age", "=", "20", "AND", "score", ">", "88", ")"], ["SELECT", "FROM", "students", "WHERE", "(", "age", "=", "20", "AND", "score", ">=", "88", ")"]],)

Expected Output: [[[1, 20, 90]], [[1, 20, 90], [3, 20, 88]]]

Explanation: The first SELECT matches only the row with score > 88. The second matches both rows where age is 20 and score is at least 88.

Input: ([["CREATE", "TABLE", "t", "(", "a", "b", ")"], ["INSERT", "INTO", "t", "(", "5", "6", ")"], ["INSERT", "INTO", "missing", "(", "1", "2", ")"], ["SELECT", "FROM", "t", "WHERE", "(", "a", "=", "5", "AND", "b", "=", "6", ")"], ["SELECT", "FROM", "t", "WHERE", "(", "c", "=", "1", ")"]],)

Expected Output: [[[5, 6]], []]

Explanation: The insert into a missing table is ignored. The second SELECT references a missing column, so it returns an empty list.

Hints

  1. Store each table as both a list of rows and a mapping from column name to column index.
  2. Parse the WHERE clause in chunks of 3 tokens: field, operator, value, with 'AND' separating conditions.

Loading coding console...