h******3
发帖数: 351 | 1 请问能否share
Binary Search Tree In Order Iterative Traversal without using a visited flag
的方法?
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
|
i**********e
发帖数: 1145 | 3 leaf 之间最大的距离？不是很懂。leaf之间必须是同一个level的吗？如果不是同一个
level的应该怎样？
我知道preorder序列能重建BST。但inorder序列不能重建原来的那个BST吧。是不是
inorder序列建一个平衡的BST？
感谢你的补充题，我会研究研究下。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 4 比如下面这个树
1
2 3
6 7 9 11
1,3和11没有nextRight
2的nextRight是3
6是7， 7是9， 9是11.
注：没有nextRight应该把nextRight指向NULL.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
s**a
发帖数: 131 | 5 Thanks.
集的一些常见二叉树面试问题（包括我亲身经历的）。多做多练习，相信你一定可以掌
握好。
left |
|
i**********e
发帖数: 1145 | 6 更新：
Finding the Maximum Height of a Binary Tree
这题就是寻找二叉树的最深度，利用DFS可以轻松解决。挑战的是：如何写非递归的版
本。有两种解法，一是用BFS，解法比较直接。另一种解法是转换成非递归BFS，方法请
参考In-Order Traversal Iterative Solution.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 7 更新：
添加了两道新题，请参考第一页：
Serialization/Deserialization of Binary Tree
Rebuild Binary Search Tree from Pre-order Traversal
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 8 怎么可以用一个queue+stack来打印zig-zag呢？
例如：以下这个例子，怎么打印 0, 1, 2, 3, ..., 14?
___ 0___
/ \
1 2
/ \ / \
6 5 4 3
/ \ / \ / \ / \
7 8 9 10 11 12 13 14
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 9 Print Edge Nodes (Boundary) of a Binary Tree
问题是要把树的周围counter-clockwise打印出来。先打印root，然后从上到下打印最
左边的节点，然后从左到右的顺序打印叶子节点，然后从下到上打印最右边的节点。这
题的精粹就在于使用depth-first traversal，一个递归就能搞定。先把树分为两个树
（root的左孩子和右孩子）处理。先处理左树，再处理右树。如果卡在怎么从下到上打
印最右边节点，可以想想post-order traversal。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 10 更新，加了一道新问题总结：
Binary Tree Post-Order Traversal Iterative Solution
这题比起 In-Order Traversal 难多了。是很罕见的面试题，好像只有 amazon 问过这
道题。用 visited flags 好做很多，但是不用 visited flags 还是有可能解出来的。
思路就是利用一个变量储存之前访问的节点。然后在每次循环的时候比较之前节点和
stack 上的节点，这样就可以知道我们在往上还是往下走。如果往上走的话，就能得知
是从左节点还是右节点上来的，这有大大的帮助。另外一个方法是使用两个 stack，解
法很简洁，很巧妙，但是空间复杂度没有一个 stack 的解法少。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 12 更新，一道新面试题总结：
Largest BST in a Binary Tree
要求在树里找最大的 BST subtree。注意，这里指的是 subtree，如果不清楚定义，先
跟面试官确定一下。subtree 在维基百科的定义是指包括树节点和它所有的
descendents。做这题前必须知道怎么才能判断树是不是 BST。这题的巧妙之处在于利
用了 bottom-up 的 Depth-first 遍历来解决所有 top-down 遍历的难处。当然，如果
面试官要求的是 largest BST（不一定是 subtree），那就是另外一套思路了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 14 longest increasing sequence 的方法来找最大的 BST（不管是 subtree 与否） 是个
容易掉入的误区。
你可以参考一下我贴的图片，这就是其中的反例之一.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 15 Could you please explain the idea of your code?
I am not quite sure of your idea.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
i**********e
发帖数: 1145 | 17 你这个答案不够优化，因为：
1）必须构造新的链表，需要额外空间。
2）必须把每一个元素给de-allocate，然后再allocate memory，需要额外的时间。
最优解是不需要变动元素的内存位置，变动的只是指针。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
|
m**********r
发帖数: 122 | 20 linux scripting 一般都有哪些常见的面试题？临阵磨枪一下。 |
|
K*****k
发帖数: 430 | 21 从自己的经历和他人的面经看，很多时候，70%或者更多的题目都是版上见过的简单题
，常见题，经典题，也就是你onsite的时候绝对有思路.
但是有思路不等于能写对,能写好。
如果70%的轮次,你都出现了这样或那样的小bug, 或者：
1) 代码过于冗长，变量引入太多，重复代码摆在那（可以抽取成函数），不善于利用
现有的类，Java的数据结构或者C++的STL（比如没有必要写一个基于数组的，自己维护
top指针的裸stack)
2) 代码风格不好，命名，缩进，空行有问题
3）做完不检查，忙把代码交，漏了边界条件，非法输入，溢出。
4）不探讨其它的方法，不引申关联的主题和扩展
我想因为这样失败的例子肯定不少。
我有一个MSFT失败的电面例子：
题目很简单，就是经典的数组求连续的子数组最大和，心中暗喜，很快搞定。
老印接着问，如果数组全是负数怎么办？我说这个方法返回0
老印说，如果要求返回最大的负数呢？
我说检查这个特殊情况单独处理，然后开始写代码
1）先写了第一个一重循环，判断是否全部是负数
2) 如果不全是负数，用先前的方法，第二个一重循环
3）如果全是负数，在用第三个一重循环找到最大的负... 阅读全帖 |
|
s*********d
发帖数: 2406 | 22 cool
判断是否BST也是常见题
Linkedlist cycle |
|
g***j
发帖数: 1275 | 23 我拿了MS的offer，然后在犹豫是否relocate，于是给HR发了信，HR回复的时候cc给我
未来的老板了，未来的老板直接给我写信，解释西雅图怎么好怎么好，还说要找时间
chat。请问，这种情况常见么？搞得我压力很大啊。 |
|
|
j******2
发帖数: 362 | 25 哦。
第一问具体是不是这样：
用3个phase:
1. 确定在哪个million——O(n)
2. 确定在哪个thousand，并根据前面和后面的数，确定要找thousand里的第k个数——
O(n/1000)
3. 用partition的方法找出一千个数的第k个数——O(n/1000000)
总的时间复杂度还是O(n)
1B的数还不到整数范围，所以每个phase只要一千个int的counter就行了, partition又
是in-place的，所以总的空间就要1k*4byte=4kb。
第二问我觉得好象挺常见着的，用两个heap做，cc150书里的18.9的原题。不过没说
stream能有多长就是了。
谢谢大师指点哦～～ |
|
M********y
发帖数: 21 | 26 好不容易过五关斩六将，反反复复的面试和跟HR之间各种沟通的无力（基本上都是他的
单向沟通，我想联系上他几乎是不可能，即使是在第二次onsite之后，他留言让我回电
话的情况下）之后，HR说要下offer了。周一电话问我salary expectation（这个我第
一次面试之前的application form里已经填了，也填了我现在的salary），我明确告诉
了他。两天后周三offer letter过来比expectation少将近20％，低于我现在的薪水。
。。
公司是很好的公司，做的东西也算感兴趣，本来是兴致勃勃的。怎么会出现这样的情况
呢。这种情况是属于常见的吗？还是我太弱太背了？还有negotiate的可能吗？ |
|
r*******e
发帖数: 7583 | 27 这是单机器的答案，常见的follow-up是如何利用多台机器加快速度
billion |
|
c*********l
发帖数: 3438 | 28 sammamish (sammamish) 发于 Sun Aug? 4 15:49:07 2013, 美东, 信区: working
标? 题: 公司面试，对方HR邀我住到她家里过夜，常见么？
是个小公司总共没几个人。在中部一个小town上。 约好星期五面试。HR突然说希望我
住在她家过夜。还说她家里只有她和一条狗。在FB上联了她，看得出是个30出头，典型
的中部Lady。房子很漂亮。
FB后她还说希望我能在她家多住几个晚上，留到周一再走。这种事正常么？ |
|
q*****w
发帖数: 62 | 29 那个帖子开头是常用java api总结。然后就是常见的树的面试题总结。不知道有谁见到
过。多谢！ |
|
S*******C
发帖数: 822 | 30 一道Amazon常见设计题，其他公司也考过
设计个电话本, 可以用那些数据结构？
Design a phone book application. He was mainly looking for the data
structure. Follow up question was to write a code to insert data into a trie!
要求是可以根据人名字找到他的电话号码，根据电话号码可以找到人名字，一个人名字
下，可以有好几个号码，但是一个号码只对应一个人
我的解法：用trie储存所有人名String，trie node中有一个List类型的成员
变量来储存这个人的电话号码，这个解法是不是最优的？如果不是最优又该怎么做呢？ |
|
h***n
发帖数: 1600 | 31 找intern，发过来几道题目，其中的一道题目像这个样子：
• A father, a mother, 2 sons, 2 daughters, a guard and a prisoner
want to cross the river.
• The raft can carry only 2 people.
• The father cannot be left with any of the daughters unless the
mother is present
• The mother cannot be left with any of the sons unless the father
is present.
• The criminal cannot stay with any family member unless the guard
is present.
• Only the father, mother, and guard know how to... 阅读全帖 |
|
c*****u
发帖数: 867 | 32 请问谁有请问谁有Java常见面试题？就是常考的知识点，比如hashmap、
concurrentHashMap、hashTable之间的区别，就是这种knowledge based的题。
谢谢大家，高手轻拍。如果只是想拍，那就拍吧，我只是想问问有那些常考题而已。 |
|
d*********e
发帖数: 141 | 33 那些常见的设计题，有没有大牛总结过了啊，谁有资料可以分享下吗 |
|
k***e
发帖数: 1931 | 34 面试最近似乎经常面到分布式环境下的设计问题，比如设计一个分布式的storage
system，分布式health monitoring system，有没有什么好的材料可以针对常见的
design问题介绍和解答的？ |
|
发帖数: 1 | 35 看看open souce的doc 有时间再看看源码
比如hdfs，yarn
[在 koote (koote) 的大作中提到：]
：面试最近似乎经常面到分布式环境下的设计问题，比如设计一个分布式的storage
：system，分布式health monitoring system，有没有什么好的材料可以针对常见的
：........... |
|
|
b******y
发帖数: 2729 | 37 发信人: chinagogogo (吃拿走 (闷声才能发大财)), 信区: Stock
标 题: 公司面试，对方HR邀我住到她家里过夜，常见么？ (转载)
发信站: BBS 未名空间站
是个小公司总共没几个人。在一个小town上。 约好星期五面试。飞过去的。昨天和HR
简单视频面试后，她突然说我头天晚上可以住在她家过夜。还说她家里只有她和一条狗
。HR是个30出头的白女，典型的中部Lady，FB写是单身。房子很漂亮。
FB后她还说希望我能在她家多住几个晚上，留到周一再走。这种事正常么？ |
|
w*****g
发帖数: 1415 | 38 1. 最先分析query，看看query有没有优化的空间，或则简历index
2. 预先计算某些query的结果，然后存起来。比如学生的GPA，实时算起来很费时。我
们就建立一些trigger，每次某些数据库表有变动就自动计算并保存结果到GPA表。
3. 静态化，最常见的是新闻系统和文章管理系统。每次更新新闻/文章的时候，产生一
个文本文件，在file system里面存储。用户读取的时候从文件系统读，不经过数据库
，或者只有小部分数据经过数据库。
4. mysql replica，费时的查询可以交给只读的Mysql
5. memcached/redis
6. 升级服务器硬件（很多时候这个方法最省钱省时间） |
|
s*****r
发帖数: 43070 | 39 常见的办法就是sharding，把大量数据分散存储
如果query需要join的，比较麻烦。一小一大，可以用hash join
大数据计算的主要目的其实就是join table |
|
q******0
发帖数: 32 | 40 最近看到一个人list的一些常见东西的国内和美国价格，美国这边的价格看上去挺靠谱
，国内的那部分不知道靠谱不？ 好些年没有回去了。呵呵
在美国买辆奔驰E-320，50000 元，相当于半年多的工资。
在中国买辆奔驰E-320，980000 元，相当于十年多的工资。
在美国买双意大利皮鞋，50 元上下。
在中国买双意大利皮鞋，1500 元上下。
在美国租一套三居室，1000 元上下。
在中国租一套三居室，2000 元上下。
在美国吃份麦当劳的巨无霸，4 元。
在中国吃份麦当劳的巨无霸，20 元。
在美国置套好点儿的西服，500 块差不多了。
在中国置套好点儿的西服，2000 块还不够。
在美国买台苹果G5计算机，顶死了1500。
在中国买台苹果G5计算机，怎么也要 30000。
在美国买斤瘦猪肉，三元。
在中国买斤瘦猪肉，十五元。
在美国订一个大生日蛋糕：二十元。
在中国订一个大生日蛋糕：二百元。
在美国买一盒哈根达斯，三块！
在中国买一盒哈根达斯，六十！
在美国 Holiday Inn(四星宾馆)， 七、八十块。
在中国 Holiday Inn， 七、八百块。
在美国加满一箱汽油，三十 |
|
R**a
发帖数: 190 | 41 靠铺个鬼头啊。
为啥在中国要吃巨无霸，而不吃地摊小面？
应该这样比：
中国吃巨无霸（20人刀）= 美国吃意大利餐馆的面条（16美刀+税+小费=20美刀）
中国吃地摊小面（5人刀）= 美国吃巨无霸快餐（5美刀）
还有啊，有没有比过：中国报销出租车和手机的费用是多少？报销汽油的费用是多少？
我兄弟在中国是主管一级，相当于这里的director之类，反正，公司给他一辆车，
汽油、保养全都包了，一分钱不用自己出。这每年省下的汽车开销，得买多少巨无霸了？
美国这里是不是很常见啊？反正，我们部门的VP，手下600多人，也没见大老板给他
买个车免费开。
还有，俺的实际收入，是工资单gross income的70%；俺兄弟的实际收入，是他
工资单的200%。
哦，对了，俺家的保姆，1600美刀一个月；俺兄弟的保姆，1000人刀一个月。
所以，最烦有人比来比去，非得证明美国好、还是中国好，没劲。
反正，我觉得，美国、中国，就是不同的生存环境。好还是不好，都是针对于不同人
的不同生活目标和方式，相对而言的。非要来比绝对值的高低，是脑子有问题。 |
|
s******9
发帖数: 11 | 42 I looked a couple of times about the headline topic "首次购房者8000退税常见
问题解答(12.3k)" for this forum, but found it is empty. I even doubt it is
an illusion, or anybody
can give me a hint? |
|
w**a
发帖数: 487 | 43 想买一些常见的中国菜种子，大家知道有什么网站有卖菜种子的吗？我们这儿离最近的
中国超市也比较远。 多谢！ |
|
B****n
发帖数: 1523 | 44 对于你这个问题，我觉得Stucco moisture问题应该是很常见
这事儿不要听realtor的，还是自己判断，买房还是小心点儿好 |
|
a********n
发帖数: 52 | 45 刷墙的是中国contractor，没有license的那种，所以也没有签合同
快完工了，他提出要现金（五六千的样子），可能是为了不交税？
这个常见吗？我们答应的话对我们有没有什么坏处？ |
|
w******t
发帖数: 16937 | 46 光图便宜的后果就是未来2年睡不着觉。
刷墙的是中国contractor，没有license的那种，所以也没有签合同快完工了，他提出
要现金（五六千的样子），可能是为了不交税？这个常见吗？我们答应的话对我们有没
有什么坏........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
l**h
发帖数: 7994 | 47 请问家具常见木头种类是什么？
好坏比较？价格差别？
多谢！ |
|
p*****e
发帖数: 537 | 48 这边常见的就那几种吧？maple,oak,birth,cherry,rubberwood.我买家具的时候就没考
虑是啥木头。只要是solid wood，样子喜欢价钱合适，（另外个人不喜欢贴veneer的）
就买了。估计你要再考虑木头那就比较难买了。 |
|
|
C******e
发帖数: 11790 | 50 LZ不喜欢的是“常见总来问”，好多问题，被反反复复重复问，问得人根本没有好好
google或者在这个版找以前的帖子来看，张口就问。 |
|
