G家实习电面挂经

zzgzzm 发表于 2016-11-10 23:51
用二维dp[][]好像不必要。我又写了个改进的在30层，就是直接pre-order traversal Trie （DFS, 不要在s.su ...

你看下我的思路 我的思路对leetcode 只有两个string的case beat了98.32%的submission

DreamBoy 发表于 2016-11-10 15:40
思路和我类似 但是code实现感觉不容易 好多次recursion 你可以记录trie里面每个node在s里面的index，iswo ...

这个是不是我在42层回复的意思？对于每个Trie node (i.e., prefix)记录在s中的index，完全可以的，本质上应该和我在30层写的"pos" map的功能差不多，都是要把index / length的信息用DFS (i.e. trie pre-order traversal)传递到更深层。
至于时间复杂度的计算：k*l (=字典单词总长)是没有问题的。但"n*m"的估计应该太保守了。因为n=s.length()就是给定的一个固定单词，而且要和字典所有单词比较，所以最好提前处理一次，放到合适的container里，以后直接使用，不要在DFS (trie traversal)阶段再计算与s index有关的信息。这个O(n*m)应该可以优化到O(n) (30层), 也就是说对于只由于字典的扩张带来的额外复杂度不应该受到s长度的影响，否则不是最优的，也就是面试官follow-up问若s特别长怎么办吧。
最后我整体想了一下各种Trie的方法和two pointers对字典的每个单词一一处理的trade-off。Trie的方法就是要先付出时间空间代价做铺垫，以后就快了。所以在字典size趋于INF大时，Trie的时间asymptotically还是有优势的(利用公共prefix)，而任何时间空间复杂度的讨论都只在N, L, 等巨大时才有意义。

zzgzzm 发表于 2016-11-11 00:38
这个是不是我在42层回复的意思？对于每个Trie node (i.e., prefix)记录在s中的index，完全可以的，本质上 ...

"因为n=s.length()就是给定的一个固定单词，而且要和字典所有单词比较，所以最好提前处理一次，放到合适的container里，以后直接使用" 这句话我不很清楚细节 你准备怎么处理s呢 我感觉其实s是指loop了一次的 因为我每个node都会记录下index 之后从index+1开始查起 那时间复杂度说是nm是确实保守了 但是是个upper bound吧

zzgzzm 发表于 2016-11-11 00:38
这个是不是我在42层回复的意思？对于每个Trie node (i.e., prefix)记录在s中的index，完全可以的，本质上 ...

突然想到leetcode有道题 存word的时候不存prefix tree直接存成dictionary， key是prefix ，value是set，感觉这样implement容易些，如果没时间可以不implment trie用dict但是这样会浪费空间。。

DreamBoy 发表于 2016-11-11 01:47
"因为n=s.length()就是给定的一个固定单词，而且要和字典所有单词比较，所以最好提前处理一次，放到合适 ...

我的提前处理s就是指下面这段从30层code拿出来的一段（时间O(s.length)），只和s有关，与字典无关。这个"pos"是之后DFS要用的。
对于在DFS中记录每个node在s中的index, 例如s="czzab", dict = {"ab", "cab"}。那么DFS中先判断node "a" ("ab"中的)在s中indexOfFirst=3. 那么等DFS到"cab"的"a"时要判断"a"在s中index >0 (skip matched "c")后的indexOfFirst也是3. 那么这个就重复算了，其实若某个char c在s[j,...]首现位置是k的话，那么本来可以立即得到c在所有s[t,...] (j<=t<=k)的首现位置都是k (因为在index j~k-1之间是不可能有该字符c的)。也就是说在DFS过程中在同一个depth上traversal时的确s只loop了一遍，但换到另一个branch时就有可能有重复loop。

1. // pos[c][i]: position of first occurrence of c in s.substr(i)
   
2. unordered_map<char, vector<size_t>> pos; // default -1 if not found
   
3. int ls = s.length();
   
4. for (char c = 'a'; c <= 'z'; c++) {
   
5.   for (int start = 0; start < ls; ) { // time O(ls)
   
6.     int i = start; while (i < ls && s[i] != c) i++;
   
7.     for (int j = start; j <= min(i, ls - 1); j++) pos[c][j] = i < ls ? i : -1;
   
8.     start = i + 1;
   
9.   }
   
10. }

复制代码

感觉第一题可以用位运算？ 因为每天的员工list里边，无论哪个人都不会出现两遍，然后把昨天的员工列表hash到26位bit里边去，然后吧今天的员工列表hash到另外一个26位bit里边去，然后两个数xor一下，如果结果得0，那么昨天和今天的员工是一样的，没人来没人走。 如果不一样的话，要么有人走了，要么有人来了。把xor之后的结果跟今天的员工list & 一下，得到的应该就是今天新来的员工，然后跟昨天员工list &一下，应该得到的是昨天还在今天已经走了的员工。

keke_shu 发表于 2016-11-22 08:03
感觉第一题可以用位运算？ 因为每天的员工list里边，无论哪个人都不会出现两遍，然后把昨天的员工列表hash ...

能说一下&怎么操作的嘛 谢谢

xiaozhuxiaozhu 发表于 2016-11-9 07:01
第1轮，第2题，就是combination sum的小变形，加个小于target就行了吧。

这题怎么感觉是组合加排列啊。

DFS着combination， 每当找到一个解，对该解做permatation。。。

问一下楼主，第一面第二题，你说给一个list，是指int nums[]这种还是List<Integer> list 这种啊

楼主你好！

我跟你同一天实习面试，至今没有hr回复，请问你有后续了吗？

祝我们好运～