Watch a technical mock interview with a MathWorks engineer
Jocular Panther, a MathWorks engineer, interviewed Quantum Tetrahedron in Java
Share
Summary

Problem type 

Verify rotated integer

Question(s) asked 

1) Given an integer, is the 180 degree rotation of it equal to the original integer? 2) Given a list of Product Id pairs, group them according to their categories and return the new list containing categorized Product Ids.

Feedback

Feedback about Quantum Tetrahedron (the interviewee)

Advance this person to the next round?
  Yes
How were their technical skills?
3/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4
1. Name variables and functions which sets the context for the solution. You can follow these guidelines: https://google.github.io/styleguide/javaguide.html 2. Type out your approach as you are talking through it. It can be just states of data structures you are using or pseudo code. Come up with more test cases (edge cases) if necessary. 3. Keep your code quality high. Something you would feel comfortable sending to code review. 4. Liked the fact that you stated time and space complexities before writing the solution. It's a good practice to have. 5. You did good in coming with the solutions for both the problems. All the best! and Keep practicing!

Feedback about Jocular Panther (the interviewer)

Would you want to work with this person?
  Yes
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
My interviewer was really good with the feedback and describing the small details that I needed to improve on. The questions that my interviewer provided to me were of different pace and helped me think and experience new subjects in interviews. I really enjoyed the interviewers demeanor and how well they pointed out flaws in my interview. I would definitely look forward to being interviewed by this person.
Transcript
Jocular Panther: Hello. Quantum Tetrahedron: Hi. Jocular Panther: Can you hear me? Quantum Tetrahedron: I can. Jocular Panther: So let's begin then. So can you introduce yourself? And, you know, after which we're going to solve a couple of problems. Quantum Tetrahedron: Yep. So interviewing for some practice. I'm going to be using Java. Just, uh, you know, looking for some good interview practice. Jocular Panther: Okay. Okay. Sounds good. Yeah. So let's begin then. I take this out. Let's say, I give you a number, something like that. If you sort of, imagine this number as an image, the entire number. Now let's say you were to rotate this, you rotate this image by 180 degrees. So this image is rotated by 180 degrees, it's going to be the same right? Now, because you know, like, think of you're rotating around this axis, you know, the axis is going to be at eight. Now, if you rotated, the number is going to be 16891. So given a number, can you tell me if rotated by 180 degrees, Is the number going to be the same? Or if it's a valid number? Quantum Tetrahedron: Okay. Yeah. Okay, cool. So just want to ask a couple questions before you know, I get started into the coding part. Yeah. So my input will be an integer? Jocular Panther: Yes, yeah. Quantum Tetrahedron: Okay. And my output should be like a boolean value or something like that. Jocular Panther: Yes, yeah. Quantum Tetrahedron: So will the number be... Can it ever be negative? Or can I always guarantee it to be positive? Jocular Panther: For now? Like, let's imagine it's just a positive number that I'm going to give you. Quantum Tetrahedron: Okay, cool. Cool. Is there like a range of this number? Maximum number? Jocular Panther: It should not... I mean, like, you can now consider it as an integer. But, I mean, but for an image, it should not really matter. Because, yeah, but for now, let's, let's consider it for integers. Quantum Tetrahedron: Yeah. Okay, cool. Cool. So, is there like any, like, any time or memory constraints you should be aware of before I start talking about the solution or anything like that. Jocular Panther: For now, you know, you can probably, you know, tell me your solution. And later on, if there is an opportunity to optimize properly, we can do it later. Quantum Tetrahedron: Okay, cool. So well, for my solution, what I'm thinking about right, is I just want to know whether or not a number is valid if you rotate it 180 degrees, right? Yeah. Yeah. So if you think about like, numbers, right? What I want to do first is I want to point out the numbers that if you rotate them 180 degrees, they are you know, they're still the same, they're they're still the same. Or when they rotate 180 degrees, what they look like, right, okay, correspond to another number, right? So for example, one, rotate 180 degrees is one, six, rotate at 180 degrees is nine. Nine rotated 180 degrees is 6. 8 rotated 180 degrees is 8. And 0 rotated 180 degrees is 0 as well. Let's see. So we have 123456789. Okay, yeah, I think these are five numbers that would rotate 180 degrees, they become another valid number. Okay. And so, what we can do, my proposed solution is to take the input number, right and begin... Well, first, before we even get to the solution, what I want to do is create like a mapping between these numbers I listed here. So ideally, I would use, like a hash map where the key value would be one, right? And then like the value of the hash map would be the rotated 180 degrees number version of it, right? Okay. And then jumping into my solution, what I want to do is, I want to iterate through the number, right, from right, to left, right. And what I want to do is, I want to, I want to essentially just create the 180 degrees, rotated image of it, right. So for example, for the number input we have here, what I'll do is I'll take one, right, I'll go into my mapping, I'll find the 180 degrees version of it, and then I'll add it on to like some, let's say like some, some variable that holds my 180 degrees, rotated resulting number, right? Okay. And then I would move on to nine, I will check my hashmap. Okay, nine corresponds to six rotated, so then I add six to the end of this one here. And then I go to eight, and then six, and then one, correspondingly. And then after I do that, what I'll do is I'll check to see if my rotated number is equal to my input number, right? And just to reiterate the problem I want to check if the rotated number is equal to my input number, right? Okay. Jocular Panther: Yeah, if you rotate, like, if you have any number combination with these, you know, whatever numbers you have listed here, I guess, if you rotated by 180 degree? Yeah, there are more or less going to be... not the same. But for now, let's imagine that if the numbers are equal, if the input and output numbers are equal. Quantum Tetrahedron: Yeah. And then so we know for the algorithm, the runtime would be equal to O(n), where n is the length of the number, right? Because I just had to iterate through the number and then space complexity will be constant, because I'm always holding just five elements. Jocular Panther: Like, what if? What if, you know the number has like 10 digits or more than 10 digits? This can also be for now, let's say 1689. And then six or something like this? Quantum Tetrahedron: Yeah, but it would still be constant, because all I need is the mappings. And if I ever run across a number that is not in the mapping, then I'll return false immediately, because there's no valid number that equals my map matching. Jocular Panther: Okay, okay. Quantum Tetrahedron: Yeah, so I'll only always need to hold the five numbers. Jocular Panther: Okay, good. Yeah. Quantum Tetrahedron: Okay, cool. Um, yes, I'm just gonna get started. So I'm just gonna do a class definition. I'm just gonna set up my main function, public static void main. And then what I will do is, I'm just going to create the function that we talked about public static boolean, as we discussed, and I'll call the function isValid right? And then input value. input, right. And so, you know, like, I guess, like, it's more practical sort of talking, you know, like, if this is like a class that's to be used, you know, more commonly, I guess I could just have like, you know, Well, this is like a class can be used in like a larger system, or something like that. I might just have like, you know, my hash map saved is like a more of a global elements, I just having to create it every function, but for now I'm just going to create it and just for the assumption, okay, yeah. So it's going to be a hash map of integers. So I'm just going to, you know, create this mapping that we have here, that is highlighted above in the comments. Okay, cool. So now, you know, we're gonna get into, like, you know, the algorithm, we have, I guess, one edge case that I, you know, I guess it doesn't really help my algorithm take care of that. But like, one edge case, we would have to sort of take care of it's like, a number, like, that's the end to the zero. But like, it won't matter, but I'm just saying, you know, at the end of the zero, then like, zero, go in front to like, for example, like, she was like, one zero, then it would go like 001, essentially, but the way I'm gonna set my algorithm, it will just turn to one. So it won't be valid. But that's just something to keep in mind as I guess. Jocular Panther: I mean, this is, like, if you rotated by 180 degree to be like, 001, which is not equal to the input? It's going to be, it's going to be false, right? Quantum Tetrahedron: Yeah, yeah. So yeah, I'm just gonna create this variable called reverse. And so what I'm going to do, right, I'm just gonna have a while loop, and it's gonna do, while input is greater than zero. Then I'm just doing while input is greater than zero, because I just want to grab every number as long as it's valid. So as I start taking the numbers from right to left, eventually I'll end up at zero after I take the last number. And so the way I'll do this is, I'll grab the right most number by doing.... rightmost, I'll just grab it by modulo-ing the input. So input modulo, 10. And modulo-ing it by 10 will always get the rightmost digit for me. Right. And so what I'll do is, I'm going to have a check here, you know, because I guess I should have asked this in the beginning, is like, you know, can any digit be in my input? Or is it can only be the five digits? Jocular Panther: No, it can any, like 123456789, whatever. Quantum Tetrahedron: Yeah. Okay, so I'm just going to check if not, hm contains key, right most, then we know right away that this is not a valid number, because we can't find a reverse mapping for it. So we're just gonna return false. Because there's no need to check any further, right. But if there is, you know, if it makes it passes, if there is going to be one, so we want to do is we want to add to reverse, right? Well, actually, let me stop there. What we want to do is, we want to multiply the reverse by 10. And we want to do that, because we want to make space for the new digit, we're going to be adding, right? So that's what we want to multiply by 10. And then after we multiply reverse, or the reverse number by 10, then we want to add the reverse mapping number. So then we add in, hm dot, right. And then the last step is to move our iterator for input. Or, like since we just prune our number in a way, by just sort of getting rid of the right lowest number that we just use, the way to do that is just divide it by 10. And then that should take care of itself. And then the last thing to do is return if the reverse is equal to... well actually looks like I need to have a variable to hold the original number, or how else am I going to know, you know? So, you know, then I'll have this check here that is equal return true. If it's not equal, we return false, okay. Jocular Panther: What's the space complexity now? Quantum Tetrahedron: Space complexity is still going to be I mean, if you know you think about it's still going to be constant, in my opinion, because your hashmap. You're always just gonna hold five values for the function, reverse, we have these two integers, right, the two integer variables, they're always just going to hold 32 bits. So regardless of the number we have, and then there's always just going to be 32 bits. And it's never going to change regardless of the input. So in my opinion, space complexity is still constant, okay. We just have, like, right here.... Solution is supposed to be capitalized. But yeah, I think we can try this out now. Okay, well, it's true, man, we can try you know, like 100. False. We can also just like, create, like, if you want, I can just create like that, you know, your testing function or something that like, you know, run through all these things? Jocular Panther: Let me see, because zero is gonna get reversed. Quantum Tetrahedron: 010, 0 should get ignored. Interesting, is because of this interesting input, because... So essentially, yeah, it's just like, I don't think like Java should have, like, you know, to give this number or something, because it has a zero in front of it. It's not a valid integer, essentially. Jocular Panther: In Java 010 is not a valid integer? Or does it really convert it to 10? If it does, if it does get converted to one zero, then it should return false, right? Because that's right? I mean, ideally, for the input, like if I if you consider this as an image, then it should return true, which your solution is doing. But ideally, the solution, probably because I don't know what what exactly is going on in the solution like, like, based on your solution, it should have written false, right? Quantum Tetrahedron: Yeah. I mean, if you, like, if you take it as like a string or something, right, then yeah, it would return, you know, for something like, you know, it returned true, right? Because, you know, is equal the same image, but like, I just sort of want to see what his input is. Yeah. I just want to see what an actual input is. Cuz I'm actually very curious about this... 8. The thing is, this is interesting. Seems like it's taking the binary version of the number. Not even the binary version. This is like three or four or something like this is, this is weird. Jocular Panther: This is something I mean, I'm not doing Java for a while. Even this is interesting. Yeah. So for now, why don't you change the input as a string? And can you change your solution to handle it? Quantum Tetrahedron: So I guess yeah, I could do that. I just want to make a couple more... Jocular Panther: Yeah, we should consider it as a string from the beginning, because like, I want to sort of wrap into numbers like 010. Since you know, I'm talking about images, right? Quantum Tetrahedron: Yeah. Yeah. Yeah. I just have a couple questions for that. Like, you know, we're going to change our inputs have a string input, right? Okay. Yeah. So that means is, you know, so that means, like, you know, can we have? I guess my question now is like, do we want to know if it's like a valid integer? Or do we just want to know, is that equal to the input? Yeah. If it's just equal to the input, okay. Yeah. So in like, I'm just going to have integers in it as well, right? Jocular Panther: Yeah, this is going to be just, you know, collection of integers. Digits. Yes. Okay. Yeah. To be four or whatever, you know, are the integers that you have in the map as well? Yeah. Quantum Tetrahedron: Okay, cool. Yeah, so we can definitely just change this to have to, you know, figure this out. So we can do, you know, just change the input, right, obviously, some things we need to change about it. First and foremost, you know, there's a lot of things we need to change about it. But now we can just have like, you know, the input greater than zero sort of solution in a way. So what we're going to need to do is we have a string now, you know, for all of our integers, which, you know, makes sense. So what we're going to do is, for our reverse variable that we had before, and so the integer, we're just gonna have the empty string, right. And then, for our original variable, we're just going to have, we're just going to have it like, you know, it's a constant holder to see what, what it what the originally was. But now, what we will also want to add is like a variable called like an iterator, so we can iterate through the string, right. And we want to set it to the rightmost element, so we need to input dot length minus one, right? And we can change the conditions for our while loop. So we can change it to while picture is greater or equal to zero, right. And I'm just going to go ahead and get rid of a lot of this logic, because it's no longer valid in terms of input as a string. But for this one, I'm just gonna, I'm just gonna leave this empty for now as well, which gets through it. So my solution is similar to what I said before, when the input was just an integer. What I'm going to do is, I'm going to iterate from the string from right to left, I'm going to get the numeric value of that character, because I'm assuming I can get my input is always going to be valid and will always only contain integers, right? So I'm just going to get the integer value of that character, I'm going to see if that integer value of that character is in my hashmap. If it is, I'm going to get the reverse mapping of it and then add it to my reverse string. If it's not, yet again, I can return false because there's no point because there's no reverse mapping, right? And then I'll just move my iterator to the left one so I could go on to the next character. Okay. And then, you know, it's a bit I guess you'd say it's a bit more tricky, I would say because this I would say the only difference the time complexity would be the same, but the space complexity I would say we need now more towards O(n) because you need to like have a variable that holds the length of the integer, right? So now it would be like time, complexity O(n) space complexity O(n). So yeah, so I'm just going to go ahead and get into it, it's going to create a variable called right most that we had last time, it's going to be equal to character dot get numeric value of, and this will just get you look at the number value of the character that you pass into it. So we just do input, and actually, now that I think about it more, I don't really need this original input, cuz I'm not altering the input at all. Yeah, check at the end. Yeah. So you just input that charAt. I mean, like, what, like, it depends on like, how clean you want, like the, the the code to look, you know, people depend, you know, people will rather have like, one liners, two liners, just like that, but I'm just gonna keep it like, you know, more readable. So I'm just going to have, you know, the iterator. So we want to get the input, that char at the iterator, and then I'm going to do in a separate line, the deep decrement of my iterator value, I could do it here. But you know, just want to make it look cleaner. Yeah. But yeah, so can I get the numeric value. Check if it's in the hashmap, like before, it is, then what I want to do is I want to add to reverse plus equals, I want to add the mapping of right most that I have. And then last thing I want to do is I just want to return reverse dot equals input. So that I return the input. And then the features are here. Let me just get your answer. Yep. It will be false for this one. And true for this one. Jocular Panther: Okay, so I know that I mean, it's definitely the solution. I mean, definitely works in O(n) and, you know, time complexity. Can you think of like a more optimized solution? I know it's all fine. But do you have to, you know, create this reverse? Can you do it in? I mean, what I mean, what I meant is? Can you do it in O(1) space? Quantum Tetrahedron: O(1) space? Yeah. Yeah, yeah, yeah, I can do that. So the way instead of just creating this reverse input string, right, that we have, and just holding it and values and things like that, what we could do instead is, we could just have, you know, I'm just going to put it like in comments. So we can, we can implement it later if we want. But so what we're going to have instead is we could create a second iterator, right. And we have in pointing to the left of it right, to the left most value of it. And then what we can do is, we can just grab the mapping, right, like we do here. And instead of just, you know, adding on to the reverse, what we can do is we can just turn that into like a char element, right? So like, we can, instead of having integers to integers of a hashmap, we have characters to characters, right. And then when we get through one a degree reverse of a character, we can just check if it's equal to the mirror mapping of it on the other side. So for example, for this number up at the top, for example, we can have an iterator for one iterator at one one iterator at the other one, the other end. We get the reverse mapping of that. And then we check it compared to its mirror value on the other end, and we say okay, it's equal, we can move forward one, and then it's equal move forward one, yep, it's equal. And then that would be constant time complexity, because all we would need is just another iterator. Jocular Panther: Okay. Can you implement that? Quantum Tetrahedron: Yeah. So I'm going to go ahead and change that. To get rid of that right for now. And so what we want to do is, this will sort of change the time complexity in a way as well, because instead of like, O(n) now, to be more specific, it'll be O(n/2), because now we only essentially need to go through the the input element, only half the way through, we don't really need to go through it twice. Or like, the whole thing, we only need to go half of it. Yeah, so I'm just gonna have this other iterator called two have been changed the bounds of it. Change the bounds of it. So that iterator two is less than or equal to iterator, the first iterator we have, right. And also just make it a little bit easier. I'm just gonna make all these maps, this mapping now changed to characters. Okay, and then. So now what we can do is change this to a char. And we can get rid of this API call to character to get new value, because right now we just want the char of it, of the rightmost. So we, you know, we can guess we don't really need to have this as... Oh, yeah, I guess we do need to have this because if it's not in there, then you know, it's already full. There's no point. Oh, right. Yeah. So now we can just have another char called reverse just for the name here. And it's going to be equal to h, the hashmap get right most. And then what we also want to do is iterate to get the char from the left side, like we did. For above, we're gonna have a char called leftmost. It's going to be equal to input dot char at iterator two. And what we want to do is also increment our iterator to one. And then the last thing, we want to do is check if leftmost does not equal to reverse, then we want to return false. Right. And then it makes through this while loop without returning any false items then we know the stream must be valid. Jocular Panther: Okay, right. Yeah. Yeah, that's the other one. Okay. Okay. It works. Just to sort of, I mean, nitpick, I would ideally like to, to sort of, you know, name the variables, like, with the right context, like, I mean, this is just to, you know, sort of let you know, that for companies, like, you know, Google or, you know, like, of big four companies, you might know, they want the code to be of highest quality, you know, as if you're sending the code to code review. And this is just to sort of let you know that, like, if you're practicing, sort of, instead of naming, hm, probably can think of, you know, like, a variable which gives you which gives context to what you're actually what's actually trying to do. So. Yeah. Apart from that. Yeah, I mean, you came, you did a good with the two solutions that we implemented, it works. So let's move on. I will... Let me give you another problem. Because we still have time. So, okay, so let's delete this. Okay, yeah. Okay. Okay, in Java, it's fake, okay. Take a few minutes to go through this problem and then like, tell me the solution, like how you're going to implement it. Quantum Tetrahedron: Okay, let me just take a second. Okay. So, from reading this problem, it looks like essentially just asking, you know, given a list of pairs that correspond with each other or are associated with each other, find all the ones that are all associated to a group them all together, essentially. Jocular Panther: Yes, yeah. Quantum Tetrahedron: Yeah. Cool. So, you know, just got some questions for it, you know, get started into anything. You know, can you always guarantee that the input will be provided in pairs. I won't ever have like, three or four pairs or anything like that? Jocular Panther: For now just start, you know, a pair is gonna just have I mean, just two elements here. Quantum Tetrahedron: Okay, and input will be a list of lists, or...? Jocular Panther: Yeah, I mean, it's gonna be like a vector of vectors, right? Um, I mean, okay. Quantum Tetrahedron: Yeah. Yeah. That makes sense. And then I want to return like a little list of lists of solutions? Yeah. Yeah. So it looks like I can have duplicates in here? And is there any ordering that you want me to, like return the ids in other than like, or can just be any ordering at all? Jocular Panther: They can be in any order? Quantum Tetrahedron: Okay. Cool. So thinking about this problem, it's sort of reminds me sort of, like, close to a graph sort of problem in a way, where you have all these edges, and that are associated with these points. And what you want to do is just, essentially just find... Essentially, just want to find out the word for it, but it's like, the, like, you know, the groups of nodes, essentially, after you have all these edges, right. So, you know, brute force, sort of straight ahead method, or like solution I can think of right away is just to do like, first, a little bit of pre processing. And what we want to do is, essentially just create, like a mapping of edges, right? And what I mean by that is, like, make it easier for me to find out what else what other nodes are connected to the current node I'm on, right. And so what I'm thinking is like, you know, to use a hashmap, where the integer value or the where the key value will be an integer, right. And the value of the hashmap will be, since there are duplicates, I see here, I would say, the value of it will be a hash set. And that will just in what the hash map will represent, like I said, was the number of nodes or the nodes that have an edge associated with the key, right? And after we do that, what we can do is, we can just do a sort of depth first search, you know, recursive algorithm, where we just go through the nodes we have, right? If they haven't been visited before, we want to do a depth first search through them. Add, you know, like, look at every single no revisit, right? Add them to a list, right? And then once that return, we add, we take that list, and then we add it into our resulting list. Right. And then, you know, one thing to keep in mind here is that we always want to, we want to keep track of all the nodes we have visited, so that we don't like end up in like, sort of like a cycle, right? Because it sort of looks like these edges could be undirected. And we also want to make sure that we don't revisit a group of nodes we've already been revisited once already. So yeah, that's essentially what my algorithm, that's always my solution would be, and it would be the time complexity of that algorithm would be first would be n, and where O(n) is the number of nodes to create my hash map first, and then O(n) again, to do the depth first search to gather all the groups of nodes together. So it would be O(2n), and then my space complexity will be O(n) as well, in order to hold all the nodes. Yeah. I think, yeah, that's a solid solution. That would do this. Jocular Panther: Yeah. Yeah, for sure. Just go ahead and start on, you know, go ahead and implement this? Quantum Tetrahedron: Sure. Yeah. Same thing for class. My main function are just gonna have the function we talked about. So the public static. And, you know, I'm going to return a list of lists. And in Java, we have lists. Yeah, similar to like how C++ has like the vectors with your brackets and like a list of arrays, an array, how to essentially same thing. And what I'm going to have is, is going to call it categorize IDs. And then I'm not sure how the inputs have been played. So I want to do now is I just want to create that edges mapping that I talked about in the beginning. So I'm going to have a hashmap, then to have an integer. And you know, I'm just gonna call it edges. Then now, what I want to do is, I want to go through my input, create the mappings, right? So I just wanted to go through lists of integer. What I want to call this is I'm just gonna call this pairs right here. And, you know, like I said before, it looks like this can be sort of an undirected sort of graph in a way. So I'm just going to have to do like dual mappings. You know, thinking about it, I could not... I'd rather have it as undirected graph, and I think it makes it slightly easier. Yeah. Yeah. Yeah. So I'm just gonna do input, if absent, this will essentially just put in my hashmap the hashset if it's not already there, just copy this part. And now what I want to do is I do edges. So now we want to make the recursive sort of function. Right. So we want the recursive function, I'm just going to create the recursive function first. And then I'm going to come back to this main function to create the logic that sort of implements or sort of sets up the recursive functions depth first search function. Right. So I'm just going to have it as a shouldn't have as a void function. And I'm doing that because what I plan to do is, essentially, I want to just, I'm going to have a list object in my recursive function. And what this recursive function would do was just add in the nodes I see into that list object that I have an input. So here's a couple of variables that I want to have in place. First, is current node. Second, what I want to have is the edges. So I can you know, yet again, you know, like I said, in the last time, I could, you know, if this is a function, or a class that's being or function that's being called a lot on a specific object, I would just have the mappings already created, and now, you know, as a global for various variables in class. But yeah, we're gonna have a local. And then, what I want to have is my list of integers, which will hold all the nodes I've seen so far. And I'm just going to call this product and current node. And then last thing I need is something like a hash set that can prevent me from going in cycles, because it's a doubly or it's a you know, like, an undirected graph so I'm just going to do the hashset of integers called visited. And so, in this recursive function, what we do is right, like, I visit this, this node, right? So I'm here, so I'm just gonna have product dot add current product, right. And then I also want to add this product to my visited. Right. Now, what I want to do is I want to go into my edges list. And what I want to do is iterate through all the edges connected to where I'm currently at. And I want to check first, have I visited it before, if I haven't, then I want to recurse down that node. Okay, so I'm just gonna have an edge, I'm just going to edges dot get current product. Then I want to recurse down to this part. Right. And then since it's a void function, I don't really need to return anything, we just end on it. It doesn't after it goes through all the edges, or if none of the edges, or if all the edges, all the edges associated with this product have been visited, you'll end up with them. Okay, so I'm just gonna go ahead and quickly, you know, I'm just gonna go and quickly implement the algorithm to set this up, this recursive function. So what we want to do first is, I want to have just set up my list of lists. And I'm just going to call it categorizedProducts. And one of the things that you have to keep in mind up here is similar to how we have a visited hash that to keep track of the nodes you visited before, in order to prevent repetitive searches for the same group, we want to have another hash set as well, to let us know what nodes we have visited. And this will just make sure that the algorithm doesn't have repeated groups. So I'll just call this... and we'll bring you more onto this. This hashset that we have here is actually going to be this hashset that we pass into here. And it's going to be it's going to be like that, because we want to, it'll help us reuse a data structure as well as it just makes sense that we pass this visited in, or this visited hash set into a recursive function, because we want all the nodes that any recursive function has visited, so that we don't repeat ourselves. Right. Yeah. So now, you know, the finishing touches. I just want to iterate through my hashset or hashmap on keys, which essentially hold all the all the unique nodes, or the whole unique products, edges, key set. And then, you know, if not visited contains product. I want to have a list with integers, this is a list that will be filled up on our recursive function of consistency. And then I'm going to call my function product edges. And then the last thing I want to do is I want to add it to my categorize and then I want to return to and then they'll return the function for me. Yeah. Jocular Panther: Try it with the sample input. Quantum Tetrahedron: So in Java may be a bit verbose. So I'm just going to have to, like had on the pairs I just add on like, yeah, the guy just got to create like a list of lists. Jocular Panther: Don't you initialize, like, in the declaration itself as in, not in Java, I'm forgetting it. Like, it's been a while since I used Java. Quantum Tetrahedron: So yeah, I think the closest thing you can do for initializing a list is like, like have have like an array, because you can initialize arrays with objects, and then you have to, like, instantiate the array into a list. Jocular Panther: Yeah. So I mean, due to a shortage of time, but, you know, I just want you to focus on this solution. And I'll get nowhere. And, you know, can you think, you know, if this if it's doing the right thing? Or can you see where it could probably, in the sense that, like, you're basically adding the products no matter what. And you're also adding it to the visited? Like, I mean, can you think of sort of correcting this, I do see an issue with this function. Like, for example, you know, like, I go to one, and then I go to two, I got it from two to five, okay. And then you basically, here in this loop, you again, pick up the edge, which is a two, and then you come here, and then you again, add it to the product. So can you can you think of a way to sort of get that, you know, function, right? Quantum Tetrahedron: What I can think of right, is to change sort of the ordering of how I do this. So one way to do this is... Well, I think there's sort of two ways to do this. One way to do with is, if visited contains current product. Another way is to just do this. Just add it, as soon as you get it, as soon as you see it. So like, hash sets have a function called add, right? And add will return true if it's not in the hash set and false if it's not, if it's already in there. Jocular Panther: This is what this is the condition that I'm actually I was asking you to look into. Yeah, this is good. Because, I mean, I guess without this, I believe if without this condition, probably you're gonna have a lot of duplicates in the products array. I mean, since we're not really verifying with any input. I just wanted to, you know, sort of let you know that without this condition, probably, I guess we might have duplicates in the output and that you might you might that you're returning so yeah.
Want to get some practice yourself?
Become awesome at interviewing, and get actionable feedback from engineers at top companies – it’s 100% anonymous!