P*******e
发帖数: 1353 | 1 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. |
g*******y
发帖数: 1930 | 2 好像都是比较常规的google题目，赞分享！
祝楼主好运！ |
H*M
发帖数: 1268 | 3 第四个是什么意思?楼主能把题意说清楚下吗?
【在 g*******y 的大作中提到】
: 好像都是比较常规的google题目，赞分享！
: 祝楼主好运！
|
k***e
发帖数: 556 | 4 good luck!
应该不错吧
forb
to
【在 P*******e 的大作中提到】
: 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
|
r****o
发帖数: 1950 | 5 第2个和第5个怎么回答比较好？
什么是runtime crash?
第5个是说怎么产生0-1随机数，但是不是50%-50%的概率吗？
forb
to
【在 P*******e 的大作中提到】
: 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
|
P*******e
发帖数: 1353 | 6 就是你测试一个程序，测试序列是t0, t1, t2, ... tn，然后crash了，用的不同的inp
ut，单独运行tn是没问题的，要你找到最大的k满足tk, t(k+1)...tn会crash
【在 H*M 的大作中提到】
: 第四个是什么意思?楼主能把题意说清楚下吗?
|
S******A
发帖数: 1002 | 7 7. is it similar to Fib series?
d1=1;
d2=2;
f(n) = f(n-1)+f(n-2)
of forb
ways to
【在 P*******e 的大作中提到】
: 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
|
P*******e
发帖数: 1353 | |
P*******e
发帖数: 1353 | 9 yes, that is the answer.
【在 S******A 的大作中提到】
: 7. is it similar to Fib series?
: d1=1;
: d2=2;
: f(n) = f(n-1)+f(n-2)
:
: of forb
: ways to
|
r****o
发帖数: 1950 | 10 那这个概率是指定的吗？比如说30%-70%?
【在 P*******e 的大作中提到】
: nod
|
|
|
r****o
发帖数: 1950 | 11 top 10 searched location是什么意思啊？
forb
to
【在 P*******e 的大作中提到】
: 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
|
c****s
发帖数: 241 | 12 这些题都要现场写算法吗？还是只要说说idea就行了？
forb
to
【在 P*******e 的大作中提到】
: 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
|
S******A
发帖数: 1002 | 13 肯定要写吧
【在 c****s 的大作中提到】
: 这些题都要现场写算法吗？还是只要说说idea就行了？
:
: forb
: to
|
P*******e
发帖数: 1353 | 14 嗯，大部分都是要写的
【在 S******A 的大作中提到】
: 肯定要写吧
|
P*******e
发帖数: 1353 | 15 对阿，比如bool bias(double p)
【在 r****o 的大作中提到】
: 那这个概率是指定的吗？比如说30%-70%?
|
P*******e
发帖数: 1353 | 16 就是搜索次数最多的的地方，他说地方就是经度纬度的pair
【在 r****o 的大作中提到】
: top 10 searched location是什么意思啊？
:
: forb
: to
|
c****s
发帖数: 241 | 17 我看的题比较少，所以趁着大牛门都在，想验证一下我的几个解法是不是正确。
1)
class queue{
public:
void push(int val){
inStack.push(val);
}
int pop(){
if( outStack.isEmpty() ){
while( !inStack.isEmpty() )
outStack.push(inStack.pop());
}
return outStack.pop();
}
bool isEmpty(){
return inStack.isEmpty() && outStack.isEmpty();
}
private:
Stack inStack;
Stack outStack;
}
2) maitain one hashtable and one heap. The hashtable sto
【在 P*******e 的大作中提到】
: 就是搜索次数最多的的地方，他说地方就是经度纬度的pair
|
w**********8
发帖数: 121 | 18 6. how to create password with a random password generate and a list of forb
idden strngs
how is this solution?
build a sufix tree using forbidden strings and then check the the randon
password is in the tree or not |
w**********8
发帖数: 121 | 19 6. how to create password with a random password generate and a list of forb
idden strngs
how is this solution?
build a sufix tree using forbidden strings and then check the the randon
password is in the tree or not |
P*******e
发帖数: 1353 | 20 这题没让写code，你说的办法可以，后来他说限制空间的使用，我就说用bloom filter
forb
【在 w**********8 的大作中提到】
: 6. how to create password with a random password generate and a list of forb
: idden strngs
: how is this solution?
: build a sufix tree using forbidden strings and then check the the randon
: password is in the tree or not
|
|
|
w**********8
发帖数: 121 | 21 5 is too difficult. Its solution was published as a research paper. |
P*******e
发帖数: 1353 | 22 我觉得你写的对吧，另外就是可以考虑一下是不是full
loc
这个没让写code，他一直强调地址有很多很多，不知道答案是啥
这个似乎不对吧，你搜一下，网上有答案的 |
P*******e
发帖数: 1353 | 23 really? any citation or link?
【在 w**********8 的大作中提到】
: 5 is too difficult. Its solution was published as a research paper.
|
c***y
发帖数: 560 | 24 for (2), u can split the data to different sets, and get top 10 for each of
them, then merge/heap sort
another idea is to use map-reduce if parallel machines available
【在 P*******e 的大作中提到】
: 我觉得你写的对吧，另外就是可以考虑一下是不是full
: loc
: 这个没让写code，他一直强调地址有很多很多，不知道答案是啥
: 这个似乎不对吧，你搜一下，网上有答案的
|
m*****f
发帖数: 1243 | |
c****s
发帖数: 241 | 26 3)那个我错了，多谢，多谢。正确的应该是这个吧：
rand7(){
int i;
do{
i=(rand5()-1)*5+rand5();
} while(i>21);
return i%7;
}
【在 P*******e 的大作中提到】
: 我觉得你写的对吧，另外就是可以考虑一下是不是full
: loc
: 这个没让写code，他一直强调地址有很多很多，不知道答案是啥
: 这个似乎不对吧，你搜一下，网上有答案的
|
s*****i
发帖数: 355 | 27 这是对的，不过要搞清楚为什么
【在 c****s 的大作中提到】
: 3)那个我错了，多谢，多谢。正确的应该是这个吧：
: rand7(){
: int i;
: do{
: i=(rand5()-1)*5+rand5();
: } while(i>21);
: return i%7;
: }
|
c****s
发帖数: 241 | 28 说的是，多谢
【在 s*****i 的大作中提到】
: 这是对的，不过要搞清楚为什么
|
S******A
发帖数: 1002 | 29 ..
should return (i%7 +1)
【在 s*****i 的大作中提到】
: 这是对的，不过要搞清楚为什么
|
w**********8
发帖数: 121 | 30 http://delivery.acm.org/10.1145/1080000/1070587/p1079-pae.pdf?key1=1070587&key2=1367507621&coll=GUIDE&dl=GUIDE&CFID=79356995&CFTOKEN=68901377
but i have a simple solution. I can prove it is right.
if it shows head, odd round, let head = 0;even round, let head = 1.
v.v.
proof: for 0s, we have 1/2 * p + 1/2 *q = 1/2
for 1s, same thing.
【在 P*******e 的大作中提到】
: really? any citation or link?
|
|
|
c****s
发帖数: 241 | 31 是啊，是啊。这个也没有注意到。多谢指点
【在 S******A 的大作中提到】
: ..
: should return (i%7 +1)
|
c****s
发帖数: 241 | 32 他是说我最后return的时候忘了+1了
【在 s*****i 的大作中提到】
: 这是对的，不过要搞清楚为什么
|
s*****i
发帖数: 355 | 33 555，我真瞎，怪不得要move on了
【在 c****s 的大作中提到】
: 他是说我最后return的时候忘了+1了
|
P*******e
发帖数: 1353 | 34 我是你这么回答的，但是那个面试的似乎不是很满意，那哥们专门做google earth的。
。。
of
【在 c***y 的大作中提到】
: for (2), u can split the data to different sets, and get top 10 for each of
: them, then merge/heap sort
: another idea is to use map-reduce if parallel machines available
|
P*******e
发帖数: 1353 | 35 我说那题是有一个好的coin，让你模拟一个bias的
你说的好像是相反的方向
【在 w**********8 的大作中提到】
: http://delivery.acm.org/10.1145/1080000/1070587/p1079-pae.pdf?key1=1070587&key2=1367507621&coll=GUIDE&dl=GUIDE&CFID=79356995&CFTOKEN=68901377
: but i have a simple solution. I can prove it is right.
: if it shows head, odd round, let head = 0;even round, let head = 1.
: v.v.
: proof: for 0s, we have 1/2 * p + 1/2 *q = 1/2
: for 1s, same thing.
|
s*****i
发帖数: 355 | 36 对任意给定概率p (p<0.5)，找到2p的irreducible fraction. 找即约分数可以一个
while循环每次乘以10再mod 1，直到余数为零为止。然后找分子分母的最小公倍数
let w=2p=A/B, then
Random r = new Random();
toss = Math.random();
if ( (r.nextInt(B) % B < A) && (toss < 0.5) )
return true;
else
return false;
【在 P*******e 的大作中提到】
: 我说那题是有一个好的coin，让你模拟一个bias的
: 你说的好像是相反的方向
|
r****o
发帖数: 1950 | 37 一直没明白rand5()是1-5还是0-5还是0-4?
【在 c****s 的大作中提到】
: 3)那个我错了，多谢，多谢。正确的应该是这个吧：
: rand7(){
: int i;
: do{
: i=(rand5()-1)*5+rand5();
: } while(i>21);
: return i%7;
: }
|
s*****i
发帖数: 355 | 38 1-5
【在 r****o 的大作中提到】
: 一直没明白rand5()是1-5还是0-5还是0-4?
|
d********e
发帖数: 132 | |
s*****i
发帖数: 355 | 40 DP
【在 d********e 的大作中提到】
: 爬梯子的那道题应该怎么分析？
|
|
|
n******r
发帖数: 1247 | 41 3 is not right
【在 c****s 的大作中提到】
: 我看的题比较少，所以趁着大牛门都在，想验证一下我的几个解法是不是正确。
: 1)
: class queue{
: public:
: void push(int val){
: inStack.push(val);
: }
: int pop(){
: if( outStack.isEmpty() ){
: while( !inStack.isEmpty() )
|
r****o
发帖数: 1950 | 42 那个Math.random()是什么意思阿
【在 s*****i 的大作中提到】
: 对任意给定概率p (p<0.5)，找到2p的irreducible fraction. 找即约分数可以一个
: while循环每次乘以10再mod 1，直到余数为零为止。然后找分子分母的最小公倍数
: let w=2p=A/B, then
: Random r = new Random();
: toss = Math.random();
: if ( (r.nextInt(B) % B < A) && (toss < 0.5) )
: return true;
: else
: return false;
:
|
s*****i
发帖数: 355 | 43 java api，返回0-1之间伪随机数。就当是toss a fair coin
【在 r****o 的大作中提到】
: 那个Math.random()是什么意思阿
|
w*********l
发帖数: 1337 | 44 呵呵，你上这儿来发面经来了？
bloom filter比那个tree好多了。这些题估计让你答问题都不大。祝拿offer。
filter
【在 P*******e 的大作中提到】
: 这题没让写code，你说的办法可以，后来他说限制空间的使用，我就说用bloom filter
:
: forb
|
h**k
发帖数: 3368 | 45 我觉得原题是以各50%的概率产生一个0或者1的随机数生成器，现在让你用此生成一个
任意的概率。
我的基本思路是连续生成n个随机数，那么任意一个指定的序列出现的概率是1/(2^n)。
比如n=3，那么000出现的概率是0.125。那么如果我们想生成0的概率为0.25，1的概率
为0.75，我们可以观察生成的序列，如果序列是000或者001，则输出0，其它序列则输
出1。
如果n足够大，理论上我们可以输出任何精度的概率。
有更好的解法么？
【在 s*****i 的大作中提到】
: java api，返回0-1之间伪随机数。就当是toss a fair coin
|
s*****i
发帖数: 355 | 46 是啊，我只是用这个API来产生0或1而已。后面有个是不是大于0.5的判断就是做这个事的
你这个idea很好，但是要写成代码，也一样要判断什么时候输出0，什么时候输出1.这
才是关键
【在 h**k 的大作中提到】
: 我觉得原题是以各50%的概率产生一个0或者1的随机数生成器，现在让你用此生成一个
: 任意的概率。
: 我的基本思路是连续生成n个随机数，那么任意一个指定的序列出现的概率是1/(2^n)。
: 比如n=3，那么000出现的概率是0.125。那么如果我们想生成0的概率为0.25，1的概率
: 为0.75，我们可以观察生成的序列，如果序列是000或者001，则输出0，其它序列则输
: 出1。
: 如果n足够大，理论上我们可以输出任何精度的概率。
: 有更好的解法么？
|
r****o
发帖数: 1950 | 47 请问这个r.nextInt(B)是什么意思
原题中的随机函数只能返回0或1吧。
【在 s*****i 的大作中提到】
: 对任意给定概率p (p<0.5)，找到2p的irreducible fraction. 找即约分数可以一个
: while循环每次乘以10再mod 1，直到余数为零为止。然后找分子分母的最小公倍数
: let w=2p=A/B, then
: Random r = new Random();
: toss = Math.random();
: if ( (r.nextInt(B) % B < A) && (toss < 0.5) )
: return true;
: else
: return false;
:
|
b****g
发帖数: 570 | 48 Good luck呀。
拿到google 的on-site，牛人！
forb
to
【在 P*******e 的大作中提到】
: 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
|
r****o
发帖数: 1950 | 49 能不能就让random()函数跑B次，如果返回A次1的话，就返回1，否则返回0。
这种方法可以吗？
【在 r****o 的大作中提到】
: 请问这个r.nextInt(B)是什么意思
: 原题中的随机函数只能返回0或1吧。
|
s*****i
发帖数: 355 | 50 应该是小于等于A次1
【在 r****o 的大作中提到】
: 能不能就让random()函数跑B次，如果返回A次1的话，就返回1，否则返回0。
: 这种方法可以吗？
|
|
|
r****o
发帖数: 1950 | 51 对对，呵呵。
【在 s*****i 的大作中提到】
: 应该是小于等于A次1
|
s*****i
发帖数: 355 | 52 你这样应该是对的，如果只给了一个函数，随机返回0或1的话。
我的代码里面用了java api函数， nextInt(B)是随机返回 [0, B) 之间任意整数。
【在 r****o 的大作中提到】
: 能不能就让random()函数跑B次，如果返回A次1的话，就返回1，否则返回0。
: 这种方法可以吗？
|
a*u
发帖数: 2334 | 53 谁解释一下为什么是这个吧？
rand(7) = rand(5) + (rand(5)+rand(5)>5? 1:2)
行吗？
【在 c****s 的大作中提到】
: 3)那个我错了，多谢，多谢。正确的应该是这个吧：
: rand7(){
: int i;
: do{
: i=(rand5()-1)*5+rand5();
: } while(i>21);
: return i%7;
: }
|
c****s
发帖数: 241 | 54 题目是要求平均分别。你这个最后只能有2,3,4,5,6,7。而且2，7被hit的概率要小于其
他数字。
【在 a*u 的大作中提到】
: 谁解释一下为什么是这个吧？
: rand(7) = rand(5) + (rand(5)+rand(5)>5? 1:2)
: 行吗？
|
a*u
发帖数: 2334 | 55 为什么是
do{
i=(rand5()-1)*5+rand5();
} while(i>21);
?
我那个可以再加一个Rand(5)，然后1-5，+0；6-10，+1； 11-15， +2 也是平均的
【在 c****s 的大作中提到】
: 题目是要求平均分别。你这个最后只能有2,3,4,5,6,7。而且2，7被hit的概率要小于其
: 他数字。
|
c****s
发帖数: 241 | 56 精华区里面有讨论，给你个链接，你自己去看吧。
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/mianshiexp/line14/M.116329
1981.m0/%5B%BA%CF%BC%AF%5D+%C4%C7%B8%F6Google+random+generate+1-7
【在 a*u 的大作中提到】
: 为什么是
: do{
: i=(rand5()-1)*5+rand5();
: } while(i>21);
: ?
: 我那个可以再加一个Rand(5)，然后1-5，+0；6-10，+1； 11-15， +2 也是平均的
|
a*u
发帖数: 2334 | 57 got it, thank you.
【在 c****s 的大作中提到】
: 精华区里面有讨论，给你个链接，你自己去看吧。
: http://www.mitbbs.com/bbsann2/life.faq/JobHunting/mianshiexp/line14/M.116329
: 1981.m0/%5B%BA%CF%BC%AF%5D+%C4%C7%B8%F6Google+random+generate+1-7
|
h**k
发帖数: 3368 | 58 小于等于A的概率是
C(B,0)*0.5^B+...+C(B,A)*0.5^B
（这里C(B,k)是指从B个元素中任意取k个元素的组合数)
你让这个值等于指定概率p，恐怕不容易求出A和B的值吧？
【在 r****o 的大作中提到】
: 能不能就让random()函数跑B次，如果返回A次1的话，就返回1，否则返回0。
: 这种方法可以吗？
|
c******f
发帖数: 2144 | |
p******y
发帖数: 708 | 60 . rand5 -> rand7
有一种说法是：
产生一个5进制数，产生的方法就是用random5()-1产生该5进制数的各位权值，然后将
此数转换为10进制数对7求余。
不知道这种思路对不对 |
|
|
h*h
发帖数: 23 | 61 还是不太明白这个. loop里面为什么要乘5呢? 乘4行不行呢? 比如把loop改成下面这样:
i=(rand5()-1)*4+rand5();
i应该是1 - 21之间的数, do-while loop的目的不就是找一个1 - 21 之间的数吗? 这
样也不需要do-while loop了.
请牛人指教.
谢谢
【在 c****s 的大作中提到】
: 3)那个我错了，多谢，多谢。正确的应该是这个吧：
: rand7(){
: int i;
: do{
: i=(rand5()-1)*5+rand5();
: } while(i>21);
: return i%7;
: }
|
c******f
发帖数: 2144 | |
m*****g
发帖数: 226 | 63 我怎么记得是
rand7()
{
i= rand5()*rand5();
if(i<=21) return i%7+1;
else return rand7();
}
样:
【在 h*h 的大作中提到】
: 还是不太明白这个. loop里面为什么要乘5呢? 乘4行不行呢? 比如把loop改成下面这样:
: i=(rand5()-1)*4+rand5();
: i应该是1 - 21之间的数, do-while loop的目的不就是找一个1 - 21 之间的数吗? 这
: 样也不需要do-while loop了.
: 请牛人指教.
: 谢谢
|
l*y
发帖数: 21010 | 64 你这21个数概率不均等啊
比如5就比4的概率高
样:
【在 h*h 的大作中提到】
: 还是不太明白这个. loop里面为什么要乘5呢? 乘4行不行呢? 比如把loop改成下面这样:
: i=(rand5()-1)*4+rand5();
: i应该是1 - 21之间的数, do-while loop的目的不就是找一个1 - 21 之间的数吗? 这
: 样也不需要do-while loop了.
: 请牛人指教.
: 谢谢
|
a********u
发帖数: 4 | 65 Two steps:
1. make rand(25) as 5 * rand(5) + rand(5) - 5
2. call rand(25) till the value falls within 1..7
Original problem makes sense if rand(5) returns evenly distributed integers
(1..5) and the goal is to write a function with the same distribution. There
can be a cave-in of pseudorandom sequences, so the assumption is that we
work with a "real random values generator". |
