Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

I have a thing against “design” interviews. It’s not that I don’t want to see candidates design something, but I often think a full interview of talking about design has a tendency towards false positives. Design is hard. Recognizing good design is an art form. Art is subjective. Everything about interviewing is subjective, though, including my opinion that design interviews can easily fall into false positive traps. I think my general feeling is that the insights that can be found while working through a design problem can also be found when working through a tough data structures and algorithms problem. I’m probably wrong, though, so we’ll play this one by ear. Here’s a design problem that I ultimately want to shape into a data structures and algorithm problem that involves writing code. The reason for this is because technical interviews should always involve writing code, or else they’re just polite conversation amongst people who like (well, we hope) using computers. Here’s the initial problem statement: “Design a deck of cards.”

Before We Get Started

First off, there’s a little bit of a problem with this question. Not everybody is aware of what a deck of playing cards is. Not kidding. You will interview somebody who has never worked with a deck of playing cards before. Ask yourself before you ask the question “Can I accept the risk that I may need to spend a few minutes explaining playing cards to a candidate?” If you can afford that time in an interview slot or if you want to use the candidate’s knowledge of playing cards as a screening mechanism, please continue.

Beating a Dead Horse

I’m not quite ready to abandon that last point, as it is a subtle illustration of a less subtle type of interviewing quandary. Here are some genetically similar problems that I may eventually explore in further posts:

  • Design Poker.
  • Design Chess.
  • Design Go.

It has to be assumed, when asking a question like this, that the candidate is completely unfamiliar with the problem space. Just because you, the interviewer, really like poker does not mean that the candidate can remember the difference between a flush and a full house. Or, quite possibly, that they know anything about poker. And again, this still assumes they’ve seen playing cards. I’m really not kidding. I’ve had several candidates that have never used playing cards.

How long does it take to describe poker to an interviewee? Well, the basic mechanics of how cards fit together, assuming they understand cards, to make different-ranked hands is not overly intense. It takes a little more time to explain how those cards may change. But now we also need to talk about betting. Bluffing. Different species of poker. Dealers. Blinds. Acting dealers. All sorts of stuff I don’t know about because I’m not a poker player.

There’s a neat aspect about design problems — they are rewarding when the candidate asks a lot of questions. Neat questions are things like “Are we optimizing for computer play?” “Do we need to worry about performance of X?” “Do we want something that conveniently logs plays?” I mean, there are limitless possibilities of great questions that can come from a problem like “Design Poker.” But, if a candidate hasn’t seen the game before, first we spend ten minutes explaining Poker, and then the candidate still doesn’t a) understand poker b) know what questions to ask.

As I said I want to explore this concept, as well as the notion of design interviews in general, at a later date. There are a lot of interesting interview questions that involve problem situations that are completely foreign to the candidate, but I’m a bit nervous about questions that involve a requirement of understanding a rather significant problem space before being able to make intelligent decisions about design. But let’s get back on track.

Design a Deck of Cards

// forward declarations
class Suit;
class Value;
class Card {
public:
   Card();
   Card(const Card& c);
   ~Card();
   Card& operator=(const Card& c);
   virtual Suit get_suit() = 0;
   virtual Value get_value() = 0;
private:
   Suit suit_;
   Value value_;
};
class QueenOfDiamonds : public Queen, public virtual Diamond { 
   // ...
};
class Deck {
   Deal(std::vector<Player>& p) {
      // some hair-brained visitor pattern
   }
   Shuffle() {
      // magic
   }
   // a singleton, nat&uuml;ralich
   // implementation and thread safety discussion for the reader
};
bool operator<(const Card& a, const Card& b) {
   // implementation details left up to the reader
}
//...

Woah, woah, woah. Stop. We’ve got a major problem here, and it’s not just how atrocious the above is.

There’s one correct response to a design problem, and it’s not to start designing shit. It’s to start asking questions. There are a ton of questions to ask before one ever starts a design problem. Even for something as “simple” as “Design a deck of cards” it should take a few minutes to figure out the constraints, goals, and point of the problem. What features do we need to support? What needs to be fast? Should it be object-oriented? Procedural? Functional? Do we care about space usage? Do we want to support other types of cards? Do we want to model relationships between cards? Do we want to make it easily extensible? Do we want to be able to design the appearance of the cards? This is just a tiny taste of things; there are millions of these questions. Your job as an interviewer is not to answer all of them, but it’s to field some and steer the candidate in the direction you want. Narrow down the scope to steer them towards the design/algorithms/data structures/code you want to see. It’s not an exact science, but it’s a red flag if you’re working with somebody that doesn’t have questions.

In professional work, do you feel comfortable assigning a new employee to a task like “rewrite this product” and then letting them go off without asking questions (yes, that stated problem is a horrible way to manage a project, too, but that’s a topic I’m not at all qualified to talk about)? Of course not. Interviews are the same. It’s not that you want somebody that questions you, but you do want somebody that asks you questions. It scares me to death when people just start implementing stuff and don’t have a critical thought center in their brain.

Where was I?

Here’s some code ripped/paraphrased from Programming Challenges:

#define NCARDS 52
#define NSUITS 4
char values[] = "23456789TJQKA";
char suits[] = "cdhs";
char suit(int card) { return suits[card % NSUITS]; }
char value(int card) { return values[cards/NSUITS]; }

Is this the right way to design a deck of cards? It really depends. There are some distinct advantages to designing decks of cars as arrays of integers. Here’s the code needed to represent a deck in the above scheme:

int deck [52];

The boilerplate needed to build up a deck using the crazy polymorphic thirty-seven class approach would be insane. I’m not going to write it, just like I don’t want to write the code to actually work with a built-up deck. Does that mean the Programming Challenges approach is the right one? No. But it’s small and elegant and useful for solving problems. This is meant to illustrate the point that, without knowing what the interviewer wants, you would be stupid to start designing an answer to their design problem question, as a candidate.

Design Problems are Crap

We’ve established via the hand waving proof technique that an array of 52 integers is sufficient to represent a deck. Inductively this tells us that design problems are a waste of time. I’m going to attempt a more rigorous proof in the future, but we’ll just assume I’m not lying to you for now. Many of you will disagree with me and tell me that design interviews are worthwhile. We’ll revisit this in the future, I promise. One of the best hiring decisions I ever made was pushing for somebody that failed to achieve an architecture like the first approach, and instead chose a representation like the second one. The specifics are all quite a bit different, but the interviewer was expecting the candidate to design a class hierarchy, and instead they chose to represent game state via a string. The problem was that the interviewer wanted the candidate to show off their object oriented design skills and the candidate wanted to demonstrate how they would approach solving actual programming problems in the real world. Clearly this isn’t a problem inherent with the idea of a design problem, but rather of mismatched expectations and/or unclear problem specifications. It’s hard to say whether this is the fault of the interviewer or the candidate, but I much prefer questions that don’t leave this sort of development up to chance.

The Saving Throw

If you made it this far, we’ll close with a bit of a gem. There is a very interesting problem hiding in the idea of a deck of cards, which we’ll represent as an array of integers for the sake of simplicity and ease of programming. The interesting issue is the problem of shuffling cards. Here’s how the problem is stated:

“I have an array of 52 integers representing a deck of cards; design me an algorithm to shuffle them; you may use whatever approach and data structures you like.”

If the candidate isn’t familiar with cards, just say you have an array of 52 elements (or whatever number you are particularly fond of) and you want to produce a random permutation of those elements. If they don’t know what cards are and they don’t know what permutations are, you can either attempt to explain by taking three unlike things and putting them in different orders, or you can do a kindness and send them home early.

This problem statement leaves a lot of details unspecified, but is enough to get going, and should provide the appropriate entry point for some initial questions from the candidate. Here’s a bit of a trick: This is still a design problem. Not sure it’s a design problem? It says “Design me an algorithm.” It’s a design problem. It’s just not “Design an architecture to represent a thing.” Here’s another neat one that we’ll explore later: “Design a data structure and algorithm to represent and run a deterministic finite automata.” The big difference is that we’re designing something specific, and not asking the candidate whether their personal imagination and design aesthetic matches up with the interviewer’s. Obviously this is another argument by hand waving, and the end state, like all of this, is that it’s subjective. It’s a gray area. Everything is a design problem. Everything is data structures and algorithms."

Shuffling Cards

There’s the obvious answer, of course:

std::random_shuffle(deck, deck + 52);

But, of course, that doesn’t count.

Ask a candidate to shuffle an array of 52 integers, and you’ll get a lot of different initial answers. Here’s one of my favorites, which is something you’re not unlikely to see from a college undergrad:

// given
int deck[] = { 0, 1, 2, ... , 51 };
int used[52] = {0};
int newdeck[52];
int i(0);
while (i < 52) {
   for (;;) {
      int pos = rand() % 52;
      if (!used[pos]) {
         used[pos] = 1;
         newdeck[i++] = deck[pos];
         break;
      }
   }
}

“What’s the running time?”

“Linear.”

“No.”

… pregnant pause …

“Quadratic?”

“No.”

“Is it guaranteed to halt, even?”

At the end of the day, the implementation is non-deterministic. If given an adversarial RNG, you’re totally fucked. If this isn’t clear to the candidate, I then present them with the following RNG:

int evil_rand() {
   return 42;
}

Or, we could be slightly less stupid, but still horrible:

int less_evil_rand() {
   return rand() % 5;
}

I guess this means you can talk about the halting problem with the candidate now, but I don’t think I’ve ever had an interesting discussion about that on an interview, aside from quick jokes.

In a few trials with the algorithm and a non-adversarial RNG, it takes us a few hundred runs through to get a random permutation. Real-world this performance isn’t terrible, but it makes me break out in hives, and it should make the candidate break out in hives too. Further, what is its behavior on big sets, or ranges of numbers that invoke bad behaviors in our generators? I have no idea, I’m not smart enough for that kind of rocket science, but I’d rather not find out by not leaving it to chance.

“Okay, okay, I can fix that” says the clever candidate. They come up with a novel approach: Shuffling with chaining! In the event that we pick something that’s been picked before, we just keep going until we find one that’s not picked. Here’s our new algorithm:

while (i < 52) {
    for (;;) {
        int pos = rand() % 52;
        while (used[pos]) pos = (pos + 1) % 52;
        if (!used[pos]) {
            used[pos] = 1;
            newdeck[i++] = deck[pos];
            break;
        }
    }
}

“What’s the running time?”

“Linear.”

“No.”

“Quadratic?”

“Yes?”

Okay. What’s the behavior if we have an adversarial RNG?

“It halts.”

“How good is our permutation?”

“Are you really qualified to even ask that?”

“No, but I have the marker now, eat it.”

“Depends.”

“Okay, how do things look when we use the adversarial RNG that returns 0-4?”

Something like this: 0, 2, 3, 4, 1, 5, 6, 7, 8, 9, 10, 11, …

“That looks pretty random.”

“Yeah. Okay.”

While the adversarial RNG is a bit silly, it illustrates a weakness in the chaining approach — it chains. While recognizing/thinking of the chaining approach is clever (maybe they picked it up while learning about hash tables), the result is still pretty bad with a good RNG, because it means we’re not unlikely to have some cards going in order for no particular reason. The results will cluster. Again, the math of randomness is hard. I’m not good at it, but intuitively we can see how this would happen just by using an adversarial RNG, and inductively thinking about a good RNG.

Sub-quadratic performance, perhaps with a good distribution…

The upside is that we’ve managed to convert a non-deterministic algorithm to a deterministic one. A quadratic one, at that, which isn’t that big of a deal for 52 cards. Quadratic is slow, though, and intuitively, this should not feel like a problem that mandates a quadratic solution. The downside we discovered is that our newly deterministic approach has a decidedly bad property not shared with the non-deterministic approach, namely that it produces a really shitty shuffle.

Here’s how you make progress if the candiate can’t make the next leap: “We have a bad quadratic solution. I think we can find a solution that is at least n lg n.” Sorting should be popping into their head right about now. Push them a bit and suggest sorting if necessary

If that doesn’t work, you can give them a nice kick in the ass with “So, tell me about sorting.”

The basic approach is to generate 52 random numbers, and then sort the deck by that list of random numbers. This isn’t hard, and we basically get random shuffling for free, without doing any of the hard work. The code isn’t trivial to write, but still well within the range of leaving time for more implementations later. Here’s one silly stab at it, not necessarily the best approach:

struct C {
  C(int* c) : c_(c) {}
  bool operator()(const int& a, const int& b) {
    return c_[a] < c_[b];
  }
private:
  int* c_;
};
// ...
vector<int> v(52, 0);
generate(v.begin(), v.end(), rand);
C c(&v[0]);
copy(deck, deck + 52, newdeck);
sort(newdeck, newdeck + 52, c);

They may have a hard time figuring a good way to combine the sorting with an auxiliary array unless they sort objects (containing the item and the sort value) or implement their own sort. While fun, this is sort of a waste of time.

Getting linear

This is where I hit the love/hate wall with this question. There’s a trivial linear solution to the problem that’s very easy to fuck up, and explaining why it gets fucked up is probably beyond the scope of a normal interview, unless we use the trivial hand waving explanation of “we want to see each item having the same probability of a swap.”

The basic push is that you want to explore whether or not there’s a linear solution to the problem via swapping elements. Good candidates can make this reduction without too much pushing. The algorithm ends up now being:

for (int i = 52; i > 1; --i) swap(deck[i - 1], deck[rand() % i]);

The Knuth Shuffle is certainly both succinct and impressive. And I’ve probably screwed up the implementation. The chances of the candidate reaching a correct unbiased implementation is pretty low, but I don’t think that spending the time to develop this or realize this is probably worth it. I used this problem a lot many years ago when doing 30-minute campus screenings, because it was something that was pretty quick, involved some thought, wasn’t too heavy on advanced data structures, and allowed for a progression through implementations.

How the hell did we get here?

This is a fun little toy that we got to from the “Design a deck of cards” point, based on the least interesting deck of cards — an array of integers. This is a very interesting discussion between the candidate an interviewer that will take some time (15-30 minutes, probably, depending on how much code is written) that doesn’t involve designing anything about the deck. The downside is one that I hate about many of these interesting toy problems: The code gets substantially less interesting the more interesting the implementation gets. So, the advice stays the same I’ve given before: Get the candidate to implement an early version, and then talk through how to make it into a better version. Implementing the intermediate sorting-based approach is probably the most challenging one.