Card deck and sparse matrix interview questions [closed]

Question

I just had a technical phone screen w/ a start-up. Here's the technical questions I was asked ... and my answers. What do think of these answers? Feel free to post better answers :-)

Question 1: how would you represent a standard 52 card deck in (basically any language)? How would you shuffle the deck?

Answer: use an array containing a "Card" struct or class. Each instance of card has some unique identifier... either it's position in the array or a unique integer member variable in the range [0, 51]. Shuffle the cards by traversing the array once from index zero to index 51. Randomly swap ith card with "another card" (I didn't remember how this shuffle algorithm works exactly). Watch out for using the same probability for each card... that's a gotcha in this algorithm. I mentioned the algorithm is from Programming Pearls.

Question 2: how to represent a large sparse matrix? the matrix can be very large... like 1000x1000... but only a relatively small number (~20) of the entries are non-zero.

Answer: condense the array into a list of the non-zero entries. for a given entry (i,j) in the array... "map" (i,j) to a single integer k... then use k as a key into a dictionary or hashtable. For the 1000x1000 sparse array map (i,j) to k using something like f(i, j) = i + j * 1001. 1001 is just one plus the maximum of all i and j. I didn't recall exactly how this mapping worked... but the interviewer got the idea (I think).

Are these good answers? I'm wondering because after I finished the second question the interviewer said the dreaded "well that's all the questions I have for now."

Cheers!

Answer 1

That's a good start with the cards. Here's my idea if you want to get more realistic modeling: You should take into account the fact that a deck can contain more or less than 52 cards (e.g. if you have jokers in it, or if it's a euchre deck, etc.). So instead of an array, maybe a generic enumerable list (like C#'s List<Card>). That would also make inserting and removing individual cards easier (say, for simulating dealing).

Then, for shuffling, you could split that list into two stacks of arbitrary size, pop cards off the top and push them onto a third list, randomly selecting which half to choose from each time. That would be more realistic.

As for the second question, that sounds reasonable to me.

Answer 2

Well, shuffling in a statistically correct way is surprisingly hard. Since I know that it's tricky I'd just look it up to be sure I'm doing it correctly.

If you do program it yourself, make sure to let it run a few thousand times to see if it's correct. And point that out to the reviewer.

Answer 3

Question 1: how would you represent a standard 52 card deck in (basically any language)? How would you shuffle the deck?

In Java, I would use:

1. ArrayList<Card> deck as data type and name.
2. Collections.shuffle(deck) or Collections.shuffle(deck, myRnd) to shuffle the deck.

Question 2: how to represent a large sparse matrix? the matrix can be very large... like 1000x1000... but only a relatively small number (~20) of the entries are non-zero.

In Java, I would store only non-zero elements, in:

1. HashMap<TupleN, Data> matrix as a data type in general case, where TupleN is a value class (with a custom hash function) and contains element locations.
2. In case of 2 dimensions I would combine them in long type HashMap<Long, Data> m and use m.get(((Long)i1<<32)+i2);, if i need an element.

Answer 4

It's not the best technique for sorting cards.
See Kneuth for details.

A better algorithm is:

 1) Have a deck of all cards (a)
 2) Have a deck with 0 cards (b)
 3) Pick one card at random from (a) and remove it.
 4) Add picked card to top of (b)
 5) While (a) is not empty goto (3)
 6) (b) is now shuffled.

Note when implementing this you can use a single deck. The secret is that once a card has been selected it is never selected again (ie once moved to the shuffled deck it is not touched).

Answer 5

In the second question, I'd have asked what operations we wanted to optimize on the matrix. The best implementation of a sparse matrix would seem to depend on the operations being performed.

Answer 6

The answer to both questions really is "It depends on what you want to do with it".

A playing card can be considered as an element of the Cartesian product of values and suits and implemented as a pair which composes two enums. Great for school-level OO lessons. But if you're implementing, say, optimised poker hand evaluation for a system with limited memory (i.e. can't just use a 2GB FSM), then that's not a helpful representation. When I did this (partially for the relevant Project Euler problem, partially because a friend expressed interest) I used a 64-bit int per card with bit representation 23456789TJQKA00200300400500600700800900T00J00Q00K00A00C00D00H00S because then bit fiddling can get a lot of properties very fast.

For sparse matrices you really have to think about what kind of matrices you're implementing and what you want to do with them. Diagonal matrices, for instance, are amenable to a very specialised implementation.

Answer 7

I would say to be honest, since I know there are people smarter than me who have already solved a problem like that, and since I've never spent much time thinking about it in particular because it doesn't come up often in embedded network programming, I would start by looking up published algorithms or third party libraries. Do you want me to take a couple minutes to do a search, or just tell you the best I can come up with on my own?

The "best I can come up with on my own" is very similar to yours, although I might go into more application details like data structures needed to ensure a card isn't duplicated across hands, "view" of a card versus "model," etc.

Answer 8

Wouldn't this ensure that you do not touch an already placed element again?

for (i = 51; i >= 2; i--) {
  swap(arr[i], arr[rand() % i]);
}

swap(arr[0], arr[1]); //just to be safe.

(referring to Watch out for using the same probability for each card... that's a gotcha in this algorithm.)

Answer 9

Basically shuffling means, then end result should be as much random as possible (no one should be able to guess the resulting sequence, given the original sequence).

I like Martin's simple approach, only thing is your rand() function should be good.

Btw, even if i use swap algo (without any constraint on revisit), that as well should form a good approach. the iteration should be >= 52/2 = 26 times.