CODEWITHSUNDEEP
algorithm
n179911
n179911

Reputation: 20331

Write algorithm to return top 2 elements in terms of frequency from a long list of elements

I was asked this question during interview. I was not able to solve this. I wonder if anyone has a good idea how to solve it:

If I have a long list of integers, return the integer which top 2 in terms of frequencies.

e.g. [1, 2, 3, 1, 4, 5, 6, 7, 8, 6, 1, 8, 8] returns [1,8]

Thank you.

Upvotes: 0

Views: 133

Answers (3)

AD.Net
AD.Net

Reputation: 13399

Loop through the list and create a max heap with the value and count.

There is definitely a challenge about how to keep track. Thinking of a quick solution (as often is the case in an interview), I'd probably keep a dictionary to keep track if I've created an object for any given int in the array/list and if so it's current index in the heap. If so, then I'll get that object, update it's counter and trickle up in the max heap.

I'll probably have a class that contains data, such as this:

public class MyData
    {
        private readonly int _key;

        public MyData(int key)
        {
            _key = key;
            Count = 0;
        }

        public int GetKey()
        {
            return _key;
        }
        public int Count { get; set; }
    }

I'll have a structure like this (where the tuple contains the object and it's index in the heap array (i'm going for the array implementation of the heap)

var elementsInHeap = new Dictionary<int, Tuple<MyData, int>>();

When looping through the input list, check if you have any entry in that dictionary for that int, if so get that value, get the object, increase the counter, and then do the trickle up in the heap. For the heap you can use the MyData object, when doing trickle up or down use the counter value. If not, create a new MyData object, have it trickle up int he max heap based on it's counter, when finished add it to the dictionary with it's index in the tuple.

Hope this helps, I'm sure there is a smarter solution out there. Hopefully someone will help us with that.

Upvotes: 3

user1935024
user1935024

Reputation:

If you know the range of numbers (max and min elements) you can use array and count frequencies in one loop through the array ,

you also can use heap-fast construction algorithm O(n) and just extract max 2 times,

or use hashing (if your are able to implement it during interview)

Upvotes: 0

skortzy
skortzy

Reputation: 169

I think the answers that suggest building a heap or sorting the array have O(n log n) complexity.

First build a hash map in which the keys are the (distinct) elements of the array and the values are their frequencies. This map can be easily built in O(n).

Then find the maximum and second maximum of the entries in the map. This can also be done easily in O(n) by iterating through the map entries only once. Even if you decide to iterate twice (find a maximum, remove it and find the next maximum), your complexity will still be O(n).

Upvotes: 1

Related Questions