Amazon.com Interview Question
1,580 Interview Reviews |
Back to all Amazon.com Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Development Engineer at Amazon.com:
This was not unexpected but a bit difficult. How would you represent the ordering of a deck of card if you only have 32bytes to work with. So, he explained that you have 52 objects, there are 52! possible ordering of them. how to encode one of those ordering within 32 bytes?
| Tags: | analytical reasoning See more , See less 8 |
See more for this Amazon.com Software Development Engineer Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (9)
1 of 1 people found this helpful
(20*6 + 16*5 + 8*4 + 4*3 + 2*2 + 1) = 249 bits
32 bytes is 256 bits.
Helpful Answer?
Yes |
No
Inappropriate?
1 bit -> encode 1 card
2 bits -> encode 4 cards
3 bits -> encode 8 cards
4 bits -> encode 16 cards
5 bits -> encode 25 cards
1 * 1 + 2 * 4 + 3 * 8 + 4 * 16 + 5 * 25 = 222 bits
Helpful Answer?
Yes |
No
Inappropriate?
@evert: yours should work!
although the implementation would be a little slow. But with this problem you can achieve the theoretical minimum log_2{52!} (that is the information content of the message passed) by numbering each permutation. That is order (preferably lexicographically) each permutation. And number then incrementally.
Helpful Answer?
Yes |
No
Inappropriate?
Isn't there any conflict with the encodings?
Thanks
Helpful Answer?
Yes |
No
Inappropriate?
Helpful Answer?
Yes |
No
Inappropriate?
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
We will use (4*13) for each face card and (2 *4) for the suits.
Combined this would consume 52 for an entire deck of card.
struct Card {
unsigned char face:4, suit:2;
};
Helpful Answer?
Yes |
No
Inappropriate?
Don't use any bits for the suit. Instead, use the implied position: first pair of 13, second pair of 13, etc.depict the suit. Then 3 bits for first seven faces and 3bits for the next six. Now let's do the math (hold on, let me take out my calculator, got it):
7 x 3 + 6 x 3 = 39. Then 39 x 4 = 156 bits or 19 bytes.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up



0 of 1 people found this helpful
by Interview Candidate: