## Amazon Interview Question for Software Engineer / Developers

Country: India

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

Complex problem, backtracking is the algorithm technique that needs to be used though. Modifications to the solution of the standard problem should work.

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

Correct me if I am wrong but is this even possible to achieve. I tried placing 2 queens on 2X2 but no equilibrium, I tried placing 3 queens on 3X3 board still no equilibrium, I tried few other combinations where M was less than 15 for a MXM board but no equilibrium. If someone understands this problem correctly please present an example. Thanks!

Comment hidden because of low score. Click to expand.
0

10000000000000
00000000010000
00000000000010
01000000000000
00000100000000
00000000001000
00100000000000
00000010000000
00000000000100
00010000000000
00000001000000
00000000000001
00001000000000
00000000100000

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

Isnt it like the safe zone will change depending on M?

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

This is technically not possible or else I got it totally wrong. Because in a two dimensional matrix a single Queen at least will cover 1 full row and 1 full column. After that there will not be any single cell whose row or column does not intersect with either the first Queens row or column.
So two Queens can not be placed in such way in any chase board.

Comment hidden because of low score. Click to expand.
0

Two queens' "attack zones" will always intersect for the reason you stated. But that is not a direct attack. For instance, if I place a queen on the a1 square of a chessboard, and another queen on b8, they are not directly attacking eachother.

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

This is not possible to do. Lets say for starters we are not placing the queens but only the castles which means that m castles are placed such that each castle occupies a row in mxm matrix. Now if you take (i,j) as one co-ordinate, because of the restrictions in placing them these no i and j value are equal for any two of the castles if they are they either fall in the same row or in same column. This would only mean that the (i,j) values of all these castles have to increase simultaneously, which puts them all on a diagonal and now if these castles were given the powers of bishops (now they are queens) they end up being in the attack zones of each other. Irrespective of the knight powers you can't place m queens on mxm board

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

Not possible. However it can be achieved if special queen does not have the power of knight but in that case too M should be greater than 3 i.e M>3

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

This problem is a variant of a long-standing math problem known as the "N-Queens problem." This version in which the queens also can move like a knight is sometimes called "superqueens." The problem, in general, is computationally very complex and requires just a lot of searching and iterating; there isn't any one best way to do it and therefore a good answer is one that's efficient in CPU time.

I found a discussion of the general problem at a Web site by Jeff Somers (I'm not allowed to include the URL here). A couple of noteworthy comments I found there:
{
There is no quick and easy way to calculate the total number of N queen solutions for an N x N board.
}
and

{
The backtracking algorithm used to solve this problem
We place a queen in the top row, then note the column and diagonals it occupies. We then place a queen in the next row down, taking care not to place it in the same column or diagonal. We then keep track of the occupied columns and diagonals and move on to the next row. If no position is open in the next row, we back track to the previous row and move the queen over to the next available spot in its row and the process starts over again.
}

Got that? It's an iterative, row-by-row search of possible solutions, terminating each branch when it gets stuck, or when a solution is found.

Is such a search too slow? Our problem states that we only need to search up to a 14x14 board. If we place each queen on a different row, and each queen must be in a column not already used, then an upper bound on the number of arrangements is 14! = over 81 billion. But each queen actually has fewer legal spots than that since it can't be within 2 columns of the queens in the 2 rows above it; therefore the number of choices to search is bounded (I'm being approximate since it gets more complicated when some queens are near an edge) by 14x11x8x8x8x8x8! = 25.4 billion. This is not an optimal solution but it indicates that such a search is doable on any current-generation PC. According to Somers (above), the largest board for which the regular n-queens problem had been solved at his time of writing was 23x23.

You could do such a search either with an iterative loop, or a recursion formula. Since the maximum depth of recursion is only 14 levels, there's no risk of a stack overflow.

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

Permutation and then remove other illegal solutions

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

i) iterate over all possible placement spots for a queen, placing one at each possible spot at each iteration
ii) delete all spots she can go to from set of possible placement spots
iii) place another queen
iv) and so on until the map is filled
v) this continues until the outer loop (which runs over the entire board) finishes

From considerations of symmetry we only really have to do about half the board on the outermost iteration (above and including the main "diagonal").

There should be other possible optimizations. Either way, it's a problem that demands an expensive solution. Not sure if there is an approach better than brute force.

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.

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