Amazon Interview Question for Computer Scientists

Country: India
Interview Type: In-Person

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

1. squares in NxN grid

``````1X1	 ->  (N)^2
2X2	 ->  (N-1)^2
3X3  ->  (N-2)^2
...
NxN  ->  (1)^2
So, total no. of squares=sigma(N^2) over N
=(N)*(N+1)*(2*N+1)/6``````

2.squares in MxN grid

``````let M>N //swap if M<N
let k=M-N
1x1  ->  (N+k)x(N)
2x2  ->  (N-1+k)x(N-1)
3X3  -> (N-2+k)x(N-2)
...
NxN  ->(1+k)x(1)
So, total no. of squares=sigma((N+k)*(N)) over N
=sigma(N^2 + k*N)
=sigma(N^2) +k*sigma(N)
=(N)(N+1)(2*N+1)/6 + k*N*(N+1)/2``````

3.rectangles in MxN grid

``````In an MxN grid you have M+1 horizontal lines
and N+1 vertical lines to enclose a rectangle.
If we choose 2 out of M+1 lines and 2 out of N+1 lines then the intersection of these 4 lines makes a rectangle.

so,answer is 	  (N+1)C(2) * ((M+1)C(2))   		//nCr
=(N*(N+1)/(2)) * (M*(M+1)/2)``````

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

// assume that the numbers of rectangles before index(i,j) is s
// when the rect in index(i,j) is included, another (i+1)*(j+1) rectangles add to s

int sum = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
sum += (i+1)*(j+1);
}
}
return sum;

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

Is the grid fill with 1s and 0s?

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

Number of Squares:

``````for (int i= N through 0){
numSquare += i^2;
}
return numSquare;``````

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

Assumption M<=N

For no of squares in MxN

``````Size of square:			1	2	3	4.....	k...		M-1		M
No of squares in row:	N	N-1	N-2	N-3	N-k+1	N-M+2	N-M+1
No of squares in col:	M	M-1	M-1	M-1	M-k+1	2		1
Total no of squares = no of squares in row * no of squares in col
sigma [(N-k+1)*(M-k+1)] for k from 1 to M``````

For rectangles

``````Length of rectange		1	2	...	k	...	N-1	N
No of rectange			N	N-1		N-k+1	2	1
Total rectangles  = N*(N+1)/2
Height of rectange		1	2	...	k	...	M-1	M
No of rectange			M	M-1		M-k+1	2	1
Total rectangles  = M*(M+1)/2
Total no of rectanges = M*N*(M+1)*(N+1)/4``````

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

your approach is good but in rectangle case we can solve it more easily

m* n matrix has (m+1) vertical lines and (n+1) horizontal lines and a rectangle will form if we chose any 2 vertical lines from m+1 lines (i.e (m+1 C 2)) and any 2 horizontal lines from n+1 horizontal lines (i.e. n+1 C 2),
hence

Ans - m+1C 2 * n+1 C 2 = m*n*(m+1)*(n+1)/4

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

Thats a much simpler explanation. Good one.

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

This solution uses DP, however, it's not as good as those that provide a cool formula, plus its demonstration, for calculating the value :(

Number of squares:
The idea is that for getting the number of possible squares at cell (i, j), we want to add the existing ones at (i-1,j) + (i, j-1) while ignoring duplications, i.e., (i-1,j-1). Then, we want to add all new squares that have cell (i, j) as part of them, which in this case is the value of min(i, j) for the squares of size 1, 2, 3 ... min (i, j) that have cell (i, j) at its bottom-right corner.

Hence,
F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + min(i, j)

You can fill the matrix top-down while reading left to right.

Number of rectangles:

Same idea as previous one, except that the number of new rectangles added at cell (i, j) that include such cell is given by i * j.

F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + i * j

Space complexity: O(n^2), ouch...

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

Solve reccurance equation:
C(1)=n; C(n)=C(n-1)*2 - n + N + 1
The solution:
C(n) = 2^(n-1) (n+N-2)+n-N+1

Notice, with adding row we only doubling previous squares (each has shifted copy) plus aad all covering new width

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

There is mistake in my previous, sorry, shifts create extra duplicate counts.

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.