Iphone 6+ 在AMAZON开卖了，$1,722.00 + $10.49 shipping (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Iphone 6+ 在AMAZON开卖了，$1,722.00 + $10.49 shipping (转载)

Iphone 6+ 在AMAZON开卖了，$1,722.00 + $10.49 shipping (转载)# Joke - 肚皮舞运动

d*m2014-09-19 07:09

1 楼

Given an unbalanced binary tree, write code to select a node at random (each
node has an equal probability of being selected).

d*r2014-09-19 07:09

2 楼

【此篇文章是由自动发信系统所张贴】
⊙ 博彩开启于：Sat Aug 28 00:12:43 2010 类别：单选
⊙ 主题：8月30-9月3月日一周大盘(DOW)涨跌
⊙ 博彩题目描述：
本博彩没有描述
【选项如下】
(1) 涨200点以上
(2) 涨200点以内(包括200)
(3) 平或跌200点以内(包括200)
(4) 跌超过200点

r*82014-09-19 07:09

3 楼

【以下文字转载自 LosAngeles 讨论区】
发信人: realman888 (realman), 信区: LosAngeles
标题: Iphone 6+ 在AMAZON开卖了，$1,722.00 + $10.49 shipping
发信站: BBS 未名空间站 (Fri Sep 19 17:08:24 2014, 美东)
靠，
http://www.amazon.com/Apple-iPhone-Plus-128gb-Gold/dp/B00NGBIMD

l*s2014-09-19 07:09

4 楼

traverse once first to get node total amount, then use this amount as random
domain.

each

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

: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).

l*t2014-09-19 07:09

5 楼

降价了？
$1658+$4.49

h*g2014-09-19 07:09

6 楼

用个计数器C，初始值为1，遍历树的时候以1/C的概率用当前被访问节点的值替换要返
回的值，然后C 1 这样只需遍历一遍忘了算法的具体名字了

w*a2014-09-19 07:09

7 楼

这玩意儿就是短期行为，有价无市，愿意买的就那几个，你标价1700，拉高市场价格预
期，只能让极少数人赚一两个iphone的钱，其他人标价1300都不一定能卖的出去。
等iphone流通够了，应该一周内就回落到几乎apple的标价。
现在的短期炒高行为是被少数希望早日用上i6的土豪鼓动的，不可能持续超过一周，就
算他标高价，没人买还不是赚不到钱。

a*y2014-09-19 07:09

8 楼

postorder遍历一次，在每个parent节点上返回左右节点总数，有这个信息之后就可以
随机访问了吧

q*l2014-09-19 07:09

9 楼

这东西早用几周晚用几周会有什么差别呢，很难理解

l*z2014-09-19 07:09

10 楼

有点象算术编码反过来

each

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

: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).

r*e2014-09-19 07:09

11 楼

https://en.m.wikipedia.org/wiki/Reservoir_sampling

【在 h*********g 的大作中提到】

: 用个计数器C，初始值为1，遍历树的时候以1/C的概率用当前被访问节点的值替换要返
: 回的值，然后C 1 这样只需遍历一遍忘了算法的具体名字了

d*n2014-09-19 07:09

12 楼

按node subtree size 分配概率，然后recursion。1/root.size概率选root，root.
left.size / root.size 概率从left subtree选， root.right.size/root.size从
right subtree选。

each

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

: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).

h*p2014-09-19 07:09

13 楼

为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
问？

c*n2014-09-19 07:09

14 楼

easy
count total
then select 1 from that range
then go down the preorder traversal. and take n'th node

each

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

: Given an unbalanced binary tree, write code to select a node at random (each
: node has an equal probability of being selected).

r*e2014-09-19 07:09

15 楼

需要做两次遍历的不是最佳答案

【在 c******n 的大作中提到】

: easy
: count total
: then select 1 from that range
: then go down the preorder traversal. and take n'th node
:
: each

r*e2014-09-19 07:09

16 楼

你觉得面试官会期待这样的答案么

【在 h**p 的大作中提到】

: 为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
: 问？

c*n2014-09-19 07:09

17 楼

OK 那也简单， recursive 每个子树，给出 size 和要的 random number ，然后
parent 根据 1/（left size + right size+1）给自己，左，右。分概率，产生
parent 层的 random

【在 r*******e 的大作中提到】

: 需要做两次遍历的不是最佳答案

k*i2014-09-19 07:09

18 楼

BinaryTree* randomTreeNode(BinaryTree* root)
{
if(!root) return NULL;
int count=0;
BinaryTree* choice;
randomTreeNode(root, count, choice);
return choice;
}
void preOrder(BinaryTree* root, int& count, BinaryTree*& choice)
{
if(rand()<1/count) {
choice=root;
}
if(root->left) {
count++;
preOrder(root->left, count, choice);
}
if(root->rigth) {
count++;
preOrder(root->right, count, choice);
}
}

k*a2014-09-19 07:09

19 楼

感觉是访问Kth节点的变形。
一次遍历，给每一个节点加上其下包含的节点的总数。
根节点的总数为n，那么随机取第n*random()个节点。

l*i2014-09-19 07:09

20 楼

getRandomNode(Node *root) : return pair

g*42014-09-19 07:09

21 楼

if(rand()<1/count) {
rand()是什么方法？

【在 k****i 的大作中提到】

: BinaryTree* randomTreeNode(BinaryTree* root)
: {
: if(!root) return NULL;
: int count=0;
: BinaryTree* choice;
: randomTreeNode(root, count, choice);
: return choice;
: }
: void preOrder(BinaryTree* root, int& count, BinaryTree*& choice)
: {

k*a2014-09-19 07:09

22 楼

两遍的方案可以接受，reservoir sampling虽说简单，但是不知道的还是不容易想到

【在 r*******e 的大作中提到】

: 需要做两次遍历的不是最佳答案

l*s2014-09-19 07:09

23 楼

not too far from reservoir sampling, while it's space O(k), yours is always
space O(n), k is the random number, n is the total space. when k == n, that'
s the worst case of reservoir sampling.

【在 h**p 的大作中提到】

: 为什么不能遍历一遍，把node存在array里面，然后用random（1，arr.size） - 1来访
: 问？