Facebook Phone Screen - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Facebook Phone Screen

Facebook Phone Screen# JobHunting - 待字闺中

M*d2007-09-27 07:09

1 楼

三个问题
1. Given a linked list, unsorted, determine the middle point of it;
2. Find the deepest common ancestor of two leaves in a binary search tree;
Do not traverse from the leaves. Instead, locate the node top/down.
How about finding the shallowest common ancestor of two leaves?
3. Given constant incoming requests, each associated with a unique key,
estimate the total amount of unique requests within a period of time.
The number of keys explodes the memory. Do not touch the disk. Rou

s*n2007-09-27 07:09

2 楼

这第三个问题怎么答？

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

: 三个问题
: 1. Given a linked list, unsorted, determine the middle point of it;
: 2. Find the deepest common ancestor of two leaves in a binary search tree;
: Do not traverse from the leaves. Instead, locate the node top/down.
: How about finding the shallowest common ancestor of two leaves?
: 3. Given constant incoming requests, each associated with a unique key,
: estimate the total amount of unique requests within a period of time.
: The number of keys explodes the memory. Do not touch the disk. Rou

s*t2007-09-27 07:09

3 楼

一块一慢两个指针？
tree;
从root往下找，如果左边小右边大。common acestor应该是从root往下处于两者之间的
那个节
点。
啥叫做shallowest？难道不就是根节点么？
key,
time.
Rough
不理解。如果每个都是unique的，难道不是加一堆计数器就行了么？
如果要id可以重复的话可以用checksum之类的东西来缩短id吧。可以maintain一个hash
之类的
东西吧。

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

f*r2007-09-27 07:09

4 楼

Sampling, I suppose...

s*t2007-09-27 07:09

5 楼

我来写一下吧
第一个：
1. Given a linked list, unsorted, determine the middle point of it;
class Node {
Node next;
int value;
}
int getMiddle(Node root){
Node fast=root;
Node slow=root;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

s*t2007-09-27 07:09

6 楼

第二个：
2. Find the deepest common ancestor of two leaves in a binary search
tree;
从root往下找，如果左边小右边大。common acestor应该是从root往下处于两者之间的
那个节
点。
Node findAncestor(Node a, Node b, Node root){
Node c = root;
while(true){
if(c.value> a.value && c.value > b.value) c = c.left;
else if(c.value< a.value && c.value < b.value) c = c.right;
else break;
}
return c;
}

s*t2007-09-27 07:09

7 楼

找了一个以前写的递归的
public int findLowestAncestor(Node root, int value1, int value2) {
if (root == null) return -1;

if (root.value > value1 && root.value > value2) {
findLowestAncestor(root.left, value1, value2);
}
else if (root.value < value1 && root.value < value2) {
findLowestAncestor(root.right, value1, value2);
}
else return root.value;
}

s*n2007-09-27 07:09

8 楼

我问的就是第三个问题。。。。。:P

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

: 找了一个以前写的递归的
: public int findLowestAncestor(Node root, int value1, int value2) {
: if (root == null) return -1;
:
: if (root.value > value1 && root.value > value2) {
: findLowestAncestor(root.left, value1, value2);
: }
: else if (root.value < value1 && root.value < value2) {
: findLowestAncestor(root.right, value1, value2);
: }