Diverse Product Recommendations
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.
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:
m consecutive products in the final recommendation list come from the same category (stream).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.k recommendations cannot be generated (e.g., due to insufficient products or the m constraint making further picks impossible), return all available recommendations.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:
k (or fewer, if not enough available) product IDs in the merged, diverse recommendation list.productStreams may be empty. Your solution should handle this gracefully.k: If the total number of available products (considering m constraint) is less than k, return all available products.m value: m will always be at least 1.Examples
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).
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.
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
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)productStreams[i] are unique and sorted in ascending order.k, non-array productStreams).m consecutive category constraint across all edge cases.Loading editor...