Placeholder Image

字幕列表 影片播放

  • Here's a quoting interview question from Amazon.

  • It is.

  • Find the number of negative integers in a row wise and column wise sort of metrics.

  • So here's an example.

  • As you can see, the numbers in the metrics are sorted, rule wise and column wise, and here we have four in their numbers.

  • So our function let's say funk should return four.

  • In this case, here's a naive solution for this problem.

  • We'll just start from the first row and we'll count the number of negative numbers one by one.

  • So we find three negative numbers here on in the second row.

  • We find just one negative number on in the third row.

  • In the last row, we find zero new numbers, so we add them up on we get four.

  • In this case, the worst case scenario for the solution is when we have all native numbers in The Matrix.

  • In that case, we'll need to traverse all the elements in your ray or matrix, so the time complexity for the solution would be big.

  • Off end times M, where n is the number of rose we have on Emma's number of columns we have in the Matrix.

  • Here's the optimal solution for this problem will start from the top right corner and we will find the position of the last negative number in the first row.

  • And using that information, we'll find the position of the last negative number in the second row, this one and so on to we get to the last row or we don't have any more and they got the numbers to count for the first row.

  • The position of the last name and number's nearly one is, too.

  • So we'll know that the number of negative numbers in this row is just three and same thing with the second rope.

  • The position off the last name and number is zero.

  • So the number of negative numbers is just one here on.

  • We have their internal numbers in the last row will add them up on.

  • We get the answer for the time.

  • Complexity for this solution is an older off n Plus M.

  • Where again and he's a number of rows and m is a number of Collins may have.

  • So here's the optimal solution in code.

  • We're defining our function here with the Matrix, Andi, the number of rows and the number off columns as impetus were initializing counter zero, which we're going to use to keep track of the number of negative numbers we've seen so far on I 20 which is are rowing necks and Jay to M minus one, which is our colony next.

  • So we'll use I m j to keep Jack off which element we're looking at.

  • So while Jay's larger than or equal to zero, so we still have more, they got numbers account on I is less than end.

  • So we haven't got to that last row yet.

  • If the element we're looking at am I Jay is and they're the number, Then we found the last Nagel number in the road.

  • So we increment the count with J plus one, and then we go to the next road.

  • If the number we're looking at is not and they're gonna number, then we'll move our pointer to the left or we'll try the same thing with the number on the left on will repeat this process over and over again until we get the total number of negative numbers in this matrix and then we're gonna return that.

  • All right.

  • Thanks for watching this video.

  • If you're watching this on YouTube, make sure to check out the original article on Gates for gigs in the description below.

Here's a quoting interview question from Amazon.


單字即點即查 點擊單字可以查詢單字解釋

B1 中級

亞馬遜編碼訪談。在行/列明智排序矩陣中計算負整數 (Amazon Coding Interview: Count Negative Integers in Row/Column-Wise Sorted Matrix)

  • 0 0
    林宜悉 發佈於 2021 年 01 月 14 日