A家面经求Offer - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

A家面经求Offer

A家面经求Offer# JobHunting - 待字闺中

r*k2013-02-04 08:02

1 楼

面的SDE intern，题目比较简单，但是第二题没答好，希望能拿到offer
1号：
谈谈经历
讨论了一下hashtable的特性，collision怎么办，复杂度如何
hashset和treeset的利弊
然后是题目： BST的第二大元素
2号：
（感觉面试官没怎么好好准备）
OOP题目
一个company，有boss，vp,dir,manager,employee，让设计类
boss下面有2个vp，vp下面有3个dir。然后又让改成节约空间的，再让改成节约时间的
（其实就是想让我用tree实现，无奈OOP太不熟练了，没想到）

a*o2013-02-04 08:02

2 楼

这俩是背靠背吗？

【在 r******k 的大作中提到】

: 面的SDE intern，题目比较简单，但是第二题没答好，希望能拿到offer
: 1号：
: 谈谈经历
: 讨论了一下hashtable的特性，collision怎么办，复杂度如何
: hashset和treeset的利弊
: 然后是题目： BST的第二大元素
: 2号：
: （感觉面试官没怎么好好准备）
: OOP题目
: 一个company，有boss，vp,dir,manager,employee，让设计类

c*t2013-02-04 08:02

3 楼

然后是题目： BST的第二大元素
应该是从右子树开始inorder travesal的第二个吧。要求必须iteration吗？

【在 r******k 的大作中提到】

l*b2013-02-04 08:02

4 楼

找到最大然后call一下in order previous?

【在 c********t 的大作中提到】

: 然后是题目： BST的第二大元素
: 应该是从右子树开始inorder travesal的第二个吧。要求必须iteration吗？

r*k2013-02-04 08:02

5 楼

没要求，虽然我当时是用iteration

【在 c********t 的大作中提到】

: 然后是题目： BST的第二大元素
: 应该是从右子树开始inorder travesal的第二个吧。要求必须iteration吗？

f*72013-02-04 08:02

6 楼

Bless

p*22013-02-04 08:02

7 楼

就是最右叶子的父亲吧？如果没有右子树，就是左子树的最右叶子。

【在 c********t 的大作中提到】

: 然后是题目： BST的第二大元素
: 应该是从右子树开始inorder travesal的第二个吧。要求必须iteration吗？

e*e2013-02-04 08:02

8 楼

bless! recursion is a simple solution based on coldknight's suggestion. It's
the reverse inorder.
first right sub-tree
then itself
last left sub-tree.

p*22013-02-04 08:02

9 楼

's
没这么麻烦吧？

【在 e****e 的大作中提到】

: bless! recursion is a simple solution based on coldknight's suggestion. It's
: the reverse inorder.
: first right sub-tree
: then itself
: last left sub-tree.

d*x2013-02-04 08:02

10 楼

1
\
3
/
2

【在 p*****2 的大作中提到】

:
: 's
: 没这么麻烦吧？

p*22013-02-04 08:02

11 楼

错了呗。
1
\
2
/
3
这个是BST吗？

d*x2013-02-04 08:02

12 楼

我改了
想的是上面那个

【在 p*****2 的大作中提到】

: 错了呗。
: 1
: \
: 2
: /
: 3
: 这个是BST吗？

p*22013-02-04 08:02

13 楼

确实呀。我想一下。

【在 d**********x 的大作中提到】

: 我改了
: 想的是上面那个

e*e2013-02-04 08:02

14 楼

recursion不麻烦。几行代码而已.
int count = 0;
Node found;
public void secondLargest(Node root) {
if ( root == null )
return;
secondLargest( root.right );
count++;
if ( count == 2 ) {
found = root;
return;
}
secondLargest( root.left );
}

【在 p*****2 的大作中提到】

:
: 确实呀。我想一下。

p*22013-02-04 08:02

15 楼

主要是面试的时候很可能不让用recursion

【在 e****e 的大作中提到】

: recursion不麻烦。几行代码而已.
: int count = 0;
: Node found;
: public void secondLargest(Node root) {
: if ( root == null )
: return;
: secondLargest( root.right );
: count++;
: if ( count == 2 ) {
: found = root;

d*x2013-02-04 08:02

16 楼

你的方向应该是对的
只是情况没考虑周全。。。

【在 p*****2 的大作中提到】

:
: 主要是面试的时候很可能不让用recursion

a*o2013-02-04 08:02

17 楼

最右叶子,如果有左子树,那就是左子树的最右叶子
否则就是父亲,如果没有父亲,就是左子树的最右叶子
一共三种情况

【在 p*****2 的大作中提到】

:
: 主要是面试的时候很可能不让用recursion

c*t2013-02-04 08:02

18 楼

那就用stack啊

【在 p*****2 的大作中提到】

:
: 主要是面试的时候很可能不让用recursion

d*x2013-02-04 08:02

19 楼

1
\
3
/
2
\
2.5

【在 a***o 的大作中提到】

: 最右叶子,如果有左子树,那就是左子树的最右叶子
: 否则就是父亲,如果没有父亲,就是左子树的最右叶子
: 一共三种情况

a*o2013-02-04 08:02

20 楼

你这个不是BST吧
3的左子树都要<3的

【在 d**********x 的大作中提到】

: 1
: \
: 3
: /
: 2
: \
: 2.5

d*x2013-02-04 08:02

21 楼

sorry
我总是想到那个结构。。然后数字写错，你看我改的

【在 a***o 的大作中提到】

: 你这个不是BST吧
: 3的左子树都要<3的

p*22013-02-04 08:02

22 楼

def secondLargest(root:TreeNode):TreeNode={
if(root==null || root.left==null && root.right==null) return null
var node=root
while(node.right!=null && node.right.right!=null) node=node.right
if(node.right==null || node.right.left!=null){
node=if(node.right==null) node.left else node.right.left
while(node.right!=null) node=node.right
}
node
}
这个行吗？还没好好过test case

【在 d**********x 的大作中提到】

: 你的方向应该是对的
: 只是情况没考虑周全。。。

a*o2013-02-04 08:02

23 楼

3kx,我也改了一下,改成左子树的最有叶子

【在 d**********x 的大作中提到】

: sorry
: 我总是想到那个结构。。然后数字写错，你看我改的

p*22013-02-04 08:02

24 楼

这题应该没那么麻烦。

【在 c********t 的大作中提到】

: 那就用stack啊

d*x2013-02-04 08:02

25 楼

看这个
http://bbs.sjtu.edu.cn/bbscon,board,Algorithm,file,M.1041171619
其中那个in-order的前驱

【在 p*****2 的大作中提到】

:
: 这题应该没那么麻烦。

p*22013-02-04 08:02

26 楼

我的思路跟你是一样的。有什么问题吗？

【在 a***o 的大作中提到】

: 3kx,我也改了一下,改成左子树的最有叶子

d*x2013-02-04 08:02

27 楼

那就应该没问题了

【在 p*****2 的大作中提到】

:
: 我的思路跟你是一样的。有什么问题吗？

c*t2013-02-04 08:02

28 楼

如果node没有parent 指针,前驱怎么找？我看还要遍历才行。

【在 d**********x 的大作中提到】

: 看这个
: http://bbs.sjtu.edu.cn/bbscon,board,Algorithm,file,M.1041171619
: 其中那个in-order的前驱

d*x2013-02-04 08:02

29 楼

这个特殊问题里不需要，只要记录两个节点，轮换着来就行了
因为这个问题里前驱无非是最右leaf的左子树的最大节点，或者是它的parent。

【在 c********t 的大作中提到】

: 如果node没有parent 指针,前驱怎么找？我看还要遍历才行。

p*22013-02-04 08:02

30 楼

看看我的code有没有什么问题。

【在 c********t 的大作中提到】

: 如果node没有parent 指针,前驱怎么找？我看还要遍历才行。

c*t2013-02-04 08:02

31 楼

明白了，没有问题。
多谢devil和二爷！

【在 p*****2 的大作中提到】

:
: 看看我的code有没有什么问题。

p*22013-02-04 08:02

32 楼

算法稍微改进了一下，放到博客了
http://blog.sina.com.cn/s/blog_b9285de20101icm1.html

e*s2013-02-04 08:02

33 楼

求设计题答案，节约空间，节约时间是个什么做法？

e*e2013-02-04 08:02

34 楼

I'm not sure about "节约空间，节约时间是个什么做法？".
Here are my classes.
enum Role{
BOSS,
VP,
DIR,
MANAGER,
...
}
class Employee{
String id;
Role role;
List managed;
}
Maybe another class keep track of all references to the vips, dirs, managers
... so we can get them from this class by a single get method instead of
traversing from Boss employee. Like
class QuickRetrival {
List vips;
List dirs;
List managers;
...
}

【在 e***s 的大作中提到】

: 求设计题答案，节约空间，节约时间是个什么做法？

e*s2013-02-04 08:02

35 楼

谢谢，有没有大牛能解释一下节约空间，节约时间是怎么个思路？

【在 e****e 的大作中提到】

: I'm not sure about "节约空间，节约时间是个什么做法？".
: Here are my classes.
: enum Role{
: BOSS,
: VP,
: DIR,
: MANAGER,
: ...
: }
: class Employee{

e*s2013-02-04 08:02

36 楼

我推敲了一下，是不是用继承比较好。
class Employee{
UUID id;
String name;
List subordinates;
...
}
class Boss extends Employee{
}
class VP extends Employee{
}
...
这样是不是更符合开闭原则？

【在 e****e 的大作中提到】

: I'm not sure about "节约空间，节约时间是个什么做法？".
: Here are my classes.
: enum Role{
: BOSS,
: VP,
: DIR,
: MANAGER,
: ...
: }
: class Employee{