Snapdeal Interview Question for SDE1s


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[0].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[0].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[0].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);
	}
}

- gigi84 December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- madhur.eng May 14, 2015 | Flag
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.

- keshy December 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- using two for loops December 23, 2014 | Flag Reply
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)

- Anonymous December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankit Tripathi December 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhishek January 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- karthik339 January 08, 2015 | Flag
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[0])):
			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)))

- Anonymous December 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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[0])):
			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[0])):
			for c in range(a+1, len(data)):
				for d in range(b+1, len(data[0])):
					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']

- Sidharth Shah December 24, 2014 | Flag
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[3][5] = {{1,3,5,1,8},{8,3,5,3,7},{6,3,9,6,0}};
        int cord[4];
        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[0];i<= cord[2];i++)
        {
                for(j=cord[1];j<= cord[3];j++)
                {
                total = matrix[i][j] + total;
                }
        }
        printf("%d\n",total);
}

- kshitiz gupta December 24, 2014 | Flag Reply
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)

- Ravi teja December 26, 2014 | Flag Reply
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]

- alonsomh December 26, 2014 | Flag Reply
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[0])

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

x = (0,2)

y = (2,4)

add = 0

for val in range(x[0],y[0]+1):
    add += b[val][y[1]] - b[val][x[1]-1]

print add

- pavan8085 January 03, 2015 | Flag Reply
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};
int add=0;
for(int i=x[0];i<=y[0];i++)
{
for(int j=x[1];j<=y[1];j++)
{
add += arr[i][j];
}
}
System.out.println(add);

}
}

- Pradeep kumar R S January 21, 2015 | Flag Reply
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[10][10];
		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();

	}
}

- Hanamant August 11, 2016 | Flag Reply
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[3][5];
		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++){
					
				 arr[i][j] = Integer.parseInt(dis.readLine());
				
			}
		}
		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");
		int startval = Integer.parseInt(dis.readLine());
		int endj = Integer.parseInt(dis.readLine());
		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);
	}
}

- umamahes December 29, 2014 | 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