Interview Question & Answers – Migratory Birds Count – 11

Question

You have been asked to help study the population of birds migrating across the continent. Each type of bird you are interested in will be identified by an integer value. Each time a particular kind of bird is spotted, its id number will be added to your array of sightings. You would like to be able to find out which type of bird is most common given a list of sightings. Your task is to print the type number of that bird and if two or more types of birds are equally common, choose the type with the smallest ID number.

For example, assume your bird sightings are of types arr=[1, 1, 2, 2, 3]. There are two each of types and , and one sighting of type . Pick the lower of the two types seen twice: type 1.

You can download the problem statement from here.

Solution

We first need a hashmap to save the count of each migratory birds. Then we take the max value of has set. If there are more than one key with same value, get the Min Key from the Hash Set.

 static int migratoryBirds(List<Integer> arr) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < arr.size(); i++) {
        int count = 0;
        if (map.containsKey(arr.get(i))) {
            count = map.get(arr.get(i));
        }
        map.put(arr.get(i), ++count);
    }

    int maxValue = Collections.max(map.values());
    int minKey = 0; 
    int curKey = 0;
    for (Map.Entry me : map.entrySet()) {
        if ((int) me.getValue() == maxValue) {
            curKey = (int) me.getKey();
            if ((int) me.getKey() < minKey || minKey == 0) {
                minKey = curKey;
            }
        }
    }
    return minKey;
}

You can checkout the previous Interview Question here.