Google Interview Question
SDE1sCountry: United States
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int ar[][] = { {1,2,3,1},
{0,1,4,2},
{1,9,10,4}
};
maxArea(ar,11);
}
public static void maxArea(int ar[][],int limit){
int costs[][] = new int[ar.length][ar[0].length];
for(int i=0;i<ar.length;i++){
for(int j=0;j<ar[0].length;j++){
int cost=0;
if(i>0){
cost = cost + costs[i-1][j];
}
if(j>0){
cost= cost +costs[i][j-1];
}
if(i>0 && j >0){
cost = cost-costs[i-1][j-1];
}
costs[i][j]=cost+ar[i][j];
}
}
// System.out.println(Arrays.deepToString(costs));
int p=0,q=0,r=0,s=0;
int maxArea = 0;
for(int i=-1;i<ar.length;i++){
for(int j=-1;j<ar[0].length;j++){
for(int k=i+1;k<ar.length;k++){
for(int l=j+1;l<ar[0].length;l++){
int cost=costs[k][l];
if(i > 0){
cost = cost-costs[i][l];
}
if(j > 0 ){
cost = cost-costs[k][j];
}
if( i > 0 && j >0){
cost = cost + costs[i][j];
}
if(cost <= limit){
int area = (k-i) * (l-j);
if(maxArea < area){
p=i;
q=j;
r=k;
s=l;
maxArea=area;
}
}
}
}
}
}
// System.out.println(p+" "+q+" "+r+" "+s);
for(int i=p+1;i<=r;i++){
for(int j=q+1;j<=s;j++){
System.out.print(ar[i][j] + " " );
}
System.out.println();
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
using namespace std;
#define DEBUG
int **arr, **arr1, R, C;
int maxLandVal = 11;
int maxBlock = 0;
void move(int r, int c, int landVal, int numBlocks, string s)
{
if (arr1[r][c] != 0 && arr1[r][c] <= numBlocks)
return;
++numBlocks;
landVal = landVal + arr[r][c];
arr1[r][c] = numBlocks;
if (landVal > 11 )
return;
if (landVal == maxLandVal && maxBlock < numBlocks)
{
maxBlock = numBlocks;
cout << "land value: " << landVal << endl;
cout << s << endl;
}
if (r < R - 1) move(r + 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (r > 0) move(r - 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c < C - 1) move(r, c + 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c > 0) move(r, c - 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
arr1[r][c] = 0;
}
int main()
{
freopen("Text.txt", "r", stdin);
setbuf(stdout, NULL);
cin >> R;
cin >> C;
arr = new int*[R];
arr1 = new int*[R];
for (int i = 0; i < R; i++)
{
arr[i] = new int[C];
arr1[i] = new int[C];
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> arr[i][j];
arr1[i][j] = 0;
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout<< arr[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
move(i, j, 0, 0, "");
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
using namespace std;
#define DEBUG
int **arr, **arr1, R, C;
int maxLandVal = 11;
int maxBlock = 0;
void move(int r, int c, int landVal, int numBlocks, string s)
{
if (arr1[r][c] != 0 && arr1[r][c] <= numBlocks)
return;
++numBlocks;
landVal = landVal + arr[r][c];
arr1[r][c] = numBlocks;
if (landVal > 11 )
return;
if (landVal == maxLandVal && maxBlock < numBlocks)
{
maxBlock = numBlocks;
cout << "land value: " << landVal << endl;
cout << s << endl;
}
if (r < R - 1) move(r + 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (r > 0) move(r - 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c < C - 1) move(r, c + 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c > 0) move(r, c - 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
arr1[r][c] = 0;
}
int main()
{
freopen("Text.txt", "r", stdin);
setbuf(stdout, NULL);
cin >> R;
cin >> C;
arr = new int*[R];
arr1 = new int*[R];
for (int i = 0; i < R; i++)
{
arr[i] = new int[C];
arr1[i] = new int[C];
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> arr[i][j];
arr1[i][j] = 0;
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout<< arr[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
move(i, j, 0, 0, "");
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
using namespace std;
#define DEBUG
int **arr, **arr1, R, C;
int maxLandVal = 11;
int maxBlock = 0;
void move(int r, int c, int landVal, int numBlocks, string s)
{
if (arr1[r][c] != 0 && arr1[r][c] <= numBlocks)
return;
++numBlocks;
landVal = landVal + arr[r][c];
arr1[r][c] = numBlocks;
if (landVal > 11 )
return;
if (landVal == maxLandVal && maxBlock < numBlocks)
{
maxBlock = numBlocks;
cout << "land value: " << landVal << endl;
cout << s << endl;
}
if (r < R - 1) move(r + 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (r > 0) move(r - 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c < C - 1) move(r, c + 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c > 0) move(r, c - 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
arr1[r][c] = 0;
}
int main()
{
freopen("Text.txt", "r", stdin);
setbuf(stdout, NULL);
cin >> R;
cin >> C;
arr = new int*[R];
arr1 = new int*[R];
for (int i = 0; i < R; i++)
{
arr[i] = new int[C];
arr1[i] = new int[C];
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> arr[i][j];
arr1[i][j] = 0;
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout<< arr[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
move(i, j, 0, 0, "");
}
}
}
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
using namespace std;
#define DEBUG
int **arr, **arr1, R, C;
int maxLandVal = 11;
int maxBlock = 0;
void move(int r, int c, int landVal, int numBlocks, string s)
{
if (arr1[r][c] != 0 && arr1[r][c] <= numBlocks)
return;
++numBlocks;
landVal = landVal + arr[r][c];
arr1[r][c] = numBlocks;
if (landVal > 11 )
return;
if (landVal == maxLandVal && maxBlock < numBlocks)
{
maxBlock = numBlocks;
cout << "land value: " << landVal << endl;
cout << s << endl;
}
if (r < R - 1) move(r + 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (r > 0) move(r - 1, c, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c < C - 1) move(r, c + 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
if (c > 0) move(r, c - 1, numBlocks, landVal, s + "[" + to_string(r) + to_string(c) + "]");
arr1[r][c] = 0;
}
int main()
{
freopen("Text.txt", "r", stdin);
setbuf(stdout, NULL);
cin >> R;
cin >> C;
arr = new int*[R];
arr1 = new int*[R];
for (int i = 0; i < R; i++)
{
arr[i] = new int[C];
arr1[i] = new int[C];
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cin >> arr[i][j];
arr1[i][j] = 0;
}
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
cout<< arr[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
move(i, j, 0, 0, "");
}
}
}
Using dp: time O(m*m*n*n), space(m*n*n)
#include <iostream>
using namespace std;
class myClass
{
int** matrix;
int M;
int N;
public :
myClass()
{
cin>>M;
cin>>N;
matrix = new int*[M];
for(int i=0; i<M; i++)
{
matrix[i] = new int[N];
}
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
cin>>matrix[i][j];
}
}
}
int FindArea(int budget)
{
int dp1[M][N][N];
int dp2[M][N][N];
int dp3[M][N][N];
int maxArea = 0;
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
dp1[i][j][j] = matrix[i][j];
}
}
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
for(int k=j+1; k<N; k++)
{
dp1[i][j][k] = dp1[i][j][k-1] + dp1[i][k][k];
}
}
}
for(int i=0; i<M; i++)
{
for(int j=0; j<N; j++)
{
for(int k=j; k<N; k++)
{
dp2[i][j][k] = dp1[i][j][k];
//cout<<dp2[i][j][k]<<endl;
if(dp2[i][j][k] <= budget && maxArea < (k-j+1))
{
maxArea = k-j+1;
}
}
}
}
int count = 1;
for(int i=0; i<M-count; i++)
{
for(int j=0; j<N; j++)
{
for(int k=j; k<N; k++)
{
dp3[i][j][k] = dp2[i][j][k] + dp1[i+count][j][k];
if(dp3[i][j][k] <= budget && maxArea < (count + 1)*(k-j+1))
{
maxArea = (count + 1)*(k-j+1);
}
}
}
for(int l=0; l<M-count; l++)
{
for(int j=0; j<N; j++)
{
for(int k=j; k<N; k++)
{
dp2[l][j][k] = dp3[l][j][k];
}
}
}
count++;
}
return maxArea;
}
};
int main() {
myClass* obj = new myClass();
cout<<obj->FindArea(11);
}
So easy
- Anonymous December 22, 2017