FastPrepFastPrep
Problem Brief

Find Most Frequently Purchased Products

OA

The manager of a grocery store tagGrocery wishes to determine which products are most popular with his customers (i.e. which products they purchase most frequently). The manager selects N customers who purchase a shopping bag of items containing M products, each labeled with a productID. By analyzing these M products, the manager wishes to find the productIDs of the distinct products that get purchased most frequently by at least K(given) customers.

Write an algorithm to help the manager find the productIDs of the products that are most frequently purchased by the K customers.

Input

  • The first line of the input consists of two space-separated integers - tag_row, tag_col, representing the number of customers (N), the number of products in the shopping bag of each customer (M).
  • The next N lines consist of M space-separated integers - tag[0], tag[1], ......., tag[M-1], representing the productIDs of the products contained in the shopping bag of each customer.
  • The last line consists of an integer- K, input representing number of K customers who are chosen by the manager (K).

    • Output

    Print space-separated integers representing the lexicographically sorted productIDs of the products that are most frequently purchased by the K customers.

    Constraints

    1 ≤ tag_row ≤ 10^3
    1 ≤ tag_col ≤ 10^3
    1 ≤ K input ≤ tag_row
    0 ≤ tag[0], tag[1], ......., tag[N-1] ≤ 10^9

    1Example 1

    Input
    tag = [[1, 2, 3, 2], [2, 3, 4, 8], [8, 3, 11, 12], [2, 3, 6, 8]], K = 3
    Output
    [2, 3, 8]
    Explanation
    The products with ProductIDs 2, 3 and 8 are purchased by at least K customers. So, the output is [2 3 8].
    public int[] findMostFrequentlyPurchasedProducts(int[][] tag, int K) {
  // write your code here
}
    Input

    tag

    [[1, 2, 3, 2], [2, 3, 4, 8], [8, 3, 11, 12], [2, 3, 6, 8]]

    K

    3

    Output

    [2, 3, 8]

    Sign in to submit your solution.