[TL] {OT} 笔试归来，不会的很多

[kroody]

int test(int n)

{

        int nCount = 0;

        while(n)

        {

                nCount++;

                n = n & (n - 1);

        }

        return nCount;

}

求test（9999）

2 不用递归法 求一个固定集合内的所有子集
3 假设 一个系统只发 ABCDEF六种信息  各自的概率分别为 P1  P2 P3 P4 P5 P6 求怎么设计才能达到最节省带宽 好像 具体忘了是不是这样表述的


问我怎么用python发送邮件
问我ip校验和怎么计算 我...

ps 你不是对linux很熟悉吗  为什么那两个问题都回答不上来呢？（大哥，对linux熟悉也有不会的啊 ，我真的不知道该怎么回答）

总之， 以前没碰到过类似的笔试，做的一塌糊涂

不知道各位什么看法或解法

--
彪悍的人生不需要解释！

[Doyle]

2010/4/27 kroody <krood...@gmail.com>

int test(int n)

{

        int nCount = 0;

        while(n)

        {

                nCount++;

                n = n & (n - 1);

        }

        return nCount;

}

求test（9999）

假设9999的二进制表达为xxxxxxxxxx...xxx1,显然最后一位是1(因为是奇数)

则可知9998二进制表达为xxxxxxxxxx...xxx0,显然最后一位是0(因为是偶数)

显然,9999&9998=>9998(xxxxxxxxxx...xxx0)

然后是9998&9997=>我不知道是多少,但是,肯定是xxxxxxxxxx...xx00

继续下去,就是xxxxxxxxxx...xxx0和xxxxxxxxxx...xxx(反)0(反)相与

所以最后n = 9999表达为2进制时需要多少位列

于是  取整(log(9999,2))=13,所以n=14

[sagasw]

嘿嘿，答案应该为8（跑出来的结果）
第一题我也是想了又想才想明白。

------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
http://t.qq.com/sagasw
------------------------------------------

2010/4/27 Doyle <doyl...@gmail.com>

[qiaojie]

题目有点难度，不过也不算很过分，稍微动点脑筋还是可以做的。

 

1. 把9999转化为2进制，数一下里面有几个1

2. 用递归的思路是，先从集合里减掉一个元素，成为一个新的子集放到输出里，然后以这个新的子集作为输入递归调用直到遇到空集返回，每个递归函数里依次执行n(n为元素个数)遍，放到输出里的结果要注意去掉重复子集。不用递归的话自己开个Stack存放中间数据也是可以搞定的。

3. huffman编码

 

2010/4/27 kroody <krood...@gmail.com>

[kroody]

我也是跑完了才知道是8  当时做的时候傻了

怎么个思路

2010/4/27 sagasw <sag...@gmail.com>

--
彪悍的人生不需要解释！

[xxmplus]

2010/4/27 kroody <krood...@gmail.com>:

> int test(int n)
> {
> int nCount = 0;
> while(n)
> {
> nCount++;
> n = n & (n - 1);
> }
> return nCount;
> }
> 求test（9999）

第一感觉是9999，跑程序的结果大吃一惊，还是被二进制给耍了orz

--
Any complex technology which doesn't come with documentation must be the best
available.


--
Subscription settings: http://groups.google.com/group/pongba/subscribe?hl=zh-CN

[sagasw]

个人感觉，不用递归，应该是指解决思想，而不是中间结果吧？

------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
http://t.qq.com/sagasw
------------------------------------------

2010/4/27 qiaojie <qia...@gmail.com>

[qiaojie]

解决思想就是先用递归解，然后把递归转化为迭代解。

2010/4/27 sagasw <sag...@gmail.com>

[Shuo Chen]

2. N 个元素的集合，从 0 到 2^N - 1 遍历，把二进制数打出来，每个数是一个子集。
3. 简单的可以用 huffman 编码，结果不是最优的。好一点可以用算术编码，可以接近信息论下界。

[kroody]

霍夫曼编码以前上学学过一点，基本忘掉了， 笔试的时候倒是想到这个(只想到这个) 不过题目还是不会 笔试一共还有30分钟的时间

另外还有几个题

2010/4/27 xxmplus <xxm...@gmail.com>

--
彪悍的人生不需要解释！

[sagasw]

每次减一相当于消减掉了最低位的1，
0b110000 - 1 得到
0b101111

如1100000为96
   1011111为95

故此得知。

------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
http://t.qq.com/sagasw
------------------------------------------

2010/4/27 kroody <krood...@gmail.com>

[qiaojie]

2010/4/27 Shuo Chen <gian...@gmail.com>

2. N 个元素的集合，从 0 到 2^N - 1 遍历，把二进制数打出来，每个数是一个子集。

 

正解。

[sagasw]

这个2不错，这次的确不是递归了。

------------------------------------------
blog: http://sunxiunan.com/
C++, Lua, living in Dalian
http://twitter.com/sagasw
http://t.qq.com/sagasw
------------------------------------------

2010/4/27 Shuo Chen <gian...@gmail.com>

[kroody]

http://topic.csdn.net/t/20040731/11/3229129.html

原来早就有讨论此类题目的， 没学到而已 

2010/4/27 sagasw <sag...@gmail.com>

--
彪悍的人生不需要解释！

[Lucas Zhang]

恩，这的确是个简单快速的方法～

2010/4/27 qiaojie <qia...@gmail.com>

2010/4/27 Shuo Chen <gian...@gmail.com>

2. N 个元素的集合，从 0 到 2^N - 1 遍历，把二进制数打出来，每个数是一个子集。

 

正解。

--
Zhang Qing (张卿)
@SJTU ShangHai

[郑海涛]

觉得这种面试太变态了吧，

我觉得说出思想就可以了，他居然还有那么变态的9999计算，服了。

[kroody]

还有关于linux的题目

用户空间和内核交换数据有哪几种方式

2010/4/27 Lucas Zhang <zhangq...@gmail.com>

--
彪悍的人生不需要解释！

[kroody]

问我期望待遇多少， 吓得我说多少都可以（觉得反正没戏了，要多少是多啊）

2010/4/27 kroody <krood...@gmail.com>

--
彪悍的人生不需要解释！

[郑海涛]

你去哪里面试啊，这么变态的，是不是要打压你的待遇啊，呵呵。

[Xpol Wan]

就是啊，给个15，16啥的我可以口算出来。9999……我只有吐泡沫了，我只能告诉他说，我要运行一下calc。

Best Regards!

Xpol Wan

2010/4/27 郑海涛 <zht...@gmail.com>

觉得这种面试太变态了吧，

我觉得说出思想就可以了，他居然还有那么变态的9999计算，服了。

[WindyWinter]

这题挺正常的吧，就"python怎么发邮件“有点偏门，谁没事儿记python那么多库。
Soli Deo gloria,
yours WindyWinter
and http://d.ream.at

2010/4/27 郑海涛 <zht...@gmail.com>

[zhichang wang]

test 函数实际是每轮消去n的二进制表示中的一个1，所以

test(9999)应该返回9999的二进制表示中1的个数

[kroody]

哦 本质原来是这样啊

2010/4/27 zhichang wang <wangzh...@gmail.com>

--
彪悍的人生不需要解释！

[Milo Yip]

我也補充一下這些問題的來歷
1. 這是Hamming weight的一個實現方式，可參考 http://en.wikipedia.org/wiki/Hamming_weight
2. 這是power set，可參考 http://en.wikipedia.org/wiki/Power_set

對於第2條問題，我會問interviewer輸入集合的大小，以及輸出的方式。有些情況用stack可能比較高效。

[Lucas Zhang]

9999那个还好吧，知道意思的话最多1分钟也算出来了～
它的意思不是让你去模拟这个函数-_-

2010/4/27 郑海涛 <zht...@gmail.com>

[朱雷]

第一个问题之前看到过，不然我也不会做。

《编程之美——微软技术面试心得》2.1 求二进制数中1的个数 中的解法三中

[hui liu]

这题很普通吧，9999转化为16进制再用2进制写出来，数数1的个数；0~(2^n-1)个数的2进制输出；huffman编码；随便哪家较好点的互联网公司出的题貌似都比这难...

在 2010年4月27日 下午1:39，kroody <krood...@gmail.com>写道：

int test(int n)

{

        int nCount = 0;

        while(n)

        {

                nCount++;

                n = n & (n - 1);

        }

        return nCount;

}

求test（9999）

2 不用递归法 求一个固定集合内的所有子集
3 假设 一个系统只发 ABCDEF六种信息  各自的概率分别为 P1  P2 P3 P4 P5 P6 求怎么设计才能达到最节省带宽 好像 具体忘了是不是这样表述的


问我怎么用python发送邮件
问我ip校验和怎么计算 我...

ps 你不是对linux很熟悉吗  为什么那两个问题都回答不上来呢？（大哥，对linux熟悉也有不会的啊 ，我真的不知道该怎么回答）

总之， 以前没碰到过类似的笔试，做的一塌糊涂

不知道各位什么看法或解法

--
彪悍的人生不需要解释！

[kroody]

应该不能只给出Huffman编码这一点，要把整个题目做完吧

2010/4/27 hui liu <ieli...@gmail.com>

--
彪悍的人生不需要解释！

[Mikster.Z]

这些题答不出来有点说不过去.....说明基础确实有问题

[Mikster.Z]

PS：只说前3道...

[Lucas Zhang]

把6个数字排下序，画棵树就ok了嘛...

2010/4/27 kroody <krood...@gmail.com>

[econsh]

摘自编程之美

位操作比除、余操作的效率高了很多。但是，即使采用位操作，时间复杂度仍为O（log2v），log2v为二进制数的位数。那么，还能不能再降低一些复
杂度呢？如果有办法让算法的复杂度只与"1"的个数有关，复杂度不就能进一步降低了吗？

同样用10 100 001来举例。如果只考虑和1的个数相关，那么，我们是否能够在每次判断中，仅与1来进行判断呢？

为了简化这个问题，我们考虑只有一个1的情况。例如：01 000 000。

如何判断给定的二进制数里面有且仅有一个1呢？可以通过判断这个数是否是2的整数次幂来实现。另外，如果只和这一个"1"进行判断，如何设计操作呢？我
们知道的是，如果进行这个操作，结果为0或为1，就可以得到结论。

如果希望操作后的结果为0，01 000 000可以和00 111 111进行"与"操作。

这样，要进行的操作就是 01 000 000 &（01 000 000 - 00 000 001）= 01 000 000 &

00 111 111 = 0。

因此就有了解法三的代码：

代码清单2-3

1. int Count(int v)
2. {
3. int num = 0;
4. while(v)
5. {
6. v &= (v-1);
7. num++;
8. }
9. return num;
10. }

On Apr 27, 1:39 pm, kroody <kroodyl...@gmail.com> wrote:

> int test(int n)
> {
> int nCount = 0;
>
> while(n)
> {
> nCount++;
> n = n & (n - 1);
> }
>
> return nCount;}
>
> 求test（9999）
>
> 2 不用递归法 求一个固定集合内的所有子集
> 3 假设 一个系统只发 ABCDEF六种信息 各自的概率分别为 P1 P2 P3 P4 P5 P6 求怎么设计才能达到最节省带宽 好像
> 具体忘了是不是这样表述的
>
> 问我怎么用python发送邮件
> 问我ip校验和怎么计算 我...
>
> ps 你不是对linux很熟悉吗 为什么那两个问题都回答不上来呢？（大哥，对linux熟悉也有不会的啊 ，我真的不知道该怎么回答）
>
> 总之， 以前没碰到过类似的笔试，做的一塌糊涂
> 不知道各位什么看法或解法
>
> --
> 彪悍的人生不需要解释！
>
> --

> Subscription settings:http://groups.google.com/group/pongba/subscribe?hl=zh-CN

[songyy]

第一题感觉还是挺简单的吧......
很明显 2^10 = 1024，这样 2^10 * 8 = 8192，之后做减法，重复，就出来结果是8啦~~
2的倍数还是要记清啦

[Mikster.Z]

是一的个数吧？&n-1是消最低位1

On 28 Apr 2010 08:51, "songyy" <fly...@yahoo.com.cn> wrote:

第一题感觉还是挺简单的吧......
很明显 2^10 = 1024，这样 2^10 * 8 = 8192，之后做减法，重复，就出来结果是8啦~~
2的倍数还是要记清啦

On 4月27日, 下午1时39分, kroody <kroodyl...@gmail.com> wrote:
> int test(int n)
> {

> int nCount ...

[Kenny Yuan]

这个数字好熟悉，我的第一台Universal Turing Machine就是8192 bytes内存

在 2010年4月28日 上午8:51，songyy <fly...@yahoo.com.cn>写道：

第一题感觉还是挺简单的吧......
很明显 2^10 = 1024，这样 2^10 * 8 = 8192，之后做减法，重复，就出来结果是8啦~~
2的倍数还是要记清啦

--
Kenny Yuan
-->CS, MMA, Psychology, Automobile...
http://twitter.com/kenny_yuan
http://csbabel.wordpress.com/
http://blog.csdn.net/yuankaining/

[jiang yu]

太打击人了，一个不会！

我出的笔试题只敢求一下100之内的素数，这样都挑不到几个人，对这样的牛题膜拜了

在 2010年4月27日 下午1:39，kroody <krood...@gmail.com>写道：

int test(int n)

{

[Jeff Chen]

这...建议你改成求100以内的奇数...

--
My Blog：http://jeffchen.cn

[朱晋玄]

我觉得改求一百以内的自然数也许比较恰当
话说很多学校喜欢拿100以内的素数当作作业来做.........

[kroody]

大牛们 别再笑话俺了

2010/4/28 朱晋玄 <zhuji...@gmail.com>

--
彪悍的人生不需要解释！

[qingant]

不会欧几里德算法不能说明什么阿。。。

2010/4/28 jiang yu <yu.jia...@gmail.com>

[qiaojie]

话说我以前招聘出的编程题目也是求素数，并且还要求在算法上考虑优化，这个题目对编程基础的考察是非常有效的，能力差的人连一个for循环都组织不好。

 

2010/4/29 qingant <qin...@gmail.com>

[WindyWinter]

扩展欧几里德不能当场写出来还情有可原，欧几里德都不知道的就有点过分了。
求素数太无聊了，改成问筛法求素数的复杂度吧。

Soli Deo gloria,
yours WindyWinter
and http://d.ream.at

2010/4/29 qiaojie <qia...@gmail.com>

[qiaojie]

其实要在纸上把程序写对不是件容易的事情，即使是非常简单的算法。平时我们写程序习惯了编写、出错、调试再修改。

前几天在网上看到有篇文章说，90%的程序员无法一次性写出正确的二分查找算法，我自己尝试了一下，尽管在编写的

过程中尽量避免犯错，但是第一次运行还是失败了，修改了2次才通过全部的测试。所以对编程能力的考察不需要考多

难的题目，但是一定要让他动手写。

 

 

 

2010/4/29 WindyWinter <bsl...@gmail.com>

[qiaojie]

根据我对此题面试结果的总结，发现不靠谱的程序员还是很多的，有些人估计平时写程序都是先拷贝别人的代码，然后在其基础上修修改改来的，所以你给他一张白纸，他会连基本语法都给忘了，写出来的代码完全不着边际。

2010/4/29 qiaojie <qia...@gmail.com>

[居振梁]

还有一种情况，思路是有的，
但是由于用的语言或脚本语言太多，不确定某个api在给定语言里是否存在，或者不确定详细签名。

2010/4/29 qiaojie <qia...@gmail.com>

根据我对此题面试结果的总结，发现不靠谱的程序员还是很多的，有些人估计平时写程序都是先拷贝别人的代码，然后在其基础上修修改改来的，所以你给他一张白纸，他会连基本语法都给忘了，写出来的代码完全不着边际。

--
御剑乘风来，除魔天地间。有酒乐逍遥，无酒我亦颠。
http://www.xspirithack.org
一饮尽江河，再饮吞日月。千杯醉不倒，唯我酒剑仙。

[@@]

这个是用太少，生疏。。而且总得有一个熟悉的吧。。

2010/4/29 居振梁 <juzhe...@gmail.com>

[居振梁]

碰上会代码提示的ide，用的再多还是不容易记住。
（这里讨论的前提是再纸上写）

2010/4/29 @@ <ask...@gmail.com>

这个是用太少，生疏。。而且总得有一个熟悉的吧。。

[@@]

恩 算素数。。IDE能提示什么

2010/4/29 居振梁 <juzhe...@gmail.com>

[居振梁]

汗，没准备具体到这一个情况。
或者，提示 for if 框架算吗?

2010/4/29 @@ <ask...@gmail.com>

恩 算素数。。IDE能提示什么

[guihua wu]

非常同意，，我去参加面试的时候就有过这种情况，，面试官非常鄙视的说我对语言不熟悉。。。

2010/4/29 居振梁 <juzhe...@gmail.com>

[WindyWinter]

你可以拿这个题堵他一下，看他对C++熟悉不熟悉。http://d.ream.at/politics-for-programmers/

Soli Deo gloria,
yours WindyWinter
and http://d.ream.at

2010/4/29 guihua wu <guihua...@gmail.com>

[guihua wu]

我觉得他可能只要求我是一个有良好记忆的代码工，而不需要有严谨的态度或者深刻的思想。。。嘿嘿，

2010/4/29 WindyWinter <bsl...@gmail.com>

[Mikster.Z]

有网络环境，给个题目，限定时间，只要看看输出，再看看他的浏览记录，基本上就八九不离十了

[Yongwei Wu]

伤心，我居然也落进了这90%。我第一次写出的代码如下：

int* bsearch(int to_search, int* begin, int* end)
{
while (begin != end) {
int* middle = begin + (end - begin) / 2;
if (to_search == *middle) {
return middle;
} else if (to_search < *middle) {
end = middle;
} else if (to_search > *middle) {
begin = middle + 1;
}
}
return end;
}

感觉挺简洁的，但变量的复用（end）出了问题。如果不允许变量复用，或者使用递归的话，可能就不会出这样的问题了。

下次面试，也考别人这样的题目看看。:-)

2010/4/29 qiaojie <qia...@gmail.com>:

--
Wu Yongwei
URL: http://wyw.dcweb.cn/

[Serenade]

我记得是某游戏公司的面试，当初我做出了一大半，还是被刷掉了
- -；

现在看看，闭卷的情况下不做准备的能答出来的，那个薪资待遇再翻上2翻也未必找的到人

[Hamo]

2010/4/30 Serenade <seren...@gmail.com>:

> 我记得是某游戏公司的面试，当初我做出了一大半，还是被刷掉了
> - -；
>
> 现在看看，闭卷的情况下不做准备的能答出来的，那个薪资待遇再翻上2翻也未必找的到人
>

出面试题这位估计是刚看了《代码之美》，书里面提到了种群记数的多种方法，在后面的某一章提到了两种精美（我自己认为）的位操作：
x & (x-1) 将X的二进制最低一位1置0
x | (x+1) 将X的二进制最低一位0置1

--
"""
Keep It Simple,Stupid.
"""

Chinese Name: 白杨
Nick Name: Hamo
Homepage: http://hamobai.com/
GPG KEY ID: 0xA4691A33
Key fingerprint = 09D5 2D78 8E2B 0995 CF8E 4331 33C4 3D24 A469 1A33