How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Two Sigma during technical interviews.

Implement an In-Memory Database | Two Sigma Coding Question

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.

Input: ([["CREATE", "TABLE", "nums", "(", "x", "y", ")"], ["INSERT", "INTO", "nums", "(", "-1", "-1", ")"], ["INSERT", "INTO", "nums", "(", "-1", "2", ")"], ["INSERT", "INTO", "nums", "(", "3", "-1", ")"], ["SELECT", "FROM", "nums", "WHERE", "(", "x", "=", "-1", ")"]],)

Expected Output: [[[-1, -1], [-1, 2]]]

Explanation: Negative integers are valid stored values. The SELECT returns every row whose x value is -1.

Input: ([["CREATE", "TABLE", "items", "(", "id", ")"], ["CREATE", "TABLE", "items", "(", "other", ")"], ["INSERT", "INTO", "items", "(", "abc", ")"], ["INSERT", "INTO", "items", "(", ")"], ["INSERT", "INTO", "items", "(", "7", ")"], ["SELECT", "FROM", "items", "WHERE", "(", "id", ">=", "7", ")"], ["SELECT", "FROM", "missing", "WHERE", "(", "id", "=", "7", ")"]],)

Expected Output: [[[7]], []]

Explanation: The duplicate CREATE is ignored. Invalid INSERT queries are ignored. Only the valid row [7] is stored, and selecting from a missing table returns an empty list.

Hints

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

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.