Sign in to follow this  

Sample Interview Question

This topic is 2845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was doing some brushing up on my programming interview skills and was going over various sample problems. I found one that talks about tournaments and was wondering how you would go about solving it. My initial guess at first glance is to use a modified form of a binary search tree, but I'm not sure if that is correct or even the right place to begin. Here's the problem: Assume a tournament where at the start 300k people are divided into individual game sessions of anywhere between 7-10 players. 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. Rounds in one game session are independent of rounds in other game sessions. Any time a game session can be combined with another game session while keeping their total players less than 10, they should be combined, don’t worry about rounds in progress for this problem. Write a simulation to find out total time taken to reach the end of tournament i.e. only one game session is left and it has only one player in it.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 2845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this