Answer Policy Violation Log Queries
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Answer Policy Violation Log Queries
Implement `answer_violation_queries(logs, queries)`. Each log record is `[post_id, policy, timestamp]`, with all three fields encoded as strings. `timestamp` is a nonnegative decimal integer, and `logs` is sorted by nondecreasing timestamp.
Each query is one of the following string lists:
- `["UNIQUE_BY_POLICY", policy]`: return the number of distinct post IDs that ever violated `policy`.
- `["POLICIES_BY_POST", post_id]`: return the distinct policies violated by the post, sorted lexicographically and joined with commas; return the empty string if there are none.
- `["UNIQUE_AT", timestamp]`: return the number of distinct post IDs with a violation exactly at that timestamp.
- `["UNIQUE_RANGE", start, end]`: return the number of distinct post IDs with at least one violation in the inclusive timestamp range.
- `["COUNT_POLICY_RANGE", policy, start, end]`: return the number of log records for `policy` in the inclusive range. Identical duplicate records count separately for this operation.
Return one string answer per query, in query order. Count answers use base-10 notation. Range inputs always satisfy `start <= end`.
## Function Contract
`answer_violation_queries(logs: list[list[str]], queries: list[list[str]]) -> list[str]`
## Constraints
- `0 <= len(logs), len(queries) <= 200000`
- Post IDs and policy names are nonempty printable ASCII strings without commas.
- `0 <= timestamp <= 10^18`
- Logs may contain repeated post-policy-timestamp records.
## Examples
### Example 1
```text
Input:
logs = [
["1", "spam", "10"],
["1", "abuse", "10"],
["2", "spam", "12"],
["2", "spam", "12"],
["3", "copyright", "20"]
]
queries = [
["UNIQUE_BY_POLICY", "spam"],
["POLICIES_BY_POST", "1"],
["UNIQUE_AT", "12"],
["UNIQUE_RANGE", "10", "12"],
["COUNT_POLICY_RANGE", "spam", "10", "12"]
]
Output: ["2", "abuse,spam", "1", "2", "3"]
```
Duplicate spam records for post `2` count once in unique-post queries and twice in the final record-count query.
### Example 2
```text
Input:
logs = [["p1", "a", "5"], ["p2", "b", "7"]]
queries = [
["UNIQUE_RANGE", "7", "7"],
["COUNT_POLICY_RANGE", "a", "6", "9"],
["POLICIES_BY_POST", "missing"]
]
Output: ["1", "0", ""]
```
The range endpoints are inclusive, and absent matches produce zero or the empty policy string as appropriate.
Quick Answer: Answer five deterministic query types over a timestamp-sorted policy violation log, including distinct-post and raw-record counts. The prompt fixes inclusive ranges, duplicate behavior, policy ordering, empty results, timestamp width, and query-order output for a later four-language console implementation.
Implement answer_violation_queries(logs, queries). Each timestamp-sorted log is [post_id, policy, timestamp], with all fields encoded as strings. Return one string per query in input order. UNIQUE_BY_POLICY returns the number of distinct post IDs that ever violated the named policy. POLICIES_BY_POST returns that post's distinct policies in lexicographic order joined by commas, or the empty string. UNIQUE_AT returns the number of distinct post IDs appearing at the exact timestamp. UNIQUE_RANGE returns the number of distinct post IDs with at least one record in the inclusive range. COUNT_POLICY_RANGE returns the number of records for the named policy in the inclusive range, counting identical duplicate records separately. Count results use base-10 notation.
Constraints
- 0 <= logs.length, queries.length <= 200,000
- Every log is [post_id, policy, timestamp] and logs are sorted by nondecreasing numeric timestamp.
- Post IDs and policy names are nonempty printable ASCII strings without commas.
- 0 <= timestamp <= 10^18
- Every range satisfies start <= end and includes both endpoints.
- Logs may contain repeated post-policy-timestamp records.
- UNIQUE queries count distinct post IDs; COUNT_POLICY_RANGE counts records, including duplicates.
Examples
Input: ([['1', 'spam', '10'], ['1', 'abuse', '10'], ['2', 'spam', '12'], ['2', 'spam', '12'], ['3', 'copyright', '20']], [['UNIQUE_BY_POLICY', 'spam'], ['POLICIES_BY_POST', '1'], ['UNIQUE_AT', '12'], ['UNIQUE_RANGE', '10', '12'], ['COUNT_POLICY_RANGE', 'spam', '10', '12']])
Expected Output: ['2', 'abuse,spam', '1', '2', '3']
Explanation: The first source example distinguishes distinct-post counts from duplicate record counts.
Input: ([['p1', 'a', '5'], ['p2', 'b', '7']], [['UNIQUE_RANGE', '7', '7'], ['COUNT_POLICY_RANGE', 'a', '6', '9'], ['POLICIES_BY_POST', 'missing']])
Expected Output: ['1', '0', '']
Explanation: The second source example checks inclusive endpoints and absent matches.
Hints
- Precompute the direct set-valued indexes and keep each policy's timestamps sorted.
- For many arbitrary distinct-value range queries, sweep right endpoints while tracking each post's latest occurrence in a Fenwick tree.