The interviewer first demoed Conway's Game of Life in the browser (I had never heard of it before), then pasted starter code into CoderPad:
next_gen computes the next generation of the board. There is a helper _process_cell(old_board, new_board, row, col) that decides whether a cell lives or dies based on its neighbor count. The initial board is random with a probability p between 0 and 1, so the board can be very dense and you can't just store the live cells sparsely.
The task was to scale it up to 1M x 1M.
The interviewer didn't give any details. He didn't mention that you could use file storage, you have to ask for it yourself. Only after I asked, and worked out that memory would not be enough and estimated the order of magnitude of memory needed, did he give me a file system helper, read(name, offset, length) and append(name, data).
The idea is a sliding window with local updates. Each new cell only depends on the rows above and below it, so you handle the boundaries, compute the state of the middle row, and append it to the output file. Then the window moves down. You don't have to write the live/dead logic yourself, you just use the file system and design the update window.
I spent way too much time at the start understanding what was being asked. I didn't know what to write or where the code should go, and I thought it was an algorithm problem where you use a set or something to do local updates. Turns out he was just testing engineering implementation.
Discussion
Loading comments…