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
Go 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 Full Metal Slide Rule (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
4/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4
Strengths - Clarified the question before jumping to the solution - Candidate was able to come up with the algorithm with minimal hints - Provided the right space and time complexity - Coded the solution with only one or two bugs - Good modularity in code - Was able to come up with a workable if inefficient solution to rotation extension Areas of Improvements - Use better naming convention than i,j - Check major parts of logic before signing off on a function Advice for future interviews - Practice random questions on leetcode in timebound manner to get used to new kind of questions Open Notes 13th Feb, 2024, Coding DS/Algo Clarified the diagonals and congruency, rotation Was able to come up with shape storage as well as shape deduplication Needed a minor hint DFS vs BFS - both would work Space and time complexity - correct Used i, j which is not good, but other than that okay naming Was able to code out the solution with more or less no hints Good modularity in code Missed shape re-referencing to origin Rotation extension - Workable but inefficient approach Second question Had a number of bugs
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: Hi. So before we get started, do you mind if I ask you one or two questions that sort of help me calibrate the interview properly?
Full Metal Slide Rule: Okay. I don't have any questions. Okay, go ahead.
Digital Avenger: Mainly the question is around, like, do you have any interviews lined up and which company, how long, basically from now. Is there anything specific that you're looking from this interview practice?
Full Metal Slide Rule: Yeah, I will have an interview, formal interview in coming weeks. So before that I want to have some practice. So what's the content of practice? I think mostly on algorithm, but whatever is related to the interview process, I'm just glad to practice and let someone else to help me.
Digital Avenger: Okay, got it. Can I ask which company the interview is for?
Full Metal Slide Rule: So I'm going to interview for mental.
Digital Avenger: Okay. At e six.
Full Metal Slide Rule: I just senior engineer.
Digital Avenger: Okay, got it. Sure. Okay, that makes sense. In the spirit of full disclosure, I am a wire at Amazon, so the process may not be exactly the same. Most of the things, in my opinion, will be the same. How they ask questions, what they judge. So basically, e three and e four, that's the one and two levels. I think the questions have the same more or less judgment criteria. E three has almost like, if she solves the question, you're done. E four is the modularity should be reasonably okay. You should also be able to solve the question. And nomenclature should be okay. Not using ijk variables. At e five, it does go a little bit up because at Amazon we call e five l six here. So l six, it does go a little bit up. They do look at all of these. They definitely have to be there. Nomenclature, et cetera, should be there. They also look at a few other things, in a sense that how you solve the question and the follow ups are definitely there because they'll change the same question and ask a few different follow ups. So we'll talk about that at the end of the interview. So how I want to frame this interview is we'll start in the next minute or so, go through a coding problem in the next 15 minutes, spend the last five to 10 minutes discussing some of the salient points of the feedback that I have. Obviously, I will be writing a detailed feedback at the end of this. I think we both get a chance to write it. So you're writing that, and then you can ask me any questions you have. Anything like that makes sense.
Full Metal Slide Rule: Okay. Makes sense.
Digital Avenger: Okay. Without further ado, I'll paste a question. Which language is your preference?
Full Metal Slide Rule: So I'm going to use the go long for most of questions.
Digital Avenger: Go. Okay, so I've pasted if you can see it.
Full Metal Slide Rule: Yes, I can see the screen.
Digital Avenger: I'll paste a question here. Can you see it?
Full Metal Slide Rule: Yeah, I can see it. It's called find the number of unicorn. Shapes inside of merge. Okay. Let me read this question and try to understand. Example, the total number of unicorn shape is two or minus two is two right. The unicorn shape is two. Okay, it's shapes. Okay. So you preview.
Digital Avenger: Feel free to ask me any clarifying questions, anything you have in mind.
Full Metal Slide Rule: Yeah, the description, tell me the number of shapes is two right. Which means from my understanding, the definition of shapes, it's just the shapes according to definition. So there is two shapes means there is two. One red, horizontally, vertically or horizontally. As long as these two shape can be totally overlapped, we can regard that's the same shape. Is my understanding correct?
Digital Avenger: Correct. Okay, let me ask you one question. How many total shapes do you think there are in this grid? Not unique, just total.
Full Metal Slide Rule: Total shapes. It's four for my. There are four shapes. Unique shape. Okay.
Digital Avenger: We do connect the diagonals. So the first thing that you see in line 1818 has then connected to column two, which goes down to 19. Column two which comes down to 20. Column one. So they are connected. Diagonals are connected. So that's only one whole shape.
Full Metal Slide Rule: Oh, I see. Okay, I see. So all the numbers one, as long as they are connect it vertically, horizontally or diagonally, they are considered one shape. Okay.
Digital Avenger: Yeah.
Full Metal Slide Rule: Okay. So let's say if one shape is turned to 90 degrees or 180 degrees, does that consider to another shape.
Digital Avenger: Excellent point. So rotation, assumed for a minute is not part of the equation. We'll discuss rotation later. But for the minute, assume rotation is not part of the equation. So it has to exactly fit. No 90 degree turn. No 180 degree turn. No 270 degree. It has to fit as it is.
Full Metal Slide Rule: Okay. So far I think I understand the questions. They're connected. One. Rotation is considered as different shapes. Okay, I think I understand these questions. Okay. Let me think about how to solve it. Sure. Okay.
Digital Avenger: Take a few minutes to think about it, then we'll discuss it. If we both agree on the approach, then you'll call it out.
Full Metal Slide Rule: Okay. So yeah. To be honest. Excuse me.
Digital Avenger: Yeah. Sorry, you said something?
Full Metal Slide Rule: Yeah. So the scrim is changed to a blackboard. Change to a whiteboard.
Digital Avenger: Okay. So at the bottom left, I think you clicked on the toggle whiteboard. Click it again. It should go away. You'll come back to that.
Full Metal Slide Rule: Okay. To be honest, I never encountered this problem before. So the first problem is how to represent the shapes. Okay. How to represent the shapes, how to express the shapes.
Digital Avenger: Okay, let's think about how to break down the problem first. So how would you break down the whole problem?
Full Metal Slide Rule: Yes. So the first question is how to gather the position of one shakes. How to exhaust the position of one shapes. Yeah. So the idea in my mind is just collect all the position of connected polarizations such as. Can you see my crystal?
Digital Avenger: Yeah, I can see it.
Full Metal Slide Rule: Okay, so let's say for this shape, so I will save the position of this one and this one and then this one and this one and this one. So I have array which contains all the position of this point.
Digital Avenger: When you say partition, what exactly does it mean?
Full Metal Slide Rule: Position means the index. The index of X and Y.
Digital Avenger: Okay, position, you'll say the coordinates.
Full Metal Slide Rule: Yeah. Coordinate. For this one we will have. So for this one we have 10.
Digital Avenger: Got it? I think I got it. Yeah. Understood then.
Full Metal Slide Rule: Yeah.
Digital Avenger: This sounds reasonable.
Full Metal Slide Rule: Yeah, we have one. One.
Digital Avenger: Okay, you need to write everything. I understand the point you're making.
Full Metal Slide Rule: Okay, so let's say.
Digital Avenger: We have identified the shapes. Now the point is to deduplicate them, correct?
Full Metal Slide Rule: Yeah, to deduplicate them. Okay. How to derelicate them. First. Let's, let's try to guess. So let's start with the laptop positions coordinate. So we can let's say if we want to go through all the shapes using the DFS. Okay. So for the first one, we record the relative coordinate as zero. And the second one. Recorded is one and zero because it moved right. So for the X exit, we just move right one step.
Digital Avenger: Okay.
Full Metal Slide Rule: The third one relative to this one, we can take the retail position to the first one. So it will be eleven.
Digital Avenger: That makes sense.
Full Metal Slide Rule: Okay, for. The third one, for the. First one, is it zero.
Digital Avenger: Comma, two? Yeah.
Full Metal Slide Rule: And also as well, zero. Three.
Digital Avenger: Okay, so that's how you got it.
Full Metal Slide Rule: Yeah. Okay, so let's say if the shape like this, we need a constant order of the DFS. So we will go like this. Can you see my cursor? So we will go right down. And this one, this one. Then the right one. To do that, we needed to have a consistent direction to integrate. We will have the left. Up. Right. Okay, can I suggest something? Okay, sure.
Digital Avenger: I understand what you're doing. You're basically using bfs to change the coordinates. How about we get all the existing coordinates? Let's assume we have all the existing coordinates as it is. Then can we change them to this relative format with just one quick change? Let's assume we have all the existing coordinates.
Full Metal Slide Rule: Three.
Digital Avenger: Is there a way we can change the first line into the second once we get all the exact coordinates with like not changing them in the DFS? You are right. We could change them in the DFS. Or could we do something after getting all of them?
Full Metal Slide Rule: After we getting all of them, can we do something?
Digital Avenger: Convert line 23 into 24. Do you think there is something we could do?
Full Metal Slide Rule: 22, 23, 24 we can do. We can do what we can do.
Digital Avenger: Basically we are trying to rereference the entire shape around the Origin point, right?
Full Metal Slide Rule: Yes.
Digital Avenger: In normal rereferencing, in basic cartesian plane rereferencing, what do we do? We consider the main point as origin, right.
Full Metal Slide Rule: So we just minus them, right? Yes. Okay.
Digital Avenger: So let's have. Yeah, either way we come up with line number 24. Then what do we do? We have come up with line number 24. What's the next step then? Either through dfs or through just subtracting the origin point. Okay, we have come to line number 24. What's next?
Full Metal Slide Rule: So what next is we just iterate. Why is talking. So we just go through the star. With each node which has the number one, we collect all the points, we have this shape and we group them and debug them. So we can convert this as a string or whatever as a key. So if we find duplicated key, so we can regard their same shape. So then we just count how many numbers are in this hashim map, then we can figure out.
Digital Avenger: That makes sense. So two questions here. You were using dfs, right?
Full Metal Slide Rule: Yes.
Digital Avenger: Why dfs? Why not bfs?
Full Metal Slide Rule: So for bfs, I think it can. So for the bfs, it just provides a consistent order to iterate all the neighborhood for the bfs. For the bfs, it also can be. Done as well, I think as long. As we use the consistent order to visit all the neighborhood. So we start with one, then we have these two.
Digital Avenger: Okay?
Full Metal Slide Rule: Yeah.
Digital Avenger: Okay, cool. So what's the time complexity?
Full Metal Slide Rule: So for the time complexity, I think it just visits every node of this matrix. So the final. So this should be zero. So the final time complexity should be equals the node of this matrix is o m times n. So whatever this metric is.
Digital Avenger: And what about the space complexity?
Full Metal Slide Rule: Yeah, space complexity. Is also O(n). So yeah, we just.
Digital Avenger: Sorry, what?
Full Metal Slide Rule: It's also, what is also equals the number of this matrix.
Digital Avenger: Assume it's an n cross n matrix.
Full Metal Slide Rule: Yeah.
Digital Avenger: Then how would you define the space.
Full Metal Slide Rule: And time complexities for the time complexity. Time complexity equals o n times n. The space is also same cos. Yeah, it's same. I think it's same.
Digital Avenger: It's same because.
Full Metal Slide Rule: We save our shapes. So the numbers of these shapes, the number of coordinate is equals to the numbers of the matrix, the points in the matrix.
Digital Avenger: Okay, so can you write it like space complexity is.
Full Metal Slide Rule: Yeah. Okay, let me write it.
Digital Avenger: Sorry. One quick thing before you move on, like you haven't finished the space complexity. So it's o of m. Yes.
Full Metal Slide Rule: Not times n.
Digital Avenger: Sorry. Now please write the code. Assume that you don't have to take any input. It's given to you as a function parameter. The grid is given to you like that. Your only job is to return an integer.
Full Metal Slide Rule: Okay, sure. Let me define a function here. So record count shapes. So the input is a magic and a number. So we going to do dfs. So let's say m equals non. Let's assume the size of the matrix is always above then zero. Can I assume that?
Digital Avenger: Okay, go ahead.
Full Metal Slide Rule: Thank you. It fine. So I'm going to define a function within this function. So just use some feature of closure. I know in some project this coding style may not be preferred, but if you don't like it, I can just always define this function outside.
Digital Avenger: Okay, that's fine. I don't mind.
Full Metal Slide Rule: Okay. Function. Okay, we have a collector called a shape. Okay, so shape, shapes. Okay. The shapes should be a map. I'm not sure. The ray cannot be used as a key. So let's convert it to a string. Okay, this is account. Okay, so visit inj if the matrix I and j equals one. Going to visit this one. Okay. When everything is done, I'm going to return the loss of the shapes. Okay, so let's see how we define this rigid function. Okay, we start with I, J. Okay, so let's, so, okay, so since. We are going to each direction, so the index may be out of a border. So let's check the border first. I is next to j is zero or I is great or equals mj. Great or equals n, just return. Okay. Since we are going to try the four direction, so let's. Okay, four. At this point it's zero. We're going to return. Okay. Then I'm going to set this .0 so we don't have to visit that again.
Digital Avenger: Okay, can you do something here? I don't want you to change the original matrix. Let's not change the input.
Full Metal Slide Rule: Okay. Then we are going to have a visited the map. Okay, make it as a booning. Okay, make it, make it booning matrix long is f. So let's set all. The values of this. We can do that later. So set all visited, visited map. Okay to do. Yeah. Okay. Then we'll check if this map is visited. Visited. I-J-A equals true. Okay then we set it as true. We don't need you to set it to false again because we are not. Going to visit it again.
Digital Avenger: Sure, makes sense.
Full Metal Slide Rule: Okay, so we're going to visit each neighbor. Okay, so that includes eight directions j. Okay, I know there's a way to. Make it this code shorter, but I, before minus one, minus one, minus one, minus one, plus one, minus one minus one plus one. Okay, so, okay, we did it. So are we, okay, so every time we encount a value. So. We need to have. We need. To have a pass to collect that. Okay, we need to have a pass to collect that pass. Let's make array of, array it to correct that. So, okay, so we start with empty.
Digital Avenger: So you included path.
Full Metal Slide Rule: Yes, we include path, but I'm not sure why there is error promoter right here. Okay, function defined here. Function defined here. Okay. Yeah, you should include a path.
Digital Avenger: It, it, yeah, I'll change that. You focus on using the path.
Full Metal Slide Rule: Yeah. Pass equals append pass. I j okay. So, okay, so. I think we need to either. Decide. The path outside of this. In Golan, there's no way to return this permit. So there's two ways. Either, so we convert that into a. Pointer as a passing return parameters so we can do this. Okay, so pointers, yeah, so pass equals. A better way is to make that. Definer so dedicated to the structures. Okay, every time we will have a pass. Okay, so then we convert pass to a key.
Digital Avenger: Okay, key.
Full Metal Slide Rule: So if this map, this shape doesn't contain this key, contain this key, it. Plus, plus or it doesn't matter. Else key, it equals one. So this count doesn't matter because we.
Digital Avenger: Just need, that's fine. I think it's fine. It doesn't matter, but it's fine.
Full Metal Slide Rule: Yeah. Okay, it should be equals. Okay, so let me finish this convert method, it's called convert, pass to key convert. So that should be quite straightforward. Pass to string. So we just need to return fm s print. I think this method can do it. Yeah, I think this method basically can do it. Okay.
Digital Avenger: What does this method do? I'm not overly familiar with sprintf.
Full Metal Slide Rule: It's just generally a tool stream method like Java. It just converts any object, any array in a predefined rule. So just expand this two dimension array into a string. Okay, got it. Yeah.
Digital Avenger: So convert the exact thing into a string.
Full Metal Slide Rule: Yeah. So it's just converted like this.
Digital Avenger: Yeah. But in our case, take line 64. It will convert it in the form of line 64, not 65.
Full Metal Slide Rule: Yeah. Right. Yeah. Okay. Oh, okay, let me think. Okay, so how to convert this? How to convert this? How to convert this? We need probably.
Digital Avenger: Basically we just need to re reference the shape, right?
Full Metal Slide Rule: Yeah, we can revisit this shape, but that increase time complexity. I'm thinking about whether I can just add something during the first time with it so we don't need to visit the shape again. So using the dfs, we have to do it again.
Digital Avenger: What's the problem there?
Full Metal Slide Rule: If I do it again, that increase the time complexity. I just needed to do it again.
Digital Avenger: Okay, will that increase the big o time complexity or just increase the time in general?
Full Metal Slide Rule: It just increase the time in general.
Digital Avenger: If the big o time complexity is same, why do we care?
Full Metal Slide Rule: Okay, sure. Yeah, I it. Okay. Yeah. So, okay, let's start with, let's say the first node. Let's just call it first equals pass zero. Okay, so. For the updated pass, it's a relative pass. I just call it rpass for short. Um. Four. Okay, node, node. Okay. Range pass it. The relating nodes. The first node minus first it node. Pass equals append r node. Yeah, I think. Okay. For all the node in the process. Okay, so define a new r road. Okay. Thanks for your hint. I think this does this job not that complicated.
Digital Avenger: Yeah, if you had to do it in DFS, you might be able to do it. It'd be a little more complicated. We can discuss that later, but let's come back to the original.
Full Metal Slide Rule: Okay. Okay, so let's finish this code.
Digital Avenger: Yeah.
Full Metal Slide Rule: Okay, well just copy this code for short force. Force. Let me check. Go through this code. So start with each node and create a new pass. And. Okay, new pass. Convert it to. Okay. Start with encount one shape. Okay, so if it's zero. So if it's widget, we just return and we add a current node into our path. If it's set it widget as true. Try the four direction I direct.
Digital Avenger: Looks good.
Full Metal Slide Rule: Yeah, looks good.
Digital Avenger: Okay. Yeah, looks good to me. Okay, now let's discuss, so we have around 10 minutes. Go over four or 5 minutes, if that's okay with you.
Full Metal Slide Rule: Yeah, sure.
Digital Avenger: Okay, then let's take the next technique. First, let's discuss an extension to this problem. What if rotation was also part of the equation?
Full Metal Slide Rule: Sorry, could you say that again?
Digital Avenger: I said, what if rotation was also allowed? So if a rotated image. Okay, already mentioned that we only have, let's only consider 90 degree, 180 degree and 270 degree, 45, 20. These degrees are not really relevant and it's difficult to gauge. So let's only discuss these three other rotations. How will you handle that? We don't need to code anything here. Let's just, just.
Full Metal Slide Rule: Okay, so k. So once we get all the passes. So I will deduce the path between each two shapes. As long as the lungs of the node are same, I will try to dedup them. So the way to consider them identical so far the only way is rotate one off shape into three other directions.
Digital Avenger: Okay.
Full Metal Slide Rule: Yeah. So just rotate one shapes into three other directions. Okay. And then compare with another shape to see if one of them is identical. So yeah, just basically go through the od shape, compare with each other. Okay.
Digital Avenger: Once the entire shapes map is collected, then you will go through each shape, compare it with all the rest.
Full Metal Slide Rule: Ah. Yes. So I will basically say that just for the pass one and equals ranch. Pass and for pass two. Because ranch pass and compel, compel pass one and pass two. If they are identical. So I just convert.
Digital Avenger: How much do you think this will increase our time complexity?
Full Metal Slide Rule: Yeah. So let's say it increase the time collapse to the O m times n two square. Because each shape will compel with for each one, since it needed to rotate. So I needed to consider rotation into that.
Digital Avenger: Right line. 54, 55 is range shape, not path path is just one shape.
Full Metal Slide Rule: Yeah, it's one shape shape two.
Digital Avenger: Got it?
Full Metal Slide Rule: Yeah. So rotate shape. Rotate shape probably. For each one. Rotate shape. Yeah. Rotate shape. Everyone is one. Note, I think I just still like this. It's times n to an untime square.
Digital Avenger: Okay, that makes sense. Got it. Let me suggest something. What if when entering the shape in the map, for every shape, we got all the four rotations and check if none of them are in the map, we insert all four. Then the next time we get any shape that's similar to any of the rotations, we'll find that rotation already in the map. Right.
Full Metal Slide Rule: Oh, I see. Yeah, that makes sense.
Digital Avenger: What would be the time complexity of that?
Full Metal Slide Rule: Yeah. So in that case, beside that, we just need to add the rotations. Rotations is four times, I think just four times n times n. So that steer makes o. N.
Digital Avenger: Right. Exactly. Okay. I think we are done with this question. I'll paste a very small question. We'll quickly discuss this.
Full Metal Slide Rule: Okay.
Digital Avenger: Because we don't have time to go through all of it. But do feel we can at least take a look at this question? Come to line 68. I am pasting the question. No code is necessary. Let's just discuss it quickly.
Full Metal Slide Rule: Sure. Human array of unicorn non negative integers. Find the small integers not present in array. Okay. Non negative. Be found the smallest non negative integers not present. Okay, I understand. So there's. Array contains all the non negative integers. There are some integers there already. Find the missing one. The smallest the missing one in array. Okay, yeah, I see that.So the first question I ask. Look, this ray is not sorted, right?
Digital Avenger: It's not sorted. In this example, it's just sorted. But it may not be sorted.
Full Metal Slide Rule: Okay. So if we have array like zero, zero, one. So the answer should be two, right?
Digital Avenger: Correct.
Full Metal Slide Rule: Okay, so how can we do that? Yes. Let me think how to do that. Okay, I think I have no question for the problem itself. I'm thinking about an algorithm to do that. Okay, so. So, okay, so try to do.
Digital Avenger: They're all unique, they're all non negative. And you just need to find one integer that's not present.
Full Metal Slide Rule: Okay, so my sorter is like this. I go through. I go through this array from the first one. Before I visit the first one, I assume the answer is zero.
Digital Avenger: Okay.
Full Metal Slide Rule: Until and I have another hash map. Hash map. To save the integer I have visited already. So if I encounter one, I save it into the hashmap. So means one is founded already. I assume the smallest one. The non integer one is zero. Then until I encount the one. Assume the next smallest non negative integer is two. Until I encounter two. Then I still increase this number. Okay. I don't encounter this number. Then I find a four.
Digital Avenger: What does the hash map contain?
Full Metal Slide Rule: The hash map contains all the elements I have visited so far.
Digital Avenger: Visited so far? Okay, so why are you tracking those?
Full Metal Slide Rule: Because I want to check the cause. Let's say since this array is not sorted. So for example, it's like this. Yeah, so, yeah, I assume the first. I assume the answer is one. I encounter two. Okay. I still assume the answer is one. Okay. And then I encountered one. I said, okay, one is not possible. Let me try two. Okay. Then I encounter two is not imperative. I try three. Then I can look back into this hash map to see. Okay. The three is not there. So my subtraction is true.
Digital Avenger: You have the array, but you're only. So how are you searching whether answer is present in the array or not? You search one by one.
Full Metal Slide Rule: No, I just use this hash map. Right.
Digital Avenger: Initially, the hash map has no values. You're only putting the value of answer in it, right?
Full Metal Slide Rule: Yeah.
Digital Avenger: Let's assume this is the array. This is the array. Initially, the hash map is nothing. You're only putting the values of answer. Or are you putting the values of the array in the hash map? I didn't get that.
Full Metal Slide Rule: Yes, every time I encounter one. So it's actually just a hash set.
Digital Avenger: Okay, hash set. Okay, yeah, that's fine.
Full Metal Slide Rule: It's hash set. Then I just keep adding the element I encountered so far. Which element?
Digital Avenger: The one you get in the array or the answer element. Where do you encounter these elements? You're saying you add all the elements you encounter, but encounter where? Doing what?
Full Metal Slide Rule: I encounter one. Okay. Every time. So I start with, assume this number is zero, one, and I save one into this hash set.
Digital Avenger: Okay, you say zero and hash set.
Full Metal Slide Rule: Yeah. So until I got remove that for a second. I'm removing that. Remove that. We only have this. We have an answer zero. We have an array and we have a hash set. Now tell me, how do you start? Yeah. I found a one. So I found a zero. I know zero is impossible, so I try the first how do you know zero is impossible? Because I just encountered it. Right.
Digital Avenger: So you search the array and find if zero is there or not.
Full Metal Slide Rule: No, I just interact this array just once from the beginning. So I start from the zero and I also found a one. I know zero is impossible. I also check the hash set to see if the hash set contains zero. Okay, then either of them. I found the identical value, either the current value.
Digital Avenger: I think I'm getting a little confused. We have a few minutes. Can you code it out? I think I'll understand that better then.
Full Metal Slide Rule: Okay. Okay. Small east non neck number. Okay, so numbers. Okay, so I say I will have a set. Okay, so set. Make map, integer. Okay, it's a set, but it's still implemented by hashimap. Okay, that's fine. For numbers encounter, this is zero. Okay, we're going to return the assume eventually. Okay, if numbers equals assume or set contains. Let's just use this contains assumed and to set. Okay, I mixed java with go, but let's see, number equals two. Okay, so if number equals. Okay, if.
Digital Avenger: Okay, give me a second.
Full Metal Slide Rule: It.
Digital Avenger: Okay, let's do a quick dry run. Let's see, zero to one. What do you think the answer would be?
Full Metal Slide Rule: The answer, let me go through it.
Digital Avenger: Talk about what the answer should be.
Full Metal Slide Rule: Should it be three? Should it be three?
Digital Avenger: Now let's do a quick dry run.
Full Metal Slide Rule: Yeah, assume. Start with zero. So the set start with the empty comes in with first encounter. The number equals zero. So then assume it will be one. The set will be one. Okay.
Digital Avenger: Yeah.
Full Metal Slide Rule: Okay, so the second comes in. The one comes in. Okay, so.
Digital Avenger: Contain, and then you add one as well. But the loop breaks. Yeah, but the loop breaks and then you end up returning two, which is not the answer.
Full Metal Slide Rule: Okay. Yeah, sure. Okay. If for set contains, assume, assume plus. Yeah, I think that should fix.
Digital Avenger: Yeah. So in that case we could just remove that assume plus plus. In the beginning, all we need to do is put everything in the hash set, traverse through assume, doing a quick plus plus if the set has that number. If not, you just break and return.
Full Metal Slide Rule: Yeah, that's for the worst occurs.
Digital Avenger: Yeah, but the overall time complexity is not going to change at all.
Full Metal Slide Rule: Yeah, that's the idea I have so far.
Digital Avenger: Okay. Yeah, this makes sense. Okay, so I think we are done with this part. Now, let me write down something. One thing that you should expect in any fine interview as well. They will be taking notes. So right now we can't see each other. In most interviews, you'd be able to see the interviewer and you'd see them looking down or typing them on the keyboard. You should expect that.
Full Metal Slide Rule: Taking notes. Yeah. So in that case, what, should I pay attention if the cameras are sound, should I have some eye contact even when I'm typing?
Digital Avenger: No. Okay, so that's just for you, that it's okay if they are not looking at you. So that's just for you. Don't worry too much about eye contact, et cetera. Keep focusing on your question. But if, let's say you see them looking down or something, don't worry about it. That's all. Okay, now I'll go through some of the feedback. So you were able to code out most of it, which was great. Space and time complexity was correct. You were able to come up with an algorithm for the first question quickly. In a sense, within time, you needed one minor hand, but other than that it was fine. Modularity in code was decent. Two issues. One, that you used IJ, which is not really the best variables to use. See, if you use row call, anything like that, I really don't paint a good picture. So that's just for your reference.
Full Metal Slide Rule: Row call is better than IJ. Okay.
Digital Avenger: Yeah. And the second is you missed the shape rereferencing. That was a pretty big part of the code, which had to be pointed out again. So it wasn't a minor thing. Minor things are still fine. And this was not a big thing too, but it wasn't a minor thing because that's half the question.
Full Metal Slide Rule: You mean during this shape converting?
Digital Avenger: Yeah, the convert shape to keep. You just did an FMT sprintf, which was not. You missed that. We had to convert first into an rpath.
Full Metal Slide Rule: Okay.
Digital Avenger: Yeah, your approach was workable. You were able to come up with an approach that was great, might be a little inefficient, but at least it worked and that was enough. Second question, we saw a number of bugs, so that was a bit of a problem. But given that we were on a very limited time budget, it's fine. But in future, especially that this is not a difficult question. The first was a much more difficult question that you were able to come up with. This, on the other hand, was not. So the expectation here was that before saying that this would work or something, my suggestion is dry run on a few of your own test cases.
Full Metal Slide Rule: Okay. Yeah, sure.
Digital Avenger: Of course that would actually help you out quite a bit. Other than that, it was good.
Full Metal Slide Rule: Okay.
Digital Avenger: I'm basing the whole thing on the first question and the extension because that's what we did in the majority of time. Based on that you would pass. But given that you are applying for a senior, they would ask a few follow ups here and there. They might twist the question a little, ask how this would change that. If some things to keep in consideration are concurrency. If I have to scale this and make it concurrent, how do you handle that? Multiple threads going into convert, path to key or multithreading to ease the pain of solving this big problem, how would you handle something like that? How do you make it safe? Things like that. And they would keep coming in. If this was in a distributed system, how would you handle, would you use a different cache? How do you handle cache misses, cash hits, things like that?
Full Metal Slide Rule: Of course.
Digital Avenger: But you should know that there is a possibility that they might. That's all I'm saying. Okay.
Full Metal Slide Rule: Yeah, I noticed that it's not threat safe sometimes. Okay. I would definitely consider it that. Thanks for your coaching.
Digital Avenger: Sure. I think that's all the feedback I have for you. Anything else you want to ask me?
Full Metal Slide Rule: Yeah, first question, I never encountered this before, so I kind of feel kind of overwhelming at the very beginning during the real interview. So if this is a new question, the interviewer will, you need some hint from the interviewer. So is that cause some negative impact? So what is the expectation from?
Digital Avenger: So first thing is you should expect that there is a decent chance the question you encounter is an unknown question. Okay. So in most cases meta Amazon. Sometimes you might encounter a similar question that you have some idea about, but there is a chance you might encounter question you haven't really seen before. So that is part and parcel of the job. You should expect that it would be new now, depending. Given that I know this is a bit of a difficult question. Minor hints are okay. If I have to give a major hint, that's a bad sign.
Full Metal Slide Rule: Okay.
Digital Avenger: Especially at an e five, like at an l six. Basically, at l five, a minor hint or two are fine. So as I said, if you break down problems, like the breaking down is something I expect you to come up with that. Okay, we have to first calculate shapes, get the shape, and the second part is deduplicating them. Then maybe we can discuss a little on deduplication. I can suggest a few things. I suggested rereferencing this much minor hint for my question. I expect. Okay, but if I have to point out how to store the shape itself, or how you would go about deduplifying it in the first place, if I have to tell that completely, then I expect a perfectly perfect code. Then if I have to point out even a minor, because I provided the algorithm, then at least you should be able to code it out without any hints, any problems at all. So that's how I look at it. So, minor hints, you should consider basically go through the question, keep thinking, and think out loud like you were doing right now. So if you're going too much in the wrong direction, most likely the interviewer themselves will point it out that hey, you have gone too far off. That approach wouldn't work. The minor hints are not considered problematic. But major hints, especially at an e five, will cause you some problems.
Full Metal Slide Rule: Okay, so for the hint you give to me, especially for how to represent the shape by minus the relative point from the first node, does it count? A minor hint.
Digital Avenger: That's a minor major, because you are already thinking about using dfs to accomplish that. I just said that we could do it after getting the whole ship, so it was merely a change in process. You are going to do the same thing. You'd already arrived at the fact that line 118 is the final thing that we had to get to. Okay, I just suggested that rather than messing a DSS, you could have done that. I've had people do that with the same question. But you could just re reference the whole thing. That also works, that's all.
Full Metal Slide Rule: Okay.
Digital Avenger: That counts as a minor hint.
Full Metal Slide Rule: Okay, I see. But minor hint is still worse than no hint.
Digital Avenger: No hint is obviously the best I won't deny that, but don't put too much stock in if you can get it in no hands or something like that. And generally the interviewer will only interfere when you have gone too far off where I see that. Okay. That's just not going to pan out in any direction. So it's best to keep confirming that. I'm thinking this. I think that this is okay. Go through some cases in your mind to see that. If it actually does feel okay, then confirm. Is it okay with you as well? If it's not okay with them, most likely they will point out something.
Full Metal Slide Rule: Okay. So it's just one final question. Sometimes I focus on the code, the quality and the modularity, and also the communication between me and interviewers. Sometimes I feel the time is quite limited. Should I focus on the finish or the code should focus on the finish first, or focus on this communication and modularity and coding. There are more.
Digital Avenger: Good question. Normally, and this, I know this is not, maybe not the answer you're looking for, but normally the expectation is both. So what I'd suggest is, and especially at an ESX, unless it's a behavioral round or something like that, keep the intros very short because I've done this as well when I've interviewed, as in me as an interviewee, taking the long approach for an introduction actually reduces my time for the interview because that doesn't add any value. Not the interviewer. The interviewer is not looking for your introduction whatsoever. Doesn't matter because that's not how they are going to grade you. It has no bearing on your overall grading. So cut short all the initial chitchat, give a very 60 to 92nd introduction and then directly jump into the problem. So you have time for communication in problem. You should be definitely clarifying first, then communicating. This is what I think. If they say it, then you should be able to code it out quickly. Now, in most cases, especially eight, five, I would expect, people do expect both, that you should be able to communicate and code it out. Worst case scenario, this is like worst case where you don't have time or something has gone, sort of thing. And interviewer also has an eye at the clock, so they know, okay, what can be done, what can't be done. So my suggestion then would be keep coding while talking about what you're coding and try to see if you can finish the code. If you can finish the code, you can actually talk about at the end. Take 30 to 60 seconds and just quickly explain the code in 60 seconds. Quickly sort of say that okay, I'm doing this broad level. I'm doing this. I'm checking the h conditions. If this has already been done, then I'm returning if the path. Then I'm appending this as an integer array to the path, making sure that we don't visit this again, going off in all eight directions. So this took less than 30 seconds to explain your entire visited function.
Full Metal Slide Rule: Okay, so during the code, should I call it loudly or should I just don't talk too much? Because sometimes I realize when I walk out I may say something that doesn't make a sentence. So is that something I should.
Digital Avenger: It's fine. It doesn't really matter.
Full Metal Slide Rule: Okay.
Digital Avenger: Most interviewers don't care that much. It's fine if you talk out loud. If you don't talk out loud, if you don't talk out loud, then you need to talk out loud after you have coded. So in that case, I would expect that you code really fast. It can't be that you code at the same speed while talking out loud and not talking out loud. So if you're explaining while you're coding, that's fine. I understood while you were coding. But if you're not, that's also fine. If you reserve enough time so that I can understand post you've coded.
Full Metal Slide Rule: Okay. So overall, do you think I have a chance to pass based on my performance today?
Digital Avenger: Yeah, you would.
Full Metal Slide Rule: I see. Okay, that's good. Okay, thank you.
Digital Avenger: Because quick thing, I'm only basing it on the first question, the question we did within 1 hour. So the second one went over 1 hour. I'm not counting that at all because that was not a good showing. And I'm attributing that to our lack of time. Because we had limited time. We didn't give it proper thought. So I'm ignoring it.
Full Metal Slide Rule: Okay. Thank you. Thank you for your opinion. That's very valuable.
Digital Avenger: Okay. I will provide detailed feedback as well with most of my notes. I think we'll both get a chance to provide feedback as well. So please, if you feel anything I could do better, please do. I'm always looking for.
Full Metal Slide Rule: Sure.
Digital Avenger: Okay.
Full Metal Slide Rule: Sure. Okay. Thank you.
Digital Avenger: Thank you. Have a good luck for your interview.
Full Metal Slide Rule: Yeah. Have a good rest of the day.
Digital Avenger: You too. Okay, bye.
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.
