印度小哥挂经
下午刚面了Yelp的电面，是一个印度小哥，上来先自我介绍，然后问了why yelp? 我提了一嘴项目，然后顺着项目往下问了一点点
没有怎么问基础知识。
Code的题
Meeting Room I 某code 252，Fellow-up是Meeting Room II 某code 253，面试前这题只看了一遍之前写的代码，并没有手写一遍，感觉并不是之前面经的中频题，或者说我RP太差？第二题没来得及写，只说了个思路和分析时间复杂度，感觉要凉
印度小哥挂经2
七月handshake海投的
一开始问了些简历，然后小印哥开始自我介绍了很久，就聊了聊简历上project的经历 没有BQ
然后开始coding:
给一些bussinessName, 比如"Burger King", “kdk dnsd Burgers”, “sad Burger’s”, “asdd das a”, “Walburgers”
要求1是prefix search, 比如输入"bur"返回"Burger King", “kdk dnsd Burgers”, “sad Burger’s”， 返回的顺序无所谓
要求2是substring search, 返回"Burger King", “kdk dnsd Burgers”, “sad Burger’s”, “Walburgers”
面试官印哥，一直在讨论方法没让写代码，最后剩了十分钟没写完，最后说没事的我理解你的思想就行了，不用写完, “perfect”, 不知道是不是要黑我。讨论的思路如下：
lz一开始说用trie, 然后他说ok，讨论了一下时间复杂度之类的，然后我说substring search的话用KMP就行了, 然后他说不用那么复杂，先讨论要求1吧，用trie.
我的思想是把input每个string 按空格split, 存到map里，然后trie里存split后的每个substring, 搜索prefix搜到之后去map里找对应的bussiness name即可，然后面试官问这样和每个string暴力搜有啥区别？ 我说这样一次建trie终生受益有没有？ 他说ok.
然后就是trieNode的定义, 我的思路是每个trieNode 存 isEnd 和word, 这样搜到node.isEnd的时候把string word加到result里即可。(比如burger的r存上burger)他又问那么这样时间复杂度如何？和暴力搜有啥区别？我回答了, 之后说还有另一种方法：在每个char都存上set, 搜完prefix的长度返回se t即可. 小印哥又让我比较这两种方法优缺点，我就是要么牺牲时间换空间，要么反之，看你选咯？小印哥说那我们开始时coding吧！
此时还剩下大概十分钟，写的差不多了还剩一个函数时面试官说行了我相信你可以写完了不用写了，然后开始问了些问题草草结束了。
希望小印哥不是黑我，感觉yelp家很重视交流，不知道没完成代码能不能过。
new grad 店面过经
You are given an array a = [8, 9 , 10 , 0] with max value k
All values in array have this property 0<= value <= k, value>=0 (non-negative)
You have to sort this array in ascending order a = [0, 8, 9, 10]
Allowed unlimited space complexity. Use k to your advantage.
Write code to get Minimum Time Complexity
我的解法是 count sort 或者 bucket sort：
Since values are between 0 and k. Just take hashtable with K+1 values as key and count frequency of elements in array ( O(1) ) step.
For example, [8,9,10,0] frequency for all element fro 0 to 9 would be : 0->1, 1->0, 2->0, 3->0, 4->0,…,8->1, 9->1, 10->1
Loop from 0 to k values and depending on their frequency copy into result array. O(n) step.
overall time complexity: O(n), space complexity O(k)