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.
Is the question supposed to be picking n-1 elements from each row instead of m-1 elements? If it is m-1, there will be a case ( 3 x 100 matrix) that it's not possible to pick at least one element from each column.
- vikram.kuruguntla October 26, 2019The below logic is to choose n-1 elements from each row.
There are two cases for this problem.
case 1> If the maximum element of each row is not the same column position, then excluding the maximum element from each row and sum all other elements gives the result.
1 100 120
10 3 9
5 70 100
In the above example, the maximum element from each row is 120, 10, 100. They are not in the same column position. In this case, simply exclude maximum element from each row gives the result which is (1 + 100) + ( 3 + 9 ) + ( 5 + 70) .
case 2> The opposite of the 1st case is that the maximum element of each row is the same column position. In this case, choose one of the element from that column such a way that the resultant sum is minimum.
1 100 120
10 3 90
5 70 100
In this case, the maximum element of each row is in the 3rd column. The objective is to choose one value from the 3rd column. Choosing the least value from that column does not give minimal value. The reason is that picking the value in column 3 of some row needs to remove the second largest element in that row. The overall increase is in total sum is "element at column 3 minus next largest element in that row".
Let's find how much increase happens in all three cases.
Picking 1st element in column 3 --> overall increase is 120 - 100 = 20
Picking 2nd element in column 3 --> overall increase is 90 - 10 = 80
Picking 3rd element in column 3 --> overall increase is 100 - 70 = 30
Hence pick the 1st element of column 3.
like in case 1 calculate the sum of all elements by excluding the maximum element in each row ( i.e (1+100) + ( 10 + 3) + ( 5 + 70 ) = 189 ).
Now directly add the overall increase by picking the element in column 3. That is 189 + 20 = 209.
Which eventually same as ( ( 1 + 120) + (10 + 3) + (5+ 70) = 209 )
All of these can be easily done in a single traverse in a matrix.
Please comment if there are any logic issues. :)