c******w
发帖数: 102 | 1 经过半年多的征战，现在总算要进入尾声。 为了回馈jobhunting版， 特发面经，感谢
所有对我有过帮助的战友们，并希望后来者都能有好的offer。 声明： 谢绝某些喜欢
吓唬小mm的WSN来看贴，要看去火星看。
某Palo Alto公司（P）：
Interview 1:
1. 两个sorted array, 如果merge成一个array。
2. 如果这两个array没有sort呢？并分析复杂度。
3. 如果有K个没有sorted的array怎么办呢？
4. 如果当前机器有K个cpu， 怎么处理问题3呢？复杂度分析。（考虑
multithreading）
Interview 2：
1． 给定一个array，如何找到两个数字， 他们的和等于一个target number。 需
要提供几种不同的算法，并比较分析。
2． 关于数据库的。 什么是Key， 什么是foreign key。 为什么要用foreign key？
3． 怎么提高数据库查询的速度？ （indexing）。 Indexing是如何实现的。
4． 如果有一个数据库现在运行速度很慢，请分析原因并提出解决方案。
On-site interview:
1. 给定一个tree， 每个节点有一个数值， 如果找到一个从root到leaf的path，使
得这个path上的所有节点的sum最小。 Interviewer所要的答案是和hashtable联系上的
，因为考虑到树很大的时候需要很长的时间。这个题很容易用recursive的方式解答，
可是这个不是interviewer所要的答案。后来按照interviewer的意见，还是基本写出了
用hashtable的算法。
2. 分层打印一棵树。
3. Reverse一个linkedlist。
4. 游戏设计题。 设计一个射击游戏， 一个player和一个alien， 他们可以在平面
上左右移动比规避子弹。我按传统的OOD的方式， 给出了各种class，还给出各自的关
联以及class中的方法。 可是好像都不是那个很年轻的ABC所要的。最终也没有搞明白
他想要啥，不知道是我有问题还是他有问题. 唉……..
题目其实都不难，最终还是莫名其妙的挂了。
某Seattle公司：
On-site interview:
1. 谈research。谈internship project。
2. 些关于电话号码的combination， 然后给他用example解释why it is correct.
3. 设计题， 如何设计处理大规模数据的data center， 考虑用cluster等等。还有
如何压缩数据量。
4. 设计题，其实也就是有关static 变量用来在整个class中共享数据的问题。
5. 基于问题4， 探讨各种synchronization技术， 以及busy waiting的优缺点，问
啥有时候要用基于busy waiting的 spinlock。 主要是基于性能的探讨。 如果有一个
应用程序运行时没有达到timing constraint， 你如何去分析问题出在哪儿， 可以用
什么工具或者技术。
6. Interviewer拿出一张写有代码的纸， 让我找出里面存在的问题。 这些问题包
括exception control， 大量string的连接， 以及没有关闭的connection。找出后，
分析解释为什么这些是问题，问为什么要解决这些问题， 主要侧重于高质量的代码和
随之产生的performance问题。 结果运气比较好，所有的问题都找出来了。
Interviewer很满意，也很高兴。
7. 设计题， 有一个多台机器构成的cluster。 现在有大量公司的数据文件 （并有
多个备份）。 如果设计一个算法，使得每台机器尽量均衡的使用，并且 每个公司文件
的不同copy不能存在于同一台机器上。主要的Idea就是用round-robin的方式assign每
个公司的原数据文件到一台机器，再结合使用hashtable。 Interviewer提到我的解法
正是他现在在使用的解法。
8. 谈research谈了20分钟， 解释我的一个paper的内容。然后来算法题：给定一棵
树，如何找到从root到leaf的最长路径。 我首先proposed了一个先DFS找最长长度，然
后用BFS找到这个path的解。Interviewer说这个算法也行可是太麻烦， 其实只要BFS就
够了。于是我就要了一分钟好好独自想了想， 原来根据interviewer的意见，用BFS按
分层打印的方式就可以搞定，只是需要用两个list， 因为当while loop结束的时候，
另外一个list一定是存储的到达root最远接点。Interviewer又问道如果输入是个graph
怎么办。其实就是mark visited nodes。然后和interviewer一起去吃饭，中间聊得还
不错。我婉转的问了问，是不是吃饭后就可以休息了。结果interviewer说，你还要见
两个人呢。于是我总算放心了，知道今天不会吃完饭就打道回府了。
9. 谈research谈了20分钟， 基本就是到了要呕吐的地步。 然后就是算法问题。
给定一个array，如果找到所有的triple使得 x^2 + y^2 = z ^2，这个题实际上就是三
个数等于一个target number那道题的变体。 他让我随便写，说主要是看我的c++的
coding style。于是就来了个三重循环的算法。 写出后被小挑了一点毛病，主要是因
为混淆了Java和C++的有些语法。后来他继续问， 有没有比O(n^3)更好的算，我就提出
了先排序，然后在用O（n^2）的时候和O（1）的空间的那招，顺利搞定。不过
interviewer好像没有想明白为啥我没有用hashTable就搞定了，于是我就用两个
example解释了好一会儿，最终interviewer认可了算法。不过他还是提出，他听说用
hashtable可以解决这个问题，于是俺立马说that is right，谈后给他解释了一把如何
用hashtable搞定， 但是用我这招还不需要O（n）的空间。Interviewer也表示了认可。
10. 满以为这个interview就结束了，结果这个interviewer有写了一段Java的代码
，说这段代码是正确的一定可以实现功能，让我看看这个代码可能有啥问题。 我说应
该是有性能问题把， 就是string累加的问题。 我说我觉得用stringBuilder会更好，
他于是让我解释二者之间的差异。我就解释到O（n^2）和O（n）的差异。然后他就给我
继续提到反复创建临时变量是件很time-consuming的事情，这对高性能系统而言是很大
的代价。我也表示认可。
11. 这个interview依然没有结束， interviewer又问了一个如何design amazon的
database的问题，让我先画ER图， 然后设计schema。最终在interview进行了65分钟以
后我们结束了这个interview。
12. 后面就是见大老板了， 聊了很多是否喜欢这个组啊，为啥喜欢这个公司啊等等
的问题。 到了还有15分钟结束interview的时候，这位manager突然说， 我们还有15分
钟，那我们来讨论个设计加算法题吧。于是他开始在白板上开始描述那个在版上讨论过
的舰船游戏问题。就是向舰船开炮，可能是miss，可能是hit，如果被击中一定次数就
sunk。 我可以自由设计数据结构，自己设计算法。 考虑了三分钟， 开始有点小紧张
，后来一再提醒自己镇定，还真想出来了，于是上代码， 顺利搞定。 然后结束了长达
6个小时的面试过程去见recruiter了。
总得来说运气也比较好，没有遇到变态题。整个过程感觉主要就是累，到了最
后两面的时候，已经明显感觉到自己说错字了， 脑子有短路的感觉。不过俱往矣，这
几天好好放松休息一把， 然后继续实验写毕业论文。 希望各位战友都有好运。 |
o********p
发帖数: 127 | |
i****s
发帖数: 1152 | |
l*****a
发帖数: 14598 | |
f***g
发帖数: 214 | |
l*****a
发帖数: 14598 | 6 给定一棵树，如何找到从root到leaf的最长路径
不时递归求depth吗？
why use DFS/BFS |
g******0
发帖数: 221 | |
g*********s
发帖数: 1782 | 8 recursive is dfs.
【在 l*****a 的大作中提到】
: 给定一棵树，如何找到从root到leaf的最长路径
: 不时递归求depth吗？
: why use DFS/BFS
|
g*********s
发帖数: 1782 | 9 hash_map, key is node, int is the sum from root to this node.
bfs:
when insert child to queue, update hash_map based on current node
also keep trace of min_val of leave node.
O(N) time and O(N) space.
【在 l*****a 的大作中提到】
: 最小路径用哈希表，讲讲吧
: 很抽象
: 谢谢
|
g*********s
发帖数: 1782 | 10 给定一棵树，如何找到从root到leaf的最长路径。
same technique. but all weight is 1 and now you search for longest.
【在 g*********s 的大作中提到】
: hash_map, key is node, int is the sum from root to this node.
: bfs:
: when insert child to queue, update hash_map based on current node
: also keep trace of min_val of leave node.
: O(N) time and O(N) space.
|
|
|
g*****i
发帖数: 2162 | 11 谢谢分享.
舰船游戏的问题能解释下或者给个link吗?以前板上讨论没看到过. |
c****m
发帖数: 179 | 12
good。
不过有个疑问，如果要求的是global optimum, 肯定要遍历所有节点。就算是树很长，
用DFS的时候
加一个variable保存路径上之前节点的和不也可以避免重复计算（回溯的时候减去当前
节点值），另外
用一个数据结构track leaf min value，而且还不用hashtable那么大的空间？
【在 g*********s 的大作中提到】
: hash_map, key is node, int is the sum from root to this node.
: bfs:
: when insert child to queue, update hash_map based on current node
: also keep trace of min_val of leave node.
: O(N) time and O(N) space.
|
g*****e
发帖数: 3417 | 13 http://www.careercup.com/question?id=8210023
【在 g*****i 的大作中提到】
: 谢谢分享.
: 舰船游戏的问题能解释下或者给个link吗?以前板上讨论没看到过.
|
g*********s
发帖数: 1782 | 14 yes, dfs is more memory efficient.
【在 c****m 的大作中提到】
:
: good。
: 不过有个疑问，如果要求的是global optimum, 肯定要遍历所有节点。就算是树很长，
: 用DFS的时候
: 加一个variable保存路径上之前节点的和不也可以避免重复计算（回溯的时候减去当前
: 节点值），另外
: 用一个数据结构track leaf min value，而且还不用hashtable那么大的空间？
|
e******0
发帖数: 211 | |
h**********d
发帖数: 4313 | 16 请问第一个是什么公司阿。。谢谢！
bless!! |
a*******y
发帖数: 559 | |
c******w
发帖数: 102 | 18 Palantir
【在 h**********d 的大作中提到】
: 请问第一个是什么公司阿。。谢谢！
: bless!!
|
g*****i
发帖数: 2162 | |
s*****y
发帖数: 897 | 20 同问。
【在 c****m 的大作中提到】
:
: good。
: 不过有个疑问，如果要求的是global optimum, 肯定要遍历所有节点。就算是树很长，
: 用DFS的时候
: 加一个variable保存路径上之前节点的和不也可以避免重复计算（回溯的时候减去当前
: 节点值），另外
: 用一个数据结构track leaf min value，而且还不用hashtable那么大的空间？
|
c******w
发帖数: 102 | 21 Interviewed Feb 2011 (took a day)
Got interview through a recruiter. Interviewer was terrible; he kept
stumbling going 'uhh do you mean this' it's obvious they have no managers (
they told me) and no real recruiters cause everyone is an engineer.
You are given a pyramid; the numbers for example is 2 on the first level, 3
-1 on the second level, 4 7 8 on the third, etc. How do you calculate the
maximum sub sequence of any path traversing the pyramid?
Use dynamic programming. Treat the pyramid as a binary tree. Use a hash
table to store the values of each sum in the subtree, with the key being the
level + order of the node, and the value being the maximum sum of the paths
in its children. runtime and space complexity is O(n) going from the root
and doing a depth first traversal through each node.
Interview Questions
You are given a pyramid; the numbers for example is 2 on the first level, 3
-1 on the second level, 4 7 8 on the third, etc. How do you calculate the
maximum sub sequence of any path traversing the pyramid?
View Answers (1)
这个是来自于这个链接的题目：http://www.glassdoor.com/Interview/Palantir-Technologies-Software-Engineer-Interview-Questions-EI_IE236375.0,21_KO22,39.htm
【在 s*****y 的大作中提到】
: 同问。
|
