Google Coding Interview Question and Answer - Min Cost To Hire K Workers [LeetCode 857]

In this video I explain the solution of a Google programming interview question “Minimum Cost To Hire K Workers”.
You can find it here - leetcode.com/problems/minimum...
Link to the solution code -
github.com/shiran-afergan/You...

[@vikasbairwa604]

The best part about this video is that she didn't go with the optimized solution from the get-go but rather gradually build up to it explaining all the optimizations.

[@ShiranAfergan]

Glad you enjoyed it 😊

[@andrewcenteno3462]

The code is simple, but this problem is really hard to wrap your head around. She did an incredible job explaining the ratio concept at the start

[@danielzhang3827]

This is definitely the best explanation i've seen online! Thanks for drawing out and running through an example where each worker has a chance to be the captain. That definitely cleared up all of my confusion. Keep it up!

[@ShiranAfergan]

That’s awesome! I’m glad it helped :)

[@sambasivareddyasam5712]

the best thing about the solution is the math questions ...thank you for the solution

[@shatulbansal4756]

A very tough question & the way you explained it by starting from the brute force approach & then gradually moving to optimized approach was just awesome, kudos Shiran !! Keep it up :)

[@raghavsood768]

Spent over a day trying to understand the optimized solution. You made it really simple. Thank you so much!

[@iamrey192]

Thanks. You really explained great. I was struggling to find a solution like yours. Once again thanks

[@iulianabinzar8297]

Thank you so much! This channel is by far the best I've found on the topic.

[@akashsrivastava8324]

This is the best explanation I have seen yet.

[@ShiranAfergan]

Thank you! That’s great to hear:)

[@dincerbeken5761]

This is really one of hardest questions I saw. I could neever even understand the solution without your guidance. Thank you.

[@ShiranAfergan]

Yes, it’s definitely a tough one. I’m glad the video helped:)

[@pranjalabhishek7566]

Your explanation is far better than many content on youtube. Please post such odd leetcode problems in such a fantastic way.

[@ShiranAfergan]

Thank you :) I’m working on a new one now. Hopefully will be up next week.

[@pareshpandit802]

This explanation makes it so simple! Thanks!

[@skyisbluexd]

I knew this would be the best explanation. thanks

[@priyanshgupta6830]

Brilliant explanation, You definitely deserves more views. Top quality content

[@ShiranAfergan]

Thanks Priyansh! I’m glad you enjoyed it :)

[@KidCrippler]

Loved the video and the explanations, you rock! I also really liked the fact that contrary to what common sense dictates, the algorithm wouldn't let us choose the best and cheapest worker, since he's skewing everybody's paychecks (שובר את השוק). Keep it up 👸

[@ShiranAfergan]

Thanks! Glad you liked it 🙂

[@DavidSharma-ds]

Amazing visuals and solid explanation of the intuition. You actually explained why does the ratio of wage/quality matter and how to optimise choosing captian.

[@harryscorner7135]

Thanks a lot for this amazing video @Shiran Afergan!!!!

[@ShiranAfergan]

You’re welcome :) I’m glad you enjoyed it!

[@addictedgamerclashofclansa1251]

You are great explainer! Loved it! Looking forward to more questions

[@siddharthasriramvinjam167]

Concise and clear. Thank you Shiran Afergan.

[@ShiranAfergan]

Thanks 😊 glad you liked it

[@raviprakash4-yearb.tech.ch375]

by your explanation i am able to do 2 question this one and other "maximum performance of a team"(leetcode) . great explanation . thanks a lot

[@ShiranAfergan]

That’s awesome! 💪🏽😎

[@khalidkhan8292]

The best explanation so far. It's not about the code. As if you are solving or trying hard problems you already know how to write that. What matter here is what is the problem , how to solve the problem and why this approach is best and let me tell you, you nailed the explanation part. You earned a subscriber miss.

[@cvivek503]

Thanks for the great explanation ! Each time you applied some optimisation I felt like "dayum" . Your naming of variables was also top-notch.

[@ShiranAfergan]

😆 Thank you! I’m glad you enjoyed it 😁

[@chaunguyen8202]

YOU'RE THE BESSSTTTT! Thank you for making it easy to understand.

[@ShiranAfergan]

Thanks 🙏🏽 😊

[@ptr2587]

Really liked your way of explaining. Thank you so much for such an explanation. Using a variable named "Captain" was very cool.

[@ShiranAfergan]

Thank you! The leetcode solution also had the “captain” worker so can’t take credit for that name :) glad you enjoyed the video!

[@jishulayek8252]

Explanation is really crisp and detailed. Keep up the good work.

[@ShiranAfergan]

Thank you :)

[@vxz90044]

Great explanation. I really enjoyed the "paper" explanation and process onto code. Keep it up

[@ShiranAfergan]

That’s awesome! Thanks:)

[@adityatiwari2412]

Thank you so much for this video!

[@pushkarraj4640]

Most Unique and Nicest Ever explanation seen on KZbin for a leetcode hard Problem. Thanks a lot. Code Quality Oh My God !!👌 U are killing it there 🔥🔥🔥🔥

[@ShiranAfergan]

Thank you!! 🙏🏽🙏🏽

[@AniketSingh-mt6zr]

Very Nice!! I love the way u start from naive approach to the best solution and optimised the solution step wise .

[@rohitrout6450]

wow Just outstanding explaination ! after spending some years people can learn to code but very few get this skill of explaining the code.

[@ShiranAfergan]

Thank you! 😊

[@harishsn4866]

Thank you so much for such a clear explanation.

[@habilismayilov838]

excellent explanation!! [best ever]

[@tongyuyang2073]

Thank you so much. This is super clear!

[@ShiranAfergan]

I’m glad it helped:)

[@tejaspatel2212]

Why you stopped making videos?? This was such a great explanation, pls solve more leetcode questions 😅

[@ankoor]

Awesome explanation!

[@sbrahma0]

Best explanantion so far.

[@RadGopalakrishnan]

Thanks for showing the solution that won't work and then improvising. Was easier to connect the dots!

[@ShiranAfergan]

You’re welcome :) I’m glad it helped!

[@siddharth4069]

Please keep uploading, your videos are among the best on youtube

[@ShiranAfergan]

Thank you! 😊

[@lopamudrarath7176]

Why don't you make a playlist, it would be very helpful. You explained it very nicely. This is best.

[@ShiranAfergan]

Didn’t think of that. I’ll do it, thanks :)

[@poojapalod]

Brilliant explanation🙂Thanks for sharing

[@shrimpo6416]

Fantastic!

[@ShiranAfergan]

🙂

[@satviksharma4897]

Really good explanation! Thanks.

[@ShiranAfergan]

Thanks 🙏🏽

[@Ari-pq4db]

Well Explained , thank you

[@pwnweb5734]

Brilliant Explaination. Thank you

[@vishnuvardhan-md1ux]

Very well explained in 15 minutes.

[@ShiranAfergan]

Thanks:)

[@RahulGupta-hn5cl]

Your Explanation is very nice and good approach .. plz make these type of video continuously

[@ShiranAfergan]

Thanks Rahul! I got one coming up in a few days :)

[@snehilgupta1558]

Explanation is top notch...keep going.

[@ShiranAfergan]

Thank you :)

[@rajatbansal7431]

And wow great solution video !

[@ShiranAfergan]

Thanks!

[@jionghongli7826]

Great explanation! keep going

[@ShiranAfergan]

Thank you!

[@vineetkumar2899]

that's awesome

[@pawandeepchor89]

Liked your explanation 👍👍

[@ShiranAfergan]

Thanks for watching :)

[@hapysethi1306]

Thanks!

[@executenow4211]

Your explanation is good...

[@ShiranAfergan]

Thanks!

[@sidharthbansal5835]

Very good Explanation

[@ShiranAfergan]

Thanks :)

[@rajatbansal7431]

You look too good to post solutions to leetcode problems * NVM*

[@ShiranAfergan]

:)

[@VasudevaK]

At 13:15, I liked the video!

[@himanshuchhikara4918]

Please make a video on Strobogrammatic Number II .. by the way this video was extremely helpful(literally best explanation that can be) video thankyou very much :)..

[@ShiranAfergan]

Thank you! That’s great to hear :) i like your suggestion, Haven’t done a video on this type of recursion yet. Adding to my list.

[@almasabdrazak5089]

subscribed

[@sriramkrishnamurthy4473]

HEy Also ! How are we always sure that there will be a person whi can be the captain of the team (i.e form a team of size k) because even in this example we saw how 2 peoplw were not able to make a team unless we would somehow pay more than his expected wage and make him the captain

[@deveshsharma7487]

Hey Shiran, could you please explain that why is discrepancy in the time complexity you mentioned in insertion of heap for the two code blocks. For the code block from line 16 to 19 you told it is O(k) and for 23 to 34 you told it is nlogK, Why is is O(k) although we are inserting in the heap which acutally takes O(log of size of heap). Please explain this. Thanks a lot!

[@litaibaikidmort]

You are so cute and this explanation is so awesome!! Love this!! However, should captainRatio in line 20 be workers[k-1].first? Since I thought k-1 should be captain in the first place. Though its no big deal since the answer is correct lol.

[@ShiranAfergan]

It is! Great catch, it’s a bug that i fixed later in the video (fix is at time: 14:57)

[@fluffymattress5242]

9:15 Why not just use a minHeap(negative of what you are pushing into the maxheap) and pop the top K?

[@ShiranAfergan]

That will also work. but the complexity is different. What you suggest has O(n + klogn) time and O(n) space. what i did in the video is O(k + (n-k)logk) time and O(k) space.

[@philongpham3886]

@@ShiranAfergan I usually use std::multiset for the heap. Under the hood it's implemented using RB tree so the time complexity would be similar. The great thing about it is that you can pop the last element using minHeap.erase(minHeap.end()--) It also allow you to find an arbitrary element using minHeap.find(). Great explanation btw. I was so lucky to find your channel :)

[@c.4469]

I think this is the hardest one.

[@Opportunity631]

please tell me how quickly you were able to come up to this solution ? Amazing!!!!

[@ShiranAfergan]

I don’t remember but I can tell you I highly doubt I’d be able to come up with this during a 45 minutes interview 😆

[@Opportunity631]

@@ShiranAfergan thank you, my confidence has lowered after seeing this problem and the way you solved it😅 I was no way I can do this.

[@jionghongli7826]

Why only compare the quality[k] to quality[n-k] with maxHeap.top() instead of every element in maxHeap ?

[@jionghongli7826]

so Why do we choose the highest quality person to remove? Why not choosing other workers?

[@ShiranAfergan]

Because we want the heap to contain the k smallest qualities. Let’s say we have k=3, heap={1,2,4} and current quality is 3. If we were to replace 3 with anything other than the largest quality (4), the heap will not contain the 3 smallest qualities (1,2,3)

[@jionghongli7826]

@@ShiranAfergan Thank you so much for replying， but what if we have k=3,heap={2,4,5}, and current quality is 3, and there are more elments coming after the current elment, if that's the case, shouldnt we pop out 4 and 5 the elements and push 3 then push 4 again to make {2,3,4} in the heap ? if we only choose the highest quality person to replace, does it mean we have k-1 elements already optimal in the heap ? I am so confused.

[@ShiranAfergan]

Yes, after each iteration, the heap will contain the k smallest elements we have seen up until that point and not necessarily in the whole array. So only when we finish looping over the entire array, the heap will contain the k smallest elements in the array. If you’re still confused, try contradicting this assumption. Start like this - assume that the heap does not contain the k smallest elements. Meaning there is at least one element x, which is one of the k smallest elements but is not in the heap. So either x was never inserted to the heap or it was inserted and later replaced. Can one of these options really happen?

[@prashantjha439]

Better than the stupid leetcode editorial

[@ShiranAfergan]

Thanks :)

[@sriramkrishnamurthy4473]

Man !! Effortlessly cute

[@symbol767]

I hate math problems so much...

[@JamesBond-mq7pd]

who is from May 11th 2024?

[@VishalKumar-xr4nm]

Here is my code: class Solution { public double mincostToHireWorkers(int[] quality, int[] expWage, int k) { double mincost = Double.MAX_VALUE; int n = quality.length; double[][] workers = new double[n][2]; for (int i=0;i Double.compare(a[0], b[0])); PriorityQueue pq = new PriorityQueue(Comparator.reverseOrder()); double qsum = 0; for(int captain = 0;captain k){ qsum -= pq.poll(); } if(pq.size() < k) continue; mincost = Math.min(qsum * ratio ,mincost); } return mincost; } }