How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Roku.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Roku during technical interviews.

Implement ad filtering and concurrent cache

Quick Overview

This question evaluates algorithmic problem-solving and systems-programming skills by combining an ad candidate filtering task that tests data-structure selection, complexity analysis, and test-design thinking with a concurrent LRU cache task that tests implementation of a fixed-capacity data structure, thread-safety, and concurrency primitives.

Company: Roku

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Two coding tasks were described. 1. **Ad candidate filtering**: You are given a list of ad candidates. Each ad has `ad_id`, `company`, `topic`, and `score`. Return up to `k` ads in input order such that no selected ads share the same `company` or the same `topic`. Describe the time and space complexity, how you would optimize a naive solution, and what unit tests you would add. 2. **Concurrent eviction cache**: Implement a fixed-capacity key-value cache with least-recently-used eviction. Support `get(key)` and `put(key, value)` in average `O(1)` time. The cache will be accessed by multiple threads concurrently. Explain what makes your implementation thread-safe and what performance issues can appear if the design uses a single global lock under high throughput.

Quick Answer: This question evaluates algorithmic problem-solving and systems-programming skills by combining an ad candidate filtering task that tests data-structure selection, complexity analysis, and test-design thinking with a concurrent LRU cache task that tests implementation of a fixed-capacity data structure, thread-safety, and concurrency primitives.

Part 1: Ad Candidate Filtering

You are given a list of ad candidates in their original display order. Each ad is represented as a tuple (ad_id, company, topic, score). Select up to k ads while preserving input order such that no two selected ads share the same company or the same topic. Return the selected ad_id values in the order they were chosen. The score field is metadata only and does not change the required input-order selection rule.

Constraints

0 <= len(ads) <= 100000
0 <= k <= len(ads)
Each ad is a 4-tuple: (int, str, str, int|float)
ad_id values are unique

Examples

Input: ([(1, 'A', 'sports', 0.9), (2, 'B', 'music', 0.8), (3, 'A', 'tech', 0.95), (4, 'C', 'music', 0.7), (5, 'D', 'food', 0.6)], 3)

Expected Output: [1, 2, 5]

Explanation: Pick 1 and 2. Ad 3 conflicts on company A, ad 4 conflicts on topic music, and ad 5 is valid.

Input: ([], 2)

Expected Output: []

Explanation: Edge case: empty input.

Input: ([(7, 'X', 'travel', 0.5)], 0)

Expected Output: []

Explanation: Edge case: k is zero, so nothing can be selected.

Input: ([(10, 'Acme', 'news', 0.9), (11, 'Beta', 'news', 0.8), (12, 'Acme', 'sports', 0.7)], 5)

Expected Output: [10]

Explanation: Only the first ad can be selected; the others conflict by topic or company.

Input: ([(1, 'A', 'x', 0.1), (2, 'B', 'y', 0.2), (3, 'C', 'z', 0.3)], 2)

Expected Output: [1, 2]

Explanation: Stop once k ads have been selected.

Hints

You do not need to compare each ad against every selected ad. Think about what information can be stored in O(1)-lookup data structures.
Because the required order is the original input order, a greedy left-to-right scan is enough.

Part 2: Concurrent Eviction Cache

Implement a fixed-capacity least-recently-used cache. The cache supports two operations: put(key, value) and get(key). A get returns the stored value if the key exists, otherwise -1. When inserting a new key into a full cache, evict the least recently used key. A successful get or an update to an existing key makes that key the most recently used. Although the judge will provide a sequential list of operations, your design should use internal locking so that the cache methods would be safe if called by multiple threads concurrently.

Constraints

0 <= capacity <= 100000
0 <= len(operations) <= 200000
Keys and values are integers
Operations are valid and use only 'get' and 'put'

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [1, -1, -1, 3, 4]

Explanation: Standard LRU example with multiple evictions.

Input: (2, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])

Expected Output: [10, -1, 3]

Explanation: Updating key 1 makes it recent, so key 2 is evicted when key 3 is inserted.

Input: (0, [('put', 1, 1), ('get', 1), ('put', 2, 2), ('get', 2)])

Expected Output: [-1, -1]

Explanation: Edge case: zero-capacity cache stores nothing.

Input: (1, [('get', 5), ('put', 5, 7), ('get', 5), ('put', 6, 8), ('get', 5), ('get', 6)])

Expected Output: [-1, 7, -1, 8]

Explanation: Edge case with capacity 1 and eviction on each new key.

Hints

To achieve O(1) average time, combine a hash map for key lookup with a doubly linked list for recency order.
If methods must be thread-safe, updates to both the map and the linked list should be protected together so they cannot get out of sync.

Quick Overview