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 Snapchat.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snapchat during technical interviews.

Find top co-purchased products | Snapchat Coding Question

Quick Overview

This question evaluates algorithmic problem-solving and data engineering skills, focusing on computing and ranking co-occurrence frequencies, choosing efficient data structures for pairwise counts, and contrasting offline batch implementation with streaming updates.

Find top co-purchased products

Company: Snapchat

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You receive purchase logs where each order is represented as an integer array of product IDs bought together in a single transaction. Implement a function top_k_related(product_id, k= 10) that returns the k products that most frequently co-occur with the given product_id across all orders. Break ties by smaller product ID. Discuss data structures to support streaming updates (orders arriving continuously), memory considerations for very large product ID spaces, and the time/space complexity of building and querying the co-occurrence counts. Provide code for the offline batch case and outline an approach for the streaming case.

Quick Answer: This question evaluates algorithmic problem-solving and data engineering skills, focusing on computing and ranking co-occurrence frequencies, choosing efficient data structures for pairwise counts, and contrasting offline batch implementation with streaming updates.

You receive purchase logs where each order is an integer array of product IDs bought together in a single transaction. Implement `topKRelated(orders, productId, k)` that returns the `k` products that most frequently co-occur with `productId` across all orders. Rules: - A product co-occurs with `productId` in an order only if both appear in that order. Count at most one co-occurrence per order even if a product ID is listed multiple times in the same order (treat each order as a set). - `productId` itself is never included in the result. - Rank by descending co-occurrence count. Break ties by smaller product ID (ascending). - Return at most `k` product IDs, in ranked order. If fewer than `k` products co-occur, return all of them. Example: orders = [[1,2,3],[1,2,4],[1,3],[2,5]], productId = 1, k = 2. Product 2 co-occurs with 1 in 2 orders, product 3 in 2 orders, product 4 in 1 order. Counts: {2:2, 3:2, 4:1}. Tie between 2 and 3 broken by smaller ID, so ranking is [2, 3, 4]; top 2 -> [2, 3].

Constraints

1 <= number of orders <= 10^5
0 <= products per order <= 10^3
Product IDs are non-negative integers and may span a very large ID space
1 <= k <= 10^4
A product ID may appear multiple times within a single order; count it at most once per order

Examples

Input: ([[1, 2, 3], [1, 2, 4], [1, 3], [2, 5]], 1, 2)

Expected Output: [2, 3]

Explanation: Counts co-occurring with 1: {2:2, 3:2, 4:1}. Tie between 2 and 3 broken by smaller ID; top 2 -> [2, 3].

Input: ([[1, 2, 2, 3], [1, 2], [1, 3, 3]], 1, 10)

Expected Output: [2, 3]

Explanation: Duplicates within an order count once: order 1 contributes {2,3}, order 2 {2}, order 3 {3}. Counts {2:2, 3:2}; tie broken by smaller ID -> [2, 3].

Input: ([[10, 20], [10, 30], [10, 20], [10, 30], [10, 40]], 10, 1)

Expected Output: [20]

Explanation: Counts {20:2, 30:2, 40:1}. k=1, tie between 20 and 30 broken by smaller ID -> [20].

Input: ([[5, 6, 7], [8, 9]], 1, 3)

Expected Output: []

Explanation: Product 1 never appears in any order, so no co-occurrences -> [].

Input: ([], 1, 5)

Expected Output: []

Explanation: Edge case: no orders at all -> [].

Input: ([[1, 2], [1, 3], [1, 4]], 1, 5)

Expected Output: [2, 3, 4]

Explanation: All co-occur once: {2:1, 3:1, 4:1}; k=5 exceeds the 3 available, return all sorted by ascending ID.

Input: ([[1, 7], [1, 7], [1, 3], [1, 3], [1, 9]], 1, 2)

Expected Output: [3, 7]

Explanation: Counts {7:2, 3:2, 9:1}. Tie between 3 and 7 broken by smaller ID -> [3, 7].

Hints

Treat each order as a set so duplicate IDs in one transaction are not double-counted.
Only orders that actually contain productId contribute to the co-occurrence counts.
Use a hash map from product ID to count; you never need to materialize the full product ID space.
Rank with a comparator that sorts by descending count then ascending product ID, then take the first k. For huge result sets a size-k heap with the same ordering avoids fully sorting U items.
Streaming extension: on each arriving order containing productId, increment counts incrementally; the same map answers point queries. For very large ID spaces, bound memory with count-min sketch / heavy-hitters (Space-Saving) to approximate top-k.

Quick Overview