【10.13技术笔经】
第一题：简要说明树的深度优先、广度优先遍历算法的特点
第二题：一个复数相加的编码挑错题 。
程序如下：
1 typedef {
2 int num;
3 int imag;
4 }Complex_t;
5
6 int alloc(Complext_t * a,int num){
7 a=new Complex_t[num];
8 if(a==NULL){
9 return -1;
10 }
11 return 0;
12 }
13
14 unsigned long long compute(){
15 Complext_t * a;
16 int num,pos;
17 unsigned long long sum;
18 cin>>num;
19 if(alloc(a,num)<0){
20 return -1;
21 }
22
23
24 cin>>pos;
25 while(pos26 cin>>a[pos]>>a[pos];
27 cin>>a[pos+1]>>a[pos+1];
28 sum+=a[pos]*a[pos]+a[pos]*a[pos];
29 sum+=a[pos+1]*a[pos+1]+a[pos+1]*a[pos+1];
30 pos+=2;
31 }
32 return sum;
33 }
参考他人答案(不一定正确)：
第六行：Complex_t *变为Complex_t * &
去掉第八至第九行。因为根据C++99new不再返回NULL，而是throw std::bad_alloc
18行的cin没有检查()是不是返回true
19行应该用h围绕
24同理于18行
25行的条件可能导致越界访问，所以应该改为pos
26,27同理于18行
第三题：告诉内存大小和cpu速度，计算可能的程序运行最长时间
问题是一个1K内存和1MHz和CPU(意味着它1秒钟能改变10^6次状态)，问如何在不死循环的条件下让它最长时间的运行，而且是因为某个状态退出的。可以假设你的条件。
(一点没看懂，参考他人解答吧!)
一 开始我毫无头绪。最后终于醒悟，应该用最最底层的办法做。就是在内存放着一段代码，就这样让它跑。怎么让它跑得最长又不死循环呢?我想应该是让除了代码之 外的所有内存在一个周期内加一位，也就是说把剩下的内存看作一个巨大的整型，正如int是32位一样，这个内存区域是XXX位。好了，我假设CPU是16 位的8086，初始状态寄存器全部是0(考试的时候我犯傻了，居然写32位x86)。
程序段放如下编码：
start:
inc al 1B
jno start 3B;不溢出则重新增加
xor cx,cx 2B
overflow:
movb al,[data_start+cx] 3B;data_start是数据起始地址
inc al 1B
movb [data_start+cx],al 3B
xor ax,ax 2B
jno start 3B
inc cx 1B
jmp overflow 3B
于 是代码段使用了1+3+2+3+1+3+2+3+1+3=22B，还剩1024-22=1002B内存用于数据存储。另外还有1B的寄存器，所以是 1003B的存储区域。另外假设改变内存状态和改变寄存器状态一样只花一个周期，还有忽略别的消耗(比如上面的xor cx，cx)这样状态会改变2^1003次，所以最长时间为2^(8*1003)/10^6。上面这段代码会在越界访问的时候退出。
第四题：复杂项目的组件编译依赖，设计一个快速算法并计算复杂度
说的是一个系统有N个组件组成，N个组件之间有依赖关系。为了解决依赖，必须确定编译的顺序。问算法。
其 实这是著名的穿衣问题，问题是一个人有内裤，裤子皮带……这些东西，问人应该怎么穿才能不变成超人!所以解决方法也是一样的，就是拓扑排序。拓扑排序是先 对图中所有子节点进行广度优先的遍历(郑K说是深度遍历，我敢肯定他错了，因为深度遍历得到的是一棵树，而不是几棵，依赖关系可能不只是一棵树的)，然后 在遍历同时标记遍历的起始时间和结束时间，然后对起始时间进行排序。
第五题：写个c程序，返回字符串中最长数字字符串的长度和地址，不能用标准库函数
第六题：设计个系统，存储100亿个url和属性信息，并可以更改属性信息和查找url，快速搜索站点的所有url及信息 。特点是分布式数据库，条件是快速访问。
【2010非技术类笔试题】
1、09年的第一道图形推理题，不过我不知道正确答案，知道的童鞋请帮忙告诉一声，我选的C
2、还是往年论坛上有的非技术题，只是换了下字，分析2010年的.网络购物，宠物用品和化妆品
3、说出10种易拉罐为什么做成圆柱形的理由
4、一个八边形，各角觉有一小虫，爬呀爬，计算终点之类的，题目太长，没记住，抱歉。。。
5、3个男人、2个女人一起渡河，只有一条船，每次只能渡两个人
女人要求：不能让一男一女同时一起过河
男人要求，每人只能划一次浆
如果只有一个划桨的，阿特第一，本第二，**第三。。
问：用最短的过河次数推测，谁最后一个划桨渡河?
6、有两张标准版的世界地图，一张的比例尺是1：3600万，另一张的比例尺是1：2000万，将较大的一张完全的覆盖较小的一张(两张都是平整铺开的情 况)。请问：取出一枚图钉，是否可以选择到一个点，按下去，刺穿的两张地图的点对应的是同一个真实地球上的点?不论是或否，请给出你的思考和论证过程。
7、说明一些你对互联网和百度产品的理解、分析之类的
8、你认为这次测试是否能够基本反映出自己的水平?你对自己今天的答案满意么?如果不是，你还有哪些补充?
【2010.10.13用户体验部笔试题】
第一部分:答一题，多答不限
1.方差分析的统计原理和运用条件
2.什么是社会网络研究?它的主要观点是什么?有哪些应用?
3.市场调研过程分为几个阶段?各个阶段的核心任务和目标是什么?
第二部分：三题必须都答
1.用户体验研究领域有哪些专家?用一句话描述他们的主要观点?
2.用户体验研究和产品运营之间的关系
3.交互设计是什么?一个好的交互设计具备哪些特征?举例说明。
第三部分：答两题，多答不限
1.简述用户体验研究方面的企业实践项目?(没有可以不写)
2.有用户提出反馈“搜索结果页面，需要将页面拖放到最底才可点击下一页，可否实现翻页置顶或自动反应功能”，如何处理这个问题
3.百事可乐攻击可口可乐时，曾经在马路上随机做双盲实验，多数人认为百事可乐比可口可乐好喝，百事可乐公司以此为据进行推广。可口可乐也在马路上做双盲 实验，惊奇地发现，多数人认为百事可乐比可口可乐好喝，因此，可口可乐公司下定决心改进产品，推出新产品“newcoke”，没想到“NEWCOKE” 推出后消费者抵制，并且要求推出原来的口味。请分析“newcoke”失败的原因。
4.统计关键词的搜索量时(有一个图，统计200720082009关键词搜索量)，有人说“......，因此，当台风来时，人们就更关注变形金刚”，设计一个研究说明结论正确与否。
第四部分：附加题
有四道逻辑推理题
估算你所在城市的出租车数量?简述估算理由。
【2010运维web开发两道笔试题】
1.推理：24个人，每人至少养一种宠物，养鸟、狗、鱼、猫的分别为13、5、10、9人，同时养鸟和狗的2人，同时养鸟和鱼、鸟和猫、鱼和猫的各为4人，养狗的既不养猫也不养鱼。问只养一种宠物的总共几人?同时养鸟鱼猫的几人?
2.找程序的错和不足：
inttest(char*value,intvalue_len,intflag)
{
chartemp_buf[BUF_SIZE];
sprintf(temp_buf,value);
chartemp_new_buf=newchar[value_len];
if(flag)
{
strcat(temp_buf,"flagistrue");
printf(temp_buf);
return1;
}
[]temp_new_buf;
return0;
}
【2010非技术类笔试】
一、选择题
30道，共60分
主要是逻辑(verbal类、推理类，无数字题)和互联网商业常识(比如市场份额最大的搜索引擎)。
二、论述题
1道，40分
对推广“百度知道”产品的思路和方法。
难度不大，时间充裕。很多人提前交卷的。
【2010年运维部笔试及相关说明】
这次应聘的是运维部的数据库DBA，实际上运维部的所有岗位试题是一张卷子，五个简答，一个算法完善程序，一个系统设计题。
这次百度是分部门考试的，每个部门一张卷，不是像以往的好几张卷子。
由于公司的保密性以及对其他同学的公平性考虑，这里不透漏具体题目，但是可以告诉大家方向。
之前一直以为会考很多算法，后来证明是错误的
运维部的备考还是以运维岗位的需求为主题，重点不是算法，而是系统，数据库，以及简单的算法知识。
整张卷子只有一道题目要写程序，而且是比较基础的。
其他简答题里，有一道算法题，只是简答，EASY;另外有关于linux的文件系统的题，性能优化，数据库基本概念，以及硬件处理能力相关知识之类
最后的设计题，也是和运维紧密相关的，当然是数据库和系统架构知识的结合，不是很细。
希望对大家有帮助。祝考完的同学好运!
【分享13日笔经】
1.简述深度优先及广度优先遍历算法，并说明非递归实现的特点
2.程序找错，一大段。
3.假设有一台迷你计算机，1KB的内存，1MHZ的cpu，已知该计算机执行的程序可出现确定性终止(非死循环)，问如何求得这台计算机上程序运行的最长时间，可以做出任何大胆的假设。
4.大型软件有很多组件，编译时存在复杂的依赖关系，比如N1和N2存在依赖关系，要编译N1必须先编译N2,假设存在N<1000个组件，之间存在复杂的依赖关系，但不存在依赖环，问采用怎样的算法来构建编译规则，说明算法的复杂度。
5.写一个函数intMaxContinuNum(constchar*inputstr,char*outputstr)
找出一个字符串中最长的连续数字串，返回最长数字串的长度，并将最长字符串存入Outputstr指定的地址，
如，abcd1234abd123abcd123456789,最长连续字符串为123456789，长度为9
6.有100亿个url，要求设计一个系统，能实现url的添加、删除、更新，并能查看url的内容
【百度2010商务搜索部
