Google电面。。被完虐。。

follow up答题方向感觉应该是拓展到多台机器并行计算,MPI之类的.

follow-up map-reduce, 检查boundary

tailofjune 发表于 2016-10-21 07:13
follow up答题方向感觉应该是拓展到多台机器并行计算,MPI之类的.

说了这个，他继续问只有一台machine怎么办。。

何打发123 发表于 2016-10-21 07:04
感谢楼主！ 感觉就是life game~~ 然后如果n很大的话 就存亮的点坐标就好了 不用存整个matrix~ 但是k很大的 ...

这个也说了，但是只能针对sparse的。。

我觉得Follow up的问题是要用解决稀疏矩阵点积的方法来解决。
我想的方法是，把所有亮灯的坐标和状态存到一个hashtable（key(坐标),value(state)），遍历matrix的时候，按坐标查找周围的灯就好了。

补充内容 (2016-10-21 07:53):
检查完当前位置的状态后要更新hashtable。

illumi 发表于 2016-10-21 07:45
这个也说了，但是只能针对sparse的。。

说了这个面试官还不满意吗?.. 如果很满的话 下一个状态就会稀疏了啊。。0.0而且如果真的很满  不管什么数据结构都需要存这么多点啊。。

何打发123 发表于 2016-10-21 08:01
说了这个面试官还不满意吗?.. 如果很满的话 下一个状态就会稀疏了啊。。0.0而且如果真的很满  不管什么数 ...

反正他一直强调n非常大，问我怎么才能fit into memory，我说了map reduce分割文件他也不太满意的样子，最后说的每次只读一部分，他让我把code写出来但是没时间了。。其实我也不会写从特定byte开始读的方法＝＝

何打发123 发表于 2016-10-21 08:01
说了这个面试官还不满意吗?.. 如果很满的话 下一个状态就会稀疏了啊。。0.0而且如果真的很满  不管什么数 ...

反正他一直强调n非常大，问我怎么才能fit into memory，我说了map reduce分割文件他也不太满意的样子，最后说的每次只读一部分，他让我把code写出来但是没时间了。。其实我也不会写从特定byte开始读的方法＝＝

那可能意思是让你提出来其实不用将所有的内容都放在内存里,内存里只存三行.

雖然我覺得可能對運算複雜度沒有太大幫助,但可以利用00,01,10,11 =>0,1,2,3 這四個植來記錄上一次的狀態跟這一次的狀態,省一點memory?