We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Please read our definitive guide on Amazon's hiring process and questions
Python Interview with an Amazon engineer
Watch someone solve the unique shapes in a matrix problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Unique Shapes in a Matrix
Interview question
Find the number of unique shapes inside a grid of matrix. A shape is denoted by a grouping of 1s from above, under, left, and right. Example: 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 0 1 Total number of unique shapes - 2
Interview Feedback
Feedback about Cashmere Flamingo (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
3/4
How was their problem solving ability?
2/4
What about their communication ability?
4/4
Strengths - Candidate asked a lot of clarifying questions - Candidate explained the solution and approach really well - Was able to code out the solution without a lot of hints - Was able to provide the right space and time complexities Areas of improvements - Needed a lot of hints to arrive at the solution - Code written had a lot of bugs, few of which were self corrected but few of which had to be pointed out - Spent too much time explaining the algorithm which left less time for coding Advice for future interviews - Practice more leetcode questions in time bound manner - Clarify as many of the edge cases and outlying scenarios as you can in the beginning - Dry run the code yourself before saying done Open Notes 8th Feb, 2024, Coding DS/Algo Asked some clarification questions, checked in about the diagonals, checked about rotation Was able to separate out the problem into two halves Came up with DFS approach, was able to talk about traversal Needed a bunch of hints and counterexample around the storage and dedup Was able to code out the BFS properly without any hints Had a number of bugs If condition Row and col not added to Visited array Space and time complexity - Provided the right SC and TC
Feedback about Digital Avenger (the interviewer)
Would you want to work with this person?
YesHow 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
Interview Transcript
Digital Avenger: Okay, so before we get started, I feel that. Can you answer a few questions? That sort of helps me model the interview in a better format for anything that you might have in mind.
Cashmere Flamingo: Yeah. Okay. Basically I have a virtual final interview for intern position.
Digital Avenger: Okay.
Cashmere Flamingo: Yeah. So I would basically like to use this opportunity to prepare for my actual interview.
Digital Avenger: Excellent. Okay, that is mostly what I was going to ask. Okay, so it's for an internship position and you have that coming up. I'm assuming since the interview is targeted, the position is at Amazon.
Cashmere Flamingo: Yeah, position is at Amazon.
Digital Avenger: So you're in. Forgive me for asking, is this a bachelor's or a master's student?
Cashmere Flamingo: I'm a bachelor's student, so I'm a junior.
Digital Avenger: Okay. Third year, fourth year.
Cashmere Flamingo: Third year.
Digital Avenger: Okay. Excellent. The optimal time to do this. Okay, cool. I'll conduct the interview like that. You might get some behavioral questions. I haven't taken an internal interview in quite a while. I don't think you will. Not combined at least.
Cashmere Flamingo: Oh, sorry, can you repeat? Did you say we don't get behavioral questions?
Digital Avenger: You won't get it. As far as I recall you wouldn't get it combined with your coding interview because with all the other positions we do, for example as an SD one and SD two for sure, SG one. The sort of bar varies from time to time. It keeps going back up and up and sometimes it goes lower where we don't actually ask behavioral questions directly. It's the HM who asks all the behavioral questions. But for sure within SDE two, every interview conducted has like 20 minutes, 15 to 20 minutes of behavioral. And only the 35, 40 minutes is coding for you. I think most of it would be coding only.
Cashmere Flamingo: Oh yeah, because mine is a 45 minutes interview for sure.
Digital Avenger: Then it's coding only. Then we won't waste any time. I'll tell you a quick format of the processes. You'll get initial two, three minutes to do a quick round of introduction that we just did in our current interview. Obviously you expose more details there and they'll ask for more. I'll suggest sticking to a quick 62nd to 82nd intro. Don't exceed that because that's actually going to cut into your coding time. And nobody, and I frankly mean nobody, is going to grade you on your intro skills too much. Okay? So just have a quick 60 to 82nd introduction prepared for yourself. I know it feels a bit weird to do that, but have it, it's going to save you a lot of time and headache later. Companies. Then they'll introduce the format of the interview, which I'm going to do now. What language are you familiar with Python? Python. Okay, so we'll modify it to Python. Now, as an interviewer, I would not care either there or here about what the language you choose is. We do not simply put, what we do care is the code should be working. I don't want pseudocode, I want code that actually works.
Cashmere Flamingo: Okay. Yeah.
Digital Avenger: With that, we'll jump into it. Generally speaking, the last two, three minutes are reserved for the interviewee to ask the interviewer any questions, any questions, any questions about the work. And this is again me suggesting to you, please ask something. Do not say that you have no questions.
Cashmere Flamingo: Oh, yeah, of course.
Digital Avenger: Yeah. That paints a very bad picture if somebody says that they have no questions or nothing to ask. Let's say ask about tech stack, ask about what they like about working at the company. And yeah, these are some questions you can look up more online, but have those.
Cashmere Flamingo: Okay.
Digital Avenger: With that, we will jump into a question. Now, I'm going to paste this question. I'm not overly familiar with Python myself. Any way we could make a bunch of lines commented out, like beginning or ending of a comment?
Cashmere Flamingo: I think you can use this or you can highlight, and then if you do command this, then you should be able to comment.
Digital Avenger: Okay, let me just paste it.
Cashmere Flamingo: Yeah. All right, that's great.
Digital Avenger: Control. So we have started at eleven, six. Please read the question, ask me any clarifications, any doubts, anything that you need to get. Okay?
Cashmere Flamingo: Okay. Yeah. So the task is find the number of unique shapes inside a grid of matrix and we are given a 2d matrix. So from this the rows and columns are not equal. So I guess I can assume that the rows and columns are not going to be all equal, though there might be cases. Okay. And help me to find the number of unique shapes. Okay, looking at this problem, we have a shape right here. One. One. So are these ones supposed to represent the type of our coordinate which we dictate the shape?
Digital Avenger: Sorry, I didn't understand that.
Cashmere Flamingo: Can you repeat it? Told you to find the unique number of shapes. Right. So are we counting the ones, not the zero?
Digital Avenger: Yeah. So one are all the shapes. One is basically zero means there is nothing there. Okay. One is basically something is there and that is what represents a shape.
Cashmere Flamingo: Okay. Basically I see one shape right here. It's a two x one. And this one right here is kind of like similar to a triangle. There's four spaces available. And this one also has two. And this one also has two, which is equal to the other one. One here. So that's why I think the unique ship is two. So one question I have here is.
Digital Avenger: Sorry, I'll cut in here. And quick thing. This is something you should expect the interview to do as well, given that you're on limited time. So you think there are four shapes?
Cashmere Flamingo: Yeah, two shapes. So there's four in total, but there's two unique.
Digital Avenger: Two unique. Got it. There are only three shapes in total and only two unique. So we are connecting across diagonals as well.
Cashmere Flamingo: Okay. This one is also connected.
Digital Avenger: It's only one shape. There is only.
Cashmere Flamingo: Yeah.
Digital Avenger: Row number two. Row number three. Row number four, row number five. That one shape is connected.
Cashmere Flamingo: Okay. Yeah. So one question I have is basically, notice how these two are. Basically, they're spanning two rows. But what if you have a similar shape that spans two columns? Like, for example, these two, are they considered the same shape?
Digital Avenger: Right. Okay, wait. You have a big shape and there are some shapes that are part of it or sort of would fit inside it? No, they would be counted as different. So the only thing that qualifies it is not size, not pattern. Exact congruency. You familiar with congruency? Basically, it should fit exactly on top of each other, let's say one month. And then we have three ones, four ones. That's just an expanded shape. No, nothing like that. We would only two shapes. Two ones. So it should superimpose completely.
Cashmere Flamingo: So these two, the line 17 and the one right here. Right. 1112. They're not equal.
Digital Avenger: They are not equal because they would not superimpose each other. There is no rotation. We'll come to rotation. Possible. But let's stick to this now.
Cashmere Flamingo: Okay. Got it? Yeah. So the immediate approach I'm thinking is basically, I'm understanding that this is some sort of a graph problem, and we'll basically have to traverse the entire graph and see how many shapes are there. And we'll basically determine how many unique shapes are there, too, based on what kind of shapes we've received. So that's my initial approach. Yeah. Sorry, was I clear?
Digital Avenger: Yeah, I was saying that sounds very reasonable.
Cashmere Flamingo: Yeah. Okay. Yeah. Basically, I also count the diagonals. Okay. So I'll basically run a dfs on each. Each number in the graph that is a one. And one shows that node is part of a shape and we haven't visited yet. So basically, in the first row, the first one we visit is in the fourth column. And basically we will run a DFS here and we'll basically return the shape. And basically we'll zero these out so we do not visit. And the reason why we do this is so that we can actually save space. Instead of having a visitor set, we can use the in place grid and change these values so we can.
Digital Avenger: That's fine. I'd suggest keep a visited set. We don't want to modify the initial input.
Cashmere Flamingo: So you don't want to modify the initial input?
Digital Avenger: Yeah.
Cashmere Flamingo: Okay then yeah, I'll just use a set that tracks out which nodes being visited or not. And we'll only visit the node if we do not visit before. Okay. Since we visited this one here and this one here. And the next gift will run over here. And we'll visit these two. And we'll also visit this one and this one and this one because they're all part of a shape and they're connected. And then finally on the last iteration we'll visit 14, the last column here. And we'll visit the last column here. And that will be the end of our dfs.
Digital Avenger: Okay. So your dfs will visit these. Quick question here. How are you storing all of this? I know visited will keep a track of the cells you have visited, but you need the shape.
Cashmere Flamingo: Yeah. So I'm actually trying to think about how I can store the shape here. So let's see. Um. Okay. So one approach I'm trying to think of is basically maybe we can count the number of rows and columns that shape spans. And for example, this one will span two columns, so it has a width of two. And this one spans four columns. So it has a length of four. And out of rows and two columns. Right, sorry.
Digital Avenger: That would be still two columns, but four rows.
Cashmere Flamingo: Yeah. So two columns, four rows. And we know that these ones are zeros in between. So we'll have to basically, so one way I can think is basically for the shape, we'll have the width and the length and how many of the, from there we're basically, let me see. So how many of those, oh yeah.
Digital Avenger: Sorry, I was just saying you're on the right track. Keep thinking.
Cashmere Flamingo: Okay. Yeah. So how many of those out of there we're going to check how many of them have ones or zeros. So in this problem we have five ones and three zeros. So my hint is that somehow we can use those properties to determine if it's a unique shape or not. So in this case, I'll store how many ones we have and that will basically be 12345, width should be two length should be four. So this is basically one kind of way of thinking. Maybe we can represent it in each shape. I'll also try to think of a way we can break this rule.
Digital Avenger: Yeah. Because let me propose a sort of counter example. I'm going to change the existing array. Do you see the problem?
Cashmere Flamingo: Yeah, I see it.
Digital Avenger: So what do you think about what we need to store? How can we. We have the number of rows, we have the number of columns. Don't worry about space for now. I think you're getting a little hung up on that. Assume for a minute, stop optimizing space and see what else would you need to completely be sure that this shape matches another shape.
Cashmere Flamingo: Okay. Okay. So one alteration I have is maybe we can store the vertices of the outer edges. So let me see.
Digital Avenger: Outer edges, asum, the top, left, bottom right, those.
Cashmere Flamingo: Yeah. Okay. The unique shape.
Digital Avenger: Say, for a minute. Okay, so let me paint a picture here. You have the entire width of width and height of basically the shape.
Cashmere Flamingo: Right.
Digital Avenger: So any edge total, overall, it touches, you have it. Even if the shape is, let's say, a bit distorted like this. I'm painting a picture here. Give me a second. Let's say the shape is this. I'm putting that zero so that we have one shape. Now, the height will still be four, the width will be three. Correct, sorry, let me put this as zero as well. Correct.
Cashmere Flamingo: Sorry, can you repeat?
Digital Avenger: I was saying for this big shape, the height will be four, the width will be three. Correct.
Cashmere Flamingo: Yeah.
Digital Avenger: So we are touching on the most outside aspects. We are seeing how far the shape extends, even if it's just one thing. Extending now to compare this. And we are capturing the shape from here till here. From line 13, column one to line 16, column three. Now, if we have this entire grid with us.
Cashmere Flamingo: Yeah.
Digital Avenger: We would be able to compare it to another grid and see if it matches, right?
Cashmere Flamingo: Yeah, that would be possible.
Digital Avenger: So can we do that?
Cashmere Flamingo: Okay, basically what you're saying is that we're going to find the outer parts of how far our shape can extend. So in this case, we have the second row. So this shape is part of the second row. And from our dura, we can see that this shape is part of our first column and our third column. So basically our window was banned from the first row to the last row and first column to the third column, right? Yeah.
Digital Avenger: And we need to store all the data in it. Right. That's the only way to compare it.
Cashmere Flamingo: Okay. So after the DFS, I'll try to initially, not after, but I'll initialize a shapes array or a shape set we can use think. And I'll basically, after we finish the DFS, I'll basically add in the entirety of our shape here and we'll compare with the other shapes and we'll see if there are equal or if there is a similar shape. Then I'll basically not increase the counts, but if the shape is unique, then I'll increase the counts of unique shapes and I'll store it in the set.
Digital Avenger: That sounds reasonable.
Cashmere Flamingo: Okay.
Digital Avenger: Yeah. Okay. So you are using bfs for this, right?
Cashmere Flamingo: Yeah.
Digital Avenger: Quick question. Why not BFS?
Cashmere Flamingo: Yeah, so I was actually just thinking about BFS. Now that you've mentioned the if you run a BFS on here, then we'll basically add this node and then add its neighbors, and we'll be able to kind of track what's the max row, max column or the Min. In this case, we want to track the min column, the max column, the min row, and the max row because that will basically determine our rectangle. Judging from the observation of storing the entire shape, I think the DFS will be more appropriate in this case because if you use a DFS, it will be kind of hard to manage because we will have to basically get the min and max variables and return it back to our first stack.
Digital Avenger: Okay, sure.
Cashmere Flamingo: Go ahead. Yeah, I would say in this case we should use BFS. It'll be more necessary. So, yeah, let me just go ahead and begin the explain the BFS approach. So we're going to basically add the first node to our bfs and we'll basically add its neighbors. So it also includes a diagonal, but in this case the neighbors don't have a one. So we'll add this to our queue. And basically one thing to keep in mind is that we have to lose each one, right. Because if you just look at this one node, then we don't really know if it's because this graph is not connected. So if you just look at a single part, then we might not be able to visit all the parts and that will actually get a wrong answer. So we'll basically have to iterate through the entire grid. But we are also using a visited for our BFS, so we won't be able to look at each node more than once. So for example, we'll start one here in the last column and we'll visit all its neighbors. And after that, since our min row and min column is one, because these are all zeros, in this case the min row should be only the first one and min and max column should only be the last column. So we'll basically copy that size into our set. And based on that, I'll tell you.
Digital Avenger: What, given in the interest of time, how about you code it out for me? I think I understood your DFS solution.
Cashmere Flamingo: Okay.
Digital Avenger: You only have to code out a method that has a 2d array given to you as an input. Assume it's an integer array or whatever. Okay.
Cashmere Flamingo: Okay. So we're always going to be given a 2d array.
Digital Avenger: Yeah. You don't have to input anything and the return output is just another integer.
Cashmere Flamingo: Okay. Yeah. So is our numbers in our board, are they going to always be a string or maybe a number?
Digital Avenger: How is it numbers? I'm fine with either a number or a character. Whatever you prefer is fine by me.
Cashmere Flamingo: Okay. Yeah. Then I'll use a number.
Digital Avenger: That's fine.
Cashmere Flamingo: Okay, so define, so I'll call this function count unique shapes. And this is going to take a board and our board is 2d. So initially, for the sake of traversing, I'll initialize two variables, rows and columns. And this will basically be the length of the board. So how many rows and board zero. And this is how we can get the length of columns. And since we're implementing a BFS approach, we also need to implement add a queue in the python. We can do this with DQ. Do you want me to write collection DQ or is that fine in the actuator? Fine.
Digital Avenger: Don't worry about the import. You have the import, right? Forget it. That's not.
Cashmere Flamingo: I'll have to iterate through all the rows and columns. And we also want to have a visited, right, because we don't want to visit the same node twice. And we also want to have a shape. So this is, so we don't visit, we can count the unique shapes and we can also count number of, we can just say unique shapes. And initially we'll set it to zero because if there are no shapes at all, then our answer will be zero. So first we have to check to see if you can run a BFF here or not. So how do we do that? We'll basically look at if RC invisited. So in our visit set we're going to store it as a tutor. If RC invisited then we're basically or RC. So board rc not equal to zero. This means that this is not part of a shape, so we should ignore it in this case. So just say continue here. And then if our if loop is not triggered, that means that this is a valid shape. So we'll basically use our bfs. So before we initialize our bfs we have to add the first element to our q. So we're going to Q append and in this case we're going to store the r and c. So this is how we're going to traverse the bfs. So we're going to use a row and column and we also want to have a min row and min. So min row and max row. So this is basically going to be used to determine our shape so how far our shape spans. And initially I'll set them both to r because we know that at least there is length one that spans the shape since the shape exists. And we'll also have a similar value for min and max column and default also be set to c because that's the current row and column we're on and yeah, so let's get started with the bffs. So while Q. And we're going to have to iterate all the elements in our queue. So we're going to basically RC. So RC is basically what we're storing in the DQ. That's what we're going to pass but to make the variables not repeated. So I'll just set nr, node r and node c. So this is our current r and current c of our node and we'll do Q dot, top left because we want to get the leftmost elements we're going to check. So min row first we have to see that if our new node has a smaller row or column then we have to update that. Right. So we're going to update min row and node r. And similarly for our max row we're going to update the max row and the current node r. Yeah. And we'll do this similarly for our columns.
Digital Avenger: Columns.
Cashmere Flamingo: Yeah, so min column, it goes min column and c or node c and what is it? Max column and node c. Yeah. So we're doing this basically so we can track the minimax of our bfs just in case. Maybe if this node we already visited or then we'll basically have to not do this. But I'll make sure we don't ever add a visited node. But I'll just do this just in case for now. So it visited, then we're going to continue because we already visited this node and now what we have to do, so we have to traverse the edges, right. So we're going to have to symbolize the edges because this can go always I'll have a directions and this is basically going to symbolize our new row and column. After the edge. After we go through the edge. So zero, one first. Basically we move the column by one and zero, negative one and 10. So 10, negative 10. And we also mentioned that we will have to traverse a diagonal, right, right.
Digital Avenger: Eight directions.
Cashmere Flamingo: Okay. So using the example here. So we're on row two, t, right. And we want to visit here. Then how will we do that? Well, we have to go down one column and go up one row. So we'll have to basically subtract both row and column. And how do we get to the next one here? Well, basically to do that we'll have to go one row down and one row, one column. Right. So we'll have to go one, one. And also we have to visit here, right, because this is the diagonal and we also have to back the antidiagonal. So in this case, our row is in the second row, our index is two and the column is one. But we want to go one column to the right and one row behind. Right. So to do that we'll do negative eleven. Yeah. Similarly we have to basically visit this here. So to do that we'll basically go one row down and one column down. So we'll do one and negative one and these will basically be all the possible combinations that we can go through. So now we're going to do a bfs for Dr. So Dr. Is how much we're moving the direction of R and Dr. DC is how much we're moving the direction of r column. And we're going to loop through each one. And we have to first check if this new direction is inbound. Right. So we don't want to go to the end of the list or end up the matrix. So we'll have new r equals R plus Dr. New C equals B plus C. And we have to check if this is imbalanced. We did row and columns here. So I'll just do row and zero less than, new column has to be less than the number of columns. New R and new C should not be invisited since we passed through the previous. Then we know that this new row and column is a valid index. So we can just directly reference it like that. And this won't draw an error because we already checked if it's in bounce and not equal to zero or zero. Because if it's zero, it's not part of a shape. Then we're basically going to continue here. Okay. And if it is, so if this test case does not pass, so it means it's a valid, then we're going to append TRq. So we'll append the new r and new c. Yeah.
Digital Avenger: Okay, hang on.
Cashmere Flamingo: Yeah.
Digital Avenger: Wait, can you look at the logic again?
Cashmere Flamingo: Okay, yeah, sure. Oh, yeah, sorry. Not invisited. Invisited. Not invisited means that we didn't visit invisited and board. New r news B should not be equal to zero. Okay. Should be equal to zero.
Digital Avenger: The problem is that, let's say new r is greater than rows, then you actually. Yeah, let's assume new r is greater than rows. What do you think will happen?
Cashmere Flamingo: So if new r is greater than rows, right, then we know that this first statement is not going to pass. So we don't even have to look at the previous statements. We are already throwing false here.
Digital Avenger: If new r is greater than rows, the first thing will immediately fail, right? Yeah, this will fail and the condition will fail and it will append it. Do we want that?
Cashmere Flamingo: Oh, but I put continue here. I'm pretty sure it should stop the for loop here and then go back.
Digital Avenger: Wait, but this will only continue if the entire condition matches. Correct. So new r needs within zero and rows.
Cashmere Flamingo: Oh no, it fails even if one of them doesn't meet, because this is an and statement. So if it's an or, then it has to be. Sorry.
Digital Avenger: What I'd suggest is don't do this. Make it all of it. So don't try to create the continue condition. Try to create the condition where you actually need to append, because that condition requires very specific things.
Cashmere Flamingo: Okay, yeah, sorry. I'll keep that in mind. After that, we'll basically add it to our stack. And then basically after we finish the loop. So after our for statement is completely finished, then we have to basically get the image right. So image equals. How should we do this? So we want the board and we want the min row and the min column. And we also, and we also want to add one here because we want to look at, because in python in this case, you don't look at the end, but we do want it in this case. And we'll similarly have min column and max column plus one. So this will be our image. So in the previous sample it'll be like this square or rectangle, and we have to check. So if image in shape, right. So if you have this shape already, then we're simply going to. Okay, I'll just say image not in shape. If this is the case, we actually have to add it to our shapes. We'll add the image. Okay. And we'll also have to increase the number of unique shapes by one. Sorry. This should run after we're done with our pfs. Okay. Yeah, we can get the main row, max row because they're defined here. So yeah, this will not throw an error, I believe, while Q. Right, this is our bfs. And after we finish our bfs, we're going to get the board and if the image is not in shapes, then we're going to add it to our shapes and we're going to increase the unique shapes. If it's in shapes already, then this is not going to run. And then we'll basically have to do nothing to change the shapes or unique shapes. And after we list through each node and row and column, we're going to simply return number of unique shapes. Yes.
Digital Avenger: Okay, give me a secondary. Imagine for a second you have going through your code. Let's assume you have new r equal to dose and new c equal to. What do you think is going to happen?
Cashmere Flamingo: Okay, so if new r equals rows, since new r equals rows, then we will fail this because this will be out of bounds.
Digital Avenger: Okay, but the first part will run. It will fail, but it will still go to the or, right?
Cashmere Flamingo: Yeah, sorry. So yeah, it will basically fail this case. So we won't basically add it to our queue.
Digital Avenger: So you'll continue. Okay, makes sense. Now let me test this part. Let's say this is one comma zero.
Cashmere Flamingo: Yeah.
Digital Avenger: And let's say you started this from zero comma zero. So one comma zero is also one.
Cashmere Flamingo: Okay, so I started at. It went to 10.
Digital Avenger: Yeah, it went to 10. Now you are going through this if condition.
Cashmere Flamingo: Okay then. Oh, sorry. It should be. Wait. Okay. Yeah.
Digital Avenger: You'll continue, right? That's what I. Yeah.
Cashmere Flamingo: Okay, my bad. I really shouldn't have done this way. So we'll say if new r is less than zero. And we'll say if.
Digital Avenger: What I'd suggest is why don't you let go of the or conditions, just do all the and conditions where new r and mu C actually fit what you needed to fit. Like new r should be less than, greater than, equal to zero, less than rows, same with new column. And it should not be in the visited and board. New R. New C should be one. Okay, only condition where you would append it, right?
Cashmere Flamingo: Yeah. Okay. Yeah, I'll just make the new code. So this will basically check if our condition satisfied so we can add it to the queue. So if new r is inbound. So button rows and columns. And so we don't want this to be invisited and er, not invisited. And we want this to be a one board equals one. So in this case we can add it to our queue and we will add it to the queue. And if not this will simply not run.
Digital Avenger: Yeah.
Cashmere Flamingo: Okay.
Digital Avenger: Barring that you think it's done.
Cashmere Flamingo: I'll just try to evaluate through like an example maybe.
Digital Avenger: Oh sure, go ahead please.
Cashmere Flamingo: Yeah, and just check for example. Okay, using this we have one unique shape and there's one more here and this one is also part of it. So we basically won't count. So there's two unique shapes this answer, is that correct?
Digital Avenger: Sorry.
Cashmere Flamingo: So there's two unique shapes in this test case, right? Yeah. So basically initialize a row and column. So like the four, like the 40 and Q is DQ. Is there a case where we never receive a board?
Digital Avenger: It's possible. Let's say it could be null, but let's assume null case you don't have to handle. But yes, the board could be empty. The board could have only zeros. Those cases are possible.
Cashmere Flamingo: Okay, let me see it. Yeah. So we'll also fix this statement then. So we basically want to, for our simplicity sake. So we'll run it only if it satisfies our condition. So we'll set rc not invisited and four rc equals to one. So this is the only case when we actually go through our algorithm typo. So we initialize a Dq visited set and shape set number of unique shapes and we're going to loop through each row and column and we're going to see if the RC is not invisited is equal to one. Right. This is the only case we can actually visit that node. So we're going to go to the min row, we're going to set the min call Max initially to our current and we'll start bfs here. And initially we'll get our first node which we just considered and we'll visit its neighbors. So we don't even actually really need this because we're already checking here. So I'll just remove that for readability sakes. Max column. We're going to update these depending on our most recent node and we're going to basically loop through the directions. So there's eight of them. 345678 yeah. And we're going to get the new r muc by adding the new edge. And we're basically only going to add this if our satisfy also right here. So we wanted to add new r and new c here because we just visited. Yeah. So that was one error I had in my implementation. So we have to check if it's less than equal to rows, greater than zero, greater or equal to and greater or equal to zero and less than columns. And they're not invisited and it is a valid index. So one is a valid shape. Then we're going to add it to our visited and we're going to add it to the queue, this new node. And then, yeah, basically we'll loop through that and after that we'll get the image. So we're going to get the board. So min row, Max row plus one, because as I mentioned, python doesn't look at the last one and similarly min and Max. And then since this is basically going to store a 2d array. Right, and python can check if each one is same.
Digital Avenger: Okay.
Cashmere Flamingo: Yes. If image is non inches, then we're going to add the new image star shape and add the unique shapes.
Digital Avenger: Few things here. Nicely done on the, I think there anyways over time. So we'll cut the interview part here and now I'll take the next ten minutes. I think we'll go over two, three minutes, but I'm okay with that. I hope you are too.
Cashmere Flamingo: Yeah, that would be very helpful.
Digital Avenger: Okay, so now we'll go over some feedback, some salient points I'll highlight. So one thing I want to highlight is like, you might have heard me sort of typing a lot. That is to be expected. And at least you weren't looking at me. But when you actually have an interview and the person sort of faces on the screen, please expect a lot of typing. Copious note taking is part of the Amazon interview process. They would be taking notes, you would hear the sound of their keyboard. You may see them looking down. I forgot to mention this in the beginning. Some interviews mentioned in the beginning. If not, you should know this now. Nice job on the adding the visitor add. This was one thing I was looking at, because otherwise the code would not work at all. This was a bit of a big miss. Next part is, let me ask you, what's the space and time complexity of the solution?
Cashmere Flamingo: Okay, so first of all, we have a visitor set. Okay, I'll just think of the time complexity. So since we're visiting each node only once, our board is a m by n board, so m rows and columns. So our time complexity will be m by n because we will have to visit each node and our space complexity. In this case we're adding all the different combination of coordinates into the visited. So that would also be m by n. And we also have to store our unique shapes. Right? Yeah, but we also know that we do not visit the same node again, which means our unique shapes will be unique itself. So I think the time complexity will be m by n, where m is the number of rows and m is column, and similarly that will be the same space complexity.
Digital Avenger: Makes sense. One thing, and at this part, even I'm a little unfamiliar with Python. The 2d set that you have maintained, the 2d array set shapes that contains 2d arrays, don't you think the checking will take some time there, checking whether this shape is unique or not? Are you familiar with hash functions and collisions?
Cashmere Flamingo: I do know them in theory, but I don't really know it in implementation.
Digital Avenger: Never mind. I think you should be fine there. Okay. Now, coming to this, I think we took a little bit longer than you would have in a 45 minutes interview. But I will also grant you this was a little more complicated question than you would be expected. So I'm going through my notes here. You did provide the right SC, the space and time complexities. That's good. Your clarification questions were good. I did like that you explained most of your situation quickly, in the sense quick part was missing, but you did explain everything as you are coding. That was well done. You did need a bunch of hints around the sort of, what do you call it? The storage part, and how to sort of deduplicate it. There were a few required hints from my side and a little more than I was expecting. But given that it's an intern position, it's not overly bad.
Cashmere Flamingo: Okay.
Digital Avenger: But yeah, one final point that I'd like to point out is there were a number of these minor mistakes that it took you a while to figure out. The if condition visited. Add, I think the line 29 conditions. So that was invisited. That should have been not invisited. These are the sort of things that one does expect you to already have a handle on because it's fine if you can't figure out the overall algorithm happens. It can take a few tries. It can take a little while to figure it out. But these are things that you already know. It's not like you didn't know them. It's not like this is something new. So nomenclature was good. That is something I really liked. You sort of tried to stay as close as possible to what the right nomenclature should be. You didn't use just ijK. That doesn't send a bad picture. Sorry, a good picture. You used a deck. So using a deck was also good for BFS. But I think a deck is the only choice. You can take directions out I feel that is something you should have figured out on your own. But you do realize that the directions array is a static thing that could exist before this loop or even outside of this function, right?
Cashmere Flamingo: Yeah. Okay, so you mean like putting this to the end like a global variable?
Digital Avenger: Yeah, you can make this a global variable or just declare this after 926 before the for loop doesn't need to be declared every time. That's all I'm saying.
Cashmere Flamingo: Okay.
Digital Avenger: Other than that, code was good. You're able to figure most things out. So yeah, on balance I'd say you clear, but it's not a full thumbs up. It's not more or less on the fence leaning towards green. That's how we put it at Amazon. I would go with mildly inclined but willing to change my vote if I see same pain points that I saw in mine. Because repetition, like if I see some minor issues now as a one off, they're okay. But if I see them again in somebody else's interview, that sends a very bad sign. That sends a bad picture that, okay, you're going to do this again, which means there is a possibility that this would happen in real life as well. So that is sort of a clincher. Try to make sure these small things definitely do not occur again.
Cashmere Flamingo: Other than that.
Digital Avenger: One point about clarification as well. Ask these edge case clarification quickly. In the beginning you asked a few small clarifications which were good. You also clarified the diagonal part and checked if your understanding of the example worked. That was well done. A lot of people miss that. They assume that. That's why I generally gave the example I gave because people generally assume those three shapes are only one shape and assume that there are overall four shapes. So unless you clarify with me, you would miss the part that diagonals are part of the same shape.
Cashmere Flamingo: Yeah.
Digital Avenger: But check the null empty and this is just a tip. Check the null empty and those kind of edge cases quickly in the beginning itself. Ask them that. Let's say the input is null, the input is malformed, the input is empty. So have that.
Cashmere Flamingo: Okay? Yeah.
Digital Avenger: The same thing would have worked with DFS as well. Frankly. I mean, we wouldn't have seen any difference, to be honest. Your maintenance of max men would have maybe made a difference. But other than that, no real difference. Coding skills are, I would have to say you are able to code out all of it. And this is the frankly speaking, this is the main reason, if not the only reason, why I would say you clear it because this is a big code and sure there were some minor mistakes here and there, but you were able to code out most of it with more or less no help from me. Sure, once we fixed on the algorithm that took hints, but coding it out is also a bit of a challenge and not everyone can do that. The fact that you were able to do that is a very good sign for you. That is what sort of tips scales in your favor.
Cashmere Flamingo: Okay, so the main things I have to work on is basically fixing these small errors and quickly discussing the edge case. Right. Because I was kind of using too much time early on.
Digital Avenger: Yeah, I had to cut you off saying that. Okay, we need to move on to the code. I didn't write that because that wasn't part of the feedback. Okay, so once this interview is done, I will provide detailed feedback to you and I will highlight some of these salient points and you can go through my notes. I'm not extensive in this case because I've discussed most of it with you already. But 25, 30 minutes discussing the problem is not the right approach to take because at the end of the day, no matter how much you explain it, I do need to see functional code. Okay, so if you take way too much time explaining the code and you have no time left to work it out, no time to actually write it, that's just not going to work out. Okay, so take 1015 minutes, go through the clarifications very quickly. Take only five, seven minutes to go through just the clarifications in the beginning. Stop worrying about anything else. Just go through clarifications, then work on the algorithm. And at 20 minutes, mark, generally 20 to 25 at most. I wouldn't go till 25, I would keep it to 22, 23. You should start coding in a 45 minutes interview. You should have started coding at 22, 23. And assume this is again a pro tip here. The requirement will be more or less the same. Nobody will ask you to input anything. That never happens. No interviewer is ever going to ask, like do a C in, c out, anything like that. You'll always be given the input directly as a function parameter. And the answer is more or less always supposed to be returned, never printed out. But even if it is printed out, it's a quick line, so you don't have to go into in depth of that or passing through the input. Okay.
Cashmere Flamingo: Okay.
Digital Avenger: Thing else I can help you with?
Cashmere Flamingo: I'm just curious. Generally in a 45 minutes interview, you just go through one question.
Digital Avenger: Depends on the question. Okay, I don't have time to ask this, but normally I would hang on let me give it, this is a question that I would definitely. You can copy paste the questions or I will paste this question in my feedback as well. I think we both get a chance to put up feedback after this. Please provide me feedback as well. This is just. Yeah, so in this question you see like note on the question or see it normally we would go through this and time permits. I would go through either an extension of this or a different question, a much smaller, similar size question than the current one I asked you. But yes, we'd go through either two questions or one question plus extension. So in this question, if you read it, read it, then I'll tell you what the extension is.
Cashmere Flamingo: Yeah, I think this is like a bucket sort question. So since the arrays are on non negative integers, then we'll basically put them in their respective location and then we'll find the first one that's not in their location.
Digital Avenger: Yeah. That is one way you can work it out. If you do it in place, no extra space is used. If you try to do in place. There are some edge cases you have to consider. Other than that, yes, your solution works. If you maintain a set or a hash set or a hash map, you can just check starting from zero. If the number is not there, the first number that you encounter that's not in the set, that gives you the answer. Now the extension of this question generally I ask is, let's assume the array is sorted. Currently, array sorting is not given the example I give specifically sorted so that it prompts the user to ask. Because people generally assume that the array is sorted. They even write out an algorithm based on the fact that the array is sorted. Then I have to point out, I haven't mentioned that anywhere. Why are you assuming that? Now that I tell you the array is sorted, what will you do?
Cashmere Flamingo: Sorry, did you say you sorted the array?
Digital Avenger: Assume that the array is also sorted. It's all the same conditions. Numbers are unique, non negative, but the array is also sorted.
Cashmere Flamingo: Okay. Yeah, that'll be very simple. So we basically have to not present array. Okay. So yeah, so we'll basically start at zero or one, right. And then we'll look at the first index. And then if that index is like, let's say one wasn't here, then that will be the smallest non negative integer.
Digital Avenger: So that will take a full traversal. It's the same time complexity as the previous one.
Cashmere Flamingo: Yeah.
Digital Avenger: So what have you gained? My sorting, the array has not added any value to.
Cashmere Flamingo: It. Yeah, because previous implementation doesn't matter if it's sorted or not, right?
Digital Avenger: Yeah. So how about we try to come up with something that uses the fact that it's sorted.
Cashmere Flamingo: Okay.
Digital Avenger: What is the main algorithm that comes to you when I talk about sorting or let's say post sorted? We have already something that is sorted and we want to find things in there.
Cashmere Flamingo: Okay, so, okay, yeah. So if they are sorted, basically, so we can say it's like 1568, these are all sorted. And the answer to this one would be two. Right.
Digital Avenger: Would be zero. We are starting with zero.
Cashmere Flamingo: So it would zero also counts. Yeah. Okay. If that was zero, then answer would be one.
Digital Avenger: Right.
Cashmere Flamingo: Okay. One way I'm thinking we can do this.
Digital Avenger: Maybe.
Cashmere Flamingo: Guess so. See? Um.
Digital Avenger: Okay. Do you want me to suggest something?
Cashmere Flamingo: Yeah, sure.
Digital Avenger: Okay. How about we use binary search?
Cashmere Flamingo: Yeah, so I was thinking about that because we have to reduce it to log n if you want it better than n. Right?
Digital Avenger: That's an excellent way to think about it. Like if it's n and somebody asks you to reduce it, you are right. We should go with login. How many algorithms do you know that work in login?
Cashmere Flamingo: Okay, yeah. Okay. Let me think. Okay, so, yeah, so we're basically going to.
Digital Avenger: Let me expand the example that might actually help you out. Now, if you conduct binary search on this, what do you need to know and how do you split the array? What is the condition that tells you whether the answer lies in the left or the right?
Cashmere Flamingo: Yeah, okay. How I would do it is basically I'll look at the length, right, so it's 34567. And if they're in order, then this should be six. But there's a here, the middle element should be half, so it'll be basically like three. We'll look at our middle and if the middle is greater than three, then that means there's this integer we skip. So we are going to the left and then if not we're going to go to the right.
Digital Avenger: That would work as well.
Cashmere Flamingo: Yeah.
Digital Avenger: Another thing you could check is can you check with the index, the same thing you were doing last time, you can check with the index as well, right?
Cashmere Flamingo: Yeah. Okay. Yeah. So basically we'll get the mid to some index. So in this case length of six, we'll say three. And then we'll check the index of three. And then since it is correct, then we go to on the right portion. Is that what you're mentioning?
Digital Avenger: Right. Yeah. If the value at the index is equal to the index, that means everything to the left is pick and fun. So the answer lies, if not answer lies. To the left.
Cashmere Flamingo: Yeah.
Digital Avenger: So yeah, I'd suggest practicing a little more. And these are the sort of questions that are asked. So the speed at which you come up with these needs to be a little bit more. Okay, when's your interview? If you don't mind.
Cashmere Flamingo: Just one more question. But do you guys ever ask like bid manipulation type of questions in these 45 minutes interviews?
Digital Avenger: Sorry, what kind of questions?
Cashmere Flamingo: Bid manipulation.
Digital Avenger: Bid manipulation?
Cashmere Flamingo: Yeah.
Digital Avenger: Some interviewers might. I have never seen anyone ask that ever.
Cashmere Flamingo: Okay, thank you.
Digital Avenger: I can't rule it out, as I said, I can't rule it out, but nobody I have ever known or seen asks that because, see, most of the questions that come up, so I've given you just the exact question. Like given an array, find the number of unique shapes, these kind of things. Questions are generally framed around real life problems. And bitwise manipulation is not something we encounter as software developers a lot. Most of the people who work in normal jobs, unless your job is hyper specific, does very something specific related to that. You don't encounter that and you don't ask that because you don't use it in your own job. So answering it yourself would be a bit of a challenge that's rarely asked, if ever.
Cashmere Flamingo: Okay, yeah, that's all I have for now.
Digital Avenger: Okay.
Cashmere Flamingo: Yeah. Thanks for the extra time.
Digital Avenger: Sure, no worries. I'll provide a detailed readback to you with most of the stuff we have already discussed, but at least you have something in writing and later on to check. Okay, yeah.
Cashmere Flamingo: Thank you so much.
Digital Avenger: Cool, thank you.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
