M****d
发帖数: 20 | 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***n
发帖数: 116 | 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******t
发帖数: 2374 | 3
一块一慢两个指针？
tree;
从root往下找，如果左边小右边大。common acestor应该是从root往下处于两者之间的
那个节
点。
啥叫做shallowest？难道不就是根节点么？
key,
time.
Rough
不理解。如果每个都是unique的，难道不是加一堆计数器就行了么？
如果要id可以重复的话可以用checksum之类的东西来缩短id吧。可以maintain一个hash
之类的
东西吧。
【在 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
| f**r
发帖数: 865 | | s******t
发帖数: 2374 | 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******t
发帖数: 2374 | 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******t
发帖数: 2374 | 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***n
发帖数: 116 | 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);
: }
| t******t
发帖数: 2404 | 9 bloom filter check the uniqueness of the key?
【在 s***n 的大作中提到】
: 我问的就是第三个问题。。。。。:P
|
|
