← Roku Interview Insights

Roku·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Roku coding screen for a software engineer role. One problem, pretty focused, they wanted clean logic and a discussion of tests afterward.

Questions Asked (1)

Q1

Given a stream of ads where each ad has a topic and a company, filter the stream so that only ads with a topic and company not seen in any previously accepted ad are returned. Solve it in O(N) time.

Algorithms & Data Structures
Author's notes

The core logic clicked pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints, then propose using two hash sets to track seen topics and companies. Iterate through the stream, accepting an ad only if both its topic and company are new, and update the sets accordingly. This yields O(N) time and O(N) space.

Pro tip: Mention that the solution can be extended to handle multiple attributes or weighted filtering, and discuss trade-offs between memory usage and latency in a streaming context.

1. Clarify Requirements

Ask about stream characteristics (infinite, rate), definition of 'seen', and whether ads can have multiple topics/companies. Confirm O(N) time and acceptable space complexity.

2. Choose Data Structures

Select hash sets for O(1) average-time lookups and insertions to track seen topics and companies. Consider memory implications for large streams.

3. Design Algorithm

Iterate through each ad: if topic not in seenTopics and company not in seenCompanies, accept the ad and add both to their respective sets. Otherwise, filter it out.

4. Analyze Complexity

Explain that each ad is processed once with O(1) set operations, resulting in O(N) time. Space is O(U) where U is the number of unique topics and companies.

5. Discuss Edge Cases and Optimizations

Address empty stream, duplicate ads, memory limits, and potential use of Bloom filters or distributed sets for scalability.

Key Points to Mention

  • Use of hash sets for O(1) membership checks
  • Two separate sets for topics and companies to enforce both conditions
  • Time complexity O(N) and space complexity O(N) in worst case
  • Handling of streaming data and potential memory constraints
  • Edge cases: empty stream, ads with missing fields, repeated ads
  • Possible optimizations: Bloom filters for approximate filtering, or partitioning for distributed processing

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