Quick Overview

This question evaluates concepts in sliding-window algorithms, hash-based duplicate tracking, case-insensitive string handling, and the extension of batch solutions to streaming (online) inputs.

Find longest unique show window

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an array of show names (strings) representing a user's viewing history, return the start and end indices of a longest contiguous subarray that contains no repeated show names (case-insensitive). If multiple answers exist, return any one. Achieve O(n) time and O(min(n, m)) space where n is the length and m is the number of distinct shows. Follow-up: adapt your solution to a streaming input API that yields one show name at a time and must always be able to report the current longest unique-name window; describe data structures, update complexity, and memory bounds.

Quick Answer: This question evaluates concepts in sliding-window algorithms, hash-based duplicate tracking, case-insensitive string handling, and the extension of batch solutions to streaming (online) inputs.

Part 1: Longest Unique Show Window

You are given an array of show names representing a user's viewing history. Find the start and end indices of the longest contiguous subarray in which no show name appears more than once, treating names case-insensitively. For example, "Friends" and "friends" count as the same show. If multiple longest windows exist, return the one with the earliest start index. Indices are 0-based, and the end index is inclusive. If the input list is empty, return (-1, -1). Your solution should run in O(n) time.

Constraints

  • 0 <= len(shows) <= 200000
  • Each element of shows is a string
  • Comparison is case-insensitive
  • Use 0-based indexing
  • The end index in the answer is inclusive

Examples

Input: ["Friends", "Seinfeld", "The Office", "friends", "Lost"]

Expected Output: (1, 4)

Explanation: The longest case-insensitive unique window is ["Seinfeld", "The Office", "friends", "Lost"], from index 1 to 4.

Input: ["A", "B", "a", "b"]

Expected Output: (0, 1)

Explanation: Several longest windows have length 2: [0,1], [1,2], and [2,3]. Return the earliest start index.

Hints

  1. Try using a sliding window with two pointers.
  2. Store the most recent index of each normalized show name so you can move the left side of the window in O(1).

Part 2: Streaming Longest Unique Show Window Reports

A streaming API yields show names one at a time. After each new show arrives, you must be able to report the longest contiguous window seen so far whose show names are all distinct case-insensitively. For this coding task, you are given the full arrival order as a list. Simulate the stream and return the answer after each arrival. More precisely, after processing shows[0], return the best window in the prefix shows[0:1]. After processing shows[1], return the best window in shows[0:2], and so on. If multiple longest windows exist at a given step, keep the one with the earliest start index. Indices are 0-based, and the end index is inclusive. If the input list is empty, return an empty list. Your design should conceptually support O(1) average-time updates and O(1) reporting per new show.

Constraints

  • 0 <= len(shows) <= 200000
  • Each element of shows is a string
  • Comparison is case-insensitive
  • Use 0-based indexing
  • The end index in each reported tuple is inclusive

Examples

Input: ["A", "B", "a", "C"]

Expected Output: [(0, 0), (0, 1), (0, 1), (1, 3)]

Explanation: After the third show, the current unique suffix is [1,2], but the best-so-far window is still [0,1]. After the fourth show, [1,3] becomes the new best.

Input: ["Ted", "Dexter", "Office", "ted", "Lost"]

Expected Output: [(0, 0), (0, 1), (0, 2), (0, 2), (1, 4)]

Explanation: The repeat of "Ted" forces the current window to start at index 1, and adding "Lost" then creates a longer best window [1,4].

Hints

  1. You only need to know the current unique suffix ending at the newest item, plus the best window seen so far.
  2. A hash map from normalized show name to its latest index lets you update the left boundary quickly when a duplicate arrives.

Loading coding console...