Frontend School

Diverse Product Recommendations

DSA
medium

Diverse Product Recommendations

Medium
Heap
Priority Queue
Algorithms

Overview

Meesho's product recommendation engine aims to provide a diverse and engaging shopping experience. When a user is browsing, we often have multiple streams of trending or relevant products, each corresponding to a specific category. To prevent monotony and ensure users discover a wide range of items, we need to merge these sorted product streams into a single list while enforcing a diversity constraint.

This problem challenges you to implement a core component of this system: generating a merged list of product recommendations that prioritizes overall relevance (lower product ID implies higher relevance) but limits consecutive products from the same category to ensure a balanced display.

What you need to do / Task

Implement a function getDiverseProductRecommendations that takes an array of sorted product streams, a target number of recommendations k, and a maximum consecutive count m for products from the same category. The function should return a list of k product IDs, adhering to the specified diversity constraint.

Specifically, your solution must:

  1. Merge products from multiple streams based on their product ID (smaller ID first).
  2. Ensure that no more than m consecutive products in the final recommendation list come from the same category (stream).
  3. If a category's m limit is reached, temporarily skip its next product and consider the next best available product from a different category. The skipped product becomes eligible again once a product from a different category has been picked.
  4. If k recommendations cannot be generated (e.g., due to insufficient products or the m constraint making further picks impossible), return all available recommendations.

Input & output

Function Signature:

function getDiverseProductRecommendations(productStreams: number[][], k: number, m: number): number[]

Parameters:

  • productStreams: An array of arrays of numbers. Each inner array represents a product category stream, sorted in ascending order of product IDs. Product IDs are unique across all streams.
  • k: A number representing the total count of product recommendations to generate.
  • m: A number representing the maximum number of consecutive products allowed from the same category (stream).

Return Value:

  • An array of numbers, representing the k (or fewer, if not enough available) product IDs in the merged, diverse recommendation list.

Clarifications

  • Empty Streams: Some productStreams may be empty. Your solution should handle this gracefully.
  • Total Products vs. k: If the total number of available products (considering m constraint) is less than k, return all available products.
  • Product IDs: Product IDs are positive integers. Lower ID implies higher relevance. If two products from different streams have the same ID, any tie-breaking is acceptable, but for this problem, assume IDs are unique across all streams.
  • m value: m will always be at least 1.

Examples

1

Example 1

Input:

productStreams = [[1, 5, 9], [2, 6, 10], [3, 7, 11]], k = 5, m = 2

Output:

[1,2,3,5,6]

Note:

No 'm' constraint is hit in this simple case. Products are picked in ascending order of ID: 1 (from stream 0), 2 (from stream 1), 3 (from stream 2), 5 (from stream 0), 6 (from stream 1).

2

Example 2

Input:

productStreams = [[1, 2, 7, 8], [3, 4, 9, 10], [5, 6, 11, 12]], k = 7, m = 2

Output:

[1,2,3,4,5,6,7]

Note:

1 (S0), 2 (S0). S0 is now throttled (2 consecutive, m=2). Next best is 3 (S1). Pick 3 (S1), 4 (S1). S1 is now throttled. Next best is 5 (S2). Pick 5 (S2), 6 (S2). S2 is now throttled. Next best is 7 (S0). Pick 7 (S0). Total 7 products.

3

Example 3

Input:

productStreams = [[10, 20, 30], [1, 2, 3], [100, 200]], k = 6, m = 1

Output:

[1,10,2,20,3,30]

Note:

With m=1, we can't pick two consecutive from the same stream. Picks alternate: 1 (S1), 10 (S0), 2 (S1), 20 (S0), 3 (S1), 30 (S0).

Constraints

Constraints & assumptions

  • 1 <= productStreams.length <= 100 (Number of categories)
  • 0 <= productStreams[i].length <= 1000 (Length of each product stream)
  • 1 <= productStreams[i][j] <= 10^9 (Product ID values)
  • 1 <= k <= 10^5 (Target number of recommendations)
  • 1 <= m <= k (Maximum consecutive products from same category)
  • All product IDs within each productStreams[i] are unique and sorted in ascending order.
  • Product IDs are unique across all streams.

Out of scope

  • Error handling for invalid input types or values (e.g., negative k, non-array productStreams).
  • Network latency or external API calls for fetching product data.

What interviewers evaluate

  • Correctness: Accurately merges products and strictly adheres to the m consecutive category constraint across all edge cases.
  • Efficiency: Achieves optimal time and space complexity, leveraging appropriate data structures like priority queues/heaps.
  • Code Quality: Writes clean, readable, and well-structured code with good variable names and comments where necessary.
  • Problem-Solving: Demonstrates a clear understanding of the problem and ability to adapt standard algorithms to fit specific constraints.

Loading editor...