How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Implement Event Filtering and Queue Routing

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

An upstream event pipeline continuously emits events as JSON strings. You need to implement an in-memory routing service that decides which downstream queues should receive each event. Implement an `EventRouter` with the following behavior: - `void subscribe(String queueName, String filterExpression)`: registers a queue with a filter expression. - `List<String> route(String eventJson)`: parses the incoming JSON event, evaluates all registered filters, and returns the names of every queue whose filter matches the event. Return queue names in subscription order. In a real system this method would send to queues, but for this exercise returning queue names is enough. Filter-expression requirements: - A filter compares JSON fields using dot paths, such as `type`, `region`, or `detail.userId`. - Support comparison operators: `==`, `!=`, `>`, `>=`, `<`, `<=`. - Support boolean operators: `AND`, `OR`, `NOT`, and parentheses. - Values may be quoted strings, numbers, booleans, or `null`. - Missing fields should be treated as `null`. - Use JSON type-aware comparison where possible; for example, numeric comparisons should only be applied to numbers. Example: ```text subscribe("usOrders", "type == \"order\" AND region == \"us\"") subscribe("largeOrders", "type == \"order\" AND amount >= 100") subscribe("errors", "detail.level == \"error\" OR type == \"failure\"") route("{\"type\":\"order\",\"region\":\"us\",\"amount\":125}") => ["usOrders", "largeOrders"] ``` You may assume a standard JSON parser/helper is available for converting the event string into a traversable JSON object. Focus on the service structure, filter parsing/evaluation, and routing behavior.

Quick Answer: This question evaluates parsing and evaluation of domain-specific filter expressions, JSON traversal and type-aware comparisons, boolean logic handling, and in-memory routing with subscription-order preservation.

An upstream event pipeline emits events as JSON strings. Implement an in-memory routing service that decides which subscribed downstream queues should receive each event. For this platform, implement solution(operations), which simulates an EventRouter. A subscribe operation registers a queue name with a filter expression. A route operation parses one event JSON string, evaluates all previously registered filters, and returns the queue names whose filters match, in subscription order. Filters compare JSON fields using dot paths such as type, region, or detail.userId. Supported comparison operators are ==, !=, >, >=, <, <=. Supported boolean operators are AND, OR, NOT, with parentheses. Precedence is NOT before AND before OR. Filter values may be quoted strings, numbers, booleans, or null. Missing fields are treated as null. Equality is JSON type-aware; ordering comparisons return false unless both sides are JSON numbers.

Constraints

0 <= len(operations) <= 200
queueName values are unique across subscribe operations
Each filterExpression is syntactically valid and has length at most 500
Event JSON strings are valid JSON objects with nested objects, strings, numbers, booleans, and null values
Dot paths contain object field names separated by '.', and array indexing is not required
Ordering operators >, >=, <, <= only match when both compared values are numbers; booleans are not considered numbers

Examples

Input: ([('subscribe', 'usOrders', 'type == "order" AND region == "us"'), ('subscribe', 'largeOrders', 'type == "order" AND amount >= 100'), ('subscribe', 'errors', 'detail.level == "error" OR type == "failure"'), ('route', '{"type":"order","region":"us","amount":125}')],)

Expected Output: [['usOrders', 'largeOrders']]

Explanation: The event is a US order with amount 125, so it matches the first two subscriptions. It has no detail.level and type is not failure, so errors does not match.

Input: ([],)

Expected Output: []

Explanation: There are no operations, so there are no route results.

Input: ([('subscribe', 'missingRegion', 'region == null'), ('subscribe', 'nonNullRegion', 'region != null'), ('route', '{"type":"order"}')],)

Expected Output: [['missingRegion']]

Explanation: The event has no region field, so region is treated as null. Therefore region == null matches, while region != null does not.

Input: ([('subscribe', 'urgentUs', '(type == "alert" OR detail.level == "error") AND region == "us"'), ('subscribe', 'activeUs', 'active == true AND region == "us"'), ('subscribe', 'notDebug', 'NOT detail.level == "debug"'), ('route', '{"type":"metric","detail":{"level":"debug"},"region":"us","active":true}'), ('route', '{"type":"metric","detail":{"level":"error"},"region":"us","active":false}')],)

Expected Output: [['activeUs'], ['urgentUs', 'notDebug']]

Explanation: The first event is active in the US but has debug level, so only activeUs matches. The second event has error level in the US and is not debug, so urgentUs and notDebug match.

Input: ([('subscribe', 'large', 'amount > 100'), ('subscribe', 'negative', 'amount < 0'), ('subscribe', 'stringAmount', 'amount == "125"'), ('subscribe', 'notHundred', 'amount != 100'), ('route', '{"amount":"125"}'), ('route', '{"amount":-5}'), ('route', '{"amount":125}')],)

Expected Output: [['stringAmount', 'notHundred'], ['negative', 'notHundred'], ['large', 'notHundred']]

Explanation: Ordering comparisons only apply to numeric JSON values. The string amount matches only the string equality and notHundred. The negative amount matches negative and notHundred. The numeric 125 matches large and notHundred.

Hints

Parse each filter expression once at subscription time into an expression tree. A recursive descent parser works well for handling NOT, AND, OR precedence and parentheses.
During routing, resolve each dot path against the parsed JSON object. If any path component is missing, return null for that field, then perform type-aware comparison.

Quick Overview

This question evaluates parsing and evaluation of domain-specific filter expressions, JSON traversal and type-aware comparisons, boolean logic handling, and in-memory routing with subscription-order preservation.