Google Software Engineering Mock Interview: John Conway's "Game of Life"
Vložit
- čas přidán 28. 07. 2024
- 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
Watch our technical coding mock interview with Angie and Simon Ayzman (Software Engineer at Google) as he solves John Conway's famous "Game of Life" software engineering interview question.
Simon implements a method to update the board game continuously to its next state. This software engineering interview question is commonly asked at Google and other top tech companies.
Learn more about Simon here: www.simonayzman.com/
Chapters -
00:00 - Introduction
00:53 - Question
02:30 - Clarifying questions
09:37 - Answer
21:31 - Follow-up questions
23:47 - Test cases
31:56 - Interview analysis
Watch more videos here:
- Amazon SWE answers system design interview question: • Amazon System Design I...
- Google SWE answers algorithms interview question: • Google Software Engine...
- Google TPM answers Tiktok system design interview question: • System Design Mock Int...
- Microsoft SWE answers algorithms interview question: • Microsoft Software Eng...
👉 Subscribe to our channel: bit.ly/exponentyt
📧 Sign up for our email newsletter with PM interview lessons: bit.ly/exponentpm
🕊️ Follow us on Twitter: bit.ly/exptweet
💙 Like us on Facebook for special discounts: bit.ly/exponentfb
📷 Check us out on Instagram: bit.ly/exponentig
ABOUT US:
Did you enjoy this interview question and answer? Want to land your dream career? Exponent is an online community, course, and coaching platform to help you ace your upcoming interview. Exponent has helped people land their dream careers at companies like Google, Microsoft, Amazon, and high-growth startups. Exponent is currently licensed by Stanford, Yale, UW, and others.
Our courses include interview lessons, questions, and complete answers with video walkthroughs. Get access to hours of real interview videos, where we analyze what went right or wrong, as well as our 1000+ community of expert coaches and industry professionals, to help you get your dream job and more!
#softwareengineer #softwareengineering #tech #software #entrepreneurship #product #softwaredeveloper
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
If only "solving life" was this simple! And in less than 42 lines of code to boot 😉 Great to be back, Exponent!
Always a pleasure!
Clean code. Calm. Confident!
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.
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.
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
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...
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?
@@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.
@@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.
What is the time and space complexity of this algorithm ?
It would be O(m * n), where m and n are the number of rows and columns in the grid, respectively.
I thought that he is clément mihailescu😂
Hard to compete with the OG Algo Expert 😂
😂