z*****n
发帖数: 7639 | 1 你搞清楚没有？你这25个格子（值）是平均分布的吗？
你要是用rand5 by rand5，我告诉你，不行。
想清楚再来，ok？最好拿出代码。动嘴皮子最简单了，
码工们都不屑。 |
|
z*****n
发帖数: 7639 | 2 嗯, 回头仔细看了看, 是对的.
不过这个的复杂度貌似并不比我说的那个解法低。
至少那个解法不用建表查找。
解法1：
#define rand5() rand()%5+1
int rand4(){
int a;
do{
a=rand5();
}while(a==5);
return a;
}
int rand8(){
if(rand4()%2) return rand4();
else return 4+rand4();
} |
|
y****n
发帖数: 60 | 3 给的答案是：
int num = 5*(rand5()-1) + (rand5()-1);
if(num<21) return ( num%7+1);
不明白为什么第一行代码要两个相加？前面一个不就是0 到20 的uniform
distribution 了吗？两个random number 加之后并不是uniform 的distribution 啊？
谢谢。 |
|
A**u
发帖数: 2458 | 4 5*(rand5()-1) + (rand5()-1)
可以这么理解，
从0,1,2,4,取两个随机数A,B
组成AB, 以5为base. 则数值为 A * 5 + B.
所以 00,01,02,03,04, 10,11,12,13,14.....,40,41,42,43,44 都是1/(25)概率
对应于0,1, 2, 3, 4, 5, 6, 7, 8, 9........ 20,21,22,23,24都是1/25概率
发生.
取余只不过是为了增加效率 |
|
m*****n
发帖数: 5245 | 5 ☆─────────────────────────────────────☆
howiknow (dd) 于 (Sun May 3 01:21:24 2009) 提到:
how to do this?
thanks.
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Sun May 3 01:31:20 2009) 提到:
不行的
☆─────────────────────────────────────☆
hypocenter (振源) 于 (Sun May 3 01:33:23 2009) 提到:
这样不是平均分布的
☆─────────────────────────────────────☆
shuiguan (guanshui) 于 (Sun May 3 02:46:52 2009) 提到:
no can do
☆─────────────────────────────────────☆
algorithmics (沙盘推演) 于 (Sun Ma |
|
s*****i
发帖数: 355 | 6 a = rand31();
b = rand31();
c = (a-1)*31 + (b-1); //uniform distributed between 0 and 960
return c%32;
rand5 -> rand7 照葫芦画瓢的 |
|
o****d
发帖数: 2835 | 7 思路跟 rand5 rand7 一样
rand31() 产生每个数x1,x2...的概率是 1/2^31
所以产生一对(x1,x2)的概率就是 1/2^62
因为只需要2^32个数 于是将所有pair 每2^30形成一组就是了
于是就有了2^32个组，每组代表一个数就是了
具体实现上当然不需要用乘 那太大了
看x2的某一位（比如最高位）是0 还是1 就可以了
所以最终的答案就是从x2里面拿某一位插入到x1中的某一位就是了 |
|
P*******e
发帖数: 1353 | 8 general hiring，PhD，看大家讨论收获不说，也简单汇报一下。
坐了一晚上飞机题记不全了，简要说几个吧，老题比较多
1. implement queue using two stack
2. design an algorithm to return top 10 seached location on google map
3. rand5 -> rand7
4. binary search找最小测试序列用来reproduce runtime crash
5. biased coin toss
6. how to create password with a random password generate and a list of forb
idden strngs
7. if you can jump one or two stairs in one time, how many different ways to
climb N stairs. |
|
r****o
发帖数: 1950 | 9 一直没明白rand5()是1-5还是0-5还是0-4? |
|
p******y
发帖数: 708 | 10 . rand5 -> rand7
有一种说法是：
产生一个5进制数，产生的方法就是用random5()-1产生该5进制数的各位权值，然后将
此数转换为10进制数对7求余。
不知道这种思路对不对 |
|
|
m*****k
发帖数: 64 | 12 我看了careercup,但是还不太理解，谁能解释一下么？ |
|
m*****k
发帖数: 64 | 13 if (num < 21) return num % 7;
前21个也是平均分布,那么我取num<14也可以么？
7 |
|
|
x*****p
发帖数: 1707 | 15 5*rand5 mod 7 can only generate 0, 5, 3, 1, 6 and can not generate 2,4. |
|
x*****p
发帖数: 1707 | 16 So if rand5 is iid, then it is impossible to generate rand7 also with iid. |
|
t******h
发帖数: 37 | 17 yeah,
it's easy mistake
rand(5)*7+rand(5) distributes different than rand(5)+rand(5)+...(
rand5) //8times |
|
x****3
发帖数: 62 | 18 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 19 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
d********t
发帖数: 9628 | 20 用rand5()产生rand7()，有大侠能指教的吗？ |
|
s********r
发帖数: 277 | 21 我贴下面经吧。
两轮电面.
第一轮问了下怎么实现，query auto completion。 我说trie，他然后问了下trie 很
大比较大的情况下怎么scale
第二轮问了题。
怎么用rand5是实现rand7
onsite问的题目都很不是很难。
intersection of two arrays.
maximum sub array.
intersection of two sorted arrays. how to optimize when two array size are
different.
reservoir sampling
detect number of duplicates in bst
最后一道
http://www.mitbbs.com/article/JobHunting/32061411_3.html |
|
p***s
发帖数: 78 | 22 detect number of duplicates in bst
duplicates in array is nlogn （不用hash), 这个怎么更快？
标 题: Re: 明天onsite，求下bless了
发信站: BBS 未名空间站 (Tue Jun 12 01:19:01 2012, 美东)
我贴下面经吧。
两轮电面.
第一轮问了下怎么实现，query auto completion。 我说trie，他然后问了下trie 很
大比较大的情况下怎么scale
第二轮问了题。
怎么用rand5是实现rand7
onsite问的题目都很不是很难。
intersection of two arrays.
maximum sub array.
intersection of two sorted arrays. how to optimize when two array size are
different.
reservoir sampling
detect number of duplicates in bst
最后一道
http://www.mitbbs.com/ar... 阅读全帖 |
|
N**N
发帖数: 1713 | 23 那就是leetcode上的答案，其实不难：
用两个rand5()得到一个范围更大的均匀分布，然后只取出其中1-7的部分就行，或者在
这个范围取出7的整数倍个 |
|
s**********y
发帖数: 33 | 24 11月27面的，今天follow up说还在under review，估计是备胎了... 求版上各位不打
算去A的大牛（kindle组）据了offer，也许还有希望。觉得据人不用托这么久吧
签了NDA, 可能不够详细，如果被潜水的interviewer看到了，请多多包涵。
5轮：
1，第一轮，巨紧张，国人小哥，问了问背景，出了个半设计半coding的题，不是很方
便说，但是不难，自己紧张+实力不够吧，做得磕磕绊绊，小哥不是特别满意觉得，但
还算完成了，中间讨论了一些排序算法的复杂度什么的。面完心灰意冷。
2，第二轮，老印，人很nice，直接出题，word count，然后follow up 词频统计，再
follow up top 高频词，写了前两个，top k 那个跟他说用堆，他说不用写了，讲了讲
复杂度，词频统计那个用了hashtable，他问还有别的方法么，说了trie，比较了复杂
度，很顺。
3，第三论，老美，设计题，大概就是个公交系统，如何从A到B，估算时间，感觉设计
题就是一边写，他一边问，加条件，比如bus坏了，遇到traffic等等，中间穿插oo概念
。然后coding... 阅读全帖 |
|
n****r
发帖数: 120 | 25 有三个问题：
第一个问题：题目要求是int r7,也就是说要求等概率随机产生[1..7]之间的一个数
第二个是你的解法：
说白了，就是 rand7 = 6*((rand5 - 1)/4)+1,这里面涉及两个问题，如果你用int来做
这个计算，最后结果将是1或者7。若用double来处理，应该是可以返回[1..7]之间的数
，但是不是等概率的。原因是因为数学运算的时候无法避免精度上的变化，这个变化会
影响到随机性。我试了一下，这个算法好像产生3这个数的概率奇低（如果不是不能的
话）
第三个是你提到的Career Up的解法
while (r >= 21); //这里应该是 while (r>21); |
|
l***8
发帖数: 149 | 26 random integers, not real numbers |
|
y****n
发帖数: 743 | 27 你的算法返回2的概率要远大于返回6的概率。
[0,1,2,3,4] + [0,1,2]
有三种可能返回2，一种可能返回6 |
|
t****t
发帖数: 6806 | 28 reject sampling有一个无限循环不是吗?当然作为一个可操作的算法, 这个循环真正变
成无限的机会是无限小. |
|
h***i
发帖数: 1970 | 29 是的，被reject的sample，需要从新来，是loop. |
|
r*********n
发帖数: 4553 | 30 a simpler version of this problem could be using a fair coin to simulate an
unfair coin with probability p |
|
r*********n
发帖数: 4553 | 31 不是光数几种可能就行了，还要看没中可能出现的概率啊
你想想出现6的概率是多少？如果不是1/7，那么答案就是错的。 |
|
h***t
发帖数: 2540 | 32 Then what if we generalize this question
given positive integers n>m,
how to generate randn() from randm() and vice versa |
|
r*********n
发帖数: 4553 | 33 其实有限次方法也不是不可行的，因为电脑都是finite precision。
比如我给的方法，1/7用base 5来表示，小数点后面有无穷循环位，但是实际上考虑10
位就足够了，因为5^(-10)已经很小了，如果觉得不够就用20位，30位。
这种方法模拟出来的rand7()和真正的rand7()在用起来是没有差别的，因为在rand7()
重复之前，你的counter已经溢出了。 |
|
w********p
发帖数: 948 | 34 你的解释有给我启发。
现在想请问下如果题目给的是 用randM() 实现 randN() M
思路改是咋样的？ 是不是 M * randM() + randM() ; drop 掉 最后几个( M*M %N)
cases. |
|
|
y****n
发帖数: 743 | 36 这个算法不对，Rand7()的值范围应该是[0..6]。
你的算法有可能返回7。 |
|
|
c********p
发帖数: 1969 | 38 我就没看懂阿。。。
面试会出么？
我不想看了。。。 |
|
|
|
c********p
发帖数: 1969 | 41 还是得明白阿？
我智商越来越低了。。。
哎呀呀 |
|
c********p
发帖数: 1969 | 42 能给解释解释cc150上那个答案么？就是能work的第一个，第一个就没看懂，后边的就
没看了。。。 |
|
r*******e
发帖数: 7583 | 43 前者能产生1-25的均匀分布，后者只能等概率产生6 12 18 24 30 |
|
|
|
|
z****e
发帖数: 54598 | 47 这种题我很早以前总结过哈
可以暴力构造pool
只要给我一个p和一个q，p+q=1就行
比如4以内的整数
pqqq0
qpqq1
qqpq2
qqqp3
搞定
至于生成的其它组合，全部丢掉 |
|
|
|
b***e
发帖数: 1419 | 50 那是将近十年前，老印电面问我这个题，我当时跟丫说我不会。丫居然说给我时间让我
再想想。我还就想了个也还行的答案出来。那老印是我那份工作里唯一一个觉得还行的
老印，后来自己搞startup去了。 |
|
