Ruby Interview with a Shopify engineer

Watch someone solve the validate string against dictionary problem in an interview with a Shopify engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Validate string against dictionary

Interview question

1) Given a string and a list of words, determine if the string is valid based on the list of words 2) Determine if the given string contains valid words while ignoring extraneous characters

Interview Feedback

Feedback about Dystopian Corgi (the interviewee)

Advance this person to the next round?

How were their technical skills?

2/4

How was their problem solving ability?

2/4

What about their communication ability?

4/4

- Talked about approach, runtime analysis, optimizations before jumping into code - Talked about tradeoffs between approaches and different data structures Cons - Review dynamic programming (will help you ace these types of questions)

Feedback about Captain Hamburger (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

Honestly, I think you were one of the best interviewers I've had. Keep it up!

Interview Transcript

Dystopian Corgi: Hello.

Captain Hamburger: Hello.

Dystopian Corgi: Hey, what's up?

Captain Hamburger: Hey now much, how about you?

Dystopian Corgi: Not much.

Captain Hamburger: Yeah. Great. So is this your first time using the platform or have you already tried a few times?

Dystopian Corgi: I've used it a couple of times. So yeah, I'm a little bit familiar with it.

Captain Hamburger: Awesome. So great, let's just jump right into it. So I guess I'll tell you a little bit myself and then maybe you can share a little bit about yourself. I'm currently working as a software engineer. I've been out of school for about two years, working at one of the big tech companies. How about yourself?

Dystopian Corgi: Yeah, so I went to a coding boot camp and I've been working about two and a half years now as a Rails developer. I don't really have much in the way of like a CS background so that's why I'm kind of going through this platform to kind of practice my algorithm knowledge and like interview questions.

Captain Hamburger: Awesome. Yeah, that's a great idea. Even you know, I studied CS in college, but I find interviews pretty different from like just taking courses.

Dystopian Corgi: Yeah, it seems to be way different. It's like a pressure situation and all that, but it's definitely a great like platform for practicing.

Captain Hamburger: Great, so do you have a language of preference?

Dystopian Corgi: I guess I'll go with Ruby, if that's okay?

Captain Hamburger: Great, that's a great language, yeah.

Dystopian Corgi: All right.

Captain Hamburger: Okay. Yep. I'm familiar with Ruby and I will... so my question for you is, this right here. So given a string and a dictionary of words, determine if the string is valid based on all the dictionary words and I have a couple of test cases for you to start off with. So here is an example of a test case. Sorry, I usually code in Python so I will allow you to recode them or if you want me to, I can recode them in Ruby. But the idea behind it is pretty straight forward. So how do you set... I forget... multiline string comment for Ruby?

Dystopian Corgi: I think you use a begin and end but... I think, yeah, there you go. It should work. Okay. Alright so, I guess I'll try to kind of reiterate kind of how I'm interpreting this question. So it seems like it's pretty straightforward, at least the wording. So we're given a string and a dictionary of words. We want to determined if the string is valid based on all different words. So I basically just read your prompt, but let's look at your first example here, practice makes perfect. Okay, so our dictionary change [practice, perfect, makes], that's true, so looks like every word of the string is contained in the dictionary, which is why it's valid. And for your second example, looks like it's missing a word, so that's why it's invalid, okay interesting. Okay. I guess I will just start like brainstorming to like kind of tell you what I'm thinking. Yeah maybe it'll go somewhere, hopefully it goes somewhere. Okay, so it looks like the most immediate thing that comes to mind... maybe it's not like the ideal way of doing it is if we could somehow grab the words from the string and then you know, you can iterate through each word and just check if it's in the dictionary. But if you did that, it would be me... let me write it out. So you're like, we're going to like split the the string into the words. And for each word, check if it's in the dictionary. It's like, I think time-wise this wouldn't be as efficient as maybe another way, but time-wise this would be... let's see hmm. So you have to for each word, say we have like w words, and I guess we could do like a search through the string perhaps. Or sorry, search through the dictionary. Hmm so I think in that case, if we were to sort it and search it, it's like O(n log n) if there's like n words in the dictionary. I think that would be the time correctly in that case.

Captain Hamburger: Can you tell me why you think that's the time complexity again?

Dystopian Corgi: I guess for search, the fastest way to search the sort, it would be O(n log n) time and then we could do like a binary search through the sorted dictionary, which would be O(log n) time, I believe. This is given like n words. I guess I have to take into account like, how many characters are in each word.

Captain Hamburger: Remember, this dictionary is just a list of strings. So, we're not sorting here. Yeah.

Dystopian Corgi: Okay gotcha. So I guess like okay... I was thinking we could like do like an operation on top of that, but if we don't want to sort it then we can just do like a linear scan through that, yeah linear scan through that. So that would be O(nw) time I believe.

Captain Hamburger: That's correct yep.

Dystopian Corgi: Okay, and then I guess for space complexity... So we had to split the words or have to put them into an array of words. It'll be O(w) space I believe. Okay, so I think that's like a slow approach. Maybe if there is a faster way of doing this. I don't imagine being much faster but maybe think about if there is a faster way of doing this. We have to iterate through the words no matter what. Hmm, let me think. Maybe if we... I guess like another way would be once we've stored the words or once we split the words we can store them into like a hash and then we iterate through the dictionary. Oh, no, that doesn't make any sense. That wouldn't work. Or what if we? Actually if we stored the dictionary in the hash for a constant lookup or like approximately constant lookup? And iterate through the input words, whatever. And like return false if there's a word that's not in the dictionary. And in this case, I think this would be a story dictionary words in a hash would be... So we have like n words. This would be O(n) time worst case and then here, this would be O(w) time. So these aren't nested operations. So I'm running in like sequence, so I think this would be, let me see... Like I guess O(n) time, depending on if n or w is greater. I'm not sure if this is the right analysis for this.

Captain Hamburger: No, that sounds correct, yeah.

Dystopian Corgi: Okay and then I guess like space then, that would be... O(w) space because you still got to split the words and store them in a hash. Okay. Trying to think if there's like a...

Captain Hamburger: You're also storing the dictionary in a hash right? So that would increase your space complexity.

Dystopian Corgi: Oh yes, absolutely yes. I guess O(n) space if n is greater than w.

Captain Hamburger: Both of those answers are correct. I was just saying like if you're being because you're being very thorough, which is really cool. So I was just like okay, if you can do that. But anyway, that's besides the point. I think you have two good strategies. It's up to you which one you want to code up.

Dystopian Corgi: Okay sure, I guess it seems like the second one might be faster, so try this one.

Captain Hamburger: Cool.

Dystopian Corgi: Alright, let's see here. This guy here so... Oh okay let's call this... We are just basically following like the steps here. Yeah. Right, so store dictionary in the hash. There's some kind of dictionary hash I guess. Okay so storing a word in the hash and so we have an input string. We want to split it on the words or on the white space. So that gives you an array of words. Okay so for each.... So now we check each word array, make sure it's in the dictionary. Basically just returned false if it's not in the dictionary hash. Then finally return true for this. And like usually what I would do is like probably try write like a test case, so maybe like use a put statement to start if it's true and you gave me some examples so I'll try these. Okay. Using puts instead.

Captain Hamburger: Yeah, this looks good.

Dystopian Corgi: Alright. I'm gonna go ahead and run this. So first one, just forgot to lowercase everything. So I guess like, can we assume that the dictionary is all lowercase words?

Captain Hamburger: Yes you can.

Dystopian Corgi: Okay, so if we assumed that, then we just had to check for lowercase words. I'm going to go ahead and downcase this guy. Okay, let's do a little debugging I suppose.

Captain Hamburger: Oh yeah, I'm just gonna save you some time, it's the punctuation.

Dystopian Corgi: Oh shoot okay, oh thanks. That would have taken me a lot to get that I think. Okay, so punctuation, interesting. So that means if we're splitting across the white space, that's not gonna catch the punctuation. Interesting. Can we assume that it's... let's see. Can we assume that there are no apostrophes or anything funky like that?

Captain Hamburger: Let's say that the only punctuation is a period. Sorry, go ahead.

Dystopian Corgi: Okay sure. So assuming that and I'm assuming like every language or like, in English language, periods end the sentence, then I guess we can. I'm confused why the dictionary stored the perfect with the period.

Captain Hamburger: So your sentence will contain a period but your dictionary will just contain a word, right?

Dystopian Corgi: Um, oh yeah, you're right, yes, because we didn't didn't store the period with the word. Okay, so I guess it's like the simplest way would be to kind of take the string up to the period or up to before the period. Okay, so. Let me see here. Maybe there's some edge cases that this doesn't really quite catch.

Captain Hamburger: No, I think it looks good, it's clean, looks good. Yeah, so you pretty much solved this part of the problem. Is there anything... there's a second part to the problem, just so you know, but we'll talk a little bit about the current iteration of this problem. So can you can walk me through what you might think would happen if say you had a really massive dictionary, I don't know, like the English language probably contains millions of words right, so just walking me through what you think might happen if you're sentence is really small and then your dictionary is really big in your program right now.

Dystopian Corgi: Sure, so like given the current implementation... So I guess my immediate thought is it a problem that we're storing every word into like a hash, like are we gonna run out of space? I suppose that could be a problem. I guess like if there are a lot of words in the dictionary, it's like more than the amount of memory, we could run out of space for the dictionary. So I'm actually not a hundred percent sure how like a hash lookup works. I know it's like on average time, it's like constant lookup and if I'm not mistaken, maybe if it's like there's a lot of elements in the hash, then I think it could perform worse. I'm not 100% sure but I think I might have read somewhere and I guess if that were the case, then this would not be ideal because you don't want to look through because you have a lot of words in your dictionary hash so like that wouldn't be so ideal. What else?

Captain Hamburger: It's cool if that's it. That sounds pretty good to me. Yeah, so actually it wouldn't matter, this was kind of a trick question because there isn't much scaling involved in this problem, but you're right, so hash tables have an O(1) access time, or sorry search time, not access time, so if you search for an element, it's gonna be on average, depending on your hash method, it's gonna be O(1). But in this case, you could have... There are only a million words in the English language, there's a finite amount right, so you're never gonna... As long as you know the dictionary, the world's largest dictionary, you can sort of provision the amount of memory, so it'll never keep growing. Cool.

Dystopian Corgi: Gotcha, so it wouldn't scale.

Captain Hamburger: It'll be fine actually, your program would run great. All you need to know is the size of your dictionary, you'd just be constrained by the amount of words in your dictionary right?

Dystopian Corgi: Gotcha, yeah yeah.

Captain Hamburger: Cool. That was kind of a trick question, I just wanted to get the conversation going in that direction. So the next part of my question is if you go back to line 24. Say we have a sentence like this now. The same sentence with punctuation and spaces removed and all lowercase and you have your dictionary. And I want you to find out if the words in the sentence... if the string returns true because there are words in that string that belong in your dictionary. So as a counter example, this would be... Okay. Does that make sense?

Dystopian Corgi: Yeah, also this would also be true then in this case.

Captain Hamburger: Oh sorry yeah, I should change this. The idea is there's the words practice makes perfect and there's an extra X, which is not in the dictionary.

Dystopian Corgi: Okay gotcha, so all the words... to I guess verbalize out loud like how to describe what's going on, so looks like all the words that are in the dictionary... I guess taken together... I guess you said the length of all those words is equal to the original string length. That makes sense, to add on to your example here...

Captain Hamburger: But if you were to take that same example and remove the X, then that would be correct.

Dystopian Corgi: So it's like any combination of the words in the dictionary. Okay gotcha. Okay, so If we were like walking along the string, say we walk along the string character by character and then we kind of hit a substring that's in the dictionary and then we could say okay up to that point it's good to go. And then we kind of keep on walking along the string and hit another word. Then we hit like x... Interesting. Actually, may I ask, like in this case this would also return false, this example?

Captain Hamburger: Either your program would capture XP, in which case you know, you have like RACTICE, which is not a word dictionary or you have practice and you have an extra x, which is not in your dictionary either. But if you were to put it like another p here, then it would pass.

Dystopian Corgi: So it's kind of like... my mind is... it's kind of like, you know, where should you make a word, you know like to check if it's like valid. In the example we have here is like we were not like how can we track that. How do we do that? Interesting. Maybe we could just look at like at... Trying to think of it like, maybe like a really like a slow way or like I guess naive way of doing it.

Captain Hamburger: I think it might be simpler to start with line 26, where say you only look for the true case.

Dystopian Corgi: Sure, okay so we're relying on this example. So I guess we would have to check all the... I guess like in this case like we already know that's already three words, so we could check like... if we knew there were three words in the string then we could do like a triple nested loop and then kind of just look at all the other substrings and just basically, you know, return true if any of those arrangements fit our criteria. Like I said, that'll be a slow way of doing it. I guess like if you didn't know the number of valid words in this string, you could check from... Oh you could do from... Shoot that might not be... That's not a good approach because we don't know how many valid words are in the string. Yeah, I guess like the part that I'm kind of stuck on is what range of the string to look at to determine if it's like a word if that makes any sense. I guess like going back to the example on line 42, is like do I look at XP or do I start another word at p and look for the rest of it? So that's kind of like what I'm stuck on.

Captain Hamburger: I think this would be a good way to start it if you want to roll with it. When you're trying to solve this problem like as a human being, how do you try to solve this problem?

Dystopian Corgi: As a as a human being? I suppose you look through the string from the beginning and basically as soon as you see a word that you, see you look at like practice and then look in the dictionary and then you look at makes, it it in the dictionary, and then you look at perfect. Basically just iterate through the word and kind of look at each substring and similarly for line 38, makes is in the dictionary, perfect and then yeah XP and then practice

Captain Hamburger: You're... as you look for words, you're going character by character and you're like eliminating, so for example on line 26, you're going PRACTICE you find your word and then you don't look past again.

Dystopian Corgi: So looks like as soon as you see a word then you don't even... Like anything before that you don't you even worry about that anymore. So I guess in the case that like what if we see like you know the, if example... So I guess like yeah, so for the example we had like...

Captain Hamburger: So are you familiar with dynamic programming? Have you heard of that term?

Dystopian Corgi: Kind of. From what I like know of it, it's essentially like store data that you've already seen and kind of caching it and pulling it out later if you see it again.

Captain Hamburger: Well, the reason why I mentioned that is one of the common ways of solving these kind of problems where you know, you were mentioning you are looking at a string and you're looking at it, you're looking at the rest of. it and then you're segmenting it and you're looking at the rest of it... A table comes in real handy when you do that right? So if you're looking at each character and you're saying like from the beginning of this string till to this point, I don't have a word just, you know, keep track of so... for example if I highlighted practice that's a word right, so if you were to store it in a table each character, you probably store it as like here's a sequence of characters and it's only valid when you know, this particular string of characters is in the dictionary. So I don't know if that helps in any way but it might be a potential direction to go in.

Dystopian Corgi: I'm a little confused by what you mean by storing it and like iterating through the string.

Captain Hamburger: By table we can... so since this is just a string, imagine it as a single table. So in the beginning you have like... So you have p as your first character, does that make a word? No. You have PR, does that make a word? No. And then like A, no. And then c, no, and then t, i and then c and then when you hit e, you encounter a word, right? So in that case as you can see, every character up until this point is false and then as you keep going, you can keep going. So once you hit a value of true, you can say that for everything until the previous false, that's a word. That's a valid word. And like we're mentioning, you can segment it, right? So now that you found a word, all you're considering now is this. So your sentence then shrinks down into this. And you just do the same strategy so you take a look at m and then a then you look at k then e and then you take a look at s and each time you're checking whether this substring is inside of your dictionary and each time you either get a true or false and then you you know, you'll get like a similar table until you hit true, does that does that make sense?

Dystopian Corgi: I guess the approach I understand. I'm just trying to figure out how we could use that to I guess like solve the issue, so I'm trying to put that together in my head. So we're iterating through each of these characters and basically keeping track of that substring is in the dictionary and then once we have one then we can put true. Yeah, okay, maybe I'll try to kind of finickie here and then we keep practice and so for makes it would be to here. Then I could alter this a little bit with an x perfect.

Captain Hamburger: If you want, you can do that. It may not be important to solve for the null case, but if you feel you want to go through those that's a pretty good idea too.

Dystopian Corgi: Yeah, I guess I'm just trying to piece things together here.

Captain Hamburger: Why don't we do that? So imagine your next word is x, right? So say x is your word even. What would happen? How would that table look like? Or you know, tell me what the next part is. So you've successfully segmented up to this part, toString now looks like this, right?

Dystopian Corgi: Yes, so. So we see xp, so we see x. We false, and then we see the p, true, if I'm understanding it correctly. The rest of it just all falses here. Yeah and that points to that string.

Captain Hamburger: So in the end here your program would return false, right?

Dystopian Corgi: Yeah. I think I'm over complicating this my mind. Yes, sorry about I don't know if I'm like overcomplicating this.

Captain Hamburger: Yeah, don't worry about it. Do you want some more time to think about it or do you want to talk about the solution, maybe or...? It's up to you.

Dystopian Corgi: I guess like one more minute if that's okay. Appreciate it. Sorry if I could ask, like I guess like in this example here... Because you see the xperfect... I guess for yeah the last up to here it's a word... but I guess if we were to kind of iterate through and we see XP and then that's like that's a word in dictionary but then we check the rest of it, which is not something like how do we like account for that case?

Captain Hamburger: Um, yeah, that's a good question.

Dystopian Corgi: If that's even a possibility of that happening.

Captain Hamburger: What do you think would happen here? Not that it makes any difference. I know we're going a bit into a rabbit hole, but I'm just kind of curious.

Dystopian Corgi: Oh yeah. I'm trying to figure out. Yeah, I'm not sure. I don't want to take up too much your time, but I guess like yeah, I would I would ask for another hint at this stage.

Captain Hamburger: Okay yeah, um, do you want to... it's up to you but do you want to walk through the solution or do you want to try this on your own maybe? I don't know, it's up to you. I'd be happy to share what I was sort of looking for.

Dystopian Corgi: Sure, yeah, that sounds good.

Captain Hamburger: Okay, so yeah, so the the main concept behind this particular problem is, you know, the use of... I think like the easiest way to solve this problem is by using some form of dynamic programming and it's exactly the way you see it in the solution that we have so in this case you would just construct a really long table of all of these things together. Why don't we include xperfect in this example, so let's get interesting. Up to here is practice, to here is makes, this is XP and then... So the idea behind it is you're doing backtracking almost, so you're taking a look at all the characters from like as you're iterating through the array. You're gonna be looking at all the characters from say, as you're going through i, you're gonna be looking at from j to i plus 1 and i is going to be counting down from from i. So if i is equal to...This is a bit too long but like... how many characters does this have?

Dystopian Corgi: Sorry I made it so I complicated.

Captain Hamburger: No it's definitely not a complex solution, so I'm gonna I'm gonna switch into Python a bit just because I'm more familiar with the syntax. Okay, so let's go to the solution. So we're gonna call it a valid sentence. And we're given a string. And we're given a dictionary, right? So just like we were doing it before, I'm just gonna go through the very... Right here.. .And we're just gonna pass it and this is our dictionary. Alright and we want to... So the first thing that we want to do is initialize some kind of a table, right? And the first thing we want to do is if it's an empty string, for example, it'll be vacuously true because empty strings are true by nature. Then what we want to do is we want to go through the string, so for i and range of length of string. We want to keep iterating and as we keep iterating, the default character, so as soon as you add a new character, as soon as you examine a new character, you're gonna append a false value to your table. Because right now, your program has no idea whether it's true or false. Then what you're gonna do is iterate from i, so you're taking a look at all characters from i and then backwards. So say you've gone 10 characters ahead, you want to look 10 characters back, right? So you're gonna keep incrementing in the range of that. And basically what you're trying to check is if the table at that character, remember you have an extra value in your table so you're going to need to increment... so if the table at that value... I guess why don't we make it a little bit simpler for this particular example - I am good. So what you're doing is you're checking if that current value is correct and you're also checking if the string is from where you're at to i + 1 is in your dictionary. So this part... let's unpacked it a little bit. So over here, you're gonna take a look at your first character, right? And then i is equal to zero and then your table value is also equal to zero and your string goes from zero to one. Right? That's just zero. And it checks if the table at j, so table at j is true, right? Your table looks like this, true and then you just added a false, so it looks like this because you're considering the current character. And then it says, okay table at value zero is true and the string that I'm constructing is the string from zero to one, which is just string at zero, right? Which is just the character at i. And we're checking if that character is in the dictionary. And if it is, what we're gonna do is we're going to set the table at j equal to the true and we're gonna break out of this loop.

Dystopian Corgi: Kind of, yeah kind of. Not like explicitly clear.

Captain Hamburger: And just to wrap this up to make our program run, we're looking at, like you mentioned, if we can go through the whole thing and just get correct words, but if that last string is wrong, the whole thing is wrong. So we're just gonna look for the very last table character. And it's correct. So if you want, we can unpack it a bit. So you're probably wondering about j and the i plus 1.

Dystopian Corgi: Yeah, that's my main confusion, like iterating backwards.

Captain Hamburger: Yeah, so in this case you understand that we are going to continuously go backwards, right? j will go from the value i, all the way back to the end of the string for each iteration. And just quickly, just knowing these that there are two loops, what do you think the run time of this program would be?

Dystopian Corgi: Sorry, another thing is, that when you say... oh, you're iterating backwards?

Captain Hamburger: Yeah, this is just Python code to go backwards.

Dystopian Corgi: Oh, okay gotcha, oh okay. I thought you were saying... my impression was it was going forwards, so I was confused but okay.

Captain Hamburger: Yeah, so why don't we walk through this I am good example? So I, obviously we solved for that. And then say, for example, you're at M. So i is equal to 0 1 2, right? At the character M, then j is equal to 2, right? And it goes all the way back to 0. And every single time, you're going to be checking the value at j. So in the very first initial value, since you're appending false every time, so I AM is currently false. So 0 1 2... So we add true then we have false for A and then as we can do...

Dystopian Corgi: We're at j is equal to two at this point?

Captain Hamburger: Yeah. I'm just backpacking a bit... the construction of the table is a little bit off. So in the first case, it's gonna be i, so it's gonna be true and then since table at j is equal to zero and then string from zero is one, so we just do table at i plus one, so now we do that's true, you see because of this property. So we do the next value of i becomes true. So imagine the first character as just a... if you're familiar with like bits, like imagine negative one, right? The negative doesn't mean anything, it could be say if you just represent it as negative or positive and then you actually start your value at one, right? Imagine you're throwing that all, so your first bit is basically just like a parity bit, like you would just check if it's one, it's false, whatever just ignore the first character, it's for like... So actually, the character i is actually i plus one is the first character that tells you whether the first character in your string is a word.

Dystopian Corgi: Yeah still iffy, I apologize. I think I have to like walk through.

Captain Hamburger: Let's look at it from this, so imagine this is just outside now. So that makes sense, right? So the first letter i is in the dictionary. Then we look at A, so now i is equal to one and j goes from i to zero, so the table at j, which is one, is... so in this case everything's incremented by one because of that vacuous condition, so just imagine this j minus one, if that makes it easier, but uh, yeah. In this case, let's do j minus one. So it looks behind it and it says okay, that's true, right?

Dystopian Corgi: At that point, it's table at zero, which points to the i.

Captain Hamburger: Ok, we're looking at the A right now, right? So now it's false, right? So it's a table at j is equal to one, so the value at one is false, and we checked if zero. So we checked the value for one and then we also checked from one till the end, so the first thing that we do is one to the end, so the last two characters are ia, right? So even if we were to go back to our example, like j minus one, this still works, so if we're considering the table... so j minus one is zero, it's true and then the string is from sorry j to the end of the string.

Dystopian Corgi: Yeah.I think I'm starting to see... Yeah, I think I would have to like walkthrough like each line, like put some print statements and walk through each step.

Captain Hamburger: Yeah, this is just some one of the ways to solve it. You can actually use multiple loops to solve it, although that is a.. That's not like you know, that's like not accepted too much, usually.

Dystopian Corgi: I was going to say that the time complexity, it looks like if it is nested, it will be O(n^2) if I'm not mistaken.

Captain Hamburger: That's right, yeah.

Dystopian Corgi: So this is a lot cleaner than like multiple nested loops.

Captain Hamburger: Yeah and what would be the the space complexity for this?

Dystopian Corgi: This case, I think we're creating... So for the table, that's where all our extra added space is coming from, so I believe... if s is the length of the string the O(s) space complexity?

Captain Hamburger: Yeah, that's right. I just want to go through the XP because I'm actually curious myself. Did you have the X perfect? Yeah there we go. So I think ideally your program should return true because it is a valid string. It exists in the dictionary, so yeah, there you go.

Dystopian Corgi: Cool, awesome.

Captain Hamburger: Sounds good, alright.

Dystopian Corgi: I think yeah, I'll have to... thank you for trying to explain that, I think I need to like go through it like kind of myself and kind of try to to figure what's happening.

Captain Hamburger: Cool yeah, this is a question I was asked at Facebook, so just something...

Dystopian Corgi: Is that that way you're working right now?

Captain Hamburger: No no, not working at Facebook, but it was an interview problem there. I did interview there though, so you'll find a lot of companies will do two part questions, so the first part is a warm up that sort of gets you into the flow of the question and the second part is actually the meat of the the problem.

Dystopian Corgi: Yeah, the first part is easy, you like warm up but yeah, I think like I'm kind of curious like when you're preparing, like what was your kind of like method for like preparing for these kinds of questions?

Captain Hamburger: Yeah, so what I did was I think... so I have my notes from college for the basic data structures and stuff, so I probably recommend the first thing if you aren't familiar with those, just make sure you familiarize yourself with the different data structures and algorithms. So you don't reach need to remember too many, but like it's good to remember like binary research trees, linked lists, you can look at heaps or hash tables, but definitely cover the basic implementation of data structures. I'd go through the implementation of algorithms and then unfortunately just grind through leetcode is what I kind of recommend.

Dystopian Corgi: How many questions do you... I don't want to be too specific here like, but curious like how many would you like recommend in terms of a range of like anywhere from like a hundred to like a couple hundred? I mean, I guess it depends on each person but yeah in your case?

Captain Hamburger: In my case, I did about like 70 or 80 and then I was like interviewing at the time as well, so maybe that counts as more or something because I was doing interviews at the same time as doing the questions, but I think like if you do a hundred questions, you should be okay, if you're doing it properly, like actually spending half an hour to 45 minutes trying to solve the question and then you know, you're not just looking at the solution sort of thing, because that doesn't really help.

Dystopian Corgi: I'm like 15 through, I went through a cracking the coding interview, but it wasn't like an ideal like, you know, actually yeah write out and implement it, so that's good that leetcode kind of course you to write everything out. Yeah okay cool, I think we went way over time.

Captain Hamburger: No, don't worry about it. This cool question is actually from leetcode, so there you go, I highly recommend leetcode.

Dystopian Corgi: No doubt, that's an easy interface to to run your code.

Captain Hamburger: Sweet, so yeah, if you don't have any more questions, um, I think we'll call it.

Dystopian Corgi: Alright cool yeah, thanks man. I think we went over time, but I appreciate your help, was very helpful, and your patience too.

Captain Hamburger: Thanks a lot man, I'm always trying to improve as an interview as well, so thanks. If you have any feedback, let me know. Thanks, good luck.

Dystopian Corgi: Yeah sure, alright take care, bye.

Captain Hamburger: Bye.