Snapdeal Interview Question
SDE1sCountry: India
Interview Type: In-Person
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.
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)
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)))
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']
#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);
}
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)
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]
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);
}
}
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();
}
}
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);
}
}
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:
Example 2:
This is the code for this solution, you can use:
to generate a Matrix of size n,m with random integers, and:
to print the matrix. The method:
will preprocess the matrix with the running sum and the method:
will compute the sum of all the elements in the Matrix included between upperLeft and lowerRight vertices.
Here is the complete code:
- gigi84 December 24, 2014