百度在线笔试题求解（二）！！！！！！！！！！！！！！
1.（5分）下面这段代码是把中英文混合字符串(汉字用两个字节表示，特点是第一个字节的最高位为1)中的大写字母转化为小写字母，请找出其中的bug，注意各种异常情况。
for (char *piterator = szWord; *piterator != 0; piterator++)
{
if (*piterator & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
*piterator += 32;
}
2.（5分）对给定的上亿条无序的url，请按照domain、site以及path分别排序，并请指出排序过程中可能会遇到的哪些问题？如何提高效率？
例如：http://www.baidu.com/path/about.html，domain、site以及path的定义分别如下：
Domain:baidu.com
Site:www.baidu.com
Path: www.baidu.com/path
3.（10分）某型CPU的一级数据缓存大小为16K字节，cache块大小为64字节；二级缓存大小为256K字节，cache块大小为4K字节，采用二路组相联。经测试，下面两段代码运行时效率差别很大，请分析哪段代码更好，以及可能的原因。
为了进一步提高效率，你还可以采取什么办法？
A段代码
int matrix[1023][15];
const char *str = "this is a str";
int i, j, tmp, sum = 0;
tmp = strlen(str);
for(i = 0; i < 1023; i++) {
for(j = 0; j < 15; j++) {
sum += matrix[i][j] + tmp;
}
}
B段代码
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j][i] + strlen(str);
}
}
问题点数：100、回复次数：35Top
1 楼hziee_（）回复于 2006-10-08 22:41:07 得分 0
B段代码
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
int temp = strlen(str);
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j][i] + temp;
}
}
肯定比较好。
Top
2 楼iambic（）回复于 2006-10-08 22:50:39 得分 0
1题，if (*piterator & 0x80 != 0)应该加个括号：
if (（*piterator & 0x80） != 0)
别的看不出来。
2题，研究过排序算法的人来说吧。我不懂。
3题，好像A段代码好点吧。是不是这样定义数组更好些：
int matrix[15][1023];
或者
int matrix[16][1024];？
还是熟悉计算机的高手来吧。
tmp也不用每次都加吧。
没说什么，其实就顶个贴而已。^_^Top
3 楼neoadane（乌云）回复于 2006-10-08 22:52:40 得分 0
呵呵，谢谢～Top
4 楼fflush（stdin）回复于 2006-10-08 23:30:57 得分 0
第3题A段代码更好，因为A的局部性更好，反映在体系结构上就是cache的命中率更高，因此比B要好很多。Top
5 楼laiwusheng（风清扬）回复于 2006-10-09 07:20:30 得分 0
markTop
6 楼superskilledman（）回复于 2006-10-09 10:53:25 得分 0
你们什么时候给baidu投的简历啊？
什么时候他通知的在线笔试啊？
为何我没有接到通知呢？Top
7 楼superarhow（苏泊尔耗）回复于 2006-10-09 11:16:30 得分 0
第一题真正的bug是
if (*piterator & 0x80 != 0)
{
piterator++;
}
这里没有考虑是否是最后一个字节就加了1，假设输入的串是：
char a[] = {0x80, 0};
那么在piterator++之后，for循环又会++，就漏掉了那个0，而去判断一个非法的地址的值是不是等于0，就瓦了。Top
8 楼OOPhaisky（异化$渴望成功~~）回复于 2006-10-09 11:40:18 得分 0
哈哈，baidu的笔试题目答多了，我发现都大同小异^_^Top
9 楼superskilledman（）回复于 2006-10-09 12:23:00 得分 0
if (*piterator & 0x80 != 0)中0x80是什么意思啊？
好像是一个16进制的数，但是它在这里进行&运算又有什么意图呢？
高手们，帮忙解释一下哈，多谢！Top
10 楼dbjk（独臂剑客）回复于 2006-10-09 12:58:29 得分 0
0X80二进制就是1000000,所以能够判别.
1:&运算要加括号,因为&运算是自右向左的.
2:排序过程中会遇到重复的值,提高效高可以先开始确定Domain让字符唯一,即开始排序前保证都是唯要的,其间可以用KMP算法优法.
3:1023 / 8 = 128
而1025 要分配129字节空间.一级数据缓存大小为16K字节，cache块大小为64字节刚好128.
百度笔试题是不能公开的,LZ不厚道.
嗯,百度对我太远了........Top
11 楼kulongus（公司会计说：零钱太少了，你还是半年领一次工资吧）回复于 2006-10-09 14:02:48 得分 0
mark
Top
12 楼superarhow（苏泊尔耗）回复于 2006-10-09 14:57:31 得分 0
第1题确实要加括号,!=优先级比&高Top
13 楼Richard_Hong（武昌鱼）回复于 2006-10-09 15:41:26 得分 0
markTop
14 楼98440622（民工++）回复于 2006-10-09 15:48:29 得分 0
markTop
15 楼huke1980（飙风）回复于 2006-10-09 15:50:17 得分 0
请教下
一级数据缓存大小为16K字节，cache块大小为64字节刚好128
怎么算出来的Top
16 楼blue_zyb（）回复于 2006-10-09 16:10:48 得分 0
to: superarhow(苏泊尔耗)
可是题目说“汉字用两个字节表示，特点是第一个字节的最高位为1”
那0x8000的第一个字节高位为1，处理为汉字，所以后面的00是属于该汉字的，而不应该作为结束符吧Top
17 楼neoadane（乌云）回复于 2006-10-09 16:44:13 得分 0
to：superskilledman()
国庆之前投的，昨晚上给我通知的，今天早上笔的。。。
做得很郁闷。。。Top
18 楼lwaaa（迦叶）回复于 2006-10-09 16:44:51 得分 0
markTop
19 楼neoadane（乌云）回复于 2006-10-09 17:00:50 得分 0
to：dbjk(独臂剑客)
我觉得程序员之间是应该互通有无的，相信每个人（除了大牛）笔试面试前都会希望能找到点相关资料吧。
还是谢谢你的解答哈。Top
20 楼vsong（房价越来越高，所以，好男人越来越少……）回复于 2006-10-09 17:12:03 得分 0
markTop
21 楼Jerffsan（ayun）回复于 2006-10-09 17:20:52 得分 0
第一题：
经调试得知：&表达式应加(),
if (*piterator & 0x80 != 0)语句是处理汉字Top
22 楼superarhow（苏泊尔耗）回复于 2006-10-09 17:31:43 得分 0
to blue_zyb() :
括号的错误是主要的。至于会不会有0x80,0这样的输入，个人觉得还是应该判断一下，毕竟题目上说了要注意异常情况，偶们不是学院派，不过字符串通常是从外部得来的，出现什么样的都有可能的。Top
23 楼laiwusheng（风清扬）回复于 2006-10-09 17:53:07 得分 0
markTop
24 楼xiaov007（）回复于 2006-10-09 18:34:22 得分 0
好热闹啊:>发表点意见。
第一题改为：
if ((*piterator) & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
*piterator += 32;
}
感觉原来的表达式相当与：*（piterator & 0x80）Top
25 楼shareyao（）回复于 2006-10-09 19:32:13 得分 0
同样mark!Top
26 楼dbjk（独臂剑客）回复于 2006-10-09 22:13:54 得分 0
To neoadane(乌云)
你误会了我的意思，哦问一下你属于那个地区的，如东北，西南，或东部之类的，就是你大学所在地区。Top
27 楼houdy（致力于图像/图形领域，成为有思想的程序员）回复于 2006-10-09 22:47:22 得分 0
对于第一个问题，我在我的BLOG中进行了深入的分析：
http://blog.csdn.net/houdy/archive/2006/09/24/1271448.aspxTop
28 楼dick248（）回复于 2006-10-09 22:56:43 得分 0
mark
Top
29 楼neoadane（乌云）回复于 2006-10-10 00:01:53 得分 0
to:dbjk(独臂剑客)
呵呵，中部吧，怎么了？Top
30 楼dbjk（独臂剑客）回复于 2006-10-10 00:19:09 得分 0
to:neoadane(乌云)
------------
我还认为你是四川西南地区的呢，没什么问问而已，祝你好运。Top
31 楼neoadane（乌云）回复于 2006-10-11 23:15:03 得分 0
呵呵，3x！Top
32 楼caoyuflyin21st（木头人）回复于 2006-10-12 15:35:43 得分 0
if(mark)
...
else
...Top
33 楼yuanxiaofei（）回复于 2006-10-12 16:42:41 得分 0
if ((*piterator & 0x80 !)= 0)
{
piterator++;
}
是为了跳过汉字的第二个字符。
看不出还有什么bug?
高手指教，详细啊，很菜，不详细看不懂Top
34 楼Dugowe（我不是火星人,我家狗狗才是..）回复于 2006-10-12 17:53:16 得分 0
markTop
35 楼IMGGTOO（寻找自己的远方）回复于 2006-10-12 22:23:07 得分 0
赶回时髦,也来个
mark!!!Top
