Card deck and sparse matrix interview questions [closed]

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!

-

closed as unclear what you're asking by MichaelT, Dan Pichelman, amon, whatsisname, ratchet freakMay 16 '14 at 15:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

Sparse matrices are common in numerical analysis. The problem is even harder if you need to perform parallel computations on the data structure. There are a lot of PhDs minted on exactly this topic. – chrisaycock Feb 25 '11 at 22:03
The shuffle algorithm is okayish, "the same probability" specifically means that you shouldn't swap with positions already visited. – biziclop Feb 25 '11 at 22:15
By the way, the Java implementation of this algorithm is simply `Collections.shuffle(cardList);` :) – biziclop Feb 25 '11 at 22:28
I like these questions (I think your answers are along the right lines, too). You ought to add them to my question programmers.stackexchange.com/questions/20927/… ! – NickC Feb 25 '11 at 23:34
Decent answers, but do not stop interviewing. It never hurts to have multiple offers to choose from. – Job Feb 26 '11 at 4:25

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.

-
Thanks for the reply. Your card shuffling algorithm sounds neat. Would be fun to try to implement it in O(n) time and O(1) space like the Knuth shuffle algorithm: tekpool.wordpress.com/2006/10/06/… – MrDatabase Feb 25 '11 at 22:14
@MrDatabase — Off the top of my head, doing my stack-based algorithm in O(1) space (did you mean O(n) space?) is probably impossible in O(n) time, but I'm no algorithms expert. Very nice article, though. – Andrew Arnold Feb 25 '11 at 22:18
I meant O(1) additional space (so not counting the space of the array you're given). Regarding your shuffle algorithm: I was thinking about implementing it with some tricky/clever indices into the original array. For example you can have an index to the "top" of the first "stack", an index to the "top" of the second stack and then do some clever swapping of values when shuffling. This approach is vaguely like performing heap-sort on an array with only O(1) additional space... i.e. it involves some clever swapping of values in the array. – MrDatabase Feb 25 '11 at 22:39
@MrDatabase: You could implement this in place using two pointers into your list/collection/array and should be solvable in O(n) time. – oosterwal Feb 26 '11 at 2:52

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.

-
Just use Fisher-Yates shuffling. – edA-qa mort-ora-y May 11 '11 at 10:58

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.
-

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).

-
The algorithm he is thinking of is an inplace version of this. – Winston Ewert Feb 25 '11 at 23:40
@Winston Ewert: He may be thinking it but that is not what he is doing. What he is doing is actually the standard anti-pattern for shuffling. To do this algorithm in-place you still need to reduce the range of the randome card each iteration. 0->51 first time 0->50 second time etc and you must swap with the top un-shuffled card. – Loki Astari Feb 26 '11 at 1:18
His description does miss that very important part of the algorithm. But at that point he is explicitly vague and notes he doesn't remember how it works. It is clear he has seen the correct algorithm although he doesn't remember it perfectly. – Winston Ewert Feb 26 '11 at 1:42
This is an important point. The implications are on the probability of shuffling each card being the same... I did manage to mention this. – MrDatabase Feb 26 '11 at 2:04

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.

-

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.

-

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.

-
Are the upper bits used to determine if the card is a straight, or what's the intention? I can see that for up to seven card stud the lower bits will quickly tell you how many cards of each rank and suit there are; they could also pretty easily identify if there's a straight, though perhaps the upper bits are better for that? – supercat Mar 18 '15 at 22:48
@supercat, yes, exactly. The point of the upper bits is that after ORing the masks of the cards the lookup table for detecting a straight only requires 2^13 entries rather than 2^39. – Peter Taylor Mar 19 '15 at 2:14
That makes sense. If one was only having to evaluate five cards, one could find a straight other than ace-high, without the "concentrated" upper bits by computing `v1 = v & 011111111111110000` on the "or" of all the cards to get the ranks info, then `v2=v1 & ~(v1-1);` to locate the LSB, `v3 = (v1 | 066666666666660000) + v2;` to process a carry chain, and `v4=v1 & v3;` to see if all bits were consecutive. I can see, though, that a lookup table would be helpful if one needs to see if any five cards out of seven would yield a straight, though I'd think concentrating lower bits would be better. – supercat Mar 19 '15 at 15:22

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.)

-

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.

-
Why revive an old thread if you're not going to add anything useful to it? – Peter Taylor May 11 '11 at 12:28