l****i
发帖数: 2772 | 1 今天onsite，前三个面试官都是三哥。
被第二个三哥问晕了。问了我3道题。有一题是一个DP，白板写了。其他2个问题，跪了。
1.
问：无限数据流里，sample出k个。
答：reservoir sampling
问：解释一下这个算法
答：blabla
问：这个算法取每个数据的概率不一样，不可以
答：这是个经典算法，有paper证明过这个
问：好，那你现在证明一下这个算法
没研究过这个算法的证明，当场跪了。三哥坚持reservoir sampling是错误的。没办法
，我给了另外一个解法，每个data算一个random score，用heap保持score高的k个。
2.
问：给你一个binary tree，换成linked list
答：我问，是普通的binary tree? 不是BST？
问：就是最普通的任意binary tree
答：可以inorder走一遍，转换成linked list，返回inorder的第一个node作为list的
head
问：变成linked list后，怎么reconstruct回原来的binary tree。要求in place。
答：！#%&（，跪了，我觉得无解。
最后问三哥，怎么能reconstruct回去，三哥说，你多看看网上的题目，你会学到很多
知识。。。。！#%&（。。。 |
g*********e
发帖数: 14401 | 2 1
可以用数学归纳法证明
2
binary tree serialize / deserialize leetcode有 |
l****i
发帖数: 2772 | 3 第2题不是那个意思。inplace flatten变为linkedlist，再变回去。不是普通的BT的
serialize、deserialize
【在 g*********e 的大作中提到】
: 1
: 可以用数学归纳法证明
: 2
: binary tree serialize / deserialize leetcode有
|
g*********e
发帖数: 14401 | 4
肯定是需要insert一些空node，三哥都叫你看网上题目了。也真赤裸裸 lol
【在 l****i 的大作中提到】
: 第2题不是那个意思。inplace flatten变为linkedlist，再变回去。不是普通的BT的
: serialize、deserialize
|
l****i
发帖数: 2772 | 5 这样不是inplace了。。。三哥要求constant space
【在 g*********e 的大作中提到】
:
: 肯定是需要insert一些空node，三哥都叫你看网上题目了。也真赤裸裸 lol
|
S******1
发帖数: 216 | 6
了。
哥们不想在微软了？
【在 l****i 的大作中提到】
: 今天onsite，前三个面试官都是三哥。
: 被第二个三哥问晕了。问了我3道题。有一题是一个DP，白板写了。其他2个问题，跪了。
: 1.
: 问：无限数据流里，sample出k个。
: 答：reservoir sampling
: 问：解释一下这个算法
: 答：blabla
: 问：这个算法取每个数据的概率不一样，不可以
: 答：这是个经典算法，有paper证明过这个
: 问：好，那你现在证明一下这个算法
|
l*********8
发帖数: 4642 | 7 1。 数学归纳法
2. 刚才想了下，这样可否：
binary tree转换成linked list时，按level遍历， right child指针指向next。
left指针没用，可以指向parent.
这样就可以从"linked list"恢复binary tree了。
了。
【在 l****i 的大作中提到】
: 今天onsite，前三个面试官都是三哥。
: 被第二个三哥问晕了。问了我3道题。有一题是一个DP，白板写了。其他2个问题，跪了。
: 1.
: 问：无限数据流里，sample出k个。
: 答：reservoir sampling
: 问：解释一下这个算法
: 答：blabla
: 问：这个算法取每个数据的概率不一样，不可以
: 答：这是个经典算法，有paper证明过这个
: 问：好，那你现在证明一下这个算法
|
c*******r
发帖数: 610 | |
i*******n
发帖数: 114 | 9 第二题和我年初电面google的题目一样（也是印度人面的）
这个需要pass by reference。如果用C++做，就比较好做。如果用java，需要自定义一
个类，然后里面有一个成员变量带有node。下面的是我使用全局变量做的。
/**
Convert a binary tree
into a circular double linked list such that the linked list
elements are in the order of the in-order traversal result of the binary
tree.
**/
class Node{
int val;
Node left;
Node right;
}
public class BinaryTreeIntoDoubleLL{
/**
*
* return the head node of the converted double linked list
*
* @param rootNode
* @return
*/
public Node convertBinaryTreeIntoDoubleLL(Node rootNode){
if(rootNode == null){
return null;
}
visitAndConvert(rootNode);
/**
* now the rootNode becomes the middle node
*
* set the head and tail nodes
*/
Node head = rootNode;
Node tail = rootNode;
while(head.left != null) {
head = head.left;
}
while(tail.right != null) {
tail = tail.right;
}
head.left = tail;
tail.right = head;
return head;
}
/**
*
* global variable to keep the previously visited node
*
*/
Node prevVisitedNode = null;
private void visitAndConvert(Node node){
if(node == null){
return;
}
if(node.left != null){
visitAndConvert(node);
}
node.left = this.prevVisitedNode;
if(this.prevVisitedNode != null){
this.prevVisitedNode.right = node;
}
this.prevVisitedNode = node;
if(node.right != null){
visitAndConvert(node.right);
}
}
public static void main(String[] args){
BinaryTreeIntoDoubleLL sol = new BinaryTreeIntoDoubleLL();
Node rootNode = new Node();
sol.convertBinaryTreeIntoDoubleLL(rootNode);
}
} |
l*********8
发帖数: 4642 | 10 楼主还需要从linked list restore binary tree。 如果只是double linked list的话：
class BinaryTreeToLinkedList {
public:
TreeNode *head, *tail;
BinearyTreeToLinkedList(TreeNode *root) : head(NULL), tail(NULL) {
convert(root);
}
private:
convert(TreeNode *curr) {
if (!curr) return;
convert(curr->left);
if (tail)
tail->right = curr;
else
head = curr;
curr->left = tail;
tail = curr;
convert(curr->right);
}
};
【在 i*******n 的大作中提到】
: 第二题和我年初电面google的题目一样（也是印度人面的）
: 这个需要pass by reference。如果用C++做，就比较好做。如果用java，需要自定义一
: 个类，然后里面有一个成员变量带有node。下面的是我使用全局变量做的。
: /**
: Convert a binary tree
: into a circular double linked list such that the linked list
: elements are in the order of the in-order traversal result of the binary
: tree.
: **/
: class Node{
|
l*********8
发帖数: 4642 | 11 重新想了一下之前第二题的思路。 觉得应该转换成linked list的时候，应该用pre
order遍历。
【在 l*********8 的大作中提到】
: 1。 数学归纳法
: 2. 刚才想了下，这样可否：
: binary tree转换成linked list时，按level遍历， right child指针指向next。
: left指针没用，可以指向parent.
: 这样就可以从"linked list"恢复binary tree了。
:
: 了。
|
R********r
发帖数: 48 | 12 感觉yahoo要被三哥占领了，走在campus里一水阿三 |
