## Snapdeal Interview Question for SDE1s

• 0

Country: India
Interview Type: In-Person

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

In order to compute the sum of all the elements within the area of rectangle in O(1) running time we can preprocess the Matrix to have in each element of the Matrix the sum of all the elements between (0,0) and the lowerRight corner. Then we can use this preprocessed Matrix to get the sum for all the elements between upperLeft and lowerRight by getting the sum at lower right, minus the sum at the element on the bottom left-1 of the rectangle (that will subtract all the elements on the left os the Rectangle), minus the sum at the element on the top-1 right (that will subtract all the elements above the rectangle, and then we have to readd the elements that are both on the left and above the reactangle, because we have subtracted them 2 times, so we add the sum at the top-1 left-1 corner. In this way we can compute the sum of all the elements in a rectangle inside a matrix we just 3 operations for any dimension.

So there are 2 steps:
1. Preprocess the matrix substituting the elements with the sum of all previous elements (like a running sum)
2. Get the sum in a rectangle by getting the sum at lowerRight minus the sum at position bottom left -1 (elements on the left), minus the sum at position top-1right, plus the sum at position top-1 left-1.

The complexity is O(n*m) to preprocess the matrix as we need to process each element (n and m are the dimensions of the matrix), and O(1) to get the sum after preprocessing.

Example 1:

``````Original Matrix:
1,2,8,1
7,4,6,1
4,7,7,8
Summed Matrix:
1,3,11,12
8,14,28,30
12,25,46,56

The sum in the rectangle betweeen
UpperLeft corner (0,1)
and
LowerRight corner (2,2)
is: 34``````

Example 2:

``````Original Matrix:
9,9,9,6
2,5,1,8
4,3,0,7
9,3,7,3
6,5,3,5
Summed Matrix:
9,18,27,33
11,25,35,49
15,32,42,63
24,44,61,85
30,55,75,104

The sum in the rectangle betweeen
UpperLeft corner (1,1)
and
LowerRight corner (2,3)
is: 24``````

This is the code for this solution, you can use:

``int[][] genMatrix(int n, int m)``

to generate a Matrix of size n,m with random integers, and:

``void printMatrix(int[][] m)``

to print the matrix. The method:

``int[][] preprocessSumMatrix(int[][] m)``

will preprocess the matrix with the running sum and the method:

``int sum(int[][] m, Vertex upperLeft, Vertex lowerRight)``

will compute the sum of all the elements in the Matrix included between upperLeft and lowerRight vertices.

Here is the complete code:

``````import java.util.*;

class Vertex {
int i;
int j;
public Vertex(int i, int j) {
this.i=i;
this.j=j;
}
public String toString() {
return "("+this.i+","+this.j+")";
}
}
public class SumElementsInRectangle {
public static int[][] preprocessSumMatrix(int[][] m) {
int[][] summedMatrix = new int[m.length][m.length];
for(int i=0;i<m.length;i++) {
for(int j=0;j<m[i].length;j++) {
summedMatrix[i][j] = m[i][j];
if(j-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] + summedMatrix[i][j-1];
}
if(i-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] + summedMatrix[i-1][j];
}
if(i-1>=0 && j-1>=0) {
summedMatrix[i][j] = summedMatrix[i][j] - summedMatrix[i-1][j-1];
}
}
}
return summedMatrix;
}
public static int sum(int[][] m, Vertex upperLeft, Vertex lowerRight) {
int sum = 0;
if(m==null) return sum;
if(upperLeft.i>lowerRight.i || upperLeft.j>lowerRight.j) {
System.out.println("ERROR: Input Vertices not Correct, check the coordinates.");
return sum;
}
if(upperLeft.i<0 || upperLeft.i>=m.length || upperLeft.j<0 || upperLeft.j>=m.length) {
System.out.println("ERROR: Input Vertex UpperLeft out of Bounds.");
return sum;
}
if(lowerRight.i<0 || lowerRight.i>=m.length || lowerRight.j<0 || lowerRight.j>=m.length) {
System.out.println("ERROR: Input Vertex LowerRight out of Bounds.");
return sum;
}
sum = m[lowerRight.i][lowerRight.j];
if(upperLeft.i-1>=0) {
sum = sum - m[upperLeft.i-1][lowerRight.j];
}
if(upperLeft.j-1>=0) {
sum = sum - m[lowerRight.i][upperLeft.j-1];
}
if(upperLeft.i-1>=0 && upperLeft.j-1>=0) {
sum = sum + m[upperLeft.i-1][upperLeft.j-1];
}
return sum;
}
public static int[][] genMatrix(int n, int m) {
if(n<=0 || m<=0) {
System.out.println("ERROR: Non-positive values to create Matrix");
return null;
}
Random r = new Random();
int[][] matrix = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
matrix[i][j] = r.nextInt(10);
}
}
return matrix;
}
public static void printMatrix(int[][] m) {
if(m==null) {
System.out.println("ERROR: Null Matrix");
return;
}
for(int i=0;i<m.length;i++) {
for(int j=0;j<m[i].length-1;j++) {
System.out.print(m[i][j]+",");
}
System.out.println(m[i][m[i].length-1]);
}
}
public static void main(String[] args) {
int[][] matrix = genMatrix(3,4);
System.out.println("Original Matrix:");
printMatrix(matrix);
int[][] summedMatrix = preprocessSumMatrix(matrix);
System.out.println("Summed Matrix:");
printMatrix(summedMatrix);
Vertex upperLeft = new Vertex(0,1);
Vertex lowerRight = new Vertex(2,2);
int sum = sum(summedMatrix,upperLeft,lowerRight);
System.out.println("The sum in the rectangle betweeen\nUpperLeft corner "
+upperLeft+"\nand\nLowerRight corner "+lowerRight+"\nis: "+sum);
}
}``````

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

Hi, the wording of your algorithm (the last part of calculating the sum) is not clear. If possible please run an example for the same. Thanks.

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

seems this would work
- each time the matrix is populated - compute all possible sums for rectangles/matrix built so far that has dimensions greater than 1.
- store in dict as your building this {'x1-x2-y1-y2': sum} where 'x1-x2-y1-y2' is a serialized format of the co-ordinates that can be used for easy lookup.
- Look ups can now by done via serializing the input co-ordinates and extracting the value.

- We can further optimize the pre-processing where as we are building the matrix we'd be calculating all possible sums for x-1,y-1 x>0, y>0 so we can re-use their values easily.
We would just need to get the sums for those rectangles that would need to include this new value.

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

hint- 5+1+8+7+0+6+9+5+3

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

Pre-calculate the sum for every sub-matrix whose origin is at (0, 0). This results in a matrix the same size as the input matrix, and M(x, y) is the sum of all elements in the sub-matrix from (0, 0) to (x, y)

When the user gives the points (x1, y1), (x2, y2), return:

M(x2, y2) - M(x1, y1) - M(x2, y1) - M(x1, y2)

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

Hmm,
I think this approach will work.
Let me code and verify it
Thanks :)

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

It should be + M(x1, y1), not minus. Other than that, this is the right approach.

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

M(x2,y2) - M(x1-1,y2) - M(x2,y1-1) + M(x1-1,y1-1)

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

I did not get this solution .How does this work ?

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

``````from compiler.ast import flatten

data = [[1, 3, 5, 1, 8],
[8, 3, 5, 3, 7],
[6, 3, 9, 6, 0]]

def clip_matrix(data, x1, y1, x2, y2):
matrix = []
for i in range(len(data)):
row = []
for j in range(len(data)):
if i >= x1 and j >=y1 and i <= x2 and j <= y2:
row.append(data[i][j])
matrix.append(row)
return matrix

if __name__ == "__main__":
print sum(flatten(clip_matrix(data, 0, 2, 2, 4)))``````

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

I think the following would be the right solution

``````from compiler.ast import flatten

data = [[1, 3, 5, 1, 8],
[8, 3, 5, 3, 7],
[6, 3, 9, 6, 0]]

pre_computed_solution = {}

def clip_matrix(data, x1, y1, x2, y2):
matrix = []
for i in range(len(data)):
row = []
for j in range(len(data)):
if i >= x1 and j >=y1 and i <= x2 and j <= y2:
row.append(data[i][j])
matrix.append(row)
return matrix

if __name__ == "__main__":
for a in range(len(data)):
for b in range(len(data)):
for c in range(a+1, len(data)):
for d in range(b+1, len(data)):
k = "%d-%d-%d-%d" % (a,b,c,d)
pre_computed_solution[k] = sum(flatten(clip_matrix(data, a, b, c, d)))

print pre_computed_solution['0-2-2-4']
print pre_computed_solution['0-0-2-4']``````

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

``````#include<stdio.h>
#include<stdlib.h>

int main(int argc,char *argv[])
{
int matrix = {{1,3,5,1,8},{8,3,5,3,7},{6,3,9,6,0}};
int cord;
int k,i,j,l=0;
int total =0;
for(k=0;k<2;k++)
{
printf("Enter the cordinates position\n");
scanf("%d%*c%d",&i,&j);
cord[l++] = i;
cord[l++] = j;
}
for(i=cord;i<= cord;i++)
{
for(j=cord;j<= cord;j++)
{
total = matrix[i][j] + total;
}
}
printf("%d\n",total);
}``````

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

Assuming there is no Update-Query on A[]
Consider a 1-D matrix A[]={1,3,5,1,8}
we will calculate aggregate sum as A[i]=A[i]+A[i-1] for all i in 2 to n
Reslut array is A[]={1,1+3,1+3+5,1+3+5+1,1+3+5+1+8};
now we can answer any query .

In th similar way we have to do it for 2-D array

Given matrix M[][]

1 3 5 1 8
8 3 5 3 7
6 3 9 6 0

now we have to pre-calculate SUM as
M[i][j]=M[i][j]+M[i-1][j]+M[i][j-1]-2*M[i-1][j-1]; for all i,j belongs 1 to n

1 1+3 1+3+5 1+3+5+1 1+3+5+1+8
1+8 3+1+3+8 2*3+2*5+1+8 . ...
. ..
. ..

Now suppose there is Query like sum(values from i,j to p,q)
so answer will be M[p][q]-M[i][q]-M[p][j]+M[i][j]; which is O(1)

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

The DP formula for calculating any element of the matrix is :

ResultMatrix[x,y] = ResultMatrix[x-1,y] + ResultMatrix[x,y-1] - ResultMatrix[x-1,y-1] + OriginalMatrix [x,y]

with the exception of the first row and column where:

ResultMatrix [0,0] = OriginalMatrix[0,0]

ResultMatrix [x,0] = ResultMatrix[x-1,0] + OriginalMatrix[x,0]

ResultMatrix [0,y] = ResultMatrix[0, y-1] + OriginalMatrix[0, y]

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

A simple solution in Python

``````a = [[1, 3, 5, 1, 8 ],
[8, 3, 5, 3, 7 ],
[6, 3, 9, 6, 0 ]]

row = len(a)
col = len(a)

b = [[sum(a[j][:i+1]) for i in range(col) ] for j in range(row)]

x = (0,2)

y = (2,4)

for val in range(x,y+1):

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

public class SumOfAlltheElements
{

public static void main(String [] args)
{
int [] arr[]={ {1, 3, 5, 1, 8},
{8, 3, 5, 3, 7},
{6, 3, 9, 6, 0}};

int [] x={0,2};
int [] y={2,4};
for(int i=x;i<=y;i++)
{
for(int j=x;j<=y;j++)
{
}
}

}
}

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

Guys check this may or may not work

``````import java.util.Scanner;
class Demo
{
public static void main(String[] args)
{
int a[][]=new int;
Scanner s=new Scanner(System.in);
System.out.println("Enter the matrix row and column");
int m=s.nextInt();
int n=s.nextInt();

System.out.println("Enter elements of a matrix");

for(int i=0;i<m;i++)
{
for (int j=0;j<n ;j++ )
{
a[i][j]=s.nextInt();
}
}

System.out.println("Entered Matrix elements are");

for(int i=0;i<m;i++)
{
System.out.println();
for (int j=0;j<n ;j++ )
{
System.out.print(a[i][j]);
}
}

System.out.println("Enter the matrix from whare u want to display");
int sum=0;
int m1=s.nextInt();
int n1=s.nextInt();
int m2=s.nextInt();
int n2=s.nextInt();

for(int i=m1;i<m;i++)
{
for (int j=n1;j<n ;j++ )
{
sum=sum+a[i][j];
}
}

System.out.println(sum);
System.out.println();

}
}``````

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

``````import java.io.DataInputStream;
import java.io.IOException;
public class Matrix {
public static void main(String[] ags) throws NumberFormatException, IOException{
int arr[][] = new int;
int result =0;
DataInputStream dis = new DataInputStream(System.in);
System.out.println("enter values");
for(int i=0;i<3;i++){
for(int j=0;j<5;j++){

}
}
System.out.println("result");
for(int i=0;i<3;i++){
for(int j=0;j<5;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println("\n");
}
System.out.println("enter boundries");
for(int i=startval;i<3;i++){
for(int j=endj;j<5;j++){
System.out.print(arr[i][j]+" ");
result = result + arr[i][j];
}
System.out.println("\n");
}
System.out.println("FINAL result .... "+result);
}
}``````

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.