Microsoft Interview Question Software Engineer in Tests
0of 0 votesfind one missing card from deck of 51 card
That would help find the face value of the missing card. But how would you find the suite then?
Yeah Hashing sounds like the best option. Have a hashmap consisting of key = suite and value = sum. Go through the given deck entirely once and keep adding face value to the corresponding suite entry from hashmap. When you look at the hashtable you'll immediately know which card and which suite is missing. Only problem with this is that you'll need 4 variables.
Assign multipliers for each suite as;
spade: 100
club: 1000
diamond: 10000
heart: 100000
Add the values by multiplying card value with the suite multiplier.
Find the difference between the sum of 52.
In this way both the value and the suit can be found.
for ex:
If the difference is 300000, missing card is heart_3
Note: In order to avoid collision, do not use the value of 10. Set card value for jack as 11 (not 10), queen 12 etc..
Space complexity: O(1)
No need for an extra container
Hearts : *100
Spades : *1000
If so then 10 of hearts and 1 of spades both evaluate to 1000. Here is a collision.
Instead, i recommend use of distinct prime numbers beyond 15 as multiples. 17,19,23,29
Actually i had added the note about how to prevent the collision case:
"Note: In order to avoid collision, do not use the value of 10. Set card value for jack as 11 (not 10), queen 12 etc.."
Correction on the note: "... Set the card value for 10 as 11 (not 10), jack: 12, queen: 13 and the King: 14
I think there should be small change to ern solution to avoid collisions, where 10*100(Hearts, 10) == 1*1000(Club, 1).
So taking
spade: 1
club: 100
diamond: 10000
heart: 1000000
would be the correct solution. Please crrect me if i am wrong,
Thanks,
Satya Chaganti.
I think there should be small change to ern solution to avoid collisions, where 10*100(Hearts, 10) == 1*1000(Club, 1).
So taking
spade: 1
club: 100
diamond: 10000
heart: 1000000
would be the correct solution. Please crrect me if i am wrong,
Thanks,
Satya Chaganti.
I think we can also use Multipliers such as
Hearts = 1
Spade = (Heart * 13) + 1
Club = (Spade * 13) + 1
Diamond = (Club * 13) + 1
Assuming the suite starts from A = 1 and ends in King = 13
When we subtract the sum from the original sum and get the diff,
if(diff % club == 0)
missing card is of the value (diff/club) in the suite "club"
because
King of Hearts = 1 * 13
Ace of Spade = 13 * 1
They give the same product. So, to be safe, we choose multipliers such that maximum product of a suite is less than the minimum product of the next suite. In other words,the LCM of two suits (eg: spade and club) will be always higher than highest multiple of club.
Why is it necessary to multiply? Can't we just use:
0: Hearts 1 - 13
1: Spade 14 - 26
2: Club 27 - 39
3: Diamond 40-52.
Then sum up 1 to 52. If n = sum - givenSum, then suit is n / 13, card number is n%13.
use XOR.
- chait November 30, 2010XOR numbers of cards = missing card number
XOR colors of cards = missing card color
XOR of suites of cards = missing card suite.
XOR(A, A) = 0
and if u do XOR on even times repeated no.s we will get zero.
and if u do XOR on all even times and one no. odd times then we will get odd time repeated no.
Here, in our case... missing no. repeated odd no. of times n other no. repeated even no. of times.
So, our XOR will work here.
plz correct me if I'm wrong...
Thanks