A Circular Dilemma Concluded

Thursday, March 26, 2009

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.

Whiteboarding the Google O.S.

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 solutionin 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:

  • PokerSeat.Table
  • PokerPlayer.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... 

A rectangular table

...into this: 

A circular table

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:

  • PokerSeat.Left
  • PokerSeat.Right

This gives us the ideal data structure for representing a poker table in code: an array-bound, doubly-circularly-linked list. 

The array-bound, doubly-linked circular list in action

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.

 

Tags: OOA&D, online poker, poker

13 comment(s)

"The circle is the fundamental geometry of poker."

A circle is not a geometry. Though it can be described by one. Please speak with precision.

On the other hand, the segue from Seat.Left/Right to your array bound concenctric quadruple was some of the more brilliant OOA&D I've seen, at least when it comes to the subject of poker. I completely 100% intuitively agree with everything you say.

Heh, a circle is a [url=http://www.answers.com/geometry]geometry[/url], actually.

Nice article. I think you nailed that table data structure.

""The circle is the fundamental geometry of poker."

A circle is not a geometry. Though it can be described by one. Please speak with precision.

On the other hand, the segue from Seat.Left/Right to your array bound concenctric quadruple was some of the more brilliant OOA&D I've seen, at least when it comes to the subject of poker. I completely 100% intuitively agree with everything you say."

So you agree that a circle is the fundamental geometry of poker ? If not then don't you think you should "speak with precision" especially if you're going to critasize someone else for the wording they choose.

Loved the article.

Ridiculous. PokerTable.BeerHolder and PokerSeat.MassageGirl are the two properties that would best improve the design.

Obviously.

Quadruple-ply!. Lol. I think I actually understand what you mean. I was doing some work on this last year.

  • One ring for all seats.
  • One ring for all occupied seats.
  • One ring for all occupied seats containing a player not sitting out.
  • One ring for all occupied seats containing a player actively engaged in the current hand.

Four rings = quadruple-ply. ;-)

Do I get a no-prize?

"Ridiculous. PokerTable.BeerHolder and PokerSeat.MassageGirl are the two properties that would best improve the design."

Made me lol. Fascinating blog post again, mate.

I'm rewiring my poker table even as we speak...

One of the better articles I've read here. I liked how you explained why some of the best submitted ideas were good, but not best fit. Too often I see writers dismiss incorrect ideas without an analysis of pro/con. Keep up the good work.

I think the best solution would be to take each seat, create a GUID, then insert it into a hash. Then, lexically compute a word such that the distance between players is an integral sum of the Haldebert function in s-dimensional hypercube space, interpolating linearly of course, and superimpose that on a relativistic probability space in which the Eichenberg constants have been shifted.

A trampoline, if you will.

Oh and I agree. A circle is definitely a geometry and the meaning of the sentence is clear.

This is actually a great interview question. I found your blog through StumbleUpon and I won't be building a poker bot, but I do think we'll add a couple poker-related questions to our list of interview questions. Shuffling a deck of cards is another great one. Jeff Atwood (who I notice you link to occasionally) has a good post on this:

http://www.codinghorror.com/blog/archives/001015.html

So... I was right with the properties... he, he... Now, when is the next intallment. Will we have to wait another 3 months? Any details about that job in PokerStars? LOL

Use the form below to leave a comment.






Coding the Wheel has appeared on the New York Time's Freakonomics blog, Jeff Atwood's Coding Horror, and the front page of Reddit, Slashdot, Digg.

On Twitter

Thanks for reading!

If you enjoyed this post, consider subscribing to Coding the Wheel by RSS or email. You can also follow us on Twitter and Facebook. And even if you didn't enjoy this post, better subscribe anyway. Keep an eye on us.

Question? Ask us.

About

Poker

Coding the Wheel =
Code, poker, technology, games, design, geekery.


Hire

You've read our technical articles, you've tolerated our rants and raves. Now you can hire us anytime, day or night, for any project large or small.

Learn more

We Like

Speculation, by Edmund Jorgensen.