M********5
发帖数: 715 | 1 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
准备的还是不够，希望能对其他找工作的人有帮助。
一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
另外两道题
1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
)”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
2 第二道题，以1/(2^n)的概率返回1，其它的时候返回0，题目应该假设有个函数可以
生成1或者0，以1/2的概率
我当时想了一下，最intuitive的想法是先产生一个数，num = 1<
(double)num * rand();
当时写的时候没有把num转化成double，这是一个bug，并且我觉得这个bug其实是不
应该的，也是个很关键的bug。 然后他不满意，我也知道，我说n很大的时候num会
overflow，这个时候有两种解决方式，一种是用BigInt，还有一种用divide and
conque，举了个例子，如果int是16位的话，那么n大于16的时候，就不断地divide and
conque，直到小于16为止。
然后我第二天把这个问题想了一想，我现在来讲，比较好的解决方法是：
int probability(int n){
std::vector vec_n;
int i;
for(i=0; i
int t = fun_0_1();
vec_n.push_back(t);
}
if( vec_n[0] == 1 )
for(i=1; i
if( vec_n[i]==1 )
break;
}
if( i==n )
return 1;
else
return 0;
}
说实话，题目不难，但是第一题，我真是没看出来他想要什么样的答案，并且最后他要
的这个答案的方向，我觉得很奇怪，其实我最后给他的答案跟他这个意思也很相近了，
但是他觉得这不是他想要的，我也没有办法。
第二题，说实在的，我觉得divide and conquer是可行的，并且这个方法的效率也不差
，但是我觉得最后的code写得还是很不完美的，有两个地方我做的不好，一个是不能假
设int为16位，可以用sizeof函数算出来，第二个我divide and conquer的时候没有考
虑到奇数偶数的问题，这个应该是考虑到的，不然没有办法保证产生的概率是1/(2^n)
不过其实我依然觉得，这个题目不难，但是也不像想象中的那么简单，主要是这些并不
是常见的算法和数据结构的题目，没有碰到的时候，你一下子能不能有最好的思路，这
个很难说。
最后希望大家面g家的人好运了，如果能碰到相同的题目，算是对你有点帮助了。 |
j******2
发帖数: 362 | 2 请问这个是店面吗？能透露是什么组吗？
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
M********5
发帖数: 715 | 3 对，这个是电面，没有什么组吧，general的。。。
【在 j******2 的大作中提到】
: 请问这个是店面吗？能透露是什么组吗？
:
: -1
|
j*****y
发帖数: 1071 | 4 bless.
第一题 还用在 计算一个数 有多少个1 bit
第二题这么做可以吗， 那个随机函数 call n 次， 每次都是1 的话 返回 1, 否则返
回 0
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
j******2
发帖数: 362 | 5 谢谢分享！祝好运！
【在 M********5 的大作中提到】
: 对，这个是电面，没有什么组吧，general的。。。
|
M********5
发帖数: 715 | 6 这个，如果说你说出来了每次改变最后一个1，自然就推出可以计算有多少个1了
第二个这么做是对的，不过我当时拿到这个题目的时候有点懵了，其实他没有跟我说他
有一个那样的随机函数，他没有加什么条件，是我最后面完了把这个题目想了想，他应
该是这个意思。应该是你说的这个方法，1/(2^n)就是(1/2)^n嘛。。。没有准备好啊，
要是这个题目onsite我也肯定悲剧。。。
【在 j*****y 的大作中提到】
: bless.
: 第一题 还用在 计算一个数 有多少个1 bit
: 第二题这么做可以吗， 那个随机函数 call n 次， 每次都是1 的话 返回 1, 否则返
: 回 0
:
: -1
|
d*********g
发帖数: 154 | 7
感觉这样做应该是最简单的~
【在 j*****y 的大作中提到】
: bless.
: 第一题 还用在 计算一个数 有多少个1 bit
: 第二题这么做可以吗， 那个随机函数 call n 次， 每次都是1 的话 返回 1, 否则返
: 回 0
:
: -1
|
l**b
发帖数: 457 | 8 能不能直接生成n个0，1，然后如果全部是0才返回0，只要出现1个1都返回1？这样就不
用担心overflaw了吧？也是比较naive的想法 |
M********5
发帖数: 715 | 9 反了，如果全部是0才返回1，只要出现个1就返回0，跟上面的思路是一样的。。。
【在 l**b 的大作中提到】
: 能不能直接生成n个0，1，然后如果全部是0才返回0，只要出现1个1都返回1？这样就不
: 用担心overflaw了吧？也是比较naive的想法
|
l**b
发帖数: 457 | 10 丢，老年痴呆，再次看错题目，你没问问如果n小于0的话怎么处理？是不是直接返回1
如果n <= 0？
【在 M********5 的大作中提到】
: 反了，如果全部是0才返回1，只要出现个1就返回0，跟上面的思路是一样的。。。
|
|
|
p*****2
发帖数: 21240 | 11
这样不错。这个题还有个变形。就是可以按照任意的概率来返回。
【在 l**b 的大作中提到】
: 能不能直接生成n个0，1，然后如果全部是0才返回0，只要出现1个1都返回1？这样就不
: 用担心overflaw了吧？也是比较naive的想法
|
l**b
发帖数: 457 | 12 就是不一定按照1/2^n返回1？可以是1/5^3这样？
然后谢谢楼主的MJ和题目，收录了。
【在 p*****2 的大作中提到】
:
: 这样不错。这个题还有个变形。就是可以按照任意的概率来返回。
|
r*****e
发帖数: 146 | 13 prob1: it can be used to count how many 1's for a number in binary
representation.
prob2:
int fun(int n){
while(n){
if(rand_0_1()==1){
n--;
}else{
return 0;
}
}
return 1;
}
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
b*********h
发帖数: 103 | 14 第二题感觉这样做挺好的 只是看实现方式还可以大大提高 这样写 google 应该不喜欢
的... |
p*****2
发帖数: 21240 | 15
嗯。可以在0－1之间任意概率返回
【在 l**b 的大作中提到】
: 就是不一定按照1/2^n返回1？可以是1/5^3这样？
: 然后谢谢楼主的MJ和题目，收录了。
|
l**b
发帖数: 457 | 16 第一题followup这样好晕啊，如果没有看过完全不知道吗。 |
M********5
发帖数: 715 | 17 我也是这么想的，他这么followup我不知道他要什么东西
【在 l**b 的大作中提到】
: 第一题followup这样好晕啊，如果没有看过完全不知道吗。
|
m******s
发帖数: 165 | 18 第一题可以用来遍历一个bitmask的所有1，不过我不太喜欢这么写。。。
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
p*****2
发帖数: 21240 | 19
我把这道题做了以下，放到了我的博客里了。
http://blog.sina.com.cn/s/blog_b9285de20101h463.html
【在 p*****2 的大作中提到】
:
: 嗯。可以在0－1之间任意概率返回
|
f********s
发帖数: 35 | 20 Smart!
【在 p*****2 的大作中提到】
:
: 我把这道题做了以下，放到了我的博客里了。
: http://blog.sina.com.cn/s/blog_b9285de20101h463.html
|
|
|
e******o
发帖数: 757 | 21 靠，牛逼，面试的时候能想到bayes
【在 p*****2 的大作中提到】
:
: 我把这道题做了以下，放到了我的博客里了。
: http://blog.sina.com.cn/s/blog_b9285de20101h463.html
|
c*****z
发帖数: 182 | 22 忍不住说，第二题不酒是第一题的应用吗
【在 e******o 的大作中提到】
: 靠，牛逼，面试的时候能想到bayes
|
n****r
发帖数: 120 | 23 “实现一个函数随机返回任意概率的true”这题如下解有啥问题没有？
static boolean tureWithProbablity(double p){
int r = (int)(new Random().nextDouble() * 100);
int prob = (int)(p * 100);
return r < prob;
} |
f*******t
发帖数: 49 | 24 第一个都没看明白，怎么能算出N的1个数呢？
1111 & 1110 = 1110
10100 & 10011 = 10000 |
p*****2
发帖数: 21240 | 25
需要个循环吧。
【在 f*******t 的大作中提到】
: 第一个都没看明白，怎么能算出N的1个数呢？
: 1111 & 1110 = 1110
: 10100 & 10011 = 10000
|
y********9
发帖数: 130 | |
d******e
发帖数: 164 | 27 解释下吧。。。看不懂
【在 p*****2 的大作中提到】
:
: 需要个循环吧。
|
y********9
发帖数: 130 | 28
求解释
【在 d******e 的大作中提到】
: 解释下吧。。。看不懂
|
f*******t
发帖数: 49 | 29
哪本呢？
【在 y********9 的大作中提到】
: 第一题在那本卖的最好的c语言书里有讲到。。
|
y********9
发帖数: 130 | 30
名字忘记了 以前看的 反正就是基本上每个人都买的作为“c语言101”的书
【在 f*******t 的大作中提到】
:
: 哪本呢？
|
|
|
A****L
发帖数: 138 | 31 太牛了! 你是现场写出这个code的吗？
弱问下，如何从数学上，推到出来呢？
【在 p*****2 的大作中提到】
:
: 需要个循环吧。
|
p*****2
发帖数: 21240 | 32
博客上加解释了。
【在 y********9 的大作中提到】
:
: 名字忘记了 以前看的 反正就是基本上每个人都买的作为“c语言101”的书
|
p*****2
发帖数: 21240 | 33
不是我面的。是某大牛面遇到的。我大概花了40分钟解出来的。我数学不好，在
macbook上java试验证明是可行的。
但是当时有人在linux上效果不好，我研究了一下，是linux上本身的random函数有问题
。
【在 A****L 的大作中提到】
: 太牛了! 你是现场写出这个code的吗？
: 弱问下，如何从数学上，推到出来呢？
|
h*u
发帖数: 122 | |
y********9
发帖数: 130 | 35
懂了 多谢 当场想出来很难啊
【在 p*****2 的大作中提到】
:
: 不是我面的。是某大牛面遇到的。我大概花了40分钟解出来的。我数学不好，在
: macbook上java试验证明是可行的。
: 但是当时有人在linux上效果不好，我研究了一下，是linux上本身的random函数有问题
: 。
|
e******o
发帖数: 757 | 36 有个简单的，不是有doulbe 的binary representation么，initialize 一个为0 的
double, 不停的抛硬币，抛到正面就把相应的bit set为1，反面就set为0, 如果得到的
数如果大于p, 输出false, 小于p就输出true.
【在 p*****2 的大作中提到】
:
: 不是我面的。是某大牛面遇到的。我大概花了40分钟解出来的。我数学不好，在
: macbook上java试验证明是可行的。
: 但是当时有人在linux上效果不好，我研究了一下，是linux上本身的random函数有问题
: 。
|
p*****2
发帖数: 21240 | 37
嗯。那个大牛是ACMER，所以出的题比一班人要难。
【在 y********9 的大作中提到】
:
: 懂了 多谢 当场想出来很难啊
|
p*****2
发帖数: 21240 | 38
有其他人提出这个思路了，当时。不过我也不太懂binary的representation, 这个算法
应该fair吧？
【在 e******o 的大作中提到】
: 有个简单的，不是有doulbe 的binary representation么，initialize 一个为0 的
: double, 不停的抛硬币，抛到正面就把相应的bit set为1，反面就set为0, 如果得到的
: 数如果大于p, 输出false, 小于p就输出true.
|
e******o
发帖数: 757 | 39 bool tossCoin();
bool randP(double P)
{
doule p0(0);
for ( int i=1; i!=N; ++i ) \\N根据double的精度，多少不记得了
{
if ( tossCoin() )
p0 += 1/pow(2,i);
if ( p0 > p ) return false;
if ( p - p0 ) > 1/pow(2,i) return true;
}
return false;
}
【在 p*****2 的大作中提到】
:
: 有其他人提出这个思路了，当时。不过我也不太懂binary的representation, 这个算法
: 应该fair吧？
|
b***y
发帖数: 14281 | 40 两个都是正解，LZ还在迷雾中，悲剧是正常的。
★ 发自iPhone App: ChineseWeb 7.7
【在 j*****y 的大作中提到】
: bless.
: 第一题 还用在 计算一个数 有多少个1 bit
: 第二题这么做可以吗， 那个随机函数 call n 次， 每次都是1 的话 返回 1, 否则返
: 回 0
:
: -1
|
|
|
M********5
发帖数: 715 | 41 我说了这两个都是正解，你哪看出我还在迷雾中了。。。
【在 b***y 的大作中提到】
: 两个都是正解，LZ还在迷雾中，悲剧是正常的。
:
: ★ 发自iPhone App: ChineseWeb 7.7
|
s****g
发帖数: 257 | 42 This sounds like not as hard. The bar has been lowered?
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
y****n
发帖数: 743 | 43 我能想到比较快的方法：
const int ShiftStep = 63;
static bool Random2N(int n)
{
Random rand = new Random(DateTime.Now.Millisecond);
while (n > 0)
{
int shift = Math.Min(ShiftStep, n);
double randVal = rand.NextDouble() * ((UInt64)1 << shift);
if (randVal >= 1)
return false;
n -= shift;
}
return true;
} |
f*****n
发帖数: 405 | 44 这个还可以再简单：
Prob2:
int fun(int n) {
while(n--) {
if(rand_0_1()==0) return 0;
}
return 1;
}
【在 r*****e 的大作中提到】
: prob1: it can be used to count how many 1's for a number in binary
: representation.
: prob2:
: int fun(int n){
: while(n){
: if(rand_0_1()==1){
: n--;
: }else{
: return 0;
: }
|
h*******e
发帖数: 1377 | 45 n&(n-1)可以用在8 皇后问题里面，枚举下一个取得皇后。
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
l****g
发帖数: 1320 | |
m*****k
发帖数: 731 | 47 如果你都可以生成num ＝ 1<
那干嘛不直接 new Random().nextInt(n) 来产生一个 int x, where n-1>=x>=0,
return x==0 就完了。
我实在是看不出（double）num*rand() 为何能work？
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
e***s
发帖数: 799 | 48 第二题最简单就是这样吧？ 不知道有BUG没有
int func(int n){
for(int i = 1; i <= n; i++)
{
if(Rand() == 0)
return 0;
}
return 1;
} |
c********t
发帖数: 5706 | 49 赞，引申问一个这类题经常被问道的follow question，如何测试验证你的程序？
【在 p*****2 的大作中提到】
:
: 有其他人提出这个思路了，当时。不过我也不太懂binary的representation, 这个算法
: 应该fair吧？
|
l*****a
发帖数: 559 | 50 除了simulation，还能如何验证？
【在 c********t 的大作中提到】
: 赞，引申问一个这类题经常被问道的follow question，如何测试验证你的程序？
|
|
|
c********t
发帖数: 5706 | 51 不知道。但觉得验证random的方法应该也可以用来验证概率吧。
★ 发自iPhone App: ChineseWeb 7.8
【在 l*****a 的大作中提到】
: 除了simulation，还能如何验证？
|
e*****r
发帖数: 93 | 52 第一题在树状数组里面有用，是标准做法，用做数多少个1的话，渐进复杂度和直接扫
一遍一样的。。。数多少个1有更快的做法 |
M********5
发帖数: 715 | 53 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
准备的还是不够，希望能对其他找工作的人有帮助。
一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
另外两道题
1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
)”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
2 第二道题，以1/(2^n)的概率返回1，其它的时候返回0，题目应该假设有个函数可以
生成1或者0，以1/2的概率
我当时想了一下，最intuitive的想法是先产生一个数，num = 1<
(double)num * rand();
当时写的时候没有把num转化成double，这是一个bug，并且我觉得这个bug其实是不
应该的，也是个很关键的bug。 然后他不满意，我也知道，我说n很大的时候num会
overflow，这个时候有两种解决方式，一种是用BigInt，还有一种用divide and
conque，举了个例子，如果int是16位的话，那么n大于16的时候，就不断地divide and
conque，直到小于16为止。
然后我第二天把这个问题想了一想，我现在来讲，比较好的解决方法是：
int probability(int n){
std::vector vec_n;
int i;
for(i=0; i
int t = fun_0_1();
vec_n.push_back(t);
}
if( vec_n[0] == 1 )
for(i=1; i
if( vec_n[i]==1 )
break;
}
if( i==n )
return 1;
else
return 0;
}
说实话，题目不难，但是第一题，我真是没看出来他想要什么样的答案，并且最后他要
的这个答案的方向，我觉得很奇怪，其实我最后给他的答案跟他这个意思也很相近了，
但是他觉得这不是他想要的，我也没有办法。
第二题，说实在的，我觉得divide and conquer是可行的，并且这个方法的效率也不差
，但是我觉得最后的code写得还是很不完美的，有两个地方我做的不好，一个是不能假
设int为16位，可以用sizeof函数算出来，第二个我divide and conquer的时候没有考
虑到奇数偶数的问题，这个应该是考虑到的，不然没有办法保证产生的概率是1/(2^n)
不过其实我依然觉得，这个题目不难，但是也不像想象中的那么简单，主要是这些并不
是常见的算法和数据结构的题目，没有碰到的时候，你一下子能不能有最好的思路，这
个很难说。
最后希望大家面g家的人好运了，如果能碰到相同的题目，算是对你有点帮助了。 |
x*****e
发帖数: 9 | 54 第二题我觉得可以这样来做。
假设有个函数f以1/2的概率产生1和0
记i=1，用f产生一个数字。如果是0的话，停止
如果是1的话，记i=2，继续用函数f产生是1或者0。如果是0停止，如果是1继续这个迭
代步骤，直到i=n。
以n=2为例。产生0的概率是1/2+1/4=3/4，产生1的概率就是1/4 |
X****y
发帖数: 33 | 55 楼上正解。。
【在 x*****e 的大作中提到】
: 第二题我觉得可以这样来做。
: 假设有个函数f以1/2的概率产生1和0
: 记i=1，用f产生一个数字。如果是0的话，停止
: 如果是1的话，记i=2，继续用函数f产生是1或者0。如果是0停止，如果是1继续这个迭
: 代步骤，直到i=n。
: 以n=2为例。产生0的概率是1/2+1/4=3/4，产生1的概率就是1/4
|
e****b
发帖数: 25 | 56 第一题不就是想你说可以算一个数二进制1的个数呗 我认为 |
w**********o
发帖数: 140 | 57 2.
It's a variation of unbiased coin.
Python version
====================================
import random
def getProb(n):
for i in xrange(n):
if toss() == 0:
return 0
return 1
def toss():
return random.choice([0,1]) |
g*****y
发帖数: 1120 | 58 不错，比n个bits生成一个特定数一样效果但省事
【在 x*****e 的大作中提到】
: 第二题我觉得可以这样来做。
: 假设有个函数f以1/2的概率产生1和0
: 记i=1，用f产生一个数字。如果是0的话，停止
: 如果是1的话，记i=2，继续用函数f产生是1或者0。如果是0停止，如果是1继续这个迭
: 代步骤，直到i=n。
: 以n=2为例。产生0的概率是1/2+1/4=3/4，产生1的概率就是1/4
|
w********s
发帖数: 1570 | 59 第一题，其他方法包括：
1, bit count(n)
如果"1"为1个，那么就是2^n，可以用1条cpu instruction解决，叫popcnt，如果面试
你的不知道什么叫popcnt，那么太差劲了。
2, bsr == bsf，也就是左边数起1的位置==从右边数起1的位置
2条386汇编解决。
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
w********s
发帖数: 1570 | 60 第一题还可以用来测试奇偶吧
n & (n - 1) == n - 1
n & (n - 1) == n - 2
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
|
|
w********s
发帖数: 1570 | 61 第二题，递归
int rand2()
{
return rand() > (RAND_MAX >> 1);
}
int randn(int n)
{
if (n == 1) return rand2();
return randn(n - 1) && rand2();
}
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
b****f
发帖数: 138 | |
f********x
发帖数: 2086 | 63
-1
能再解释一下他想要的第一题的答案么？“改变最后一位不是0的数字”？
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
w*****d
发帖数: 105 | 64 2 第二道题，以1/(2^n)的概率返回1，其它的时候返回0，题目应该假设有个函数可以
生成1或者0，以1/2的概率
n次rand()都是1（或都是0）的概率就是1/2^n。 |
p*******i
发帖数: 190 | 65 第一题 是 想问 memory address alignment 吧
-1
【在 M********5 的大作中提到】
: 刚收到消息，悲剧了，意料之中，不过我也还ok，还有其他公司move on吧，可能今年
: 准备的还是不够，希望能对其他找工作的人有帮助。
: 一共三题，有一道是c++的基础题，那个很简单，基本你要是会c++应该就会写。
: 另外两道题
: 1 第一道题，是说你知道(n&(n-1))得出什么结果吗？
: 这个好答，我当时说这个我见到过，是看一个数是不是2^n，然后他问，除了这个之
: 外，还可以用在别的地方吗？然后他问了这个之后，我主要是不知道他要问的point在
: 哪。。。最后兜兜转转地跟他聊了很多，结果最后终于知道，他要的答案是，“n&(n-1
: )”改变最后一位不是0的数字。I mean,这个我未必不知道，但是他问我还可以用来做
: 什么的时候，我确实不知道他想要什么答案，因为这个可能可以用在很多情况下
|
s******u
发帖数: 550 | |
l*****8
发帖数: 1083 | 67 Mark
★ 发自iPhone App: ChineseWeb 8.6
【在 s******u 的大作中提到】
: thanks for sharing,
|
g*********e
发帖数: 14401 | 68 第二题
int foo(int n) {
for(int i=0; i
if(halfChanceTrue()) return 0;
return 1;
} |
T*****u
发帖数: 7103 | 69 第二题就产生n个[0 1]随机数,乘一起是不是就行了? |
