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:

• 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.
• top(K): Return the score sum of the top K players.
• 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? Yes
• 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 designed 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.
• Your 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 optimized your implementation.

Overall: I feel you did solid in this interview and I would have given a hire call.

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. ... Professor Squirrel: 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 adScore 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. 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.

[Feedback about the interview and potential job search advice continues...]

Problem 2: Integer Target

...

Conclusion

• 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.

All the best for your job search.