s******n
发帖数: 3946 | 1 bool isAVLTree(Node* n, int* height)
{
if (n==NULL) {
*height = 0;
return true;
}
int left_height, right_height;
if (isAVLTree(n->left, &left_height) && isAVLTree(n->right, &right_height) && abs(left_height-right_height)<=1) {
*height = max(left_height, right_height)+1;
return true;
} else {
return false;
}
} |
|
w****x
发帖数: 2483 | 2 手机号码那个肯定是AVL Tree把， 又能做到搜索平衡又能显示范围区间。 |
|
c****m
发帖数: 179 | 3 其实排好序的linkedlist就成了（Node是name 和number），他的意思是scroll顺序显
示所有联系人的时候tree traversal都不要做了。
BST应该不是理想的答案，因为tree可能不平衡。对，其实可以用任意一个扩展avl，
redblack tree , splay tree都成。 |
|
a***y
发帖数: 547 | 4 用第二种办法吧
avl 树能保证两边节点个数一样多么
balanced |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 6 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
P**********c
发帖数: 3417 | 7 self-balancing tree AVL的好写一点吧。本科数据结构学的。
OO |
|
g*********e
发帖数: 14401 | 8 我在股沟intern电面的时候被要求写一种自平衡二叉树，直接虚了
要是onsite的话，写AVL tree rotation倒也还算合理 红黑树一般人吃不消吧 |
|
l***i
发帖数: 1309 | 9 multiway merge is not hard, if you know AVL tree or treap, you could get
away with 2-3-4 tree or Red-black tree as they do similar things. |
|
G**********s
发帖数: 70 | 10 i got your point, thanks!
BTW,for insertion/deletion, red-black tree is fastest, faster than AVL.. |
|
h********w
发帖数: 221 | 11 靠他AVL的insertion 和deletion, 给出时间复杂度
或是DFS and BFS |
|
g*********e
发帖数: 14401 | 12
骗你干吗 而且是intern电面。不过写AVL tree应该也行 |
|
a******9
发帖数: 12 | 13 两个美国哥们,都是同一个做payment的组.
1面:
1. OOP question. Class->Object->Interface 等等
2. 一个recordmanagement系统, 只用保持最新的10个record, 怎么实现? 写代码念给他听
3. 如果同时要保持这10个record的min和max, 怎么实现? 写代码念给他听
2面:
1. 一个树,多个孩子,深度优先遍历每个孩子. 他提供了一个interface, Node有一个getChildren()返回一个collection
2. Int转罗马数字
3. 怎么估计cube里很多penny堆起来的高度 跟帝国大厦比哪个更高? (没怎么听清楚,我说我会用鸡蛋做,最后时间快到了,不了了之了)
问题都挺简单,两个美国哥们很和善,思路很清晰,不会从一个方向的问题跳到另外一个方向. 没有问OOD.
感谢前几天的一个面经贴,所以才有机会今天面试前准备了罗马数字题.
之前有些害怕会碰到偏题怪题,因为昨天在别的论坛上看到有intern 面经报告说问了 AVL树 的impleme... 阅读全帖 |
|
w****3
发帖数: 232 | 14 今天早上收到的邮件，不过说给我安排的不是面我的那组（这是怎么回事？）是Engineering Systems Dev team。 有谁知道这是干啥的不？怎么感觉是干杂活的啊。
------------------------------------------------------------------------------------------
周五的面试，今天发邮件给hr和大boss，都没有回信。下面的是周六写的，不过那时候
刚刚注册，所以现在才能发上来。有懂的帮我看看还有没有希望。
面试11:30 开始，先是见到一个hr，简单的询问了一些问题。因为我现在有工作，所以
他问了问公司的事情。
第一轮技术面试12:30 开始，跟一个senior的印度女士的lunch interview， 1个半小
时。吃饭的时候聊了聊两个公司的产品，构架，询问毕业之后在公司里的工作。回到办
公室，开始问算法，写code。题目很简单，就是一颗BT，怎么找两个点，他们的和是给
定的一个数。BST如何做，只找一对和找出所有的pair的code怎么写。写code的时候有
点失误，而且因为字迹太潦草。。... 阅读全帖 |
|
p*********m
发帖数: 619 | 15 面试MS有5轮面试的话，见到了manager，通常希望都是很大的
如果没希望的，3，4轮后就结束了。当然表现最好的可能当场就给offer了。
但是如果见到了manager，一般来说都很有希望。
提前恭喜一下
周五的面试，今天发邮件给hr和大boss，都没有回信。下面的是周六写的，不过那时候
刚刚注册，所以现在才能发上来。有懂的帮我看看还有没有希望。
面试11:30 开始，先是见到一个hr，简单的询问了一些问题。因为我现在有工作，所以
他问了问公司的事情。
第一轮技术面试12:30 开始，跟一个senior的印度女士的lunch interview， 1个半小
时。吃饭的时候聊了聊两个公司的产品，构架，询问毕业之后在公司里的工作。回到办
公室，开始问算法，写code。题目很简单，就是一颗BT，怎么找两个点，他们的和是给
定的一个数。BST如何做，只找一对和找出所有的pair的code怎么写。写code的时候有
点失误，而且因为字迹太潦草。。。有几句code解释来好些时间。不过总的来说我刚觉
和她聊得还不错。因为这轮过后，我就被额外加了两轮面试（原schedule只有三轮，据
说是表现好... 阅读全帖 |
|
N*****8
发帖数: 253 | 16 来自主题: JobHunting版 - 请问两道题 从右往左扫数组，然后建AVL/RB tree(普通的BST不能保证logn时间)，右边的分支需要
把root的个数加上然后加一，左边的不需要。
然后再扫数组，从左往右，每次node都减一。 |
|
N*****8
发帖数: 253 | 17 来自主题: JobHunting版 - 请问两道题 可能更多的是讲思路吧，顺便把AVL/RB里面的关键算法也考了，突然觉得这个题一举两
得啊。 |
|
w****x
发帖数: 2483 | 18 我觉得因该想想那家伙是不是存心不让楼主过的, 我知道A家电话一面有要实现AVL
Tree的, 然后把代码读出来... |
|
f*****o
发帖数: 95 | 19 recruiter 会给一个大概要复习的范围，诸如要掌握一两个nlogn 的sorting(merge &
qsort)
binary tree traversal, red-black or avl-tree, graph msp, np etc, 电面咱的时
候考官花大概十分钟介绍他的project，然后大概十来分钟跟咱聊咱以前和现在的项目
，最后让咱logon google doc, 用C十十写螺旋输出一个方矩阵的毎个值，从没见过，
一下傻眼，一时也想不出好的方法，就用最傻的for loop 嵌套plus if-then-else, 坑
爹的iPad+google doc+disturbing spell correction使得C十十coding very
difficult, 折腾了一阵，考官说很close 了，时间也差不多了，跟考官说tree会不会
是好方法，考官说maybe |
|
b*********h
发帖数: 103 | 20 平衡树有很多种，性质也不同
CareerCup 上说的是 AVL
2 楼想说的可能是 Red-Black
感觉如果问这个问题 可以说些公有的性质和思想 如果直接默认 interviewers 说的是
什么树，并且说它的性质可能不是他们想要的。或者提问后谈一种自己熟悉的 |
|
x******i
发帖数: 172 | 21 Given an AVL tree (using pseudocode) how to support the following queries:
RangeMin (k1, k2): consider the field data stored in each node to be an
integer. Find the key with minimum data values among all the keys which are
between k1 and k2 in O(log n) times. (Hint: Consider storing an additional
field in the Node structure and show how can this field be maintained during
updates).
Thank you very much. |
|
W*********y
发帖数: 481 | 22 不是说用到rb tree的地方，用avl tree代替都更balance更好吗？
刚学完clrs，刚开始做题，说错了请指教 |
|
l*****a
发帖数: 559 | 23 复习data structure时，发现插入后做rebalance需要height。网上能找到的getHeight
（）函数的时间复杂度是O（n）的。插入不可能做到O（lgn）。
public int getHeight ()
{
if (this.leftChild == null && this.rightChild == null)
{
return 0;
}
else
{
int leftH = 0;
int rightH = 0;
if (this.leftChild != null)
{
leftH++;
leftH += this.getLeftChild().getHeight();
}
if (this.rightChild != null)
... 阅读全帖 |
|
|
e*****r
发帖数: 93 | 25 getHeight复杂度是O(lgN)还有可以插入的时候就顺便更新了 |
|
O******i
发帖数: 269 | 26 二爷的意思是用平衡的二叉排序树，比如AVL或者红黑，然后每个节点是一个线段(可以
用两个端点表示)么？ |
|
|
B********t
发帖数: 147 | 28 小冷骑士 多谢建议 我也刚学c++不久
c++里有set和map set是avl树实现的 map是红黑树实现的 为什么这里要用set而不
是map呢？
如果用set就是这样
bool myfunc(string s1, string s2)
{
return (s1.size() > s2.size());
}
bool findLongestWord_helper(string &s, set &hs)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hs.find(sub_f) != hs.end())
{
if(i == s.size())
return true;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hs))
return true;
}
}
return false;
}
string findLongestWord(vector &vs)
{
string ... 阅读全帖 |
|
A**u
发帖数: 2458 | 29 Industry experience with C++ and BOOST
Proficient in template and preprocessor metaprogramming techniques.
Understanding of modern CPU cache hierarchies and their impact on software
performance.
Software profiling and optimization experience
Test case and unit test development experience
Knowledge of advanced data structures like B-trees, binomial and fibonacci
heaps, AVL/Red Black trees, Splay Trees, Skip Lists, tries etc.
Able to recognize and code dynamic programming solutions, good knowledge... 阅读全帖 |
|
x***y
发帖数: 633 | 30 来自主题: JobHunting版 - RF 面经 Congradulations!
2. For the tracer problem, does that require coding? The idea should be
simple. Sort by the start the time first, and scan them in the reverse order
while inserting the value into a sorted strucutre. (But what structure to
use to guarantee the logn insertion time, red-black tree, avl tree (a little
tricky to code)
5. One Observation is that if number A is poped out, and then later number B
is poped out, if A>B, then all the values between A and B that are still in
the queue shou... 阅读全帖 |
|
x***y
发帖数: 633 | 31 来自主题: JobHunting版 - RF 面经 Congradulations!
2. For the tracer problem, does that require coding? The idea should be
simple. Sort by the start the time first, and scan them in the reverse order
while inserting the value into a sorted strucutre. (But what structure to
use to guarantee the logn insertion time, red-black tree, avl tree (a little
tricky to code)
5. One Observation is that if number A is poped out, and then later number B
is poped out, if A>B, then all the values between A and B that are still in
the queue shou... 阅读全帖 |
|
g*******s
发帖数: 2963 | 32 Black-Red tree 或者 AVL tree？
我在一个recruiter发给我的准备建议里看到的，如果真让写一个完整的实现（至少包
括build，search， insert， remove， balance）这得要多久啊？ |
|
g*********e
发帖数: 14401 | 33 avl tree
red black tree |
|
s*********t
发帖数: 52 | 34 终于看懂了，这个算法好，不需要维护AVL树，C++好实现 |
|
M*****8
发帖数: 17722 | 35 【 以下文字转载自 Military 讨论区 】
发信人: MB80528 (肥猫(Contrarian)[食MM而肥]), 信区: Military
标 题: Re: 2013年7月9日最新的1688个看跌的股票。
发信站: BBS 未名空间站 (Tue Jul 9 22:18:23 2013, 美东)
2013年7月9日最新的1688个看跌的股票。
多数到顶。墙街已深入插管，吸血在即。
排列依次为，号码，股票符号，收市价。
#0001, A , 44.6000
#0002, AA , 7.9010
#0003, AAGIY , 17.1600
#0004, AAMRQ , 4.7300
#0005, AAN , 28.9700
#0006, AAON , 24.7400
#0007, AAP , 83.2000
#0008, AAUKY , 9.5300
#0009, ABAX , 50.2800
#0010, AB... 阅读全帖 |
|
s********r
发帖数: 403 | 36 这个网页说的和讨论进程所占内存是否 free 的问题，并没有关系 。
Linux 进程内核态数据结构 task_struct 中的 struct mm_struct *mm 负责与进程所
使用的内存挂钩。
mm_struct 中的 vm_area_struct 既组成一个 link list,又是个avl tree, 便于高效
内存管理。
btw, 这个网站:
http://www.linuxatemyram.com/
linuxatemyram.com 谁想出来的，是微软的人干的吗？哈哈哈哈 |
|
H**M
发帖数: 128 | 37 我遇到的三哥还成，有一个Qualcomm的三姐实在恐怖：口音重的每句话我都要问4、5遍
才能大概猜到是什么意思。她开始还算耐心，但后来就不行了。我记得她问我AVL和红
黑树。 |
|
H**M
发帖数: 128 | 38 我遇到的三哥还成，有一个Qualcomm的三姐实在恐怖：口音重的每句话我都要问4、5遍
才能大概猜到是什么意思。她开始还算耐心，但后来就不行了。我记得她问我AVL和红
黑树。 |
|
m****i
发帖数: 15 | 39 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
m****i
发帖数: 15 | 40 找工作期间在本版潜水两个月，收益良多，发一下最近面经和经验作为回馈。
本人背景：美国不错学校电子PHD即将毕业，专业是EDA做电路设计算法优化。因为EDA
已经是一个很稳定的工业，没什么太大的前景，随想转到前沿的tech公司。本专业只投
了一家现在最大的公司，拿到offer。别的投了Google, Facebook, Rocket fuel,
Twitter, Linkedin, Yahoo, Amazon, Box, Oracle. 除了box别的都找人refer了， 在
此感谢板上大哥们的热情帮忙. 除了GFR别的都没理我，可能背景差太大了。
因为之前是学算法的，mit算法书以前就看过两遍，基础还可以，前期8月份刷了遍
leetcode。然后9月初投出简历。两个星期刷Career cup 150， 最后面试期间一直查缺
补漏。到现在尘埃落定大概两个月。 最后GFR全挂，总结下惨痛经历：
1. Facebook电面
面试官做distributed cache infrastructure的，先问我最难的project，没怎么好好
准备过behavior，胡乱说了一通。但是因为做的是电... 阅读全帖 |
|
s********u
发帖数: 1109 | 41 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只有两端的时候，会比较有用... 阅读全帖 |
|
s********u
发帖数: 1109 | 42 是个国人大哥，人很nice，不过下午很冷，穿了衣服还哆嗦。而且中间collabedit抽风
了几次，然后有些写的就没了，谁知道什么问题么？感觉很奇怪啊，就算断网也不该这
样吧。不过他说会给足时间。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
分享题目和答案：https://docs.google.com/document/d/
1fXfv0GDKc6Uu03ZUU7iac9TcEqpv2YePDE9IAzwhPGo/edit?usp=sharing
这个我记得就是用BST做的。
有一个bug，就是插入的时候给空指针 n = new Node(c),这么做了，被指出了，还是基
础不扎实啊，可能以前都是链表或者用递归做的，就从来没发现这个问题。应该说明下
还可以用递归做的。
中间讨论了一下维护min和max变量是否必要，我说主要是在val超出范围的时候直接判
断，他说那其实interval中间也有空当。我就说那就只... 阅读全帖 |
|
w*******e
发帖数: 395 | 43 设计一个支持concurrency的BST，该BST是类似于AVL和RBT的balanced，也就是说有些
操作会rotation。
请问谁有大概的思路？ |
|
m*******n
发帖数: 103 | 44 critical section + AVL tree rotation. |
|
|
|
y***n
发帖数: 1594 | 47 就想问问大家。我的基本知识不好。都是想把Tree搞得balance,很多书都讲 Red Back
Tree，不知道为什么，我觉得挺难的。 |
|
|
|
r****r
发帖数: 54 | 50 我觉得Left Leaning Red Black Tree特别简单，大概实现起来就100行左右Java.推荐
看一下。 |
|
