Design a predicate structure and filter records with comparison, AND and OR

You are given a list of data items and a predicate. The task has two parts: design the data structure that represents a predicate, and implement `filter(data, predicate) -> filtered_data`, which returns the items for which the predicate holds. Predicates must support the comparisons greater-than (`>`) and less-than (`<`) and must combine them with `AND` and `OR`. The source does not say what an item looks like. The example below assumes that each item is a record of named fields and that each comparison tests one field against a constant; confirm that reading with the interviewer. ```python data = [ {"id": 1, "score": 85, "age": 30}, {"id": 2, "score": 40, "age": 25}, {"id": 3, "score": 60, "age": 70}, {"id": 4, "score": 95, "age": 45}, ] # predicate: (score > 50 AND age < 40) OR age > 65 filter(data, predicate) # -> the records with id 1 and id 3, in input order ``` ### Clarifying Questions - What is a data item: a plain value such as a number, or a record with named fields? If records, can a field be missing or nested? - Which value types can be compared (numbers only, strings, timestamps), and what should happen when a field's type does not match the constant? - Is every comparison a field against a constant, or can two fields be compared with each other? - Can `AND` and `OR` nest to any depth, and do they take exactly two operands or any number? - Must a predicate be serializable, for example sent from a UI or stored, or does it only live in memory? - Should the result keep the input order, and should it be a new list or a lazy sequence? - Will more operators be added later, such as equality or `NOT`? ### Part 1 — Design the predicate data structure Define how a predicate is represented so that comparisons and the two logical operators combine to any depth, and so that new operators can be added later without rewriting `filter`. ```hint Leaves and inner nodes Draw the example predicate as a tree. Decide which kinds of nodes it contains, what each kind must store, and which kind can contain other predicates. ``` #### What This Part Should Cover - A recursive structure of comparison leaves and logical nodes, with the fields each one holds - Where the evaluation logic lives, and what adding a new operator or node type requires - Validation when a predicate is built (unknown operator, empty `AND` or `OR`), and optionally a serializable form ### Part 2 — Implement `filter(data, predicate)` Implement `filter`, returning the items that satisfy the predicate in their original order, and handle the edge cases you clarified. ```hint Decide one item at a time Write the check that decides one item against one predicate node, then think about what it does at each kind of node and when it can stop early. ``` #### What This Part Should Cover - Correct recursive evaluation with early exit, preserving the input order - A missing-field and type-mismatch policy, applied consistently - The cost in terms of the number of items and the size of the predicate, and the tests you would write ### What a Strong Answer Covers - Pins down what an item is and what missing fields and mismatched types mean before writing code - A tree representation in which `AND` and `OR` hold child predicates, rather than a flat list of conditions or an ad hoc string - A clean separation between the predicate structure and the filtering, with an easy path to new operators - Readable code with tests covering nesting, empty data, boundary values and missing fields - A stated cost for filtering, and how evaluation order affects it ### Follow-up Questions - Add `NOT` and equality. What changes, and does anything go wrong for records with missing fields? - Users type predicates as strings such as `score > 50 AND (age < 40 OR age > 65)`. How do you turn them into your structure, including operator precedence? - The data has millions of records and the same predicate runs many times. How would you make filtering faster? - Predicates arrive as JSON through an API. How do you validate them and protect the service from huge or deeply nested predicates?