Katkat
Back

Implement an in-memory SQL-like table

ValonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a flexible, in-memory table structure that supports dynamic schema definition, data storage, and basic relational query operations.

Problem Statement

Design an in-memory Table class that functions as a lightweight relational store. The table should support arbitrary column names and types. You must implement the following core functionality:

  1. __init__(self, columns): Initializes the table with a list of column names.
  2. insert(self, row): Adds a row (provided as a dictionary mapping column names to values) to the table.
  3. query(self, select=None, where=None, order_by=None): Returns a list of rows that satisfy the criteria.

Query Parameters

  • select: A list of column names to return. If None, return all columns.
  • where: A dictionary representing an equality filter (e.g., {'age': 30}). Only rows matching all key-value pairs should be returned.
  • order_by: A tuple of (column_name, direction) where direction is 'asc' or 'desc'. If None, return in insertion order.

Constraints

  • Assume column names are strings and values are integers or strings.
  • Efficiency matters: repeated queries on large datasets should be performant.
  • Handle cases where a row might be missing a column (treat as None).

Example

t = Table(['name', 'age', 'city'])
t.insert({'name': 'Alice', 'age': 30, 'city': 'NY'})
t.insert({'name': 'Bob', 'age': 25, 'city': 'LA'})
t.insert({'name': 'Charlie', 'age': 30, 'city': 'SF'})

# Query
results = t.query(select=['name'], where={'age': 30}, order_by=('name', 'desc'))
# Returns: [{'name': 'Charlie'}, {'name': 'Alice'}]

Edge Cases

  • Empty table.
  • where clause with a column not in the table.
  • Sorting by a column that has None values.

Hints

Hint 1

Represent the table internally as a list of dictionaries to allow for easy row access.

Hint 2

For filtering, use a simple loop over the internal list to check against the 'where' criteria before applying projections.

Hint 3

For sorting, use Python's built-in `sort` or `sorted` function with a custom `key` lambda, accounting for the direction and potential `None` values.

Follow-up questions

  • How would you optimize the 'where' query if this table were to hold millions of rows (hint: consider indexing)?
  • How would you extend this design to support complex conditions, such as 'greater than' or 'not equal' filters?
  • If multiple threads are accessing this table simultaneously, what synchronization mechanisms would you add to ensure thread safety?