Python Interview with an Apple engineer

Watch someone solve the count islands problem in an interview with an Apple engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Count islands

Interview question

Given a 2D matrix, where 1 represents land and 0 represents water, count how many islands are present

Interview Feedback

Feedback about Phantom Dragon (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

Great problem solving skills. I would work on providing more test scenarios before jumping to the actual algorithm. This way you can identify all corner cases and ask clarifying questions.

Feedback about General Avenger (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

1/4

Interview Transcript

Phantom Dragon: Hello.

General Avenger: Hello.

Phantom Dragon: Hello, can you hear me?

General Avenger: Yes. Can you hear me?

Phantom Dragon: Yeah, I can hear you.

General Avenger: Okay, perfect. So hi, my name is.... I'm calling you from interviewing.io and this still a good time to talk?

Phantom Dragon: Yeah, sure. So, my name is....

General Avenger: Good to meet you. Okay, so this is how I see this interview going. Normally, I would like to have you introduce yourself, give your background, probably in about five minutes, and then I would suggest to keep short so you have more time for your algorithm, for your programming assignment. Then for about 40 minutes, we will have time again to work on your programming assignment and at the end of the interview, I'll try to save five to ten minutes for us to just to talk, to see if you have any questions.

Phantom Dragon: Awesome, so yeah, so I graduated from a university in computer engineering back in 2018, and I joined a payment company back in 2019 as a software engineer. And right now I'm working on our data processing analytics system actually that caters to the audience and assures them a lot of analytics regarding their deployment strategies and all.

General Avenger: Okay. Since this interview is language agnostic, I would still like to know what is your language or the preferred language to be interviewed in?

Phantom Dragon: Sure. I prefer to actually use Python most of the time, since it's more compact and precise.

General Avenger: Sounds good. Okay.

Phantom Dragon: I can change that for you.

General Avenger: Sure, that'll be great. Alright. Let me paste the programming assignment and let me modify a little bit. Okay, first... Why don't you go ahead and try to read the assignment and tell me if you have this... if you have seen this problem before. If you have, maybe we can have a different question. If not, let's break it down and let's work on it.

Phantom Dragon: Sure, so you're given a 2D matrix, please write a function that finds the number of islands in a given matrix. Island is combination of one's... So actually, I have seen this question, but it's been like way back. I haven't practiced this kind of thing in a while.

General Avenger: Okay, so do you want to work on this problem? Or do you want to have a different question?

Phantom Dragon: I think yeah, this problem is good. I want to do this one since it'll be almost as if I'm starting fresh.

General Avenger: Yeah and it's a fairly popular question during the interviews, so I think it's good to practice.

Phantom Dragon: Yeah sure. So yeah, so what I could remember is that is a 2D matrix and all the islands... so the lands are all one, and zeros are the water, right? So the land would be say... one island would be this because it's surrounded by zeros and water, so this would be one island from this and this, this forms one island. Then similarly this and this will form another island, so there are two islands. So what are the conditions, are they going to be surrounded by the right, left, top, and bottom matrix, the bottom elements, or they can be joined by the diagonal element as well? What if say instead of this zero, it was a one? Then we could have considered this entire thing as one island or still it would be one island here and one island here, since this joined by a diagonal?

General Avenger: Yeah, so great question, so if you have another one in here... Then we would have one island. Just one island.

Phantom Dragon: So the corner diagonal also counts?

General Avenger: Yes. Very good question.

Phantom Dragon: Alright, so then I'm thinking at this point it's going to be... it's basically kind of a graph and we have to traverse the graph and see where are we encountering all the ones and basically keep track of it. Our stop condition will be if you reach all the way down here or if you reach any of the edges and you cannot go right or top because it's boundary, then you have to stop there and you have to move in towards the way where you can move basically. And which has not been covered by any other movement that you have been doing. So that would be one of the way. Now the important things here is, you will keep track of what elements you already have visited, else you can end up in a loop and it will go down and you'll never come out of the loop.

General Avenger: Good point.

Phantom Dragon: Yes, do you want me to start writing?

General Avenger: So before we jump on it, what would you say the runtime complexity is going to be with the graph approach?

Phantom Dragon: So if we do a graph approach, basically it's going to be a depth first search and the runtime complexity will always be O(n), given n equals to the number of elements, so if you take it in terms of rows and column, which is R and C, it will be O(R*C). So it will be a linear time complexity.

General Avenger: Alright, excellent. Sounds great. Let's do it.

Phantom Dragon: So I'm going to see the number of items. And I'll be declaring something like total islands which initially is set to zero. And then after, I want to... Actually... I want to declare something called paths, so basically I'll store the paths that I can go from say here or anywhere, the possible path that I can proceed. The possible paths would be... and I want to store it in tuples, for example if I say (1,1), so that means I can move x coordinate... I can move one x coordinate and one y coordinate. So if it is (0,0) here, zero plus one and then again in column zero plus one, so that would be (1,1), so that will be here. I can move here. So similarly try to something like, (0,0). And then I can move 1 and 0. Then I can move. But if it's 0 and 1 then I'll be moving 1 column, that will be here. If it's 1 and 0, I'll be moving here. Yeah. And if it is here, I can move backwards as well, right? So I can move (-1, 0).

General Avenger: So, what is the value of this path again?

Phantom Dragon: Yeah, so I'm going to do current coordinates, which would be the coordinates that I'm currently, say for this one, I'll be in (1,1), and then I'll go to all the possible paths. Say if I choose this, then I'll add my x coordinate to this x coordinate, that will be my future path and my y current to this y coordinate, that will be my future y coordinate.

General Avenger: So from any given coordinate, you want to see which path should you go and check for value?

Phantom Dragon: Yeah.

General Avenger: I see okay.

Phantom Dragon: So I think I'm missing two here because I took care of this and this and I'm gonna take care of this and this and that would be... if I'm here and I'm gonna go here, so that will be an increase in column... sorry an increase in row and a decrease in column, so that would be 1 minus 1. And similarly minus 1 and 1 would give me the other one, the opposite one. Alright, and now I'm just storing my role and... Now for each, I have to go for each element, I have to keep moving. So I'm gonna calculate my future path, so my future position, so my future position is equal to my current position... Alright, does this is make sense? So what I'm doing here is I calculated my current position, which is nothing but the row and the column, and where I'm gonna move is my future position, which is current position 0 plus... Yeah, so basically I am adding the first value of my path, my path being this, and my current position 0, which is x coordinate plus the x coordinate of the path, which gives me the x coordinate of my future position, and I'm gonna do it for all here now. I'm gonna check whether I can move there or not. So still I haven't coded what would be the condition where I'd be counting whether this is an island or not.

General Avenger: Okay.

Phantom Dragon: My conditions are... basically also I have to make sure that I have a visited the path and how am I gonna do that is... I can keep track of... I can just keep another grid as a memory, basically I can use something like memoization technique, where I can do another grid of the same dimensions and adjust the binary value to visited, for example. If I do.

General Avenger: I have a question. Future position, are there any corner cases with future position?

Phantom Dragon: Yeah, so there will be corner cases with future position, for example, when you are going to overflow this way, so when you are going to overflow, say something like zero and minus one, which would be less than 0, or greater than length of row and column. So that will be our corner case and that we can handle when we are visiting that future position, so we don't want to visit the future position if we hit the corner case.

General Avenger: Excellent, thank you.

Phantom Dragon: So I'm creating a visited memory, visited map, where I am keeping everything first of all. And here I'm gonna do... Now I'm gonna check... I will check where my conditions end, like where do I increment my total number of islands. So say if I start from here and this is not a one, and if I end up here, and this is not a one. I do nothing with the total number of islands. And say if I end up here, then what I do is I'm going to increment my total islands to one. Again if I'm going to end up here, I'm not going to increment my count to one, so the only condition where I'm going to increment my total island to one would be I guess here. And the condition here is my future position when... And my future is and they are not visited yet. And if they are all zero, then I can increment my total number of islands to one. Okay.

General Avenger: So, just to summarize it, where exactly are you planning to increase the number of islands in you or in your traversing logic?

Phantom Dragon: If I'm here and my future position... so if my current position is say here and my future positions, which are not visited yet, and say I come from here and here I end up here. I've already visited these. And say we are traversing, the next thing I'll be traversing is to a zero here. Then... that is not right. Yeah, that would not be right.

General Avenger: So I have a question for you. So, just visually walk me through how the depth first search algorithm works.

Phantom Dragon: The DFS algorithm, sure. So the DFS algorithm would basically work from each position, you would traverse to every other possible positions, say if you start from here. First you say first you are going down, so if you go down, then for this position again, you can go down this way this way and all other way. So basically you'd be traversing the depth first, and then you'd be tracing back and whatever paths are not covered, you'd be travelling those positions.

General Avenger: Right and so once you find your first one, right? You ran into the island or piece of island. You ran into your first one and then your algorithm should... And I think that's where towards what you're moving, is your algorithm should keep traversing the matrix or grid to the point where it found all the ones or it ran out of the options for this island, right? So it ran into the water or it found all the ones.

Phantom Dragon: Yeah.

General Avenger: There's gotta be some sort of recursive call, so it has to keep tracking the future position for every of the next elements.

Phantom Dragon: Right, so you think if we start from here, if I start from zero, I should not be traversing anywhere because I am on zero. I should be only be traversing when my current position is a one?

General Avenger: Right.

Phantom Dragon: And then I have to figure out what would be, if I start from one, say one, then I have to figure out where do I have to stop as well. Right, you're right. So that would be here. I am at one, my future position say... so I would start at one only after I have covered this. Right because I won't do any DFS if I'm at zero. If I'm at zero, then I go here. So something like for each row, so my current position, then I would be checking if my current position is read. Then I'd be doing a DFS here. And also, here I would be Setting up the visited. So here I have to do a DFS. Now I should probably modularize it and write another function called DFS. And what would be my parameters again? Great. And my say current position.

General Avenger: Yep, you're on the right track.

Phantom Dragon: Alright. Okay, so this is my future position and I'm gonna see if future position... Actually, this would be more easy if I just name it as a future current X current Y and future X and future Y. how

General Avenger: Yeah, I think that's the naming convention here.

Phantom Dragon: Yeah. Now I need a condition first and my condition first is check the boundary condition. And we keep recursing, right? Oh sorry, recurse with grid. And now my current x and current y will be my future x and the future y. Okay, and also I will make sure that I am not looping up because if I'm starting from here, so the future x and future y, this is a valid future x and future y, I have already visited this so if I go here again then I'll end up in a loop. So I don't want to end up in a loop, so there should be another condition and not visited. This is invalid syntax basically because yeah... So yeah, this is how I'm going to do my DFS from here. So basically when I'm here, so basically I have eliminated this position. I'm not going here. I have basically eliminated the corners. This one as well. I have eliminated this, as well, because I've already visited and this as well, so the only thing I'm left with is I'm going to visit this and this and nothing else. So, yeah, so the only thing that remains here is when am I going to... Also have to make sure I set my visited here as well. Alright, so I have to see at what condition am I going to implement my value, my total number of islands value? So that would be the else collection I guess.

General Avenger: So remember when we talked that the moment you hit one, right? You have found the island, you don't know how big the island is, but you have found the island. And then you keep traversing.

Phantom Dragon: Yeah, so basically this is a code where I'm just traversing now. I still haven't figured out like how to keep track of number of islands that I have traversed, right?

General Avenger: Right. But that's where I'm leading you towards. So you found the island, right? You ran into the first one. That means you found the island and then you'd depth first search does the job, right? It keeps traversing until it ran into the water, into zeros, and found all of the ones. And then you keep going, you already have one island, you keep looking toward the other for the second island. Then you run into another one, right? That's your second island. And then you're DFS kicks in again.

Phantom Dragon: Right, exactly, so that's what I'm saying. So I was thinking I can do it here actually, so here I can just add another condition and it has not been visited, and then as because my I'm taking my DFS from here, and this DFS will stop, and this DFS is going to stop when the connection is going to break. So this DF is going to stop here. So the next DFS will kick off from here. And that's when I can increment my next island.

General Avenger: Right.

Phantom Dragon: Right, so whenever I hit the one, I can just increment my island. Also I have to make sure the same conditions hold for here as well. Yeah. So, I think I'm just gonna go once through the entire code and let's see if it makes sense, because for me, it makes sense. But I am just going to repeat it so that we are both on the same page. So yeah, so I have first of all, declared a variable called total_island, which I am going to keep track of number of islands that I am hitting, like a number of disconnected islands. And then path, is an array of tuples, where I have kept eight possible paths that I can go where my future coordinates can be from my current coordinates. And then row length and column length are just the length of row and column. And visited is an n x n grid of boolean variables, first of all, it is initialized with false because I have not visited any of the grid yet. So, next it will start from here, the control. So I'm going to traverse through each and every element, starting from here. So if I start from the top left, it's going to... First of all, it's going to save memory. So it's going to say that okay, I have visited zero. Now it's going to see if the grid and column is equal to one, which is not. So it's just going to go forward, which is the second element, the same thing. It's going to keep track of visits. Now, we are hitting this one. Now when we hit this element, this is going to kick in, which is where column equal to one and not visited the row and column, which is true, we have... Oh it's actually not true. I think this condition is at the wrong place. Yeah, this condition...

General Avenger: No this condition is at the right place I guess. It's just that...

Phantom Dragon: Yeah, I don't think I should be doing this, yeah. This is not necessary. This will produce false results. So I mark the status as visited equal to 2 and I see that this is a 1, so I increment the value to 1, the number of islands, and I do a DFS. So okay. So in DFS, it's going to visit, now it's going to enumerate through all the possible paths and all the possible paths will be here. And the only elements that is going to visit is this one. And then it's going to mark it as visited, and then it is going to mark this one. It is going to come here it is going to mark that as visited that would have come here and mark that as visited. Now when it comes here, the traversal actually stops because of all these conditions. Because if it is here, we have already visited this, so it's not going to go there, so the only condition is here. And since any of the future y, any of the possible future y, is not going to be a one, it is going to stop here. So again, it will come out of the DFS loop, increment, so now we were here, it will increment to this one. Now this is the tricky conditional because when it comes here, it is going to increment the total islands to two, but I should not be because I should not be doing DFS here, and that's why keeping this condition is tricky here. I'm thinking where should I put this condition? Or I do not need this condition at all here because this condition is being taken care of here.

General Avenger: So in your depth first search, when you land on your first traversal, you are passing current x and current y, and they're equal to one, right? Which means you have to mark it as visit it, but post back then though.

Phantom Dragon: Yeah. I mean yeah after this not here. So, I'm thinking is because here I am doing the visited future x future y equal to true, which is necessary. And if I do a visited current x, current y equal to true, that should work. And I can here and not... Yeah, this would work. So the next time when I start from here, it will see that it is already been visited and is going to skip that. And so again, when we advance here again, since this is not a one, it's not going to kick, in not going to kick, in here, not here, not here, because visited, or here visited, not here as well because this this is also, because this is not equal to one. Then here is going to kick in again because this was never visited and this is a one. And it will increment the total number of islands by once, and it will kick off the DFS again.

General Avenger: You have a cycle, yeah.

Phantom Dragon: This is really like a couple of years after I'm doing this up first. I know this looks messy, this can be improved a lot I guess. But for time sensitivity, what do you think is the best I guess.

General Avenger: Yeah, I agree, the depth first search was the way to go. And I think your code looks good. The only thing I would probably move out the depth first search, not have it declared within the function. Just move it out. But for now, let's just go ahead and run it.

Phantom Dragon: Yeah.

General Avenger: I think the the logic and the code looks good. Good debugging too.

Phantom Dragon: Can I just copy this one?

General Avenger: You can just declare it. I didn't assign it to any variable, so.

Phantom Dragon: Oh yeah.

General Avenger: Is input a reserved word or not?

Phantom Dragon: Input is not a reserved word, but why would it color? I don't know. Let's say one. Okay, let's go ahead, it's giving out three instead of two. I guess somewhere the logic is flawed. Let's see if I give it a one, then it will give me a two. Yeah, it should give me one, but it's it's giving me one extra for some reason. Okay one zero, which is expected, now two zero, which is not expected. Why is it... so that means it is not called. The two zero, which is this one, was not covered in this DFS. I have to look at that. And this one should be X plus one and y plus zero, so (1, 0). I have a (1, 0).

General Avenger: Yeah, there must be either something in that if statement, somewhere we aren't marking it as visited. I'm trying to see if the path conditions are right. Can you print out the visited?

Phantom Dragon: Yeah, I can print out the visited, as well. Here?

General Avenger: You can print it out once at the end.

Phantom Dragon: After the base case or here?

General Avenger: Yeah, before the return statement. Or you can do it there.

Phantom Dragon: Why does my visited look so weird? I just have two rules for some reason.

General Avenger: Are we missing the... Should the second for loop also be wrapped in the square bracket?

Phantom Dragon: So it looks like right to me. Yeah.

General Avenger: Yeah, I'm trying to research how to declare a 2D matrix. Python is not my language though. But it looks like that's the request. Oh okay, check this out. Let me just copy paste that. Looks like you need a I and J versus...

Phantom Dragon: Oh, no actually this is just a blank operator which you do not need to use it anywhere because we're not using it. But here is what I'm seeing actually. I feel visited row and column length as 4x5, which is true, because I am printing it out here, and the next thing I print my visited is actually... Yeah. Oh I think this is the correct one, just that yeah, yeah. I think I'm getting the right thing. It's just the length of it that was a problem. So I think the visited is getting initialized correctly, it's somewhere else that is the problem. Yeah, it's somewhere else. It's just getting a one, it's just getting an extra island every time.

General Avenger: So visited is a five by two matrix, right?

Phantom Dragon: Five by two?

General Avenger: That's what I see from the printout.

Phantom Dragon: Is it? Yeah it's a four cross five, sorry yeah four cross five, so one, two, three, four rows and five columns, each of them has five columns.

General Avenger: Oh, okay, thanks.

Phantom Dragon: So I'm just going to do a smaller example. I think the edge case is where it is failing is there are no islands at all. Oh, no that's not the part where it is failing. And what if I just do one? Which is one, okay. And if I extend it to one here, that is going to give me two, yeah. This is the part where it's failing. And if I do zero here, if I do one here. Yeah. So for the initial condition.

General Avenger: Actually, no.

Phantom Dragon: I keep getting zero, one.

General Avenger: Since we're marking visited on every depth first search. And then we're marking it once again, can you remove the second?

Phantom Dragon: Still.

General Avenger: Okay, well looks like it's um... Sorry we ran out of time, but greater debugging session. I think it's just some corner case that we're missing. I'm not able to spot it either.

Phantom Dragon: Yeah, yeah. I think I'm gonna work on this.

General Avenger: It is the right approach, code looks good, yeah debugging was great, it's just that one corner case, which is a fair remainder. So, do you have any questions?

Phantom Dragon: Actually yeah, so this is my first time on interviewing.io, I have like this, are you like an interviewer here or have you just?

General Avenger: I have been doing the interviews, yeah.

Phantom Dragon: Okay, okay. So one thing would be, I want to get something back on... So sometimes what happens is if I see for example this kind of problem that even if I have not done it or practiced it, I tend to blank sometimes and sometimes it happens that even in this interview, you might have felt that there was some like awkward pauses for say two or three minute where it went to completely silent, so that was just I think I was just thinking something, so would that count as a negative thing in an interview? Because I sometimes find that if I want to concentrate and if I have not seen the problem, I want to think about the problem, I need a little pause time to think it through and I cannot like, I know I could not talk and think at the same time. So, how do you feel about that?

General Avenger: Generally speaking, it's important to voice all of your thoughts. I understand that it is much easier and you're not alone here, that it's easier just to think silently, right? To focus on something. For the interview, it's important to hear your thought process. So anything that you think of. And maybe think of in the wrong direction, so the interviewer can intercept that, and you know guide you on where he or she wants you to be in. So generally speaking, I would say two, three minutes, I would not recommend... or just go ahead and say you know what, give me to two minutes I need to gather my thoughts, but something, you have to give a heads up why there is a silence, right? But again, it's very much recommended to voice any of your thoughts during the interview.

Phantom Dragon: I see, that makes complete sense.

General Avenger: And what I would suggest... I think overall you did really good. What I would suggest, generally it's better to have... I know it's hard to follow, normally you write your task before you write your short algorithm. But if you have, I would say walk through of one example, not just verbally, but on the paper, right? You say, okay I'm going to index x, then I'm moving to index x plus one, x minus one, and things like that, just write it all down. So it's much more clear for the interview where you thoughts are heading to, where is your algorithm heading to? Generally writing a small test case beforehand will help a lot. That would be the only feedback that I would suggest.

Phantom Dragon: So for example in this case instead of this big input, I would like started with a small use case and that would have been like much easier to debug, right?

General Avenger: Yeah, yeah, see it's hard to catch all the corner cases in your head, so it's better just to start coming up with use cases, and all the use cases was will come to you once you start writing your first test right? Once you walk someone through your first scenario, then all this things will pop up. So it's strongly recommended to have all of this. For the interviewer, by the way, I think the interviewer will appreciate an engineer who not jump into the solution right away. Rather try to drill down on all possible use cases and cover all the questions before we come up with a solution.

Phantom Dragon: I see, that makes total sense, yeah.

General Avenger: Okay, well it was a pleasure speaking with you today. Again, great exercise, great debugging and great problem solving skills. I hope yeah, I'll write feedback for this interview, so you should be receiving this feedback shortly, and I hope you enjoy the rest of your weekend.

Phantom Dragon: Sure, thank you.