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 agree with gen-y-s that it can be solved using trees.
However, segment trees are a little overkill here.
In fact this can be solved using just a binary search, although it is easier to visualize this problem using a balanced BST which we can easily build because what we are going to store in it are just indices 0 to N-1 (as the number of bulbs) which are already sorted, so the Tree is actually for visualization purposes. I will try to rewrite this code to not use BST, but to calculate indices of "roots" of intervals directly on the given array of bulbs.
But anyway, here is implementation using BST that is built initially and never changed (as far as its structure). Each is only keeping track of whether some range was toggled even or odd number of times. When asked to get a state of a bulb, it does search on BST, collecting states of nodes on the way. The final result calculated from the accumulated state.
Runs in 3 ms with 10000000 bulbs and doing 1000 toggles.
- blckembr October 06, 2015