刚刚面完的Google intern，地里最简单的题了

Jun仔。 · 发表于 2016-11-11 04:23:59

注册一亩三分地论坛，查看更多干货！

x

早上刚刚面完Google的intern，我觉得我的题应该是地里最简单了的。面之前看了地里的题，现在瞬间觉得地里的题不知道高到哪里去了。
第一轮：NY 印度哥，好在口音不是很重
1. Given two arrays (or lists), A and B, return an array (or list) containing the elements in A that are not in B
2. Given Strings convert it to number:
Example: Input: “123”, output: 123
Given Int charToInt(char) convert char to int
这题很坑，看到example以为string只有整数的，小哥让我写test case的时候才发现还可以是小数或者负数的
第二轮：Mountainview的白人小哥
1. Given A and B, determine if B is A's substring
Input : “google” “gl” return true
2. Given D, find the longest subsequence of S in D
example：
S = "google"
D = ["goog", "g", "Afasgadsfg"]
output: goog
这个小哥很喜欢optimization，第一题做完是runtime = O(|A||B|), 然后不断和他交流，最后optimize到O(|A|)
第二题做完naive的方法后还剩15分钟，他说不用写optimize的code，说想法就好了want O(|S| + |D|log|S|)，但是最后剩五分钟了还是想不出来，他说他interview了这么多人没一个想出来的，solution是要把S的char弄成一个dictionary，key是char，value是一个list with length = |S|，每个element是key在S里面下一次出现的index. 然后用veb tree。（这个是什么鬼，我没听说过，小哥也是这也是他在看了solution后第一次听说的。。。。）

祝我好运吧～～
好怕跪了，因为optimization的时候都是一点点和小哥们交流后才弄出来的，第一次写的时候不是最optimal的