Zillow Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
/*
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;
}
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