gg全套

readman 发表于 2016-9-15 03:36
楼主电面那题你的方法空间是n^2么, 二维dp做的?

然后onsite管子那题是union-find么? 下边的是2d fenwick ...

我咩有用dp做。。用的recursion。。

feichangh 发表于 2016-9-15 04:00
第四题第一小问暴力检查除了对角线的半个matrix（i = 0 ~ m, j = i+1 ~ n）看看m[j]是不是等于m[j]。第二小 ...

第二小问我是提议建一个trie tree先建字典。然后面试官说可以假设我已经有一个hashmap里面key是prefix，value是所有prefix是key的单词。然后再dfs。

因为当第一个单词选定的时候，第二个单词的第一个字母已经确定了，可以用prefix在字典里找。同理第三第四。

readman 发表于 2016-9-15 04:15
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构

这些都没有说死，基本就是你怎么想就怎么设计，我觉得这里可能考了一点OOD

第二题感觉上用heap会比较好

第三题用额外空间的话楼主是怎么处理edge case的啊， 我assume你是提前把加和存起来了……

plich 发表于 2016-9-15 04:52
第二题感觉上用heap会比较好

第三题用额外空间的话楼主是怎么处理edge case的啊， 我assume你是提前把加 ...

嗯第二题是heap
第三题就存每行的和 然后edge case就算的时候判断一下。。

hyperspace 发表于 2016-9-15 04:33
我的方法是有一个boolean[4]。分别代表上下左右有没有口子。

然后四方向做BFS ？

wtcupup 发表于 2016-9-15 06:55
然后四方向做BFS ？

没有四方向了。题目的设定就是只有一个入口和一个出口。

请问lz，电面那题是不是直接从中间向两边遍历就可以了？O（n）的时间复杂度

todayand 发表于 2016-9-15 12:05
请问lz，电面那题是不是直接从中间向两边遍历就可以了？O（n）的时间复杂度

我是从两头从向中间弄的

感谢楼主分享！我把能有的米都贡献给你，祝你以后offer多多！