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've approached the problem by constructing possible rectangles convering the upper part of the matrix while scanning it row-by row.
Pseudo code:
1. Extract runs: Extract begin end positions for each all-one substrings on each row.
2. Maintain a set of possible rectangles while consuming runs for each row.
3. Obtain the maximum area from possible rectanges.
In step 2.:
- If the run does not overlap any possible rectangle: create a new rectangle with height 1
- If the run matches a rectangle perfectly: make the rectangle higher.
- If there is partial overlap: Close rectangle, create new rectangle for the overlap, begin new rectange for the run as well.
I belive these cover all possible cases. Can someone find a case where this approach would not work? See the code below.
I belive time complexity is O(n). Space complexity is O(width).
- muudry June 07, 2014