f****4
发帖数: 1359 | 1 一模一样的题
但我觉得是个老中；周四晚上11:30(east)打来的电话，问了半个多小时
末了说把我resume给hm
hashtable & bst
问cellphone contacts怎么设计，我就说hashtable，如果没有内存限制的话
他说不对，hashtable是无序的；我和他argue bst有序的那叫binary search tree |
|
y**i
发帖数: 1112 | 2 我又想了一下，其实对于普通的二叉树，算法还是一样的，只不过需要依赖中序来实现
BST的“小于到左边，大于到右边”的属性了，这个算法就是确定唯一的重建的（不唯
一的重建有很多种，根本就不需要想算法了）。
同样，在前序序列，第一个元素肯定是根，从第二个元素开始循环，对于每个待插入元
素A[i]，如果小于之前的元素A[i-1]（对应普通的二叉树，相当于待插入元素在中序序
列里在之前的元素的左边），就插入到之前元素的左孩子处；待插入元素如果大于之前
的元素（类似的，对应普通的二叉树，相当于待插入元素在中序序列里在之前的元素的
右边），并且任一祖先不是其父结点的左孩子的时候，就插入到之前元素的右孩子处，
如果有一个（最近一个）祖先是其父结点的左孩子，就比较待插入元素和那个父结点的
值（同样，对应普通的二叉树，相当于比较待插入元素和那个父结点在中序序列里的位
置），如果小于（思想同上），同样插入到之前元素的右孩子处，如果大于（思想同上
），就插入到那个父结点的右孩子处。
总而言之，中序序列就是二叉树的顺序，是BST的有序序列，也是普通二叉树的一个顺
序参考，甚至可以看做是一个改写后的比较函数（相当 |
|
r****o
发帖数: 1950 | 3 你是说两个都以non-recursive的inorder访问?
我有个疑问是，对于第二个BST的每一个节点，怎么找到第一个BST的一对L1和L2呢？
这里是不是要用到binary search?
该也是O(1)，所以总的时间为O(n) |
|
x*******7
发帖数: 223 | 4 ood: polymorphism,overriding举例，virtual func., virtual table,abstract/
interface ...
uml:use case
知道的design pattern...
code: bst 的remove方法。
准备的时候就准备了数组，链表之类的，没准备bst，以为一面应该不会问这个。结果
弄的我当时很紧张。。。
没有问具体设计parking lot之类的，比较奇怪。不知道多久有通知。也没叫我有没有
疑问。 |
|
j**l
发帖数: 2911 | 5 BST,返回最长的path from root to leaf
和BST有什么关系？不就是普通二叉树求最大高度？ |
|
r****o
发帖数: 1950 | 6 谢谢，我没搞明白为什么是lg(n) of m character comparison for BST.
我觉得对于BST就是lg(n)啊. |
|
t*******r
发帖数: 2293 | 7 公司股票涨了，有几个臭钱，就以为怎么样。把人挑来拣去，。。。 搞得自己招不到
人，还来什么推荐大竞赛。无非是想扩大新人 POOL 进一步左挑右选。
真不觉得问几个 BST DP 就能选到好的程序员啦？ 无非是，事先知道考题类型的，准
备过的，把BST 算法背个烂熟的被选上。
那些写 Code 的活，还不是任何能来北美读书，受 CS Master， PhD 教育，写过几年
Code 的都能做。
真是对 Amazon 很反感！ |
|
f*******r
发帖数: 1086 | 8 有一个面试题目就是对于一个bst，
check是否存在 Root to leaf path sum equal to a given number:
以下是geeksforgeeks上的样例代码:
int hasPathSum(struct node* node, int sum)
{
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
我自己也写了类似的code，但是测试发现貌似不对，比如如果我有一个
bst如 |
|
s****n
发帖数: 150 | 9 把这两天我的两个amazon的电面题总结下，有些东西没记全，只能记得什么写些什么了。
1. why amazon ? 这题感觉被考几率很大，必须准备的题目
2. 谈了下简历中的project
3. stack 与 queue的区别
4. HashTable 和 Binary Search Tree(BST)的区别，他们的lookup，insert的time
complexity. 之后针对 HashTable 和 BST 分别做了展开：要从电话本中列出一定范围
的人名
（比如某个姓的），要用哪个数据结构？hash。 还谈了些别的应用情境，我记不大清
了。
5. process 和 thread的区别
6. 什么是deadlock ，有什么方法避免deadlock
7. 什么是context-switch
8. OS 中 schedule process有什么方法
9. 喜欢哪种编程语言 ？ python。 那你觉得python有哪些地方你不是很满意的 ？
10. coding, coding完后根据程序问相应的time complexity 和 test的问题:
（1）输入一个整数 |
|
p********7
发帖数: 549 | 10 4. HashTable 和 Binary Search Tree(BST)的区别，他们的lookup，insert的time
complexity. 之后针对 HashTable 和 BST 分别做了展开：要从电话本中列出一定范围
的人名
（比如某个姓的），要用哪个数据结构？hash。 还谈了些别的应用情境，我记不大清
了。
电话号码典型用trie啊。
谢谢面经 |
|
d*******r
发帖数: 23 | 11 "Programming Interviews Exposed" has the solution. One of the properties
of BST is that left subtree nodes is always smaller than right subtree
nodes. So all you need to do is to iterate through the BST from the root
and find the first node that is lesser than one node and greater than
the other node. Pseudo code:
If valuel and value2 are less than the current node's value
Examine the left child
If valuel and value2 are greater than the current node's value
Examine the right child
Otherwise
The |
|
j*******c
发帖数: 95 | 12 好。
电话面试比较简单，主要说onsite
第一轮有4个人
1.简单题。
2.bst 后序遍历建树
3.讨论research
4.有大量重复数列，做binary search
第二轮有三个人
1. 经理，讨论machine learning 算法。
这个一点没准备。瞎掰。
2. 经理，讨论lsu，c++题，纯虚函数，重载。
这个也没怎么准备，说错了一点.
3. bst 非递归中序，前序，后序遍历。 |
|
j*******c
发帖数: 95 | 13 我以前share过，再发一便
电话面试比较简单，主要说onsite
第一轮有4个人
1.简单题。
2.bst 后序遍历建树
3.讨论research
4.有大量重复数列，做binary search
第二轮有三个人
1. 经理，讨论machine learning 算法。
这个一点没准备。瞎掰。
2. 经理，讨论lsu，c++题，纯虚函数，重载。
这个也没怎么准备，说错了一点.
3. bst 非递归中序，前序，后序遍历。
我的题目都比较简单，没怎么遇到难题。
phone/on- |
|
e****9
发帖数: 316 | 14 之前两轮phone screen都是常规题目.
这周一on site,昨天刚下飞机收到hr的voice message通知被拒,赞一下hr的效率
一面:BST到排序双链表.之前准备过,所以很快给了code. Follow up问题,排序双链表到
BST,只给了个大概的想法,code没搞出来. 然后是OOD问题,餐馆预定系统.
二面:先谈一下过去的项目,技术上的难点.然后是code问题,字符表格找单词.
比如下面的3*3字符表格
1 2 3
4 5 6
7 8 9
每一个位置都是随机生成的char,给你一个字典然后找到表格里面所有可能的单词.
单词的定义是任意个连续字符组合,一个位置用过之后就不能再用.
比如14,214,159,153,1245,1457都是合法的组合.121是非法的.
这个题答得不好.想到了要用递归,但是后面code的时候有点乱.
经验教训,Amazon面试code题是逃不掉的,所以自我介绍和谈过去的项目都不要耽误太多
的时间,要不后面的code题就没时间了.
三面:hr
四面:要限制某个应用x的heap的内存使用,实现一个x_malloc和x_free |
|
K******g
发帖数: 1870 | 15 一面：可不可以把链表先写到一个数组里，然后再转换成BST？如果需要转换成与原来
一样的BST的话，那还需要建立一个preorder的list。
二面：这题其实就是grid遍历
int isVisited[n][m];
N*M
grid[N][M]
void findWord(int n, int m, string &str)
{
if(n<0 || m<0 || n>N-1 || n>M-1) return;
if(isVisited[n][m] == 1) return;
isVisited[n][m] = 1;
str += grid[n][m];
if(lookupDict(str)) cout << str << endl;
findWord(n-1, m, str);
str.pop_back(); //assume that the string can delete the last char.
findWord(n, m-1, str);
str.pop_back();
findW |
|
K******g
发帖数: 1870 | 16 你的意思是在p指针之前放一个整型的数据表示这个p指针指向的buffer有多大，是吧？
然后p指针的地址不一定是4的倍数，那请问前面那个数据怎么会是整型的呢？malloc怎
么把buffer size写到那个地址里去的呢？
那个填色的那题，如果已经是相同颜色了，就不要再填了吧？
第二题如果没有辅助数据，怎么把BST转换成BST呢。
请指教 |
|
p**********s
发帖数: 115 | 17 2月份在学校网站上投的tripadvisor,电面三轮，然后去boston onsite.住的地方隔壁
的mm或者大妈估计在谈恋爱，打电话直到凌晨3点，弄得我只睡了3个小时。
tripadvisor的工作环境不错。我面了3个人就挂了。感谢其中一个华人shanshan，人很
nice。只记得几道题了：
1 写BST的class
2 DP problem: coins找零
3 实现构造prefix tree
4 如何用1个随机数公平的产生permutation。（实现windows里的用户公平选择5种浏览
器）
youtube4月份有个collage day，学校网站上投简历。电面一轮onsite.总共有20多个学
生参加那天的collage day.4轮面试。问的都是算法基础题。
1 各种sort。
2 找出一个array里所有和为特定值的pair
3 设计算法和数据结构，找出所有视频里最popular的10个。
4 bst里两个node的最小共同祖先
5 给几个数，比大小（形如n^google, n^n, 2^n, n!） |
|
d**e
发帖数: 6098 | 18 ☆─────────────────────────────────────☆
cherishlife (珍爱生命) 于 (Sat Dec 19 01:34:56 2009, 美东) 提到:
第一个面试官是个中国人，女的。
开始想同她套套近乎，也不知道是不是套错了，反正当时感觉她不喜欢我（其实后来回头想想，可能不是她不喜欢我，她就是那样说话的态度，是我感觉不对）。
编程题
given a character string, print the number of occurence of each charcater in
order. ie. if the string is "ceabcw", then you should print something like:
a 1 b 1 c2 e 1 w 1.
she asked the possible data strucutre to approach. I gave array, hashtable,
and BST. she asked me to use BST, and using no recursive. |
|
y*********e
发帖数: 518 | 19
是BST嘛？假设是BST。
6
/ \
4 8
/ \ / \
1 5 7 9
inorder是 1 4 5 6 7 8 9
levelorder是 6 4 8 1 5 7 9
6
/ \
4 8
/ / \
1 7 9
inorder是 1 4 6 7 8 9
levelorder是 6 4 8 1 7 9
注意到，在 levelorder 中， INDEX (parent) < INDEX (node)。
解法思路如下：
1、取 levelorder 的第一个，作为 root。在 inorder 里面，小于 root 的值，是为
left sub tree。在 inorder 里面，大于root 的值，是为 right sub tree。
2、在 levelorder 里面找寻第一个值 n，使得 n < root && INDEX(n) >
INDEX(root) |
|
w*****e
发帖数: 158 | 20 1.when would you use a hash table vs. balance binary tree to represent a
dictionary? Discuss tradeoffs, algorithm performance
2. How would you keep track of the 10 largest elements in an input stream?
3. If the same shared library exists in absolute path /a/path1 and
/b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
runtime?
第一题应该从那些方面考虑呢？ 只知道 hashtable: ~O(n); BST: ~O(logn)
第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
希望大家指正，给些意见。多谢！ |
|
y*********e
发帖数: 518 | 21 在实际应用中 hashtable 的效率接近于 O(1)，当然前提是有个好的hash函
数。比如Java的hashtable实现。
hashtable 的速度远比 BST 要高。但是 hashtable 的 memory overhead
会较大。
还有 hashtable 是无序的，BST是有序的。
第二题用大小为10的max heap就可以了。O(Nlog10)的复杂度。 |
|
j*****g
发帖数: 223 | 22 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 23 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
e**********6
发帖数: 78 | 24 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
此由衷的对海内外所有华夏儿女表示感谢。。。
题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
检查一个bs是否为一个bst。
这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
家有兴趣的话可以讨论一下。
bool is_bst(BTNODE *root, int min, int max){
if(!root)
return true;
if(root->a>max || root->a
... 阅读全帖 |
|
d**e
发帖数: 6098 | 25 ☆─────────────────────────────────────☆
toprunner (长跑者) 于 (Fri Jun 11 21:00:38 2010, 美东) 提到:
公司股票涨了，有几个臭钱，就以为怎么样。把人挑来拣去，。。。 搞得自己招不到
人，还来什么推荐大竞赛。无非是想扩大新人 POOL 进一步左挑右选。
真不觉得问几个 BST DP 就能选到好的程序员啦？ 无非是，事先知道考题类型的，准
备过的，把BST 算法背个烂熟的被选上。
那些写 Code 的活，还不是任何能来北美读书，受 CS Master， PhD 教育，写过几年
Code 的都能做。
真是对 Amazon 很反感！
☆─────────────────────────────────────☆
inspire (Serenity) 于 (Fri Jun 11 21:06:02 2010, 美东) 提到:
行为艺术么？
年
☆─────────────────────────────────────☆
clusive (clusive) 于 (Fri Jun 11 2... 阅读全帖 |
|
x****k
发帖数: 2932 | 26 amazon 第一轮phone interveiw面经，印女
1. the most challenging project.
2. linklist, hash table, bst,
In what case prefer bst over hash table.
3, write a function to search in a rotated array.
4. OOdesign for a deck of poke. |
|
l**********3
发帖数: 161 | 27 刚刚面的，问了很多数据结构，design，OS，和OO的基本概念，面试了1个半多小时。
== Resume ==
1. Describe the projects listed in the resume.
== Data Structures & Complexity ==
2. Lookup in linked list and array (sorted, unsorted)
3. Sorting strategies (comparison-based & non-comparison-based)
4. Lookup, insert, delete in hash table.
5. How to resolve collision (chaining, open addressing)
6. How to support delete with using open addressing
7. What affects collision (hash table size & hash function)
8. What the complexity when using ... 阅读全帖 |
|
n****t
发帖数: 241 | 28 我看到貌似正确的一个解法，加了很多限制条件。。。
面试题之二叉搜索树的中位数 收藏
这个问题不算是很常见的问题，基本上在中文的论坛社区没有看到过，遇见这个是因为
偶尔在http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi 上面注册了账号而看到的，题目如下：
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
* No extra memory.
* Function should be reentrant (No static, global variables allowed.)
* Median for even no of nodes will be the average of 2 middle elements and
for odd no of terms will be middle element only.
* Algorithm should be efficient in terms of comple... 阅读全帖 |
|
g*********s
发帖数: 1782 | 29 Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original description, which is misleading. |
|
n****t
发帖数: 241 | 30 所以我一直没有想明白怎么样是lgn...
Sorry, even if u know the count of descent for each node, how can u achieve
O(lgN) with that info?
In the worst, case the bst is a sorted singly linked list. How can you get
the median of the SLL in O(lgN)?
Unless it's a balanced bst. But the condition is missing from your original
description, which is misleading. |
|
z*s
发帖数: 209 | 31 I mean the former one. given a bunch of numbers and create such a bst (
unbalanced).
My method is to use a regular recursive bst node insertion http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set numOfDescendents of the newly added node to 1 and increment numOfDescendents of the nodes along the insertion path by 1. |
|
a***o
发帖数: 1182 | 32 刚刚结束，
两轮，每轮30分钟
第一个：
没用google doc，先胡扯research project，然后说coding：
给个sorted array， build BST
然后问输入很多字符串，怎么去重复。
第二个：
胡扯另一个project，然后coding：
find next bigger node in BST
然后问，怎么加快google search速度，胡扯clinet端，server端啥的
都很简单，各位good luck! |
|
d******u
发帖数: 397 | 33 Using BST is a nice idea.
However, one question: what is the key for each node of the BST?
If the keys are the line numbers, do we need to change the key values that
are no less than the newly inserted line ?
Then, that would still be linear, right? (even though you don't need to move
the data entries as in the array case).
If you don't use line numbers as the keys of the nodes, search will not be
logN. Right? |
|
g*********s
发帖数: 1782 | 34 sorry, but can u prove this is balanced? i believe this algorithm creates
a bst. but i'm not convinced the created bst is balanced.
u can see the left and right sub-tree can have size difference by 1. if u
do recursion, then is it possible at each level the left and right may
have difference by 1? if so the worst case this difference is accumulated
with an O(lgN) bound... |
|
e*****e
发帖数: 1275 | 35 Given a BST in a language where memory must be handled manually, how do you
completely remove BST from memory? Recursion is not allowed. Was later told
that desired solution had O(N) time and O(1) space. ??????
实在是想不出不要 recursion O(1) 的办法 |
|
l*****a
发帖数: 14598 | 36 you can get the result from PIE
BST give u O(lgn) insertion/lookup but sorted
while
hashtable give u O(1) insertion/lookup but not sorted
if u don't have enough memory and u want an ordered output
u should use BST |
|
h**********d
发帖数: 4313 | 37 bst你怎么保证取出来每次插入都为balanced bst? |
|
a********e
发帖数: 80 | 38 复杂度O(M*N)
这个矩阵就可以看成一个BST，根在右上角,左边一格是左儿子，下边一格是右儿子。左边元素比自己
小的是左子树的节点，下边元素比自己大的是右子树节点。
然后中序遍历BST就可以了。
void InOrder(int x, int y, int low, int high)
{
if ((x>=0) && (x=0) && (y
x][y]>=low))
{
InOrder(x, y-1, low, array[x][y]);
cout<
InOrder(x+1, y, array[x][y], high);
}
} |
|
y**********7
发帖数: 17 | 39 我当时就是沿用bst search的那个方法，但用了2个variables keep tracking最小的差
值，和最近的数。然后每
个iteration里都比较下，如果比当下的那个数更接近的话，就更新一下。当然我的这
方法不是最有效的，因为
bst是有规律的，所以不必每次都比较，但不比较的话有时候需要go back。所以当时选
了个每次都比较的方法，
感觉不会出错，保险起见。 |
|
m****u
发帖数: 3915 | 40 float BST我有个想法
就是遍历tree的时候
不用每次都算差值，遍历float BST，会向左走或者向右走
记住向左走的最后一个节点，记住向右走的最后一个节点
那么要找的数一定在这两个节点之间
算差值，比较这两个节点谁离要找的数最近就可以了 |
|
c*****z
发帖数: 182 | 41 bst那个，是不是recursive一下就搞定了
mindistance search(bst root, value target) {
if (target = root.value) {
return 0;
} else if (target < root.value) {
return min(distance(target-root.value), search(root.left, target));
} else {
return min(distance(target-root.value), search(root.right, target));
}
}
这个是只返回最小距离， 如果还要数的话返回个pair就行了 |
|
s*********3
发帖数: 389 | 42 It seems that it doesn't need to use recursive. Traverse the BST, if the
root value is less than target value, find the minimum value of the right
subtree and compare the difference between the root value and the target value vs. the minimum value of the right subtree and the target value. Similar for left subtree.
//Given a BST, find the number closest to a target number
public Float searchClosestNumber(TreeNode x, float d) {
if (x == null) {
return null;
}
... 阅读全帖 |
|
D*****7
发帖数: 766 | 43 每碰到一个，就去已经找过的部分看看是不是已经存在，时间复杂度很高
如果对时间复杂度有进一步的要求话，就将已经找过的部分构建成一个BST（用Array来
表达BST）。 |
|
b*******8
发帖数: 37364 | 44 从左到右扫描，碰到左边界，表示开始进入这个矩形，碰到右边界，表示扫描出了这个
矩形。任一时刻，同时在BST里的矩形，X轴上一定Overlap，但还要在Y轴上进行判断是
否Overlap。用BST是为了搜索，插入，删除的时间复杂度都是log级别。 |
|
m***g
发帖数: 90 | 45 这个算法里生成的是 bst
12
/\
11 34
/\
22 45
/ \
43 67
/\
56 89
\
98
为啥不是:
12
/\
11 34
\ \
22 45
/ \
43 67
/\
56 89
\
98
bst的生成是先满足右子树么？
public static void main(String args[]) {
BinaryTreeTest b = new BinaryTreeTest();
int data[] = { 12, 11, 34, 45, 67, 89, 56, 43, 22, 98 };
BinaryTreeTest.Bin... 阅读全帖 |
|
y*******e
发帖数: 4 | 46 面试官很nice 一共三道题
why amazon
什么是bst，怎么判断是否是bst， 说了三种方法，inorder，按定义求和利用范围求的
方法
design chess board game
中间coding的时候急于求成，出了个小bug 求bless吧。 |
|
k*p
发帖数: 1526 | 47 LRU still has to use double linked list + hash to implement. BST is used to
find max element. Any new element to LRU or removal of tail element needs in
sertion/deletion to BST in O(h) time. |
|
r*********u
发帖数: 75 | 48 You have two BST, you have to merge them into a single BST, inplace and
linear time. |
|
g**e
发帖数: 6127 | 49 convert bst to single linked list in-place感觉比convert成doubly linked list
还难一些。tree rotation感觉写起来挺麻烦的，不知道有没有简洁的方法？转doubly
linked list写递归很容易。
用链表的排序来建立 BST. |
|
i**********e
发帖数: 1145 | 50 1. No it does not require it to be balanced. But the algorithm you posted
basically is a variation of inserting nodes in a BST. Inserting a node in a
BST takes O(height of tree) time. If the tree is not balanced, the worst
case is O(mn) time. Even if the tree is balanced, it still takes O(m log n)
time (ie, not linear).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
