P*******b
发帖数: 1001 | 1 thank you!
本质上graph的两个结点是否有通论。对吧。 |
|
h**6
发帖数: 4160 | 2 没看见记录了结点指针，这样的话，确实可行。和刚才那题hit cache有异曲同工之妙。
如果稍微改改，也可以只扫描一次的。 |
|
r***8
发帖数: 86 | 3 有两单向縺表，表头不一样，但两表可能中间某个结点会合，请写个最好算法，把会合
点找出来。
我是初到此处，如果题目出重，还请各位见谅了 |
|
h**6
发帖数: 4160 | 4 把链表尾和其中一个链表头连起来变成循环链表，然后求开始循环的结点。 |
|
h**6
发帖数: 4160 | 5 集中回复一下各位朋友：
1.微软的绿卡政策还不清楚，不过听说最近perm拒了一大批。59级SDE是很低的等级，
一般master都有这个级别，我只能指望进去慢慢升级了。
2.关于QuadTree，我确实了解不多，以前我自己实现的时候，用的是洗牌后随机顺序插
入结点的方法，以达到平衡，面试时只提到中位数法。至于自平衡，更是一无所知了，
不知larrabee是否有更好的方法。
3.股票的问题，可能我写的不够清楚。是价值5w的股票，分4年给，如果是5w股，我做
梦都笑醒了。
4.在长度未知的文件中查找字符串。每次我从文件中读取一定长度(大于等于所查找字符串长度)，然后把相邻两段合在一起查找字符串，如果没有就继续读下一段，直到文件末尾。
5.长整数四则运算问题，我是在白板上写的，并没有电子版代码，没法贴在这里了。 |
|
j**l
发帖数: 2911 | 6 这是采用有序链表来实现优先队列的思想吧，优先级最高的就是首结点。优先队列当然
也可以用其他底层数据结构来实现，比如说heap。
只不过插入一个元素的时候可能伴随一系列的删除操作，一般的优先队列插入的时候不
删除。
不过，这是一个从头删除，从尾插入和删除的双端队列, 用单链表怎么实现从尾部向前
删除元素呢？是否要用双链表才行？ |
|
h**6
发帖数: 4160 | 7 ... && (prev = p->data) && ...
如果刚好有个结点值为0怎么办呢 |
|
z****t
发帖数: 1090 | 8 能不能用Trie. 可以每个结点存IP地址中的一个数字，总共也就4或6层。 每个叶子
存着一个IP地址的count
顺着读一遍输入，建这个树。 然后再在这个树上找出现最多的ip地址。 可能优势是找
某个IP的count快， 缺点是还得列出所有的count，才能知道哪些是出现最多的IP。 |
|
h*********3
发帖数: 111 | 9
想了半天也没想出2题的相似之处 。。。。。
觉得还是用hash+heap,hash把 index of the array 影射为一个指针，指向这个结点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW). |
|
f*********i
发帖数: 197 | 10 sorry,头昏了，是DP。
queue的那道题目就是implement enqueue 和 dequeue，不是priority queue。
tricky在判断异常，比如size＝0的时候dequeue抛异常和size full的时候抛提示，还
有头尾结点的指针位置变换，要考虑蛮多细节的 |
|
g***s
发帖数: 3811 | 11 post-order traverse实际上是用recursive的方式实现了一个栈。额外空间是tree的深
度。
而且，这个算法，如果两个结点在最右边，那么要遍历玩所有节点。时间复杂度是O(n).
而用同时向parent移动找的方式，算法时间是树的深度。 |
|
g***s
发帖数: 3811 | 12 知道拉格朗日定理，可以进一步优化。
不知道的，用现有的知识递归做效率也可以达到很高。 （感觉减枝都应该可以减到1万
个结点以下）
因为再大的数字（32bit整数），第一个找到的解其实就是贪心的解，基本也就是6，7
左右。
BTW：为啥和写程序无关了？
force |
|
h**6
发帖数: 4160 | 13 用递归吧。没有必要把所有结点都存下来，找到一个输出一个即可。 |
|
a*o
发帖数: 54 | 14 不会是问最深的结点这么简单，应该是说把边都看作无向的，然后找一条最长路径 |
|
a********m
发帖数: 15480 | 15 先找到1个，然后看返回路径上结点的右子树是不是包含另外一个就可以了。 |
|
x***n
发帖数: 70 | 16 大家好，想问一个基础的问题。假如有一个二叉树，
A
B C
怎么打印出AB, AC，就是从根到各个叶子结点的路径?请问有什么好的方法吗。谢谢！ |
|
l***u
发帖数: 26081 | 17 贡献一道MS面试题
输入：
一棵二叉树和树上的一个结点（每个节点有一个整形数据）
输出：
这棵树上的另一个节点（如果不存在返回NULL），要求这个节点的整形数据与给定节点的差距最小（如
果有多个这样的节点就返回与给定节点的树距离[1]最小的任意一个）
注：
1. 树距离定义为f(x,y)=L(x)-L(c)+L(y)-L(c)，其中L是某节点的层数，c是x和y的最小公共祖
先节点 |
|
b*****c
发帖数: 1103 | 18 原因是这样的，你的方法只适用于 ""这个链表是不变的""
比如说，题目已知当碰到链表尾时，头结点有可能被砍掉，你再从头部找正数第n+1-m
就错了 |
|
l*****a
发帖数: 14598 | 19 你这理由太牵强了吧？
按照你的理论，即使那个所谓的标准做法，
fast pointer走到头之后，如果中间有结点被删掉，你能得到正确结果？
对于其他任何问题，如果需要两次loop
按照你的说话，如果一次loop后有数据被修改/删除，
那你刚才的操作岂不白费了。
m |
|
l*****a
发帖数: 14598 | 20 我认为你的想法正确
其实一个指针两次，根两个指针一次遍历的结点数目一样
两个指针是一个好的思路，但效率上并不真正那么优化
-m |
|
|
S**I
发帖数: 15689 | 22 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
K*******g
发帖数: 26 | 23 跟你的思路一样，不过找第一个结点可以优化以下
struct Node{
int value;
Node *left;
Node *right;
Node *sibling;
};
void connect_sibling(Node *root){
root->sibling = 0;
Node *cur, *dummy;
dummy = new Node;
while(root){
cur = dummy;
while(root){
if(root->left){
cur->sibling = root->left;
cur = root->left;
}
if(root->right){
cur->sibling = root->right;
cur = root->right;
... 阅读全帖 |
|
b*******h
发帖数: 53 | 24 收到Amazon的offer，是E-commerce这边的supply。比如warehouse该在哪里建，
warehouse内部怎么取用户买下的东西。怎么wrap等等。我觉得还是很多算法的东西，
large amount of data，in time, high efficiency. 求问有没有人知道这个position
怎么样？
面试之前来论坛里求过祝福来着，谢谢大家的祝福，收到了offer。也谢谢NND同学，在
面试前给了我一些有用的建议。回报论坛， 把我的经历给写下来：
amazon面试我的战线拉的很长，7月底amazon发邮件问敢不敢兴趣，我们给你安排电面
。我说好，因为当时实习，平时没什么时间准备，把时间安排到了8月底，8月中开始准
备，主要看了thinking in java。一面问了很多java语言的细节和概念：记得的有：1.
final， finally，finalize区别 2. Polymorphism. 3.abstract class,
interface.
4.garbage collection 5.inheritance and Compositio... 阅读全帖 |
|
m*****k
发帖数: 731 | 25 amazonLocal 组，
上上周3面的，本周2收到据信，攒人品，上面经。
印女，PM，
1. copy linked list with random link in each node. 我给的答案不是回家后
google到的那个big linklist then separate， 我让原node的random link point to
its clone。
这样也能达到要求但改变了原始link,她也没反对。
2. code IsBST,
我写了个递归，还需要看root结点是否大于left child's subtree max, 以及是否小于
right child's subtree min, 被她问到复杂度， 指出非最优，重新想了一会， 说那
就inorder traversal , 每次和前一个值比一下，先给一个Prev=-infinity, 在白板上
纠结了一阵写出了和http://www.mitbbs.com/article/JobHunting/31990685_3.html相似的code.不过我是把prev传入IsBST,而且用
prev = +infinit... 阅读全帖 |
|
a**h
发帖数: 2150 | 26 1
2 3
4 5 6 7
可不可以所有结点编号存到数组中.恢复时,根据编号找对应位置. |
|
g*********8
发帖数: 64 | 27 我觉得可能不行，用一个v，本质上还是copy，否则如果传引用的话，比如我右边的
traverse中加了一个结点到path上，左边立刻就加了一个，这个不对啊。 |
|
l*********t
发帖数: 371 | 28 好像是的。
归根结点intel是个硬件公司，
这个朋友国内本科ＥＥ，美国CS Master, 估计这是这是她跟Intel能对口的原因吧 |
|
l*********t
发帖数: 371 | 29 好像是的。
归根结点intel是个硬件公司，
这个朋友国内本科ＥＥ，美国CS Master, 估计这是这是她跟Intel能对口的原因吧 |
|
l*********t
发帖数: 371 | 30 好像是的。
归根结点intel是个硬件公司，
这个朋友国内本科ＥＥ，美国CS Master, 估计这是这是她跟Intel能对口的原因吧 |
|
l*****a
发帖数: 14598 | 31 能说一下你原题的pointer指向什么吗？
删掉结点之后又准备指向什么？ |
|
l*****a
发帖数: 14598 | 32 就是数组。
对于a[i]两个子结点是a[2*i],a[2*i+1] (如果有的话) |
|
|
l*****y
发帖数: 56 | 34 ht 是一个测深度的函数， 如果在某个结点两个子树的深度相差大于1就返回－1， 否
则返回两个子数的最大深度。
不知道有没有问题，请指教。
int ht(Node p){
if (!p) return 0; /* 之前写成1了，应该是0.
int L=ht(p.left);
int R=ht(p.right);
if (L!=-1 && R!= -1 && abs(L-R)<=1 ) return max(L+1, R+1);
else return -1;
}
int main(){
Node p;
if(ht(P)!=-1) cout<<"It is balanced!\n";
} |
|
d********w
发帖数: 363 | 35 apple面试经历：最后被一个变态中国人给灭了，问了我一个半小时，太过分了。干脆把面
经公布出来，希望大家能有机会。
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，grep 电话号码
第二次onsite都是hadoop相关，join的mapreduce实现，分布式wc 列出文件行数， 见
了3个... 阅读全帖 |
|
l******o
发帖数: 144 | 36 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
d********w
发帖数: 363 | 37 删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expression tree设计，gr... 阅读全帖 |
|
l******o
发帖数: 144 | 38 我了个去了，这些题还真是难啊
删除个人情感，把纯面经提供给大家，
面试职位: c++ server-side engineer
requirement: c++, python, hadoop, 数据库，large scale data process
组：GEO Team
第一轮onsite，每个人45分钟
round 1：c++ shared pointer用法和实现，python generator, yield, list
comprehension，xrange, range区别，结构题对齐，编程 FIFO队列
round 2: hadoop相关，deamon进程有那些，循环有序数组查找，递归和非递归
round 3: 电梯设计,调度算法
round 4: 拓扑排序, 矩形相交，树的结点个数，位运算
round 5: map/reduce 程序，相当与sql(select count(*) from a where c='x')， 位
运算，将16个{00，01，10，11}变成一个32位整数，并解码。 fib递归和非递归
round6：几何题，求方块和圆弧的交集，expr... 阅读全帖 |
|
d********w
发帖数: 363 | 39 cloudera面试也算是挺变态的，先是一轮coding homework, 两轮电面，两次onsite,
主要是面hadoop了。很多题已经及不清了。现在把当时笔试题给大家参考一下
Write a program that takes an integer and prints out all ways to multiply
smaller integers that equal the original number, without repeating sets of
factors. In other words, if your output contains 4 * 3, you should not
print out 3 * 4 again as that would be a repeating set. Note that this is
not asking for prime factorization only. Also, you can assume that the
input integers are reasonable in size;... 阅读全帖 |
|
d********w
发帖数: 363 | 40 他们家老印太多了，不推荐去吧
1. threadpool design: 给出一些任务, 并发去处理，设计到queue排队等待，同步在
哪里加锁，线程池预先分配，饥饿和队列溢出的处理
2. 压缩算法，给一个16进制字节流如何压缩
0x 12 32 FD FD 32 43 43 43
3. 实现semaphore
4. 2-phase commit 要几次通信，3-phase commit呢，分布式系统中给一个信息，如何
最快传输到每个结点，gossip？
5. 给一个任意的path “/etc/abc/def/a.txt”去验证是否存在，如果是目录的话，假
设可以用getFiles()获取所有的当前文件和子目录，然后给一个父目录，/etc/, 遍历
所有的子目录和文件，判断是否文件句柄有效，这道题也有些模糊了。 |
|
d********w
发帖数: 363 | 41 他们家老印太多了，不推荐去吧
1. threadpool design: 给出一些任务, 并发去处理，设计到queue排队等待，同步在
哪里加锁，线程池预先分配，饥饿和队列溢出的处理
2. 压缩算法，给一个16进制字节流如何压缩
0x 12 32 FD FD 32 43 43 43
3. 实现semaphore
4. 2-phase commit 要几次通信，3-phase commit呢，分布式系统中给一个信息，如何
最快传输到每个结点，gossip？
5. 给一个任意的path “/etc/abc/def/a.txt”去验证是否存在，如果是目录的话，假
设可以用getFiles()获取所有的当前文件和子目录，然后给一个父目录，/etc/, 遍历
所有的子目录和文件，判断是否文件句柄有效，这道题也有些模糊了。 |
|
d********w
发帖数: 363 | 42 我记得linkedin有道题问
给个tree，让你把每个结点的值更新为自己子树的sum，
写个多线程版本，改怎么做么？
是不是还有并行的quicksort, mergesort |
|
d********w
发帖数: 363 | 43 我记得linkedin有道题问
给个tree，让你把每个结点的值更新为自己子树的sum，
写个多线程版本，改怎么做么？
是不是还有并行的quicksort, mergesort |
|
p**********8
发帖数: 55 | 44 今天看career up 150题的时候做到平衡树的题目。
他是这样描述的
Implement a function to check if a tree is balanced For the purposes of this
question, a balanced tree is defined to be a tree such that no two leaf
nodes differ in distance from the root by more than one.
想请问大家下边这样的算是平衡吗？因为我记得以前的定义是说每个结点的左右子树深
度之差不超过1。下边的这棵树好像不符合这个定义但是符合150题上的描述吧。
1
2
3
4
这样的呢？谢谢大家了。
1
2 3
4 5 6 7
8 9 10 11
... 阅读全帖 |
|
s******t
发帖数: 169 | 45 PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。
其实... 阅读全帖 |
|
H**********y
发帖数: 7928 | 46 赞
PhD念得不开心，刚来就被老板push到死，对研究的兴趣逐渐转变为每个星期的汇报任
务，感觉不爽，准备工作去。本来以为基础还凑合，国内参加过ACM拿过一个小奖，平
常也捣捣自己写的小project，但是基础不牢，从来做题需要哈希的时候就直接map，要
二分的时候直接lower_bound。这样的习惯直接导致我看career cup反感觉不适应。。
。做题目什么的时候从来就没用过链表之类的东西，写个删除结点能写半天。
然后就这样的状态面google，感觉答得还不错，不知道咋的就被刷了。
google的题目：
在一个平面(N*M的grid）上有W个点，求在这N*M个点中跟W个点距离和最小的一个点。
似乎这个是个经典题目，一开始没想出来，提示了一下做出来了。
另外一个问的：
直接递归法求fib（N）的复杂度是多少
还有很多杂的，各种数据结构复杂度是多少之类的。
一星期之后催HR结果被拒。悲剧。
然后急了，本来找得就比较晚，２月才开始准备，于是各种乱投简历，多数石沉大海。
本来都有点绝望了，准备好好准备一年算法搞一年竞赛明年直接申工作得了，结果拿到
了一个start up的intern。... 阅读全帖 |
|
l****p
发帖数: 397 | 47 最后一轮面试由4次视频面试组成，每次45分钟，总共持续3小时。相比前两轮面试，这
轮的面试官都是比较有经验的工程师，问的问题难度也相应加大。
第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
第二次面试。面试官大部分时间都在聊他们组在做的项目，面临的问题，然后问我的兴趣
第三次面试。来自另外一个组的面试官继续聊他的工作，关于performance test方面的
。然后问我是不是对统计学很熟，我说了解一些，用得更多的是数据挖掘和机器学习的
。接下来他就问我聚类算法，我先把k-means给他说了一下。然后问如果数据量很大怎
么办。我说可以用一些top-down或bottom-up的算法，想办法分布到多台机器上去算。
接下来又问我如何构建一个Bayesian Network，我说我用现成的包，自己没写过，然后
一边回忆Bayesian Network。他好像不想拷问我具体的原理，就开始说他怎么用
Bayesian Network来查找性能瓶颈的。他问我一般跑那些数据挖掘的程序要花多少天，
我说几个小时到一两天吧。那时间主要花在哪？我说把数... 阅读全帖 |
|
m****i
发帖数: 650 | 48 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
|
m****i
发帖数: 650 | 49 第一次面试。上来先问一些我研究相关的问题。然后出编程题：给一个二叉树，找出最
长不重复的结点间路径。
这个啥意思呢 |
|
l****p
发帖数: 397 | 50 怎么预处理比较好呢？用breadth-first search的复杂度能达到O(4^n)，如果最近结点
很远的话，那也是很耗时的。
Twitter基本得面试完一周后才有结果，然后schedule下一次再拖它一周 |
|
