## Zillow Interview Question for Software Engineers

• 0
of 0 votes

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.

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

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

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