raganwald
(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)

Tuesday, January 30, 2007
  Please design a deck of cards in Java


Dear Future Colleague:

I’ve been asked to perform a quick technical evaluation of your résumé before we ask you in for an interview. You obviously have the right kind of experience and I’m looking forward to meeting you soon.

We are asking all candidates to perform a little exercise before coming in for the first meeting. I realize you have a great deal of relevant experience, so this will not take very much of your time at all.

And I’m sure you appreciate the fact that we value ability and merit above certifications and other pieces of paper.


Please design a deck of cards in Java

Imagine that we are writing a casino program. We are not going to write the whole program right now, just the part of the program that has to handle the decks of cards to be used by the rest of the program.

If you are not familiar with the kind of cards used in European card games (like Poker, Bridge, Blackjack, Crazy Eights, Rummy, and so on), please write back and I will give you a different problem. You should be comfortable with concepts like the ranks of the cards, the suits, shuffling, and dealing.
Your task is to design the interfaces and/or classes we would need for the deck(s) of cards. At a bare minimum, your classes should handle everything we need to know about decks of cards, the cards themselves, and operations on decks of cards like shuffling, dealing, removing cards from a deck (some games have one or two jokers, some don’t, some only use the cards from 9 and up, some from 7 and up, some use them all), and combining decks (Canasta uses two, four, six, or more decks of cards with jokers!)

You do not need to worry about the mechanics of games like hands of cards, ranking Poker hands, knowing about Trumps or Bowers (as in Euchre and Bridge), discard piles (as in most games), or melds (as in Gin, Rummy, and Canasta). Imagine that other people will write all of that stuff using your classes for decks and cards.

Please be specific about the interfaces, abstract classes, and concrete classes you will need. There is no need to actually write the bodies of methods, but please be specific about what the methods are called, what parameters they take, and what they return (if anything).

I am especially interested in the relationships between the classes. Although you don’t have to write out each method, if you expect that a method would call other methods in your design, please say so.

For example:

class Deck {

// calls Card.arrangeRelativeTo(Card othercard)
public void shuffle () { ... }

}


You can see that in this hypothetical design cards have some ability to arrange themselves relatively to each other and I am documenting that Decks can be shuffled and they use the Cards’ arrangeRelativeTo method to do so. Obviously, you don’t need to follow that design. It’s just an example.

This extends to constructors. Does creating a Deck create Cards? Or does it use Cards that already exist? Or are Cards not even objects but are represented by primitive types?

About UML

You can just write out the skeleton of the classes and interfaces. If you prefer to use UML, be my guest. As long as your design answers all of the questions I have, use whatever notation you prefer. Just don’t fall into the trap of letting the notation drive the design: just because a certain type of UML diagram doesn’t indicate the CREATES-A relationship, that doesn’t mean you shouldn’t add it: what’s important is the design, not the document.

Requirements?

Feel free to email or call with any questions you might have about requirements. This is not meant as a test of your ability to read my mind about what I want or to ask insightful questions. So, it’s ok to ask me questions. If you have a choice to make, it’s also ok to just decide.

For example, you might wonder how to represent which cards are left in a deck after dealings some out. Should you use a standard OO pattern like a List or Set? That might be fine if our Casino program is a single-user game. But if we are running a web-based virtual casino with many thousands of users, performance might be important enough that we consider using something like a bitfield for each deck.

If you want, you can ask what’s more important. Or you could just decide for yourself. Using a bitfield for performance is a fine decision. So is having a standard OO design. Each works well for a particular set of requirements.

So don’t be too concerned about asking a million questions. I just want to get a basic idea of your comfort level designing OO software.

Thanks,




Reg Braithwaite

p.s. This isn’t a trick question. There’s no right answer, and as I said above I don’t even expect full implementations, so you don’t even have to write code that compiles.

There is absolutely no need for a bunch of stuff I didn’t ask about, like requirements in three-ring binders or JUnit test cases. I know that you are probably tempted to show off your depth of experience and SDLC knowledge, however I really only want to know how you would approach the design in this question.

Please save the other stuff for the interview. Just because I don’t need to know about it right now doesn’t mean I don’t agree that it’s important!

Labels: ,

 

Comments on “Please design a deck of cards in Java:
Vorlath says:

What's the point of this post? Are you looking for people? I feel sorry for anyone who'd try to do this in real life. My reasons are below.

I've already done this many times in both Java and C++, and Java was so slow that we had to rewrite the entire server in C++. The client stayed in Java (although we would have rewrote it too if we had the time and resources).

On the server in C++, having a class for every card was ridiculous for memory usage and speed. For Java, memory was the main problem. Getting it to just run was a hassle so I have no idea if this would even be possible.

This isn't to trash Java. It's just that certain tools just don't work. It was a costly mistake. The gaming industry is plagued with Java servers that are slow and unresponsive. I know, I've been in direct contact with some of them internally. Most can't handle more than 2000-5000 users max per machine while a C++ server on Linux can handle 100,000 users only limited by RAM and bandwidth. If you want performance, you can't use Java. I know. It's supposed to be a rumour that Java is slow. Well, when you're faced with reality, I couldn't care less what's rumour and what's not. I'm only interested in results and Java doesn't cut it. Go on almost any gambling site. They're slow and crash all the time and they're written in Java.

There's no point in writing interfaces unless you expect cards to change sometime soon which they haven't done in centuries. Sure, anything can happen, but then the games would change too and the point would be moot.

Use a standard container for your deck. You can use a wrapper class if you wish. The container should just hold integers.

In C++, you'd overload the [] operator, but in Java, you'd use a method like FetchCard(int index) (and you need a FetchTopCard() to grab the top card when dealing and Shuffle() obviously). You'd perhaps want to have it return a class when returning a card so as to get what rank and order it is as long as you're not creating a class for every card all the time. I still recommend using plain integers with a static Card class for fetching rank and order. Your base Deck class should have constructors where there are no cards in it and derived classes for each kind of deck you want to create. Merging decks should just be a method to add lists of cards (maybe using some protected methods).

Although you didn't ask for it, the important part isn't the deck. It's the game rules engine. You don't want to be duplicating the game rules for every deck. The memory aspect would be ridiculous. You use a single class for each game rule (one for each thread if you're doing that) and you need to pass to it a gameroom class that contains the state of the game including the cards in play. It's not just about the deck, but what cards the users have and what the community cards are (as well as burn cards). The game rules is where you need a standard interface, not the deck of cards. You want to be able to plugin any game rules you want without the rest of the server being the wiser.

Inside your game rules classes, you can use this library for poker http://gnui.vlsm.org/directory/poker-eval.html It's ridiculously fast for comparing hands.

I realise this isn't quite OO and more like the 70's style helper libraries, but it's SO much less hassle. The reason is that a deck of cards is not a "worker" where you should ask it to do something. Rather, it is "acted upon", so the commands should lie elsewhere. More specifically, the commands should lie within the game rules engine. Helper classes are useful for common tasks. So without knowing HOW the cards will be used, it's a very common thread in OO where interfaces and classes fail to provide acceptable functionality.

For example, paper is not something you ask it to fold or burn itself. *You* do the folding and burning. And there's no possible way you can think of everything you can do with paper. Someone will always come up with things you have never dreamed about. Cards are no different.
 
Vorlath:

What's the point of this post?

It's an exercise for getting a general idea about someone's OO modeling approach.

There is absolutely no requirement that the result be appropriate for an on-line casino application. As I mentioned explicitly, if you want to think about real-world requirements, that's fine, and it's also appropriate to ignore them.

Thanks for sharing some of the real-world requirements and your experience. I'm not surprised that Java servers, especially those written from a pseudo-pure OO perspective, were ineffective.

I can think of a few domains where objects are absolutely the right way to go, and many more where they are not (it is a surprise to most people who have read about the "OO revolution" in business applications, but many business applications are not particularly object oriented!)

Why pick cards? Just because most people know card games well enough to make this a design exercise and not an explaining the requirements exercise.

As I mention, it's ok if you want to design something with realistic requirements in mind. It's not worth extra nor is it worth less.
 
Voriath, I think you missed the point by, oh, 500 miles or so...
 
"I can think of a few domains where objects are absolutely the right way to go"

...or so you think.
 
"I can think of a few domains where objects are absolutely the right way to go"

...or so you think.


That's tautological!

But in any case, I am quite comfortable keeping OO in my toolbox. It's not the only tool in there. It isn't the shiniest, nor is it the one most used: it's surpising how little of what I do is really OO.

But I'm not throwing it out just yet.
 
Vorlath says:

"Voriath, I think you missed the point by, oh, 500 miles or so..."

Comments like this without any reason serve only to be contentious. They're not even wrong.

There was suggestion for an online Casino software. I offered why Java and deck of cards might not go so well together. And I guarantee that the original server was written in Java by others who are far more well versed in OO than I am. I also showed that Java not working in Casino software is the norm, not the exception. I realise it's just an interview question, but I'd be making things up if I disregarded the premise given. Making things up when they don't work in practice is useless.

However, I did point out where OO would be useful in an effort to perhaps formulate a better interview question. I still use OO. I just don't use it on things that are "acted upon". People who use OO seem to want to encapsulate everything in sight even in cases where this should not be done.

My purpose wasn't to answer the interview question, but to show why it's a trick question. You have to assume the impossible in order to make it work.
 
Shuffling is one of my favorite tricks.

At first glance, you'd probably write a function that picks two random positions and swaps them... then run it a bajillion times.

The way I do it is to assign each card a random number, then sort the deck.
 
I'd just like to point out to Vorlath that the suggestion that a static part of code for a class like the rules engine would be duplicated for every instance is preposterous. This isn't 1975, our OO compilers have advanced a little bit.
 
There's nothing preposterous about it. It's a design issue. If you have threads, they can't all be using the same class. So if your compiler assumes it's static, it'd be wrong. You can create wrapper classes for each thread to use the rules engine as long as it's built to supports this mechanism (re-entrant). Oddly enough, it's a 70's style solution that still works wonders. For you patterns buffs, it's called dependency injection with SoC. Last I checked, compilers still aren't psychic, so you have to tell it what you want.

Trust me, the compiler will do very little for you in this case. If it did, everyone would be doing it (without it crashing all the time).
 
# posted by Anonymous : 9:39 AM
Shuffling is one of my favorite tricks.

At first glance, you'd probably write a function that picks two random positions and swaps them... then run it a bajillion times.

Why not just use the Collections.shuffle() method on the list (vector, arraylist or whatever) of cards.

It "traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive."
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /