Python Interview with a Facebook engineer

Watch someone solve the lucky numbers in a matrix problem in an interview with a Facebook engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Lucky Numbers in a Matrix

Interview question

1) Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column 2) Given an m x n binary matrix mat, return the number of special positions in mat. A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Interview Feedback

Feedback about Parallel Bandit (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Strengths: + TC came up with the working approach for both the problems. + TC wrote easy to follow code with good naming conventions. + TC wrote the bug free code with ease. + TC has good speed. We were able to complete both problems in 40 minutes. + TC can analyse the space and time complexity of their solution. + TC was thinking out loud and it was easy to understand what they were doing. + TC took on hints and optimise the approach for second problem. Improvement Areas: - TC made assumption in first problem that number are positive without stating it out loud. - TC had a implementation issue in the first problem while calculating maximum in each column. Suggestions: 1. Practice writing down the approach and complexity analysis before jumping to coding whenever you would practice on online judge like leetcode. 2. Practice bit more on matrix problems to improve implementation clarity.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

He was pretty good.

Interview Transcript

Red Maelstrom: Hello.\nMassively Parallel Bandit: Yes, hi. Sorry. Apologies for the delay.\nRed Maelstrom: So yeah, so spending like, initial 40-45 minutes on the coding problem. The other 10-15 minutes for feedback. Yeah, here\'s your question. Can you go through it.\nMassively Parallel Bandit: Okay. Given n x m matrix of distant numbers return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is the minimum element in it\'s row and the maximum element in it\'s column okay. So I\'m just gonna read through the example just to make sure I understand. Okay, so. So, for this input, so a lucky number is the element of the matrix is the minimum element in it\'s row and the maximum in it\'s column, okay. So input 3, 7, 8, 9, 11, 13, 15, 17. Okay so, in its column, 15 is the largest and it\'s row is the smallest. Okay, so it has meet two conditions. Let\'s see for example, 1 , 10, 4, 2. 9,3,8,7, 15 and 12. Okay, so I\'m looking for the smallest element. So from the first column, the smallest is one second smallest is three. Third one of course is 12. Okay so is a one the largest in its column? No. Is three the largest in it\'s column? No. Is 12 largest in column? Yes. Okay. Okay. Okay, for example 3, 7, 8, 1, 2. So one, two okay so that\'s the smallest and then okay. Is it okay if I have like a minute just to gather my thoughts? Okay.\nRed Maelstrom: I think yeah, hello, I think yeah so I think this should work, your approach should work. What would be the complexity of that?\nMassively Parallel Bandit: So for getting the smallest interger I was thinking we could implement it was before so just in the first for loop when we\'re going through each list we get them into that would be O of n squared for that function before the getting the smallest I\'m thinking the time complexity would would would be O of n squared.\nRed Maelstrom: Sure can you implement it.\nMassively Parallel Bandit: Yeah. Okay so first step getting the smallest numbers okay. I think the way we want, so getting the smallest numbers won\'t be a challenge. I\'m just gonna think about how once you have the smallest numbers in each row, we go to checking if it\'s the largest in it\'s column. So maybe in addition to storing the smallest in each row, I could store its column and then and then I can go through the loop and just search for specific columns. Maybe I could search each colour and then have like the largest in each, hold on let me think about this for a second. So if I if I, store it\'s column, do another pass and say okay, okay, I can break apart whatever I stored and see if the largest. Okay, so in addition to just storing the value, you could also store its column. And then I\'m thinking I do like a second pass kind of thing. And where I where I like to decompose each smallest value and I say if so like and I\'m looking so for now I\'m basically looking at each column, like if this column is this get the max. Okay so I could have a separate\nRed Maelstrom: What is the issue with the simple approach, like get the smallest in each row. So keep a track of column and see if it is maximum in each column.\nMassively Parallel Bandit: Okay I\'ll give it a shot we make changes. Okay, okay. Since they\'re distinct integers I could say okay, what if I just did this. For c in range. So if it\'s in smallest or I could also I could also just go through each column. I could get like the max I can get the yeah I can just get the max in each column since they\'re distinct integers I could just see if they if any of them that in smallest are also in a column next.\nRed Maelstrom: Right because yeah they are distinct so yeah.\nMassively Parallel Bandit: Okay. So what I could do is I could just so yeah so what I could do is I could just traverse over the first few in range. Then I\'m gonna say smallest row and then largest col. Okay let\'s see okay yeah you could add all these elements okay yeah. So okay so for number in largest col if num is in smallest, I should make this a set to make this so that, for time complexity sake and then we\'re gonna add else here. For num, numbers is in smallest row, result dot add. And then we continue so we were just going through each of the values, the numbers in largest column and then if it\'s in the smallest row we\'ll append otherwise we won\'t do anything and then return result.\nRed Maelstrom: Do you want to try running for one of the examples.\nMassively Parallel Bandit: Okay before I run this, I\'ll probably go through this to make sure I don\'t make any typos. Okay, so lucky number six in the matrix there\'s also initially empty smallest row in the set. This row is a list or just a, rows columns, the number of columns and then for each row in rows, we\'re adding the minimum value in each in each row of the minimum value. And then for each column, we\'re adding the max value. Okay, and then for number in largest column, if it\'s in smallest row okay. Integer not interable.\nRed Maelstrom: Yeah, this is just a column right, you can\'t use like a row and iterate through it.\nMassively Parallel Bandit: Okay. Okay, okay. Okay, all right. Okay, yeah that\'s right. I should just. Okay, so I could say, I can make largest column, be the size of the rows. So I\'ll make it initially negative one times length of cols. I\'ll just basically just store the maximum value at each at each index if that makes sense. So I\'ll just traverse that.\nRed Maelstrom: Do you want to traverse each column for each row or each row in that column?\nMassively Parallel Bandit: Oh, okay, I could do that. I was just gonna Yeah, that\'s probably a better way of doing it. I just gonna say for each index, but like, update the value, butno I think that\'s a cleaner way to do it. So okay. So what I\'m gonna do is okay so what i\'ll do is, I\'ll say. Make it specific to each okay that makes sense putting it on top of each each iteration or updating the specific column okay and then. Yeah so for each column initially, initially the columns is of size columns and for each\nRed Maelstrom: So you\'re making the assumption that matrix is positive right.\nMassively Parallel Bandit: Oh that\'s true. That\'s true negative infinity. This is negative infinity right? Yeah so this will go through each column, each okay yes, so for each row, it\'ll store the max and then so for this example. It\'ll be plus seven, largest so initially. So the length of columns is two, that\'s going to create two negative infinity values in the largest col. And then it\'s going to go through seven when it goes to seven to store seven times larger than so now largest col, index of zero will be seven, and then itt goes through one seven is to the largest and so continue then it goes to eight and then eight is greater. So it\'s going to store seven and eight, and then so that will have seven and eight in our, in our largest col array. And then if that number is in smallest row, then it\'ll append it and return result.\nRed Maelstrom: Yeah, let\'s try running this code. 15 Yeah, 15 is the right answer for this. Cool, I think yeah, that\'s good. Let\'s move to the second question.\nMassively Parallel Bandit: Okay.\nRed Maelstrom: So basically, it\'s another matrix problem with given m x n and binary matrix. You have to return the total number of special position. A position is special if it is only matrix in that it\'s only position with the value one in that row and that column.\nMassively Parallel Bandit: I don\'t know why there\'s so many space okay, given an m by n, binary matrix. Okay, so like zeros and ones return the number of special positions in the matrix I and J in the matrix okay. Position i, j is called special if matrix i, j is equal to one and all the other elements in the row are zeros. Okay. So, in the first example 100, 001, 100 output\'s a one. That explanation, a one two in special position. Okay. And, okay. Okay, so one two, okay so one, okay. Because for that row, it\'s the only one and for that. Okay. And we\'re supposed to return the number of them. Okay. Okay. So the second example. So in that row, so that row was only one, and that col only one and for the second one in that row it\'s only one. Okay. Okay, that sounds good. I think for this one, my approach would be would be like traversing the matrix. And then if we reach a one, we want to see, if we reach a one we want to see, we want to check its its entire row and column. So then we\'ll call a depth first search function. And then that will check it for us like that. If we use the base case, then we know, if we use the positive base case in the depth first search function, then we know that it\'s true and so we\'ll have to increment, maybe a global variable. And then return the global variable.\nRed Maelstrom: I did not understand, like, what do you mean by depth first search?\nMassively Parallel Bandit: So like, so while while we\'re, while we\'re, while we\'re traversing the matrix, I guess like my thing. My idea, like my initial approach is if we encounter a one, we would we would call a depth first search function on that, on that indices, and then that depth first search function will go through all of its rows and all of its columns, I mean, its entire row and its entire column. And if it doesn\'t encounter one, then it will, then we increment. Okay, but if it does, then, then we don\'t.\nRed Maelstrom: Okay. Yeah I\'m okay with that. What would be the complexity of that?\nMassively Parallel Bandit: Sorry?\nRed Maelstrom: What would be the maximum complexity of this?\nMassively Parallel Bandit: So I think the time complexity, so initially, just for traversing it\'ll be like O of N squared, but with the depth first search function, we\'re going to at most be traversing m by n as well. Again, m by n again. So that we should be going all the m m to m by n again. So I guess that would be like in total O of n to the power four.\nRed Maelstrom: Can we optimise it?\nMassively Parallel Bandit: Yeah let me see, okay maybe\nRed Maelstrom: You just need the information like how many number of ones are in that particular column or that particular row right?\nMassively Parallel Bandit: Sorry say that again.\nRed Maelstrom: You just need information like how many number of ones are in that particular row or that particular column?\nMassively Parallel Bandit: Yeah.\nRed Maelstrom: Yeah so can you pre compute it?\nMassively Parallel Bandit: Yes that\'s true, yeah let\'s see. So maybe what we could do is having a one, so storing an additional, if we could expand each row and have like an additional value, let me think about this for a second. Okay okay yeah I think so another approach I\'m thinking of based off what you\'ve told me is maybe for like each row and each column we could let\'s see, if we had so for the first one is one, second one is one, third one is one. Then for each column and then yeah I guess you could store a top left variable to look at like I said this will be one, this would be one and this would be one. So, since I guess like since I guess the max you can have is max possible is three, let me see in this one. Over here we have. We have two, zero, one and then we have one one okay. So, that means this column can\'t have any. This one has zero and then this one can have one.\nRed Maelstrom: So like why do you measure number of ones in each column and each row, you can just iterate over the matrix and see each position right? So rather than calling your DFS now you know the answer in order of 1 time.\nMassively Parallel Bandit: So could you say that again?\nRed Maelstrom: So, you were, your initial approach was going through each and if it is one call the dfs right? Now rather than calling the DFS can you use this pre computed values?\nMassively Parallel Bandit: Okay, so, if I pass that into DFS then in the DFS I would know\nRed Maelstrom: You don\'t need to, you just need to know like whether this is only one in this row, whether this is only one in this column right?\nMassively Parallel Bandit: Okay. But if it\'s over one then we know that don\'t even check the column?\nRed Maelstrom: Yeah.\nMassively Parallel Bandit: Okay. So okay. So, I guess the first step would be the pre computations. So I could, I could pass and so I guess is the first step is just generating the value so I could store it in. Okay, so rows and columns okay. So okay, if you just store and just make an array of rows or columns anything so define lucky, special positions matrix. So, I guess I could have, call this. Row count and then col count now just pass in the indexes, now just pass in, the row count of i and col count of i, taking one pass and calling DFS. For i in range, for c in range. Okay so if matrix and we\'ll have the count over here. Oh first thing is pre populating. Okay so then we want to, so it makes this equals to zero, we want to increment the value so we\'ll count. We want to call, we want to call our DFS but with the DFS we pass in, we pass in r, c and we also pass in\nRed Maelstrom: Here you just need to check whether in that row and column the count is just one right? So do you actually, do you really need to\nMassively Parallel Bandit: Oh that\'s true. I think we\'re putting that in one of the bases but again that\'s also like I did say if. If col count of c equals 1 and row count of r is equal to 1. Then result, so in this case it would be true. So they\'re both true they\'re both true. They\'re both true. Okay, so it shouldn\'t happen every time. I guess. I could just check it for each. So the maximum possible is is like the number of rows right? If they\'re different sizes.\nRed Maelstrom: It could be minimum of rows and columns, right?\nMassively Parallel Bandit: Oh it could also be columns\nRed Maelstrom: It could be minimum of rows and columns right? The maximum possible.\nMassively Parallel Bandit: Okay.\nRed Maelstrom: Yeah, let\'s try to run this for the example\nMassively Parallel Bandit: Okay.\nRed Maelstrom: Yep that\'s correct, 15 from previous one. So, yeah, this works. So yeah, but these are the questions I had, what would the complexity of this second one?\nMassively Parallel Bandit: The space complexity would be O of N. Since we\'re storing, like a linear, a linear, there\'s going to be two to two linears. But it\'s but asymptomatic, that\'ll just be O of N, O of N space, time complexity would be O of n, O of M x N. Since we\'re traversing each row and each column.\nRed Maelstrom: Good. Awesome. I think, yeah, that make sense. So looking at feedback, I think. Only only thing like, you could have include, like in the first question, you somehow made an assumption that numbers are positive. Right? So, yeah, so so like do state out your assumptions. Don\'t make anything assumptions like that. Apart from that, like, I really like the way you came up with like an approach for the first problem. And then for the second problem. I think you struggled a bit about, you somehow there was an implementation error when finding out the maximum in the column, right. So yeah, but like, this helps, you were able to identify, rectify that. So it\'s good. I think, yeah, I think you need some implementation practice, like my suggestion would be to like to practice a bit more about like matrix kind of problem, because there was like, in the first problem, they want to take little hiccups in implementation, but in second problem, like it was easy to follow. And I think I mentioned you use right names for different variables and method. So yeah, I think like yeah overall it would have been strong hire based on implement performance, so yeah good job for that. Like, like, once you share the approach, right, right to discuss the complexity of that approach right away rather than waiting for the interviewer to ask you the question like what is the complexity mention it and write the complexity because you don\'t want to waste time on some optimal problem or you don\'t want to waste time. Okay. So, yeah, that would be one solution, I would say like, whenever you share the approach, follow it by the complexities, okay. So, yeah, so, here is what I used to do when I was practising. So, you know, on a leetcode or something I used to create a comment section and I used to write down the clarification questions for problem, which I can think about and then I will try to write down my approach in plain English words right? Followed by the complexity, so that I get in the habit of easily explaining or articulating mine solution or approach. So I will say this, like, if you can wait for for a while you will get in the habit of doing that.\nMassively Parallel Bandit: Okay. I appreciate that. I appreciate that. Thank you.\nRed Maelstrom: Cool. Awesome. Do you have a question for me?\nMassively Parallel Bandit: Um, I guess, was it one thing I\'m always nervous about, is like one of our ask if I can have a minute or two to, to think about the question like, how\'s that? Cuz I just, I always feel like I\'m taking too much time. Or like, is that a bad sign? Negative signal?\nRed Maelstrom: No that\'s not a bad sign in fact, if you are able to complete both of the question in 40 minutes, but so I don\'t think you needed much more time. Yeah.\nMassively Parallel Bandit: Okay.\nRed Maelstrom: That\'s a good question, like so clear communication. So yeah, rather than having an awkward silence, stating out like you\'re taking you\'re taking time to think about it. It\'s a good way to do it.\nMassively Parallel Bandit: Okay. Okay. Sounds good. Sounds good. Thank you so much.\nRed Maelstrom: Cool awesome. Do you have any upcoming interview?\nMassively Parallel Bandit: Yes. I have a few. A few interviews coming soon.\nRed Maelstrom: Awesome. Awesome. Yeah. Let me know how it went. Like all the best for your upcoming interviews. So yeah I\'m hopeful you\'ll do good in them also.\nMassively Parallel Bandit: Thank you. Appreciate it. Thank you.\nRed Maelstrom: Have a nice day bye bye.\nMassively Parallel Bandit: Take care. Bye.