由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - Groupon面筋。。。。
相关主题
● 来个面经：unfair coin問題● 一道rocket fuel的题
● Epic 店面被考到coding的题目。。。（面经）● fb家面试题讨论
● 问个anagram的算法题● LC装水容器题一定要O(nlogn)做法吗？
● 发一个fb面经● array 转换成 linkedlist, 在线等, 挺急的--help is still nee
● 一道面试题● rand5 -> rand7的解法？
● List Flattening from book ● Bloomerg 还没放弃我。 电话二面经过。
● 问一道twitter面试题● google phone interview
● 明天电面，求建议● 问个anagram的题目啊
相关话题的讨论汇总
话题: rand话题: head话题: return话题: tail话题: rand2
进入JobHunting版参与讨论
1 (共1页)
m*****1
发帖数: 147
1
1.如何判断Anagram
2.一个file有1billion个数字，找到top15
3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
何利用原有方程，再写一个function，使得返回true和false的概率一样。。
这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
少了。。。真的希望顺利啊。。
P*******b
发帖数: 1001
2
这三题怎么做？

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
p*****2
发帖数: 21240
3
1. if rand==head return head
2. if rand==head return head
3. if rand==head && rand==head return head
else return tail
e***s
发帖数: 799
4
if(rand == head) return head;
if(rand == head) return head;
return tail;
就行了吧？ 1/4 + 1/4 = 1/2;

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
x*****0
发帖数: 452
5
mark
s*****l
发帖数: 10
6
这样返回tail的概率是(3/4)*(3/4) = 9/16吧？

【在 e***s 的大作中提到】
: if(rand == head) return head;
: if(rand == head) return head;
: return tail;
: 就行了吧？ 1/4 + 1/4 = 1/2;
j******2
发帖数: 362
7
请问面的哪个office?
thx

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
p*****2
发帖数: 21240
8

是

【在 s*****l 的大作中提到】
: 这样返回tail的概率是(3/4)*(3/4) = 9/16吧？
h***i
发帖数: 1970
9
1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
不对吧？

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
p*****2
发帖数: 21240
10

我得意思是可以继续下去，

【在 h***i 的大作中提到】
: 1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
: 不对吧？
相关主题
● List Flattening from book ● 一道rocket fuel的题
● 问一道twitter面试题● fb家面试题讨论
● 明天电面，求建议● LC装水容器题一定要O(nlogn)做法吗？
进入JobHunting版参与讨论
h***i
发帖数: 1970
11
其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
的两种情况重新来。

【在 p*****2 的大作中提到】
:
: 我得意思是可以继续下去，
R******1
发帖数: 58
12
是，我也觉得不对

【在 h***i 的大作中提到】
: 1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
: 不对吧？
h*****n
发帖数: 2872
13
额...会死循环吧...

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
h***i
发帖数: 1970
14
如果你不相信概率的话，这两种情况发生的可能性占6/16，循环个3次就差不多出来了。

【在 h*****n 的大作中提到】
: 额...会死循环吧...
f*******t
发帖数: 7549
15
可能性比较小

【在 h*****n 的大作中提到】
: 额...会死循环吧...
e***s
发帖数: 799
16
我错了，我是猪

【在 e***s 的大作中提到】
: if(rand == head) return head;
: if(rand == head) return head;
: return tail;
: 就行了吧？ 1/4 + 1/4 = 1/2;
p*****2
发帖数: 21240
17

这个不错。我的那个是继续扔，最后可以非常接近1/2。

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
p*****2
发帖数: 21240
18

如果继续扔，最后可以非常接近1/2。当然没有LS的方法好了。

【在 R******1 的大作中提到】
: 是，我也觉得不对
h***i
发帖数: 1970
19
你这个需要算级数了。

【在 p*****2 的大作中提到】
:
: 如果继续扔，最后可以非常接近1/2。当然没有LS的方法好了。
b*****u
发帖数: 648
20
恩，优点是能解决任意的uneven coin
缺点是最坏情况无穷久

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
相关主题
● array 转换成 linkedlist, 在线等, 挺急的--help is still nee● google phone interview
● rand5 -> rand7的解法？● 问个anagram的题目啊
● Bloomerg 还没放弃我。 电话二面经过。● 关于anagram的老题？
进入JobHunting版参与讨论
b*****u
发帖数: 648
21
我的方法：
rand1= rand;
rand2= rand;
rand3= rand;
rand4= rand;
if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
return tail
else
return head;
3/4*3/4-1/4*1/4 = 1/2

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
p****e
发帖数: 3548
22
概率能相减的？这样可以不
if(rand() || rand())
return head;
return tail;

【在 b*****u 的大作中提到】
: 我的方法：
: rand1= rand;
: rand2= rand;
: rand3= rand;
: rand4= rand;
: if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
: return tail
: else
: return head;
: 3/4*3/4-1/4*1/4 = 1/2
d*s
发帖数: 699
23
FT/TF其余循环肯定没问题，楼上的概率不能相减，第一个为真第二个必然为真
i****n
发帖数: 109
24
这样可以不
rand1=rand();
rand2=rand();
if((rand1==head && rand2==tail)||(rand1==tail && rand2==head))
return head;
return tail;

【在 p****e 的大作中提到】
: 概率能相减的？这样可以不
: if(rand() || rand())
: return head;
: return tail;
B********t
发帖数: 147
25
这个不行吧。返回head的概率是6/16啊

【在 i****n 的大作中提到】
: 这样可以不
: rand1=rand();
: rand2=rand();
: if((rand1==head && rand2==tail)||(rand1==tail && rand2==head))
: return head;
: return tail;
g**********g
发帖数: 18118
26
不要去这家。 活多久都是问题。
c********t
发帖数: 5706
27
我怎么感觉是3/4*3/4*(1-1/4*1/4)呢？

【在 b*****u 的大作中提到】
: 我的方法：
: rand1= rand;
: rand2= rand;
: rand3= rand;
: rand4= rand;
: if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
: return tail
: else
: return head;
: 3/4*3/4-1/4*1/4 = 1/2
e***s
发帖数: 799
28
但是这样会不会有机会永远不返回？

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
h******2
发帖数: 24
29
菜鸟请教各位大牛：
这个题目是不是不能精确得到1/2,只能逼近？
如果这样的话，可不可以写个random number generator(足够大)，然后如果是tail，
就看得到的random number，其中的1/3的结果返回true。
t*********r
发帖数: 845
30
第三题加个计数器，就可以了吧？

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
相关主题
● 一个面试题，不会做，大家看看● Epic 店面被考到coding的题目。。。（面经）
● 问个anagram的问题● 问个anagram的算法题
● 来个面经：unfair coin問題● 发一个fb面经
进入JobHunting版参与讨论
c********t
发帖数: 5706
31
Zkss

★ 发自iPhone App: ChineseWeb 7.8

【在 t*********r 的大作中提到】
: 第三题加个计数器，就可以了吧？
k***x
发帖数: 6799
m*****1
发帖数: 147
33
1.如何判断Anagram
2.一个file有1billion个数字，找到top15
3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
何利用原有方程，再写一个function，使得返回true和false的概率一样。。
这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
少了。。。真的希望顺利啊。。
P*******b
发帖数: 1001
34
这三题怎么做？

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
p*****2
发帖数: 21240
35
1. if rand==head return head
2. if rand==head return head
3. if rand==head && rand==head return head
else return tail
e***s
发帖数: 799
36
if(rand == head) return head;
if(rand == head) return head;
return tail;
就行了吧？ 1/4 + 1/4 = 1/2;

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
x*****0
发帖数: 452
37
mark
s*****l
发帖数: 10
38
这样返回tail的概率是(3/4)*(3/4) = 9/16吧？

【在 e***s 的大作中提到】
: if(rand == head) return head;
: if(rand == head) return head;
: return tail;
: 就行了吧？ 1/4 + 1/4 = 1/2;
j******2
发帖数: 362
39
请问面的哪个office?
thx

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
p*****2
发帖数: 21240
40

是

【在 s*****l 的大作中提到】
: 这样返回tail的概率是(3/4)*(3/4) = 9/16吧？
相关主题
● 发一个fb面经● 问一道twitter面试题
● 一道面试题● 明天电面，求建议
● List Flattening from book ● 一道rocket fuel的题
进入JobHunting版参与讨论
h***i
发帖数: 1970
41
1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
不对吧？

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
p*****2
发帖数: 21240
42

我得意思是可以继续下去，

【在 h***i 的大作中提到】
: 1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
: 不对吧？
h***i
发帖数: 1970
43
其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
的两种情况重新来。

【在 p*****2 的大作中提到】
:
: 我得意思是可以继续下去，
R******1
发帖数: 58
44
是，我也觉得不对

【在 h***i 的大作中提到】
: 1/4 + 3/4 * 1/4 + 3/4 * 3/4 * 1/4 * 1/4
: 不对吧？
h*****n
发帖数: 2872
45
额...会死循环吧...

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
h***i
发帖数: 1970
46
如果你不相信概率的话，这两种情况发生的可能性占6/16，循环个3次就差不多出来了。

【在 h*****n 的大作中提到】
: 额...会死循环吧...
f*******t
发帖数: 7549
47
可能性比较小

【在 h*****n 的大作中提到】
: 额...会死循环吧...
e***s
发帖数: 799
48
我错了，我是猪

【在 e***s 的大作中提到】
: if(rand == head) return head;
: if(rand == head) return head;
: return tail;
: 就行了吧？ 1/4 + 1/4 = 1/2;
p*****2
发帖数: 21240
49

这个不错。我的那个是继续扔，最后可以非常接近1/2。

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
p*****2
发帖数: 21240
50

如果继续扔，最后可以非常接近1/2。当然没有LS的方法好了。

【在 R******1 的大作中提到】
: 是，我也觉得不对
相关主题
● fb家面试题讨论● rand5 -> rand7的解法？
● LC装水容器题一定要O(nlogn)做法吗？● Bloomerg 还没放弃我。 电话二面经过。
● array 转换成 linkedlist, 在线等, 挺急的--help is still nee● google phone interview
进入JobHunting版参与讨论
h***i
发帖数: 1970
51
你这个需要算级数了。

【在 p*****2 的大作中提到】
:
: 如果继续扔，最后可以非常接近1/2。当然没有LS的方法好了。
b*****u
发帖数: 648
52
恩，优点是能解决任意的uneven coin
缺点是最坏情况无穷久

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
b*****u
发帖数: 648
53
我的方法：
rand1= rand;
rand2= rand;
rand3= rand;
rand4= rand;
if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
return tail
else
return head;
3/4*3/4-1/4*1/4 = 1/2

【在 p*****2 的大作中提到】
: 1. if rand==head return head
: 2. if rand==head return head
: 3. if rand==head && rand==head return head
: else return tail
p****e
发帖数: 3548
54
概率能相减的？这样可以不
if(rand() || rand())
return head;
return tail;

【在 b*****u 的大作中提到】
: 我的方法：
: rand1= rand;
: rand2= rand;
: rand3= rand;
: rand4= rand;
: if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
: return tail
: else
: return head;
: 3/4*3/4-1/4*1/4 = 1/2
d*s
发帖数: 699
55
FT/TF其余循环肯定没问题，楼上的概率不能相减，第一个为真第二个必然为真
i****n
发帖数: 109
56
这样可以不
rand1=rand();
rand2=rand();
if((rand1==head && rand2==tail)||(rand1==tail && rand2==head))
return head;
return tail;

【在 p****e 的大作中提到】
: 概率能相减的？这样可以不
: if(rand() || rand())
: return head;
: return tail;
B********t
发帖数: 147
57
这个不行吧。返回head的概率是6/16啊

【在 i****n 的大作中提到】
: 这样可以不
: rand1=rand();
: rand2=rand();
: if((rand1==head && rand2==tail)||(rand1==tail && rand2==head))
: return head;
: return tail;
g**********g
发帖数: 18118
58
不要去这家。 活多久都是问题。
c********t
发帖数: 5706
59
我怎么感觉是3/4*3/4*(1-1/4*1/4)呢？

【在 b*****u 的大作中提到】
: 我的方法：
: rand1= rand;
: rand2= rand;
: rand3= rand;
: rand4= rand;
: if ((rand1==tail&&rand2==tail)&&!(rand3==head &&rand4==head))
: return tail
: else
: return head;
: 3/4*3/4-1/4*1/4 = 1/2
e***s
发帖数: 799
60
但是这样会不会有机会永远不返回？

【在 h***i 的大作中提到】
: 其实可以这样，一个while loop,扔两次，如果是TF，就返回T,如果是FT，返回F，剩下
: 的两种情况重新来。
相关主题
● 问个anagram的题目啊● 问个anagram的问题
● 关于anagram的老题？● 来个面经：unfair coin問題
● 一个面试题，不会做，大家看看● Epic 店面被考到coding的题目。。。（面经）
进入JobHunting版参与讨论
h******2
发帖数: 24
61
菜鸟请教各位大牛：
这个题目是不是不能精确得到1/2,只能逼近？
如果这样的话，可不可以写个random number generator(足够大)，然后如果是tail，
就看得到的random number，其中的1/3的结果返回true。
t*********r
发帖数: 845
62
第三题加个计数器，就可以了吧？

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
c********t
发帖数: 5706
63
Zkss

★ 发自iPhone App: ChineseWeb 7.8

【在 t*********r 的大作中提到】
: 第三题加个计数器，就可以了吧？
k***x
发帖数: 6799
b*******l
发帖数: 590
65
我觉得第三题应该这么做：
首先扔2次不够，因为扔2次的话，组合和概率是这样的：
T T：1/16
T F: 3/16
F T: 3/16
F F: 9/16
没有一种组合可以得到8/16 = 1/2
所以必须扔3次，扔3次的组合和概率是这样的：
T T T: 1/64
T T F: 3/64
T F T: 3/64
T F F: 9/64
F T T: 3/64
F T F: 9/64
F F T: 9/64
F F F: 27/64
这里面有好几个组合可以得到32/64 = 1/2，最简单的是F T T + F F F. 最后我的解法
是：
result1 = rand();
result2 = rand();
result3 = rand();
if (!result1&&result2&&result3 || !result1&&!result2&&!result3)
return true;
else
return false;
扔4次也可以，但是没必要。
哪位大侠指教一下？
F****n
发帖数: 3271
66
public boolean flip() {// the given function}
public boolean adjustment() {
if (flip()) return true;
return Math.random() < 1/3 ? true : false;
}

【在 P*******b 的大作中提到】
: 这三题怎么做？
s*********s
发帖数: 318
67
这个好像是对的。

【在 b*******l 的大作中提到】
: 我觉得第三题应该这么做：
: 首先扔2次不够，因为扔2次的话，组合和概率是这样的：
: T T：1/16
: T F: 3/16
: F T: 3/16
: F F: 9/16
: 没有一种组合可以得到8/16 = 1/2
: 所以必须扔3次，扔3次的组合和概率是这样的：
: T T T: 1/64
: T T F: 3/64
r**h
发帖数: 1288
68
扔两次
如果HT则返回true，如果TH则返回false
其他reject

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
t*********h
发帖数: 941
69
硬凑啊 那如果p(h)=0.21454354 那你就很难凑出来了

【在 b*******l 的大作中提到】
: 我觉得第三题应该这么做：
: 首先扔2次不够，因为扔2次的话，组合和概率是这样的：
: T T：1/16
: T F: 3/16
: F T: 3/16
: F F: 9/16
: 没有一种组合可以得到8/16 = 1/2
: 所以必须扔3次，扔3次的组合和概率是这样的：
: T T T: 1/64
: T T F: 3/64
n**m
发帖数: 122
70
F T T + F F F = 30/64
1/2怎么跑出来的?

【在 b*******l 的大作中提到】
: 我觉得第三题应该这么做：
: 首先扔2次不够，因为扔2次的话，组合和概率是这样的：
: T T：1/16
: T F: 3/16
: F T: 3/16
: F F: 9/16
: 没有一种组合可以得到8/16 = 1/2
: 所以必须扔3次，扔3次的组合和概率是这样的：
: T T T: 1/64
: T T F: 3/64
相关主题
● Epic 店面被考到coding的题目。。。（面经）● 一道面试题
● 问个anagram的算法题● List Flattening from book
● 发一个fb面经● 问一道twitter面试题
进入JobHunting版参与讨论
u******g
发帖数: 89
71
p要是离0.5很远才会杯具，1/4这种任何practical的case下都是能接受的。。
b*******l
发帖数: 590
72
不好意思，我算错了，那看来只能接近1/2， 比如 T T T + F T T + F F F.
不管扔多少次，都只能无限的逼近1/2，扔的次数越多越逼近。

【在 n**m 的大作中提到】
: F T T + F F F = 30/64
: 1/2怎么跑出来的?
n**m
发帖数: 122
73
对，凑不出来 只能reject一部分结果
扔的次数越多 reject的越少

【在 b*******l 的大作中提到】
: 不好意思，我算错了，那看来只能接近1/2， 比如 T T T + F T T + F F F.
: 不管扔多少次，都只能无限的逼近1/2，扔的次数越多越逼近。
F****n
发帖数: 3271
74
public boolean adjustedRand() {
int n1 = count();
int n2 = count();
if (n1 > n2) return true;
else if (n1 < n2) return false;
return adjustedRand();
}
private int count() {
int n = 0;
while (!rand()) n++;
return n;
}
t*****h
发帖数: 137
75
有限次是不行的。看证明。
flip a coin n times, each outcome has a probability 3^i/4^n, where i is the
number of heads. We can prove that no combination of the outcomes will add
up to 1/2.
Proof by contradiction:
If we multiply all the probabilities by 4^n, and think them as outcome
frequencies(integers). Please note that all the frequencies but all tails
can be divided by 3. Now the question becomes whether you can find a
combination of outcomes which has an added frequency 4^n/2.
Assume there is a way to divide the outcomes into two groups A and B, such
that freq(A) = freq(B). Again assume all tails outcome is in A, it becomes
clear that freq(B) can be divided by 3, but not freq(A). It contradicts the
equality.
b*******l
发帖数: 590
76
正解！freq(B)肯定能被3整除，但是 4^n/2 一定是2的power，2的power绝对不可能被3
整除。

the

【在 t*****h 的大作中提到】
: 有限次是不行的。看证明。
: flip a coin n times, each outcome has a probability 3^i/4^n, where i is the
: number of heads. We can prove that no combination of the outcomes will add
: up to 1/2.
: Proof by contradiction:
: If we multiply all the probabilities by 4^n, and think them as outcome
: frequencies(integers). Please note that all the frequencies but all tails
: can be divided by 3. Now the question becomes whether you can find a
: combination of outcomes which has an added frequency 4^n/2.
: Assume there is a way to divide the outcomes into two groups A and B, such
i***1
发帖数: 668
77
都是书呆子。
if (rand==H)
return true
else
if (rand==H) return true
end if
1/4+1/3*3/4=1/2.
也就是初中数学题。
n**m
发帖数: 122
78
书呆子们都理解不了你这1/3从哪来的 lol

【在 i***1 的大作中提到】
: 都是书呆子。
: if (rand==H)
: return true
: else
: if (rand==H) return true
: end if
: 1/4+1/3*3/4=1/2.
: 也就是初中数学题。
i***1
发帖数: 668
79
第一题烂大街。
第二题divide and conq.
j********x
发帖数: 2330
80
既然你都说是书呆子了，对应的，你也配得上智障这个称呼了。。。

【在 i***1 的大作中提到】
: 都是书呆子。
: if (rand==H)
: return true
: else
: if (rand==H) return true
: end if
: 1/4+1/3*3/4=1/2.
: 也就是初中数学题。
相关主题
● 明天电面，求建议● LC装水容器题一定要O(nlogn)做法吗？
● 一道rocket fuel的题● array 转换成 linkedlist, 在线等, 挺急的--help is still nee
● fb家面试题讨论● rand5 -> rand7的解法？
进入JobHunting版参与讨论
i***1
发帖数: 668
81
loser, 你看不懂。你也就是个ASSHOL....

【在 j********x 的大作中提到】
: 既然你都说是书呆子了，对应的，你也配得上智障这个称呼了。。。
l*********y
发帖数: 1431
82
扔两次为啥不够呢？
r1=rand();
r2=rand();
if(r1==h&&r2=h)
return h;
else
return t;
p(r1=h)=p(r1=t)=p(r2=h)=p(r2=t)=1/2
而且两次事件相互独立
p(r1=h&&r2=h)=p(r1)*p(r2)=1/4
m***n
发帖数: 62
83
能问问什么position吗？
m***n
发帖数: 62
84
第二题怎么做啊？

【在 m*****1 的大作中提到】
: 1.如何判断Anagram
: 2.一个file有1billion个数字，找到top15
: 3.有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返
: 回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如
: 何利用原有方程，再写一个function，使得返回true和false的概率一样。。
: 这个面试真是纠结，本来约星期一，等了一个小时没打来，今天再面，面试官说没找到
: 电话号码= =Groupon的电话估计质量有问题。。今天断线了三次。。最近题目做得真不
: 少了。。。真的希望顺利啊。。
B**********2
发帖数: 923
85
用Quick-Select

【在 m***n 的大作中提到】
: 第二题怎么做啊？
n**m
发帖数: 122
86
input output颠倒了?

【在 l*********y 的大作中提到】
: 扔两次为啥不够呢？
: r1=rand();
: r2=rand();
: if(r1==h&&r2=h)
: return h;
: else
: return t;
: p(r1=h)=p(r1=t)=p(r2=h)=p(r2=t)=1/2
: 而且两次事件相互独立
: p(r1=h&&r2=h)=p(r1)*p(r2)=1/4
l*****a
发帖数: 14598
87
为什么不问找最大的15个还是出现频率最高的15个

【在 m***n 的大作中提到】
: 第二题怎么做啊？
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 问个anagram的题目啊● 一道面试题
● 关于anagram的老题？● List Flattening from book
● 一个面试题，不会做，大家看看● 问一道twitter面试题
● 问个anagram的问题● 明天电面，求建议
● 来个面经：unfair coin問題● 一道rocket fuel的题
● Epic 店面被考到coding的题目。。。（面经）● fb家面试题讨论
● 问个anagram的算法题● LC装水容器题一定要O(nlogn)做法吗？
● 发一个fb面经● array 转换成 linkedlist, 在线等, 挺急的--help is still nee
相关话题的讨论汇总
话题: rand话题: head话题: return话题: tail话题: rand2

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑