Sample Interview Question

A simulation is just that: a simulation. They want to know how you would model the problem. I.e., create classes to represent a Competitor, TournamentBracket etc.

Also, they would want you to be able to ask for missing information. For example, here, what "total time" means. Is time measured in rounds, or just what? If sessions with a different number of rounds played are merged, how should that be counted? (The final game session would likely have been merged from sessions with many different round counts.) Are sessions taking place simultaneously? If so, you could end up with a set of several sessions, any two of which could be validly combined. What rules exist for determining which ones are? Is it random?

If you just muttered something about a binary search tree, I would fail you right out. You'd show you'd missed the point completely, and also obviously aren't on the right track: there's nothing binary about the elimination (because brackets contain 7-10 people and some random number of them get eliminated), and there's no data to search for (even if building a tree made sense for the problem, the only information relevant to the actual answer would be the maximum tree depth).

This problem also sounds much like complex O(n) analysis, some parts of which might be non-trivial.

The "independent" is also a huge complication. In what order are the rounds executed vs. when are they combined. Depending on order, this might be a non-trivial scheduling problem. If these steps are performed in turn (first simulate round of all matches, then try to combine).

Finally, it depends on who is giving these tests. Answers for Google engineering position will be different from some generic IT consultancy vs. iPhone game developer.

Basically what Zahlman said, but I'll add a "partial" list of questions that come to mind immediately. Asking these questions is part of the "correct" answer. Because they aren't asking you to go sit down and code it up right away, like he said part of the correct answer is verifying that you understand the problem.

Quote:

Assume a tournament where at the start 300k people are divided into individual game sessions of anywhere between 7-10 players.

A number between 7, 8, 9, and 10 is chosen for each group, but how? Does it attempt to balance the number of people per group? For example, suppose 16 people were at the start. Should the algorithm favor a partition of (8,8) or is (9,7) acceptable?

Quote:

The game is played in rounds where anywhere from 0 to X-1 (where X is the total number of players in the session) may be eliminated from a game session.

How should the number of people eliminated by determined? Should I actually simulate each round using some sort of game, or is it sufficient to choose a uniformly distributed random number in the range [0, X-1] and then unconditionally eliminate that many people?

Quote:

Any time a game session can be combined with another game session while keeping their total players less than 10, they should be combined

Can you elaborate on this? The total number of people per session should always be between 7 and 10, so at first glance it doesn't appear that there is a valid combination of 2 sessions that can be combined to produce a legal session with between 7 and 10 players.

Quote:

Write a simulation to find out total time taken to reach the end of tournament

By "time" do you mean total number of rounds or total number of sessions? I assume rounds, since that corresponds more closely to a model of how tournaments work in the real-world -- i.e. you can have multiple sessions going on in parallel (perhaps in different arenas, rings, fields, courts, whatever).

Quote:

Original post by cache_hit Quote: Any time a game session can be combined with another game session while keeping their total players less than 10, they should be combined Can you elaborate on this? The total number of people per session should always be between 7 and 10, so at first glance it doesn't appear that there is a valid combination of 2 sessions that can be combined to produce a legal session with between 7 and 10 players.

While it is really anyone's guess, I think the idea is that after a round is played and [0..X-1] players are eliminated from a session, find another session that would complement it (7 <= |session 1| + |session 2| <= 10). That is, unless after elimination there were still between 7 and 10 players.

There are several more potential issues with wording of original problem:

Quote:

anywhere from 0

If 0 players are eliminated each round in each session, the game never ends.

While improbable, using a random generator this can occur, at least in theory.

Quote:

while keeping their total players less than 10

This is not a problem per se, but rounds start with up to, and including 10 players, but they can be combined only to including 9 players.

Quote:

don’t worry about rounds in progress

100 sessions are playing. 1 of them loses a player. We check if any can be merged - the answer is no, since remaining 99 rounds are currently in progress.

So with such wording, sessions could never be combined.

Quote:

Original post by STGBen Quote: Original post by cache_hit Quote: Any time a game session can be combined with another game session while keeping their total players less than 10, they should be combined Can you elaborate on this? The total number of people per session should always be between 7 and 10, so at first glance it doesn't appear that there is a valid combination of 2 sessions that can be combined to produce a legal session with between 7 and 10 players. While it is really anyone's guess, I think the idea is that after a round is played and [0..X-1] players are eliminated from a session, find another session that would complement it (7 <= |session 1| + |session 2| <= 10). That is, unless after elimination there were still between 7 and 10 players.

I agree, the point is just that asking these types of questions is part of the correct answer. Most of the time they intentionally leave the wording vague to see if you just blindly go off making assumptions about the problem, or if you really try to understand what to do.

The reason is obvious - if you just immediately start coming up with algorithms and data structures to use, then you're likely to do the same thing on the job as well. A week later you solve some problem and talk to the designers and rest of the team and they're like "oh, that's not really how we wanted it." Now you just wasted everyone's time and the company wasted money paying for something that was unnecessary and not even desired in the first place.