Quick Overview

Implement rolling summaries over arrival-ordered transcript events. After each event, report the maximum transcript length and number of distinct users within the latest fixed-size event window, handling duplicates and inputs of up to 200,000 records.

Summarize Transcript Events in a Sliding Window

Company: Sesame Ai

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

# Summarize Transcript Events in a Sliding Window Implement `transcript_window_summaries(events, window_size)`. `events` is an arrival-ordered list of `(user_id, transcript)` pairs. After ingesting each event, return a summary for the most recent `window_size` events, or all events seen so far if fewer have arrived. Each summary is `(maximum_transcript_length, unique_user_count)`. Transcript length is Python's `len(transcript)`. If the input list is empty, return an empty list. Duplicate users and duplicate transcript strings are allowed. ## Constraints - `1 <= window_size <= 200,000` - `0 <= len(events) <= 200,000` - `user_id` and `transcript` are strings. - The total number of transcript characters is at most 2,000,000. - The output must contain one summary per input event. ## Example With a window size of three, the fourth summary covers events two through four. Its first component is the largest transcript length in those three events, while its second component counts distinct user IDs in that same window. ## Candidate clarifications Confirm that the window is based on event count rather than elapsed time, that the newest event is included, and that a user's repeated events count once toward the distinct-user total.

Quick Answer: Implement rolling summaries over arrival-ordered transcript events. After each event, report the maximum transcript length and number of distinct users within the latest fixed-size event window, handling duplicates and inputs of up to 200,000 records.

Implement transcript_window_summaries(user_ids, transcripts, window_size). Inputs are parallel arrival-ordered ASCII string arrays. After each event, summarize the newest window_size events, or all events so far, as [maximum_transcript_length, unique_user_count]. Return one summary per event.

Constraints

  • user_ids and transcripts have equal length up to 200,000.
  • 1 <= window_size <= 200,000
  • Total transcript length is at most 2,000,000 ASCII characters.

Examples

Input: ([], [], 3)

Expected Output: []

Explanation: No events produce no summaries.

Input: (["u"], ["hi"], 1)

Expected Output: [[2, 1]]

Explanation: One event determines both metrics.

Hints

  1. Use a frequency map for users in the current window.
  2. A decreasing deque of event indices maintains the maximum length.

Loading coding console...