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.
In this problem, there will either be only one celebrity or no celebrity.
- paroksh.saxena January 19, 2015Now iterate over list of people picking two at a time say A & B. Check function knows(A,B). If A knows B, then eliminate A (as it knows someone else, so not a celebrity) and pick next person C. If A does not know B, then eliminate B (as celebrity should be known by all) and pick next person C. This will be O(n) and at the end only one person will remain (as we are eliminating one at each step) say P.
Now either this person is celebrity or none is celebrity. So again iterate over all elements picking each element once (say E) and check knows(P,E) & knows(E,P). If any of the E returns knows(P,E) as true or knows(E,P) as false, then return no celebrity found. Else return P as celebrity.
This will take O(3n) steps ie. O(n).