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 can start off with the top row, counting from the right end until we hit a 0. Let's say we hit k1 number of 1's before hitting a 0. Total number of 1's in row1 = k1.
- Ashish June 27, 2016Now for the next row, we know that every column is also sorted, so no column from the end can have a 0 if it has a 1 in this row. So, we can safely skip k1 number of 1's and start from there until we hit a 0. Let the new number of 1's hit be k2. Total number of 1's in row1+row2 = sum so far + (previous k + new k) = (k1) + (k1+k2) = 2k1+k2
Continuing, we can go down, and we'll be amassing the number of 1's. Next row, we get total 1's = 3k1+2k2+k3, and so on. The total 1's in the end would be n*k1+(n-1)*k2+...+2*k{n-1}+kn.
Time wise, the total counting is k1+k2+...+kn = actually the whole length of one row = n, since if we completely cover a lot of elements in one row, the elements to cover for the next row become lesser and lesser, and the maximum we can cover is only n elements horizontally. Thus, time is O(n).
This can be optimized by binary search. Applying that on first row to find k1 yields us log(n) steps for row1, log(n-k1) steps for row2 and so on. Total = log(n)+log(n-k1)+log(n-k1-k2)+...+log(n-k1-k2...-kn).