r******k
发帖数: 46 | 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***o
发帖数: 1182 | 2 这俩是背靠背吗？
【在 r******k 的大作中提到】
: 面的SDE intern，题目比较简单，但是第二题没答好，希望能拿到offer
: 1号：
: 谈谈经历
: 讨论了一下hashtable的特性，collision怎么办，复杂度如何
: hashset和treeset的利弊
: 然后是题目： BST的第二大元素
: 2号：
: （感觉面试官没怎么好好准备）
: OOP题目
: 一个company，有boss，vp,dir,manager,employee，让设计类
|
c********t
发帖数: 5706 | 3 然后是题目： BST的第二大元素
应该是 从右子树开始inorder travesal的第二个吧。要求必须iteration吗？
【在 r******k 的大作中提到】
: 面的SDE intern，题目比较简单，但是第二题没答好，希望能拿到offer
: 1号：
: 谈谈经历
: 讨论了一下hashtable的特性，collision怎么办，复杂度如何
: hashset和treeset的利弊
: 然后是题目： BST的第二大元素
: 2号：
: （感觉面试官没怎么好好准备）
: OOP题目
: 一个company，有boss，vp,dir,manager,employee，让设计类
|
l*******b
发帖数: 2586 | 4 找到最大然后call一下in order previous?
【在 c********t 的大作中提到】
: 然后是题目： BST的第二大元素
: 应该是 从右子树开始inorder travesal的第二个吧。要求必须iteration吗？
|
r******k
发帖数: 46 | 5 没要求，虽然我当时是用iteration
【在 c********t 的大作中提到】
: 然后是题目： BST的第二大元素
: 应该是 从右子树开始inorder travesal的第二个吧。要求必须iteration吗？
|
f*******7
发帖数: 943 | |
p*****2
发帖数: 21240 | 7
就是最右叶子的父亲吧？如果没有右子树，就是左子树的最右叶子。
【在 c********t 的大作中提到】
: 然后是题目： BST的第二大元素
: 应该是 从右子树开始inorder travesal的第二个吧。要求必须iteration吗？
|
e****e
发帖数: 418 | 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*****2
发帖数: 21240 | 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**********x
发帖数: 4083 | 10 1
\
3
/
2
【在 p*****2 的大作中提到】
:
: 's
: 没这么麻烦吧？
|
|
|
p*****2
发帖数: 21240 | 11 错了呗。
1
\
2
/
3
这个是BST吗？ |
d**********x
发帖数: 4083 | 12 我改了
想的是上面那个
【在 p*****2 的大作中提到】
: 错了呗。
: 1
: \
: 2
: /
: 3
: 这个是BST吗？
|
p*****2
发帖数: 21240 | 13
确实呀。我想一下。
【在 d**********x 的大作中提到】
: 我改了
: 想的是上面那个
|
e****e
发帖数: 418 | 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*****2
发帖数: 21240 | 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**********x
发帖数: 4083 | 16 你的方向应该是对的
只是情况没考虑周全。。。
【在 p*****2 的大作中提到】
:
: 主要是面试的时候很可能不让用recursion
|
a***o
发帖数: 1182 | 17 最右叶子,如果有左子树,那就是左子树的最右叶子
否则就是父亲,如果没有父亲,就是左子树的最右叶子
一共三种情况
【在 p*****2 的大作中提到】
:
: 主要是面试的时候很可能不让用recursion
|
c********t
发帖数: 5706 | 18 那就用stack啊
【在 p*****2 的大作中提到】
:
: 主要是面试的时候很可能不让用recursion
|
d**********x
发帖数: 4083 | 19 1
\
3
/
2
\
2.5
【在 a***o 的大作中提到】
: 最右叶子,如果有左子树,那就是左子树的最右叶子
: 否则就是父亲,如果没有父亲,就是左子树的最右叶子
: 一共三种情况
|
a***o
发帖数: 1182 | 20 你这个不是BST吧
3的左子树都要<3的
【在 d**********x 的大作中提到】
: 1
: \
: 3
: /
: 2
: \
: 2.5
|
|
|
d**********x
发帖数: 4083 | 21 sorry
我总是想到那个结构。。然后数字写错，你看我改的
【在 a***o 的大作中提到】
: 你这个不是BST吧
: 3的左子树都要<3的
|
p*****2
发帖数: 21240 | 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***o
发帖数: 1182 | 23 3kx,我也改了一下,改成左子树的最有叶子
【在 d**********x 的大作中提到】
: sorry
: 我总是想到那个结构。。然后数字写错，你看我改的
|
p*****2
发帖数: 21240 | 24
这题应该没那么麻烦。
【在 c********t 的大作中提到】
: 那就用stack啊
|
d**********x
发帖数: 4083 | |
p*****2
发帖数: 21240 | 26
我的思路跟你是一样的。有什么问题吗？
【在 a***o 的大作中提到】
: 3kx,我也改了一下,改成左子树的最有叶子
|
d**********x
发帖数: 4083 | 27 那就应该没问题了
【在 p*****2 的大作中提到】
:
: 我的思路跟你是一样的。有什么问题吗？
|
c********t
发帖数: 5706 | 28 如果node没有parent 指针,前驱怎么找？我看还要遍历才行。
【在 d**********x 的大作中提到】
: 看这个
: http://bbs.sjtu.edu.cn/bbscon,board,Algorithm,file,M.1041171619
: 其中那个in-order的前驱
|
d**********x
发帖数: 4083 | 29 这个特殊问题里不需要，只要记录两个节点，轮换着来就行了
因为这个问题里前驱无非是最右leaf的左子树的最大节点，或者是它的parent。
【在 c********t 的大作中提到】
: 如果node没有parent 指针,前驱怎么找？我看还要遍历才行。
|
p*****2
发帖数: 21240 | 30
看看我的code有没有什么问题。
【在 c********t 的大作中提到】
: 如果node没有parent 指针,前驱怎么找？我看还要遍历才行。
|
|
|
c********t
发帖数: 5706 | 31 明白了，没有问题。
多谢devil和二爷！
【在 p*****2 的大作中提到】
:
: 看看我的code有没有什么问题。
|
p*****2
发帖数: 21240 | |
e***s
发帖数: 799 | 33 求设计题答案，节约空间，节约时间是个什么做法？ |
e****e
发帖数: 418 | 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***s
发帖数: 799 | 35 谢谢，有没有大牛能解释一下节约空间，节约时间是怎么个思路？
【在 e****e 的大作中提到】
: I'm not sure about "节约空间，节约时间是个什么做法？".
: Here are my classes.
: enum Role{
: BOSS,
: VP,
: DIR,
: MANAGER,
: ...
: }
: class Employee{
|
e***s
发帖数: 799 | 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{
|
