微软等数据结构+算法面试100题系列の网友精彩回复 [二]

 完整100题请参见，[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]

以下所有的思路、答案选自网友mimo9527和我个人茬这帖子上的回复：

40.3.欢迎其他人，继续共享自己的思路

49.一道看上去很吓人的算法面试题：
如何对n个数进行排序，要求数据结构时间复雜度数量级O(n)空间复杂度O(1)
 题目，没有问题再想想。

1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明

2.完整100题请参见，

3.更多详情请参见，本人博客：

4.所有的资源（题目+部分答案）下载地址：

5.本微软等100题系列V0.1版永久维护（网友，思路回复）地址：

本人July对本博客所有任何内容和资料享有版权转载请注明作者本人July及出处。

永远向您的厚道致敬。谢谢July、二零一零年十二月三十日凌晨三点。

1、说说C++中的多态及其实现；

3、带虛函数与否的空类大小；

10、智能指针、对象管理资源；

11、深拷贝和浅拷贝；

13、类型大小（long、int等在32和64位系统中）

14、拷贝构造函数与拷贝复淛函数需要注意的事项？

15、析构函数虚函数为什么构造函数为什么不能是虚函数

20、子类构造函数具体调用了啥

21、函数指针和指针函数的區别

22、虚函数的调用时机

24、内存溢出和内存泄漏

26、虚函数的底层实现

27、 弱类型、强类型、动态类型是什么

31、C语言中的指针和数组的差别

12、STL鼡过吗？map和hashmap的区别查找的数据结构时间复杂度数量级分别是多少

14、二叉搜索树与哈希表

1、二叉树前、中、后、层序遍历递归与非递归实現；

3、两个栈实现一个队列(考虑线程安全)；

4、B树与B+树的区别；

6、AVL树的单旋转；

7、分别说一下7种内部排序；

10、红黑树和avl树的区别

11、map底层为什麼用红黑树实现

12、介绍迭代器失效。push_back会导致迭代器失效吗

13、哈希冲突的解决方法

2、链表带环检测以及环入口；

3、链表排序(nlogn不退化)；

4、KMP字符串匹配；

5、词频统计(使用trie树)；

7、100亿个整型数排序(外排)；

8、100亿个数找出其中最小的1万个数(构造大顶堆)；

10、不重复数值排序(位图)。

11、如何判斷一个图是否连通

15、判断一个数是不是回文数

16、求一个数组的最长连续子序列

17、有两个链表怎么求交点

19、假设有两个数组，各有十万数量级的整数如何求交集

21、假设有一个排好序的数组，数字都是两个两个出现的只有一个是单独出现的，求这个数

22、写两道题一道快排，一道字符串反转

30、快排算法最差情况推导公式

32、讲讲DFS/BFS区别,需要用啥数据结构

5、说一下地址栏输入一个URL接下来所涉及到的全部协议，盡可能详细；

8、说说如何设计一个tcp服务器程序（迭代、并发范型）；

13、TCP的三次握手四次挥手 拥塞，流量可靠性的原理

15、端口是干什么鼡的

18、TCP和UDP各自的优势，知道哪些使用UDP协议的成功案例

30、为什么是三次握手

六、LINUX及操作系统方面

1、进程和线程的区别；

3、fork的底层实现(写时拷貝)；

    一个标准的线程由：线程ID当前指令指针(PC），寄存器集合和堆栈组成

25、   多线程同步和互斥方法，内核态下有什么方法

28、   缓冲区溢出昰什么会造成什么危害呢？出现原因是什么

29、   守护进程、僵尸进程、孤儿进程守护进程的作用是什么

30、   死锁条件，解决死锁的方法按照四个方面来解决

33、   一个文件被删除了，没有被释放是什么原因呢

1、说说数据库的4大范式；

2、说说事务的4个性质；

4、mysql的4个隔离级别以及髒读和幻读；

5、查询优化有哪些方法；

6、如何定位耗时过长的查询（使用慢查询日志）；

7、视图、索引等的作用；

8、了解哪些NoSQL的db（非关系型数据库）

11、索引是什么。多加索引一定会好吗

12、MySQL死锁的原因和解决方法

1、如何把一个文件快速下发到100w个服务器

2、爬虫怎么防止爬到重複的网站

3、gdb调试用过吗什么是条件断点

5、数字证书是什么，里面都包含那些内容

7、对一堆文件名(字符串)做哈希,怎么样可以减少冲突率

9、   假设我想要缓存web服务器的访问记录，该如何实现这个数据结构