Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
I think it can be solved with dp with a memory of O((m*n)^2) can it be made better?

- Dinesh Sandadi May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
I think it can be solved using DP with memory of O((m*n)^2). Can it be made better?

- Dinesh Sandadi May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

It can be done in m*n*n using kadane algorithm.. Taking each pairs of column and try to apply the kadane in every row

- rahulkumarsk2015 May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem can be solved with dynamic programming you can take a constraint area which you need to maximise and another constraint budget(which remains a constant)

- offshivangig12 May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- GiriRP May 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]]

- adr June 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is 0 - 1 knapsack problem

- Anonymous June 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Raminder June 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}
}

- Sibendu Dey June 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- bansal.sulabh June 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dfs with longest path

- Anonymous September 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex October 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is 0 - 1 knapsack problem

- Daniel June 05, 2018 | 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