When I was asked to design a simple poker object model almost ten years ago, I knew it was one of those interview questions. Employers often have a handful of pet software problems they like to unveil in order to stress-test a candidate’s design whiteboarding skills.
Producing a coherent design on the fly, under pressure, for a critical audience, is one of the most difficult tasks in programming. In How To Interview a Programmer, Bill Venner quotes guru Scott Meyers on the subject:
I hate anything that asks me to design on the spot. That’s asking to demonstrate a skill rarely required on the job in a high-stress environment, where it is difficult for a candidate to accurately prove their abilities. I think it’s fundamentally an unfair thing to request of a candidate.
I agree: it’s unfair, and that’s precisely why these questions are so effective. If you want to simultaneously probe a candidate’s familiarity with building software, his ability to think on his feet, and the eloquence with which he expresses and defends his ideas, just present an open-ended software design problem and ask for a solution—in the space of a few minutes.
Anyway: in over sixty programming interviews, I’ve been asked exactly two poker-related questions. One had to do with shuffling a deck of cards correctly—actually a non-trivial proposition. And the other was the PokerTable-PokerSeat-PokerPlayer triangle I posted last month. My initial response was an eloquent summation of software design best practices:
Uhh…two properties? As in, 2? You mean, like, properties on one of the objects? Like Player.Name or something? Hmm. Hey, did I mention I play a lot of online poker? [stalling] Yep, and I’ve been putting together a poker codebase [weaselling], let me tell you a little bit about that…
But when I posed this question last month, some of you stepped up with solid answers.
- Add code to enforce the multiplicities.
- Decouple the classes through Observer or some such Go4-ish construct.
- Change the access level of things.
- Add a whole host of properties.
- Remove/introduce classes.
- Scrap everything.
These are all worthy responses. You’d want to do due diligence on all these and more, especially if poker tables and poker tables are the sorts of things that are crucial to your business. But when it comes to the interview room: sometimes you’re better off attacking the question, rather than the design pointed to by the question. Sometimes you’re better served by being cagey, even cunning, looking for clues in the structure of the question and the way it’s presented to you. Your job as interviewee is not necessarily to produce the best possible design—that will come later, after you’re hired—nor to blow them out of the water with your technical prowess. Sometimes your job is just to give them the answer you think they’re looking for, using all the information at your disposal.
And the most important piece of information in the entire problem, its single most interesting feature, is the word two.
What two lines of code—what two properties—can we add to this code in order to best improve the design?
This wording didn’t just fall out of thin air. Whoever framed the question specifically said two. Now, why would they do that? What sorts of things in programming come in twos? Well, lots of things.
- Creation and destruction
- Getters and setters
- Parent and child
- Loading and unloading
But they specifically called for two properties, attached to one of the classes. This is another piece of evidence, because in programming, a property is a very specific thing:
In some object-oriented programming languages, a property is a special sort of class member, intermediate between a field (or data member) and a method. Properties are read and written like fields, but property reads and writes are (usually) translated to get and set method calls. The field-like syntax is said to be easier to read and write than lots of method calls, yet the interposition of method calls allows for data validation, active updating (as of GUI visuals), and/or read-only ‘fields’. That is, properties are intermediate between member code (methods) and member data (instance variables) of the class, and properties provide a higher level of encapsulation than public fields.
So whatever answer they’re looking for is going to involve attaching two properties to one of the classes. Furthermore, technically speaking, properties are supposed to be lightweight. That is, a property is typically a thin wrapper around an underlying piece of data. Retrieving or setting the value of the property ideally shouldn’t take too much time, involve too much work, or have side effects. The Microsoft Design Guidelines for Developing Class Libraries has the following to say about property design:
Properties are used like fields, meaning that properties should not be computationally complex or produce side effects.
So we’re looking for two lightweight properties. One popular idea was to modify the PokerSeat and PokerPlayer objects by adding a reference to the table:
I agree that one or both of the above properties should exist. A given PokerSeat belongs to exactly one PokerTable, so for convenience’ sake we should allow navigation from a PokerSeat to a PokerTable. Similarly, it makes sense that we should be able to take a given PokerPlayer object and figure out what table he’s currently sitting at (of course, as one commenter noted, a given PokerPlayer could be seated at multiple tables if we’re dealing with online poker).
The problem is that both of the above properties are convenience properties: they don’t fundamentally improve the design. Nine times out of ten, you won’t really need PokerSeat.Table at all, because whenever you find yourself working with a PokerSeat object, you’ll already have the table. PokerSeat.Table and PokerPlayer.Table are implied. They’re in the context. It’s hard to imagine a situation in which you’d be working with a PokerSeat object in code, without knowing the PokerTable to which it was attached. Why? Because to get the PokerSeat, you’re going to have to access the PokerTable.Seats collection. There’s your table.
I’d go ahead and add the property anyway, as I like to have explicit navigability even if I don’t need it. But it’s not the answer to the question, or rather, it’s not the best-fit answer to the question.
In these pesky interview situations, we sometimes have to distinguish between designing on the merits and designing to suit the question. It’s hard to say which answer is best in an absolute sense, because we weren’t given much information. But there’s a very clear and convincing answer relative to the question: one that stands head and shoulders above the rest.
And by way of introducing that answer, I’d like to ask you how you’d go about transforming this…
The PokerTable.Seats collection is a linear array. But a poker table isn’t a banquet table, and poker seats aren’t arranged in a straight line from left to right. A poker table is circular, and seats are inscribed in that circle. The circle is the fundamental geometry of poker. And the design as given breaks that geometry in a fundamental way; it severs the circle.
Luckily, we can repair it by adding two simple, lightweight properties to the PokerSeat class:
This gives us the ideal data structure for representing a poker table in code: an array-bound, doubly-circularly-linked list.
It’s array-bound because we want to preserve a notion of each seat’s absolute ordering.
It’s doubly-linked because we want to navigate the table in both directions along the axis of motion.
It’s circular (the tail connects to the head) because we want to normalize our iteration code such that we never have to worry about wrap-around (also known as what happens when you try to graft a circular interaction onto a sequential data structure). By using a circular list , we can remove seats from that list at will, as players fold, sit out, or bust out, and we avoid the following sorts of checks:
- Is there a seat in position X of the array?
- Is there a player in the seat?
- Have we bumped into the end of our PokerTable.Seats array? If so, start back at the beginning.
It’s also circular because, even though we’re all accustomed to treating the seat to the left of the dealer tray as Seat 1 (Seat 0, for you programmers), an abstract poker table has no notion of a “first” or “head” seat. Each seat exists in a circular continuum.
Do you see the benefit here?
Because ultimately, the poker-table-as-a-circle paradigm will lead us to what is (in my opinion) the ideal way to represent a poker table in code: by using a funky data structure I like to call an array-bound concentric quadruple-ply doubly-circularly-linked list. I’m not even kidding. Circles, within circles, within circles, in a way that would satisfy Euclid himself…sheer craziness.
But that’s a story for another time.