Implement and explain `evaluate(predicate, document) -> bool` for a serialized predicate tree. Leaf predicates are `EQ(field, value)` and `GT(field, value)`. Internal predicates are `AND(children...)` and `OR(children...)`, and trees may be nested arbitrarily. A document is a mapping from field names to scalar values. Define behavior for missing fields, incompatible types, empty `AND` or `OR`, malformed nodes, and excessive nesting. Show pseudocode or code and representative tests. ### Constraints & Assumptions - `GT` is valid only when both operands are numeric. - Use short-circuit evaluation. - Missing fields do not compare equal to an explicit `null` value. ### Clarifying Questions to Ask - Should malformed predicates return false or a typed error? - Are nested field paths supported? - What maximum tree depth is safe? ```hint Validate node shape before recursion Each operator has a distinct arity and required fields; do not let missing keys turn into accidental false results. ``` ### What a Strong Answer Covers - A recursive or iterative evaluator with precise operator semantics. - Short-circuiting, type checks, missing-versus-null behavior, and malformed-input errors. - Complexity in the number and depth of visited nodes plus tests for nested combinations. ### Follow-up Questions - How would you add `NOT` and `IN`? - How would you return an explanation trace? - How would you protect the service from an adversarially deep expression?