Python Interview with a Samsung engineer

Watch someone solve the bipartite graph problem in an interview with a Samsung engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Bipartite graph

Interview question

Determine if a graph is bipartite

Interview Feedback

Feedback about Ghost Armadillo (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Good + easy to understand the question + asked an additional question such as constraint + be good at python + good communication skill Improvements + please use v, e when you calculate the time/space complexity of the graph question. + it would be better if you increase coding to speed up to 20min for 1 leetcode medium question

Feedback about Kind Dragon (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

1/4

Interview Transcript

Kind Dragon: Can you hear me?

Ghost Armadillo: Yes I can.

Kind Dragon: Okay, cool. Okay. I prepared some coding question from easy to hard. Which level of question you want?

Ghost Armadillo: I think medium onwards.

Kind Dragon: Medium, okay, cool. Okay, I pasted the question, please read it over if you haven't yet okay.

Ghost Armadillo: Yes. So we're looking at an undirected graph, return true if it is bipartite. Okay. Is bipartite everything split into two nodes and two set of nodes into two independent subsets A B. So I said every age in the graph has one node in a, another in b, okay. And the graph in the following form is given a following form, i is a list of indexes of j which is edge between, and i and j exist. Okay, list of indexes, J, okay, for which the edge between i and j exists. Okay. Okay, yeah, so that's like your neighbor. For this pit here graph i is in the list of j, which is each node is an integer between zero and the length of graph. Okay. Okay, there is no self edges or parallel. There are no self edges or parallel edges. Okay, it does not contain elements twice. Okay. So assumptions and then I think, I guess some approaches which isn't edge cases. And maybe a time and space. Ready? So we want to say you want to return if it's a Boolean, so I'm just thinking to Boolean that we returning whether it's bipartite or not, what input am I, will I be getting? It's a list of indexes? Is that what I'll be getting?

Kind Dragon: Okay. That is good question. Okay, you can assume the input is...

Ghost Armadillo: Yep. Okay, right. And right. Okay. I see.

Kind Dragon: The vertex is connected at node one and node three. Does it make sense?

Ghost Armadillo: Okay, so vertex zero is connected to vertex one and vertex three. Perfect. And this is connected to vertex zero and two. And same thing here.

Kind Dragon: Yeah, there's no one one channel is connected. But I say yes.

Ghost Armadillo: What is the largest length of graph? Okay. I guess what I'm wondering, is this this array here? What's the largest that we can get for that? Is there a maximum? Like 1000 or something?

Kind Dragon: Ah, yeah. Okay. Yeah. Yeah. So, is that up to 100.

Ghost Armadillo: Okay. Okay. Length of the array less than or equal 100. Okay. Okay. And every integer is a positive integer is one. Okay. Yeah, that's right. Except positive yet. I that's really there. Okay, I don't need to put that in. Now there are no self edges are parallel edges. So it doesn't have a loop back to itself. That's what it's saying. So that's Is that right? So it doesn't have it? Well, i doesn't depend on i.

Kind Dragon: Yeah, that is good question. Yes. There are nothing. Yeah. Yeah. Yeah. Yeah. Okay, cool.

Ghost Armadillo: Parallel edges doesn't mean element does not contain twice. Okay. That's what he's saying he doesn't contain element twice. Okay. This graph, I think what I need to do is what I'm thinking is a breadth first search traversal is my first thought. And then I need to color the graph in one set, and then color the graph in the other. So color. Let's say I start with zero, because that's my first node. And then I mark that as seen here. Say, this is me. And then they say that my color is one, I'll just say that's my color. And then one is here. If made I play. Yeah. And then same thing, when I go to one, I need to be the opposite. So let's color it the opposite, which is minus one, I can do that. Because my current color is minus one. And then it's the same thing, because this is my labor zero, one, and three, but I think they all should be minus one. All my neighbors. So say three is also minus one. And then I'll do the same one. Now. You should be one, because now I'm going into one's neighbor. That's our first thing with breadth first search? Because one in three. Yeah, yeah. Because putting one's neighbors in here. So that would be the next set of things I need to go through. So one, and then and then there's the threes, as well. So yep. So what I need to do is go through one and see which one, because that's the opposite. When I go to that, actually, because I'm visiting one, then I need to actually visit the neighbor, the one's neighbor, and that or this could be one sorry, so zero. I'm looking at that I've really visit this and because I'm currently on my current color, let's say my current color is actually one. So it's actually okay for me to zero here. I just keep going because as long as and it's the same thing with two should be one. And then yeah, I've already visited zero. So I don't need to go there anymore. I've visited zero. So, one, three. And because zero is already being visited here, sorry. So I don't actually need to do this is the because that's the same. But anyway. And then and three and then two of these are all same. So now I'm at two, should be minus one. At the moment as I visited what these two's neighbors should be one in three should be minus one, which is it is and we've already visited. Yeah. So if it's visited as well. Actually, we don't need this to the visitor, we just need to make sure that it's the same color when we actually are flipping but I do need to check that if it's visited, I need to make sure it's the same color. I do need to chat. Otherwise, we might go in a loop. So that's why I need this actually, we need to have the visited or seen as set.

Kind Dragon: Okay, okay. Can you make that graph? One maybe here? Yeah. What is the edge of this one?

Ghost Armadillo: So zero. Connecting. Here and one. Cool. Yeah. And then zero and three. And then and then one and zero is there because it's undirected. So there's two ways. So zero and two like this.

Kind Dragon: No, let me justify this default on different theories. Okay, cool. Awesome.

Ghost Armadillo: One and zero. And two, and then one and two. Yep. There's one or two. And then there are two and one, which is there. And then two and three is here. Whoops. Okay, perfect.

Kind Dragon: That's, that's right. Okay, great, okay. Or cutting off your formation, you only did two colors right? And then you try to use the two color technique. So maybe that's the one and then you throw this on the negative one, right? Yeah. That one? And then you color this one one, and then everything is valid. Are you gonna return true?

Ghost Armadillo: Yeah. Yeah.

Kind Dragon: And how about the graph? And then it's like, okay.

Ghost Armadillo: Because I'm coloring this one as... That's a good question actually. Yeah, because these, these two, they have to have the same number of nodes, right? On one set as the other. So you have to return false on this because it's uneven.

Kind Dragon: Perfect. Yeah. Okay, let's see some of the stuff from the one, and then negative one. And then yeah. Now they have to be true.

Ghost Armadillo: So we get to the last node, if they're not even the number of colors. If they're not even then... Which would also, I guess I can tally up all the minus one and the ones on to like a counter or something. That's one way of doing it.

Kind Dragon: Can you make another solution? Not BFS. Yeah. Can you make another approach? Your first approach is good, but I think we can make it up. I think that time payment space complexity is hard to meet. Right. Okay. So come to your approach...

Ghost Armadillo: Thinking, well, this depth first search, I'm just thinking this is interesting. If I did depth first search, not sure how I would actually know when they're uneven. How can I be certain?

Kind Dragon: Okay, then okay. Let's see the step by step. Can you do via the DFS one by one must be I think first must be one right? What is next? Minus one is one. All right. And then maybe we could check this on the to the neighbor, right? Yes. Neighbor kind of thing. Maybe we got it.

Ghost Armadillo: Right. Got it. Right. Okay. So it's same color. The neighbors have a color. Oh, I see. Yeah, yeah.

Kind Dragon: Okay, good. Let's go back to the previous graph. This example is a must be started with what right?

Ghost Armadillo: Yeah, that's and then that will be one. Yeah, and then that would be minus one. Perfect and then this one would be one. And then this one would be minus one. Okay. And then the neighbors are actually yeah. Its neighbors. If I go to the neighbor, and I've seen it and then yeah, I'm fine.

Kind Dragon: Yeah. Perfect. Okay, let's go one more graph. Yeah, I got it for you. Yeah, okay. Can you draw this graph?

Ghost Armadillo: Yeah, I can go one or two. This one is a bit tricky. Let's say you're three. Then one and zero and then one and two. Okay. Like I'm not sure how to draw this but I just go like this.

Kind Dragon: Okay, there's a little bit happier. Okay, this is just the tip of the red card. Every quarter that graph is going to collide can you draw this. Color it as 1 2 3, maybe you can draw it. I believe. And then next another one.

Ghost Armadillo: Then one and zero, which is fine. One and two and two, and then two and zero, which is the two and one, which is there two and three. I thought that might be here. I see. Three, and then three and three and DFS. Yeah. Three, and then minus one. And then this one should be one.

Kind Dragon: Yeah, it's going to me, maybe it's going to be really hard.

Ghost Armadillo: Then we go to three, then say minus one. And it has no, no link. So the that should actually, we should return. Yeah, that I mean, that should return true. It goes, both colored. But this one is this is what I was wondering about, actually, because two and zero the neighbor here is actually not the same color is the same color. So it's not the same, that's when you return true, that if it's the same. With the same, that's when you should return false. Perfect. That's what you want. Yeah.

Kind Dragon: Yep. Okay. Okay. Awesome. You want to painted here, channel one, day one. And now the DFS. So we need to dig in more. So now we are here, right? And maybe already visited. So we got are going to the two right? Now here is minus one. And then next, even more. One from one to two. So we are here. And then we are painting. And then different eligibility this already visited, and three will be going there. But when you check, according to the journal. But this one is same color. Right? So at that time, we needed to stop it and then return first. That's it is mixed. Because when we hear checking from neighbor, yeah. Yeah. Yeah. Okay, cool. All right. I think that you are on the right track. Can you calculate a time and a complexity?

Ghost Armadillo: Yeah, it's. So I have to visit, like the worst case is I visit all the nodes. So it's the number of nodes that I have. And the space is because I'm going to build a graph. So also, then it's my space. Yeah.

Kind Dragon: Okay. I think that it makes sense. Okay. Can we can use v and e. Yep. Yeah, point number. Number. Oh, yes. Well, you know, everybody grab the... Yeah. So it's more than Yeah.

Ghost Armadillo: I think it's the number of vertices plus the number of edges. So these are all the vertex. And then I just, yeah, all the edges as well. Yep.

Kind Dragon: Yeah, the space is the same that I think one more time, about space complexity. I think the time complexities make sense. Can you think the space complexity one more time?

Ghost Armadillo: Yeah. So I'm building the graph and calculating all the edges in the graph and the nodes, so I'll have to guess the number of actual edges here. Sorry, for the number of edges here. That's what I'm actually building.

Kind Dragon: Okay, then let's discuss after implementation, right? Okay. Yep. Okay, cool. So maybe we can discuss more clear. Okay, cool. Can you start implement now?

Ghost Armadillo: Maybe, maybe? I might do it like, yeah, okay, yeah. Fine, let's say bipartite. And then I have a graph, is that is that my only input, is the graph? Is that my only input is just the graph, right? Okay. So if I just if I had the graph and all the edges, wrapped, so that space is the number of vertices, because I'm keeping, say united spaces for the same is like all visited is actually be the same. Yeah, at the moment, as far as I know. But say I have called visited. And I'm going to keep a set of this. And then a visit. So my color I start with one. And I want to start my first node, and I want to do a depth first search on my first node. I'm just wondering whether or not it's worth me building a graph, because this is really my graph. And then I need to build the graph. So okay, let's say and the length is the length of my graph. And that's minus one. And then I need to do a depth first search on and then I need to start with the so my starting node is zero. And then and then I need to pass in my graph and my visited and my current color leaf and I just need to go that's a my node. Probably don't need to put the graph root order visited. I just need to go my color. Because if I'm doing it using this, you can get you can get the values like so. So okay, so what we saying is if it's visited, if the node in visited then we need to actually check and then all this alternate the color actually, I said the colors others... have started We are Yeah, I don't need, I don't need, I don't need set visited, I could just have colors as zero times by the length of the graph which is n. And here, that's what I need. That's because if I said I need to visit it because it is zero, then I know that it's not visited. So if node, so my colors is not equal to zero. They're not saying that it's not visited. Sorry, that's saying that it has been visited. And my current color... Say, and the colors node is if it's equal, that's when I return false. That's what we're saying. So if it's been visited, and if they're both equal, then it's that's when I returned false. I'd like to pitch if it's really been visited. Otherwise, you know that it's not equal to zero, then we just we just return true because that's, yeah, I just can return true and just continue to visit my neighbors. That's what I'm actually thinking about, I just need to make sure, check is still traversing. That's one thing. And then this is when I actually do my color. And I do my color on my node is minus my color. And then... I just need to continue... I need to go through my neighbors. Yeah. neighbor. This call it? Yeah, your neighbor in graph of my node, then I need to actually say, yep, and this is when I do my result. And I need to do depth first search. Neighbor does my node. My color is minus. That's my next color my neighbors. And if up result, then I just returned false straightaway. And then if I visited at all, it should just return true. That's what I'm thinking. Yep. So at any stage that my result is false, I should just return it. So yeah, and then when I come out of this loop, I should return true. Sure if that works, sure. Initially, this one here. Do you want me to actually run through it manually or do you want me to actually... Run it? Run the actual solution.

Kind Dragon: Okay, if any, if it's up to you.

Ghost Armadillo: Okay. All right, let me try this one. This is, let's say, this one here. Then run it manually. We start with 0 and 1 first. So again, we say the color... We start with one. Actually, I don't. That's my first one. That's really something that I need to find out. Okay. So if my color is one and my node I started at zero. Okay, if there's nothing if I don't have anything in the graph is, what do I return just false? That's another thing I need to check. If there's no there's not a graph, I just return false or other bipartite. See if it's an empty graph. Just assuming that if it's an empty graph, it's false. Is that correct?

Kind Dragon: Yep, yep, that's right.

Ghost Armadillo: Yep. I said that's correct. Okay. Yeah. Okay. So now I start my node at zero, okay, I'll put it here. Zero, and then my color is at the moment, one, okay. And then my colors, which I'll put them here. My colors is what how we have through four. I don't zero for now. If it's not zero, well, that you won't go in there. If it's not equal to zero, you won't go there you go here. So now my color is changing. My colors should be now here. And this should be one. So it is just going to be minus one but that doesn't really matter. And I'll go to my neighbors. So my neighbor is one and three at the moment. So what's happening in my neighbors is one and three. And I was going through one so my neighbor current neighbor is one and I go through and depth first search on now the color is actually minus one. Sorry, it was... Yeah, I think this needs to be color. My bad. Yeah, says one is minus one here. That's why I found my bug. Yeah. Because we're doing it here already. Yeah. Okay. So and then my color is? Yeah, sorry. It's now minus one. And then I'll go through because my color here is one and then now I am at node... What node are my node one? So node one. I go through it's zero. So I go in and put minus one here. And then... Yeah, mine This one's neighbor. So once neighbor is zero and two, actually. Actually, here zero and two. And then I need to go through the neighbors here. So I'll go with zero, I've visited. Well, let's let's keep going because because we are there to zero go in... And it's minus. Because my current color is at minus one. So now it's actually a one. And this is no zero. So it should be if it's not equal to zero, which is correct. And two are missing my colors here. This is minus one. Yep. Yep. Can you hear me? Yeah. Okay, nice. Okay. Okay. Yes. Cool. Yep. So because I'm putting my neighbors now zero, let me just restart that. And then my color was was at one. So when I put this in, go into zero. It should be minus one now. But this thing is saying that if I know that zero, and it's not equal, and it's equal and returning false, I think that's not quite right. is equal to should be the minus color here, actually. Because it should, because that they're both actually equal. Yeah, that's where I'm actually going wrong. Think, let me double check. Let me try it. Let me try again. Sorry, let me start again. Because getting myself mixed up. So as I say, all those should be one because as I'm putting it here, as I'm just gonna get rid of this, because it was just confused me. Because my node is zero. It doesn't go down here. And then my neighbor is zero is one in three my current neighbors one, and I go in, my neighbor, and then my color now is minus one. And then my node is one. Then my neighbor of one is the color is now should be here. He goes to minus one and coloring it in. Which is correct. And then I'll go to the neighbors of one which is zero and two. So I'll go into my neighbors now. Zero. And then I go into my color. It should now it's actually one. Okay. Yeah. Yeah, so yeah, that's why so it's not quite right. It's that I do get zero and one. This is not a quite right? We should be the opposite, because I'm already doing the negative here. So because zero should be actually one.

Kind Dragon: Time is almost all up, we have only one minute. So okay, let me give you the feedback of the interview. For sure. That when you got the question, you easy to understand the question that is really good. And then after when I give you the graph, you use it to draw they're so cool. And then after the question, you asked additional questions, but yes, that is really good. But one more. Okay, but as you know, the ranks arrays start from one right? They mean that given an argument has on least one item. That it just makes sense to me at one vertex. Okay, let's go to line 93 actually does on it alone it. Yeah. Yeah. So when you have a question, please check the your constraint first. Otherwise it'll deduct from your score. Yeah. Yeah. And then BFS also making sense. But it is not, not best solution of the question. So I give you DFS hint and that you each issue, make the function by yourself. There are three requirements. And then I found out you are equal that Python, but they are a little bit minor in here, but your approach is correct. I think that you have a little bit more time. You can fix it by here. Yeah, sure. Do you have any question?

Ghost Armadillo: Yeah. Yeah. No, not really, actually. You've been helping me throughout.

Kind Dragon: I guess you are the you you are in UK. Right?

Ghost Armadillo: Australia.

Kind Dragon: Your pronunciation is quite similar to the UK.

Ghost Armadillo: Yeah. My English is very similar, because I'm from South Australia. So different parts of Australia. Yeah. So there's some parts of Australia that are more Australian. Like more both.

Kind Dragon: Because I mean, the United States, the New York...

Ghost Armadillo: Oh, wow. must be pretty tough. Are you there at the moment?

Kind Dragon: Yeah, that's right. That is pretty sad story. Medically from there. How about there?

Ghost Armadillo: We, we had the worst because I'm in Melbourne it we had the the most severe lockdown in the world. So we were locked out for three months. can't go anywhere for three months. I've called it as is actually very, it's not good for the mental health. It's very hard. But now that we've got cases again, so. Yeah. Yeah, we might be a bit in trouble, I think. Okay, but we got to spend Christmas outside and we can actually travel and all that. So that's a good thing. That Yeah.

Kind Dragon: Okay. Okay. I have to go.

Ghost Armadillo: Yeah, no worries. Thanks for that. appreciate all your help.

Kind Dragon: Okay, thank you very much. Bye bye.

Ghost Armadillo: Bye.