g**u
发帖数: 583 | 1 今天刚面的Amazon，求祝福
面的题目如下：面的是5个人，第一个是HR， 就聊了些大概的问题，关于Amazon,有关
面试安排， 面试的语言和他们的工作流程之类，略无不表。后面面了4个engineer，把
记住的题目说一下。
每轮面试45 minutes， Interviewer will come to the office.
有个的题目是：如何找到bst中第二大的数；可以用in order visit,然后返回倒数第二
个，但是时间和空间都是O(n)；要求improve，一个方案是寻找最大值（right most
nodes),然后寻找bst中最后一个小于该node的节点（log n)，要求code实现第二个方法
；然后是要在hash table中实现一个function可以按照插入的顺序打印出来；接着是实
现linux下面的count words，用了2个whileloop分别处理当前指针在word中和word间的
空格，要求2种情况一起处理，写了一半没写完（缺少练习啊）
有一个题目是关于C++和Java中的内存分配的；然后问了关于3-tier(UI, middle-tier
... 阅读全帖 |
|
a**********2
发帖数: 340 | 2 1.Convert a min heap to BST without changing its structure and of course no
extra space .
2.Convert a BST to max heap without using extra memory and in as optimum
time as possible |
|
g**********y
发帖数: 14569 | 3 heap sort result is sorted array, to convert it to an BST in heap structure
seems not trival, especially inplace. For example, an array
1, 2, 3, 4, 7, 8, 9, 10, 14, 16
it's corresponding bst in heap structure should be
9, 4, 14, 2, 8, 10, 16, 1, 3, 7 |
|
g**********y
发帖数: 14569 | 4 heap sort用的额外变量应该可以，问题是转化成按heap结构排的BST, 那个要inplace
的话，好象很难。
balanced bst没法存在指定的数组空间里。 |
|
a**********2
发帖数: 340 | 5 想了一下可不可以这样做：
用sorted double linked list作为两个结构转化的过渡结构
1.1) min heap --> sorted double linked list
2) sorted double linked list --> balanced BST
2.同理，BST 按inorder 转成sorted double linked list， 再转成min heap |
|
k****n
发帖数: 369 | 6
no
2> The first thing I can think of is to still use siftdown method, the only
benifit is we don't need to do comparison, just use the right child. This
has been O(N), can it be faster? Let's see what is happening in the
heapifying process:
In a BST:
X
X4 | X
X X1 | X X
X X X2 X3 | X X
At first, X3 will swap with X1, then for X4, it will swap with X3 and then
X1.
So because of the feature of BST, an element is always swapped at the right
hand side, and gurantees to be swapped to the bottom. So ... 阅读全帖 |
|
n******a
发帖数: 114 | 7 刚面完，累。基本的3人，后来又加上另一个组的一个，完了等了40多分钟，跟这4个人
的boss的boss谈了不到半小时，基本闲扯。
第一个很nice，上来就是聊背景和简历上的东西，聊了都1个小时了，才发现时间快到
了，随便问了个design and test vending machine的问题。
第2个也不错，很nice，吸取上一个教训，留够了时间谈算法，2个sorted linked list
，怎么combine，给了2个算法，recursive和non的，讨论好坏，最后写test plan，这
次提前了5分钟完工。
第3个比较话少，lunch interview，基本都是我在说，他吃完了，我才一半。上楼继续
算法，给了tree，但是每个node还包括父节点的指针，要求找LCA，注意，不是bst。这
个因为一开始没理解清楚，一直当是bst在想解法，耽误不少时间，最后他给了提示的
情况下，解出来了，是不是最好的也不知道，谈test plan时，开始急着总结了，说下
一个人等着在。
第4个南非的，带点英国腔。考虑一个application which is constantly fet... 阅读全帖 |
|
e******s
发帖数: 38 | 8 这个题不是BST， 就是一般的binary tree.
当然有别的题是BST里找。
of |
|
k****n
发帖数: 369 | 9 来自主题: JobHunting版 - 一道G老题 no way, eventually you must visit every node of bst,
so cannot be less than something times n.
by master theorem, set both bst and tree sizes n
it should be
f(n) = 2*f(n/2)+lgn
so a=2, b=2 and n^(log_b~a) = n, case 1 applies
f(n) = O(n)
which is as good as in-order traversal plus array cursor.
If you don't remember master theorem, think this way:
for the leaf nodes, you do binary search in every section of array,
about 1/2 times leaf nodes of binary searches in the second level,
... ..., this ma... 阅读全帖 |
|
x****1
发帖数: 118 | 10 Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
得住的说吧。废话不说，直接上题：
Phone screen：
先问了10道左右的小题，都是概念性的。
包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
有没有多线程，怎么实现。
最后还有5分钟结束的时候，给留了两道coding题，让我明早之前发给他。
一个就是binary search，不用多说了。
另外一个就是如何查找rotated sorted array (这也是很常见的题，因为面试官讲的是
cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）... 阅读全帖 |
|
k*j
发帖数: 153 | 11 我觉得这题难点就在如何维护一个BST，使得insert,delete，search都是lg(n)。只能
用BST。有同学写出来了吗？ |
|
k*j
发帖数: 153 | 12 我觉得这题难点就在如何维护一个BST，使得insert,delete，search都是lg(n)。只能
用BST。有同学写出来了吗？ |
|
k****n
发帖数: 369 | 13 by adv/disadv, you must specify something to compare with...
Then the answer should be trivial, like
Compared with BST, hey can both used to abstract "dictionary". Hash
table is averagely faster, easy to implement, worse worst case
complexity, space waste (actually it is hard to tell)
BST is not only dict, but an ordered set, hash table is not ordered...
Compared with array, linked list, ... ...
You will have more than an interview's time to cover as long as he allows... |
|
x****3
发帖数: 62 | 14 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 15 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
V*****i
发帖数: 92 | 16 先说说本人大致情况：三流大学EE PhD，毕业后做博士后，一边找工作，因为觉得自己
编程还挺在行，所以主要找大公司的软工职位。近一年来骑驴找马，先后面试了Amazon
, Google, Bloomberg，可惜都挂了。其中Amazon是三轮电话面试，Google, Bloomberg
是onsite。
Amazon被一个很大路的题目问倒了(if BST)，但因为那时还没有经验，所以也很淡定。
Google本身比较难进，我发挥的也一般，所以悲剧也不难受。但最近Bloomberg悲剧让
人很接受不了，觉得他家不是很难，我也发挥的很好。
痛定思痛，觉得我准备的一个重要问题是单打独斗，可能写的程序并不好甚至有错(比
方说if BST)，但没有人指出；还有一些软题，比方说design question，可能自己想的
答案并不理想。因此，希望找一个情况相似的人一起准备软工面试，可以探讨题目，批
判对方程序，研究design question等，另外我在休斯敦，如果你在附近的话还可以
mock interview。
有兴趣的给我站内写信。希望你是serious的job hunter，也准备了一段时... 阅读全帖 |
|
g*****i
发帖数: 2162 | 17 bst怎么做? unbalance bst的话10和5在两个不同的tree里,怎么找到这对pair? |
|
S**I
发帖数: 15689 | 18 ☆─────────────────────────────────────☆
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... 阅读全帖 |
|
e*****0
发帖数: 82 | 19 上周六面的Salesforce QE，刚在路上走接到recruiter电话，给了full time offer~~
package细节没太听清楚，只记得有105K的base，6K sign on bonus, blablabla, 过
两天会收到寄来的offer letter
好了，看来可以去三番吃海鲜玩帆板啦，有同去salesforce/三番的联系我哈～～
--------------------------------------------------------------
补上面经：
在学校招聘会看到S家牌子，七八个人在那热情洋溢的宣传。本来想申developer职位，结果他们看到简
历上有automated test（不过是unit test而已）就让QA组的人和我聊。QA组长笑眯眯的介绍半天，
我说俺不想长期做QA哎。组长赶紧说S家两个职位待遇是一样滴，都要编程的，进去后也是可以换方向
的。好吧，于是一周后收到on campus面试通知。
On campus当天两个人，面一个小时。两人还是超热情，一去就说这么早来面试真是不容易啊（我心想都
九点了...）。面试前一天，他们... 阅读全帖 |
|
A**u
发帖数: 2458 | 20 你这也太夸张了
bst都用上了
得自己写一个bst?
面试来说，是不是太麻烦了 |
|
A**u
发帖数: 2458 | 21 你这也太夸张了
bst都用上了
得自己写一个bst?
面试来说，是不是太麻烦了 |
|
w****n
发帖数: 402 | 22 可以打中文了，先感谢大家的祝福。有朋友问我怎么tricky,想了半天，实在不知道怎
么在不透露题目的情况下说清楚。且一试：
熟悉Graph,Tree, 尤其是Binary Search Tree的representation, properties and
manipulation algorithms。For BST, think about when the tree is not full and
balanced, how to do things efficiently. Think about what will happen if the
basic property of BST is violated at some node.
Sorry cannot give more detail。
加点建议，把Programming Exposed和Cracking两本看看，如果编程不是很熟练最好把
题目的code都写写。我本人没有搞题海，没看面经，就是这两本书，面世的时候碰到一
道和书里基本一样的。 |
|
S****h
发帖数: 558 | 23 No. We have already discussed about hashtable. On a cluster environment, I
told him that we might want to do a two-level hash, first map to one node.
He seemed not against it. Then he said, let us switch the gear and looks at
alternative to hash. For BST, I said, we can do make something like
multilevel hash, first map to one node with a big branch. Then within the
node use BST. He seems to have something more in mind.
He is from AWS unit. That seems a very relevant question for them. |
|
p*********b
发帖数: 47 | 24 在这儿潜水很久了，学习不少。也报点面经吧，我投的是 Mobile Software
Development Engineer。
我真不记得有没有一轮HR phone screen了，有记忆的是做了一个coding exam，没有时
间限制回头发给他代码的那种。一个是实现atol，一个是写个Trinary search tree的
类，跟BST的区别就是多了个middle指针，存和本节点值相等的node，要实现insertion
, deletion，大概原理和BST差不多，照着CLRS改改就行了。。。github上有个现成的
代码，不过里面有好几处错误，不能直接抄。两题都是让用Java写的。11月初给我的题
，我12月才写。
约了今天下午phone interview，先是问了问简历，most exciting course and
project, 最困难的问题这类。
然后问Hashtable各种常规概念优缺点，然后就是问一个文件有2^32 - 4个不同数字，
要把这四个数字找出来。我说用Bitmap，通过set bit的方法数出现过的数字，O(n)时
间，空间 2^(24-8) B... 阅读全帖 |
|
v***a
发帖数: 365 | 25
这题区间不 overlap，所以随便建个 BST 就可以做了，key 是 Start
题目就是普通的 BST insert 了 |
|
S**I
发帖数: 15689 | 26 ☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 15:15:14 2011, 美东) 提到:
刚从G家onsite归来。新鲜面经奉上。
总共5轮，4轮technical interview, 一个thesis discussion。在technical里，有编
程题，有open design。我记得的问题有：
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
2. open question: 一堆文件，size差别极大( from KB to many GB). 找出所有内
容相同的文件。
3. 编程题： 有一个observer 类，监视另一个类foo 的成员变量的值，每当那个值被
修改，就要调用 该observer.updated() 方法。需要实现 foo.registerObserver(ob)
, foo.unregisterObserver( ob )... 阅读全帖 |
|
i******n
发帖数: 94 | 27 The interviewer mentioned if given a perfect balanced BST, if we have the
min node and continuously call the successor function n times.(n is the
number of nodes)So that we could have the in order traverse of the BST. Then
what's the complexity of this algorithms? He said the complexity is O(N),
could anybody help me with this? I am a little bit confused. |
|
N*****8
发帖数: 253 | 28 那为什么必须是perfect balanced BST，任何的BST不是都可以？
)。 |
|
g*********8
发帖数: 64 | 29 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traver... 阅读全帖 |
|
g*********8
发帖数: 64 | 30 第一题ihascode1337的确给出了两个数组不一样的长度的情况，如果一样的长度可以参
考Algorithm Design (by Kleinberg) Chapter 5 Exercise 1,其实也很简单，就是
binary search 的variant，但是这两道的题的coding都很tricky，要非常注意，主要
是递归函数调用的参数传入
他们的coding让我想起了由tree的in-order, pre-order， reconstruct the
binary tree的题，也是一样的tricky编程，也是递归函数调用的参数传递
另外amazon好像还有很好玩的新题：
1）Given a tree preorder sequence such as “NNNLLLL” where N denotes non-
leaf node and L denotes leaf node, with the constraint that no nodes has 1
child. Rebuild the binary tree
2） Given post order traver... 阅读全帖 |
|
e***s
发帖数: 799 | 31 来自主题: JobHunting版 - 电面犯二了 Bless.楼主别急嘛,也不一定挂,就算挂了，A家不打打G家！
我的解法是顺序遍历其中一个BST，然后再另一个BST上逐个找，找的同时用HASHSET放
每一个NODE的VALUE。找下一个的时候现在HASHSET上找。
个人觉得比较BRUTE FORCE。
求牛B解法。 |
|
P***P
发帖数: 1387 | 32 上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是不
是跟generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有没有空位
子，提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时候用
hash, time complexity多少.
他让我讲讲h... 阅读全帖 |
|
m*****a
发帖数: 636 | 33 心理素质好，google使用得当。
祝马上有好消息
上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是
不是跟
generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有
没有空位子，
提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他
怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时
候用
... 阅读全帖 |
|
w****o
发帖数: 2260 | 34 "比如什么validate BST LCA之类的。。"
这指的是什么题呀？
是不是判断一个树是不是BST?
求LCA (lowest common ancestor) in a BT?
谢谢！
。。 |
|
w****o
发帖数: 2260 | 35 "比如什么validate BST LCA之类的。。"
这指的是什么题呀？
是不是判断一个树是不是BST?
求LCA (lowest common ancestor) in a BT?
谢谢！
。。 |
|
w*******l
发帖数: 14 | 36 来自主题: JobHunting版 - G家一面。 PHONE1：
1.解释什么是BST，hashtable，时间复杂度是多少。给出情况什么时候用哪个。
2.遍历BST的算法，复杂度。
3.(5,10)(15,17)(18,25) 插入 (16,35)
合并成（5，10），（15，35）
PHONE2：
1.解释C++和JAVA的区别。
2.JAVA的GC机制。什么变量在heap里什么变量在stack里。accessible from root，
root是从哪里。
3.给一个排好序的数组画平衡二叉树。
问题都很水。。OVER。 |
|
g***i
发帖数: 4272 | 37 两个电话面试，紧挨着，两小时完成的，还挺简单的
1. 两个array 的intersection
（用了个set,直接七八行写完，说了个ok就过了）
2. BST inorder next node
（careercup原题，可惜忘了，写了好久。还有一处有个bug，问我&&逻辑先后，short
circuit问题）
---
1. 10^9个star，亮度为double类型，找出前一千个最亮的
（我一开始说用heap，后来发现不好用，就改了bst，size 1000的，超了就比较最小的
，删除最小的，再插入）
2. 一个动态规划的题目，好像是intro to design & analysis of algorithm上的课后题
3. monochrome bitmap，找出最大的白色矩形。
（卡这了，brutal force也不太会），求教这个咋做 |
|
l****p
发帖数: 397 | 38 太久了，我不记得当时说的是tree还是BST了。不过这个确实需要特别向面试官clarify
的，因为有些算法仅适用于BST |
|
h*****g
发帖数: 312 | 39 Check if identical BSTs from given number streams
Question: You are given 2 number streams. You need to find whether they will
create the same BST or not.
Example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True
Array1:10 5 20 15 30
Array2:10 15 30 20 5
Result: False |
|
w****o
发帖数: 2260 | 40 能不能解释一下这个题给定的条件和要解决的问题？好像很模糊的。
number steam是按照BST的什么order遍历的结果，还是随意的？
为什么第一个例子返回的结果是true? 而第二个例子的结果是false? 我看不出有什么
不同。
还有number steam里面可以有重复的数字吗？
我记得BST的左子树的数字 <= 当前的节点 < 右子树，对吧？
will |
|
l***i
发帖数: 1309 | 41 actually topcoder is very different from interview, or even ACM ICPC or
Codeforces for this purpose. There are plenty of problems asking people to
convert BST to linked list, sort linked list, implement a hashtable, find
next/prev of BST, binary search. In topcoder and similar places, you always
use stl algorithm to do the job. |
|
w***y
发帖数: 6251 | 42 在复习dynamic programming. 看到别人的一个list, 都是简写, 很多我都不知道是什
么问题. 麻烦大家帮我看一下吧. 我能猜到的我标了一下, 2-4, 6, 8-11 我都不知道
是什么问题?
1. BST optional BST??
2. COV
3. ILP
4. KS
5. LCS Longest Common Subsequences
6. LSP
7. MCM Matrix chain multiplication
8. ODP
9. SCP
10. SPA
11. SPC
12. TSP Travelling salesman problem |
|
p*****2
发帖数: 21240 | 43 来自主题: JobHunting版 - 讨论一道题 这个刚才我也想过
不过java里更新的时候要delete insert
heap不能解决频度发生改变时的调整，所以我想到的可以用hash BST解决，C 里BST的
实现采用setmap freq;set
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
l*********8
发帖数: 4642 | 44 来自主题: JobHunting版 - 讨论一道题 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。 |
|
p*****2
发帖数: 21240 | 45 来自主题: JobHunting版 - 讨论一道题 用hashtable找
既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
s***0
发帖数: 117 | 46 Sorry to hear you had a bad experience.
Amazon's interviews are designed so that candidates DO NOT have the reaction
you are having. The interviewer is supposed to be nice and engaging even
if the candidate is really really bad. Very surprised to hear that someone
would tell you that you did not do well.
Does knowing BST make a good SDE? Well no, but it's an hour interview and
there are lots of candidates. BST is popular because you must have a
certain level of intelligence and coding abilit... 阅读全帖 |
|
l*********8
发帖数: 4642 | 47 Maybe we can only create the BST once. And we clear the BST every time
before matching a new group of integers.
more
time |
|
O******i
发帖数: 269 | 48 两个BST，求他们merge后的BST
这题有什么trick? merge结果是唯一的么？
总不是trival的遍历一棵，依次插入到另一棵吧？ |
|
z********c
发帖数: 72 | 49 这个他说不好，最后那个方法好雷。。。。
in order traversal。。得到两个list,merge list, reconstruct from the list
我说这方法跟BST有毛关系啊，硬生生把merge sorted list和construct balanced bst
from sorted list 放到一起考 |
|
O******i
发帖数: 269 | 50 是晕了，一道题瞬间变为三道题
1) 遍历二叉树， 说不定还要考非递归的方法
2）Merge two sorted list
3) Construct BST from sorted list
bst |
|
