Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
#include <iostream>
#include <stdio.h>
//input
int money_u_have = 21;
//Result
int max_area = 0;
int i_x, i_y; //start position of the max area
int endx, endy; //end position of the max area
void calculateArea (int arr[3][3], int px, int py, int max_row, int max_col)
{
int cur_area = 0;
int cost = 0;
for (int i = px; i < px + max_row; i++)
{
for (int j = py; j < py + max_col; j++)
{
printf (" %d ", arr[i][j]);
cur_area++;
cost += arr[i][j];
}
printf ("\n");
}
printf ("\n");
if (max_area < cur_area)
{
if (money_u_have >= cost)
{
max_area = cur_area;
i_x = px;
i_y = py;
endx = px + max_row - 1;
endy = py + max_col - 1;
}
}
}
int main ()
{
int max_row = 4;
int max_col = 3;
int input[4][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}
};
int pos_x = 0;
int pos_y = 0;
for (pos_x = 0; pos_x < max_row - 1; pos_x++)
{
for (pos_y = 0; pos_y < max_col - 1; pos_y++)
{
for (int i = 2; i <= max_row; i++)
{
if (pos_x + i > max_row)
break;
for (int j = 2; j <= max_col; j++)
{
if (pos_y + j > max_col)
break;
calculateArea (input, pos_x, pos_y, i, j);
}
}
}
}
printf ("MAx area %d, with money %d, start %d,%d, end %d,%d \n", max_area,
money_u_have, i_x, i_y, endx, endy);
}
O(n*n*m), uses O(m) memory
from operator import add, sub
import random
def maxseq (s, k):
first = i = cost = 0
r = [0,[0,0]]
def update():
if r[0] < i-first:
r[0] = i-first
r[1] = [first, i]
while i < len(s):
if s[i] + cost <= k:
cost += s[i]
i += 1
else:
update()
cost -= s[first]
first += 1
update()
return r[1]
def maxrect(v, k):
first = 0
end = len(v)
r = [0,[0,0,0,0]]
def update (beg, end, arr):
[b, e] = maxseq (arr, k)
a = (e-b)*(end-beg)
if r[0] < a:
r[0] = a
r[1] = [beg, end, b, e]
return e - b
while first < end:
arr = v[first]
ub = (end - first) * len(arr)
for j in xrange (first, end):
if r[0] < ub:
ub = (end - first) * update(first, j+1, arr)
if j+1 != end:
arr = map(add, arr, v[j+1])
arr = map(sub, arr, v[first])
first += 1
for j in reversed(xrange(first, end)):
if r[0] < (j-first+1)*len(arr):
update(first, j+1, arr)
if first != j:
arr = map(sub, arr, v[j])
first += 1
return r
random.seed(42)
k = random.randint(1, 42)
n = 10
m = 15
v = [[random.randint(1, 7) for _ in range(m)] for _ in range(n)]
for vv in v:
print vv
print k
[a, r] = maxrect(v, k)
for i in xrange(r[0], r[1]):
print v[i][r[2]:r[3]]
public class LargestArea {
public int largestArea(int[][] land, int budget) {
int[][][] area = new int[land.length][land[0].length][land[0].length];
for (int i = 0; i < land.length; i++) {
for (int j = 0; j < land[0].length; j++) {
for (int k = j; k < land[0].length; k++) {
if (k == j)
area[i][j][j] = land[i][j];
else
area[i][j][k] = area[i][j][k - 1] + land[i][k];
}
}
}
int max = Integer.MIN_VALUE, max_area = 0;
for (int i = 0; i < land[0].length; i++) {
for (int j = i; j < land[0].length; j++) {
int starting_k = 0;
int curr_sum = 0;
for (int k = 0; k < land.length; k++) {
curr_sum += area[k][i][j];
if (curr_sum > budget) {
curr_sum = area[k][i][j];
starting_k = k;
}
else if (curr_sum > max) {
max = curr_sum;
max_area = (k - starting_k + 1) * (j - i + 1);
}
}
}
}
return max;
}
public static void main(String args[]) {
int matrix [][]= { {4,6,7}, {3,5,2}, {2,4,5} };
System.out.println(new LargestArea().largestArea(matrix, 16));
}
}
public class LargestRectangularArea {
public static void main(String[] args) {
int[][] plots = { {2,1,7},
{1,1,1},
{0,3,1},
{0,2,1}};
int B = 16;
largestRectangularArea(plots, B);
}
static class Cell {
int leftCol;
int rightCol;
int top;
int bottom;
int totalPLots;
Cell(int leftCol, int rightCol, int top, int bottom, int totalPLots) {
this.leftCol = leftCol;
this .rightCol = rightCol;
this.top = top;
this.bottom = bottom;
this.totalPLots = totalPLots;
}
}
private static void largestRectangularArea(int[][] plots, int b) {
int cols = 3;
int rows = 4;
int[] longestSubarray = new int[rows];
int maxPlots = 0;
Cell maxArea = null;
Cell area;
for(int leftCol = 0 ; leftCol < cols; leftCol++) {
for(int rightCol = leftCol ;rightCol < cols; rightCol++) {
for(int k = 0 ; k < rows; k++) {
longestSubarray[k] = longestSubarray[k] + plots[k][rightCol];
}
area = getAreaWithMaxPlots(leftCol,rightCol,longestSubarray, b);
if(area.totalPLots > maxPlots) {
maxArea =area;
maxPlots = area.totalPLots;
}
}
}
System.out.println("TOP: " + maxArea.top);
System.out.println("BOTTOM: " + maxArea.bottom);
System.out.println("LEFT: " + maxArea.leftCol);
System.out.println("RIGHT: " + maxArea.rightCol);
System.out.println("TOTAL NUMBER OF PLOTS (cells) in the matrix:" + maxArea.totalPLots);
}
private static Cell getAreaWithMaxPlots(int leftCol, int rightCol, int[] arr, int b) {
int sum = 0;
int length =0;
int top = 0;
int bottom = 0;
for(int i = 0 ; i < arr.length; i++) {
if(sum+arr[i] <= b) {
sum = sum + arr[i];
length++;
top = i-length+1;
bottom = i;
} else {
sum = sum + arr[i] - arr[i-length];
}
}
int totalPLots = (rightCol-leftCol+1) * (bottom-top+1);
Cell cell = new Cell(leftCol, rightCol, top, bottom, totalPLots);
return cell;
}
}
O(n^2 * m^2) time and O(n * m) space.
#include <vector>
#include <iostream>
using namespace std;
class Rect
{
public:
Rect(int r1, int c1, int r2, int c2)
: r1_(r1), c1_(c1), r2_(r2), c2_(c2)
{}
int r1_, c1_, r2_, c2_;
};
void ComputeRectSums(vector<vector<int>> &m)
{
for (int r = 0; r < m.size(); ++r)
{
for (int c = 0; c < m[r].size(); ++c)
{
if (r > 0)
{
m[r][c] += m[r - 1][c];
}
if (c > 0)
{
m[r][c] += m[r][c - 1];
}
if (r > 0 &&
c > 0)
{
m[r][c] -= m[r - 1][c - 1];
}
}
}
}
Rect FindPlace(vector<vector<int>> m, int h, int w, int budget)
{
if (h > 0 &&
w > 0 &&
h <= m.size() &&
w <= m[0].size())
{
int delta_h = m.size() - h;
int delta_w = m[0].size() - w;
for (int r1 = 0; r1 <= delta_h; ++r1)
{
int r2 = r1 + h - 1;
for (int c1 = 0; c1 <= delta_w; ++c1)
{
int c2 = c1 + w -1;
int price = m[r2][c2];
if (r1 > 0)
{
price -= m[r1 - 1][c2];
}
if (c1 > 0)
{
price -= m[r2][c1 - 1];
}
if (r1 > 0 &&
c1 > 0)
{
price += m[r1 - 1][c1 -1];
}
if (price <= budget)
{
return Rect(r1, c1, r2, c2);
}
}
}
}
return Rect(-1, -1, -1, -1);
}
Rect LargestArea(vector<vector<int>> m, int budget)
{
if (!m.empty()) {
ComputeRectSums(m);
int h = m.size();
int w = m[0].size();
for (; h > 0 && w > 0; --h, --w)
{
Rect rect(-1, -1, -1, -1);
rect = FindPlace(m, h, w, budget);
if (rect.r1_ >= 0)
{
return rect;
}
rect = FindPlace(m, h - 1, w, budget);
if (rect.r1_ >= 0)
{
return rect;
}
rect = FindPlace(m, h, w - 1, budget);
if (rect.r1_ >= 0)
{
return rect;
}
}
}
return Rect(-1, -1, -1, -1);
}
int main()
{
vector<vector<int>> m = {
{ 4, 6, 7 },
{ 3, 5, 2 },
{ 2, 4, 5 }
};
Rect rect = LargestArea(m, 16);
cout << rect.r1_ << ", " << rect.c1_ << ", " << rect.r2_ << ", " << rect.c2_ << "\n";
return 0;
}
Assumptions: matrix is a proper rectangle i.e. each sub-array has equal length. We need to check all possible rectangular plots from each plot unless cost is already more than budget. Algo starts from [0,0]. No rectangular plot is recomputed. Worst case is O(M^2.N^2)
public static int findMaxArea(int [] [] matrix, int B){
int rows = matrix.length;
int columns = matrix[0].length;
int count = 0,sum = 0,tempCount =0;
for(int c = 0; c < columns; c++){
for(int r = 0; r < rows; r++){
for(int i = c; i < columns; i++){
sum = 0;
tempCount = 0;
for(int j = r; j < rows; j++){
for(int y = c; y <= i; y++){
sum += matrix[j][y];
tempCount++;
}
if(sum <= B && tempCount > count){
count = tempCount;
}else if(sum > B){
break;
}
}
}
}
}
return count;
}
LeetCode 363. Max Sum of Rectangle No Larger Than K
- Sithis April 04, 2019