DJ Cyclone, a Snap engineer, interviewed Massively Parallel Hedgehog in Python
Deep copy linked list
1) Write a function that checks if a string is a strict palindrome. 2) Write a function that checks if a string is a palindromic phrase. That is, it ignores non-alphabetic characters and ignores case. 3) Write a function that deep copies a linked list, where each node contains data and a pointer to a different node. 4) Print a linked list in reverse order.
Feedback about Massively Parallel Hedgehog (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
Overall, very strong interview. If this were a phone screen I'd give a strong recommendation to bring onsite. For the first problem, is_palindrome, the candidate did great. Got an optimal solution to the first version right away, got an acceptable solution to the second version, and when asked to optimize got the optimal solution quickly and without prompting. For the second problem, I gave them copying a linked list with random pointers. They had a good idea at first, but got off course for a few minutes because they didn't realize that they could use an instance of a class as a key in a dictionary. This is one thing I'd recommend improving on, if using a higher level language like Python make sure to be familiar with ways to work around the lack of more traditional pointer operations that can be useful when you're doing problems with linked data structures. (That, or maybe ask the interviewer if you can switch to a lower level language for those types of problems, if you're comfortable with one). I did have to give a hint to get them on the right track here, but they took it and ran with it, coding up a correct solution in quick order. After that I gave them printing a linked list in reverse as the last question. I didn't expect them to get all the way to the optimal solution because we were approaching the end of the interview, but they actually suggested the optimal solution right away and did a great job of coding it up quickly. They made one small logical error which I got them to correct by running through a test case. One note there: when working through a test case, make sure you really go line by line and trace through what your code will be doing exactly as it's actually written, not what you think it will be doing. Often it's a disconnect between the two that the interviewer will be trying to clue you in to. Overall, very good interview, easily top 90+ percentile of phone screens I've done. Problem solving skills were strong, coding skills very strong. Communication is good.
Feedback about DJ Cyclone (the interviewer)
Would you want to work with this person?
How excited would you be to work with them?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
Massively Parallel Hedgehog: Hello? DJ Cyclone: Hi, can you hear me? Massively Parallel Hedgehog: Yes. I'm wondering if there's a way to join the audio with a phone? Do you know which numbers I should dial if I want to join this with the phone? DJ Cyclone: I believe there is, but I'm not sure how. Massively Parallel Hedgehog: Okay. Let me just spend one minute to try to find out if I can. DJ Cyclone: Okay. Massively Parallel Hedgehog: Oh, I see it. Hello? DJ Cyclone: Hello, can you hear me now? Massively Parallel Hedgehog: Yes, good. DJ Cyclone: Okay, cool. So I'm Robbie. Just to give you an idea of how this is going to go, we're scheduled for... Sorry I'm going into my like normal work interview script. We'll probably spend around 40, 45 minutes here, expect to wrap up about 15 till the next hour. I'm just gonna ask you, you know... we'll talk a little bit about your experience. Most of the time, I'll be asking some technical problems. So for these, feel free to use any language you're comfortable with. Cool, so just to get started. You may tell me, and you know this is anonymous of course, so you know, don't... If you don't feel comfortable answering anything name-wise... or sorry if you're worried about an answer giving away who you are, you don't have to answer, that's fine. But if you can, I would love to just hear about maybe you know, what is the the project that you're the most proud to have worked on and why? Massively Parallel Hedgehog: Oh well, actually, that's a great practice because I have an actual interview coming up and the company is known to ask a lot of behavioral questions. So about one project I'm proud about... Okay, this will be a virtual reality experience. So I was taking this online program that teaches you how to make a game in virtual reality, right? And then there was like a course project which asked you to make a boring maze, which has certain mechanics like you can move around, you can collect keys and enter doors. I decided to make a creative experience by telling a story using lighting, audio, and special effects. So basically what I made is a horror theme experience, right? So the user is loaded into a maze in a very relaxing afternoon and then after a few minutes, the sun goes down and everything starts getting creepy, like the environment is like an art gallery and there are a lot of like creepy paintings from artists like Picasso and Salvador Dali, and then there was this special effect. So when you look at some painting for over a few seconds, they turn on fire, like randomly, and there is women's laughter and children's crying. And then like eventually, you're given instructions about how to escape the maze, and then your left on top of the tower, and then suddenly an army of burning zombies approaches your position, and then once the zombie comes comes close, you're pushed behind from the tower and then you're dead. And after you're dead, you're loaded to like some kind of after death heaven, where it's a very like beautiful beach, there's a beautiful girl in bikini waiting for you, so that's kind of this goes. So, I'm proud of this because I made a boring, very boring course assignment into a very creative experience and right now this app is published on Apple Store. DJ Cyclone: Oh wow, interesting. Cool, score any extra credit for that? Massively Parallel Hedgehog: Oh, extra credit, right. This is like not for school, it's like an online program. My project was actually nominated the best student projects for that cohort, so yeah, that's extra credit. DJ Cyclone: Alright, cool. Well, let's go ahead and let's start with a technical problem here. So cool. Alright, so it'll be python comments here. Alright, so to start with, are you familiar with the concept of palindromes? Massively Parallel Hedgehog: Yes. DJ Cyclone: Okay, great. So what I'm going to want you to do is write me a function to start with that checks for very strict palindromes. So the function should accept a single input, which is string. It should return true if the string is a palindrome, false otherwise. And this is just a very, very strict character by character comparison for now. So for instance, we've passed in racecar, it returns True. If you passed in say cat, it would return False. But also if we passed in say Racecar, it would return False as well because, you know, each individual character needs to precisely match the character on the other side of the string. Does that all kind of makes sense? Massively Parallel Hedgehog: Yes, so basically we can do a two pointer thing: left is the beginning of the string, right is the end of a string, and then each iteration, we check if the two character are equal. If they're not equal, return False. If equals, left to the right, move right to the left. We keep doing that until the two pointers cross. If by the time they cross, we're still not returning False, that means it's True, right? DJ Cyclone: Sounds good. Massively Parallel Hedgehog: Alright. So I just code these quickly. Okay, I think this works. DJ Cyclone: Okay good, what would be the runtime complexity of this? Massively Parallel Hedgehog: Linear time, constant space. DJ Cyclone: Okay, great. Cool, so for the next part, I'm gonna ask you to do the same thing, right? Basically the same function. But this time we're going to extend this functionality a little bit. So this next version we want to ignore case and we also want to ignore anything that's not an alphabetic character. So this new version should accept palindromic phrases, for instance
A man a plan a canal panamaright? In this case, we would still want this to return true because if you ignore the case, if you strip out all the white space and punctuation, this does, in fact, work out to be a palindrome. Massively Parallel Hedgehog: Okay. Ignore any no alpha character right? DJ Cyclone: Correct. Massively Parallel Hedgehog: So we can just like preprocess the input, right? So first everything to lower. Actually no, we just doing one pass through the string right. So if a character is alpha, we convert it to lower. If it is not the alpha, we ignore it. Oh actually no, because we have to preserve the space, right? DJ Cyclone: So space is also discarded. Massively Parallel Hedgehog: Oh, spaces also? Okay, okay, so space is discarded. Yeah, it actually doesn't matter. So we just go through the string once. Convert every alpha to lower. Every no alpha, we ignore it. We have a processed input, we just put that into the first function. DJ Cyclone: Okay. And let's just, let's go ahead and write this second function. I'll call
isPalendrome2()and do you just want to go ahead and take over from there? Massively Parallel Hedgehog: Yeah, so this will be still linear time, constant space. Okay. DJ Cyclone: Cool, so this should work fine. This is still going to be a linear time, like you said. What is the memory usage of this one going to be? Massively Parallel Hedgehog: Linear memory usage, because we... yeah. DJ Cyclone: Cool. So for a final version of this question, do you think that you could write a solution that does the same thing as this function, but uses constant memory? Massively Parallel Hedgehog: Yeah basically has to be 2 pointer again, but just be smart about how we move this around. So, let me just try to consolidate this logic, alright? So basically what we can do is that have a left and a right. So, while this pointer is not point at the alpha, we just keep moving towards the right direction. For example in the beginning, like the right, is at an exclamation mark, we can move it to the A. So because this is at the alpha, it stops, right? So same thing is like when left is moved out of A. So when we have space, we should keep moving it we keep min, so yeah, so basically this is it, right? Ignore the the no alpha with the while loop and then do the same thing as the first one. DJ Cyclone: Okay, that sounds good. Massively Parallel Hedgehog: Alright. So out of this, either they are crossed or always alpha. Okay. Oh, the requirement was we converted the uppercase to lower, right? Ignore the case, right? DJ Cyclone: Correct. Massively Parallel Hedgehog: Okay. Yeah, we move it. Yeah, it doesn't matter at the line 40 if it's a valid character or not. If it's not valid, the next while loop will move this along to the correct character. Okay, let me just check the logic once again. If it's not alpha, I'll keep increasing or keep decreasing. So here... They must point at both alpha. If there's no equal, return False, otherwise, keep moving it. This will set to correct position. Yeah, that looks good to me. DJ Cyclone: Okay. Yeah, I think this is good. Cool. So the the run time is still gonna be linear, no extra memory, so I think we're good. I'm gonna just go ahead and kinda push this to the bottom of the screen and we'll start back up at the top here on the new problem. So this one, I think we're going to do a linked list problem. So let's go ahead and say, I'm not super familiar with Python classes, but let's say that we have a class called node, right? And we're just going to say that within each instance of this class, we're going to have three members. We're going to have one called data, which is going to be an integer. I would normally do this in like a constructor in Python, right? But I'll let you assume the correct definition, right? Each node is going to have data, which is going to be an integer. It's going to have a next, which is going to be a pointer to the next node. And it's going to have, as well, another member called random. And random is going to point to any other node in the same list. So to give you an idea of what one of these lists might look like, right, let's say we have a list where the next pointers point from one to two to three to a nil at the end, right? The random pointers in this list on each node, they can point to any other node in the same list. The only constraint is that they will not be nil and they will not point outside the list. So the random pointers have no rules, they can have cycles, they can be self-referential, you name it. So for instance in this list, we might say that the random pointers go from maybe from one to three, maybe from two to itself, and maybe from three back to one. So your goal is going to be to write a function which we will call deep_copy. It's going to accept the head node of one of these lists and it's going to return a deep copy. So for instance, if we pass that original list into this function, it's input would be the head mode of the list, we'll call it node one. The output would be a new list which would have nodes, we'll call them one prime, two prime, three prime and a nil at the end. And the random pointers within this new list would go from one prime to three prime. Two prime to itself. And of course three prime back to one prime, right? So we copy both the data and the relationship of the random pointers between the data. Does that all kind of makes sense? Massively Parallel Hedgehog: Yes, one question. You said that the random pointer will have two restriction: one is no pointing to anything outside of the list and another one, I didn't get it. DJ Cyclone: It will not be nil? Massively Parallel Hedgehog: It will not be..? DJ Cyclone: It will not be nil, it will always be defined. Massively Parallel Hedgehog: Oh it will not be None you mean, right? DJ Cyclone: Oh right, sorry. Massively Parallel Hedgehog: Okay, will always be defined. I think we can do one thing. Like we can first iterate through these linked list, ignore the random, right? So while we're doing this, we just create whatever we are currently at and then move on to the next. We put every node we create in a dictionary, which maps the key to the node object, right? And then after the first pass, we can do the second part and then the goal of the second pass is just to connect stuff, right? So from say original and original node, we know like one is point to some random thing, so we can just get the key of this too and then using the dictionary to connect the things together because in a dictionary we have a reference to the new object, right? So two passes, linear time, constant space. Yeah. Okay, would you like me to start coding? DJ Cyclone: Yeah, go ahead. Massively Parallel Hedgehog: Okay. DJ Cyclone: Just to make a small change in this definition here, let's go and call this data. So this isn't necessarily a key, it could be any value. Massively Parallel Hedgehog: Oh, it could be any value? DJ Cyclone: Correct. Massively Parallel Hedgehog: Then there'll be a problem with my algorithm, because in the dictionary, we use the key to identify the objects. If two nodes have the same? So we're not allowed to have a key in this node, only data? DJ Cyclone: Correct, yeah. So the data is valid. There could be duplicates in between nodes. Massively Parallel Hedgehog: Okay. Then my algorithm will not work, I have to think about a new way. So the problem with this is... Data is not unique. What about when we are iterating through the list, we create the node that random pointer is pointing at while we're doing the iteration. Yeah, we can create it. DJ Cyclone: So do keep in mind that multiple elements can also share the same random pointer. Massively Parallel Hedgehog: Yes, that's what I'm thinking. So... Because the data is not unique, so there's no way to differentiate if this is already created. DJ Cyclone: Right, so let's dig in a little bit more on your initial idea. So you initially wanted to create a map from the data to the new node, correct? Massively Parallel Hedgehog: Yeah. DJ Cyclone: But each each individual is a unique object in memory right? So could we perhaps use the object itself as the key? Massively Parallel Hedgehog: Okay. Let's see. Yeah, we don't need to use the data. Let's see, let's see. So if the object is a key, then what is the value? So the basically, the value can be none, can be anything. Okay, in that case we can do this and then on that. Oh I see, I see, I see. We're using the original object as key and then the copy version as value. That will work. Okay, I see. Okay. We know that current connects to current next. Yeah, we have to return the new head. DJ Cyclone: Yeah. Massively Parallel Hedgehog: Okay, let me just check the logic. The storage maps to the copy node. Okay I think this looks good to me. DJ Cyclone: Okay and just one small thing where we need to return a value. Massively Parallel Hedgehog: Oh here okay. DJ Cyclone: Great and there's just maybe one small little bit of cleanup we could do. So you have kind of a separate like variable that you set for the return value. So the return value is the new version of the head, right? Massively Parallel Hedgehog: Yeah. DJ Cyclone: Could you maybe derive that from the data that you already have stored? Massively Parallel Hedgehog: Oh, yes I see. This is not necessary. DJ Cyclone: Okay. Alright, I wouldn't worry about trying to run things, we're not trying to get the syntax perfect. Okay. Well looks like that's just a missing colon. Okay, cool. So what's the runtime complexity of this one? Massively Parallel Hedgehog: Linear time, linear space. DJ Cyclone: Okay, great. Let's see here, we've got a little bit of time left. Let's go on to one more problem. So for this one, we're going to do another linked list problem. This time we're going to have a node class that is a little bit more simple. So this one is just going to have self.data and this one's going to have a self.next. So this is just going to be a simple singly linked list. Each node in the list has an integer for data. It has reference to the next node in the list. And it has none when we get to the end. So your goal is going to be to write a function which accepts the head node of one of these lists, and prints it out to the screen in reverse ordered. So, for example, if we had a list that went one to two to three to none, you would want your program to print out to the screen three and then two and then one right? Each on its own line. Any questions about that? Massively Parallel Hedgehog: Yeah, no. So what we can do is we have a reverse method, we have a print method. The print method is just going to print the link from the beginning until the end. Reverse method is going to reverse the linked list. So we will first reverse the current linked list and then we'll print the list. And then we'll reverse it back. So the reverse method is a linear time. So this, will be linear time and constant space. DJ Cyclone: Okay, sounds great. Massively Parallel Hedgehog: So still a test run in line 20. Initially, we'll have this. So first we set the one point to None, which is previous, and then we move these along, c is here, p is here, and then we set this to this, and then we move C here and P here. Then it will move this, and then c is none, p is set three. We return the p, so we reverse it. DJ Cyclone: So conceptually this is correct, but let's do a test run again, but let's just take it line by line and look at very specifically what each line is doing. So we'll start with previous and current set to none and one. Could you just take me through this function a line at a time and let's look at those pointers at each line. Massively Parallel Hedgehog: Okay, so right now we should have a next, right? Next is pointing at two, right? So current next is previous, so one... no, current.next is like... current.next is pointed none right, because yeah... So we said... Okay, so after this we have a next pointed at two and then this one we just set one to point and None right? And here we previous move to current, which is p point at one, right? Yeah, and then current equals... Oh I see. Cannot be next. Current has to equal to next. DJ Cyclone: There we go. Alright, so this this should work. What is the runtime complexity of this going to be? Massively Parallel Hedgehog: Runtime is linear. In here?, I'm returning this string right? So if I'm not returning... It kind of has to be constant because while you're iterating through it.... Oh no, you don't have to do it, you can just print it out. Yeah. I don't know how to print without a new line, so if we can print without a new line, then this will be working. DJ Cyclone: Yup, new line is fine. Okay. Alright, so I think we are good. This is the optimal solution and we're kind of coming up on our time over here, so I think I'll go ahead and stop there. Massively Parallel Hedgehog: Okay. DJ Cyclone: Great, so I'm gonna go ahead and, you know, fill out feedback for you. Is there anything in particular you had questions about that I could answer now or you just want me to kind of fill out the feedback? Massively Parallel Hedgehog: Yeah, like if it's a real interview, from rating of 1-5, what kind of score would you give me and how can I improve? DJ Cyclone: Sure, so on a 1-5 scale, quite like four and a half. If this were like a real phone screen, the rating that I would give is a strong recommendation that you go to an onsite. Basically you did very well on the problems. The only real hiccup that we had is when you came up with that idea for the deep copy. You just needed to realize that you could use an object as a key in the dictionary. So that's something to, you know, to watch out for when you use a higher level language. Just make sure that if you get hit with, you know, for instance like a problem that involves moving pointers around a lot, make sure that you know your languages particular semantics for like finding the id of an object or, you know, indexing by a class, that kind of thing. Aside from that, you know, that was the only hint I really had to give you. You had a couple of very small errors, but overall very well put together, so that would definitely be a recommendation for on-site for me. Massively Parallel Hedgehog: Okay, okay cool. Here's one last question. This might be too much to ask. So currently, I'm a third year undergraduate student. I'm looking for an internship at a top tier company. If you happen to work for one of them, I'm just wondering if you would be willing to give an internal referral for internship application. Like I know this platform is making money by getting people hired, but my case is really internship and the platform does not deal with such hiring, so what I'm asking is not like... that's not like harming the platform's interest if you're concerned about that. DJ Cyclone: So probably shouldn't because... I'll tell you what.. let me actually ask the... so this is actually the first one of these that I've done, so I know for a fact that it's going to get reviewed. So let me just make sure that I ask them that that's okay and it won't get me kicked off the platform before I give you an answer. Massively Parallel Hedgehog: Okay, you can like tell them that... basically I have them about like getting hired through the platform as internship applicants. They said they don't do that. So I think this is will not be a conflict of interest, but of course like you can check with them. But in the event that in the event that they say it's okay, like please,like is there anyway like to get back to me? Maybe we can do this introduction thing. DJ Cyclone: I believe that's an option, so I'm gonna find out. Massively Parallel Hedgehog: Okay, cool. DJ Cyclone: Alright, great. Well thanks very much for your time and have a great rest of your day. Massively Parallel Hedgehog: Okay, thank you very much, bye. DJ Cyclone: Bye.