y**********7
发帖数: 17 | 1 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
足了，准备从了。
第一个电面：
1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
然后问我已知这三个order的结果，能不能construct原本的bst。
3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
order的顺序重新排序，然后返回。比如reorder("banana","na")应该返回"nnaab"。
order里没有出现的字母放在最后面就行了。
第二个电面：
1. 聊了一下我现在做的项目
2. 比较array和linked list的。
3. 两个linked list，如何找到intersect的那个node。
4. 给一个integer array，允许duplicates，而且其中某个未知的integer的
duplicates的个数占了整个array的一大半。如何有效的找出这个integer？
on-site
美丽的亚洲姐姐：
1. design caching
2. 貌似跟random number有关的，记不得了。
白人老大爷：
1. 给个float BST, 写个search(float target)的算法找出离target最近的数。
欧洲帅小伙：
1. design google search suggestions
印度哥们
1. 跟trie相关的算法。
经验：
请大家一定要对自己有信心，工作是一定能找得到的。小女子先后被ms, amazon,
vmware, nvidia, zynga, sig拒过，但从没放弃过。一定要从失败中获得教训，总结经
验，多来版上瞧瞧，胜利就在不远的前方。面试技巧上，我觉得有
两点很重要：第一个是化身为解说帝，见到一个题目的时候，想个几十秒，如果有思路
了，就要开始跟面试的人叨叨，你的算法是怎么样的，要用到神马data structure, 时
间空间复杂度是神马；很多interviewer基本这个时候就会
说，”很好很好，开始code吧！“。如果实在是没有思路，也要跟interviewer叨叨，
确认你题目是否理解对了，能不能套出神马hints。千万不要闷不吭身地三下五除二就
开始写代码，就算你写的又好又快，面试你的人也不一定领情。第二
个是对自己最近做的实习或是项目要准备一套有激情的说辞，on-site的时候几乎每个
interviewer都问了我最近做的项目（我当时重复地快吐了！！！），此时一定要表现
出你对这个项目的极度热爱和你的contribution。我觉得他们都灰
常欣赏对工作有热情和激情的人。
面试资料:
programming interviews exposed，这本书虽然比较简单，但解题思路和方法非常经典
，如果能灵活掌握，50％的算法面试题木有问题。强烈推荐！
careercup 150，这本书题目类型比较全，但答案太简略了，没有过程分析，比较适合
在掌握一定的知识基础上，进行最后冲刺。如果面试准备时间充裕的话，前期不推荐看。
programming pearls，我看的是第一版，这本书真牛！20多年前的书，看着一点都不过
时。尤其是中间有几个章节sorting, searching可以仔细地看看。因为我也没有做后面
的习题，偶尔大概的扫一下，寒假每天泡澡的一个多小时看
看，十几天看就完了。推荐推荐！！
系统地把所有的data structures复习了一遍，网上资料很多。
还看了些topcoder里dp, greedy, binary search的章节。 |
g*********s
发帖数: 1782 | 2 赞面经。很久没看到了。你的难度不低。
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
s*****y
发帖数: 897 | 3 cong
niu
zan
【在 g*********s 的大作中提到】
: 赞面经。很久没看到了。你的难度不低。
|
r****l
发帖数: 28 | 4 Cong!赞分享！
请问这个题有什么tricky的地方需要注意的吗？
1. 给个float BST, 写个search(float target)的算法找出离target最近的数。 |
j*****u
发帖数: 1133 | 5 cong!87的小MM
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
t****o
发帖数: 31 | |
a**********s
发帖数: 588 | 7 wow, congratulations~~~
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
b******n
发帖数: 4509 | 8 cong! and really good advice! the puzzles are not very hard, for interview,
it is really half on preparation half on luck |
y**********7
发帖数: 17 | 9 我当时就是沿用bst search的那个方法，但用了2个variables keep tracking最小的差
值，和最近的数。然后每
个iteration里都比较下，如果比当下的那个数更接近的话，就更新一下。当然我的这
方法不是最有效的，因为
bst是有规律的，所以不必每次都比较，但不比较的话有时候需要go back。所以当时选
了个每次都比较的方法，
感觉不会出错，保险起见。
【在 r****l 的大作中提到】
: Cong!赞分享！
: 请问这个题有什么tricky的地方需要注意的吗？
: 1. 给个float BST, 写个search(float target)的算法找出离target最近的数。
|
y******5
发帖数: 43 | 10 I think the only thing to take care is equation between two float numbers.
But in this problem we even don't need to care about it.
【在 r****l 的大作中提到】
: Cong!赞分享！
: 请问这个题有什么tricky的地方需要注意的吗？
: 1. 给个float BST, 写个search(float target)的算法找出离target最近的数。
|
|
|
y**********7
发帖数: 17 | 11 嗯，真的不难。但也要调整好心态，好好准备。机会总是给有准备的人！
,
【在 b******n 的大作中提到】
: cong! and really good advice! the puzzles are not very hard, for interview,
: it is really half on preparation half on luck
|
y******5
发帖数: 43 | 12 Thank you for your post. I have one question:
1. design google search suggestions
Design search engine or how to make suggestions more precisely? |
y******5
发帖数: 43 | 13 My thoughts:
Inverted list + Page ranking + B+ tree
We can also use user's search history if available.
【在 y******5 的大作中提到】
: Thank you for your post. I have one question:
: 1. design google search suggestions
: Design search engine or how to make suggestions more precisely?
|
s********9
发帖数: 233 | |
m****i
发帖数: 650 | 15 Thanks for your sharing
Congrats !!! |
d******2
发帖数: 456 | |
m****i
发帖数: 650 | |
j********x
发帖数: 2330 | 18 Maybe we should set a rule: post pp if got offer?
Congs... |
n********p
发帖数: 708 | |
c****m
发帖数: 179 | |
|
|
w*********g
发帖数: 1055 | |
y**********7
发帖数: 17 | 22 一个不错的金融公司，总部在费城～
【在 m****i 的大作中提到】
: sig 啥公司？
|
c****m
发帖数: 179 | 23 有个疑问，需要这么多的比较吗？
就按照BST一直搜，直到<=target或者>=target就停下，比较一下target和当前node的
parent的
差以及当前node和target的差不就可以判定最接近的了？
有反例说明要go back吗？谢谢。
【在 y**********7 的大作中提到】
: 我当时就是沿用bst search的那个方法，但用了2个variables keep tracking最小的差
: 值，和最近的数。然后每
: 个iteration里都比较下，如果比当下的那个数更接近的话，就更新一下。当然我的这
: 方法不是最有效的，因为
: bst是有规律的，所以不必每次都比较，但不比较的话有时候需要go back。所以当时选
: 了个每次都比较的方法，
: 感觉不会出错，保险起见。
|
s*****d
发帖数: 68 | 24 赞解说帝！深有同感啊，一定要保持嘴里时刻在向外蹦单词！ |
i**d
发帖数: 357 | |
g*******7
发帖数: 32 | |
s*****y
发帖数: 897 | 27 hi, which algorithm and language did you use to implenment the caching?
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
g**u
发帖数: 583 | |
m******n
发帖数: 1691 | 29 赞！
女生在IT业好像比男生受欢迎很多啊。
有没有！！！！！！ 有没有！！！！！
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
r**u
发帖数: 130 | 30 问个问题，等Offer的时候你联系过recruiter吗？recruiter什么反应？
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
|
|
y**********7
发帖数: 17 | 31 哈哈，我觉得其实有耶，物以稀为贵嘛。
我同学都跟我说，你是女生，肯定没问题。。果然拿到offer了。汗！！
【在 m******n 的大作中提到】
: 赞！
: 女生在IT业好像比男生受欢迎很多啊。
: 有没有！！！！！！ 有没有！！！！！
|
y**********7
发帖数: 17 | 32 不需要code, 只是聊一下想法，用神马data structure之类的。其实我完全不会这道题，
interviewer给了很多例子和提示。
【在 s*****y 的大作中提到】
: hi, which algorithm and language did you use to implenment the caching?
|
Y***e
发帖数: 1030 | 33 楼主肯定是stanford, mit大牛校的
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
s*****y
发帖数: 897 | 34 Thanks very much.
Did they ask you how to improve the cache performance from hardware and
software perspective?
题，
【在 y**********7 的大作中提到】
: 不需要code, 只是聊一下想法，用神马data structure之类的。其实我完全不会这道题，
: interviewer给了很多例子和提示。
|
m****u
发帖数: 3915 | 35 我怎么觉得用前缀树
就跟查字典的suggestion差不多
【在 y******5 的大作中提到】
: My thoughts:
: Inverted list + Page ranking + B+ tree
: We can also use user's search history if available.
|
y**********7
发帖数: 17 | 36 不是的。。。。。TOP20的CS program吧。主要是我们学校地域不太好，很偏僻。
【在 Y***e 的大作中提到】
: 楼主肯定是stanford, mit大牛校的
|
y**********7
发帖数: 17 | 37 面试我的MM说，如果要存的cache很大怎么办，我就说可以存在好几个机器上。她问我
怎么split和
get，我说用/和%。她看起挺满意的。硬件没提，完全不懂硬件。。。。。
【在 s*****y 的大作中提到】
: Thanks very much.
: Did they ask you how to improve the cache performance from hardware and
: software perspective?
:
: 题，
|
y*******g
发帖数: 6599 | 38 还是比较麻烦得，google suggestion不是给最接近得，而是给最popular得。
match prefix之后再按照rank和 sort一下吧。他说得哪些大概是用来觉得rank得
【在 m****u 的大作中提到】
: 我怎么觉得用前缀树
: 就跟查字典的suggestion差不多
|
y*******g
发帖数: 6599 | 39 preorder postorder什么recursive就可以了吗？
重构要code么？感觉时间不是很够啊
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
s*****y
发帖数: 897 | 40 Sounds like UIUC or Purdue?
【在 y**********7 的大作中提到】
: 不是的。。。。。TOP20的CS program吧。主要是我们学校地域不太好，很偏僻。
|
|
|
y**********7
发帖数: 17 | 41 恩恩，握爪！我当时也是用的prefix tree，结果肯定是要rank的，我就name了一些
rank的方法，
那人还挺满意的，还好没让我具体解释和code。
【在 y*******g 的大作中提到】
: 还是比较麻烦得，google suggestion不是给最接近得，而是给最popular得。
: match prefix之后再按照rank和 sort一下吧。他说得哪些大概是用来觉得rank得
|
y**********7
发帖数: 17 | 42 不是code，就是直接写答案。BST的图已经有了。
【在 y*******g 的大作中提到】
: preorder postorder什么recursive就可以了吗？
: 重构要code么？感觉时间不是很够啊
|
y**********7
发帖数: 17 | 43 不是。。。请不要人肉我。。。
【在 s*****y 的大作中提到】
: Sounds like UIUC or Purdue?
|
s*****y
发帖数: 897 | |
m****u
发帖数: 3915 | 45 float BST我有个想法
就是遍历tree的时候
不用每次都算差值，遍历float BST，会向左走或者向右走
记住向左走的最后一个节点，记住向右走的最后一个节点
那么要找的数一定在这两个节点之间
算差值，比较这两个节点谁离要找的数最近就可以了 |
i**********e
发帖数: 1145 | 46 应该是直接看图然后写出preorder，postorder and inorder的打印顺序。
如果要写出这三个非递归的代码有些残忍。
postorder 非递归不容易写(it is non-trivial)。
yingying1987:
非常谢谢你的分享，这些信息对我们都非常非常有用！在此感激不尽！恭喜你，you
deserve it!
狂赞 LZ 不放弃的态度：
小女子先后被ms, amazon,
vmware, nvidia, zynga, sig拒过，但从没放弃过。一定要从失败中获得教训，总结经
验，多来版上瞧瞧，胜利就在不远的前方。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 y*******g 的大作中提到】
: preorder postorder什么recursive就可以了吗？
: 重构要code么？感觉时间不是很够啊
|
y**********7
发帖数: 17 | 47 神ID！我也常看你的blog，收获很多，大大牛！
【在 i**********e 的大作中提到】
: 应该是直接看图然后写出preorder，postorder and inorder的打印顺序。
: 如果要写出这三个非递归的代码有些残忍。
: postorder 非递归不容易写(it is non-trivial)。
: yingying1987:
: 非常谢谢你的分享，这些信息对我们都非常非常有用！在此感激不尽！恭喜你，you
: deserve it!
: 狂赞 LZ 不放弃的态度：
: 小女子先后被ms, amazon,
: vmware, nvidia, zynga, sig拒过，但从没放弃过。一定要从失败中获得教训，总结经
: 验，多来版上瞧瞧，胜利就在不远的前方。
|
h******3
发帖数: 351 | |
r********g
发帖数: 1351 | 49 赞！收藏一下~
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
n*****o
发帖数: 1778 | |
|
|
s*******3
发帖数: 134 | |
m**k
发帖数: 4039 | 52 这150 stock是stock还是option？
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
d*******4
发帖数: 43 | |
m****4
发帖数: 827 | 54
150 stock? vesting period多久啊？！每年都给150还是一次性？
这个差不多也值10万刀了。
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
c*******o
发帖数: 1357 | 55 一般给的是stock option不是stock吧～～
【在 m****4 的大作中提到】
:
: 150 stock? vesting period多久啊？！每年都给150还是一次性？
: 这个差不多也值10万刀了。
|
H**d
发帖数: 152 | |
h*********7
发帖数: 811 | 57 G家应该是stock, RSU. 估计是4年.
另外恭喜小mm, 这么年轻拿到这样的offer，很不错的。
【在 c*******o 的大作中提到】
: 一般给的是stock option不是stock吧～～
|
k*****7
发帖数: 72 | 58 恭喜啦！
顺便问一下，你面试时写程序有没有bug然后被提醒出来改掉，还是写一遍就OK的？看
你的题目也不easy，一遍就OK很NB |
m****4
发帖数: 827 | 59
现在流行的都是直接给stock的，amazon也是，估值容易一些
【在 c*******o 的大作中提到】
: 一般给的是stock option不是stock吧～～
|
k*****7
发帖数: 72 | 60 恭喜啦！
顺便问一下，你面试时写程序有没有bug然后被提醒出来改掉，还是写一遍就OK的？看
你的题目也不easy，一遍就OK很NB |
|
|
z*s
发帖数: 209 | |
p****f
发帖数: 251 | 62 恭喜，沾喜气。。。
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
b***u
发帖数: 12010 | 63 wk钱真多。
早知投google了我那回
【在 y**********7 的大作中提到】
: 终于拿到offer，从上个月16号on-site完到今天，一共等了1个多月。今天接到
: recruiter的电话后兴奋地在办公室里蹦了好几下，我旁边的哥们都震惊了。哈哈。
: 先报下背景，fresh cs master, 无牛实习，在学校一直跟着一个还不错的项目。
: google给了我10.5w base+15% bonus+150 stock，不知道是个什么水平，但我已经很满
: 足了，准备从了。
: 第一个电面：
: 1. 比较hashtable和BST，神马时候用hashtable,神马时候用BST。各自的优势与缺点。
: 2. 那人在doc里粘了个BST的图，然后让我分别写下preorder, postorder和inorder。
: 然后问我已知这三个order的结果，能不能construct原本的bst。
: 3. 填这样一个函数 String reorder(String s, String order), 也就是要把s根据
|
v***n
发帖数: 562 | |
c*****z
发帖数: 182 | 65 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就行了 |
j********x
发帖数: 2330 | 66 Maybe we should set a rule: post pp if got offer?
Congs... |
k***o
发帖数: 125 | |
h**k
发帖数: 3368 | 68 这个要求在给定的数组中找到相邻的两个数形成的一个区间，要求target在这个区间里
，然后从构成区间的两个数中选择一
个离target最近的。
普通BST只给出构成区间的一个数，需要记录中间结果来找到另一个数。
【在 r****l 的大作中提到】
: Cong!赞分享！
: 请问这个题有什么tricky的地方需要注意的吗？
: 1. 给个float BST, 写个search(float target)的算法找出离target最近的数。
|
s*********3
发帖数: 389 | 69 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;
}
TreeNode subTree;
if (d < x.data) {
subTree = maximum(x.left);
return (x.data - d) < Math.abs(subTree.data - d) ? x.data : subTree.data;
}
else {
subTree = minimum(x.right);
return (d - x.data) < Math.abs(subTree.data - d) ? x.data : subTree.data;
}
}
public TreeNode maximum(TreeNode x) {
while (x.right != null) {
x = x.right;
}
return x;
}
public TreeNode minimum(TreeNode x) {
while (x.left != null) {
x = x.left;
}
return x;
}
【在 c*****z 的大作中提到】
: 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));
: }
: }
|
c*****z
发帖数: 182 | 70 错的，自己找个例子想想
value vs. the minimum value of the right subtree and the target value.
Similar for left subtree.
【在 s*********3 的大作中提到】
: 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;
: }
:
: TreeNode subTree;
|
|
|
W**********r
发帖数: 8927 | |
