整理的百度面经

aftyingjiesheng

整理的百度面经

zz
& h" ~, ^. o$ s5 x0 V% x  a

- I+ d; z$ N: t一面1. 网络编程经验：
   如何判断一个http请求，一个客户端请求已经结束；如何处理服务器多线程
   获得一个http请求后，是如何处理的？返回什么？有没有试过返回图片？
   服务器给客户端请求时，是用什么函数写？服务器如何获取客户端请求，用什么函数
- ^+ O- I& [/ Y! G9 s/ x   （需要函数级别的连接有一个认识）
- x7 g+ {5 k7 o. n) ~$ P2 l6 F0 l
2. cv操作是什么函数 cv_init, cv_wait, cv_signal
: a9 V, |5 u, u& d7 C
) r4 ~* D) }, C3. 有一些关键词点击次数的文件，如何输出最多点击的一百个（当时应该回答，组织一个100个元素的最大堆）

4. 相交链表，如何找相交点（不能要标记）
   第一个头遍历到尾，知道他的长度；第二个头遍历到尾，知道他的长度。这样知道两截链表在交点前的长度，长的先走几步，然后一样长了，再轮流下走，就会相聚，相遇节点就是相交节点）

5. 有些文件，频繁访问在磁盘里头的，现在要放到内存中了。采用什么策略来决定哪些放到内存中？如果是一些url文件，放在内存后，如何快速的找到某个url的位置（采用字典序或者b树之类树状结构来组织） 如何快速找到哪些文件太久没人访问了，把他替换出去？（再那一棵树，记录树里每个位置url的访问时间；同时，那个url树的节点，也有这个时间树的对应的位置信息。时间树采用最大堆组织。要替换出去时，就从树顶取走节点，并且从中获得这个节点在url树对应位置，把他从url树中取走。当url被访问时，由于url树节点有时间树的位置信息，所以也很快找到对应节点在时间树的位置，然后把他的访问时间更新，然后做堆调整，每次堆调整为logN）
5 Q+ q! P2 E) @' P
6. c语言相关：内联函数的好处？非内联函数被调用的过程是怎么样的？
   int,short,char的struct，这几个数应该怎么放，内存小？怎么防止头文件被include多次？

8 C! c1 k. p' M8 [" i  e7. 有没有什么问题想问的
8 linux 网络查看的命令
. M, ?9 R5 E% ?& h& o1 e
7 Q6 d# l  R+ |二面
! \& ]/ c2 a5 N- _7 Z1. 介绍一个项目
, U* y) n9 y8 B; u; t8 t$ c
" b0 F( `. X: W6 L0 v" E2. 2.5亿个int数，可能有相同的。统计出这里头不同的数有多少个？只有2g内存。
（2.5*1000 000 000 * 4 =1G）
统计数-用hash，key是数，value是1或0，标记是否出现。
如果key就是那个数，那么找一个数的时候，要遍历hash才知道有没有，慢（就是如果hash紧凑，慢）。
解决方案：把key作为连续的（就是hash是稀疏的，有个key值没有存在这2.5亿个数中），像数组下标一样，那么要访问第n个数，直接到第n个去看，复杂度是O(1)
但是，如果连续，2.5亿个数，范围很广，而每个key用int存，会很大量，内存不一定够。
解决方案：每个key用一位bit来标志。即数字1放在第一个bit上，数字2放在第二个bit上。看第n位在不在，就找一下第n个bit是1，还是0
" i9 i- `0 e& p" H0 g- q; w2 ~具体方法：char a[] 数组。假设找3，那么3在3/8--0...3,所以在a[0]中，找第3个bit，如果是0，就设置为1。最后看看a[]的二进制表示有多少个1就有多少个数

3. 海量数据，在mysql中，cpu占用率很高。如何解决？
5 g% [% W, s1 n4 P1.show processlist，看哪个sql查询的多，建索引（问：建立联合索引时，要考虑什么，怎么建（哪个在前，哪个列在后？）
* s& g( l8 R; j, Z6 l& j; ~6 f0 I1 T2.如果老是在拷贝到临时表，就改配置，把临时表内存改大些
3.还有什么方法：
1）分布式数据库 （问：如果你来设计分布式数据库，你会怎么设计？）
2）使用缓存   （问：如果缓存中的数据，被删除或跟新了，数据库怎么判断这个缓存的数据不能用了，是脏数据？）（不懂）
问：什么情况下cpu会高？（内存不足）为什么内存不足cpu会高（频繁io读写）
" |  A9 O& H2 r5 T% I% M
4. n个无序int，（有正有负），给一个数v，如何找出其中的a+b=v的两个数
（我的答案是：排序 O(nlogn)，记录序列中，0，大于v，小于v的3位。
尝试最小的和最大的，最大不行，次大。。。，找到某个，加起来小于v了，停止
. X* q. X' Z; p  C( J; @+ e尝试次小的，从上次大头停止的位置开始尝试
' l8 H8 Z5 U6 ~1 ?1 s, k' L---尝试范围两头不断缩小，复杂度为n）

5. 网络相册，一个人可以有多个相册，一个相册有多个图片，如何快速实现增删查移动等操作。web页面上，图片是翻页显示。
; j. F4 S, h9 d; y. L, u! U（我回答：数据库记录：usr_id, book_id, item_id, position。相片放在磁盘上，目录为position/usr_id/book_id/item_id
- F* X+ B/ ~8 a& |0 b一次查两个操作：1）数据库查找2）根据位置取图片
/ A% `% Z! Z( s9 w: L3 P$ f
如果用户提取某个相册的所有图片，先给他第一个相片和所有item_id列表。然后用户翻页了，在客户端通过javascript能够知道翻的是哪个item，把item_id，book_id, usr_id发给服务器，服务器根据这个到目录下去找）
. ~1 }1 D6 e+ ?& b+ \（你这种设计会有什么问题？（答不上来。。。）（如果用户频繁翻页，那么服务器上会不断地在传输图片）（如何解决？）
1 ?& `1 [  a( R, s6 M. b2 a
第五题我想不出好办法，我觉得一般他们都show thumbnail
就是预览小图片不把原始图片show在页面上，点击后才能看单个图片
) \* C" ?9 H. E* N" G  _
& P4 l5 g1 c5 G4 s& w
6. Unix系统里，一个简单的print hello world的c程序，从./a.out执行到屏幕打印出来这句话，是什么过程
（1.读elf，会从相对地址，计算出各个symbol的在进程中的绝对地址。然后找到入口main函数
- q" A4 |+ q4 f  1.用到std的库，所有有run time load。
  2.然后是print调用的进栈
" T. f/ Z- b* d. X  3.然后是系统调用，当前进程被挂起。系统调用会调用驱动。。。（内核切换，用户态到内核态）
- N" f" M7 N+ m2 f3 ~) Y( e  4.内核处理完再唤醒当前进程。（切换）
6 w# j1 c- d7 k2 M: B  5.print调用完毕，退栈
  6.main函数退栈
" C5 V# ~# m% L: a/ U$ I- [4 q）
问：哪个进程来调用的main？（不知道）
应该是当前运行a.out的这个和用户交互的shell作为父进程，然后父进程fork子进程，子进程和父进程一样，然后调用execv会load执行文件，和把参数传到main的堆栈中
. z# T" R  Q4 b+ S
$ Q) ^7 s( d2 p8 \+ H, g' z7.socket编程，要注意什么问题
（服务器的serversocket的基本模型。
但是大量请求，会不能及时响应。所以要多线程。
一个监听线程，多个服务线程。服务线程一开始起来都阻塞在存放请求socket的tasklist上。wait
监听线程接受到client的socket，放入tasklist中，signal唤醒一个服务线程。服务线程处理它，并把它从list中移走
注意问题：tasklist的存放的请求socket是会被放和移走的，消费者生产者问题。所以要synchronized来互斥？）
& ^1 b' L1 T! v" g! i! S
. Y* `8 j, W: d3 N三面
6 Y% U  [1 s1 h9 D

$ g3 p3 H7 Q  v6 X: u# K2. fread的过程（文件系统-内核。。。）
! H. F+ x; y- D, ]' i6 m' ^: E3. 主DB在接到数据更新后同步到后台DB，如何避免网络丢失之类的问题
' z( U. _  I" M3 i. ?  m* @$ {" J（参考答案1：传的是sql语句，接到后回ack，如果主DB发现一段时间没有回，重发；其实TCP传输，就保证了不会漏数据，所以不会考虑这个问题的）
（参考答案2：每次传sql语句和当前版本号，然后后台DB会对比版本号是不是正确，发现落后就发数据请求。主DB保留每次版本号更新关联的sql语句）
( _# o7 P9 R; ^; e7 r4. N个bit，如和判断其中有多少个1.（时间复杂度小于N）
! h7 Q- r, H5 b) Y" o7 [" Q预存一个2的8次方大小的数组，每个数组值是，这个下标的数的二进制的1的个数，例如：
a[0]=0, a[1]=1, a[2]=1,a[3]=2....a[2^8-1]=7 （以空间换时间）
, Y* w9 I) {6 T: [1 T
然后一个byte一个byte的读，看看他的值，直接以这个值为下标去数组看他的1的个数
& A- p& ?" M$ K3 m* x: ^

另一个方法：
; \7 ~; ^$ M& E/ k8 o' j2 U
while(v){
v &= (v-1);
num++;
}
# |. _, W7 _! K+ a1000 & 0111 = 0, 所以每&一次，不为0，说明有1个1，&到为0为止，num就是1的个数。复杂度为1的个数。

6 `. h: C0 q* y0 bZz
/ t4 ]3 j7 R0 Z/ |) y& [4 y该内容转载自网络，版权归原作者所有。
( }' I& ?% v$ F5 C2 G
……
. ~: b; [$ H6 x3 j6 j# b" l$ U- Zhttp://bbs.aftjob.com/thread-164201-1-1.html
; z* J. E, z. C* ^  h* w1 A

" h0 D8 x- Z3 f5 G( \' e- u. `百度(Baidu)求职俱乐部
  ?# |7 p# X+ y& \http://bbs.aftjob.com/group-4-1.html