We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Please read our definitive guide on Google's hiring process and questions
JavaScript Interview with a Google engineer
Watch someone solve the simplified blackjack problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.
Interview Summary
Problem type
Simplified Blackjack
Interview question
Consider a simplified game of blackjack, with an infinite deck of cards labeled 1-10. That means there is always a 10% chance to draw any card value regardless of what's been drawn before. Duplicates allowed. The dealer always plays deterministically, according to the following rules: If the dealer's total is less than 17, the dealer draws another card. If the dealer's total is at least 17, but not more than 21, the dealer stands. If the dealer's total is over 21 the dealer "busts" and therefore loses. Determine the number of ways the dealer can bust.
Interview Feedback
Feedback about Blue Panda (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
4/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4
Hey Blue Panda (great name, btw) aka Shazim, hoping the interview was insightful for you. It was nice to meet with you! You did well in this interview and would have cleared the hiring bar for this interview assuming this was for an onsite interview. You started around the 5 minute mark, and finished the question around the 23 minute mark, which means it barely took you 18 minutes to solve the problem. You optimized the algorithm by realizing we could memoize answers. That took you another 10 minutes or so as well. I’m happy to say that your time management skills in this section were optimal. Good time/space complexity analysis. I think you could have come to some of the conclusions a little faster, but you were very clear in your thought process and ultimately correct. Saying time/space is constant is absolutely right even though it makes me chuckle. It’s true, but not particularly useful in our analysis phase of the problem. Still, your complexity analysis was spot on, and the only complaint I have is that you needed to be prompted to give it. Keep in mind that time/space complexity is basically the point of the interviews since the point revolves around optimal code. While your analysis was good, you shouldn’t have to be prompted to talk about something so fundamental – be sure to bring it up next time on your own! This is arguably one of the most important pieces of feedback to remember from this interview. Besides interview pacing, it’s important to talk about the general structure of the interview. The general flow and process of the interview was correct and I think this is partially what helped with your pacing. Since you coded the interview in JavaScript, it’s worthwhile to spend a second talking about your knowledge of the language. Thankfully your grasp on this language appears to be strong and more than adequate for interviews. You showed strong general software engineering abilities and great overall code hygiene. Some minor comments and/or nits: Loved the template you pasted in! Great clarifying questions. You can have edge cases even without inputs. Edge cases might be a bad word. Assumptions is a better one. Hard to hear you a bit. Is it your mic? You talk fast. Are you mumbling? Hard to tell Don’t have to do it randomly. Great clarification. ES5 function not ES6, why? ES6 came out in 2015 For that last ending twist “What is the percent chance that a dealer busts?” There is a mathematical way to calculate the percentage, but note that I asked you to find it quickly. In this case you already had made a function that calculates the number of busts. It would have been trivial to write a similar function that counts the total number of stands and then just give the percentage of the two. If you can’t calculate it mathematically remember that you’re a programmer and can generate answers programmatically! 😄 Next Steps: ============== Follow this process : Read question Ask clarifying questions and test your assumptions about the problem inputs/expected outputs Discuss logic & mention complexities Get buy-in from your interviewer to confirm they like your approach (or re-think optimal solution) Write code Do a quick dry run Show confidence in your code and don’t agonize once you’re pretty sure you’re done Just as a headsup, the platform asks if you’d like to connect with your interviewer, but for every interview I say “No.” This isn’t a reflection on you specifically. I’ve just had too many candidates stalk me on linkedin and reach out asking for private tutoring and/or referrals later after knowing my name. If you get a rejection, don’t stress about it too much. Remember that even if your interview was flawless, the acceptance rate is only 0.2% of candidates and you’re more likely to get into Harvard than pass. That isn’t necessarily on you either, some many other factors go into an interview that are outside of your control. If you don’t get into Google this time, try again! This isn’t your “one chance” and the average Googler tries 3x before getting in! That’s the gist. You clearly are a good engineer that has written quality code before so you’re coming into these Google interviews with great momentum. DP algorithms are tricky! Hopefully this feedback helps you. All the very best for your prep! Good luck on your onsite interview at Google!
Feedback about The Mighty Anomaly (the interviewer)
Would you want to work with this person?
YesHow 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
I apologize for the mic/mumbling, thank you for pointing that out to me, I'll look into a solution for that. Pros: -- Interviewer's communication was super clear. -- His points about my interview were very understandable and sensible. -- Gave me extremely useful feedback. -- Interview was more of a smooth conversation/collaboration. -- Really appreciate the Google-specific information from an Engineer's perspective. Really helps clear things up when compared to given info from other sources. Constructives: -- I would have appreciated if I was told about the mic/mumbling problem at first instance so I could have spoken more loudly/clearly for the rest of the interview. -- Not sure if it's necessary to point out language usage preference for a DS/Algo interview? As long as it's valid, readable, and performant right? Just something to think about. Definitely unexpected, but I enjoy interesting conversations about JavaScript.
Interview Transcript
The Mighty Anomaly: Hi, nice to meet you. My name is ####, and is there I know this is an anonymous platform, but is there a first name that you don't mind sharing with me?
Blue Panda: Yeah, sure. My first name is ######.
The Mighty Anomaly: Perfect. Now, can you spell that out for me just so I don't butcher it?
Blue Panda: Sure, yeah, I can type it out. It's #-#-#-#-#-# #### ####.
The Mighty Anomaly: #### ###. Fantastic. Okay, great. Well, then, nice to meet you, #### ####. Let me ask right off the bat whether or not you've ever done a interviewing.io interview previously.
Blue Panda: I have, yeah. This would be, I think, my second or third one.
The Mighty Anomaly: Fantastic. Well, then, welcome back. Nice to have you with us. In this case, it sounds like because you're doing a Google interview with me, you might have an upcoming Google interview. Is that correct?
Blue Panda: Yes. That is sweet.
The Mighty Anomaly: Well, how about you give me a little bit of context around here on if you've ever interviewed at Google before or what level you might be interviewing for at Google now, any of that kind of stuff that might be relevant for the interviews.
Blue Panda: Sure. Yeah. So I'm basically on my Google on site now. I passed my tech string, and so I think the level that I'm interviewing for is L Four.
The Mighty Anomaly: L Four.
Blue Panda: Fantastic.
The Mighty Anomaly: All right. And when it comes to your interviews, are you nervous about anything in particular? Any subjects scare you or anything that you're maybe a little shaky on that I should know about?
Blue Panda: I think in terms of my strengths and weaknesses in these interviews, I think I would say I have decent communication. As I've been told in previous practice rounds, I think what I need to work on the most is probably just working through difficult problems and thinking of different avenues of poking at the problem. I think that's what I need to focus on the most. And in categories, I think dynamic programming is probably my weakest link.
The Mighty Anomaly: Okay, fair enough. I think that's probably a good starting point here to kind of go off of, and we can maybe dive into more from there. Okay. I think that gives me a good idea. Now, the coding rounds, the way they work at Google, just give you a high level overview to make sure we're on the same page, is usually 45 minutes, and it's like a five minute intro. It's like a 35 minutes coding round itself, and it's usually like a five minute wrap up. It's important to note that these two can bleed over into themselves, and you might be able to get a little bit more coding, more time for coding, if you're struggling with the problem. But it's not likely that you're going to get much more than 40 minutes at a max. So we're going to follow that structure fairly closely. And throughout this interview process, we'll mock as close to what a Google interview might actually look like. One thing is just the fact that at Google we don't use editors. And if you've never been to Google before, I just want to make it very clear that you're not going to have an editor in front of you. You'll just code inside of a Google Doc. So because of that, I recommend usually doing an interview in this plain text mode, even though it's possible to switch to another language. Does that work for you or would you like to use this in text highlighting still?
Blue Panda: I'm okay with whatever is closest to the actual Google interview, so whatever most resembles that, that would be my preference.
The Mighty Anomaly: Let's do plain text. There are a handful of forks internally of Google Docs that will let you have syntax highlighting, but that's not guaranteed, so I don't want to tell you it'll be there and then have it not. So in this case, let's go just plain text and we can go from there. What language will you be coding in today?
Blue Panda: JavaScript.
The Mighty Anomaly: JavaScript, fantastic. Okay, great. Okay, then let's get started with a question. And the question itself is pretty straightforward, but I'm curious as to whether or not you've ever heard of the game before we jump into it. So the game is called Blackjack. Are you familiar with it?
Blue Panda: I am familiar with it, but I would appreciate a refresher. I'm not familiar with all of the rules for it.
The Mighty Anomaly: Sure, no worries. So in Blackjack, the goal is to get as close to 21 as possible without going over. And there's a rule in Blackjack that says if you are between 17 and 21, you can't draw any more cards. So with that said, in a deck of cards, I don't want you to care about clubs, hearts, spades, diamonds, anything like that. You could ignore the suits altogether. We don't also have to worry about face cards or like king, queen, any of that kind of stuff. So we can just imagine we have cards 1234 all the way up to ten. And so in this sort of set of cards that we could get, there's obviously more than one of every card. But the gist here is that when you play the game, you're going to get a random card. So you start, let's say it looks like this. This is a five. Let's say you then get a seven. So we're at twelve so far. And then let's say you decide to draw again because you are still less than 17 according to this rule. So you're allowed to have another card. So you draw again and let's say you get a ten. It's important to note the terminology here. This is called a bust. You've gone over and it's a bust. Let's say we did the same scenario again and you'd gotten, let's say, a five. In this case it's a 17 and this is known as a stand. Because you are between 17 and 21, you're going to stand still and not do anything else. That's the basic gist. So that's the rules of the game. They do get a little bit more complicated than that, but that's all you really need to know for the problem itself. Is anything unclear in that explanation?
Blue Panda: Nothing unclear, but I think I'm just going to reiterate here, just for my own clarification. If you notice that I'm saying anything wrong, just feel free to correct me. Okay, so we have cards given to us between one and ten, and we start or we're given basically a random card. Each time we need to choose a card, we're given a random card. Right?
The Mighty Anomaly: That is true.
Blue Panda: Okay. So the goal is to get to as close to 21 as possible without going over. And if we go over, that's called a bust.
The Mighty Anomaly: Exactly. Right. And if we don't go over, it is known as a stand.
Blue Panda: Right.
The Mighty Anomaly: So with that said, we have enough to, I think, be successful on the problem. The question itself is really quite straightforward. Feel free to take your time and read it, make sure you have a good understanding of it, and feel free to ask questions before we jump into any code.
Blue Panda: Okay? Okay, that sounds good. I'm just going to read it like semi out loud, if that's okay.
The Mighty Anomaly: Take your time.
Blue Panda: Consider a simplified game of blackjack with an infinite deck of cards labeled from one to ten. That means there is always a 10% chance to draw any card value, regardless of what's been drawn for. Okay, so that means we can choose duplicates, right? I mean, basically we can be given duplicates. So we're always going to have a 10% chance of choosing any card.
The Mighty Anomaly: Sorry, what definitely possible for duplicates? Yes, because it's an infinite deck.
Blue Panda: Okay. Yeah, right. Infinite deck, one to 1010 percent chance of drawing any card. It makes sense. And yeah, can pick any card. The dealer always plays deterministically according to the following rules. If the dealer's total is less than 17, the dealer will draw another card, draws another card. If the dealer's total is at least 17, but not more than 21 to retain 1721, the dealer stamps. So stance basically means like, they don't draw any more cards, right. They just skip the turn or something.
The Mighty Anomaly: Yes. In this case, this would be an example of the dealer standing.
Blue Panda: I see. Okay. If the dealer's total is over 21, the dealer busts and therefore loses. Okay. Determine the number of ways the dealer can bust. Number of ways the dealer can bust. Okay, I'm going to paste something here. This helps me work through problems.
The Mighty Anomaly: Okay.
Blue Panda: So our input, if I have this correct, so in terms of, I guess what are we basically looking for here? We're looking for a function that can basically take in what and return the number of ways the dealer can bust with an infinite deck of cards labeled one to ten. So do we have an input here or do we just use cards between one and ten?
The Mighty Anomaly: Good questions. In this case, we are not given input for this problem.
Blue Panda: Okay, so no input, just okay. Number of ways a dealer can bust with the given rules of blackjack. Okay, let's see. The number of ways the dealer can bust. Total is less than 17. I'm going to write down just the points that I observed here, just so if I have any questions, they'll come out to me. If total is between 17 and 21, dealers stance. So what happens when the dealer stands? Because this almost sounds like an infinite loop to me.
The Mighty Anomaly: Sure. So when they stand, the rule says that you can't draw any more cards. So in this case, this would be an example of us trying something and then it stops. So if we're choosing to count things, this on line 15 would be something we count. This would be an example of something that we don't count. We don't add anything to our total. In this case, it's not like an infinite loop because we can't continue drawing cards.
Blue Panda: Okay, I see. So if we land between 17 and 21, we basically not count this way, right? Because we need the number of ways. Basically we're looking for the number of ways that dealers can bust. And so this would be a way that we've reached a value and we do not count this way because it's between these two values.
The Mighty Anomaly: Right. We want the ways they can bust but not the ways they stand.
Blue Panda: Got it. And so if total is over 21 strictly, right, like greater than 21, then we count this way basically and away is basically like a way to get to that number, whatever that number is. So a bunch of additions. Okay, so dealers over 21 and the total is less than if total is less than 17 strictly, then we draw a card. So basically, like continue the way. Okay, I see. So I guess what stands out to me here is that I don't know if there's any edge cases to this problem since we don't even have any inputs, right? So I guess what stands out to me is that basically it's kind of like a recursive function, right? So we start off with our total being zero and we draw cards until basically, I think these two conditions one of these two conditions is met. So the total is between 17 or 21, or if the total is above 21, then we basically add to our kind of like a global output being ways, right. A recursive function where if total is between 17 and 21, basically just like add zero, like as you said to our output. Yes, total is above 21, we add one to output. And so other than that, we need to kind of drawing a card is basically like generating a random number between one and ten, correct?
The Mighty Anomaly: Yes. In this case it could be any card between one and ten.
Blue Panda: Okay. Random number between one and ten and it'll always remain one and ten. It's not going to change. As we mentioned before, like duplicates are allowed. Okay, so we draw a card. So we need the number of ways need the number of ways that we bust. Thing is we don't want to keep drawing a card. We kind of need some I think a way to basically say if we've drawn a card before because say if we draw a six again, we've drawn a six before with this way that we have right. Like we have a current way that we've gotten to this iteration, let's say. And if we draw a six, we have basically counted this way with a six. We want to kind of mark that I think mark said visited. Right. So what I'm thinking is have like a visited array. So visited array of indices of false all the way through between zero and between one and ten. So we can have it between zero and ten. That's fine. And we'll just ignore the zero s position because we can't draw a zero card. And if we draw a card and we got a random number, we basically visit that. But I guess when we are in a different way or like when that way proceeds, we may need to draw a six again. So I don't know if we want to reset this array or something, something to basically say that for this iteration I can use this number, but for an iteration that I've already used the number, I don't want to reuse it. Right. Do you kind of understand what I'm trying to say here?
The Mighty Anomaly: When you say not reuse it, it would be possible, like line 16, for instance, for you to reuse a five again and if you'd already done it.
Blue Panda: Previously right, yeah, right. We were using a five later on down the line. Right. But I'm basically saying if I kind of backtrack and I have to continue figuring out a different way to get to a different number from five and seven, let's say. Right. I don't want to reuse a five if I'm generating a random number. Actually. Is the condition that we have to generate a random number or can we just go from one to one to ten?
The Mighty Anomaly: Iteratively great question. You definitely don't have to do this randomly.
Blue Panda: You could okay. That makes things a lot easier. Okay, we don't have to do it randomly. I should have clarified that. Yeah. If we don't have to do it randomly, then I guess we don't need to worry about counting, I guess, because we're always going to go from like one to ten. Right. So we probably don't need the visited array then at that point get rid of that. So not a random number we're basically drawing a card equals basically kind of like a loop. We could say for I in the range one to ten. Right. We can call this function with total plus this I.
The Mighty Anomaly: Yes.
Blue Panda: And so when we recall it with this so we go back into these conditions. We say if total is between 17 and 21, we add zero. If total is greater than 21, we add one to it. I think this is the crux of it. Let me see if I'm missing anything.
The Mighty Anomaly: This is a pretty good solution. I'm comfortable with you starting to code, if you like. Sure. You to code more if you prefer.
Blue Panda: Yeah, no, I think I have enough here to start coding. So I think I'll start coding function no input, as we mentioned before. So I'll take care of the conditions first. So if my total is between 17 oh, I do need a total actually, because it's a recursive function. So total is between 17. Or I could just take care of the success condition first. Then my output is like some value. Either I can have some value out here and then pass it and then basically just let the function update it. Or I could have it inside here as well. I think either way works.
The Mighty Anomaly: Okay.
Blue Panda: Depends on how we want to do it. Having a global function kind of makes it easier to just have it be updated without the recursive function kind of carrying it along the way. So if total is greater than 21, then we do that return. Else if we say total is between 17 and 21 inclusively, total is less than or equal to 21 and less than equal 21, then nothing really basically just returns. Otherwise let's see if it's less than 17. Is there anything I'm missing? Okay, then I go to my function. When I starts with one I is less than or equal to ten I plus plus. I'm going to test this as well just to make sure. Total plus I. Okay. I think this is basically my code up here. Let me just test it to make sure though that I'm not missing anything. Okay. So I'm going to call it like this NUM waves 20 starting with zero. So total, obviously now. Then I basically go through passes with one. So my initial value will be one. And that'll basically keep going. Actually it'll be quite long with just ones in the beginning. Right. But to just look at the conditions, I think it should work. What do you think? I was going to test it, but I just looked at the fact that I would be checking ones continuously all the way down. It would be quite long.
The Mighty Anomaly: How long does that first pass go? Just out of curiosity, the first path.
Blue Panda: So we keep on adding one until we basically reach 17, right? Yeah, until we basically reach 17.
The Mighty Anomaly: Right. Then we end in that case.
Blue Panda: Yeah. And then we end in that case and then we add two to the last so it'll basically be 1718, 1920 and 21 in that last subtree, all basically returning. And then from that last 1 second last one, we will add what's it called? Second last one, we will basically add six because it'll be 16. So 16 plus six will give us 22 and that'll be a bus. So that's something we will count.
The Mighty Anomaly: Fantastic. So I think I understand the crux of your code for one. I'd like to just ask whether or not you could tell me what that time and space complexity would be for it. Do you think you can name that for me?
Blue Panda: Yeah, let me just think about it. At any given stage, we have basically ten options, right? And we are going through every single one of them. So if I have to draw out the tree, I would basically see that I didn't hear saying if I have ten options, then it would be I want to say ten to the actually there's no N though, is there an N? Because we don't really have an input.
The Mighty Anomaly: There is no input. However, how does that face things in that case?
Blue Panda: If there's no input if there's no input, then basically we're asking how does the function scale given a specific input, how would the function scale but since there is no input we can't really say, okay, this input goes all the way up to N or scales infinitely. So how would this function change? If there is no input then wouldn't this always just return you a constant? It'll always be a constant because we're doing it between one and ten each time.
The Mighty Anomaly: Yes, it's a cheeky answer, I think, but you're absolutely right with it in this case. I am curious if let's just pretend there was an input and we were just trying to describe generally how maybe the cards were changing or something like that was passed in. Could you give me just a rough idea based on what you were saying before ten to the something I think you were saying?
Blue Panda: Yeah, I was saying ten to the N, but I was trying to figure out what that N would be. So say let's say I am choosing ten at each iteration, right? So I guess we're asking for the total. So if we change the limits, like for example, if we're looking for a specific range, then we would basically change our yeah, basically that would be our N, right? Because if the range is different, then we're basically going to keep choosing from ten options until we get into that range. So then it would be ten to the N, where N is our range or maximum or whatever.
The Mighty Anomaly: Great. So if I had like one through ten I was starting off and I did sort of one through ten here that I tried and I was going another one. Let's say I picked ten eventually I'd pick here. So in this recursive tree, a common way for analyzing this is sort of like branching factor raised to the height of the tree. So the question is how deep exactly in our implementation does the tree go?
Blue Panda: This is for the space complexity. You're asking.
The Mighty Anomaly: For the time.
Blue Panda: For the time. For the time, I think, wouldn't the time be the number of calls that are made? I'm unsure as to how the height of the tree is related to the time. Elaborate on that a little bit.
The Mighty Anomaly: So in any really recursive function, provided you're not pruning or anything like that, you're going to have a factor that's going to be effectively whatever the branching factor is of the recursion raised to the height. That's what you kind of said here. You said the branching factor is ten and then you said N. So what I'm curious is, because this is a fixed function and it's not changing, what is N in your case, how deep does the tree go? In the worst case, what's the height of the tree?
Blue Panda: How deep the tree goes? Well, the depth of the tree, I know, is basically going to be approximately log of the total number of calls that are made. So total number of calls that are made in the tree believe the depth of the tree is basically log of that amount. But B, I'm unsure as to you saying this is the base, right? This is basically amount of options we have at each given stage, right?
The Mighty Anomaly: Yes. So in this case, you have the right branch factor. You have given a variable for N, but this is a fixed number. Since we don't have an input in.
Blue Panda: This case, you're asking like in this specific case.
The Mighty Anomaly: Yes, exactly.
Blue Panda: That would be 21, right?
The Mighty Anomaly: Actually get to 21. Can you tell me a path that goes 21 deep? 21 calls deep?
Blue Panda: Sorry, could you repeat that? I didn't quite get that.
The Mighty Anomaly: Can you tell me a path that goes 21 calls deep?
Blue Panda: Yeah, it would be the one path. Sorry, it would be the one path all the way up to one, and then at 16 when we add five. So really I think 17 actually, yes, 17 is the right number there because the amount of calls would be basically 17 and the 17th call will determine our condition.
The Mighty Anomaly: Fantastic. Yeah, you're exactly right. So in this case, how about we talk about space for this specific example as well? What would the space be?
Blue Panda: The space would basically be the maximum the space can be is 17. Right? Because that's the depth of the tree.
The Mighty Anomaly: Fantastic. Great. So I think this is imagine I actually chose to run this recursive function. We'll find that it's a little bit slow, takes a second to kind of run. I'm wondering if you can think of any ways that would maybe speed up this calculation, make it faster.
Blue Panda: Yeah, I was honestly thinking about the same thing. When I started to draw the tree on the right here, I realized that maybe we could probably memorize in some ways. If we've seen certain calls before, we could probably memorize that, attach that, and that may reduce our time complexity from ten to the 17 to actually approximately just 17, because the rest of the calls would basically just be I think we would be able to memorize them, but I'm unsure as to how I would memorize them. I think I need to kind of draw the tree out to see which calls are being made. Okay.
The Mighty Anomaly: Just as a heads up, in an actual Google interview, you have access to something called a jam board. And I definitely would encourage you to look at that on your own time, and I'll leave it in a note for you. But right now we have what's called drawing mode. If you look in the upper left hand corner, you have the ability to draw.
Blue Panda: I remember. Yeah, I got it. Thank you for reminding me about that. Okay, I think I'll use this time.
The Mighty Anomaly: Cool.
Blue Panda: You can also access this, right?
The Mighty Anomaly: Yes, I can see it.
Blue Panda: Okay, so let's see. When I start with basically zero, I have basically ten options, right? So one, then this call basically just keeps going one, three, really long way until I basically get to move it a little bit to the right. I'm thinking about memorization. Then I think the right side of this tree will basically be able to be cast, I think, so when we go all the way up till 116. So I think we're basically looking for the number of ways. So at each given point, we're basically looking for the number of ways. In this case, though, I'm not returning anything. Like, in the function itself, I'm not returning anything. I'm calculating the output on the outside. Right. But I think I'll have to modify the function so that I return something such that if it's in the cache already, I can return it. Let's see. So I think this number obviously plays a key role. Like, or any one of these numbers basically plays a key role, right. When I get to 16, I have one, 2317, and these will basically all be between 17 and 21 until I basically get to, let's say, six. And that gets me 22. So then it basically changes. But what I basically need to know, I think, is that if I've come across a specific number before, because between this entire tree, if I go, let's say two here, I can go two here, right? So I've already seen two before. I have also seen three before I come here. I've also seen three before in this one tree, in this one path. I've seen these numbers before. Instead of recalculating all this, I can just cache it by basically saying, okay, the number of ways that we can compute any number between zero and 17, number of ways we can compute the number of ways that a okay, hold on. Number of ways would change, I think, going from two to, let's say when I go from two to four and then four to, let's say five. Yeah. So it'll be calculated in this one path and then along with that, any values that I see on this two path will also be would also be able to be calculated on this left path. But I need to basically figure out what is my cache going to look like because what am I caching exactly? Let me just write down what I'm caching. I'm caching the number of ways that I can bust from a given number or from a given total, a given sum, basically. A given sum from a given sum. Right. And so the number of ways I can bust is basically like number above 21, right. So if I come across, let's say, 17, any value between 17 and 22, I'm not going to cache that. I'm not going to cache that. What I am going to cache is as soon as I hit 22 or any value above 22, that's a plus one that goes into my NUM ways. And then once that's done, all the way up till basically like ten, right? That ten is my maximum value. Once that loop is done, then this number of ways, it has its final value and then I can basically cache that in like an array going from zero to zero to what is my cash size going to look like? Maybe 17. Once I hit 17 to 21, I don't do any addition. Right, so it has to be 16 then. Has to be 16 because 17 to 21, I don't touch those numbers once I land on them. I don't catch anything, I don't do anything. So 16 is the last number that I do any type of addition at. And any number of 21, I don't do any addition. So then things will start getting filled up at 16. That number of ways will get stored. And then when I hit 16 again, somewhere along this tree, I'll already have the number of ways that I can bust when I've cached it like this.
The Mighty Anomaly: Right. And so in this case, specifically, how many ways can you bust from 16? Just make sure we're on the same page.
Blue Panda: How many ways I can bust 16. So let's say 16 plus six is the first. So then seven, eight, nine and ten. So there's this many ways. So that's five ways.
The Mighty Anomaly: Yeah. So in this case, this was five ways of and so whenever you get to this point of the tree again, let me change to a color. Okay, so when you get to this point of the tree again, just be like plus five, right?
Blue Panda: Yeah. I'll basically get that plus five and add it to my current number of ways for whatever number I'm on all. Right.
The Mighty Anomaly: I think I've got pretty good ideas to what you're doing. I'd be interested to know how you plan to do it with the array, but if you think you have a good enough idea, you're welcome to jump back into coding. Or if you want to keep diagramming, that's fine too.
Blue Panda: Okay, yeah, let me try coding it now if I need to adjust my approach and I'll probably go back to the drawing board. Let's see. Okay, so at the moment, I'm not returning anything. So I think what I do need to do is I need to keep track of my NUM waves, which I'm not keeping track of. Let's say I do keep track of that and I have my output here. That output, if I have it globally, then it'll just keep changing as I'm recursing in different directions. But I think I need this to not change, actually, instead of NUM waste, I think if I just do like one or something, if I return one, then I may automatically be able to just calculate it on the fly. So let's get rid of output. I know that when I reach 21, that's away so I can account that with one. So if I know that I'm between 00:17 and 21, I know I can return zero. That's not a way. So then when I come here, I basically say numerous to bust with my current total and this value passed will be whatever it is here. So five is what I'll receive. Actually. I need to have it out here and then increment to it needs to start with zero. And then I basically say NUM waves plus equals whatever I get right from adding. And then I need to return that at the end. But I need to make sure that I'm caching here. So let's see what my cache would look like. Human cache would need to be on the outside. So I know that my cache is going to have a length of I said zero to 16, right? So I have to have 17 positions. Then whatever total I'm on, I need to basically cache. So before that though, I need to make sure that if this total is already included in the cache so let's say I fill this in with negative one to make sure basically say that I have not touched this total yet. So if cache at total is greater than negative one and return that and so number is zero. So before I return though, I need to say that cache at whatever total I'm on at this stage at total equals memories and then I return. So then I would just be able to say return down here, see if there's any bugs. Cash add total. Yes. That's not the correct syntax and this is also not the correct syntax. Add total. Yes, fine. Return one if I bust over, fine. And then wage starts with zero. Would it start with zero? Yeah, I think at any stage it would start zero and then I would just keep adding as I find them in my cache. And I think that should basically work.
The Mighty Anomaly: Okay. I think your overall solution is a pretty good one. I would like to maybe talk about that time and space again and let's talk about what you think that changes to now.
Blue Panda: Right. So since the tree basically after memorization is going to be skewed similar to like a Linked list, right. All the right side calls that I mentioned before are basically just going to be memoized. So it'll basically have a depth of 17 still. So the one calls are basically going to go up till 17. Right. The recursion stack space will still remain 17. I'm thinking though, the time actually now goes down to 17 approximately. Well, actually not exactly 17. Wouldn't be exactly 17. If we're talking about exact numbers, then since we're touching all the memorized, all the cached values again, right? We're touching them again. Let's see exactly how many values. Let me go back to my drawing board and maybe I might have to draw the entire not draw the entire tree out, but draw like a portion of the tree out to kind of see how many talls would it end up being in total. So we know that this side is basically just going to go up, go 17 all the way up till basically 16. One, two, three. We have ten calls here. Are we looking for exact like an exact number of calls here? Basically for the time right?
The Mighty Anomaly: I'd be interested to know. So your algorithm, for instance, is exponential pre optimization. I'm curious if you could give me at least a rough time savings from that perspective.
Blue Panda: Okay, so I know it's going to be definitely between it's going to be at least 17 because we get those 17 calls from going all the way down here from one, right? And then we start caching from well, zero doesn't get cached, but basically start caching from 16 backwards. Right. And then once we come across these again, which is basically 17 again, we're guaranteed to basically hit one of these again. So anytime we basically hit a call again on the right side, it'll be between here. So the maximum that can be called again, I don't know if each one of them will be hit. Each one will be hit once. They can be hit. Hold on, I think they might actually just be hit once at most at 16, I get ten more calls right, going this way. And so 16 just gets cached. And then let's say when we were at one and we added one here, so when we add two here, we add three. And we know that's some test here, we don't go any further than that, but we basically still are going through all of these. All right? Yeah, we're still going through all of these. So four, five. So actually we're doing ten calls again still. Ten calls again for each one of these, one of these 17 calls, that's at least 17 times ten here. Not 17 times ten. Sorry, was my previous time. Ten to the 17 times. So then I don't go any further here, but as a zero going two, three all the way, ten more here. So for each of the 17 calls, I'm doing ten calls, right? Yeah. I'm doing ten again to access the cache. I think each of the 17 calls, I'm doing ten. So would it be ten times 17?
The Mighty Anomaly: Yeah, you're exactly right. There's 170 problems here. So really good. So to be honest with you, I was honestly just looking for you to say that it was linear.
Blue Panda: It is going to be linear, but.
The Mighty Anomaly: The fact that you could calculate it is also really good as well. So last question before we end. And it's okay if you're not sure, but I'm curious. If I were to ask you to calculate the percentage of chance that a dealer would bust, and let's say I was like, some executive and I was like, okay, it's great that you did this thing. But what's the percent chance that this busts? What would you do to get me that answer? I'm curious.
Blue Panda: Percentage of chance to bust at any given stage. We're saying at any point in time.
The Mighty Anomaly: What'S the percent likelihood that a dealer.
Blue Panda: Busts at any point in time? Well, there are going to be a lot of calls in the early stages where there is a 0% chance of busting, because any number you add to two between one and ten is not going to give you a value above 21. True. So let's see what are the values where the chances started to change? So we know that between one to what value is that? What value is that? 21 minus ten. Right. Because ten is the maximum value you can basically so we're talking strictly above 21, right. So it would be 22.
The Mighty Anomaly: Yes. In this case it'd be any chance of an actual bust. So a 21 is in the bust.
Blue Panda: 21 is in the bus. Okay. Yeah. So then we're saying that one till twelve, or rather actually one till eleven is no chance of bust. One till eleven is no chance of bust. One till eleven, there's a 0% chance of busting here. So then we're saying that twelve till 16 is when our chances started to chances start to change. I'm going to move this a little bit. What happened?
The Mighty Anomaly: What happened?
Blue Panda: Can you see the screen still?
The Mighty Anomaly: I can still see the screen.
Blue Panda: It just disappeared for me.
The Mighty Anomaly: You can maybe if you're having issues or close the thing and open it.
Blue Panda: Up again, it's fine, I'll just clear the entire thing and then I'll just go, I know where I'm at. So I think I'll just say, yeah, I'm going to have to refresh it okay. Can you still see it?
The Mighty Anomaly: Yes.
Blue Panda: Okay, so one to eleven. I know that there's a 0% chance to bust, right. So I'm saying twelve onwards. So what are the numbers? That basically any number, I think not any number. Ten is the only number that busts. 12, 13, I have ten, nine and ten. Right. 14. I have eight, nine and ten. That bust. That 15. Seven, eight, nine and ten. 6,7,8,9 and ten.
The Mighty Anomaly: I'm going to pause you here. We're right at time, and I know we didn't get a whole lot of time to finish that last part, but I see where you're going, which is a good thing. So you still get credit because I see where you're going. But feel free to close the drawing mode. We're going to go back to the editor for a second and let's talk about how you did. So this is great. So normally this would be the end of the thing, and we'd be like, okay, thanks for interviewing ######, but we're going to just kind of stop and that's the end. And you don't really get to hear any feedback. But in this case, we get to give you some feedback so we could tell you how you did. Let's talk a little bit about how you think you did. First, I don't want to bias you with my opinion before you have a chance to do just a mini reflection on your own. So do me a favor. Tell me what you think went well, in addition to what you think needs improvement.
Blue Panda: I think personally, I thought I was a little slow. I know that usually I think in l four positions, and especially in onsites, I think you're asked two or more questions in a 45 minutes interval. Right. And so this was still only one question, and I was just basically just trying to achieve the optimal solution to this one question. I'm kind of sad that I couldn't get to the second question. So in terms of, I think the question itself, I hope I didn't make any mistakes or bugs. As far as I can see, I think my code works fine, and it does give the approximate optimal solution. Maybe if I did the bottom up approach, it would have been slightly, practically faster, but nonetheless, I think the time complexity would be approximately the same.
The Mighty Anomaly: Very cool. Anything else? Or is that about the end of the reflection?
Blue Panda: That's all that comes to mind at the moment for me. I'm sure if I dug more, I would be able to find more stuff.
The Mighty Anomaly: Okay, cool. Yeah. So it's not meant to be like a humility test or anything, but I think generally speaking, let's just maybe unpack a couple of things you said there. So right off the bat, I want to say that are you familiar with the website called Blind? It's a forum where people talk about their experiences at fang companies.
Blue Panda: Yes, I am.
The Mighty Anomaly: Okay, great. So it sounds like you've been reading on Blind too much. Generally speaking, you are not expected to do two questions even for an L four or L five or L six position at Google. That's a myth. It's not something that's standard. As a matter of fact, it's practically just correct from an interview standpoint.
Blue Panda: Now, that does not sorry to interrupt you. Actually I didn't read this online, but I believe my recruiter actually told me that I should pace myself so that I'm able to tackle two questions in a 45 minutes interval.
The Mighty Anomaly: Got you. So I'll say with that recruiters, how do I say this? Tax League usually don't stay at a company for more than about six months. I'm guessing that this particular recruiter worked previously at some place like Facebook where it is common to get asked two questions, or potentially some startup company or something like that. So it's not super likely that I would say anything that a recruiter tells you, and this is something to be treated with suspect. I wouldn't say just take anything that they say at face value. For instance, it's common to also be told that you are going to get a system design question, and at your level, L four, it's possible, but it's also not required, so there's a chance you might not get it. There's also a chance they'll tell you you won't get it and you might get one. So I just would treat anything your recruiter says with a grain of salt. And that makes it sound like, I don't like recruiters. I really do their job really hard. But honestly, the requirements change and they don't stay at their jobs very long because it's a very demanding job. So it's problematic. But at any rate, I would say that in a Google interview, it is not normal for you to get two questions. It is worthwhile to mention specifically, though, what we mean by two questions. So some people would say, like, the first thing you did was solving the problem recursively, and then I was like, do it faster. So it's like, is that a twist? Is that an additional question? What about the follow ups where I was asking about time and space complexity and the percentages are those additional questions? So it kind of depends on just what people mean by two questions here. But usually speaking, it's one question. There might be some twists to the problem if you get done early, but it's just one question. That's one thing to note. So you said you were slow, but you actually went by at a great pace. I was running out of twists to ask you to the problem. So I think you did really well here. In terms of your code quality, I think your code is great. Your code does appear to work at first flush, I admit. We don't copy this into an editor and verify that it passes all edge cases. Honestly, engineers don't really have time to do that, but generally speaking, at a glance, your code works, which is great. You also were able to get the optimized approach, which is also great. I think your answer towards what the time and space complexity was of being constant is really cheeky, but also great. It's a great analysis of the problem overall, and your general analysis of being able to find the amount of subproblems that there are is also pretty great. So I think you just did a really good job overall here. I think that the one thing I would say in terms of kind of like a communication standpoint that's maybe worth calling out for a second. Is it's hard to tell if it's the mic you're using or possibly maybe just because you're not particularly enunciating, but it's sometimes hard to understand what you're saying and it's really hard to tell if it's the mic or if maybe you're just like talking fast or maybe you're mumbling a little bit. It's really difficult to tell. But I suspect just a mic change might help because there were times where I had to ask you to repeat yourself or I wasn't sure what you meant, so I had to ask you to rephrase it. And that's a silly thing to waste time on just because I can't quite tell what you're saying. I do think overall, your template that you kind of pasted in was really quite great. I wish more people kind of followed this. Everyone sort of is told generally that this is the flow of an interview you should follow, and yet they're like, you're the first person I've ever seen that pasted a template and there are very few people that actually hit all of these steps in an interview. One extra thing to call out specifically was your edge case condition. You said there's no input, so I don't think there are edge cases, and that's not really a great way to think about edge cases. I think, for instance, here's an edge case. On line 15, I've got five, seven and ten. On line 16, I've got five, seven and five. Now imagine I have let's call this five A and five B. Then let's call this five B and five A. So in this case, does this count as a different sequence or does it count as the same one? I mean, that's totally up to the interviewer. In this case, it's not something you confirmed, so it's really kind of hard to tell what did I want? In this case, you happen to code exactly what I want, which is great, but there's always a chance that maybe you wouldn't get that. So edge cases aren't necessarily dictated by input, so I'd maybe spend just a second on it, regardless of whether you're given an input or not. Does that make sense?
Blue Panda: Yeah, I think I get what you mean by edge cases. You basically mean scenarios that can happen that we may not consider as normal circumstances or like normal ways for the function to proceed that could be like an outlier basically like an outlying way for the function to proceed or like a way that we have not really considered but that could be problematic.
The Mighty Anomaly: Exactly. What I call it with clients that I coach is basically assumptions. Like what are the assumptions we've made about the problem? I think edge cases sort of assume some trivialities like what if you're passed in a null input or something and nobody cares about that? We're going to assume you're passed in something valid that's not particularly worthwhile to call out, that if you're not given the correct inputs, your function won't work. But given valid inputs, what assumptions about your problem are you making? So in this case, how to count it? What counts as a sequence here is a worthwhile one to kind of spend a second on. It's also worth noting specifically that you sort of get clarification in the problem early about whether or not you needed to randomize the cards. Did you need to draw randomly? So that's a good thing to just again sort of clarify. I think people assume that you have to in which case they've been just randomly generating for some amount of time until they've computed potentially every single thing and they realize much too late in the interview that it's a problem. So I think you had an assumption that you then sort of verified, which is great, we definitely want to see that in L Four engineers, which is really quite strong in your particular case. I do agree with you that your communication also is super strong here. So I don't think there's any real work that need to be done there. And I think the template really helps you kind of just sort of keep pace, honestly. It's just also, even if the template didn't help you at all, I'd still recommend doing it because it just looks super professional to do that, to be honest with you. So that's great. I loved it. I would say one thing about your code for a second, just to spend just a brief second on. So you're coding in JavaScript, but this on line 69 is like Es Five syntax and Es Six came out in 2015, I think, or something like that. Is there any way or any reason you didn't ways to make it an arrow function? Like all that kind of stuff? The way you would kind of normally do it with more modern Es Six syntax?
Blue Panda: Actually, the thing is I'm so used to lead coding and in lead code, actually yeah, I think in lead code syntax is slightly different. I think it's more similar to basically what you said, right? Like name equals function or not naming this function. It's even weirder, there's so many different ways of making a function in JavaScript. But I went this way because actually the way I kind of practiced. I like to play around a lot with functions. I just want to have the function anywhere. Right. So the one thing about these declarations, or these declarations is they're not hoisted, these functions. If you declare them this way, they're not going to be hoisted to the top of the scope, but these functions are, right? So in, for example, vs code or wherever I'm coding, if I'm trying to just have the function anywhere I want in my page and play around with the input before and after or wherever I want, I wouldn't be able to do that necessarily here. Or I may not even be able to mess with the function before I declare it or basically refer to it. So this is kind of the way I'm used to, but I think they're both fine, right. I don't believe that there's any performance issues or anything like that.
The Mighty Anomaly: Go ahead.
Blue Panda: And also kind of like, I think readily apparent to the people who do not know JavaScript all too well that this is a function, because there's a function keyword right there.
The Mighty Anomaly: That's true. If you're coding in JavaScript. What you're saying, I think from the interviewee side that you explained, that makes sense, but think about from the interviewer side, I'm looking to see like, do you know JavaScript? And the first thing I see you write is syntax from seven years ago. While it's true that this is how leak code does it, or approximately how leak code does it, I think there's just some trade offs. Even if you just said, I'm going to write it this way because leak code does it this way and then continued on, that probably would be fine, but worth just kind of calling out that this is like super old syntax. And in terms of I agree with you, but I do think that you can also get around that by using closures. And if you're using closures within your functions, you still can play with like you'd have a class function and then kind of work within that and you still can get like 90% of the benefits. But I get what you're saying and I think you defended your case well here. So you clearly understand JavaScript and you're able to talk about more complicated topics like wasting and whatnot. So I'm not worried about it. But it is something that I think the last thing you would want to do is not have time to explain why you did it that way and then get docked down. You're using outdated syntax, right?
Blue Panda: I definitely get your point about outdated syntax. I mean, in ESX nowadays, in any JavaScript framework, you will not find usually the syntax ever being usually mostly this. So I definitely get your point about that. Cool.
The Mighty Anomaly: All right, well then that's the end of the interview. I'm going to give you maybe a couple more bits of feedback in the actual write up at the end of this, but honestly, you did really well here. You were able to optimize, go through the problem, and answer sort of follow up stuff, and you clearly understand time space, JavaScript, and general dynamic programming memorization. You did well here. You would have passed an Onsite L Four interview with me. So nice job.
Blue Panda: Thank you. Thank you so much. I really appreciate all your feedback. I think you gave me better feedback than pretty much any interviewer so far. I really appreciate that. Thank you.
The Mighty Anomaly: Glad to hear it. Well, hey, speaking of feedback, just so you know, at the very end of this, you get a chance to rate me. Now, a lot of people leave five stars and say, not applicable, but I definitely appreciate any feedback you can give. It also just kind of helps improve. So if there's anything positive or negative you want to leave on something I did, I definitely would like to take advice and improve on my own as well. So I appreciate a five star rating, but if you have any improvements, let me know.
Blue Panda: Okay? Yeah. Yes, absolutely. Definitely will. Thanks so much.
The Mighty Anomaly: All right, see you at Google soon. Have a good one.
Blue Panda: Thank you. Goodbye. Bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
