Google电面。。被完虐。。

illumi 发表于 2016-10-21 09:38
反正他一直强调n非常大，问我怎么才能fit into memory，我说了map reduce分割文件他也不太满意的样子，最 ...

我知道了！！！ 可能就是楼下说的！ 一次只需要读入三行数据
再用一行的extra memory 存储上一次状态就可以~
我当时候面snapchat第一轮就跪在这里。。。 早看到这个就好了。。。

我觉得k很大的话就用一个hashmap存key：初始状态，value:下一个状态，省去重复计算。
n很大可不可以对于每个点，只取它周围八个邻居，也就是一次只读9个点，更新中心点的状态，再读下一个点的9个以此类推

存三行怎么弄？应该不能update一部分，要先mark然后update全部吧

我觉得可以分两部分了。
如果matrix上的light很少。可以按稀疏矩阵的方式来处理。
如果Light很多。可以用一个3x3的矩阵去扫描原来这个矩阵。用新矩阵的(1,1)对着全部位置扫一遍就好了。

关键是N太大的话，怎么每次读取只读一部分呢

申请人 太多了，他们根部不在乎

想请教下大家 有什么好的办法 after k steps，求状态？ － 除了一次一次的求 O(K).