对于每一个北美码农求职者来说，“面经”永远是一个绕不开的话题。但是，大家平时收集到的面经，往往回忆不全，又没有答案，利用价值大打折扣。
为了发挥这一秘密武器的最大威力，我们决定，不定期的为你整理还原网上的最新面经，并且提供相应的解题思路。
不多说，直接上干货，以下为2018年4月1日至4月7日（第一周）北美CS方向面经与解题思路。2018年4月8日至4月14日（第二周）内容，请在公众号后台回复下载。
Airbnb-全职-电面
有一个2d array
[earth, america]
[america, south america, north acmerica]
[north america, canada, us]
[canada, ontario, quebec, calgary]
[us, california]
给你两个输入，找到他们的最近的parent。比如输入为california, canada，返回north America
基本解题思路：构造树Dfs + hashmap
Corner case: node没有parent，孤立的点
Google-全职-现场面
给定一个矩形的长宽，用多少种方法可以从左上角走到右上角（每一步，只能向正右、右上或右下走）；
follow up：如果给矩形里的三个点，要求解决上述问题的同时，遍历这三个点；
follow up：如何判断这三个点是合理的，即存在遍历这三个点的路经；
follow up：如果给你一个H，要求你的路径必须向下越过H这个界。
基本解题思路：Dp/bfs/dfs
Follow up 1: 存路径，检验3个点在路径中
Follow up 2: 3个点按y排序，检验x？随y增加而增加
Follow up 3: h定义是啥？Y值？如果y值太大，左上角可能回不到右上角，先按y值算x 的限定值。E.g.在x = x1时，如果y < h，dfs需要返回上一级
Google-全职-现场面
给一个数组，要求尽可能多的切割这个数组，使得每一个小段分别sort之后，整个数组就sort了。
基本解题思路参考：http://www.1point3acres.com/bbs/thread-380867-1-1.html
区间之间需要按照大小排序，每个区间的最小值大于等于上一个区间的最大值。
从后向前扫一遍，找出每个位置之后的最小值，时空O(n)。
再从前往后扫一边，如果某一个区间的最大值小于之后的所有值，那就切一刀。
Google-全职-现场面
在论坛发帖，有可能后面的人引用前面的内容，就这样层层引用，要求返回一个结构，记录谁引用了谁。
基本解题思路：构造树
corner case: 问清楚有没有cycle
Google-全职-现场面
字符串化简。要求输入一串单词，返回一个map保存缩写与原词的对应关系。例如：internationalization ->  i18n 就是只留头尾两个字符，中间用字符个数代替。但是会有这种情况：google -> g4e  与goggle -> g4e 都对应成了一个缩写，这样的时候，就要扩展缩写长度，继续尝试，google -> g4e -> go3e -> goo2e -> goog1e。（PS：本例中goggle缩写成g4e，google缩写成goo2g就可以保证不重复了）。
参考leetcode 527. Word Abbreviation
Make abbreviation for each word.
Then, check each word, if there are some strings which have same abbreviation with it, increase the prefix.
IBM-全职-电面
给一串数组，比如1,1,3,2,1,5,3,4,10,4,2，找规律，在五个答案中选一个数作为下一个数的预测。
单纯找规律
Pure Storage-全职-电面
给平面上四个点，判断是否能组成一个正方形。每个点是由（x，y）坐标表示。follow up是给n个点，问可以组成多少个valid square，要求先O(n^4)，再改进到O(n^3)，最后改进到O(n^2)。
基本解题思路参考：http://www.1point3acres.com/bbs/thread-205801-1-1.html
假设ABCD能组成一个正方形，AC, 和BD是对角线。
1. 首先先利用一个HashSet, 把全部点加进去，这个一是除重，二是能达到O(1) 查点的时间。
2. 写helper function, input是AC两点，计算对应的B,D点（对应的BD只有一种解）
3. 函数上写for-i-j loop, i==j 跳过，然后算相应地input, input[j]点对应的BD点在不在set里面，有就++。
1是O(N), 2是O(1), 3是O(N^2) 复杂度整体下来就是O(N^2).空间的话使用HashSet，应该是O(N)复杂度。
Zillow-全职-电面
数据结构存储一个多项式，然后把两个多项式相加（合并）,例如
Expression A: 5x^3 + 8x^4 + 3x + 20
Expression B: 10x^3 + 7x^5 + 15
A + B: 15x^3 + 8x^4 + 7x^5 + 3x + 35。
基本解题思路：Hashmap 假设a b已经合并指数相同的项
Amazon-全职-在线测试
假如有一个target单词和一堆骰子（每个骰子可能有2-6个不同的字母），问你能不能用这些骰子拼出target单词。每个骰子显然只能用一次。然后依然是follow up，如果单词很长怎么优化，如果骰子很多怎么优化。
基本解题思路：Dfs
String -> hashmap<char, int(frequency)>
dfs 每次对map操作，下一层递归后，还原map
follow up : 单词很长（先检验骰子数目，对骰子dfs）；骰子多（对map递归，可以sort string）
Oracle-全职-电面
判断最多允许删除一个字符的情况下，字符串是否构成回文。
基本解题思路：Dfs+cache
若当前级string删1个char／不删构成回文的话，存cache
base case: 1个char/空字符
返回两个链表中间的值相等的所有common节点。
Hashmap<int, int> -（value, frequency）
Corner case: 可能存在多个值相等
Bloombery-全职-在线测试
设计一个纸牌游戏, initial a cards bag with constructor 然后implement pick() 随机返回一张牌。
基本解题思路参考：http://www.1point3acres.com/bbs/thread-386931-1-1.html
card class 有symbol 和number
2个array symbols 和numbers
2个for循环把card都加入card bag 用random随机取
输出string数组中出现频率最高的string,如果频率相同，按照首字母排序输出第一个  input array["apple", "IBM", "apple", "Bloomberg", "Bloomberg", "IBM", "Bloomberg"]      output -> “Bloomberg”。
Hash map<string, int(frequency)>
Max_frequency记录全局
Hashset <string> 保存max_frequency对应的string  对set排序
这就完了？
还有更多！
请到公众号后台回复”408“领取第二期CS最新面经与解题思路！本次活动限时免费领取，截止日期：4月30日。
继续阅读
阅读原文