Quick Overview

This question evaluates proficiency in data structures, in-memory indexing and query design, algorithmic time/space complexity analysis, and reasoning about state management for dynamic event streams.

Design a violation log analyzer

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an append-only list of violation events as tuples (id: string, policy: string, date: ISO-8601 string). Build an in-memory "Violation Log Analyzer" that supports: 1) Given an id, return all policies that this id violated. 2) Given a policy, return all ids that violated this policy. 3) Given a date, return all ids that violated any policy on that exact date. Start with a straightforward approach, then: - Choose data structures and analyze the time/space of building the index and answering each query. - Optimize using appropriate inverted indexes (e.g., id→policies, policy→ids, date→ids). Show core APIs (build(log), query_by_id(id), query_by_policy(policy), query_by_date(date)) and pseudocode. - If there will be many repeated queries, propose caching or precomputation strategies (e.g., memoization of frequent queries, materialized sets), and discuss invalidation when new events arrive. - If the event list is sorted by date, explain how to use binary search to locate all events for a target date efficiently and return the corresponding ids; provide the algorithm and complexity. - Discuss trade-offs between query latency and memory, and how your design scales with number of events, distinct ids, and distinct policies.

Quick Answer: This question evaluates proficiency in data structures, in-memory indexing and query design, algorithmic time/space complexity analysis, and reasoning about state management for dynamic event streams.

Part 1: Straightforward Violation Log Analyzer

Implement a simple in-memory violation log analyzer without building indexes. For each query, scan the entire append-only event list and collect the matching unique values. Each event is represented as [id, policy, date]. Supported query types are ['id', value], ['policy', value], and ['date', value]. Return every query result as a lexicographically sorted list of unique strings.

Constraints

  • 0 <= len(events) <= 2000
  • 0 <= len(queries) <= 2000
  • Each event has exactly three strings: [id, policy, date].
  • Dates use a consistent ISO-8601 date format such as YYYY-MM-DD.
  • Duplicate events may appear, but output values must be unique.

Examples

Input: ([['alice', 'spam', '2024-01-01'], ['bob', 'fraud', '2024-01-01'], ['alice', 'fraud', '2024-01-02'], ['alice', 'spam', '2024-01-01']], [['id', 'alice'], ['policy', 'fraud'], ['date', '2024-01-01'], ['id', 'carol']])

Expected Output: [['fraud', 'spam'], ['alice', 'bob'], ['alice', 'bob'], []]

Explanation: alice violated fraud and spam; fraud was violated by alice and bob; two ids appear on 2024-01-01; carol has no events.

Input: ([], [['id', 'x'], ['policy', 'P1'], ['date', '2024-01-01']])

Expected Output: [[], [], []]

Explanation: The empty log produces empty results for every query type.

Hints

  1. For a direct solution, you do not need extra data structures beyond a set for the current query.
  2. Think about which field to compare for each query type, and which field should be added to the answer.

Part 2: Violation Log Analyzer with Inverted Indexes

Implement an optimized static violation log analyzer. Before answering queries, build three inverted indexes: id to policies, policy to ids, and date to ids. Then answer each query using the appropriate index. Each event is represented as [id, policy, date]. Return every query result as a lexicographically sorted list of unique strings.

Constraints

  • 0 <= len(events) <= 200000
  • 0 <= len(queries) <= 200000
  • Each event has exactly three strings: [id, policy, date].
  • Dates use a consistent ISO-8601 date format such as YYYY-MM-DD.
  • The total size of all returned lists is bounded by available memory.

Examples

Input: ([['u1', 'A', '2024-05-01'], ['u2', 'A', '2024-05-01'], ['u1', 'B', '2024-05-02'], ['u3', 'A', '2024-05-03']], [['policy', 'A'], ['id', 'u1'], ['date', '2024-05-01'], ['policy', 'Z']])

Expected Output: [['u1', 'u2', 'u3'], ['A', 'B'], ['u1', 'u2'], []]

Explanation: The policy, id, and date indexes answer the queries directly. Missing policy Z returns an empty list.

Input: ([], [['id', 'missing'], ['policy', 'missing'], ['date', '2024-01-01']])

Expected Output: [[], [], []]

Explanation: All indexes are empty.

Hints

  1. Build dictionaries whose values are sets so duplicates are removed automatically.
  2. After the index is built, each query should avoid scanning the entire event list.

Part 3: Cached Violation Log Analyzer with Append Invalidation

Implement a violation log analyzer that supports repeated queries and new appended events. Build materialized indexes for id, policy, and date. Additionally, cache sorted query results so repeated identical queries can be returned quickly. When a new event is appended, update the indexes and invalidate only cached answers affected by that event.

Constraints

  • 0 <= len(events) <= 200000
  • 0 <= len(operations) <= 200000
  • Each initial event and append operation contains exactly one id, one policy, and one date.
  • Dates use a consistent ISO-8601 date format such as YYYY-MM-DD.
  • Duplicate events may be appended; outputs must still contain unique values.

Examples

Input: ([['u1', 'P1', '2024-01-01'], ['u2', 'P1', '2024-01-01']], [['query_id', 'u1'], ['query_id', 'u1'], ['append', 'u1', 'P2', '2024-01-02'], ['query_id', 'u1'], ['query_policy', 'P2'], ['query_date', '2024-01-02']])

Expected Output: [['P1'], ['P1'], ['P1', 'P2'], ['u1'], ['u1']]

Explanation: The repeated first query can be cached. After appending a new event for u1, the cached query_id result for u1 must be invalidated.

Input: ([], [['query_id', 'x'], ['append', 'x', 'A', '2025-01-01'], ['query_id', 'x'], ['query_policy', 'A'], ['query_date', '2025-01-01']])

Expected Output: [[], ['A'], ['x'], ['x']]

Explanation: A missing id initially returns empty. After append, the affected id, policy, and date queries return the new data.

Hints

  1. Use sets in the indexes as the source of truth, and cache only the sorted list representation.
  2. An appended event with id x, policy p, and date d can only change cached answers for query_id x, query_policy p, and query_date d.

Part 4: Binary Search Date Lookup in a Sorted Violation Log

You are given a violation event list sorted in nondecreasing order by date. Implement efficient exact-date lookup using binary search. For each target date, find the contiguous range of events with that date and return the unique ids that violated any policy on that date.

Constraints

  • 0 <= len(events) <= 200000
  • 0 <= len(dates) <= 200000
  • events is sorted in nondecreasing order by the date field.
  • Dates use a consistent ISO-8601 date format such as YYYY-MM-DD, so lexicographic comparison matches chronological order.
  • Duplicate ids may appear multiple times on the same date, but each output list must contain unique ids.

Examples

Input: ([['u1', 'P1', '2024-01-01'], ['u2', 'P2', '2024-01-01'], ['u1', 'P3', '2024-01-02'], ['u3', 'P1', '2024-01-04']], ['2024-01-01', '2024-01-03', '2024-01-04'])

Expected Output: [['u1', 'u2'], [], ['u3']]

Explanation: Binary search locates the date ranges for the first and last queries. 2024-01-03 is absent.

Input: ([], ['2024-01-01'])

Expected Output: [[]]

Explanation: An empty sorted log has no ids for any date.

Hints

  1. Use one binary search to find the first event whose date is not less than the target.
  2. Use another binary search to find the first event whose date is greater than the target; the answer lies between those two positions.

Loading coding console...