Finding Minimum Distinct Ids

Finding Minimum Distinct Ids

Morgan Stanley Interview questions  

Given an array of items, an i-th index element denotes the item id’s and given a number m, the task is to remove m elements such that there should be minimum distinct id’s left.Print the number of distinct id’s.

Input:
The first line of the input contains a single integer T, denoting the number of test cases. Then Ttest case follows, the three lines of the input, the first line contains N, denoting number of elements in an array,second line contains N elements/ids, and third line contains the number M.

Output:
For each test case, print the minimum number of distinct ids.

Constraints:
1<=T<=100
1<=N<=100
1<=arr[i]<=10^6
1<=M<=100

Example:
Input:
2
6
2 2 1 3 3 3
3
8
2 4 1 5 3 5 1 3
2
Output:
1
3

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.Map.Entry;

public class MinimumDistinct {

 private static final Scanner scanner = new Scanner(System.in);
 private static ArrayList<Integer> output = new ArrayList<Integer>();
 
 public static void main(String[] args) {
  
  int t = scanner.nextInt();
  scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  
  for (int i = 0; i < t; i++) {
   int n = scanner.nextInt();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   String array = scanner.nextLine();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   int arr[] = Arrays.stream(array.split(" ")).mapToInt(Integer::parseInt).toArray();
   int m = scanner.nextInt();
   scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

   getMinimumDistinct(n, arr, m);
  }
  
  for (int ids : output) {
   System.out.println(ids);
  }
 }
 
 /*
  * Convert array to map and get the distinct count
  */
 private static void getMinimumDistinct(int n, int arr[], int m) {
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for (int i : arr) {
   if(map.containsKey(i)) {
    map.put(i, (map.get(i)+1));
   }else {
    map.put(i, 1);
   }
  }
  sortMapAndGetDistinct(map , m);
  
 }
 
 /*
  * Sort the map based on value and remove the least numbers of ids for m times
  */
 private static void sortMapAndGetDistinct(HashMap<Integer, Integer> map, int m) {
  Set<Entry<Integer, Integer>> set = map.entrySet();
        List<Entry<Integer, Integer>> list = new ArrayList<Entry<Integer, Integer>>(set);
        Collections.sort( list, new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare( Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2 ) {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } ); 
        for(Map.Entry<Integer, Integer> entry:list){
           if(m > 0 && entry.getValue() <= m) {
            map.remove(entry.getKey());
            m = m-entry.getValue();
           }
         }
        output.add(map.size());
 }
}

INPUT:

2
6
2 2 1 3 3 3
3
8
2 4 1 5 3 5 1 3
2

OUTPUT:

1
3