Zillow Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

You got excelling question asked Lively, Which organization and where ? Are you Fresh graduate, It seems questions are directed towards your academics and logics.

- hprem991 July 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Idea: 
- dynamic programming, we are interested in the max free square at x,y = FLS(x,y)
  - if (x,y) is free: the new point can form a new free square of min(FLS(x+1,y),FLS(x,y+1),FLS(x+1,y+1)) 
	note: the last FLS(x+1, y+1) can be optimized but it would work like this
  - if (x,y) is not free: it will never participate in an other free square
    note: even if x,y is not free, x+1,y / x,y+1 can very well contain a max square, so we need to look there
  - base case(s), sigle square with size one at the right and bottom border of the matrix, if free: 1 if there is a tree: 0

matrix mxn: boolean two dimensional array, 0<=x<m, 0<=y<n

FLS stands for find largest free square
FLS(x,y) returns the edge size of the free square starting at (x,y) not the max edge size of any square within square (x,y)(m,n)

             / if M[x,y] = 1: 0, FLS(x+1, y), FLS(x, y+1)   | the recursion is needed to search further, the max size at x,y is 0
            /  if M[x,y] = 0 and 
FLS(x,y) = |       if x = m-1: 1
            \      if y = n-1: 1
             \ all other cases: min(FLS(x+1, y), FLS(x,y+1), FLS(x+1,y+1)) + 1
			     
				 while going through the FLS - recursion, remember largest square

time complexity O(n*m) / don't see any optimization
space complexity O(n*m) / can be optimized with a bottom up method to something like min(m,n) + 1
max stack depth O(n+m) / can be optimized if doing bottom up instead of memozation
*/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

using namespace std;

class FLS
{
private:
	int m; // matrix x dimension
	int n; // matrix y dimmension
	const vector<vector<bool>>& matrix; // matrix with free/occupied squares (free=false, occupied=true)
	vector<vector<int>> mt; // memotable that holds the already calculated squares
	int maxs = 0; // greates so far seen sidelength
	int maxs_x = 0; // x position where the greates sidelength was seen
	int maxs_y = 0; // y position where ... 

public:
	FLS(const vector<vector<bool>>& amatrix) : matrix(amatrix)
	{
		n = matrix.size();
		if (n == 0) throw invalid_argument("matrix y-dimension = 0");
		m = matrix[0].size();
		if (m == 0) throw invalid_argument("matrix x-dimension = 0");
		mt = vector<vector<int>>(n, vector<int>(m, -1)); // memotable
	}

	int Solve(int x, int y)
	{
		int i = 0;

		int res = mt[y][x]; // check memoization table
		if (res != -1) return res; // we hit a memoized entry, return it

		if (x == m - 1 || y == n - 1)
		{
			res = matrix[y][x] ? 0 : 1; // basecase
		}
		else if (!matrix[y][x])
		{
			int s1 = Solve(x + 1, y);
			int s2 = Solve(x, y + 1);
			res = min(s1, s2);
			if (res > 0) // optimze min(s1,s2,s3) by only looking at the single point the recursion didn't look
			{
				if (!matrix[y + res][x + res]) res++;
			}
			else 
			{
				res = 1;
			}
		}
		else 
		{
			Solve(x + 1, y);
			Solve(x, y + 1);
			res = 0;
		}

		if(res > maxs) 
		{
			maxs = res;
			maxs_x = x;
			maxs_y = y;
		}

		mt[y][x] = res; // memoize
		return res;
	}

	int get_M() const { return m; }
	int get_N() const { return n; }
	int get_X() const { return maxs_x; }
	int get_Y() const { return maxs_y; }
	int get_S() const { return maxs; }
};

int main()
{
	vector<vector<bool>> matrix  {
		{ 1, 0, 1, 0, 1, 0, 0 },
		{ 0, 0, 1, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 0, 0, 0, 0, 0 },
		{ 0, 0, 1, 1, 1, 0, 0 },
		{ 0, 0, 0, 1, 0, 0, 0 } };

	FLS fls(matrix);
	fls.Solve(0, 0);

	cout << "matrix of dimension " << fls.get_M() << "x" << fls.get_N() << endl
		<< " -found largest square with side length: " << fls.get_S() << " at position " << fls.get_X() << ", " << fls.get_Y() << endl;
}

- Chris July 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is like finding maximum square of all 1's in a boolean matrix.Standard dp question!!

- rishavsahayiit July 03, 2016 | 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