Bloomberg
BB家的面试和一般的大公司还有点不太一样，喜欢考察他们感兴趣的点，以及考验你的解决问题的能力。所以系统设计和一些easy medium难度的算法会经常考察。当然少部分的时候会出一些奇怪的open minded的题目。他们家特别重视communication。说出你的想法，不断的沟通，并给出他们想要的解法是最最最重要的。用他们hr的话就是we look for fluency in data structures, algorithms and problem solving skills.
算法题
下面是很多网上的面经，我总结了一下，大部分都研究过了，需要我贴下代码和思路的可以给我留言。
1，所有和anagram有关的，他们家都喜欢考。建议全部刷一遍。 Group Anagrams， Find All Anagrams in a String， Valid Anagram
2，所有和topk有关的，BB家甚至system design都有一半是topk的问题。比如经典的topk股票问题。 Top K Frequent Elements， Top K Frequent Words， Kth Largest Element in a Stream
3，所有和meeting room，interval有关的，特别是 Meeting Rooms II，Merge Intervals，Non-overlapping Intervals ， Intersection of Two Arrays，例如，会考 find min number of room for N meeting appointments换个说法考。
4，和买卖股票相关的，毕竟他们的主营业务，所以 Best Time to Buy and Sell Stock交易次数没有限制，输出最大获利的各个买卖点这类的也是常考。
5， Number of Islands超级高频，请掌握，有时候要求会有点小改变，比不仅仅考虑4个方向的，要考虑对角线8个方向。还有另一个版本的题，和小岛数量实质是一模一样的，好像是算什么云。单纯的换个说法而已。记住好好研究下时间复杂度哦。
6，LRU cache相关的以及各种变种都会考，为数不多的hard题需要完全掌握。其实各大公司也都在考。LFU之类的。 LRU Cache有很多lru相关的变种，
Given a stream of 'query name' and 'execution time',
design a data structure that can return the k fastest query name.
If a new entry's query name is already seen, replace the old execution time with the new one.
ex stream:
query1, 10s
query2, 30s
query3, 20s
query1, 20s
class TopK:
def update(query, time):
def get(k):
一个马拉松比赛，假设路上有10个marker，然后你需要设计几个函数 Top(k)
返回跑在前面的k个人的id， Update（runnerId，markerId）每次跑到某个marker的时候 call这个函数。Hashmap + linkedlist （虽然这里我觉得好像和LRU没太大的关系。别人的面经）
k can is given at runtime.
7，Candy crush的一维版本，给一个string比如acbbbccddd, 消除连续3个以上的，返回最后的结果，先删3个b和3个d变成accc，再删c，最后返回a。
8， 给一个字典，里面包含很多词组什么的（我也不知道该叫什么好），比如{AppleTree，Pineapple，AppleTea}。让你实现一个功能，可以给一个input，返回字典里所有包含input的词组。比如pT是AppleTree，AppleTea的子串，所以你要返回AppleTree，AppleTea。
9，给2个array，比如arr1 {1, 2, 4, 5, 9}的sum是21，arr2 {2, 3, 5, 7, 10}的sum是27, 那么让你swap他们2个中的各一个元素，使得他们的sum相等，比如arr1中的2和arr2中的5换一下，就是sum1和sum2都是24了。
当时第一反应就是2个for loop把情况都扫出来，解释了一下time complexity是O(m*n)，我就说感觉不是很好，应该可以优化。然后就讨论怎么优化。想了一会觉得可以用配合HashMap来做。就是for loop 2次把sum1和sum2先求出来，然后第二次for loop的时候，把arr2的元素都put进HashMap里作为Key。然后写一下公式：
int diff = sum1 - sum2；
sum1 - arr1[i] + arr2[j] = sum2 - arr[j] + arr[i] → diff / 2 = arr[i] - arr[j], 通过map.containsKey判断出arr[j], 到最后好像也没优化多少，大家有什么好办法可以给我留言。
10， 有一些，原题海，我出现过的我直接贴在这里了，大家可以参考利口或者lintcode
🔎详情点击展开
Tree相关的：
- Same Tree
- Binary Search Tree Iterator,
- inorder && Binary Tree Postorder Traversal
- Binary Tree Zigzag Level Order Traversal
- binary tree level order traversal(print指定level的binary tree),
- Binary Tree Upside Down
- add next to every tree node,
- Convert Sorted Array to Binary Search Tree
- Binary Tree Maximum Path Sum
- recover binary tree from inorder and preorder
- linkedlist找merge point,
- copy linkedlist with random pointer,
- flatten BST to linkedlist(把BST替换为2Dlinkedlist，本质不变),
- depth, interseciton of linked list(一个一步一个多步是否可以（复杂度高）)
- word search I,
- min stack,
- stock transaction I(buy date is needed) II,
- two sum,
- subset,
- unique paths II,
- merge two/k sorted array/linked list,
- Find kth largest number(quickselect, array partition),
- sort colors,
- remove duplicate from a sorted array,
- search in sorted rotated array(binary search),
- search for a range and delete it in array, next permutation,
- find peak element(一个先降后升的数组，怎么在这个数组中找到target值 [先找到最小值，然后分别二分查找]),
- rotate array,
- single number(简单版-两个整数数组 所有元素完全相同 但第二个array少了一个数 求少的那个数。array中数字是乱序),
- valid Parentheses(follow up如果加入" " 和 ’ ’ 怎么处理？" "中间的视为全部合理，里面的内容可以忽略),
- Trapping Rain Water,
- Container With Most Water,
- course schedule II(topological sorting),
- surrounded region(起点给定，而非四周，通过最后判断是否全X来判断给定的X是否封闭) palindrome number(先让count一下6位数的palindrome有多少种可能，比如100001，234432这种. 然后让print出所有的),
- reverse integer(reverse a float, follow up 用 a == reverse(reverse(a)) 来判断overflow行不行), atoi, excel sheet column title/number, power(recursive; iterative), sqrt (指定精度 or返回double - 牛顿迭代),
- RomanToInteger, IntegerToRoman,
- 矩阵螺旋(给一个矩阵，从中间开始旋转着一圈一圈把值打印出来。代码写完之后还追问了一下如果要允许用户自定义螺旋的方向要怎么改)
- reverse words in a string(1.一开始我想用两次while循环那种解法，边写边念叨思路。然后三哥说不要用这种，换一个一次循环的，函数容器随便用。感觉他确实在干别的事，我就直接把char *的input转成string然后空格分割存进vector再逆序合并
- 去掉一句话中多余的空格。输入“ The sky is beautiful ! " 输出 ”The sky is beautiful!" 他开始给的例子里没有标点符号，我就没考虑到=。= 后来也没让修改了。。),
- anagram [hashmap,面试官prefer质数],
- add and search word(给一个string的字典和一个target string，要求找出字典中所有跟target近似的string，带*的匹配),
- longest palindrome substring, shortest palindrome(从后面添加), strstr()
11， entry[1, 5, 9 15, 20], exit[2, 6, 18, 35，60] 里面存的是time stamp，记录是进入会议室的时间，给你一个时间，问你此时会议室里面有多少人，我说了一下方法就是binary search什么的，后来非要我优化，我就说了一种类似于radix sort的方法，已知一些数据可以进行预处理(?利用bucket sort预处理, e.g.每个bucket存10k ~10k+9, 在对应bucket内binary search)
12， find unique missing(1-100有99个数只出现一次，找到missing one, 用求和可能溢出 ----我说用平均数代替，他说用tree可以达到O(lgn))
int findUniqueMissing(const std::vector;int; a)
int ans = 100;
for (int i = 0; i < 90; i++){
ans ^= i+1;
ans ^= a[i];
}
return ans;
}
若array为sort，可以binary search，类似： Given an array of unique integers in increasing order, return the integer with its value equal to its index in the array
13,
- 求array 平均数， 非常基础，要求念出具体的code。又问数多溢出怎么办.
- 有很多个node，每个node 存了一个int数组。 ——如何求一个global_Average，全部node里所有数组的平均值。简单。 ——如何求一个global_Median。他提示，你可以写一个function 去check If_global_median。 这个可以写，就是让每个node 返回有多少个数比他大，多少个数比他小，总个数，是否存在这个数。用第一步得到的平均数去check(or 最大最小的平均值)，然后二分查找。
- 找streaming median。 我用了两个heap，三哥说你确定要用这个吗，我说是，他说那你写吧，写完再说。 时间复杂度，nlgn。 他说还可以更快吗。我想了一下，可以建数组，存frequency，他问这样做问什么可以找median。
14, 把多个string存成一个string来传输，然后对方可以还原为多个string (cipher and decipher),过程要求无空格, 原串中可以包含任意字符。 - 可以用length的数值作分割，放在每一个string的前面，可以在数字后面加个# - 把一个非空格字符x变成1x, 空格变成00 - 转义：约定空格编码成\，原本的\用\来表示。那么在decode的时候如果看到了\，就看后面连着的是什么。如果是\就替换成, 如果就孤零零的\，那就是空格了。
15, 给个数组，例如｛3，1，1，6，6，9，9，9｝， 然后按照数字频率由高到低输出，如果频率一样，则大的先输出。结果就是“9，9，9，6，6，1，1，3”, 这道题用的hashtable先算每个数频率，然后对所有的arraylist排序。
16, fib数列, 基本递归（T(n)=T(n-1)+T(n-2)=> T(n) = ((1+sqrt(5) )/ 2)^n）和循环的让说了下复杂度，DP的代码让说了下
17, 给两个matrix S和P，判断P是否是S的submatrix，面试官说用brutal force即可。
To be continued!
加油哈！