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.
I think I have got the idea:
- onsankawai February 28, 2016Observation:
Scan the seats from left to right, if you have found a person P who is not single and is not sitting with his/her counterpart Q
1. If one of P's neighbor or Q's neighbor is a single, swapping P or Q with the single man never hurt the optimality - add only 1 swap
2. If swapping the man sitting on right side of P (who is also sitting with his counterpart) does not break them, swap him with Q. i.e. the case ABBA, swapping the first B with the second A does not break the BB couples - add only 1 swap
3. Find 2 single men sitting together and do 2 swaps with them, this also never hurt the optimality since all other ways would require to break at least one couple in this case, ending up using at least 2 swaps to fix that in total - add only 2 swaps
4. As the last resort, greedily swaps the person sitting on the right side of P with Q(which breaks the couples) - at least 2 swaps, can be more
The idea is not too complex and the code can be a bit long, this method passes the following testcases:
AABCCDDEEBFFGGHI - 2 swaps
CABBADDCEETK - 2 swaps
AABCCDBFHGGFEE - 2 swaps