Java Interview with a Facebook engineer

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

Interview Summary

Problem type

Longest Path Direct Graph

Interview question

Given a direct graph. n nodes 0 to n-1. Find the length of the longest path from all nodes.

Interview Feedback

Feedback about Stochastic Hurricane (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

+: Strengths - : Growth Areas +: TC can deal with ambiguity. They clarified the both important requirements: is graph cyclic and how graph is represented. +: TC is good with data structures. TC comes up with optimal representation of adjustancy list for graph. -: TC struggles with basic complexity analysis. TC could not talk about complexity of the DFS algorithm. +: TC writes the modular code. TC wrote code with helper method of DFS. +: TC can write code with good speed. +: TC was able to change their solution for the follow up questions. -: TC has basic testing skills. TC missed few good test cases.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

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

4/4

That was a really good experience. His communication was good, he showed empathy/understanding and provided valuable feedback.

Interview Transcript

Red Maelstrom: Hey hi am I audible?

Stochastic Hurricane: Yeah. How's it going?

Red Maelstrom: Okay, I'm good. I'm good. How are you?

Stochastic Hurricane: Can't complain.

Red Maelstrom: Cool So basically 40, 45 to 50 minutes, focus on the coding problems. And last 10, 15 minutes, I will try to give you feedback, like, what could have been done better, or what I like and what you could keep doing?

Stochastic Hurricane: Cool. Sounds good.

Red Maelstrom: Yeah. So yeah, this is the first question. So basically, you have a directed graph. And you have to find the length of the longest path from all the nodes. So, for example, if you consider zero, you can go from zero to 1, 1 to 2, 2 to 3. So the length of the longest path originating from zero is three. And if you consider one, the length of the longest path originating from one is like one to two, two to three, so it's two. Similarly for two its, if length one, because we where just one is from two to three. There is no edge originating from three, that's why zero. And for four to three it's one, because you can go from four to three.

Stochastic Hurricane: Gotcha, that makes sense. And I'm trying to determine whether I should be worrying about cycles.

Red Maelstrom: That's a good problem. That's a good question. We can assume that for first part of this problem, we can assume that there are no cycles. It's a directed graph. And once we solve it, maybe we can introduce.

Stochastic Hurricane: Okay. Okay, that sounds good. So I'm just gonna select language here, just to make sure. Oh, sorry. I erased your whole. Oh it's still there cool, cool, cool. And then I'm just gonna run this to make sure I understand how this works. So it's just going to loop through this array and then return all the strings here. Okay, great.

Red Maelstrom: Don't worry about running it? Yep. I, we can just consider that. You, you, you need to write one from a function. And you wont run it, yeah.

Stochastic Hurricane: Okay. Okay, gotcha. I can write this out. Just

Red Maelstrom: Not even main, like we are okay if like we just talk about the function which takes this.

Stochastic Hurricane: Okay. Yeah. Cool. So I'll start by just kind of explaining my initial thought process. So I think so the input is it just going to be a list of tuples.

Red Maelstrom: You can assume that you have whatever format you want this input to be, you have it in that format. I'm okay with it. I'm even okay, if you can, if you assume there is a graph class, it provides you the whatever it is you require.

Stochastic Hurricane: Gotcha. Gotcha. Okay, so I'm thinking, just just kind of keep the input simple. It's just going to be a list of lists of integer. Yeah, exactly. And then that's going to that can look something like, here's the outer list, and then the inner list and like you had mentioned zero one, one two, and then outer brackets, etc. And then, so the first thing I was thinking about doing and something I like to do on a lot of graph problems is just to basically loop through this list this input list and then create a HashMap.

Red Maelstrom: Yeah, um, so you can assume you already get an input as a HashMap. Don't don't worry about processing into hash map. You can already assume that you have an HashMap as an input.

Stochastic Hurricane: Okay. Gotcha. Gotcha. And then sorry, I may have missed originally, this output list. Is this. This isn't in order.

Red Maelstrom: That yeah. Yeah. So basically, one more factor is like your graph has n nodes. I just missed it. Yeah, it has n nodes. zero to n minus one. So yeah, they are numbered zero to n minus one. They are not scattered nodes. So yeah,

Stochastic Hurricane: And sorry, I didn't quite get the output is supposed to be an ordered list. Ordered path rather.

Red Maelstrom: Right, no, it's like, for example, the longest path originating from node zero is of length 3. Zero to 1, 1 to 2, 2 to 3. That's why index zero has three. The longest path originating from one is like 1 to 2 and two to three.

Stochastic Hurricane: Oh okay, gotcha. So you're saying that the output is basically the number of nodes in the graph?

Red Maelstrom: Yeah, yeah. Yeah. The output size is the number of nodes in the graph, which is

Stochastic Hurricane: and then each index in the output, so like index zero, you have three, that means that there's the longest path for node zero is 3.

Red Maelstrom: Yes, Yeah.

Stochastic Hurricane: Gotcha. So, yeah, so the inputs a HashMap. And I'll definitely be using some sort of depth first search to determine the longest path per node. So I can start by just looping through the HashMap. And then for each node, performing a depth first search, and then once I do that, it's just for each node, it's just getting the max depth of that kind of graph or tree structure. Basically, it's almost like a tree structure at that point. And, yeah, yeah. So I can start by writing just I think there'll be two functions, one function will be kind of iterating through each node in the graph. And then the second function will be the actual depth first search function.

Red Maelstrom: Awesome.

Stochastic Hurricane: So this is going to return an integer. And it will be get longest path. And like you said, we're going to make it a map. And this map is going to have integers, the key and a list a list of integers as the value and that's just kind of like the children. And then we'll just call this graph. This, is all my syntax, correct? I think so. I'm not sure why I'm getting this.

Red Maelstrom: Don't worry about these things like

Stochastic Hurricane: Gotcha okay. Cool. So I'm gonna go ahead. And so we'll call, we'll do oh, it's sorry, that the output supposed to be?

Red Maelstrom: List of integers

Stochastic Hurricane: A list yeah, yeah. So list of integer. And so we'll, we'll, we'll add that as the result. We'll call this res new array list. And then, this is just yeah, this will be of size. Like, at the end, this is going to be a size. Graph, dots size, basically. And then we'll loop through map dot entry the map. Yeah, this is going to look like this. Entry. Graph dot in tree set. And then, what's going on here? Cool cool. And then we can basically do like res dot add at entry, dot, get key. And then DFS like that. Does that make sense? So this will insert the entry at the longest path at index, whatever the. Like, the noDe is, does that make sense?

Red Maelstrom: Yeah.

Stochastic Hurricane: Cool.

Red Maelstrom: And whatever the answer DFS gives right? Okay.

Stochastic Hurricane: Exactly. So I'm gonna go ahead and write the DFS function. Private int, it doesn't need to be private. DFS and then an important kind of an important thing to think about is what the input is going to be and what the base case is going to be. So let's see, you know, I'm gonna make, yeah, so I'm gonna make the graph a global variable. So it can be accessed from the DFS function without having to pass it in as an input. This dot graph equals graph, cool cool cool. Yeah, that looks fine. And so then we're just going to pass in, basically, all we need to pass in is the integer that we're trying to get the longest path for. Let's see node. We can actually make this integer node. And then for the base case, you know, we might not need a base case, we can just like loop through the children of the nodes, we can get like the children. Children equals graph dot get node, and then we can loop through the, integer child, children. Cool. And then we can do like int res equals zero. And then let's let me think really quick. So this is going to be a list of children. And then we loop through each child. And for each child, we're going to make another recursive call. This is supposed to and then we can return, return res plus one. Okay, yeah, I'm just trying to think about how this recursion is going to work basically. If we pass in, says zero, then zero will only have one as a child. So we'll loop through that. And we'll pass in one and one will have no children. And so we'll get just one as the path length. And that'll yeah, so we'll have to res Equals Math dot max, res for path length. So yeah, we pass in zero, and then we get one only a list of length one, I'm just thinking about this kind of input example, a list of length one, we loop through that list of length one we pass DFS, it doesn't have any children. So this is going to be or it does have children. I'm sorry, but just I'm going to assume it doesn't have any children just for the simplicity sake. So say it doesn't have any children. It could be null. So I need to handle like a null case gets. No, actually, I'm going to assume the input. If if a node doesn't have any children, it'll be an empty list. So the key will be the node and then it'll be an empty list. So I don't need to kind of I'm just going to make that assumption for now. So children one, so yeah, I feel like initially, I'm thinking that this recursion will work. So I think I'm going to give that a try.

Red Maelstrom: Um like, yeah, for any recursion, do you need some base case right? And then you will end it what will it look like?

Stochastic Hurricane: Yes, so I'm thinking, So correct me if I'm wrong, but I think, you know, basically, no, since we don't have a cycle, yeah because there's going to be no children. So we won't instate or create invoke any more recursive calls basically, if that makes sense.

Red Maelstrom: Right. Do you need to add a return statement in the first function?

Stochastic Hurricane: Can you say that once more?

Red Maelstrom: Yeah.Do you need to add a return statement in the first function?

Stochastic Hurricane: Yeah, yep. Yep. For sure. So it, yeah. So we just return results. And so

Red Maelstrom: Yeah, I think this should work. What would be the complexity of this?

Stochastic Hurricane: So we're going to So here, we're I don't know if you can see what I'm highlighting. But here, we're looping through every node in the graph. So let's say like, every node in the graph is like an n. And then we're performing a recursion for all its children. And so yeah, it's the time complexity for graph problems is always a little tricky. But for any sort of like backtracking or DFS, we're basically it's a lot of the times it can be like the number of recursive calls. So let's say on average, we have like two or maybe three recursive calls per node like three children, I mean, in then it would be to like the power of the total number of notes or something like that. Does that make sense?

Red Maelstrom: Do you know the complexity of depth first search in terms of if there are n nodes and like if I say like graph has n nodes and m edges with the you know the complexity of when DFS on this graph?

Stochastic Hurricane: it would be n times m.

Red Maelstrom: n times m?

Stochastic Hurricane: Yeah.

Red Maelstrom: Okay.

Stochastic Hurricane: Is that right? Oh, sorry, your you don't think that's right?

Red Maelstrom: That's right. Yeah, I don't think this is right.

Stochastic Hurricane: Okay, gotcha. Yeah. Okay. So let me think more then. So

Red Maelstrom: You consider like there are how many times you will visit any edge?

Stochastic Hurricane: How many times will I visit an edge on a graph

Red Maelstrom: For one call from, for one of this call.

Stochastic Hurricane: It will be, It could be. I want to say one.

Red Maelstrom: Yeah, that's correct. Because like, you will visit that edge when you are at first node of that edge, right. And you're going to start off that. So you will visit every edge just once and you will visit at max once not every time you will visit it you can visit and how many times you will visit nodes?

Stochastic Hurricane: Once?

Red Maelstrom: Yeah.

Stochastic Hurricane: Yeah. Yeah, definitely something I need to kind of brush up on this time complexity of graph problems. I'm honestly like a little. It's funny that you asked me a graph problem. This is something I'm studying right now. And something I've been kind of struggling with the time complexity on. I'm good with I'm really good with, like recursion and DFS. and stuff like that. But for some reason determining the time complexity for these is a little bit difficult for me. Yeah, to be honest,

Red Maelstrom: I can understand yeah, I've been in similar situations so. Yeah don't stress about it. So basically, you analyse it by, it's not a straightforward analysis, I know that. But like, the key here is that you will visit every child parent relationship only once. That's why you will use it every edge at max once and you will go through all the nodes. So it will be one n plus m for one one of the recursive call, but you will call that for n times. So it's basically n to m plus. Because you iterating for n times, so this is the first n comes from this for loop. n plus m is the complexity of DFS. Because if you consider DFS, right, so you will reach every node and you will use every edge once.

Stochastic Hurricane: Okay, okay. In worst case?

Red Maelstrom: Right.

Stochastic Hurricane: Gotcha. Gotcha. That makes sense. That makes sense. n times n plus m. Okay. Got it. Got

Red Maelstrom: Okay, so yeah, I think you solved it. But like, do you think you can optimise it somewhere?

Stochastic Hurricane: Yes. Yeah. Yeah, I was actually thinking about that briefly. Because in each depth first search, as you're, you know, traversing the graph, you hit, you can potentially hit the same node or child many times. So we can keep some sort of maybe memoization that a separate memoization map, that will, that will basically keep track of whether we have already found the max length of the path for a given node. Does that make sense?

Red Maelstrom: Yep. Can you do those changes?

Stochastic Hurricane: Yeah, let me give it a go. So I'm going to create this memoization map. It will be integer to integer that's node to max length of the path. And I'll just call this memo. And then, before we do any sort of recursion, we're just going to check if memo contains key node. And if it does contain this key, then we'll just return memo dot get node and then we'll do, we can do

Red Maelstrom: Do you want to make this first statement of a function?

Stochastic Hurricane: Hmm. That's, that's a good point. I think it can be the first statement of the function. It's, I think the reason why I didn't is because I'm so used to having a base case up here that I always want it under the base case, but I think you're right that we can't do under the first part of the function. And then I'll do memo dot put node and res plus one. We can put actually, let's just put a res plus. Yeah, it's kind of like repeating code here. I can just Oh.

Red Maelstrom: I think yeah that's okay.

Stochastic Hurricane: Yeah, yeah. I think that should work. And I'll add that to the function call here. We can just do a new hash map.

Red Maelstrom: Are you sure it should be new hash map for every function call?

Stochastic Hurricane: Great, great, great point. We'll do map interger memo equals new hash map. Yeah, yeah. That's true. Yeah. And then yeah, if it contains key we'll just return and if it's in the memo map. Then that means that we've already found the max.

Red Maelstrom: So can you analyse the complexity now, your improved complexity now?

Stochastic Hurricane: Yeah, yeah. Let me let me think about this for a moment. Oh, actually, I think I'm missing the parentheses here. Yeah. So this will basically, I think it'll actually just make it O of n plus m.

Red Maelstrom: That's good.

Stochastic Hurricane: Cool, cool.

Red Maelstrom: Yeah. So yeah, I think yeah we solved original problem, I have couple of follows up, one you already asked about what will happen if there is cycle in your current code. If we make any changes and this graph contains cycles, what how it will be, it will behave

Stochastic Hurricane: There will be a stack overflow.

Red Maelstrom: Literally, now, what I'm want is like from if there is a cycle, all the nodes which can reach to that cycle should return int max as a longest path. So for example, if I change my given example, lets say there is a H from zero to one. And there is also H from one to zero. Sorry, one to zero. Then for zero and one, you can keep repeating. That's why output should have like int Max, let's say some big large numbers. And int max for these two numbers. And for the rest of the things as it is.

Stochastic Hurricane: Okay, so if we find a cycle, we just put Max interger.

Red Maelstrom: Yeah, for all elements, which can lead to that cycle.

Stochastic Hurricane: Gotcha. Gotcha.

Red Maelstrom: Yeah, there could be the case. Like, for example, there could be an h from, let's say, four to four to one. That case four should also have int max, because you can go to one, and you can keep repeating from there.

Stochastic Hurricane: Gotcha. Gotcha. Yeah. Okay. So for I'm going to tackle this by using extra memory. And I'm basically, I think I'm going to use some sort of. So yeah, all these integers are unique right?

Red Maelstrom: Right within the nodes, right?

Stochastic Hurricane: Yeah, yeah, exactly.

Red Maelstrom: Yeah yeah

Stochastic Hurricane: No node has the same value. And so I think we can add another input parameter, and call it visited, and we'll make it a hash set. And so we'll know whether or not we've seen a node before. And if we come across a node that we've already seen, then we can just return integer dot max value, basically.

Red Maelstrom: Can you make the code changes for me?

Stochastic Hurricane: Yes. Yeah. So node. So we'd added visited. We've already visited this node. Yeah, I think we could add it I want to say at the top, here let me think about this for a second. Because I want to make it that if we start recursing and then we eventually hit the node, the original parent node, that this is recognised. So I think, we can do if visited dot contains node. We can return integer dot max value and yes, next. Uh huh. So the one issue I'm seeing here is integer overflow. So I don't really know if I want to return max value here. Because then we're basically adding one and then that'll cause an overflow. So I'm thinking that, can always be positive?

Red Maelstrom: What ones?

Stochastic Hurricane: All the nodes, are they all positive numbers?

Red Maelstrom: They are. Yeah, they are always zero to n minus one.

Stochastic Hurricane: Okay, cool. Great. So maybe I can just return negative one here. And then if memoed up, we can do if but then this is math dot max. Actually, yeah, actually, sorry, I'm gonna go back and make this return integer dot max value. And then yeah, then we can go if res equals integer dot max value, then return negative one else, return res, plus one, and then we'll just return memo dot get node and then we will here we'll do kind of something similar if we'll actually extract this. And then we'll put an int max or max path length. And then we'll do if max length is equal to negative one. And we'll do integer dot max value. Else we'll do max path length. Okay, so yes, so if we say, just to run through an example, if we pass in zero to this DFS, it will return that it'll return an array of children just containing a single element one, and then we do the one, but we add zero to this visited set. And then we do a DFS on the node of one. And then we come back into here, visited and we add one to the visited, to the visited set. And then we get zero and two as possible children, but we loop, we first do zero, and then we come back into this kind of third DFS and but zero will already be, zero will be in the visited array. And so we'll return integer dot max value, and that'll always be the max value for res. So even when we go through two, there's no way twos going to whatever the length of two is, assuming two doesn't have a cycle. It there's no way it's going to be max value. So then we'll return negative one. And then we'll have that up here. And then we'll add that to the res array at the specific index, like you had mentioned up here. Does that make sense?

Red Maelstrom: Yep. Do you also need to pass the set where you will pass the set visited sets from the original call?

Stochastic Hurricane: Yes. Good point. And this this one, we actually are going to instantiate it with every new function call.

Red Maelstrom: Makes sense. That's right. I think yeah, that that takes care of first follow up like I've second follow up is, here we are assuming the edges have just single weight, like weight of any edges single weight. Now say that our edges could be positive weights, it may not be one. So it could be every like zero to one can have weight of fours, one to five, one to two can have a weight of five. So each edge can have different positive weights. So if that is the case, like what changes you will require in your code.

Stochastic Hurricane: Positive?

Red Maelstrom: Did you get the question?

Stochastic Hurricane: I didn't quite understand. Are you saying each node will also have a weight assigned to it?

Red Maelstrom: Not node, edges. Like for example, when we consider the length of a path. The number of edges was the length of a path, right.

Stochastic Hurricane: Did you say, sorry, ages?

Red Maelstrom: Yeah, edge, edges on the graph

Stochastic Hurricane: Oh edges. Oh, I'm sorry. Okay, gotcha.

Red Maelstrom: Yeah, so number of edges was, was the longest was the answer for any node, right. But rather than that, what we can, what I'm saying is every edge, every edge will have a weight associated with it, for example, 01, and a four. Zero, like, one, two and like, flip the five, then the longest path from zero, ending at two would be like four plus five, not just the length of that. Let's say this is one. So the longest path originating from let's say, this is not there. If that is the case, the longest path originating from zero would be of length 10. Four plus five plus one.

Stochastic Hurricane: Understood. Okay, let me think about this for a moment. So we need to keep track of ah okay, so this kind of going back to what you had mentioned in the beginning, it sounds like we're gonna have to implement a separate class, or we don't have to, but I think for to make things neat. It might make sense. So, like, I could implement a second class and call it node in this could have like, like, integer parents, interger child and int weight?

Red Maelstrom: Will it be the node class? Or will it be the edge class?

Stochastic Hurricane: Yeah, yeah. So you're right, in that it probably would make more sense to call this edge. Because this basically represents the connection between parent and child and then the weight associated with that, like we were talking about. And so instead of like an input of a map to a list of integers, we can do a list of edges. And let me just change the code as needed. This will remain the same map. Memoization that should remain the same. Integer memo node. Yeah, that's the same this should be edges and then res zero int yes. And so instead of one here, yeah. It will be res is so we get a list of edges.

Red Maelstrom: You can't do it here right?

Stochastic Hurricane: Right, right. Yeah, yeah. Okay. I see what you're saying. So res will be math dot max path length plus and this will also be an edge right? Child dot weight.

Red Maelstrom: Uh are you sure? I think it should go. It should be like result is equal to Max. Max of result coma path length plus child plus weight.

Stochastic Hurricane: Oh like right here's what you're saying. Plus child, it could Yeah, it could be here or it can be up here, right? Plus, child dot weight. Does that make sense?

Red Maelstrom: That makes sense. Yeah I got it.

Stochastic Hurricane: Okay. And,

Red Maelstrom: What changes you will do on line number 49?

Stochastic Hurricane: Yeah. So we can return still Max integer. So that's. So I still need to make changes here, I'm gonna get an overflow potentially. So yeah, yeah, I think what you said before it makes more sense. So we can basically say if pass length is equal to integer dot max value, then we just return that. Else, we'll do path length. Oops, oh wow didn't mean to do that. Else we'll do path length, plus child dot weight. And so here, we don't need that. Yeah, I think that should do it.

Red Maelstrom: Cool. Awesome. Now lets say like we are done with this code. What kind of different test cases you would like to consider? To test your code against?

Stochastic Hurricane: Yes, so we can start kind of simple test case. Case, I don't know why it's auto correcting. And so we can kind of so so basically, it's like, we can like create, I don't know, I'm just going to basically give us a list of these tuples to represent the edge case unless you want me to, like instantiate a map and start to

Red Maelstrom: Yeah. Even even rather than tuples. You can just say that like, okay, a graph, you can just explain in plain English. And that's, that should be okay.

Stochastic Hurricane: Okay, rather than writing out here. Yes, yeah. So I would just, you know, have our kind of base happy case, like, kind of like almost the original one you had set here. Basically a test case with no cycles, I would have a test case with, or I would have maybe multiple test cases with varying cycles. And I would have, you know, like, a null test case. And that's actually something I didn't check yours if like, like do a null check if draft equals null. Then return collections dot empty lists, something like that, depending on what you'd like returned with null. This should be collections. And then I would also have a test case, with the test cases, with just varying weights, to make sure to handle all the different possibilities of weights and things like that, just to make sure that how I'm calculating weights per edge makes sense.

Red Maelstrom: Like, cool. Uh yeah, I'm happy. Like, these are good set of test cases, you've come up with. Yeah, I think we hit the 45 minute mark also, maybe like this is time where we move to the second part about the feedback. Right. So one feedback you already encountered is like, you need to brush up the complexity of known graph algorithms right. That stands there. For the rest of the feedback, what I will do is I can start from beginning to end I will say like, what I liked and what you can keep doing and what could have done better in terms of your approach. Okay. So yeah, I like the fact that spot on you ask the right clarification question about is graph, cyclic or if graph non cyclic. That was spot on, you also asked how the graph is represented. That was a really good clarification question at the beginning. And keep doing that, I like the fact, keep doing that. That's a good, good, good way to go. You straight away talked about the solution by using DFS depth first search. Do you also get breadth first search as an alternative solution while you're thinking about solution or you just got BFS?

Stochastic Hurricane: I'm very comfortable with DFS. So I usually just go straight to that.

Red Maelstrom: Okay. Like, do you get that this could also be solved with breadth first search? Okay, no worries if you didn't get that

Stochastic Hurricane: Sorry, I just need to think about it more, but not not like instantly.

Red Maelstrom: Okay, good. But like, yeah, this could easily be solved with breadth first search also. But if you didn't get that, what you did is good. But it's like, in some sense, whenever you get multiple solution to talk about, like, it could be solved by both. And why you will choose one over another that shows that you kind of can make a decision, and you can kind of talk about it off. But yeah, in your case, in this particular case, you did not get that second solution. And it's okay. And it's good thing like you did not waste time to find the alternate solution. But like, if you would have got both of them, you could have got a feeling that okay, this could be solved by DFS, or it could also be solved by BFS, then you should talk about it and why you chose one. But this wasn't the case. So it makes sense. Yeah so another thing like you once you say that you will talk you solve it by DFS you straight on when to the coding. This is the place where I would suggest you to take your approach. My position would be once you talk about solution. Analyse the complexity of a solution. It's best, but it's the best case if you can even prove the correctness of solution. But not, if it is straightforward to that, but don't worry about it. But at least the complexity analysis. Once you talk about the solution, do the complexity analysis and to ask interviewer whether he wants you to go and code the solution, like it doesn't happen that if you can spend five more minutes and you can optimise it and can give him the optimised code rather than writing an own optimised code. So my suggestion would be whenever you share the approach straightaway do the complexity analysis and follow that up with a question like, does this complexity, does this work for you? Shall I code it? So that like you are on the same page.

Stochastic Hurricane: Gotcha. So I just said DFS, I didn't give the complexity analysis, or the DFS should work instead of should be I'm gonna go with DFS. The complexity analysis will be our complexity will be roughly this. And this is roughly how it's going to work. Would you like me to go about coding this up?

Red Maelstrom: Right, right, yeah, this is like two cases like one is your approach is totally wrong. Or if you are solving it for some wrong problem, you have not understood the problem and you're writing a code for some wrong problem. And you waste time or you're you're solving it for the right problem, but you're not writing an optimal code. And we were fortunate enough here to have time to go back and optimise it doing memoization, but it might happen that if your time takes just before you are done with the code, and there are just four or five minutes and rather than giving you time to optimise it, interviewer might choose to focus on another area and he might consider that you are not able to come to optimal solution. So my solution would be once you are done with approach discussion, follow up with the follow it up with complexity analysis and ask him if this is something he wants, or you should try for something else.

Stochastic Hurricane: Gotcha. Gotcha. I like that.

Red Maelstrom: Yeah, the good interviewer won't penalise you for it, but it's not, if you're not like it's not your lucky day interview might not be that well trained and he might not poke you. And then he has nothing to lose right? It's it's you who is who is investing time and effort?

Stochastic Hurricane: Yeah, it's not much additional effort on my part to just do that. Makes sense.

Red Maelstrom: Yeah so that's the one thing. Yeah. In coding you are flawless or like, I really enjoyed the way you go ahead. I like you straightaway talked about modularizing code right into functions keep doing that good thing. Yeah and at the end, so let me know, like, how much for which roles you're targeting? Is it a mid senior senior or it's like starting roles, because like I, my, I would like to add few things if it's based on like this level, if you're trying to apply for.

Stochastic Hurricane: I have five years of experience. This is kind of my first cycle of interviewing I've ever done. I've just been at one company for five years. I'm my goal is senior, but mid level to senior.

Red Maelstrom: Yeah, so yeah, my suggestion would be to involve include validation, while writing code. Don't assume that input is always correct. Try to write a validation code, it's again, like you 30 seconds extra and my suggestion is like to add code to validate the inputs.

Stochastic Hurricane: So like a null check for and then maybe ask the interviewer, if it's possible that there's there could be other issues with the input.

Red Maelstrom: Right, right. It's okay. And it's totally fine. If you thinking like you're against running against the clock, once you are done with a code, do talk about that, I should have added validations that shows that you are a senior person and you have some coding experience, like try to give all the signals to him, right. It's basically he's trying to find a teammate, and he would like to have a teammate who thinks about validation and thinks about test cases. Right. So once you're done with the code, ideally, what I do is whenever I'm giving an interviews, while writing code, I first thing I do is I validate the input, at least basic validations to give him the sense that I do care about input validation. It's for me, like, I don't take interviews as to trying to solve problem. I take interviews as giving him as many signals of being a good software engineer as possible. Yeah, that is a place where I take the advantage, okay, like, yeah, let me give him a signal that oh, no, I'm just not a guy who write a code. I'm a guy who takes care of who takes ownership of my code. So yeah, once you are done with the code, and rather than pausing there, what you can say is like, if there is an awkward pause, you should think about test cases for your code. Rather than him poking you. Yeah, here, I was asking you some follow up questions. So that's okay. But if there is an awkward pause, you think like, Okay, you're done with the code? There is no, he's not asking any follow up question. It's time to showcase that my testing skills yeah.

Stochastic Hurricane: Gotcha. Gotcha. Okay, that makes sense. That makes sense. Cool.

Red Maelstrom: Cool, awesome. I don't have any other feedback. Like, yeah, I really like the way who took care of like, follow up questions. And you also, and you're always about keeping your code clean. So that's a good thing. So yeah, keep doing that. Just like just these tweaks in in the steps you follow, to solve problems, just to be good to interviewer. You're a good candidate, but it's like, just to be a better interviewee to help your counterpart, gather all the signals.

Stochastic Hurricane: Gotcha. It sounds like what you're saying is, it's as much about optics as solving the problem.

Red Maelstrom: Right, right. Right. Yeah.

Stochastic Hurricane: And quick question, if I had was able to solve the time complexity, would you have given me a thumbs up? I'm assuming because I couldn't do the complexity

Red Maelstrom: Yeah, yeah. Yeah. Currently, I would have given you a thumbs up, still given a your thumbs up with low confidence. But like, if you had come up with the clean complexity analysis, I would have given thumbs up with high confidence.

Stochastic Hurricane: Nice, nice. Okay. Great. Thanks so much. This has been quite helpful.

Red Maelstrom: Cool. Yeah. I think after the interview, you also need to submit The feedback for me. Yep. Cool.

Stochastic Hurricane: Sorry one last question. So this would be a question that is asked by. I know, I can't ask you what company you're from since it's supposed to be anonymous. But I can expect a question like this from, like any kind of top company or startup as far as like the difficulty of this question goes, how would you like? Rate it?

Red Maelstrom: Yeah. So it's, it's a Google. It's a Google level question like basically, yeah.

Stochastic Hurricane: Okay. Gotcha. Gotcha. All right. Thank you so much. I appreciate it.

Red Maelstrom: Yeah.Cool. Awesome. Yeah. Have the rest of the nice, nice day.

Stochastic Hurricane: All right. Take care.