Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
6
of 6 vote

Its simple. It goes only through once in a loop.

*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.

- Kashif Khan September 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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?

- IZ September 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just brute force it?

- Anonymous September 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Algorithm picks up a number from your 3x3 randomly. Bruteforce won't work.

- endless September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course it will work. You calculate the expected values/probabilities using brute force

- Anonymous September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Return 3x3 matrix whose mode = maximum element in 8x8 matrix
This increases the chances of picking maximum element but no guarantee

2. If algorithm didn't pickup max element for player 1, choose the same matrix otherwise use the same technique mentioned in 1.

- vamana September 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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... :)

- Bharat Kumar Arya September 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Meir Shani December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

- Celestial September 28, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More