Amazon Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
Neat solution. I think this would be the most efficient one. I propose a small change, an integer for each player to keep track of his score. The score will be +1 or -1 as per the prediction.
The solution I came up with was using an array, but I didn't think of using XOR to calculate the score. I have been thinking if there is a way to find the winner without scoring each fan individually but no luck.
I agree with @pkushigiang that this won't work beyond the first round. Say I guess 00... and it's actually 11..., then in round two I guess 1... <- that's not the correct team. In fact I was completely wrong about which two teams would advance to the second round in the first bracket so anything I guess for the outcome of that match in the second bracket would be incorrect.
I think we'd need 64 bits per round, each team has a bit, 1 means they're still in and 0 means they're out. Last round has 64 bits with 1 bit on for the winning team. Long.bitCount(guess & actual) would score each round for a fan.
Wait...this doesn't really work. You don't get points just for guessing whether the first team wins or the second team wins in each matchup. It could be that in a given matchup, you correctly guessed that the first team wins, but since you incorrectly predicted which team it would be from the previous round, you don't get any points.
Well, just like a heap in an array, you can also search that both the previous games were correctly predicted for the rounds after the first round. May be, it can be in the reverse direction - to start with it would be bit 1 (0-based indices) from the left for the final, the next 2 bits for the semi-final, the next 4 for the quarterfinal and so on. When any of the other rounds are being calculated, you need to check the previous rounds are all correct, so it won't be a simple XOR, but still manageable.
I think approach is fine. For all tournament we can 64 bits where each bit is representing one team. Then for each round winner team's bit would be set to 1. So for 6 rounds, we have 6 unsigned short numbers. Then similarly for every FAN, there is a list of 6 numbers which will predict his result in all 6 rounds. Now compare relevant rounds by XOR and if value is 0 assign point for that round else dont do any thing. We will get result in that way.
How about the entire tournament being represented by 64 bits where each bit corresponds to which team one a particular game (0 means the first team one and 1 means the second team won):
- zortlord July 15, 2015First round- 32 bits
Second round- 16 bits
Third round- 8 bits
Fourth round- 4 bits
Fifth round- 2 bits
Sixth round- 1 bit
Scoring would be simple- XOR the user prediction with reality and count the resulting 0s.