G****A 发帖数: 4160 | 1 Given a stream of integers. The elements arrive one by one. Write code to
find the median of the most recent k elements. You can assume k is odd.
e.g., when k=3,
输入: 1,3,5,7,9,11 ...
输出: 3,5, 7,9 ...
[1,3,5] --> [3]
[3,5,7] --> [5]
[5,7,9] --> [7]
[7,9,11]--> [9] | c*b 发帖数: 3126 | 2 用indexable skiplist可以做到每次取median是O(lgk)
https://rhettinger.wordpress.com/tag/running-median/
【在 G****A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a stream of integers. The elements arrive one by one. Write code to : find the median of the most recent k elements. You can assume k is odd. : e.g., when k=3, : 输入: 1,3,5,7,9,11 ... : 输出: 3,5, 7,9 ... : [1,3,5] --> [3] : [3,5,7] --> [5] : [5,7,9] --> [7] : [7,9,11]--> [9]
| r*********n 发帖数: 4553 | 3 用indexed priority_queue(2个,上半段+下半段)和一个counter(mod k)
(counter+1)%k可以得到expired的那个数的index,然后用
indexed_pq.update(idx,new_val)
把expired掉的那个数换成最新的数new_val | R*****i 发帖数: 2126 | 4 这个题目建议用红黑树做可能最快捷有效。红黑树每一次插入,删除都是log(k),求平
均值非常简单,就是根部的那个节点。所以总的计算量是O(nlog(k))。
以下是c/c++代码(需要修改数组,以便一个一个输入)。
#include
#include
#include
#define INDENT_STEP 4
enum rbtree_node_color {RED, BLACK};
typedef struct rbtree_node_t {
int value;
struct rbtree_node_t* left;
struct rbtree_node_t* right;
struct rbtree_node_t* parent;
enum rbtree_node_color color;
} *rbtree_node;
typedef rbtree_node node;
typedef enum rbtree_node_color color;
typedef struct rbtree_t {
rbtree_node root;
} *rbtree;
typedef int (*compare_func) (int left, int right);
static node grandparent(node n);
static node sibling(node n);
static node uncle(node n);
static void verify_properties(rbtree t);
static void verify_property_1(node root);
static void verify_property_2(node root);
static color node_color(node n);
static void verify_property_4(node root);
static void verify_property_5(node root);
static void verify_property_5_helper(node n, int black_count, int* black_
count_path);
rbtree rbtree_create();
static node new_node(int value, color node_color, node left, node right);
static node lookup_node(rbtree t, int value, compare_func compare);
static void rotate_left(rbtree t, node n);
static void rotate_right(rbtree t, node n);
static void replace_node(rbtree t, node oldn, node newn);
void rbtree_insert(rbtree t, int value, compare_func compare);
static void insert_case1(rbtree t, node n);
static void insert_case2(rbtree t, node n);
static void insert_case3(rbtree t, node n);
static void insert_case4(rbtree t, node n);
static void insert_case5(rbtree t, node n);
void rbtree_delete(rbtree t, int value, compare_func compare);
static node maximum_node(node root);
static void delete_case1(rbtree t, node n);
static void delete_case2(rbtree t, node n);
static void delete_case3(rbtree t, node n);
static void delete_case4(rbtree t, node n);
static void delete_case5(rbtree t, node n);
static void delete_case6(rbtree t, node n);
static int compare_int(int left, int right);
static void print_tree(rbtree t);
static void print_tree_helper(rbtree_node n, int indent);
color node_color(node n){
return n==NULL ? BLACK : n->color;
}
node grandparent(node n) {
assert (n != NULL);
assert (n->parent != NULL); /* Not the root node */
assert (n->parent->parent != NULL); /* Not child of root */
return n->parent->parent;
}
node sibling(node n) {
assert (n != NULL);
assert (n->parent != NULL); /* Root node has no sibling */
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
node uncle(node n) {
assert (n != NULL);
assert (n->parent != NULL); /* Root node has no uncle */
assert (n->parent->parent != NULL); /* Children of root have no uncle */
return sibling(n->parent);
}
void verify_property_1(node n){
assert(node_color(n) == RED || node_color(n) == BLACK);
if (n==NULL) return;
verify_property_1(n->left);
verify_property_1(n->right);
}
void verify_property_2(node root){
assert(node_color(root) == BLACK);
}
void verify_property_4(node n){
if(node_color(n) == RED) {
assert(node_color(n->left) == BLACK);
assert(node_color(n->right) == BLACK);
assert(node_color(n->parent) == BLACK);
}
if(n==NULL) return;
verify_property_4(n->left);
verify_property_4(n->right);
}
void verify_property_5_helper(node n, int black_count, int* path_black_count
){
if(node_color(n) == BLACK) {
black_count++;
}
if(n==NULL){
if (*path_black_count == -1) {
*path_black_count = black_count;
}else{
assert (black_count == *path_black_count);
}
return;
}
verify_property_5_helper(n->left, black_count, path_black_count);
verify_property_5_helper(n->right, black_count, path_black_count);
}
void verify_property_5(node root){
int black_count_path = -1;
verify_property_5_helper(root, 0, &black_count_path);
}
void verify_properties(rbtree t){
verify_property_1(t->root);
verify_property_2(t->root);
//property 3 is implicit
verify_property_4(t->root);
verify_property_5(t->root);
}
rbtree rbtree_create(){
rbtree t = (rbtree)malloc(sizeof(struct rbtree_t));
t->root = NULL;
verify_properties(t);
return t;
}
node new_node(int value, color node_color, node left, node right){
node result = (node)malloc(sizeof(struct rbtree_node_t));
result->value = value;
result->color = node_color;
result->left = left;
result->right = right;
if(left != NULL) left->parent = result;
if(right != NULL) right->parent = result;
result->parent = NULL;
return result;
}
node lookup_node(rbtree t, int value, compare_func compare){
node n = t->root;
while (n!= NULL){
int comp_result = compare(value, n->value);
if(comp_result == 0) {
return n;
}else if(comp_result<0){
n=n->left;
}else {
assert(comp_result>0);
n=n->right;
}
}
return 0;
}
void replace_node(rbtree t, node oldn, node newn) {
if (oldn->parent == NULL) {
t->root = newn;
} else {
if (oldn == oldn->parent->left)
oldn->parent->left = newn;
else
oldn->parent->right = newn;
}
if (newn != NULL) {
newn->parent = oldn->parent;
}
}
void rotate_left(rbtree t, node n){
node r = n->right;
replace_node(t, n, r);
n->right = r->left;
if(r->left != NULL){
r->left->parent = n;
}
r->left = n;
n->parent = r;
}
void rotate_right(rbtree t, node n) {
node L = n->left;
replace_node(t, n, L);
n->left = L->right;
if (L->right != NULL) {
L->right->parent = n;
}
L->right = n;
n->parent = L;
}
void rbtree_insert(rbtree t, int value, compare_func compare) {
node inserted_node = new_node(value, RED, NULL, NULL);
if (t->root == NULL) {
t->root = inserted_node;
} else {
node n = t->root;
while (1) {
int comp_result = compare(value, n->value);
if (comp_result == 0) {
free (inserted_node);
return;
} else if (comp_result < 0) {
if (n->left == NULL) {
n->left = inserted_node;
break;
} else {
n = n->left;
}
} else {
assert (comp_result > 0);
if (n->right == NULL) {
n->right = inserted_node;
break;
} else {
n = n->right;
}
}
}
inserted_node->parent = n;
}
insert_case1(t, inserted_node);
verify_properties(t);
}
void insert_case1(rbtree t, node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(t, n);
}
void insert_case2(rbtree t, node n) {
if (node_color(n->parent) == BLACK)
return; /* Tree is still valid */
else
insert_case3(t, n);
}
void insert_case3(rbtree t, node n) {
if (node_color(uncle(n)) == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(t, grandparent(n));
} else {
insert_case4(t, n);
}
}
void insert_case4(rbtree t, node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(t, n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(t, n->parent);
n = n->right;
}
insert_case5(t, n);
}
void insert_case5(rbtree t, node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(t, grandparent(n));
} else {
assert (n == n->parent->right && n->parent == grandparent(n)->right);
rotate_left(t, grandparent(n));
}
}
void rbtree_delete(rbtree t, int value, compare_func compare) {
node child;
node n = lookup_node(t, value, compare);
if (n == NULL) return; /* Key not found, do nothing */
if (n->left != NULL && n->right != NULL) {
/* Copy value from predecessor and then delete it instead */
node pred = maximum_node(n->left);
n->value = pred->value;
n = pred;
}
assert(n->left == NULL || n->right == NULL);
child = n->right == NULL ? n->left : n->right;
if (node_color(n) == BLACK) {
n->color = node_color(child);
delete_case1(t, n);
}
replace_node(t, n, child);
if (n->parent == NULL && child != NULL)
child->color = BLACK;
free(n);
verify_properties(t);
}
void delete_case1(rbtree t, node n) {
if (n->parent == NULL)
return;
else
delete_case2(t, n);
}
void delete_case2(rbtree t, node n) {
if (node_color(sibling(n)) == RED) {
n->parent->color = RED;
sibling(n)->color = BLACK;
if (n == n->parent->left)
rotate_left(t, n->parent);
else
rotate_right(t, n->parent);
}
delete_case3(t, n);
}
void delete_case3(rbtree t, node n) {
if (node_color(n->parent) == BLACK &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == BLACK &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
delete_case1(t, n->parent);
}
else
delete_case4(t, n);
}
void delete_case4(rbtree t, node n) {
if (node_color(n->parent) == RED &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == BLACK &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
delete_case5(t, n);
}
void delete_case5(rbtree t, node n) {
if (n == n->parent->left &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->left) == RED &&
node_color(sibling(n)->right) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotate_right(t, sibling(n));
}
else if (n == n->parent->right &&
node_color(sibling(n)) == BLACK &&
node_color(sibling(n)->right) == RED &&
node_color(sibling(n)->left) == BLACK)
{
sibling(n)->color = RED;
sibling(n)->right->color = BLACK;
rotate_left(t, sibling(n));
}
delete_case6(t, n);
}
void delete_case6(rbtree t, node n) {
sibling(n)->color = node_color(n->parent);
n->parent->color = BLACK;
if (n == n->parent->left) {
assert (node_color(sibling(n)->right) == RED);
sibling(n)->right->color = BLACK;
rotate_left(t, n->parent);
}
else
{
assert (node_color(sibling(n)->left) == RED);
sibling(n)->left->color = BLACK;
rotate_right(t, n->parent);
}
}
static node maximum_node(node n) {
assert (n != NULL);
while (n->right != NULL) {
n = n->right;
}
return n;
}
void print_tree_helper(rbtree_node n, int indent) {
int i;
if (n == NULL) {
fputs("", stdout);
return;
}
if (n->right != NULL) {
print_tree_helper(n->right, indent + INDENT_STEP);
}
for(i=0; i
fputs(" ", stdout);
if (n->color == BLACK)
printf("%d\n", n->value);
else
printf("<%d>\n", n->value);
if (n->left != NULL) {
print_tree_helper(n->left, indent + INDENT_STEP);
}
}
void print_tree(rbtree t) {
print_tree_helper(t->root, 0);
puts("");
}
int compare_int(int left, int right) {
if (left < right)
return -1;
else if (left > right)
return 1;
else {
assert (left == right);
return 0;
}
}
int main(){
const int w = 3;
int A[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(A)/sizeof(A[0]);
int i;
rbtree r = rbtree_create();
for(i=0; i
rbtree_insert(r, A[i], compare_int);
}
//printf("%d", maximum_node(r->root)->value);
printf("%d", r->root->value);
for(i=w; i
rbtree_delete(r, A[i-3], compare_int);
rbtree_insert(r, A[i], compare_int);
//printf("\n%d", maximum_node(r->root)->value);
printf("%d", r->root->value);
}
return 0;
} | e*****t 发帖数: 1005 | 5 I doubt RB tree will always give you the median at the root.
http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
"The balancing of the tree is not perfect but it is good enough to allow it
to guarantee searching in O(log n) time"
You need a perfectly balanced binary search tree to get the median at the ro
ot.
【在 R*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目建议用红黑树做可能最快捷有效。红黑树每一次插入,删除都是log(k),求平 : 均值非常简单,就是根部的那个节点。所以总的计算量是O(nlog(k))。 : 以下是c/c++代码(需要修改数组,以便一个一个输入)。 : #include : #include : #include : #define INDENT_STEP 4 : enum rbtree_node_color {RED, BLACK}; : typedef struct rbtree_node_t { : int value;
| L***Q 发帖数: 508 | 6 哥,你太牛了,顶一个
【在 c*b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用indexable skiplist可以做到每次取median是O(lgk) : https://rhettinger.wordpress.com/tag/running-median/
| G****A 发帖数: 4160 | 7 谢谢。有没有更intuitive的解法?
给了2个暗示:1)k很小(<=5); 2)用最基本的逻辑和数据结构,不要用stack/queue/
hash等
ADT.
我当时就说,如果k=3,那干脆直接看3个值大小,需要compare至多3次找到median,
complexity就是O(n),where n is the size of stream.面试官说可以,让我写code,
要求考虑全所有的cases.不知道他想考察考哪方面
【在 r*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用indexed priority_queue(2个,上半段+下半段)和一个counter(mod k) : (counter+1)%k可以得到expired的那个数的index,然后用 : indexed_pq.update(idx,new_val) : 把expired掉的那个数换成最新的数new_val
| d****n 发帖数: 397 | 8 vector median(vector & v, int k) {
vector::iterator iter;
vector median;
iter=v.begin();
while((iter+k-1)!=v.end()) {
vector temp(iter,iter+k);
sort(temp.begin(),temp.end());
median.push_back(temp[k/2]);
iter++;
}
return median;
}
这个比较简单,也没有用stack,queue,hash.
【在 G****A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢。有没有更intuitive的解法? : 给了2个暗示:1)k很小(<=5); 2)用最基本的逻辑和数据结构,不要用stack/queue/ : hash等 : ADT. : 我当时就说,如果k=3,那干脆直接看3个值大小,需要compare至多3次找到median, : complexity就是O(n),where n is the size of stream.面试官说可以,让我写code, : 要求考虑全所有的cases.不知道他想考察考哪方面
| r*********n 发帖数: 4553 | 9 既然k很小,直接存到circular array里面,每次都把整个array扫一边,取出中数。
【在 G****A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢。有没有更intuitive的解法? : 给了2个暗示:1)k很小(<=5); 2)用最基本的逻辑和数据结构,不要用stack/queue/ : hash等 : ADT. : 我当时就说,如果k=3,那干脆直接看3个值大小,需要compare至多3次找到median, : complexity就是O(n),where n is the size of stream.面试官说可以,让我写code, : 要求考虑全所有的cases.不知道他想考察考哪方面
| r*********n 发帖数: 4553 | 10 这是杀鸡用牛刀吧
我个人觉得red-black tree的delete method非常难写。
【在 R*****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题目建议用红黑树做可能最快捷有效。红黑树每一次插入,删除都是log(k),求平 : 均值非常简单,就是根部的那个节点。所以总的计算量是O(nlog(k))。 : 以下是c/c++代码(需要修改数组,以便一个一个输入)。 : #include : #include : #include : #define INDENT_STEP 4 : enum rbtree_node_color {RED, BLACK}; : typedef struct rbtree_node_t { : int value;
| R*****i 发帖数: 2126 | 11 http://richardhartersworld.com/cri/2011/winmedian.html
Conclusions
Well written array implementations are preferable for small windows. Judging
from similar problems, the breakpoint is probably for window sizes of
around 20-30. For larger window sizes the double heap algorithm is simple
and has guaranteed performance. There may be better alternatives but
establishing them will require significant amounts of testing and analysis. |
|