Katkat
Back

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

CoreweaveSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Design a data structure for predicates that combine greater-than and less-than comparisons with AND and OR, then implement filter(data, predicate) to return the matching items. Tests recursive structure design, extensibility to new operators, evaluation with early exit, and handling of missing fields and type mismatches.

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.

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.

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.

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

Hints

Hint 1

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.

Hint 2

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.

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?