Roku·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Roku SWE interview with a streaming/filtering problem that looks easy but has some gotchas worth thinking through. Pretty standard technical screen setup, one question, asked to walk through the solution and talk about testing.

Questions Asked (1)

Given a stream of ads where each ad has a topic and a company, filter the stream so that you only keep ads whose topic and company haven't appeared in any previously accepted ad. Solve it in O(N) time and be ready to discuss test cases.

Algorithms & Data Structures

Author's notes

Two sets, one for topics one for companies, check both before accepting and add to both after.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use two hash sets to track seen topics and seen companies, iterating through the stream once and accepting an ad only if both its topic and company are new. This achieves O(N) time and O(N) space. Be prepared to discuss edge cases like empty stream, null values, and duplicate ads.

Pro tip: Clarify whether the stream is infinite and if memory is a concern; if so, propose a probabilistic data structure like Bloom filter for space efficiency, but note the trade-off in accuracy.

1. Understand the problem

Restate the filtering condition: an ad is accepted only if its topic and company have not appeared in any previously accepted ad. Confirm that the stream is processed in order and that we need to output the filtered stream.

2. Choose data structures

Use two hash sets: one for seen topics and one for seen companies. Hash sets provide O(1) average-time lookups and insertions, ensuring overall O(N) time.

3. Design the algorithm

Iterate through each ad in the stream. For each ad, check if its topic is in the seen topics set or its company is in the seen companies set. If neither is present, accept the ad and add its topic and company to the respective sets.

4. Analyze complexity

Time complexity is O(N) because each ad is processed once with O(1) set operations. Space complexity is O(N) in the worst case, as we may store up to N topics and N companies.

5. Discuss test cases

Cover edge cases: empty stream, stream with all ads having unique topics and companies, stream with duplicates, ads with null or missing fields, and large streams to verify performance.

Key Points to Mention

Use of hash sets for O(1) lookups to achieve O(N) time complexity.
Space complexity is O(N) due to storing seen topics and companies.
Edge cases: empty stream, null values, duplicate ads, and ads with same topic but different company (or vice versa).
Order preservation: the filtered stream maintains the original order of accepted ads.
Potential memory optimization using Bloom filters for approximate filtering if memory is constrained.
Test cases should include both small and large inputs to validate correctness and performance.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.