G 面经+加面

fubu 发表于 2016-12-3 01:59
我当时也试图用LRU类似做法，然而lru，每个node都是插入到tail，每次操作可以O(1); 这个要先判断插入位置 ...

这样行不？算two-pass?
still map to list, but if id is dup, do not sort in place, instead, put the node in another map sorted by value;
when finished, we have one list + one tree,
then merge the tree back to the list;
this one is nlogn,

你面的怎么两轮design

fubu 发表于 2016-12-3 01:52
followup1：你说的很接近，不过细节上，例如算left光亮值时，从左到右scan，每遇到light时，把colulmn In ...

楼主不太懂你这个过程啊， right应该怎么计算呢？ 你计算left的时候， 是不是依旧是对于每一个O（可放置位置）都要往这个queue里面补light?因为可能有些光是之前照不到，现在着得到的？  

zyoppy008 发表于 2016-12-2 17:25
Treemap 加hashmap啊

直接TreeSet,重写一下Comparator就好了吧。。

补充内容 (2016-12-5 10:39):
这样的话似乎，两个list原先就排好序的这个条件没有用了？

小A要当码农 发表于 2016-12-5 10:30
楼主不太懂你这个过程啊， right应该怎么计算呢？ 你计算left的时候， 是不是依旧是对于每一个O（可放置 ...

对于每一行都要由左至右scan一次，算出每个cell的left light值；再由右至左scan一次，算出right light值；每一列也要由上至下，再由下至上scan；这样就得到每个cell的light = left + right + up + down；queue的作用是store一次scan内灯的index，方便知道何时前一盏灯会淡出

恭喜楼主，拿到offer啦~~~

楼主，第三题为什么要shuffle list，直接用random number 不行吗？

fubu 发表于 2016-12-11 02:05
对于每一行都要由左至右scan一次，算出每个cell的left light值；再由右至左scan一次，算出right light值 ...

懂了  多谢楼主解释。。 所以还是要类似于对每个Cell做一个preprocess对吗？

prodigalr 发表于 2016-12-11 07:58
楼主，第三题为什么要shuffle list，直接用random number 不行吗？

用random number 的缺点是，回溯时，如果不记录之前random出来的值，会出现走同一步的情况；shuffle list的话，直接for loop list就可以了

小A要当码农 发表于 2016-12-11 08:15
懂了  多谢楼主解释。。 所以还是要类似于对每个Cell做一个preprocess对吗？

由左到右scan row，可以把该row上所有cell的left值求出
这样每个cell都会scan 4次
复杂度O（4mn）= O(mn); m n 分别是matrix的行数 列数