刷题咯

bibaboo0UID: 3565929

501. Find Mode in Binary Search Tree
Easy题。我使用dict做的，但是没想到怎么用O(1)的空间实现

bibaboo0UID: 3565929

485. Max Consecutive Ones
Easy题，不解释。

bibaboo0UID: 3565929

475. Heaters
Easy题，第一次击败了百分之99.88的人，也不知道为啥。用了先排序后计算的方法。Naive的方法应该是n方吧。我这样做是nlogn。

bibaboo0UID: 3565929

448. Find All Numbers Disappeared in an Array
Easy题。看答案看到一种很聪明的做法：
for e in nums:
            nums[abs(e) - 1] = -abs(nums[abs(e) - 1])
        return [i + 1 for i, e in enumerate(nums) if e > 0]

bibaboo0UID: 3565929

447. Number of Boomerangs
Easy题。6行python代码解决，有点小开心。至此google easy题全部结束。

bibaboo0UID: 3565929

33. Search in Rotated Sorted Array 难度Medium 耗时半小时。
经典问题之rotated array

bibaboo0UID: 3565929

昨天星期四，面了google intern。
前后两轮，每轮四十五分钟，从中午十二点一直到一点四十五。
第一轮听声音应该是一个白人女生，一开始问了一下项目的事，然后开始出题。给定一个字典，当你输入前几个字符时自动提醒所有可能的单词。我说有两种方式，一种是用prefix字典，另一种是用trie。prefix字典我之前写过，很有信心，但是trie我没写过，虽然我知道trie可能更好，但还是选择了用prefix字典写。写完之后follow up是如果单词有不同的频率，只想返回频率最高的五个怎么办。我一开始想的每得到一个新的就插入排序，然后返回前五个。后来她说如果数据量特别大怎么办，我这才想到可以把除了这五个之外的都抛弃掉。再后来的follow up是如果不是5个是n个，不停的插入删除还要保持最大的n个怎么办，我说可以用heap的数据结构。又问如果允许输入的prefix错一位怎么办，我说遍历搜索整个字典，找出所有跟这个prefix相差一个字符的prefix，输出union中最大的5个单词。总之她问的问题我基本上都能答上，答得好不好是另一回事。主要的问题有两个，一个是trie不熟练，她其实暗示过我可以尝试trie，我没信心就没敢接上。另一个是英语比较烂，说的结结巴巴，卡壳、重复的比较多，这个一定要训练！！

bibaboo0UID: 3565929

第二轮运气比较好，遇到一个中国人大哥，大哥直接让我讲中文了。也不废话啰嗦，上来直接就出题。题目是给定一个list of interger，找出其中surpassers的总数。surpasser的定义是对于i,j if i < j and A[i]<A[j], then j is a surpasser of i. 也就是一个pair，后面的数index和值都比前一个大。这个题目brute force的方法很好想，就是一个二重循环，复杂度n方。大哥开始问如何优化，说最优解是nlogn。我想半天没想出来，要大哥提醒。大哥说有两种方法，一种是二叉树插入，还有一种是merge sort的变体。大哥提醒我了之后我还是没想明白，只能再次求教。后来总算明白了merge sort的方法，其实就是分治，分成left right，两边count，再count横跨两边的pair，最后把三个数加起来。知道了算法我就开始写，写的还挺快的，但是中间又出了问题：count横跨两边的pair的时候，我用了一个二层循环，这样一来就不是nlogn了，大哥让我算一下复杂度，我算出来是n方。那么怎么才能nlogn呢？我又卡壳了。在大哥提醒下，我在divide and conquer的时候，一边count 一边排序，这样上层拿到的就是一个有序list，就可以用O(n)的时间计算pair，这样复杂度就nlogn了。大哥开始问我空间复杂度的问题，我说是nlogn。最后大哥说最优的merge sort可以只用O(n)的空间。面试结束。感觉这题比上一题要更难一些，两次思路都没想到，感觉不太妙。

bibaboo0UID: 3565929

461. Hamming Distance Easy题
python tips: 异或操作 c=x^y

bibaboo0UID: 3565929

自从面完谷歌之后，将近二十天没刷题了，准备恢复。

bibaboo0UID: 3565929

253. Meeting Rooms II 难度Medium
这题之前跟同学讨论过，没想出来方法。今天看了答案，理解了半天，豁然开朗。其实如果脱离了算法、编程这些，如果你就是一个房间管理员，这个其实很好解决，就是根据meeting的先后顺序，先来了就先分配房间，走了房间就空出来，没有空房间了就再开一个新的，就这么简单。如果非要说算法的话应该可以归类为贪心算法吧。

bibaboo0UID: 3565929

127. Word Ladder 难度medium
一开始超时。后来利用字符串的字母个数限制，将一个维度的复杂度降低到常数级才通过。
for i in xrange(len(w1)):
                    for cha in 'abcdefghijklmnopqrstuvwxyz':
。。。
这个循环大概有上百次，但毕竟还是常数级。再大的常数级都比O(N)要好。这是一个真理。

bibaboo0UID: 3565929

311. Sparse Matrix Multiplication 难度medium
稀疏矩阵的处理。

bibaboo0UID: 3565929

28. Implement strStr()
Easy题不解释。

bibaboo0UID: 3565929

149. Max Points on a Line
难度 hard
挺难的，写了好久。。三个小时
好久不写了，要多练啊，明天要二面tusimple