Kth Largest Element in an Array

Рет қаралды 110,048

5 жыл бұрын

For business inquiries email partnerships@k2.codes SOCIAL
----------------------------------------------------------------------------------------------------------------
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / programeme
Follow me on GitHub: github.com/kdn251
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
MUSIC
----------------------------------------------------------------------------------------------------------------
A0000012.WAV by bsd.u - / a0000012wav Discord: bit.ly/K2-discord

Пікірлер: 186

@KevinNaughtonJr 5 жыл бұрын

What problem / topic should I cover next?

@eliwood58378 5 жыл бұрын

subsets II

@KevinNaughtonJr 5 жыл бұрын

I'll check it out thanks for the suggestion!

@hrishikeshkulkarni2856 5 жыл бұрын

Yes please make video on generating all substring, subsequences, permutations as well as those of given length (k given)... Helpful video as always!

@hrishikeshkulkarni2856 5 жыл бұрын

Also what should be my strategy for solving LeetCode problems? Can you suggest me on that?

@KevinNaughtonJr 5 жыл бұрын

I'll try to do some of those, thanks for the suggestion!

@jeanpaultorre8335 4 жыл бұрын

This is a perfect video that prepares you for right before your interviewer asks you "okay, good... now can you do better?"

@chiranjeevipippalla 3 жыл бұрын

Quick Select is one of the ways the interviewer might be looking for.

@theschoolofalgorithms 2 жыл бұрын

I recently went to an interview and the interviewer expected to write QuickSelect. Then I found out that in average QuickSelect run in time O(n).

@deliveringIdeas 2 жыл бұрын

@@theschoolofalgorithms thanks!

@TahirAndDanish 3 жыл бұрын

I beg to differ, the runtime is not O(N). You are right that we are simply inserting N elements to the heap, but under the hood inserting an element calls the heapify() method to move the newly added element to its correct position (in order to maintain the min/max heap integrity). Each insertion with its subsequent heapify call is O(logN). So we are more or less back to O(NlogN). Am I missing something?

@galanoth17 2 күн бұрын

The insertion/removal is O(lgK) not O(lgN) because the heap is only k elements.

@ashiqimran5961 4 жыл бұрын

Runtime should be O(nlogk)

@arulantony2137 4 жыл бұрын

using merge sort and get k index (leng-k)

@mercuriallabs9 4 жыл бұрын

Worst case is when k == n. Then it is similar to build a heap. Amortized time complexity for such a case is O(n).

@bz9031 3 жыл бұрын

@@mercuriallabs9 Why amortized complexity is O(n)? k is between 0 and n, and the mean is n/2, which is still in the order of n

@zerocool5673 3 жыл бұрын

@@Derek-np7ke K isn't a constant. we can only assume that K < n where n is the number of elements inside the array.

@SamuelEvans1991 2 жыл бұрын

@@Derek-np7ke k actually can increase and decrease in size so its not a constant

@venkateshTD 5 жыл бұрын

Like one the comments previously mentioned, this is n log(k) which I guess (if I am not wrong) is upper bounded by n log(n) since k could be at most n. And there is a O(n) algorithm for this problem which is called quick select algorithm.

@KevinNaughtonJr 5 жыл бұрын

Yep you're totally right and yeah I think technically what you mentioned about the upper bound being nlogn is correct as well!

@nerdydarkknight 4 жыл бұрын

If I'm not wrong the worst case complexity of quick select is O(n^2) with an average case of O(n).

@darshanprakash 4 жыл бұрын

@@nerdydarkknight yes, that's correct

@stablesort 4 жыл бұрын

@@nerdydarkknight There is a "median of medians" algorithm that technically avoids the worst case O(n^2) and runs in linear time. So the quick select algorithm can be made to run in linear time as well, even for the worst case.

@gdthegreat Жыл бұрын

@@stablesort can you explain please in more depth?

@ankitagarwal4914 4 жыл бұрын

That's really fantastic approach! . At first I was in confusion how Minheap play role here, then your explanation really made me think into power of Heaps.

@ajaywadhwa3398 4 жыл бұрын

Thank you so much Kevin For your explanations . It really helped me alot . Very Nice way of teaching.

@janmichaelaustria620 3 жыл бұрын

Great video kevin. Just to bring up something I think you might have misspoken. The runtime went from O(NlogN) down to (Nlogk), which is better if and only if k < N (which it is). And space went down from O(N) to O(k). Inserting into a heap is logN time, and since our heap is never bigger than K, this becomes a logK operation. We do this N times, so Nlogk.

@SA-ik4ot 4 жыл бұрын

Hi Kevin, thanks for the videos, you rock, and all these videos help me more than anything. Can you create a playlist with the hardest Google interview questions that we need to focus on? I will go to onsite interview next Thursday and I will let you know if I can crack it! Cheers mate.

@youngturtlebear5315 3 жыл бұрын

Thanks for the video Kevin! As a couple of others have mentioned, there is an O(n) algorithm, linear time selection or quick select. But I've only learned the algorithm on a theory level but struggle implementing the algorithm itself. As a hypothetical, if this question was asked during an interview, is it okay to give the heap solution instead of the other algorithm? If I don't think I can implement the algorithm within the time frame, should I even mention the O(n) algorithm?

@syedyaser8753 3 жыл бұрын

Initially I was wondering how min-heap can be used here but later you explained it very well. I think adding an additional check to insert only elements greater than the minimum element in the heap can avoid unnecessary insertion of the elements and can further improve the performance of this algo. It won't improve it asymptotically though.

@jayanthm2597 3 жыл бұрын

best part of your videos is that you keep everything short!!

@dhrubo619 5 жыл бұрын

Thanks for your videos, can you please do some problems on dynamic programming. That will help immensely

@gegao9066 3 жыл бұрын

Awesome video, but I believe (as others have mentioned) the build heap step is O(nlogk) instead of O(n). However, there is a O(n) buildHeap approach which always add to the end of the heap and percolate down. so the total for build heap this way will be: (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1) which is bound by the O(n). It's just Java's PriorityQueue's `add` interface does not guarantee this buildHeap implementation.

@thecuriousmaverick 5 жыл бұрын

Hi Kevin, I'm preparing for my Google on-site (APM role) right now, and your videos are super helpful! I would love to have a chat (via phone/video) with you if possible. :) A huge thanks to you again!

@KevinNaughtonJr 5 жыл бұрын

Hey Soundarya, yeah let's do it! Shoot me an email and let's find a time to talk! kdn251@nyu.edu

@blasttrash 5 жыл бұрын

hey did you get into Google?

@ALI53481 4 жыл бұрын

follow up lol

@gdthegreat Жыл бұрын

follow up in 2022, Kevin, How can I setup a call with you?

@kesav6285 5 жыл бұрын

Hey, can we use a priority queue and insert all elements to it and pop k-1 times ? Is it a bad solution?(c++)

@sushilojhafb 3 жыл бұрын

Is it ok to use PriorityQueue or Arrays.sort in actual interview? Would they expect us to implement heap from scratch?

@avae6310 3 жыл бұрын

Hi Kevin, Thank you for easy solving this problem and great explanation. I have an interview in google in some days if you give me some advices.

@duymap09 4 жыл бұрын

Hi Kevin, I'm your new fan from VietNam. Thanks for all your amazing video.

@mikhailameerally8588 4 жыл бұрын

2 Apple interviews coming up Tuesday/Wednesday. Would love to run a mock and get some advice before.

@youko3795 3 жыл бұрын

What is the result? Are you in company now?

@gdthegreat Жыл бұрын

thanks a lot for these videos, will definitely see you someday in NYC office or in case you visit India someday then let us know.

@trustaniket 4 жыл бұрын

i have my first round of google interview in first week of november. Please advice if doing your playlist of easy leetcode and medium leetcode will suffice or shall i go ahead with hard ones as well ?

@ShortGiant1 4 жыл бұрын

So what did you find out..

@yashadukia9646 4 жыл бұрын

Can you solve this using quick sort partitioning method? Thats more efficient and would love to see that solution

@doruwyl 4 жыл бұрын

I would make a clear difference between the possible solutions: 1) Time: O (n log (n)) - (sorting and then accessing the n-k element) 2) Time: O(n log (k)) - using min heap 3) Time: O(n) - using quick select algorithm More details and in depth explanation can be found here: kzfaq.info/get/bejne/nq17kpifnZfIoqc.html

@doruwyl 4 жыл бұрын

I have to add that 2) solution (using min heap) it depends how the heap is built. If the heap is built using "sift down" approach then the time complexity will become O(n) If the heap is build using "sift up" approach, then the time complexity is O(nlogn)

@syedyaser8753 3 жыл бұрын

Just curious to see that, if we use max-heap here instead of min-heap, the complexity will be O(n^2). When we will insert the k+1th element, we will have to remove the minimum element from the maxheap which will actually take O(n) time rather O( logn).

@anushakandagal1727 4 жыл бұрын

Can i use max heap of size n and pop out the topmost element k-1 times while heapifying the rest of the heap (size of the heap keeps reducing just like in heapsort algorithm )and finally return the root (k th iteration) ?? That would take k*log n time if I'm not wrong ,better than n*log k because k

@kartikagarwal5414 3 жыл бұрын

But to create the heap you will take complexity O(n) even if you heapify instead of bubbling So really it is n + k log (n) But I like your approach

@myIndianPride_ 4 жыл бұрын

There is an O(n) Algorithm using Kth other statistics which is basically built as nth_element() in cpp.

@MadeByDAY 5 жыл бұрын

Once again, fantastic video/series! Rather than asking for a specific problem, I'm more curious on how you're able to immediately recognize the solution to these problems. There are some [otherwise trivial] problems that I will get absolutely stumped on, and will check the problem discussions for the solution and realize that I would have never come to such solutions on my own (which leads to me getting discouraged and stepping away).. Would you mind explaining (or making a video) on what to look for in a questions' description when determining the approach to the problem?

@KevinNaughtonJr 5 жыл бұрын

Hey Dom, these questions are hard, don't beat yourself up!!! It's so normal to struggle with these questions and I often do, especially when I first started. I think recognizing possible solutions to these questions definitely comes easier as you practice. Chances are if you solve one question, there's 5 other questions that you'll be able to use the same approach for. Otherwise in general, if I don't have an idea right away, I try to systematically go through data structures and think..."can a stack be useful here...no...ok, can a binary search tree be useful here" etc. I hope this helps!

@MadeByDAY 5 жыл бұрын

@@KevinNaughtonJr Thanks for the reply! You're right, just gotta find the time to practice more. It does definitely seem that some questions have the exact same approach, and are just worded differently. Systematically going through the data structures is a really cool approach and I'm going to start doing that now whenever I don't know where to start on a problem. Thanks again!

@KevinNaughtonJr 5 жыл бұрын

Anytime Dom lmk if there's anything else I can do to help and good luck! :)

@srijan4622 4 жыл бұрын

Isnt't the runtime O(n logk). We are basically calling heapify on every insert for a max heap height of log(k). And also, doesn't this now become similar to heapsort? Isn't heapsort generally slower than quicksort?

@yuliashavit3108 5 жыл бұрын

Hi Kevin, Thanks for your videos! Any chance you would do a video for question 543 - diameter of binary tree? I tried to figure out the solution, but didn’t get it throughout. If you have another awesome analogy (like the movie theater) it would be great 😅 Thanks a lot!

@mayukhchanda5805 4 жыл бұрын

I'm sorry if I make a mistake in judging the time complexity ,but won't it be O(ArraySize*log (k)) . Nonetheless, there is an algorithm that can do this in O(N) time, which always finds the approximate median and partitions the array. My questions is when I was implementing the said algorithm, I didnot take into account the case of duplicate numbers. What should I do for that, if you can help me ? Anyway thanks if you read my comment. I will also try your implementation.

@uselesvideo 4 жыл бұрын

Hey kevin, the heapify run time is O(n) but in the worst case you have to pop everything from the heap with O(logn) for each operation, so this means the worst case time complexity is O(nlogn).

@uselesvideo 4 жыл бұрын

Also just adding numbers to a heap doesnt make it O(n).. its only O(n) if you properly do bottom-up heapify.. which if you did .. using a max heap would be ideal since you only need pop k

@bismeetsingh352 3 жыл бұрын

Can u expain the quick select algo?

@manitanmoydasgupta569 4 жыл бұрын

hey Kevin, Please share details of this airplane seating arranagemnt A seating arrangement was to be designed for airplane management system which had an arrangement like [][]-[][][][]-[][] ( Pass way after the second and sixth seat ). It had three rows of such an arrangement. A group can have members ranging one to four and no person in the group must be booked with a seat alone. Write a code to allocate seats in such a manner that if the number of seats to be booked was Four : Together in the middle positions or allocated in pairs . Three : Only in the middle positions of the seating arrangement. Two : Only in pairs in the available location. One : If any unfilled position is available or in a position in sequence which is empty.

@akshayburke7905 3 жыл бұрын

Kevin , what if array has duplicate numbers ? will it work ?

@karthikk5895 5 жыл бұрын

This question is related to order statistics. Making a video on that might be more helpful. That covers this question to the core.

@KevinNaughtonJr 5 жыл бұрын

I don't know much about order statistics but I think it's just what the question is asking i.e. find the kth largest element in a set of numbers. If I did know more about it maybe I would make a video :)

@PrathamGupta2408 3 жыл бұрын

Hi Kevin, I'm currently preparing for my job interviews. I've covered almost all the aspects of DSA required. Can you please help me brush up on my skills? Thanks

@vigneshse 5 жыл бұрын

Wow, thats a nice little tip there. Replace sort with minHeap which brings down the time to O(n) right there. Awesome!

@KevinNaughtonJr 5 жыл бұрын

The runtime is actually O(nlogk) i mispoke sorry about that. nlogk because we have to go through n elements placing at most k of them into a heap I hope that makes sense if it doesn't lmk and I can explain further :)

@vigneshse 5 жыл бұрын

Kevin Naughton Jr. Ah, then the difference is negligible. Not more efficient than sort, correct?

@KevinNaughtonJr 5 жыл бұрын

@@vigneshse it's a bit better, but it does depend on what k is (so technically it can degrade to O(nlogn) if k = n). Sorting will be O(nlogn) (or N^2 depending on the sorting algorithm used) regardless of the value of k

@thirumagaldhivya2549 2 жыл бұрын

I think we should use maxheap right. Will minheap be used here?

@yashgandhi9698 2 жыл бұрын

@AdityaPrasad-dt3oh 2 жыл бұрын

Can someone explain me why would the kth largest number would be at root of the minHeap ? I am new to this and I thought we have to use maxHeap for the question.

@piyush12121 4 жыл бұрын

The usual follow up is what if the input can't be fit in the memory ?

@vedankgoyal1706 3 жыл бұрын

I think a better approach would be to go with quicksort algorithm. We take an element and find its position in the array in O(n) time. Then if the element's position is K we return the element. If the element's position is less than K we do the same thing for the subarray greater than K else we do it again for subarray less than K until we reach the position of K. Divide and Conquer approach. Time Complexity : O(n) { Maximum iterations would be 2n} Space complexity : O(1) { In place }

@aydasu 5 жыл бұрын

It would be fantastic if you could do some graph questions from leetcode Kevin. Thank you!

@KevinNaughtonJr 5 жыл бұрын

Anytime I hope you enjoyed the video! I'll see what I can do about more graph problems in the future!

@himanshuchhikara4918 4 жыл бұрын

superb bro

@karljay7473 5 жыл бұрын

A asked about this problem in a forum because there were several solutions from different sources. Seems QuickSelect, Heap, and median of medians are all workable, but median of medians has the best performance. en.wikipedia.org/wiki/Median_of_medians. Is there a reason to use a heap instead of a median of medians?

@karljay7473 5 жыл бұрын

Update: I have an answer, seems median of medians has extra overhead and the "real world" solution is QuickSelect. Kinda confusing when there are so many answers to one question.

@KevinNaughtonJr 5 жыл бұрын

Hey Karl, thanks for the comment. You're right it can be confusing when there are so many answers to a single question. Because of that I think it's always a good idea to try and lay out 2 or 3 approaches for a problem (to your interviewer) and pick one while explaining that specific solution's benefits. Some things to consider might be...runtime, space complexity, readability, scalability, etc.

@abhinavmishra7617 4 жыл бұрын

Really helpful

@KevinNaughtonJr 4 жыл бұрын

Thanks Abhinav!

@supremoluminary 4 жыл бұрын

You said you were using a heat but it looks like you’re using a priority queue object. I don’t know what either one of those things are. What is that in JavaScript?

@KevinNaughtonJr 4 жыл бұрын

A max/min heap is a priority queue just based on value! I don't think javascript has a heap library :(

@Kaan-qr5pv 4 жыл бұрын

I think solving this via a heap is very smart. I'm curious how this would be solved in Swift since Swift doesn't come with a pre-defined Heap like data structure (would have to write it custom or import some code). Any ideas?

@Kaan-qr5pv 4 жыл бұрын

Ok I found this: codereview.stackexchange.com/questions/145877/quickselect-algorithm-in-swift seems nice!

@Smigo 3 жыл бұрын

Wouldn't the last minHeap.remove() actually delete the Kth element? I am confused at the last line.

@RenatoRaeffrayBarbosa 3 жыл бұрын

remove and return to removed element

@rubinip1956 3 жыл бұрын

But this heap approach runtime is around 4ms when I tried it in leetcode. When I use normal approach (Arrays.sort) runtime is 1ms. How can you say this is effective

@Garensonic 5 жыл бұрын

Also these videos were very useful to help me prepare for a few phone screens and an on-site at Goldman Sachs and at Amazon. I am having an on-site in two weeks with Goldman Sachs as well and am pretty sure I have to write code in that interview as well. Is there any resource that could be of help or even a time to mock interview so I can be more prepared

@KevinNaughtonJr 5 жыл бұрын

Hey Garen thanks so much I'm happy to hear that the videos have been helpful! I believe there are a few sites that offer mock interviews I also offer them on my Patreon if you're interested! www.patreon.com/KevinNaughtonJr

@5MrSlavon 2 жыл бұрын

it should not be O(n). Removing from heap is logarithmic. As you keep K elements in the heap it is going to be log(k). So overall solution is O(n+ (n-k)* log(k)) , not O(n). Inserting into heap is constant so we only take removal of the elements into account. And why not Quick sort selection algorithm which takes ~ n on average ?

@KJ-1271 3 жыл бұрын

I WROTE ALL THIS CODE THINKING I WAS SOME SAINT AND THIS GUY FINISHES IT IN 2 LINES. O K. Buddy. I forgot about sorting

@jacob5253 5 жыл бұрын

There is a better solution with quick select.

@yathuarulnanthy5822 4 жыл бұрын

Is it? I thought the worst case for quick select is O(n^2)?

@FavoriteBananaTWO 4 жыл бұрын

@@yathuarulnanthy5822 Yes, but the average case is faster, so it depends on what is more important for the person implementing it

@CoolnesXcore 3 жыл бұрын

@@yathuarulnanthy5822 so worst case happens on rare occasions ("more likely to get struck by lightning" according to the Cornell algo class on coursera) that is why it is safe to use it because it is more likely to get O(n) since we need to shuffle the array.

@siobhanahbois 3 жыл бұрын

1:58 return nums[nums.length - k +1]; no?

@vikasjainOfficial 4 жыл бұрын

Hi Kevin, Your videos are very helpful and I am watching them on a regular basis. I have google interview lined up next month, so just wanted to check if we can sync sometimes for a quick chit chat to make myself well prepared for the google? Regards, -Vikas

@KevinNaughtonJr 4 жыл бұрын

Thanks Vikas and congrats that's amazing!!! Check out my Patreon page I have a few different options that I think could help you prepare for your Google interview!

@kautukraj 2 жыл бұрын

Did not discuss the quickselect algorithm.

@sriharikamariyala1931 Жыл бұрын

I was asked question to design a RDBMS database design schema for a UPI transactions system(my problem statement). I couldn't come up with relationships and table attributes correctly. Can you PLEASE MAKE A VIDEO ON DESIGNING DATABASE SCHEMA FOR A GIVEN PROBELM STATEMENT IN AN INTERVIEW ENVIRONMENT------PLEASEEEE🥺🙏

@ronaldmackee3401 5 жыл бұрын

Just like sorting, adding the array elements to a priority queue would be O(n log n) time complexity. I give you that it is a cooler solution.

@KevinNaughtonJr 5 жыл бұрын

Hey Ronald! I believe you can actually build a heap in O(N) time where N is the number of elements you are inserting into the heap. The runtime becomes O(NlogN) normally because you remove all the elements from the heap (because the heap has to heapify with every removal). I think in the code I provided the runtime would actually be O(NlogK) because we are restricting the size of the heap to be at most K at any point in time. I hope that makes sense I'd love to hear your thoughts! :)

@ronaldmackee3401 5 жыл бұрын

@@KevinNaughtonJr I mean, an insertion is log n time and you have n elements to insert. I don't see how it is linear. You are not just adding elements to the array, they have to be correctly placed after inserting them at the end of the array, or it would not be a min or max heap. Maybe we are talking about different things?

@KevinNaughtonJr 5 жыл бұрын

@@ronaldmackee3401 Nah I think we're talking about the same thing and it's hard to understand my tone because it's just a message but I don't want you to think I'm trying to prove you wrong or be mean or anything, but I believe building a heap is O(N) time. It's kinda mind blowing and you can look it up but from what I understand the general idea is that yes it takes O(logN) time to insert into a heap but the 1st insertion is constant time (because there are no elements in the heap...the 2nd insertion almost takes constant time...same for 3rd, 4th, 5th, etc...you eventually reach a point where it's it starts looking less like constant time and more like logN time so the runtime to build the heap is O(N) here's a link that will involve math but might help: stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity (when I first learned about this it blew my mind). LMK your thoughts!

@ronaldmackee3401 5 жыл бұрын

@@KevinNaughtonJr I see what you're saying, but let's consider that O(n log n) refers to the worst case, i.e., you have an initial array that is sorted in descending order (the code doesn't know, right?), and then you start populating a min heap from that array, so every insertion but the first has to be heapified up. Let's agree that Big O notation always refers to the worst case. That is pretty much my whole point.

@KevinNaughtonJr 5 жыл бұрын

@@ronaldmackee3401 Big O def is always worst case and I totally agree with your logic that it sounds like it would make it O(NlogN) but according to math I don't think that is a tight asymptotic bound (which I could reason with the math but not sure i can :( ). I'll have to do some more reading and hopefully I can understand it better then. It definitely seems like building a heap should be O(NlogN) but according to a ton of resources online it can be done in O(N)

@ZwartCode 3 жыл бұрын

Could also negate the value, and then pop till that many in and then un-negate the value.

@Dinakaran4 3 жыл бұрын

Hi, i am watching your videos to prepare my interview can you share me any good sample resume as it helps me since ny resume is getting rejected in many companies

@sujatagg9838 3 жыл бұрын

Hi Kevin, I have a google interview in 3 days. Could you please help me with few topics to focus on? I watched your playlists. Thanks in advance!

@shanthureddy4234 2 жыл бұрын

can we do it from the QuickSelect Algorithm ? right ?

@nishithaponnapati4797 2 жыл бұрын

Hey Kevin can you help me prepare for the Google interview I am practicing quite a few algorithm

@jazzpants 4 жыл бұрын

I have an interview at Google in two weeks 😱😱😱... would love to do a mock interview session with you...

@KevinNaughtonJr 4 жыл бұрын

That's awesome congrats on getting the interview with Google! If you're interested in doing a mock interview check out the "Onsite" tier on my Patreon: www.patreon.com/KevinNaughtonJr

@Sim0000n 2 жыл бұрын

Actually the heap takes n*log(n) rutime, even with Fibonacci Heap. Quick select is faster

@DataScienceDiaries 3 жыл бұрын

Hi Kevin, I have a big interview coming in my way, i have roughly 30 days of time. For the same i have couple of questions , if you can help me on those that will be great - 1. How should i prepare ? 2. How to build problem solving approach like how would i know for any question that it should be solved with this approach or that approach. 3. Also, what i face more frequently is that lets say for any problem i was not able to solve it and then i looked at solution and understood very well and again after some days lets say 10 days if i try to solve the same problem, i get stuck. How to tackle these, please help

@KevinNaughtonJr 3 жыл бұрын

mandeep kharb hey Mandeep if you’re preparing for an interview I’d recommend joining the interviewing service I created it’ll help teach you the most common topics and questions thedailybyte.dev/?ref=kevin I’d recommend joining the annual plan if you can. I also offer tons of other services like mock interview on my Patreon page if you think that could help you too! www.patreon.com/KevinNaughtonJr

@harishdalmia6538 5 жыл бұрын

This code will not work when we want to retrieve k=1. Please sugest

@blasttrash 5 жыл бұрын

hey where do you work? Big N?

@walidzein1 3 жыл бұрын

yea he work at KZfaq making videos lol

@Nkraka 5 жыл бұрын

Can you please implement this in Python? And, I will appreciate it if you any advice for me as I'm preparing for an interview with Google for TSE position!

@KevinNaughtonJr 5 жыл бұрын

I definitely can't off the top of my head but if I had to guess it's probably even easier in Python! I'd be happy to give you some advice maybe we can chat in the Discord channel if you're willing to join? Here's the link to join: www.patreon.com/KevinNaughtonJr

@aayushdua7787 3 жыл бұрын

can someone do this implementation using priority_queue stl in c++?

@Garensonic 5 жыл бұрын

The runtime of this is actually O(nlogk) because you are inserting values in a heap of size k and insertion in a heap has O(logk) time. Do you know the space complexity of this algorithm?

@nagendra.varikuti 4 жыл бұрын

Quick select algorithm works faster than this. Runtime is O(n)

@LanceSanity 5 жыл бұрын

Do you think interviewers would expect people to get the O(n) for this problem? It's much better, but way less obvious than the other approaches. Gotta use pivots and a divide and conquer approach. Worst case would be extremely rare with random pivots.

@KevinNaughtonJr 5 жыл бұрын

I honestly don't think they'd expect the O(n) solution. I agree I think it's not obvious at all and kinda overkill

@mandeepgoyat934 5 жыл бұрын

That's where the preparation come in, better implementation is what separate the candidates!

@KevinNaughtonJr 5 жыл бұрын

@@mandeepgoyat934 I definitely think it depends on the question, but it can never hurt to do better :)

@treyquattro 4 жыл бұрын

good shortcut! In C++ I would just use nth_element ;-)

@Paul-jx6tl 3 жыл бұрын

you need to solve it using partition, not sort/heap

@farwaiftikhar2403 5 жыл бұрын

Hi Kevin Your videos are great and have helped me a lot. I have sent you an email in hopes of connecting with you for further help. Thank you for the great videos!

@KevinNaughtonJr 5 жыл бұрын

Hey Farwa! Anytime thank you so much for the support! I'm emailing you back right now :)

@farwaiftikhar2403 5 жыл бұрын

@@KevinNaughtonJr Got it and responded back :)

@KevinNaughtonJr 5 жыл бұрын

@@farwaiftikhar2403 Awesome :) I just sent you an invite to the Discord server!

@PraneethThalla 5 жыл бұрын

The runtime of this is not O(n), for each element you are inserting and deleting from a heap of size k, and since insertions and deletions of a heap of size m is log(m), the runtime is O(n*logk)

@KevinNaughtonJr 5 жыл бұрын

Hey Praneeth, good catch you're totally right I misspoke!

@PraneethThalla 5 жыл бұрын

@@KevinNaughtonJr I believe there is a O(n) solution though! It involves using the quickSort partition method, do you think Google would expect the O(n) solution or would the O(nlogk) solution be enough? Thanks! :)

@KevinNaughtonJr 5 жыл бұрын

I think you're right! Honestly, I really think if you got the O(nlogk) solution I think you're in great shape, but if you can offer an O(n) solution it can only help :) thanks for the comments!

@PraneethThalla 5 жыл бұрын

@@KevinNaughtonJr Awesome!! I have an onsite next week haha! I actually just emailed you with a few questions about the interview, I've been grinding through your videos all day today! :)

@KevinNaughtonJr 5 жыл бұрын

haha happy to hear that thanks man! That's amazing congrats!!! Keep working hard it always pays off! I'll take a look at your email now :)

@jinxscript 2 жыл бұрын

why bro stopped doing this 😭

@rahulrggupta27 2 жыл бұрын

Hi, I have a interview lined up for one of the biggest company and I need your help in finding out answer to a design problem, whats the best way to reach you? (email id pls?)

@vashi1989 5 жыл бұрын

Hi.. Can you please do a video on Leetcode Question 332. Reconstruct Itinerary.. Thank you

@brianspinos 4 жыл бұрын

Adding to a heap is not O(n) it is O(log n) because it is inserted in the bottom of the tree and it has to traverse the tree upward

@ronakpatel8230 3 жыл бұрын

this code for following example gives incorrect ans Input:- nums :- [3,2,1,5,6,4,10,11,12,13,15,15] k:- 2 Output :- 15 which is logically incorrect because 2nd largest number should be 13 and not 15.

@mfauch4444 2 жыл бұрын

Its still worst case n log n if k is the size of the array

@abhishekbhatia1168 Жыл бұрын

Dude, this is wrong. Insertion into a heap is O(log(k)). Not O(1). It's O(nlogk).

@thedataguyfromB 3 жыл бұрын

class Solution { public int findKthLargest(int[] a, int k) { if(k>a.length) { return -1; } if(a==null || a.length==0) { return -1; } PriorityQueue minH=new PriorityQueue(); for(int i=0;ik) { minH.remove(); } } return minH.peek(); } }

@_ApoorvaShinde 3 жыл бұрын

He is cute

@Turnpost2552 3 жыл бұрын

Arrays.sort() ??

@soumyadeeproy6611 4 жыл бұрын

The way you had written the code is not good at all. U are doing repetitive work. The problem that I see is that first you are inserting an item into the heap which takes logn time and then checking if heap size extends k or not. If extends,then again u are removing the top item,means after k successful insertion,you are adding one item and then removing it again !! The best way to optimize this that you should have segregated into two loops priority_queue pq; for(int i=0;i