is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
We are looking for 'at least how many'. So we do not need an efficient algorithm, we just want an algorithm that in the best case, finds the 25th with the minimum effort.
- remi.carton October 15, 2010So first race we find the median car, it's the 4th car. If we assume it's the 25th car, we only have to prove it's the 25th now.
We test it against the 42 remain cars, so
7* (6cars + our median).
Now assuming that for every single race it is the 4th car, we proved that there were 24 cars going faster (8*3 = 24), and 24 slower cars. As it was the median each time, we are sure that all the car going faster for one particular race are faster than the cars going slower for all the other races.
So that's 8 races to test our candidate versus all other cars.
Note that using this technique as an algorithm to find the 25th car would be just terrible (8*48 races or so).
Hence, at least 8 races, but note that I _did not prove_ that there were no better solution so far. I think you can prove it by saying that you need to test each car at least once, so 7*7, and you need a pivot of some sort to compare the cars between races, so at least 1 other race, so minimum number of races is 8, and we found one that works with 8 races in the best case, there is no better algorithm since the minimum is 8.