Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
1. I would look for the 3x3 matrix with the highest expected value (and since the probabilities within the 3x3 matrix are the same, the one with the highest sum). Unfortunately the only way I can think of of finding that is to do a linear search going through each row after the other and looking at all possible 3x3 submatrices individually.
2. Since I know what number the other guy has, I can convert the matrix to hold binary values. 1 if the number is greater that player1's, and 0 if it isn't. From here, we need to find the 3x3 submatrix with the highest number of ones. Linear search like in step 1?
1. Find out the highest element in 8X8 matrix and find out a 3X3 matrix with lowest variance from that element.
2. Give the second lowest to second player. and let the god decide... :)
Guys, I think you all completely missed it. The request was NOT to maximize the expected value of the random pick, the request was to maximize the chance of picking THE HIGHEST NUMBER.
Therefore look for the 3X3 matrix that has the greatest number of occurrences of the highest number (nobody said there are no duplicates) and pick that matrix. If more than one such matrix has the same number of occurrences, pick one arbitrarily.
One way is :
It's about predicting the Random number, and the code to generate random number is :
unsigned long next = 1;
int rand (void)
{
next = next * 1103515245L + 12345L;
return (unsigned int)((next > 16) & 0x7fff;
}
void
srand (unsigned int seed)
{
next = seed;
}
and most of the time, the seed is the time_tick, so if we can figure out the time in which user presses, it about reversing the above code.
I am not sure about the solution, its just a guess...
Its simple. It goes only through once in a loop.
- Kashif Khan September 24, 2012*Player 1 find the 3x3 matrix whose total sum of the elements is maximum compared to other 3x3 possible matrices in 8x8 matrix.
*Player 2 find the 3x3 matrix similar to player 1 to have at-least equal opportunity to win the situation since the algorithm to pick the element in a 3x3 matrix is random we have the probability to win depending upon on the algorithm used for randomly picking the element.