Editorial

Interview Question: A two-player card game

I’ve been asking interviewees, over at interviewing.io, to write a simulation of a two-player card game. It’s an engaging question, revealing a lot about their abilities. It doesn’t involve any trickery nor random algorithm knowledge. It’s suitable for programmers of any skill level and works in all common languages.

I’d like to share the question and some of the insights I’ve had.

Two Player Card Game

I introduce the question with a preamble about being focused on the design and structure of the code. I don’t need to have a running program, but need to see an entry point and how it would be used.

Here is the description of the game simulation.

  • this is a two player card game
  • the game starts with a deck of cards
  • the cards are dealt out to both players
  • on each turn:
    • both players turn over their top-most card
    • the player with the higher valued card takes the cards and puts them in their scoring pile (scoring 1 point per card)
  • this continues until the players have no cards left
  • the player with the highest score wins

It’s considered a simulation because the players don’t have any choices to make. We don’t need to worry about input.

There are unanswered questions in this description, or perhaps some abiguities. Some of them weren’t intended, but it’s worked out well. Candidates must identify and resolve issues in the requirements.

Based on this description I’m expected the person to write code that simulates the game: writes out who wins from one round of play.

Design

The interviewee asking questions is good, but not necessarily revealing. I expect some feedback that they’ve at least understood the problem. Beyond that I’m flexible, having seen several different styles of solving the problem. The only definite pattern I’ve seen is a negative one with over-design: trying to plan for everything and writing extensive notes. If people are taking too long here I prompt them to start writing code.

The complexity of this problem doesn’t require much prework. Beyond coming up with a couple of classes, like Player and Game, possibly Card, you can start writing code. The best approach, used by many well-performing candidates, is outlining the structure in actual code. Code is often the best pseudo-code: just leave out details and take short-cuts as you’re planning.

The Cards

Several candidates start working from the bottom up: taking a deep dive into what defines a card, or creating a Deck class. I ask them why they are building these classes, as a hint it’s not a good approach. I encourage them to think at a higher level, about what they might actually need.

Especially in a time-limited scenario, it’s best to think top-down and ignore details until you need them. That is, don’t design all aspects of a theoretical Deck class as they may not be used. It’s okay to sketch out classes, placing some variables, but the details should be sparse.

I avoid giving too much direction at this point; being able to structure a problem in code is an essential skill of coding. I reserve my comments to when I feel it’s going very wrong and the approach will not let them finish the task. If they feel confident and making progress, I try not to enforce an ideal view, instead I let them go with it.

One critical question that should arise, probably during design, and at the latest when comparing cards, is what type of cards we’re dealing with. Not everyone is familiar with standard playing cards, which is fine; they ask what type of cards these are. Others assume suited cards and ask how to compare suits. In all cases I simplify the requirement to just be a set of numbered cards, from 1 to N. With this requirement it’s acceptable to not have a Card class at all, instead just using an integer. Though, there’s nothing wrong with a trivial Card type either.

Regardless of the choice of integer or class, it’s important I understand why this decision is being made. In particular, I expect the candidate to tell me why they’ve chosen one or the other. The code should also be clear. A variable like int[] array is not helpful (yes, this happened once). Name things for their logical value, such as deck.

The game progress

I mentioned the programming should be top-down. After the initial design period, and some code sketching, I’ll expect the main sequence to be written. I want to see cards dealt out, the turns being taken, and the winner declared.

Starting with a rough structure then filling in details is good. My experience so far is that people who don’t start at the high-level have a hard time finishing the problem.

defn play_game = -> {
    deal_cards()

    take_turns()

    declare_winner()
}

Given the simplicity of the problem, it’s also acceptable code each of these directly in the function, provided it can be refactored into functions afterwards. Whether the interviewee initiates this refactoring, or I have prompt for it, seems to reflect on their experience level.

The importance of top-down design is echoed in processes like test-driven development and the concept of YAGNI “You aren’t gonna need it”.

Common issues

From here it’s a matter of filling in details. This question has a lot of small things to take care of, none of which are tricky, which is good for an interview.

The Player class

A common mistake is the failure to identify a Player type. We end up with this pattern of coding:

vector<int> player1_cards, player2_cards;
int player1_score, player2_score;

A series of matching variable names, like player1_* and player2_*, is a good indication that you should have a Player type. Most candidates come to this conclusion their own, either starting with a Player class directly, or refactoring it. Others require some prompting but usually understand quickly. A select few just didn’t comprehend and needed explicit instruction.

Prompting people, without just giving away an answer, is difficult. In this situation, I like to try things like; “look at those variables starting with player1 and player2. Do you see a pattern there?”, “Is there some structure you can use to abstract this?”, or “Couldn’t you group this better somehow?”.

Arguments and Member variables

There should be some Game class managing the simulation. The name isn’t that important, but it should contain the players and the functions for each phase of the game. Here the candidate’s ability in OOP is tested.

Member variables replace the need for repeated arguments to functions. The functions should all be passed the players, scores, and cards as arguments, but instead, the players should be part of the instance. Some people immediately do it this way, others require a bit of prompting.

The player details are almost always best as member variables, but there is some variation on how to handle the initial deck and dealing.

Again, prompting appropriately is not easy. I try things like “Is it necessary to pass the players to all the functions?”, “Is it possible to avoid this redundancy?”, or more directly, “These feel like the players belong to the class.” Honestly, I don’t remember the specific things I’ve said, but the key is to start general, almost mysterious. How much I need to say, and how explicit it needs to be, reflects a lot on the skills of the interviewee.

Magic numbers and details

There aren’t too many involved in the code, but I don’t like seeing them. For instance, a loop that runs from 1..52 to create cards uses a magic number. There’s also a 2 that comes up when adding to the score: it’s a bit more subtle, but relevant for the extended questions I have planned.

It may seem like a trivial detail, but I’ve noticed that better programmers are attuned to such things. They will create a constant, use an argument to a constructor (possibly with default), or just say, “Yeah, this isn’t good, I should clean it up after.”

By this time I usually have a good idea of how well the person knows the programming language. Comparison to natural language seems fair, some people seem to speak fluently and the code flows consistently and cleanly. Others seem to be stuttering, forgetting words, translating in their brain, and the code is less eloquent.

Though people that use advanced syntax fair well, people have also completed the question using nothing but basic imperative syntax as well. Real struggles though aren’t acceptable: the candidate gets to pick the language, so there’s an absolute expectation of basic knowledge.

Extended Questions

If the interviewee has solved the base question and we have at least 10 minutes left I’ll add the next requirement:

  • Extend the game to support more than two players

How many changes this requires depends on the initial approach they’ve taken. If they didn’t come up with a Player class, I’ll request it. I’ll also request refactoring into functions if they are a bit sparse. The code needs to be in a good state. Otherwise, this new requirement is too daunting.

By rough estimation about half of the people make it to this question. That makes it a suitable criterion for filtering: I tend not to pass people that can’t solve this extended question. I make allowance for new grads, but not for people with industry experience. I often won’t ask this question if I estimate they won’t finish it, or sometimes I propose to extend just one function. I prefer to end the interview early than add additional stress.

More Issues

The change to N players introduces a few new problems:

  • Dealing cards can no longer be done with an if-else to choose the player. I’m kind of surprised at how many people do not know how to use modulus % to select items from an array in a loop.
  • Picking the highest card from a list is no longer an if-else. It challenges some people as they know how to get the maximum value, but not always the index of that card.
  • The loop to decide if the game is over is now non-trivial, especially as players may not have the same number of cards. I noticed that better programmers naturally create a helper function, or otherwise avoid complex conditions in a loop.

The programmer’s knowledge of the language seems to play a significant role here. Individuals that are comfortable in their language have an easier time doing these changes. It has been especially true of the candidates that know Python well, as there are great constructs to make this easier.

Completing this question is a positive indication that the interviewee is indeed a good programmer or at least a good coder. I don’t even care if they had minor issues in the refactoring, but usually, they don’t. It’s a curious pattern, the people that make it this far tend not to have difficulties with this question.

Super Bonus Question

Should the interviewee manage to add N players support, I still have one additional change. It’s a bit more challenging than the previous requirements: “don’t assume the cards have unique values”. The details are:

  • Remove the assumption that the cards are unique (that is, go to a standard deck)
  • If players have the same valued card, they draw an additional card, repeat until one has a higher card
  • The person with the highest card takes all the cards, scoring one each
  • Only the players that tie continue drawing cards (1+ players may sit out on the additional draws)

Only one person has made it this far, setting the gold standard for this interview question.

Only the time pressure

What I like about this question is that it lacks any trickery or random algorithmic knowledge. The pacing seems to work well: interviewees manage varying degrees of the problem. Given the difficulties I’ve seen people have, it seems to test a good cross-section of abilities.

As interview practice, try coding the answer. Pay attention to which bits cause you trouble, and watch how long it takes you.

Categories: Editorial

Tagged as: , , ,

9 replies »

  1. If the only observable program behavior is a printout of who won the round, I’d solve this in just one line of code:

    printf("Player %d won\n", 1 + rand() % 2);
    

    In theory, an incredibly clever compiler could reduce the program to something this simple.

    • Hee hee, yes. I’ve had some clever solutions for dealing, but never the entire game. I can usually add more requirements that negate the clever solution. I can request the score be printed out as well. Or I can request each card be printed as dealt (like emitting events to a UI).

      Or, for you clever language types I can just request the rounds results are written to a volatile structure. :P

    • Yeah, a draw would be a good way to prevent that. And if Chris adds a ternary random condition then I could ask him to prove whether the rates of outcome are the same as if the game way played fully.

      Technically the `% 2` also wrong, should RAND_MAX not be even it would assign a slightly higher chance of player 1 winning.

      :)

  2. So. For me it’s all about manipulating sets of cards, and Set can be referred to as a Deck. A deck can be shuffled, dealt (returning a group of smaller deck) or cards can be transferred from one deck to another (dealing would use that). A play has 3 “decks” (pile is a good name too). Play, visible and score. You transfer 1 from play to visible, do the matching, then transfer all the cards in the visible decks to the winner scoring deck.

    Final scores are calculated by counting the score decks / piles.

    But… that’s just me.

    • Seems reasonable. I’m lenient while giving this question. If your solution looks like it’ll work and you seem confident I’ll let you run with it. It’s when people start getting stuck, or fail to account for important details, that I direct them to a known solution that works.

      Interesting that you chose a scoring stack. Very few, perhaps 2, have actually tracked the scored cards. It’s almost always been simplified to just a score value earlier in the process. I think this usually happens since many people were getting confused about players having two decks, instead putting the winner cards back into a single deck. So I probably instigate the simplified approach too early.

    • Had a similar interview question for my current job. I guess from doing a lot of Perl and other functional type languages I tend to just think of it as a lit problem. Decks are lists, you’re just moving items between the lists.

  3. This sounds like a variation on the card game ‘War.’ I guess one problem with it as an interview question is that it’s a pretty common programming exercise. I remember doing it years ago to teach myself test-driven development. I think it’s not so easy to come up with an exercise that has the nice qualities you describe but also wouldn’t be well known though.

    • Very few of the people I’ve interviewed appear to have solved this problem before. Unfortunately many of them appear not to have solve a related problem before either. There’s a fair number of people that I reject based on this question.

      I don’t think I’d have a problem coming up with variants that people for sure haven’t encountered — and I likely will should enough people read this article.

      Even if somebody does know the question, there are a lot of details that come up. How do they name things, how well do they know their language, etc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s