Google Software Engineering Mock Interview: John Conway's "Game of Life"

[@tryexponent]

Don't leave your software engineering career path to chance. Make sure you're interview-ready with Exponent's software developer interview prep course. Start free. bit.ly/3zsYnWc

[@simonayzman]

If only "solving life" was this simple! And in less than 42 lines of code to boot 😉 Great to be back, Exponent!

[@tryexponent]

Always a pleasure!

[@richardwalker3760]

His in-place solution of using 2's and 3's was super nifty, but specifying 0->1 = 2 and 1->0 = 3, is backwards. If he'd reversed it, (0->1=3 and 1->0=2), he could have skipped the cleanup step by simply always reading each cell as (grid[row][col]&1). This converts 3's to 1's and 2's to 0's in-place without needing any additional sweeps of the matrix.

[@simonayzman]

That's a fair point, if we can assume that the consumer "reading" the grid is able to interpret these new values like you're suggesting. From an implementor's perspective, you might usually prefer to mask implementation details like the 2's and 3's part from your consumers.

[@saivamsinagulapalli4456]

Clean code. Calm. Confident!

[@goeo_]

ehh does using 2s and 3s really count as doing this in place? yes, the 1s and 0s being python integers makes it take the same amount of space but realistically a cell would be one bit each, and by adding 2s and 3s you're adding another bit per cell, doubling the space - not very different than the tuple idea. i think you need to use _some_ additional space for this, but it could probably be constant

[@carbs9132]

I don't think that you can do this in constant space. His solution was O(m*n) space, because as you said, he doubled the amount of bits representing the board (from 1 bit to represent 0/1 to 2 bits representing 0/1/2/3). You could obviously do it in O(min(m,n)) space, by just going row by row, or column by column (whichever is smaller), and remembering the previous row/column. There is no "smarter" order to traverse the board to save space - and you can prove this by basically showing that the border length between "changed" and "unchanged" squares, as you traverse and change all squares, is at least O(min(m,n)) at some point (in fact, it can be shown that it's O(min(m,n)) when exactly half the squares were changed). So, the only choice you have, is to somehow be smart and reason about previous board states, like "OK, for this changed value, it's now 1, so previously it had to be either 1 with blablabla...", so basically a bunch of if cases, and try to reduce the space to constant doing that - however it just doesn't seem possible to me. Maybe you could prove so using some entropy arguments...

[@CarloLobrano]

I'm not sure he's changing the size of the grid using 2s and 3s, since the matrix is already allocating space for integers, which takes into account values bigger than 1 and 0. Or am I missing something?

[@simonayzman]

@@CarloLobrano I think the idea is that if you stored the living state using a boolean / bit, rather than an integer, using "memory state" for the 2's and 3's would mean a step-up in memory usage.

[@CarloLobrano]

@@simonayzman theoretically yes, and it is important to note in an interview, practically, being the code written in Python, the memory is still allocated (and so "used") the same way as Python does not make any difference between boolean or integer, or other types. If the code were written in C/C++, or Rust, then yes, it would've made a difference.

[@nnn2689]

What is the time and space complexity of this algorithm ?

[@simonayzman]

It would be O(m * n), where m and n are the number of rows and columns in the grid, respectively.

[@Sandeep-zd6dq]

I thought that he is clément mihailescu😂

[@simonayzman]

Hard to compete with the OG Algo Expert 😂

[@wilsharo]

😂