Implement an In-Memory Query Engine

Problem Statement

You are tasked with building a lightweight, in-memory query engine. The engine stores structured records (dictionaries) and supports filtering rows using a query language that supports comparison operators, membership checks, and nested logical combinations (AND, OR, NOT).

Implement the InMemoryQueryEngine class with the following methods:

class InMemoryQueryEngine:
    def __init__(self):
        pass

    def insert(self, record: dict) -> None:
        """Inserts a single dictionary record into the engine."""
        pass

    def query(self, condition: dict) -> list[dict]:
        """Returns all inserted records that satisfy the given filter condition."""
        pass

Query Syntax

A condition dictionary can either be a field predicate or a logical predicate:

1. Field Predicate: { "field_name": { "": } } Supported operators:

   • "$eq": Equal to value.
   • "$gt": Strictly greater than value.
   • "$lt": Strictly less than value.
   • "$in": Value must be an element in the provided list.
   • "$nin": Value must not be an element in the provided list.

2. Logical Predicate:

   • { "$and": [condition1, condition2, ...] }: All child conditions must be True.
   • { "$or": [condition1, condition2, ...] }: At least one child condition must be True.
   • { "$not": condition }: Inverts the result of the child condition.

If condition is an empty dictionary {}, return all records.

Field Handling & Types

• Record keys are strings. Values may be integers, floats, strings, or None.
• If a field referenced in a comparison does not exist in a record, treat its value as None.
• For "$gt" and "$lt", if the record value is None or if types are incomparable (e.g., comparing an integer to a string), the condition evaluates to False.
• Preserved order: Return records in the order they were inserted.

Examples

Example 1

engine = InMemoryQueryEngine()
engine.insert({"id": 1, "name": "Alice", "age": 30, "status": "ACTIVE"})
engine.insert({"id": 2, "name": "Bob", "age": 24, "status": "PENDING"})
engine.insert({"id": 3, "name": "Charlie", "age": 35, "status": "ACTIVE"})

q = {
    "$and": [
        {"status": {"$eq": "ACTIVE"}},
        {"age": {"$gt": 25}}
    ]
}
print(engine.query(q))
# Output: 
# [
#     {"id": 1, "name": "Alice", "age": 30, "status": "ACTIVE"},
#     {"id": 3, "name": "Charlie", "age": 35, "status": "ACTIVE"}
# ]

Example 2

q2 = {
    "$or": [
        {"status": {"$in": ["PENDING", "ARCHIVED"]}},
        {"name": {"$eq": "Charlie"}}
    ]
}
print(engine.query(q2))
# Output:
# [
#     {"id": 2, "name": "Bob", "age": 24, "status": "PENDING"},
#     {"id": 3, "name": "Charlie", "age": 35, "status": "ACTIVE"}
# ]

Constraints

• Up to 10,000 records inserted.
• Up to 5,000 query calls.
• Maximum depth of nested logical operators is 10.
• Field names and string values contain alphanumeric characters only.