Facebook Interview: K Most Frequent Elements - Whiteboard Thursday

Check out the detailed data structures and algorithms course at www.interviewa...
As always, don't forget to like, subscribe and share! I'll see you with a new video next week.

[@srinimurthy]

Your interviewer agrees too much with you :D

[@vijayputta7727]

dude too much

[@pemessh]

In most of your videos the interviewers voice is too low. Please provide her a mic too 😂

[@prateeksharma9321]

Lol

[@debagnikroy9450]

"Mmm hmmm,yeah and right" :P

[@hailinlin454]

correct me if I'm wrong, if the array size is large, and most numbers repeats, then the bucket array will be large with most elements empty. Spaces will likely be wasted.

[@SreeragNairisawesome]

so used a Linked List.

[@justfly1984]

for example in JavaScript sparse arrays are performance de-optimization. Please don't use sparse arrays.

[@prighwaitnaamee2193]

Alexey Lyahov please don't use JavaScript.

[@fengcunli5677]

Sreerag Nair You can’t use linked list as the buckets because you need random access one bucket by the frequency to put the element into that bucket.

[@tianyuli3015]

time complexity is still O(N) which is not bad

[@IrfanBaqui]

Thanks for watching, guys! Let me know what problems you'd like me to cover next!

[@smithabk1]

Irfan Baqui can you talk about the problem where you have to find triplets from an array that add up to a number ?

[@IrfanBaqui]

Hi Smita, that's called an n-sum problem. It's very similar to this one - kzbin.info/www/bejne/b16bfqeOpLugb8U

[@smithabk1]

Irfan Baqui that’s great! Thanks for the quick response!

[@romanahussain7190]

Can you cover system design questions too .. which covers oops , design principles ,scalability etc etc

[@IrfanBaqui]

Romana Hussain That's a good idea

[@interviewhub3408]

Hey Irfan, I liked the approach you have taken to solve this. Still, an improvement is to store the maximum frequency in a variable while creating the frequency array. Next, you know the size of bucket to allocate and iterate the bucket from end to return the results.

[@dephc0n1]

Not bad, you could also save the minimum value and attempt to chop the left side of the array too.

[@hiteshdave1826]

This code needs to be more optimized. Below is Swift optimized code. func occuranceOfMostFrequentElement(_ fromArray: Array,_ count: Int) -> Array? { var resultArray:Array = [] var hashMap:Dictionary = [Int: Int]() for digit in fromArray { if( hashMap.keys.contains(digit)) { let digitOccurance = hashMap[digit]! + 1 hashMap[digit] = digitOccurance if( digitOccurance >= count) { if !resultArray.contains(digit) { resultArray += [digit] } } } else { hashMap[digit] = 1 } } return resultArray }

[@sachinpaul2111]

A bit inefficient if you ask me. Till the HashMap , the problem will lose completeness if you remove anything. After that, you don't need a whole array to keep. You can just keep the most frequent guy. List mostFreqEles = new ArrayList(); int maxFreq = 0; for (int k : freqMap.keys()) { int currFreq = freqMap.get(k); //get current frequency if(currFreq > maxFreq) //if greater { mostFreqEles.clear(); //flush the existing list mostFreqeles.add(k); //add this key to the list maxFreq = currFreq; //set current frequency to max } else if(currFreq == maxFreq) //if equal { mostFreqEles.add(k)//just add to the list } } return mostFreqEles;

[@Existentialkev]

hmm I am not seeing how this would add more than one most frequent value.

[@Jo4nP4l4u]

Wouldn't a priority queue be fine for this? I mean, the priority is the times the element is repeated and you can just pop K times at the end to get all the results. the space would be linear, and the pop would be O(1). In addition, you wouldn't waste space as in the bucket array.

[@darkseed2k9]

That is a very good idea, but each pop() is O(log d), where d is the number of unique numbers in the array, not O(1). Remember that you also need to build the heap, which takes at least O(d). So the total complexity is O(d) + k*O(log d)

[@Dgsrgv]

Your solution is better than the given solution from the same question on leetcode (question #347). Keep up the good work! I like your detailed explanations

[@andriirubtsov5404]

Thank you so much for your hard work on these videos! They are really useful to many candidates. One concern that I have though is that in real life candidates do not know the problem in advance. You seem too confident to me, you solve problems too fast ))). I would like to see you struggle on problems you have not seen before ). Thanks!

[@brianschillaci7179]

these videos are great, really helping me prepare for interviews

[@pratyooshsharma3330]

If the variance was large between elements & space complexity of creating hashmap is a concern an alternate approach would be to sort the array in nlog(n) & then looping over sorted list. The complexity would come down to O(knlog(n)) though with that approach

[@r4dx]

O(n * logn) but O(1) memory sort(a); // nlogn int? current = None; int count = 0; Heap result = new Heap(k); // sorted by frequency desc, init-ed with k 0s for (int i = 0; i < a.length(); i++) { if (a[i] != current) { if (count > result.getMin()) { result.removeMin(); result.push(new HeapElement(a[i], count)); // logk but nlogn is still bigger than nlogk } count = 1; current = a[i]; continue; } count++; }

[@shiwanggupta8608]

Instead of using a bucket, you could have used Priority queue, then the time complexity would be O(k*logn)

[@AllTheFishAreDead]

Building the hashmap is still O(N) though so that dominates

[@chuckywang]

@Rakesh Adhikesavan But if each element occurs only once, your min heap would only consist of 1s. You would stop inserting once you reach size k?

[@Eeezus1914]

All he has to do is return the two highest counts out of the harsh map. Look up in hashmap is O(1) and O(N) worst case if there are collisions. I’m not in favor of his approach with the bucket situation tho but if it works it works i guess

[@csviraj]

If you are allowed to maintain an additional DS other than the HashMap , why not use an array where you add the element as soon as its frequency equals the stated frequency count, k=2 in your example and just return it once you are done iterating .

[@dannydjx]

Dude, this man is going serious with the look and feel. He's even using blue shirts for FB videos.

[@baranmano9791]

C# code below is to implement the same logic that your have explained using multi dimensional array. Would you like to comment on it? also please provide your code ... thanks using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace maxrepeatingelemtns { class Program { static void Main(string[] args) { int[] inputArr = { 7, 7, 5, 5, 6, 6, 6, 7 }; // find occurances for each number and store in a format [0.1]=7[0,1]=3 times int[][] output = findfreqOccurandStore(inputArr); //from the found list get top 2 output = max2(output); //this is to print elements of top 2 for (int count = 0; count < output.Length; count++) if (output[count] != null) for (int jCount = 0; jCount < output[count].Length; jCount++) Console.WriteLine("[" + count.ToString() + "], [" + jCount.ToString() + "]:" + output[count][jCount].ToString()); Console.ReadLine(); } private static int[][] max2(int[][] freqArr) { int[][] result = new int[2][]; if (freqArr[0][1] < freqArr[1][1]) { result[0] = new int[] { freqArr[1][0], freqArr[1][1] }; result[1] = new int[] { freqArr[0][0], freqArr[0][1] }; } else { result[0] = new int[] { freqArr[0][0], freqArr[0][1] }; result[1] = new int[] { freqArr[1][0], freqArr[1][1] }; } for (int count = 2; count < freqArr.Length; count++) { if (freqArr[count][1] > result[0][1]) { result[0][0] = freqArr[count][0]; result[0][1] = freqArr[count][1]; } else if (freqArr[count][1] > result[1][1]) { result[1][0] = freqArr[count][0]; result[1][1] = freqArr[count][1]; } } return result; } private static int[][] findfreqOccurandStore(int[] inputArr) { int[][] freqArr = new int[inputArr.Length][]; for (int occu = 0; occu < inputArr.Length; occu++) { int index = search(freqArr, inputArr[occu]); if (index == -1) freqArr[occu] = new int[] { inputArr[occu], 1 }; else { freqArr[index][1] = Convert.ToInt32(freqArr[index][1]) + 1; freqArr[occu] = new int[] { 0, 0 }; } } return freqArr; } private static int search(int[][] freqArr, int value) { for (int count = 0; count < freqArr.Length; count++) { if (freqArr[count] != null && value == freqArr[count][0]) { return count; } } return -1; } } }

[@stanislawpalka9015]

Non-optimal. Second part (Bucket) should be on heap.

[@vandameh.a2235]

from collections import Counter import operator def getRepeated(array,k): returnArray=[] dicc= Counter(array) sortedDicc= sorted(dicc.items(),key=operator.itemgetter(1),reverse=True) for i in range(0,k): returnArray.append(sortedDicc[i][0]) return returnArray

[@rajeshkumar_animuthu]

Solution without the bucket by checking the frequency map after updating it every time and updating it to -1 once it is added to result. function freqK(arr, k) { var freqMap = {}; var result = []; for (var i = arr.length - 1; i >= 0; i--) { if (!freqMap[arr[i]]) { freqMap[arr[i]] = 1; } else if (freqMap[arr[i]] == -1) { continue; } else { freqMap[arr[i]]++; } if (freqMap[arr[i]] >= k) { result.push(arr[i]); freqMap[arr[i]] = -1; } } return result; }

[@sahilpuri645]

Hi , great video and explanation ! but try to place the ads at the start if possible , and not in between the logic explanations. That breaks the flow and is very irritating sometimes.

[@ronaldmackee3401]

Ok, what about negative numbers, where do they go in the bucket array? If I run it with a test input like [1, 1000, MAX_INT] then you got space issues with the array bucket approach

[@vrushankdoshi7813]

How is the time complexity linear ? In the last for loop, you are iterating over the entire bucket and each array inside that cell 'k' times, it should be O(n*k), please correct me if I am wrong.

[@potterhead__5121]

Hi irfan! Great content there. I absolutely love your whiteboard videos. Especially how you communicate your ideas. Could you share some tips for communicating the ideas THAT effectively? Thanks in advance!

[@cesaredecal2230]

a little cringy to watch because of the constant mmm-s but helpful! thanks!

[@rahuljaiswal2372]

Bucket size should be maxFreq+1.

[@yavdhesh]

Aap kaafi acche shikshak ho, kaafi accha laga

[@JagjitBrawler]

What if you used a max heap (sorted by frequency), where the node contains a list of elements that have that frequency? Then for each k, you delete the max node and re-balance the tree (amortized O(logn)) Assuming this works, won’t it be more time and memory efficient?

[@JagjitBrawler]

This would require you to linearly iterate through the hash table and append values to the node of similar frequency (e.g. append 6 to the node with key 3)

[@pushpakantbehera7479]

You're awesome....😊😊😊

[@Garensonic]

I actually got this question in an interview a year ago. I solved it with a HashMap and a priority queue in Java which has O(nlogk) time. public List topKFrequent(int[] nums, int k) { HashMap counts = new HashMap(); for (int value: nums) { counts.put(value, counts.getOrDefault(value, 0) + 1); } PriorityQueue heap = new PriorityQueue((a, b) -> counts.get(a) - counts.get(b)); for (int key: counts.keySet()) { heap.add(key); if (heap.size() > k) { heap.poll(); } } List results = new ArrayList(); while (!heap.isEmpty()) { results.add(heap.poll()); } Collections.reverse(results); return results; }

[@priyankarrajgupta4198]

Hmm here is some good stuff going on :)

[@About_The_Journey]

irfan i really appreciate the technique how you represent those programing approach .Keep it up for us.You are doing great job.Can you make some videos on dynamic programing ? It will be very helpful for us also..:-)

[@sykn3z]

Thank you bro, keep the good work :P

[@IrfanBaqui]

Thanks for the support :)

[@bstrnx]

Great video! Very helpful :)

[@IrfanBaqui]

Glad you liked it, José :)

[@alapid718]

Very helpful!

[@wilsonkao17]

easy to understand but what if negative integers were allowed in the array?

[@dephc0n1]

I believe the hashmap should handle negative keys. There shouldn't be any negative frequency counts so we wouldn't attempt to index at a negative value in the bucket.

[@abhilashraipally5665]

How about using collections in JAVA. We can solve using the following 1. Create a frequency Hash MAP for each input element 2. Sort the map by value in descending order 3. Get the top k elements from the map

[@fahadahmad9881]

Sorting is at least O(nlogn). His solution right now is O(n).

[@bontkkdu5922]

How would you sort the HashMap using collections? I thought it was only applicable to lists.

[@abhilashraipally5665]

We can get the entry set from hashmap and create a custom comparator and sort it by value. Take a look at stackoverflow.com/a/13913206

[@bontkkdu5922]

Yes I am aware of that, I even used that before. But I was hoping for a cleaner solution :p It's really messy in my opinion. But thank you for you reply!

[@dabeermasood9309]

You could also just create a second Hash Map for frequencies:list of values pairing. Maintain the max count and just iterate from the max count to 0 and push to your answer until the total length of values is equal to k. Second hashmap size is also o(n) and time complexity will be o(n) at worst, but at best you avoid creating a second array with a fixed size of n. Helps a little bit.

[@zeruzeradam]

Please make your handwriting somewhat readable for next time! Thanks!

[@arjuns.3752]

We can sort the array and check if the adjecent elements are same. If same then inc. Frequency. If frequency is equal to k the print the element.

[@KeralaVibeShorts]

Content and presentation is so good! But unable to watch as the female voice really gets on the nerves!