百度武汉研发笔试题

百度2015武汉研发笔试题

　　一、简答题

　　1.列出至少6中内排序方法，并写出相应的时间复杂度和空间复杂度以及稳定性;

　　2.多线程中的同步互斥方法都有哪些?

　　3.进程间通信的方式有哪些?哪种是效率最高的.?

　　Socket，pipe，共享内存，消息队列，信号，信号量

　　效率最高的是：共享内存。

　　(360面试中问到了共享内存在系统中是如何实现的，答案应该是内存映射)

　　二、编程题

　　1.找出二叉树中任意两个节点的公共父节点。

　　可以使用"Y"型链表的方法来解决(一家之言)

　　2.删除链表中重复的元素，只剩下出现一次的元素。

　　这个题目的关键是连表中只要出现两次的元素就全部删除，一个不剩，实现比较简单。

　　3.判断一颗二叉树是不是平衡二叉树

　　这个一般的方法会有很多重复计算的情况发生。

　　较简单的方法如下：求出根节点的最大深度与最小深度，则最大深度与最小深度之差dis就是树中任一子树的深度差最大值，所以只要dis小于等于1，此树就是平衡二叉树。

　　三、系统设计题

　　这个记得不太清楚了，大概就是为一个分布式系统设计一个内存cache，来减少查找的延时。看过memcache源码的童鞋应该比较理解。