Interview Question: A two-player card game

综合技术 Musing Mortoray (源链)

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

您可能感兴趣的

Revisiting Stress Majorization as a Unified Framewo... 作者:Yunhai Wang, Yanyan Wang, Yinqi Sun, Lifeng Zhu, Kecheng Lu, Chi-Wing Fu, Michael Sedlmair, Oliver Deussen, and Baoquan Chen 发表:2017 TVCG (Inf...
Empire Problem 上周以前大学同学分享探讨了一个编程问题,觉得还是挺有典型意义的(解法与题意理解上)。故在此记录下。 Problem The empire has a capitol and a number of cities. Some cities are connected ...
Edward Z. Yang: Semantic Import Versioning in the ... The best and worst thing about semantic import versioning is that it makes BC-breaking changes hard. In the past few days, Russ Cox has made a spla...
POV Display is FAN-tastic Persistence-of-vision displays come in all shapes and sizes. But when you get a couple of students involved, well let’s just say they tend to up the...
No, Nanomsg is NOT dead There seems to have been some pretty misleading data out on the Internet, indicating that " nanomsg is dead". The main culprit here is a " pos...
责编内容来自:Musing Mortoray (源链) | 更多关于

阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » Interview Question: A two-player card game



专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录