We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
interviewing.io

Please read our definitive guide on Google's hiring process and questions

Rust Interview with a Google engineer

Watch someone solve the design a leaderboard 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

Design a leaderboard

Interview question

1) Design a Leaderboard class, which has 3 functions: 1. addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score. 2. top(K): Return the score sum of the top K players. 3. reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function. 2) You are playing a game with integers. You start with the integer 1 and you want to reach the integer target. In one move, you can either: Increment the current integer by one (i.e., x = x + 1). Double the current integer (i.e., x = 2 * x). You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times. Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Interview Feedback

Feedback about Professor Squirrel (the interviewee)

Advance this person to the next round?
Thumbs upYes
How were their technical skills?
4/4
How was their problem solving ability?
3/4
What about their communication ability?
4/4
Notes: + You clarified the problem scope. + You asked really good questions to understand the input. + You design the API for the class. + You identified the map as basic data structure to have. + You used heap to solve query part. + You used good naming convention for the variables in code. + You code was precise. + You suggested ways of improving it could be towards some sorted thing. - You needed some help to come to data structure for binary search tree. + For second problem you explained your dynamic programming solution. + You explained your greedy solution. - You could have optimised your implementation. Overall: I feel you did solid in this interview and I would have given a hire call.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?
Thumbs upYes
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
Very helpful interview, and you were very pleasant to chat with. Thanks again!

Interview Transcript

Red Maelstrom: Cool. Awesome. So I think you requested for an interviewer from Google. So is it like just because or like you specifically have upcoming interview with Google? So that would be my first question.
Professor Squirrel: Yeah, that's a great question. I do not have upcoming interviews with Google, but I get the sense that the Google interviews on interviewing IO are the best ones. So this is the one that I'm booking for practice.
Red Maelstrom: Understood. Understood. Is it fair to assume that you are generic back end engineer or a full stack engineer looking out for a free role or you have MLE or some of the specialization?
Professor Squirrel: This is pretty reasonable. I think full stack is the closest of the options you mentioned. I don't actually have any experience with web development whatsoever, but I also don't have a super specialized focus area.
Red Maelstrom: It's the generics three kind of roles which you would be interested in.
Professor Squirrel: Yeah, that's right.
Red Maelstrom: One last question where you are in your preparation, like are you good and you just want to understand how you are presenting an interview. You are at that level or.
Professor Squirrel: You.
Red Maelstrom: Still want to get a hang of how well you are prepared?
Professor Squirrel: Great question. For background. I was working at Google out of university. That was my first full time job. I got laid off at the beginning of last year as part of the layoffs. It's all good. Don't worry about it. So I passed Google interviews that time around. And that time I felt very prepared and I felt like I did extremely well. This time I'm just starting my job search. It's been maybe two weeks since I've started and I feel a little bit rusty. I had assumed it would be easy again because I just remember everything. But it turns out I think zinc code is kind of one of those things that fades without practice, just in terms of speed, raw speed. But in any case, I think I have all the fundamentals and mostly it's a matter of just getting repetition.
Red Maelstrom: Sure. So what I will do is I will kind of have this expectations that you are looking out for how you are. Like I will assume you as someone who is prepared but who might be the same. The interviewing part of it.
Professor Squirrel: Yeah.
Red Maelstrom: Okay, so one last question. One more question. Like what level you would be targeting for? I think you mentioned three years mentioned that you have three years of experience. What level you were in Google? Was it l three?
Professor Squirrel: That's right. So that was my first job out of university and it was l three, like new grad, university grad. And I was only working there for eight months before I got laid off. So I think that the roles I'll be considered for are still entry level roles. Again, like, l three.
Red Maelstrom: Got it. And, like, currently you're working.
Professor Squirrel: No, I haven't worked in over a year. I've just been unemployed. It's been nice, honestly. But I think it's time for me to start looking.
Red Maelstrom: Okay. Okay. Okay.
Professor Squirrel: You.
Red Maelstrom: You took a break and then now you're coming back to the market.
Professor Squirrel: Okay. Yeah, exactly.
Red Maelstrom: Makes sense. Sure. So I think, like, that makes sense. So, l three, you are targeting, like, kind of roles. Yeah. Got it. Cool.
Professor Squirrel: Thanks.
Red Maelstrom: For context. Yeah, I think, like, usually this helps me to understand, like, what kind of questions I should choose because, yeah, I have been there where, like, people are very early in their preparation and then they, like the basics of the graphs and stuff. So it's, like, very demoralizing asking directly. So I added these things into my initial thing. Got it. Cool.
Professor Squirrel: Yeah.
Red Maelstrom: So usually, like, I will spend, like, around 40 minutes or, like, maybe more than that. And then, like, I will keep some time for feedback based on, like, whether you have a hard stop at the end of 1 hour. I don't have any hard stop at the end of 1 hour. And I think, like, you are coming back into the interviewing things. I would like you to give some more time, maybe in terms of, like, some other aspects about job search or. Yeah. So a few other aspects if needed. So if you have some extra time, I can plan according to that.
Professor Squirrel: Okay. Yeah. Yeah. I've got no commitments after this.
Red Maelstrom: Cool. Awesome, awesome, awesome.
Professor Squirrel: Yeah.
Red Maelstrom: So let's start with the first question. So let's say that you want to design a leaderboard class. This class should provide three different methods. First one is add a score. So basically, given a player id and a score, you should update the leaderboard like this. You should add that much score to the player id. And if it's like, the first time you are seeing this player id, it should be existing score can be assumed at zero. And this should be like, total score. After ad score, the top k will return the score of, like, sum of, like, top k players score some of top k players, and the reset for any particular player id will reset the score of that particular player to zero.
Professor Squirrel: Okay. Okay. Interesting. Cool. That all sounds good to me. I guess we'll start making some notes and maybe asking some questions. So it sounds like there are a collection of players and each one has a score. Are the player ids known in advance or are they generated sort of arbitrarily.
Red Maelstrom: That'S a good question. How would that help you? I just want to understand.
Professor Squirrel: Good question. I'm not really sure yet. I'm just sort of asking probing questions to try to get all the specs.
Red Maelstrom: Got it. Yeah.
Professor Squirrel: So.
Red Maelstrom: I think so. You can assume that these player ids are random, but, yeah. So maybe I can help you. Like how this could have helped you if there would have been a specific range. Let's say the player ids are not more than 1000. You could have used array as a data structure rather than hash map as a data structure. Those things can, right?
Professor Squirrel: Totally, yeah. Let me ask some even more basic questions about the data types involved. Like the player id you suggested just now. It might be an integer. Is that case like positive integers for players? Is that assumed?
Red Maelstrom: Good question. Yeah, it's a non zero integer value.
Professor Squirrel: Okay. Non zero integer.
Red Maelstrom: Sorry. Non negative integer.
Professor Squirrel: Non negative. Sure. Okay. Non negative. Sure. Sure. And I'll assume it's small enough to fit in like 4 billion, something like that. A 32 bit integer. Is that okay?
Red Maelstrom: Exactly. Yeah. Those are the good questions. Yeah.
Professor Squirrel: Okay. And then the scores. It sounds like they're not fractional. Are they also integral?
Red Maelstrom: Yeah. They are also integers.
Professor Squirrel: Okay. So I'll say that.
Red Maelstrom: And, like, everything can fit in the integer range. Even the sum of all the scores is within the integer range.
Professor Squirrel: Okay, awesome. Okay, cool. So I think one thing that'll help me to get something on paper is actually just to write the sort of stubs for the methods in code. Are you all right with me doing that?
Red Maelstrom: Sure.
Professor Squirrel: Okay, sounds good. I'll get to that. So, leaderboard. Class. Leaderboard. And it'll have some methods, probably a constructor. And then pass or id.
Red Maelstrom: Is also.
Professor Squirrel: The number top k I sum. So kind of. This is what I'm thinking so far. And there is reset. Let me write that. Okay. And you said to design this class. Do you mean that I should write the code to implement it as well?
Red Maelstrom: Yes. Yeah, I am.
Professor Squirrel: Sounds good. Okay, so I should actually be thinking about, like, data structures and, like, practical sort of stuff at some point. I don't want to move too slowly here, so let me start thinking about that. So, I'll probably want a collection. I'm guessing the collection would be keyed by the player id and store values which are current score. I think it makes sense to use a hashmap since the player ids are from an unbounded range. So imagine this is like scores. Player scores or something. Hash. Two. And I guess the idea would be. Well, let me ask some questions about sort of what your expectations are or, like, what you want from me. Like, is this the case where you're hoping me to talk about the big O time complexity of these various operations and, like, you know, make reasonable choices to minimize them?
Red Maelstrom: Yeah, yeah. So I'm okay with, like, you going through iterations and not having all the choices at the first, but, yeah, I will definitely love if you can identify some trade offs that's not super important.
Professor Squirrel: Okay. Yeah, I can try. So, yeah, trade offs. I mean, you mentioned using a flat array. In this case, that would be, I guess, like.
Red Maelstrom: No, that was not a hint towards solution anyway.
Professor Squirrel: Oh, for sure.
Red Maelstrom: I was just talking general. Like, these kind of inputs can be used in that aspect.
Professor Squirrel: Totally. No, I just meant that I can talk about why that's bad, if that's something that would be interesting.
Red Maelstrom: Yeah.
Professor Squirrel: Okay.
Red Maelstrom: Yeah. Can you talk about why it would be bad?
Professor Squirrel: Yeah, sure. So I guess the issue is that the player ids come from a range of, like, zero to 4 billion, which if you want to pre allocate a flat array that doesn't dynamically grow and that just has, like, direct access buckets for all players, that array has to have at least 4 billion cells. And so it'll take like four gigs of memory. Or I guess in practice, because there's a four byte integer stored for each, it'll take maybe 16 gigs of memory, which is probably unreasonable, unless, I mean, you know, maybe you. You have a certain usage pattern that actually makes that make sense, but it seems very unlikely for typical workloads, I guess, is what I'm thinking. So I can note that this is like, flap array. Way too much space. Which space up front? Probably not a good idea. Okay, fine. Hashmap seems pretty natural. Will take sort of initially no space at all, and then the space grows proportional to the number of players that are currently. That currently have non zero score. Interesting, right? So the add score will never take a negative number. It's not like you need to reduce scores. It's only a reset that would decrease the score.
Red Maelstrom: Sorry.
Professor Squirrel: Well, I'm clarifying something I was asking earlier, but, like, the score input to add score. Like that is an unsigned number, right? Just.
Red Maelstrom: Yeah, that is also unsigned number. Yeah, yeah.
Professor Squirrel: So I guess, anyways, what I was in the middle of saying is just that the space complexity will grow linearly with the number of player players that have non zero scores. Got it.
Red Maelstrom: Which is kind of necessary in terms of storage. Got it.
Professor Squirrel: You said won't or will?
Red Maelstrom: Can you repeat I'm saying like, that does make sense, but it's okay. Like the total, having the complexity with terms of like number of calls which are happening to this object, having an order of that should be okay.
Professor Squirrel: I see. Yeah, yeah, I see. Okay. So in particular, it would be linear in the number of calls to ad score. Okay. Right. Okay. I guess the. So anyways, I'm probably missing the point of the question here, because ad score and reset are trivial if we have a hash map. And that's all well and good, but there's this top operation that I haven't actually started thinking about yet. So let me think about how I would implement the top operation. I guess it would be nice to have some sort of priority queue, probably. So let me think quietly about that, because I'm struggling to think and talk simultaneously. Interesting. Wow. Yeah, there are a lot of tradeoffs here, I feel. Or at least I can't think of an obviously optimal thing right away. Okay, so maybe it's hard because there's so many parameters I could use, but let's say nice n be the number of method calls. The total number of method calls. This is a bit coarse grained, but I think still useful. I'll say o of nspace ad score, one time reset. O of one time meta question, which you don't have to answer during the mock. I'm curious if this is like typical sort of thing to do for simplicity and like this is something people do.
Red Maelstrom: I think those are, you are going in the right direction. But maybe that key could be anything. And you can assume that, that k could be less most of the time it should be less than total number of players.
Professor Squirrel: Yeah, that's a great question. I hadn't thought to ask that yet. So if k is larger than the number of players, I guess implicitly there's a bunch of zeros. Like you can invent players that have score zero. So top should only sum the minimum of curdum players and k, whichever is.
Red Maelstrom: And you can even, you can even think in that case, like different ways of handling it. One way could be like it's not a valid operation, so you can just throw an exception, or you can just use the sum of all the existing players, a few things that you can ask in the actual interview. That would have been a good input from your side.
Professor Squirrel: Totally. Yeah, that makes a lot of sense. Okay, got it. I think I like the choice of using the, if k is larger than the number of players, I think I like using the sum of all players, but I see how that's a choice to make. I'm just trying to think about how to implement this. If we had a hashmap, like the naive thing would take o of n time.
Red Maelstrom: How would you do it in end time? Because k could be more.
Professor Squirrel: Right.
Red Maelstrom: So how will you maintain top k aspect of it?
Professor Squirrel: Right, so the actual implementation would involve scanning the whole player's scores. You could maintain a sum of top k. Yeah, sure. You could maintain a priority queue of bounded size, size k. And would it.
Red Maelstrom: Be like a mean heap or a max heap?
Professor Squirrel: That's a great question. Deep in my memory I've seen a leetcode question like this and I remember it's the non intuitive answer. So let's see. I guess if you're trying to find large things, you'll actually keep min heap, so that the least useful thing you've seen so far is the one these throw out that gives you efficient access to update and always hold the top k things you've seen so far. And then once you get to the end of the stream, you have a collection of k things that are the largest, and then you can add those up and return. Does that all make sense?
Red Maelstrom: Awesome. This is perfect. I'm okay with this. What would be the complexity of your top key operation in that case?
Professor Squirrel: Yeah, oven like I've written on line 26, because you do have to. Well, o of number of players, I guess, which is bounded by n won't.
Red Maelstrom: Like adding into priority queue call extra.
Professor Squirrel: Oh, there's a log factor. I'm sorry? Yeah, I mean log factors, to me it's just like a constant factor. It's like your machine can't store more than two to the 64 bytes of memory and not even close. So 64 is what I'm imagining. But yes, there are definitely log factors, and in this case it's log k. So I can throw that in there if you like.
Red Maelstrom: Sure. Cool, I'm good with this. Let's try to write code for this.
Professor Squirrel: Yeah, okay then. Sure, absolutely. So let's fill in some of these. So new, this is pretty easy. Error scores, hash, map, native, add, score, self, entry self, and this inserts with zero if it doesn't exist, called remove or delete. That's pretty easy. And this will succeed if the player id doesn't exist, which I think is fine based on the spec you say it's guaranteed. I don't need to take advantage of that, so I'll write it the way I've done. Yes, so, okay, so enough top. So k equals min n. Okay, so this is making sure that there are, at most, the k is bounded by the number of plots to start with. And then what we want to do is get the K largest scores and then add them up. So this is the goal. We can do this with the loop. So let's loop over four score in. We want a minus. I said in the heap, right? Yeah, sure. Klargis equals new. And basically we could do a couple of things. If it's less than k, it's easy. Armstrong? There's a detail here which is that the standard library heap is a max heap by default. So you need to reverse the definition of ordering, which you can do with this thin wrapper type called reverse API. Details aside, the gist is that we want it to be a min heap, and we've done that. So Keller just lined up. Okay, so basically, if it's saturated, if it's fully k, things, you could say, let me call it up, existing score. Existing score equals kandlarges off. And then let's max score. And then. I really hate these red squigglies, but I don't know how to make them go away. So that's the gist of the core approach here where we're, where we're scanning, and if the heap is saturated, we sort of will take the smallest element from the heap and we'll compare it to our existing one and we'll put back whatever one is larger. So that way we maintain this invariant of keeping the largest things that we've seen in this prefix of the stream. The very final thing we have to do is just add them. So simply do it. It's interesting that I have access to a compiler in this editor. Do you want me to fix all these errors or should I just keep writing?
Red Maelstrom: No, no, it's okay. Yeah.
Professor Squirrel: Okay. Sure, sure. I think most of them is just because I haven't imported the standard library names. It's like an import statement is all. So I guess with that, I'm done. This approach, I think this is kind of all we need to do.
Red Maelstrom: Awesome. I think. Yeah. Do you have any? Yeah, maybe like, I'm not saying that this is super important, or do you want to spend some time to think about way to kind of like optimize this? By saying of optimizing it, I don't mean that you should optimize everything. It's okay to have extra time in other operations. But let's say like, can you, with that trade off, can you try to optimize your top key API?
Professor Squirrel: Cool.
Red Maelstrom: Maybe like to optimize that you might incur additional cost in ad score or research score.
Professor Squirrel: Yeah, yeah, yeah. That sounds good. Yeah. In particular, it is kind of brutal that one of our operations takes linear time because.
Red Maelstrom: Yeah, but like, I totally understand sometimes, sometimes this might be okay because like the probability of top key operations could be very less in the actual production. So in that case we are doing it and you can even talk about. And you can sell your solution in that way also. So. Yeah, yeah, yeah.
Professor Squirrel: That kind of aligns with what I was sort of getting at here, which is in a bad case, you could have linearly many calls to top, and since they take linear time, you'd end up with a quadratic sort of overall runtime for your whole sort of like batch of operations, which is a thing that. Yeah, so, okay, so if we are interested in other ways of doing this, I'm especially interested in a way that doesn't have any linear time operations so that we don't get that bad case that I just covered. But maybe that's too ambitious. So I'll just sort of think of what else we might do. Yeah, I guess at a high level it seems like it would probably be helpful to store additional information in the class. I'm just trying to think about what and how to organize it. So let me think quietly for a couple minutes about that.
Red Maelstrom: Sure.
Professor Squirrel: Okay. I have something that I'm mulling over, but I need to sort of like think through the details, which I guess I'll try to do aloud. It feels like some sort of binary tree data structure could be pleasant, such that we maintain a roughly sorted collection, sort of sorted by score increasing. So, so if we did that and there's the details of what to do when there's a tie of two players having the same score. But I'm sure we could figure something out. Probably we could just break ties arbitrarily, say by player id. And then supposing we did have this binary. Go ahead.
Red Maelstrom: If you look at the top expected output, it's just a sum. It does not care about whether player score you are using to score it up.
Professor Squirrel: Okay, okay. That sounds relevant, interesting.
Red Maelstrom: But I like the idea that sorting, some sense of like loose sorting could be a way of looking at it. And what are the options like? I think your priority queue is also a binary tree kind of implementation. What other binary speed you can use.
Professor Squirrel: I see, I see. I mean, I think this binary tree thing would have worked, for what it's worth. But I'll pivot. So I think it's quite reasonable to keep this binary heap in the leaderboard class. So suppose we held onto a binary keep that had size k, and maybe we cast the sum as well. So we're both storing the set of, let's say like the set of players in the top. I needed some better terminology for this, but like the leading players in some sense.
Red Maelstrom: Okay, are you aware of binary search tree?
Professor Squirrel: Sorry, can you say that again?
Red Maelstrom: Are you aware about binary search tree?
Professor Squirrel: Yes, I'm aware of binary search trees, yeah.
Red Maelstrom: Can you use that somehow here?
Professor Squirrel: That's a great question. Yeah, I mean, maybe I can combine my two thoughts. So supposing, supposing we kept a binary search tree of the, well, let me think about this, because the binary search tree is actually a pretty good priority queue, all things considered. So we could use that for the top k. Like, I guess what I'm thinking is because people sometimes get reset and they sometimes leave the top k. Like we need to collect, collectively store a collection that has all player ids, both the leading players and the normal players. And probably we'll split that into two different collections and then sort of manage the movement between the collections. In particular, when you have someone evicted from the leading collection, like a reset happens on the top kick and you want to promote someone from the normal collection, that's sort of one of the more interesting cases. Let me see. So I think, honestly, I feel that we could probably do this with priority queues of either flavor. Like these could be binary heaps, these could be binary search trees. I'm not certain it would matter tremendously. I think both would probably work, but the gist, I guess, actually this feels very simple in leetcoding. Maybe when it boils down. So maybe what we could do is have a max heap and a min heap, and the max heap, which I'm visualizing to the left, is storing all the players who are not leaders. And then the min heap is storing the k, sort of currently. Well, wait, I'm sorry. So top k. Wait a second, I'm sorry. So k isn't fixed. I need to rewind my thinking, because I've been imagining k to be fixed, and that's not the case. So let me think now. Okay, okay, okay, I'm sorry. So now that k is not fixed, it's probably a simpler approach. Using what? Wow. Okay. Yeah, I need to take another couple minutes, I think, to think, to rethink of some approaches, but I'll see what I come up with. I mean, like there, I guess this is maybe worth mentioning like.
Red Maelstrom: I haven't.
Professor Squirrel: Bothered to because it feels like it's not that much better. But we could do a binary search tree bst key by score increasing. And this would be on space for n is the number of method calls. There'd be like log factors by log factor top. This sort of almost trivial thing is like this. And like, the idea is you. Well, no, let's think, let's think, let's think. The VST needs to be augmented by the size of the current subtree. I can explain what I mean if that's not yet clear. So there's, this is not like the standard BST, but this is a BST because as long as you can find the k th largest element quickly, then you find the case. And this is up to off by one. Define the case largest element, and then add up the scores of the top k. Got it?
Red Maelstrom: Yeah. I think there exists some implementations which allows you to trade through this BST, maybe from smallest to largest or largest to smallest. That would have helped you.
Professor Squirrel: I'm sorry. Yeah, yeah. Okay. Forget the thing I said about augmented, but like go from the top down. That makes way more sense. I was kind of assuming you'd have to go from bottom up, but this makes more sense. Okay, I like that. I like that a lot. Thanks.
Red Maelstrom: Cool. Awesome. I think those are the good ideas. Let's discuss one more problem so that you have more practice. Sure. So I'm typing at the beginning.
Professor Squirrel: I feel like there's something that has. Yeah, I'll come back to this, or maybe I'll ask you more about it later, but I feel like I'm just on the brink of something better than either of these approaches, but. Okay.
Red Maelstrom: Yeah. Can you. Yeah, I'm all ears. Can you explain that? Oh, no.
Professor Squirrel: I mean, like, I don't have it. I just have an intuition. Really?
Red Maelstrom: Yeah. You can share the intuition also.
Professor Squirrel: I guess, just that it feels like there should be a way to efficiently update the data structure throughout ad score and reset such that top, basically, such that all of the operations are like constant or log. I mean, that's the goal here, really. That's what I was clawing at. And I guess. Yeah, I mean, beyond that, I think I'm not quite there yet.
Red Maelstrom: Cool. I think this is good data structure binary you came up with. Maybe there could be some way of optimizing. If it is, if you are trying to deal with in a practical sense, maybe you can bucketize these scores into different buckets and then try to just work on the buckets in the largest buckets and then, let's say buckets and then. So it will kind of reduce somehow practicality. But theoretically, you can still end up having everything in the top most bucket.
Professor Squirrel: Right.
Red Maelstrom: So, yeah, so those could be like, some way of, like, practically optimizing in the real situation. But, yeah, in a theoretical sense, you cannot, I think, like, you guarantee that that approach would be better than this one.
Professor Squirrel: So I guess just out of burning curiosity to ask you directly, do you know of an approach that has sublinear time for all three operations?
Red Maelstrom: No, I wasn't expecting even that. Okay.
Professor Squirrel: And, like, you don't know that it exists. Like, it's not known.
Red Maelstrom: Yeah, yeah, I think.
Professor Squirrel: That was all I was hoping for. I would have been quite unsatisfied. Sorry, go ahead.
Red Maelstrom: So I think, like, I was expecting, like, log n for ad score, log n for reset, and for top, it would be k log n. I was okay with that.
Professor Squirrel: Well, login. Yeah, I'm always missing log factors. All right. Yeah, you got it. You got it. Thanks. Cool.
Red Maelstrom: Awesome.
Professor Squirrel: Yeah.
Red Maelstrom: Let's move to the second question. It's again, like, based on some numbers there is, you start with one and you want to reach to the target. And in any particular step, you can either increment it or you can double it. So you have to return. Like, what are the minimum steps required to transform one to the target?
Professor Squirrel: Minimum steps required. Wow.
Red Maelstrom: Okay.
Professor Squirrel: My first thought is dynamic programming, but let's actually read the question. Playing game managers. Start with one. Want to reach target move, either add one or double. I can use the increment operation any number of times. However, I can only use the double operation. There's a limit. Oh, boy. Yeah. Okay, well, that makes it harder to write the code, but might not change the approach that much. Given the two integers return, the minimum number of moves needs to restart. Okay, well, cool. Yeah, I mean, I might as well just jump straight to dynamic programming because I have a pretty solid intuition that that's sort of what this question is contrived to.
Red Maelstrom: Yeah, and that's the right intuition. What is your recursion here?
Professor Squirrel: What is my recursion? I mean, I think dynamic programming usually pretty bottom up. Like, I'm imagining an array of solutions that for all I, from one up to an including target, you could store the number of moves required to reach that number. And then the sort of base case is like I equals one and the number moves is zero. And then the case that you care about is I equals target.
Red Maelstrom: Cool. Awesome. I'm okay with that. So let's try to write a code.
Professor Squirrel: Sure. Let me walk through again in language just like the step of how you actually compute the values in that array. I guess. Well, yeah, because there's this limit operation, which I feel like it matters and I haven't thought about yet. I guess maybe let me simplify my thinking by pretending there's no limit on the number of increments that can apply. Like in that case.
Red Maelstrom: Yeah, there is no, yeah, yeah.
Professor Squirrel: Essentially I'm saying, like, store this for now. We'll come back to it. So that's the hope. And then I guess what I would do when I saw a number is, I would say, yeah, like, how do I compute a number based on numbers less than it? Because I will fill up the array from left to right. And I would say, well, it's the minimum of. Well, so it's one plus the minimum of the number immediately to the left of it. And that corresponds to. You can add one. Good, fine. And the other option is the double the current integer. If it is an even number, you could, the other way you can get there is by doubling something half of its size. And so you could do that. And then that's a recurrence relation. It's constant time to compute at each step. So you'd end up, at the end of the day, I guess I can write this down. You probably won't be writing down, end up with. So simplify version. Let's say it's like, oh, n is the target, open space, open time. And it's like a pretty classical DP. There's almost nothing interesting about it. It's almost so simple that it makes me wonder if there's some analysis you can do to the numbers and just get some constant time thing. Am I sort of over.
Red Maelstrom: You know, I think, like there is one, uh, extra aspects of it, like, uh, there is Max doubles. Like, you cannot make your numbers double more than that much time. So, but I think, like, in terms of that is just one additional complexity. Um, because, like, then that could be like one dimension of your DP. Right? So that makes sense, not just a linear answer.
Professor Squirrel: Right, right. So I guess if we'll call this limit k. So this is the real version of the problem. Okay, limit. So the limit is on the number of doublings. I see. Then, yeah, you could do again a DT, but it would be this sort of like n by k dp. And then for all inputs, n comma, k, you'd have again, a sort of two dimensional matrix of subproblems. And then for each subproblem you could have an answer. And yeah, it's like pretty standard as well. I guess if you've done a lot of gps at least, which I've done a few in the past. And yeah, if you were doubling, you'd go like down a row or up a row, whatever, and you'd rely on a subproblem which has k minus one many quota limit. So again, details aside, like boundary conditions, so on and so forth, there's not that much sort of like meaty or interesting that I feel like I haven't mentioned, I guess, about this approach, but this is a thing, and I'll write down as well, this is like n times k space. And you can do the Dp thing where you save space by, I guess, whichever is smaller, n or k. You can, how do I say this? You can reduce space by a linear factor by only keeping around the things you actually need. Well, it would work only for k. So like, I'll say this can optimize away the k. I can definitely see a way to optimize it using the standard db space trick. Do you know what I mean by that? Is that useful? And then event this is my high level understanding of what DT for the real problems could look like. Do you have any questions for me about that?
Red Maelstrom: No, I think I'm good.
Professor Squirrel: Okay. But then again, back to the analysis like this. It's starting to look like this is a problem about binary numbers because there's all these multiplications by two. And in some sense you kind of want to, like, you want to go top down. Like why don't I just start with a large number and start dividing it by two roughly? You know, like if I look at the target input as a binary number, doubling corresponds to, in some sense, I want to do these operations in reverse. I want to decrement and divide by two, but only if the number was even. And I want to do some combination of these operations to as quickly get to one. And I didn't ask clarify it. But I'm assuming target is one or greater, otherwise the task is impossible. Is that a valid assumption? Sorry, can I assume that target is positive?
Red Maelstrom: Yes.
Professor Squirrel: Yes. Okay. Forgot to ask that earlier. Anyway, so I was thinking about doing the operations in reverse. The target's even, you can divide it, but it costs you up to this limit. And it's, dividing is always sort of better in some sense. Like you get more quickly to, to one. So I guess what I'm trying to say is I want to do something like vaguely greedy, which I haven't justified a proof of, but I have a very solid intuition that it should work, which is that I want to make it so that. Well, let me think about this in some sense, like the division by two is basically just throwing away a zero. But, yeah, it feels like there's got to be some way to look at this as a binary number and just make it work. So let's see, let's see. Maybe I'll think quietly for another couple minutes, if that's all right. Yeah. Okay. This seems like a cool problem. So I drew an example of a binary number on paper, and now I'm thinking through it. It feels like let's track some by one. Well, no, no, I'm not done yet. Hold on. Hold on 1 second. Okay. Yeah, I think I am done. Okay. So unless you've seen this before, this is going to be pretty hard to explain, but I'll try and I guess I'll use an example. So. So think of target as a binary number. Yeah. Are you with me here?
Red Maelstrom: Yeah.
Professor Squirrel: Okay, so I'll walk you through what I'm thinking about. So suppose k equals like three as an example. And so the idea here is when I use one of my divisions, which I have at most three of it corresponds to removing a zero from the end of the array. I've sort of shifted everything to the right, and I've chopped off a zero from the end divided by two. Great. And that only applies if it ends with a zero. And I'm thinking I could do that right away. Well, actually, does this matter? It feels like it makes sense to divide by zero immediately, like as soon as possible anyway. Yeah. So that's basically what I'm thinking, is doing this relay. So, like, first of all, you'd be looking from the sort of right side, I guess, the least significant bits going up towards the higher bits. You see a zero, and immediately you greedily decide that the best thing you can do right now is divide by two because you are getting the most sort of value in a vague sense that it's not made precise. And if I was trying to prove this correct, I think that would be an important property in the proof. But you think it's important to divide by two, so you do it, and that uses up one of your, one of your quota. So now I only have two remaining divisions, and then I could do it again because I think that that's a good idea. Again, unjustified. And then I see a one. And that's the goal, would be to subtract one from the one because I can't divide by two, but I'd like to. So I use a decrement operation and that counts. So again, this, like total, like numops. Numops. And then remaining is numerous. Is now two because it's done two divides. Now one because I divided twice. And then I would say this, I would turn this into a zero and I'd count that as an operation. And then I'd shift. And then I'd look at this zero and I'd shift again, but it would cost me a division. Wait, wait. Sorry. I think I counted this wrong. But basically one, two, three. After I've done three divides, there's no operations left and it's costing me four. And now at this point, I'm out of divide. So I literally just have to count. So this is a number and I have to count that much. Making me think the way to actually write this code could be made a lot simpler. Again, all the edge cases conditions are not coming to mind. But the idea is basically the number of divides you have. Yeah. Like you can, you can just sort of chop off that much of the number and you pay for each one. But besides that. And you pay for each place. Gosh, yeah. I mean, yeah. I'll take a step back now, but I guess without having figured out the details of the logic, I feel good about this approach. And if it worked, it would be very efficient. It would take log time, let's say if log is like 32 or 64, because you only have to look at the bits of the number. So it's very efficient for large numbers. I'm kind of rambling on. Is what I'm saying making sense to you or do you have questions about it?
Red Maelstrom: Yes, yes, yes, yes. No, no, I'm totally following it. Yeah.
Professor Squirrel: Okay, cool, cool. Yeah, go ahead.
Red Maelstrom: Can you write the code?
Professor Squirrel: I can try. I can try. I think I almost don't have crystal clear sense in my mind of what it would look like, but I can try. I think it might actually start with pseudocode. So I actually make sure I understand this. So let me try that first because again, there's all these boundary conditions in that cases and so on and so forth, I guess. Yeah, well, yeah, I'm trying to think of the way forward here. I'll try to write English. So, like. Yeah, okay, so I'll start with the function signature. So let's say this is sort of fewest, this is target. And we'll say it was a positive stupid number and kind of want to. Oh yeah. Then we have, yeah, I mean, wow. Wow. I guess we could start with this. Like if, yeah, let me think about this. So, so the part of the number I want to throw out, like let's say, let first section, section, it's the smaller of the, the number of bits in the target, or at least like the boy. So tricky. Okay. Okay. Yeah. Minov, I want to test in the bit length of the target. So div len of target num divs. I can write a function for that. The gist is that if the div len, this is like the position of most significant one bit plus one of x, and then I actually won't need to be saved for section line. And then I kind of want to just take the target and divide out. Let second section equals target shifted by first section. So the idea here is. Yes. To shift away all that nonsense. And then at the end we return first section cost plus second section. I think this is the general idea because the second section, you do it just naively by counting in unary or counting in binary, I guess. Counting and first section cost. Yes. So this is the hard part that's left, which, it's just the first section len plus the, the number of ones in the first section. Right. Perfect. Okay. Okay. Okay. So this is, but it's not trivial to write. So it's all this bit manipulation. Yuck. I've done this in a while. This is target, but I want to mask it with. All right, let's go. First section, target, but masked to be including a number of ones that's equal to the first section lens. So this one written code like this, that mask equals, I'm going to say one shifted by first section. Then I'll check the outcome to the same, and then all minus one, something like this, to create that many ones. Let's see if that's actually correct. So if I take one and I shift it that many positions, say it's five, I shift one, five positions, I get 50, the subtract one, I get five. One. Yeah. Okay. I'm happy with this. And the order of operations matters. The addition would happen first, but we parentheses it. So we're happy. We end it with target and we got a section. Yeah, I'm happy with this. Okay. First section cost is first section length plus, plus what? Plus first section. So it's the number of ones. There's a built in function rest for this. I could also write the function myself, if you like. And then there's a couple ways to write this. The simplest is the built in function, but I could also write it out if you like. And the only thing I haven't written down is this bitland function which x leading one largest one. Maybe it's like the binary logarithm. I actually don't know what the library function for this is, but I could write it myself. I'm almost certain it exists. Yeah. Would you like to see me write this function myself?
Red Maelstrom: No, no, I'm okay. Let's pause for a feedback. Yeah, sure. Yeah, I think in the first question. I think in the first question, I really like the way you clarified a lot of aspects about the input output. I think as an l three that is really good thing to have. I feel like most of the try to jump into the solution. I like the aspects that you kind of. I like the way you explain that log could be just a constant in terms of the integers. So yeah, I like that insight about how you think about it. I like the way you are used really good naming conventions to implement it. Yeah, I think that was, I think the implementation part was good for the first problem. I like the idea that you kind of think about in the right direction that it could be loosely sorted list of things, and then I say that can manual search to be used. I think like you were able to come up with the approach. I think like you had to miss the login factor. But yeah, I think like apart from that you were able to come up do the time and space complexity analysis for your problem. So I think like all those things were really good. Maybe you can like, yeah, but I think like l three doesn't make sense, that much sense. But if you can talk about like in what situation your first solution is good, in what situation the second solution is good, that would have been a really good signal. Let's say for example, the call to top API is very less as compared to ad score and reset. In that situation your first solution could be simple and still be better, whereas in second it could be. If there are almost similar kind of calls, then I think second solution does make sense. So yeah, I think that trade off, if you can identify that could have been a really strong signal, but at an entry level it's not that super important. For second question, I think you kind of like there could have been like one something like which you could have considered before jumping into the conclusion. I think you can solve it with a greedy whenever like because like you would like to have, you would like to double it as you would like to double the larger number as early as possible. So the simple solution could be like you are trying to move from target to one. If it is an even number and there is a max is still allowed, then you will try to divide it. Otherwise you will try to decrement by one until you reach to the one. So there is a possible way of trying to solve it using a greedy in login time, because you are kind of like going from target to the one. The reason it makes sense is like you will try to use your max, like you will try to use your operation of double as with the larger impact as possible. So it's kind of a greedy kind of a problem, but that's okay. Like, I think, like I didn't give any hint or anything, I just like the way you were thinking about storing it and those aspects, I really like those things. So I still wanted to go ahead with that. So, yeah, I think those are the few things which you can consider. So, yeah, and a high level, I think, like your communication is good. It's just like you are back in the game after some breaks or maybe some more implementations, some more thorough approach towards problem solving. That could be something like, which you can consider doing it. So, yeah.
Professor Squirrel: Okay. For sure. Out of curiosity, is this binary number approach something that you endorse?
Red Maelstrom: I think like that is, that is what, that what, that is what the DD would also be doing. Right. So, but yeah, the implementation or the articulation could have been the simpler that whenever possible divided by two.
Professor Squirrel: Okay, I misunderstood something. So you're saying, let me think about this. Like my concern.
Red Maelstrom: Yeah.
Professor Squirrel: Concern was that in the worst case, the greedy approach would take linear time, but you're saying that once the quota reaches zero and you run out of doubling tokens, you immediately you can just.
Red Maelstrom: Use the packet minus one.
Professor Squirrel: Brilliant. Yes, yes, yes, yes. That is way simpler than what I wrote. Okay, thank you. Thank you. Good, good.
Red Maelstrom: Yeah, but I think I'm happy the way you can think you can still pursue. So I think if this would have been a real interview, I would definitely have given a higher call. So, yeah, but, and then there will always be something which I can say that, okay, you could have done this, you couldn't run that. So, yeah, cool. I think, yeah, that's about this interview. So, yeah. Do you have any other questions about like your search? Like maybe I would like to understand, like how you are planning to have, how you are trying to search or apply for jobs, those things. If you need any help in that, if you want me, I would be happy to help.
Professor Squirrel: Thank you. Thanks, that's very kind. Yeah, so I did actually have a friend refer me just last week and I applied to three postings because there's a limit of three and I got rejected from all of them at the resume screen. Or like a recruiter said, I got an email basically for each of them saying, we're not interested. So I'm not sure, I guess, how do I say this? I think the sense is that on paper the years of experience number, I have very few. And so I think that I'm going to struggle to get to the point where I speak to a human being. So that's the main thing that I'm thinking about with my job search. And then I'm thinking about like how do I talk directly to actual hiring managers? Like ideally through some shared connection. Like this is the thing that I haven't yet figured out is how to get interviews in the current market.
Red Maelstrom: I think that's a good strategy. Maybe like can expand beyond like Google sometimes. Like Google, they might not be interested in rehiring the people who got laid off because they might want to hire people on a lower salary. There could be a lot of things, right. So maybe you can expand your search beyond Google. That would be one thing. Definitely. Like reach out for like recruiters on LinkedIn reaching out. I think like for grad university hired position. I think like I don't think like at least what I have seen is like usually hiring manager don't, don't specifically hire directly. I think like usually university hires, at least in my experience, get hired as a pool and then hiring managers can request and get from the pool. That's what I have seen. But there may be like at least this is how I have seen in big tech, but maybe in a smaller setup this could be different. But yeah, I think just not keep your search just for the hiring manager. You can also reach out to the computers. That could be one way of doing it. Yeah, I think here in interviewing IO, I think they have some like some way of like forwarding your resume for like some, some hiring managers who they have maybe you can reach out to support and try like explain your situation and is there any help they can provide beyond just mock interview service at least to get your foot into door? That could be one step you can do. I will also try to ask like if there are, what are the avenues available and I will provide you pseudo names and they may just reach out to you.
Professor Squirrel: Thanks.
Red Maelstrom: Yeah, I think those could be the few things which you can consider. I think I gave one I don't remember. Let me just check it. Okay. I think like code signal was something where I gave some test and like based on that test score, I think they forwarded my profile to some places.
Professor Squirrel: Okay.
Red Maelstrom: Yeah. Line number 36. Code signal. Actually.
Professor Squirrel: Yeah.
Red Maelstrom: What happened is I give screening test for Coinbase and based on the overall score of the steps they even forwarded, they asked me like if they can forward to some other companies, but I'm not sure. But yeah, maybe you can just explore it. I'm not sure whether it's. It's a full about it, but yeah, I just want you to give.
Professor Squirrel: Absolutely. I'll look into that.
Red Maelstrom: Yeah, yeah, sure. Those are the few things I can think about. Yeah. So maybe like you can expand your search beyond Google. Maybe you can ask for reference in few of the other companies. That would be the few ways you can think about. I definitely like the way of like, reaching out directly to the hiring managers or recruiters on LinkedIn. That definitely could work. One small thing which you can do is like, you can broadcast that you are open for university hiring role on a blind kind of a thing where like. Yeah, I have heard from friend of mine that he has got referral in multiple places and even the recruiters replying on applying. But I'm not sure, like if you have still have access to the blind account or not.
Professor Squirrel: If not, that's a great question. I had never signed up for blind when I was at Google, so I'm guessing I don't have access.
Red Maelstrom: I think I have seen blinds providing a way to sign up you by stating that you are impacted.
Professor Squirrel: I see. Okay. I can look into that. And then you're saying posting on blind might be a way to get contact.
Red Maelstrom: Yeah, I'm just giving, like, I'm saying, like, this is like a zero investment kind of a thing.
Professor Squirrel: Right.
Red Maelstrom: If you get something out of it, it's great. Right.
Professor Squirrel: So.
Red Maelstrom: But therefore you. You are just broadcasting it, you know, in one place, so.
Professor Squirrel: Yeah. Cool.
Red Maelstrom: Yeah, yeah, I think, like, I have seen like few, uh, yeah, temporary. Yeah, yeah, I see. Like there is a way of doing it. Uh, yeah, I am just posting the link in the chat.
Professor Squirrel: Thank you.
Red Maelstrom: I'm not like, I haven't read it through, but yeah, I was aware that they are providing a way to.
Professor Squirrel: Okay, I'll look into that. Thanks.
Red Maelstrom: Cool. Awesome. All the best for your search. I really like your problem solving and stuff. I really enjoyed it.
Professor Squirrel: Thank you.
Red Maelstrom: Yeah.
Professor Squirrel: Well, thanks again for all your help and all the pointers. This has been really helpful.
Red Maelstrom: No worries. Yeah.
Professor Squirrel: All right. Take care.
Red Maelstrom: Have a good one.
Professor Squirrel: You too.

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.