ADP Interview Question
Applications DevelopersCountry: India
#include<bits/stdc++.h>
using namespace std;
#define MAX 105
int a[MAX][MAX];
int dp[MAX][MAX],visited[MAX][MAX];
int n,m;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
int boundedBy(int i,int j,int k)
{
if(i<0 || j<0 || i>=n || j>=m)
return 0;
if(a[i][j]>k)
return a[i][j];
if(visited[i][j]) return INT_MAX;
visited[i][j] = 1;
int r = INT_MAX;
for(int dir = 0;dir<4;dir++)
{
int nx = i + dx[dir];
int ny = j + dy[dir];
r = min(r,boundedBy(nx,ny,k));
}
return r;
}
void mark(int i,int j,int k)
{
if(i<0 || j<0 || i>=n || j>=m)
return;
if(a[i][j]>=k)
return;
//cout<<i<<" "<<j<<" "<<k<<endl;
if(visited[i][j]) return ;
visited[i][j] = 1;
for(int dir = 0;dir<4;dir++)
{
int nx = i + dx[dir];
int ny = j + dy[dir];
mark(nx,ny,k);
}
dp[i][j] = max(dp[i][j],k);
}
struct node
{
int i,j,key;
node(int x,int y,int k)
{
i = x;
j = y;
key = k;
}
};
bool compare(node a,node b)
{
return a.key>b.key;
}
vector<node> store;
int main()
{
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
store.clear();
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin>>a[i][j];
store.push_back(node(i,j,a[i][j]));
}
}
memset(dp,0,sizeof(dp));
sort(store.begin(),store.end(),compare);
for(int i = 0;i<store.size();i++)
{
memset(visited,0,sizeof(visited));
// cout<<store[i].i<<" "<<store[i].j<<" ";
int aux = boundedBy(store[i].i,store[i].j,store[i].key);
if(aux>store[i].key)
{
//cout<<store[i].key<<" "<<aux<<endl;
memset(visited,0,sizeof(visited));
mark(store[i].i,store[i].j,aux);
}
//cout<<endl;
}
// cout<<boundedBy(1,2,3)<<endl;
long long result =0 ;
for(int i = 0;i<n;i++)
{
//cout<<endl;
for(int j = 0;j<m;j++)
{
// cout<<max(dp[i][j]-a[i][j],0)<<" ";
result = result + max(0,dp[i][j]-a[i][j]);
}
}
cout<<result<<endl;
}
return 0;
}
def checkMatrix(w, h, Matrix):
flag = True
count = tmpcnt = 0
#print(Matrix)
while flag:
for i in range(0, w):
for j in range(0, h):
if (i == 0 or j == 0) or (i == w - 1 or j == h - 1):
pass#print(".")
else:
endtoend = min(Matrix[i][0], Matrix[i][h-1])
#print(endtoend, Matrix[i][0], Matrix[i][h-1])
uptodown = min(Matrix[i-1][j], Matrix[i+1][j])
leftright = min(Matrix[i][j-1], Matrix[i][j+1])
newList = [Matrix[i-1][j], Matrix[i][j-1], Matrix[i+1][j], Matrix[i][j+1]]
minval = min(newList)
if minval > Matrix[i][j]:#Matrix[i][j] < endtoend and Matrix[i][j] < uptodown:# and
Matrix[i][j] += 1
count += 1
elif endtoend > Matrix[i][j]:
#if i-1 != 0 and j-1 != 0 and i+1 != w - 1 and j-1 != h - 1:
if w < h:
if endtoend == Matrix[i][j] + 1:
Matrix[i][j] += 1
count += 1
else:
if Matrix[i-1][j] > Matrix[i][j]:
Matrix[i][j] += 1
count += 1
# if h > w and uptodown > Matrix[i][j]:
# Matrix[i][j] += 1
# count += 1
#
# else:#if w >= h and uptodown > Matrix[i][j]:
# Matrix[i][j] += 1
# count += 1
if tmpcnt == count and i == w - 1 and j == h - 1:
flag = False
tmpcnt = count
#print("\n", count, Matrix)
return count
def GetWaterLevel(input1,input2,input3):
global flag
w, h = input1, input2
count = 0
newList = []
Matrix = [input3[i:i+h] for i in range(0, len(input3), h)]
return checkMatrix(w, h, Matrix)
GetWaterLevel(4, 6, [3, 3, 4, 4, 6, 2, 3, 1, 3, 6, 1, 6, 7, 3, 1, 6, 6, 1])
GetWaterLevel(6, 3, [3, 3, 7, 3, 1, 3, 4, 3, 1, 4, 2, 6, 4, 1, 4, 2, 4, 1])
import java.io.*;
import java.util.*;
public class CandidateCode
{
public static int GetWaterLevel(int input1,int input2,int[] input3)
{
//Write code herea
//Write code here
int len=input1;
int br=input2;
int A[][]=new int[len][br];
int height[]=new int[input3.length];
height=input3;
int count=0;
int num=0;
int check=0;
if(len<1 || len>10 || br<1 || br>10)
{
return -1;
}
for(int i=0;i<height.length;i++)
{
if(height[i]<1 || height[i]>10)
return -1;
}
for(int i=0;i<len;i++)
{
for(int j=0;j<br;j++)
{
A[i][j]=height[count];
count++;
}
}
for(int i=1;i<=(len-2);i++)
{
for(int j=1;j<=(br-2);j++)
{
int min=11;
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j]<min)
min=A[i+1][j];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j-1]<min)
min=A[i][j-1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+num;
A[i][j]=A[i][j]+num;
}
if((A[i][j]==A[i][j+1]) || (A[i][j]==A[i][j-1]))
{
if(A[i][j]==A[i][j+1])
{
min=11;
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i-1][j+1]<min)
min=A[i-1][j+1];
if((j+2)<br)
{
if(A[i][j+2]<min)
min=A[i][j+2];
}
if(A[i+1][j+1]<min)
min=A[i+1][j+1];
if(A[i+1][j]<min)
min=A[i+1][j];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j+1]=A[i][j+1]+num;
}
}
else if(A[i][j]==A[i][j-1])
{
min=11;
if((j-2)>=0)
{
if(A[i][j-2]<min)
min=A[i][j-2];
}
if(A[i-1][j-1]<min)
min=A[i-1][j-1];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j-1]<min)
min=A[i+1][j-1];
if(A[i+1][j]<min)
min=A[i+1][j];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j-1]=A[i][j-1]+num;
}
}
}
if((A[i][j]==A[i+1][j]) || (A[i][j]==A[i-1][j]))
{
if(A[i][j]==A[i+1][j])
{
min=11;
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i+1][j-1]<min)
min=A[i+1][j-1];
if((i+2)<len)
{ if(A[i+2][j]<min)
min=A[i+2][j];
}
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j+1]<min)
min=A[i+1][j+1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i+1][j]=A[i+1][j]+num;
}
}
else if(A[i][j]==A[i-1][j])
{
min=11;
if((i-2)>=0)
{
if(A[i-2][j]<min)
min=A[i-2][j];
}
if(A[i-1][j-1]<min)
min=A[i-1][j-1];
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i+1][j]<min)
min=A[i+1][j];
if(A[i-1][j+1]<min)
min=A[i-1][j+1];
if(A[i][j+1]<min)
min=A[i][j+1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j-1]=A[i-1][j]+num;
}
}
}
}
}
for(int i=0;i<len;i++)
{
for(int j=0;j<br;j++)
{
System.out.print(A[i][j]+"\t");
}
System.out.println();
}
return check;
}
}
import java.io.*;
import java.util.*;
public class CandidateCode
{
public static int GetWaterLevel(int input1,int input2,int[] input3)
{
//Write code herea
//Write code here
int len=input1;
int br=input2;
int A[][]=new int[len][br];
int height[]=new int[input3.length];
height=input3;
int count=0;
int num=0;
int check=0;
if(len<1 || len>10 || br<1 || br>10)
{
return -1;
}
for(int i=0;i<height.length;i++)
{
if(height[i]<1 || height[i]>10)
return -1;
}
for(int i=0;i<len;i++)
{
for(int j=0;j<br;j++)
{
A[i][j]=height[count];
count++;
}
}
for(int i=1;i<=(len-2);i++)
{
for(int j=1;j<=(br-2);j++)
{
int min=11;
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j]<min)
min=A[i+1][j];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j-1]<min)
min=A[i][j-1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+num;
A[i][j]=A[i][j]+num;
}
if((A[i][j]==A[i][j+1]) || (A[i][j]==A[i][j-1]))
{
if(A[i][j]==A[i][j+1])
{
min=11;
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i-1][j+1]<min)
min=A[i-1][j+1];
if((j+2)<br)
{
if(A[i][j+2]<min)
min=A[i][j+2];
}
if(A[i+1][j+1]<min)
min=A[i+1][j+1];
if(A[i+1][j]<min)
min=A[i+1][j];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j+1]=A[i][j+1]+num;
}
}
else if(A[i][j]==A[i][j-1])
{
min=11;
if((j-2)>=0)
{
if(A[i][j-2]<min)
min=A[i][j-2];
}
if(A[i-1][j-1]<min)
min=A[i-1][j-1];
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j-1]<min)
min=A[i+1][j-1];
if(A[i+1][j]<min)
min=A[i+1][j];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j-1]=A[i][j-1]+num;
}
}
}
if((A[i][j]==A[i+1][j]) || (A[i][j]==A[i-1][j]))
{
if(A[i][j]==A[i+1][j])
{
min=11;
if(A[i-1][j]<min)
min=A[i-1][j];
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i+1][j-1]<min)
min=A[i+1][j-1];
if((i+2)<len)
{ if(A[i+2][j]<min)
min=A[i+2][j];
}
if(A[i][j+1]<min)
min=A[i][j+1];
if(A[i+1][j+1]<min)
min=A[i+1][j+1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i+1][j]=A[i+1][j]+num;
}
}
else if(A[i][j]==A[i-1][j])
{
min=11;
if((i-2)>=0)
{
if(A[i-2][j]<min)
min=A[i-2][j];
}
if(A[i-1][j-1]<min)
min=A[i-1][j-1];
if(A[i][j-1]<min)
min=A[i][j-1];
if(A[i+1][j]<min)
min=A[i+1][j];
if(A[i-1][j+1]<min)
min=A[i-1][j+1];
if(A[i][j+1]<min)
min=A[i][j+1];
num=min-A[i][j];
if(num<0)
{
check=check+0;
}
else
{
check=check+2*num;
A[i][j]=A[i][j]+num;
A[i][j-1]=A[i-1][j]+num;
}
}
}
}
}
for(int i=0;i<len;i++)
{
for(int j=0;j<br;j++)
{
System.out.print(A[i][j]+"\t");
}
System.out.println();
}
return check;
}
}
Is this your homework? I literally just had this as an interview question yesterday and whiffed only to completely figure it out 5 minutes after leaving the building. Just know that you can do it in O(n) time with O(1) space.
- JoseCuervo April 01, 2016