## Zillow Interview Question

Country: United States

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

It is 2*2^31*2^31/32 ----> that is 2 arrays, each with (2^31 arraylength) no of rows and each row contains ((2^31)/32 ( integers)) as columns.

To represent the state, we need say 00 for 'O' and 11 for 'X' and 01 or 10 for 'empty'.

So one array stores the state of O as 0 and rest as1s,
and in, Other array store the stae of X as 1 and rest as 0s.

Now by superimposing both together you can get the logic!

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

I think you can store each line as an integer, that is composed by 32 bits. You can use each bit of the integer to represents a single square, if the bit is 0 then the square contains a O if it is 1 the square contains an X. In this case you would need 2^31 Integers to store the entire board. You can preprocess the board to store each configuration as "winning for X", "winning for O" or "Draw".

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

Does anyone have any further suggestion on how to improve on this?

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

The size of the grid is 2^31 x 2^31 so you need 2^31 bits, not an integer that can go up to 2^31. For one line, you'd need 2^31/32 integers, which is a bit too much memory-wise.

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

An integer is composed by 32 bit, so the lowlevel representation of an integer will be 10011010100100100......11001010, thus I think you can use just one integer to represent up to 32 squares. I assumed that we had to represent final configurations of the game to check if there is the winner, then each square will be filled with X or O. we need just 2 values that means that each square can be represented with just 1 bit. If the integer has 32 bits you can represent each line with 1 integer

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

Obviously, this problem must use bit operation to store the stats sine at each cell we only has three status: empty (00), occupied by X(01), and occupied by O(10). So each cell can be stored by two bits. So we only need 2*2^31*2^31 bits to store the configure. That's right.

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

2 Arrays of 32 integers each.
In one array, the rows are stored, blanks are represented by 0
In another, the columns are stored, blanks are represented by 1

This is so that, the empty cells can be distinguished

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

You have too few integers and even if the size of the board was that small, you wouldn't be able to distinguish squares from each other with this strategy

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

Obviously, we can store 4 kind of lines consists of x or o signs. This is horizontal, vertical, and two diagonal kind of lines. For each line, store coordinates of its ends. Also, maintain hash table to map coordinates to collection of lines ending in particular point.
When putting particular symbol to some point, extract up to 8 lines ending at that point and update set of lines on the map in O(1) time.
Checks for winner in O(1) time.

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.

### 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.