DVD
BAN USER- 2of 2 votes
AnswersA single-elimination tournament with 64 teams. Before the tournament, fans construct fantasy brackets for their tournament predications. Design a data structure for storing fan brackets and algorithm to score their brackets against a winning bracket. Assume we will then need to quickly score a player’s predictions (1 point per successful round prediction) and your solution should be optimal enough to handle millions of fan brackets with minimal data.
- DVD in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Data Structures
Since there is only 1 number without a pair, the array size is always odd. We can start with the middle. If the middle number is different from its neighbors, it's the number without the pair.
Here is the code I come up with in C#.
int printDuplicate(int[] array, int size)
{
int half = size / 2;
size = half;
while (true)
{
if (array[half] != array[half-1] && array[half] != array[half+1]
{
Console.WriteLine(array[half]);
break;
}
else if (array[half] != array[half+1])
{
// Check Left
half = size / 2 - 1;
}
else
{
// Check Right
half = size + (size / 2 + 1);
}
size = size / 2 - 1;
}
}
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.
- DVD July 16, 2015