知识点整理

目录

计算机网络相关... 4

1、TCP 和 UDP 的区别？... 4

2、TCP三次握手、四次挥手... 4

3、 TCP滑动窗口机制... 5

4、 TCP拥塞控制机制... 6

5、            TIME_WAIT状态的产生、危害、如何避免？... 7

6、            为什么 TCP 叫数据流模式？ UDP 叫数据报模式？... 7

7、TCP建立连接为什么需要三次？断开连接又为什么需要四次？... 8

8、请画出 TCP 的头部， tcp头多少字节？哪些字段?(必问)8

9、 connect会阻塞，怎么解决?(必考必问，提示：设置非阻塞，返回之后用select检测状态)9

10、TCP/IP 三次握手，accept发生在三次握手哪个阶段？攻击... 9

11、udp调用connect有什么作用？... 10

12、列举你所知道的tcp选项，并说明其作用。... 10

13、流量控制与拥塞控制的区别，节点计算机怎样感知网络拥塞了？... 10

13、socket模型... 10

14、 socket在什么情况下可读?. 10

15、  如果select返回可读，结果只读到0字节，什么情况？... 11

16、keepalive 是什么东东？如何使用？... 11

17、 大规模连接上来，并发模型怎么设计... 11

18、DNS使用什么协议？... 11

19、traceroute命令有什么作用？原理是什么？... 12

20、简述一下ping的原理。... 12

C/C++相关... 13

1 虚析构、模板和宏... 13

2 虚函数实现机制... 13

4 extern 关键字有什么用... 14

5 malloc和new的区别，能否malloc(1.2G)14

6申请4G内存... 15

7、菱形继承... 15

8、            memmove实现... 15

9、            函数调用入栈顺序、返回值... 15

10、BBR. 15

11、怎么定位跑飞... 15

12、字节对齐... 16

13、bitmap. 16

14、*（int *） 0  = 0 报错，操作空指针... 16

15、char *(*a)[3][4]   sizeof(a) = 4. 16

16、（int）(int *)0+4  16位编译器 8，32位编译器 16. 16

17、去掉字符串的空格并返回空格个数... 16

18、字符串反转... 16

19、static、 const. 16

20、         大端与小端的概念？各自的优势是什么？... 17

21、         指针和引用的区别？... 17

22、         C++的内存分区？... 17

23、         C++对象的内存布局。... 18

24、栈溢出的原因及解决办法。... 19

25、内存泄漏怎么产生的？如何避免？... 19

26、堆和栈的区别？... 20

27、const的含义及实现机制，比如：const int i,是怎么做到i只可读的？... 20

28、OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。... 20

29、valitale的含义。... 20

linux以及操作系统相关... 22

1                内存池实现... 22

2 进程间通信机制... 22

3进程与线程的区别，共享的数据... 22

5 进程的内存空间... 23

6、软链接、硬链接... 23

7、            共享内存 mmap 、shmc. 23

8、            哪几种锁，条件变量... 24

9、            同步与互斥... 24

10、         动态加载dll和静态加载dll的区别... 24

11、         一个进程由哪些方面构成... 24

12、         守护、僵尸、孤儿进程的概念... 25

14、linux下你常用的命令有哪些？Linux ps命令，以及看内存当前使用状态的命令... 25

15、系统调用与库函数的区别？... 26

16、死锁产生的四个条件，死锁发生后怎么检测和恢复？... 26

17、进程调度算法有哪些？Linux使用的什么进程调度方法？... 27

18、core产生的原因，如何调试定位问题？... 27

19、阻塞IO、非阻塞IO、同步IO、异步IO的区别？... 27

20、分时系统与实时系统的区别？... 28

21、除了sleep之外，usleep()也是linux系统调用，它号称自己是微秒级的，你相信它真的有这么快吗？为什么？     28

22、怎么确定内存中栈的生长方向... 28

23. gdb调试时如何找到出错的地方... 28

24. 你知道负载吗？其实就是load。... 29

25、 32位系统一个进程最多多少堆内存... 29

26、  写一个c程序辨别系统是64位 or 32位... 30

27、   写一个c程序辨别系统是大端or小端字节序... 30

算法与数据结构 （手写代码实现）... 32

1、            hash如何取模，避免冲突... 32

2                、map的实现机制是怎么样的啊... 32

2、            vector的删除和插入  vector和list的区别... 33

3、            单链表翻转（两个指针如何实现）、查找、删除、插入以及双向链表、有序链表合并... 33

5、常见排序算法的实现以及稳定性（快排跟归并考的很多），快排复杂度推导... 35

6、 二分查找（注意边界条件）... 36

7、 链表判断是否有环，环的入口，两个链表是否相交（快慢指针）。... 36

8vector/map/multimap/unordered_map/unordered_multimap的底层数据结构，以及几种map容器如何选择？     40

4. 统计10万个单词中出现频率最高的1000个... 40

5. 求1000亿个数中的最大1000个... 40

10、10亿个整数，随机生成，可重复，求最大的前1万个。  分治法+hash+多路归并排序... 40

10、         指定一个数组，求2个数的和等于指定的和（某一个数），如果是3,4,5，n个等于个的和（某一个数）呢？（可以看作背包问题）... 41

12、手写代码，判断两个树时候相同（结构相同，内容相同）。... 42

13、大整数加、减、乘、除、求模运算实现... 42

13、         判断一个整数是否是2的整数次幂.(n&(n-1))51

15、B+树... 52

16、 最长递增子序列（nlogn的算法）... 52

17 、跳台阶问题... 55

18、 已知一个单向键表，但不知道它的头指针，给出链表中一个节点的指针，并且已知该结点的后续节点不为空，要求删除该结点... 57

19、C++ STL中vector内存用尽后，为啥每次是两倍增长，而不是3倍或其他倍数？... 58

20  vector怎么实现动态空间分布... 58

21 hash， 任何一个技术面试官必问（例如为什么一般hashtable的桶数会取一个素数？如何有效避免hash结果值的碰撞）... 58

22、100亿个数，求最大的1万个数，并说出算法的时间复杂度。... 58

23、将一个4字节的整数的二进制表示中的001替换为011，输出替换后的整数。... 59

24、         将一个数组右移几位，比如数组为1 2 3 4，右移一位即为4 1 2 3。... 59

25、输入一个表示十六进制的字符串，转换为十进制的整数输出。... 59

26、 在两个有序数组中找出共有元素... 59

27、给定两个数组a和b，求所有在a数组中不在b数组的元素；... 61

28、未知大小的文件，翻转整个文件... 61

29、各类排序：大根堆的实现，快排（如何避免最糟糕的状态？），bitmap的运用等等... 61

其他... 61

2 如果内存中有个cache存储qq号和最近登录时间问怎么样做hit和淘汰... 61

3 shell读文件并把文件的内容输出到控制台... 61

4. 某文件的第二列内容为数字，请用awk求出这些数字的和... 62

5. 按层次遍历二叉树... 62

6、问题:有两个文件,各放了100万个QQ号,请找出两个文件中相同的QQ号,用SHELL脚本实现... 62

7、C/C++方向：有N个大小为G的存储单元，用户在不断上传数据，每次上传数据的大小v是随机的，请写一个系统，把上传的数据分配给各个存储单元，使得每个存储单元的使用率和写负责相对均衡... 63

8、千万级的用户，提供一个服务，该服务有很多模块，现在有一个底层模块需要优化，问怎么实现，在不影响其他服务模块以及用户体验的情况下... 63

9、最有难度的一个题目：一个每秒百万级访问量的互联网服务器，每个访问都有数据计算和I/O操作，如果让你设计，你怎么设计？... 63

10、设计一个洗牌的算法，并说出算法的时间复杂度。... 63

计算机网络相关

1、TCP和 UDP 的区别？

TCP是稳定、可靠、面向连接的传输层协议，它在传递数据前要三次握手建立连接，在数据传递时，有确认机制、重传机制、流量控制、拥塞控制等，可以保证数据的正确性和有序性。

UDP是无连接的数据传输协议，端与端之间不需要建立连接，且没有类似TCP的那些机制，会发生丢包、乱序等情况。

TCP是数据流模式，而UDP是数据报模式。

2、TCP三次握手、四次挥手

3、 TCP滑动窗口机制

TCP是通过滑动窗口来进行流量控制。我们知道，在TCP头部里有一个字段叫 Advertised-Window（即窗口大小）。这个字段是接收端告诉发送端自己还有多少缓冲区可以接收数据，于是发送端就可以根据这个剩余空间来发送数据，而不会导致接收端处理不过来。
下面是发送端的滑动窗口示意图：

接收端在给发送端回ACK中会汇报自己的 Advertised-Window 剩余缓冲区大小，而发送方会根据这个窗口来控制下一次发送数据的大小。下面是滑动后的示意图（收到36的ack，并发出了46-51的字节）：

Zero Window：如果接收端处理缓慢，导致发送方的滑动窗口变为0了，怎么办？—— 这时发送端就不发数据了，但发送端会发ZWP（即ZeroWindow Probe技术）的包给接收方，让接收方回ack更新Window尺寸，一般这个值会设置成3次，每次大约30-60秒。如果3次过后还是0的话，有的TCP实现就会发RST把连接断了。

Silly Window Syndrome：即“糊涂窗口综合症”，当发送端产生数据很慢、或接收端处理数据很慢，导致每次只发送几个字节，也就是我们常说的小数据包 —— 当大量的小数据包在网络中传输，会大大降低网络容量利用率。比如一个20字节的TCP首部+20字节的IP首部+1个字节的数据组成的TCP数据报，有效传输通道利用率只有将近1/40。

为了避免发送大量的小数据包，TCP提供了Nagle算法，Nagle算法默认是打开的，可以在Socket设置TCP_NODELAY选项来关闭这个算法。

4、 TCP拥塞控制机制

我们知道TCP通过一个定时器（timer）采样了RTT并计算RTO，但是，如果网络上的延时突然增加，那么，TCP对这个事做出的应对只有重传数据，然而重传会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包，这就导致了恶性循环，最终形成“网络风暴” ——TCP的拥塞控制机制就是用于应对这种情况。
   首先需要了解一个概念，为了在发送端调节所要发送的数据量，定义了一个“拥塞窗口”（CongestionWindow），在发送数据时，将拥塞窗口的大小与接收端ack的窗口大小做比较，取较小者作为发送数据量的上限。
拥塞控制主要是四个算法：

·        慢启动：意思是刚刚加入网络的连接，一点一点地提速，不要一上来就把路占满。

连接建好的开始先初始化cwnd = 1，表明可以传一个MSS大小的数据。

每当收到一个ACK，cwnd++;呈线性上升

每当过了一个RTT，cwnd =cwnd*2; 呈指数让升

阈值ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”

·        拥塞避免：当拥塞窗口 cwnd 达到一个阈值时，窗口大小不再呈指数上升，而是以线性上升，避免增长过快导致网络拥塞。

每当收到一个ACK，cwnd =cwnd + 1/cwnd

每当过了一个RTT，cwnd =cwnd + 1

拥塞发生：当发生丢包进行数据包重传时，表示网络已经拥塞。 分两种情况进行处理：

等到RTO超时，重传数据包

sshthresh = cwnd /2

cwnd 重置为 1

进入慢启动过程

在收到3个duplicateACK时就开启重传，而不用等到RTO超时

sshthresh = cwnd = cwnd /2

进入快速恢复算法——Fast Recovery

             快速恢复：至少收到了3个DuplicatedAcks，说明网络也不那么糟糕，可以快速恢复。

cwnd = sshthresh + 3 * MSS （3的意思是确认有3个数据包被收到了）

重传Duplicated ACKs指定的数据包

如果再收到 duplicated Acks，那么cwnd = cwnd +1

如果收到了新的Ack，那么，cwnd =sshthresh ，然后就进入了拥塞避免的算法了。

5、TIME_WAIT状态的产生、危害、如何避免？

【答】TCP协议在关闭连接的四次挥手中，为了应对最后一个 ACK 丢失的情况，Client（即主动关闭连接的一方）需要维持 time_wait 状态并停留 2 个MSL的时间。
危害：Linux分配给一个用户的文件句柄是有限的，如果系统中存在大量的 time_wait 状态，一旦达到句柄数上限，新的请求就无法被处理了，而且大量 time_wait 连接占用资源影响性能。
如何避免：在/etc/sysctl.conf文件中开启 net.ipv4.tcp_tw_reuse重用和net.ipv4.tcp_tw_recycle快速回收。

6、为什么 TCP 叫数据流模式？ UDP 叫数据报模式？

所谓的“流模式”，是指TCP发送端发送几次数据和接收端接收几次数据是没有必然联系的，比如你通过 TCP 连接给另一端发送数据，你只调用了一次 write，发送了100个字节，但是对方可以分10次收完，每次10个字节；你也可以调用10次 write，每次10个字节，但是对方可以一次就收完。原因：这是因为TCP是面向连接的，一个 socket 中收到的数据都是由同一台主机发出，且有序地到达，所以每次读取多少数据都可以。

所谓的“数据报模式”，是指UDP发送端调用了几次 write，接收端必须用相同次数的 read 读完。UDP 是基于报文的，在接收的时候，每次最多只能读取一个报文，报文和报文是不会合并的，如果缓冲区小于报文长度，则多出的部分会被丢弃。

原因：这是因为UDP是无连接的，只要知道接收端的 IP 和端口，任何主机都可以向接收端发送数据。这时候，如果一次能读取超过一个报文的数据，则会乱套。

7、TCP建立连接为什么需要三次？断开连接又为什么需要四次？

【答】“三次握手”的主要目的是为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误。

例如：client发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达server。本来这是一个早已失效的报文段。但server收到此失效的连接请求报文段后，就误认为是client再次发出的一个新的连接请求。于是就向client发出确认报文段，同意建立连接。假设不采用“三次握手”，那么只要server发出确认，新的连接就建立了。由于现在client并没有发出建立连接的请求，因此不会理睬server的确认，也不会向server发送ack包。

为什么不是两次握手？

“已失效的连接请求报文段”的产生在这样一种情况下：client发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达server。本来这是一个早已失效的报文段。但server收到此失效的连接请求报文段后，就误认为是client再次发出的一个新的连接请求。于是就向client发出确认报文段，同意建立连接。假设不采用“三次握手”，那么只要server发出确认，新的连接就建立了。由于现在client并没有发出建立连接的请求，因此不会理睬server的确认，也不会向server发送数据。但server却以为新的运输连接已经建立，并一直等待client发来数据。这样，server的很多资源就白白浪费掉了。采用“三次握手”的办法可以防止上述现象发生。

“四次挥手”主要是为了确保数据能够完成传输。

因为TCP连接是全双工的(即数据可在两个方向上同时传递)，关闭连接时，当收到对方的FIN报文通知时，它仅仅表示对方没有数据发送给你了；但未必你所有的数据都全部发送给对方了，所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送一些数据给对方之后，再发送FIN报文给对方来表示你同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。

8、请画出 TCP 的头部， tcp头多少字节？哪些字段?(必问)

TCP头部最长60字节，其中包括20字节的固定部分。包括源端口号、目的端口号、序列号、确认序列号，头部长度、窗口大小、校验和等。

     9、 connect会阻塞，怎么解决?(必考必问，提示：设置非阻塞，返回之后用select检测状态)

     当客户端插上网线，但是连接网络失败，也就是说能够获取到ip地址，但是和服务器是ping不通的。这种情况下connect就可能会发生阻塞，因为按照《UNIX 网络编程》中讲解，connect的在进行三次握手，如果失败情况，需要等待75s的超时时间的

原理很简单，就是先把套接字设置为非阻塞，因为在非阻塞情况下，connect的结果是立即返回的，然后我们再使用select或者poll等机制来检测套接字一定的时间，如果在超时时间内不可写，则认为connect失败，然后需要把套接字重新设置为阻塞，当然如果你不需要在阻塞模式下工作，可以不用设置。如上，我们就可以对connect的超时进行可控。

一、connect会阻塞，怎么解决?

1.使用定时器；（最常用也最有效的一种方法）

2.采用非阻塞模式：设置非阻塞，返回之后用select检测状态。

10、TCP/IP 三次握手，accept发生在三次握手哪个阶段？攻击

三次握手完成后，客户端和服务器就建立了tcp连接。这时可以调用accept函数获得此连接。  

SYN攻击属于DOS攻击的一种，它利用TCP协议缺陷，通过发送大量的半连接请求，耗费CPU和内存资源。SYN攻击除了能影响主机外，还可以危害路由器、防火墙等网络系统，事实上SYN攻击并不管目标是什么系统，只要这些系统打开TCP服务就可以实施。从上图可看到，服务器接收到连接请求（syn=j），将此信息加入未连接队列，并发送请求包给客户（syn=k,ack=j+1），此时进入SYN_RECV状态。当服务器未收到客户端的确认包时，重发请求包，一直到超时，才将此条目从未连接队列删除。配合IP欺骗，SYN攻击能达到很好的效果，通常，客户端在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。

11、udp调用connect有什么作用？

1、因为UDP可以是一对一，多对一，一对多，或者多对多的通信，所以每次调用sendto()/recvfrom()时都必须指定目标IP和端口号。通过调用connect()建立一个端到端的连接，就可以和TCP一样使用send()/recv()传递数据，而不需要每次都指定目标IP和端口号。但是它和TCP不同的是它没有三次握手的过程。

2.还可以通过在已建立连接的UDP套接字上，再次调用connect()实现以下功能：

a.指定新的IP地址和端口号。

b.断开连接。

 12、列举你所知道的tcp选项，并说明其作用。

Timestamp时间戳选项

     时间戳选项使发送方在每个报文段中放置一个时间戳值。接收方在确认中返回这个数值，从而允许发送方为每一个收到的 A C K计算RT T（我们必须说“每一个收到的 A C K”而不是“每一个报文段”，是因为T C P通常用一个A C K来确认多个报文段）。我们提到过目前许多实现为每一个窗口只计算一个 RT T，对于包含8个报文段的窗口而言这是正确的。然而，较大的窗口大小则需要进行更好的RT T计算。 

  13、流量控制与拥塞控制的区别，节点计算机怎样感知网络拥塞了？

拥塞控制的任务是确保子网能够承载所到达的流量。这是一个全局性问题，涉及到各方面的行为，包括所有的主机、所有的路由器、路由器内部的存储转发处理过程，以及所有可能会削弱子网承载容量的其它因素。

与此相反，流控制只与特定的发送方和特定的接收方之间的点到点流量有关。它的任务是，确保一个快速的发送方不会持续地以超过接收方吸收能力的速率传输数据。流控制通常涉及到的做法是，接收方向发送方提供某种直接的反馈，以便告诉发送方别人一端的情形到底怎么样。

RTO超时，发生数据包重传，就发生了网络阻塞。

13、socket模型

socket服务端的实现，select和epoll的区别(必问)

epoll哪些触发模式，有啥区别？（必须非常详尽的解释水平触发和边缘触发的区别，以及边缘触发在编程中要做哪些更多的确认）

 14、 socket在什么情况下可读?

  1. socket的接收缓冲区中的数据字节大于等于该socket的接收缓冲区低水位标记的当前大小。对这样的socket的读操作将不阻塞并返回一个大于0的值(也就是返回准备好读入的数据)。我们可以用SO_RCVLOWATsocket选项来设置该socket的低水位标记。对于TCP和UDP.socket而言，其缺省值为1.

2. 该连接的读这一半关闭(也就是接收了FIN的TCP连接)。对这样的socket的读操作将不阻塞并返回0

3.socket是一个用于监听的socket,并且已经完成的连接数为非0.这样的soocket处于可读状态,是因为socket收到了对方的connect请求,执行了三次握手的第一步:对方发送SYN请求过来,使监听socket处于可读状态;正常情况下,这样的socket上的accept操作不会阻塞;

4.有一个socket有异常错误条件待处理.对于这样的socket的读操作将不会阻塞,并且返回一个错误(-1),errno则设置成明确的错误条件.这些待处理的错误也可通过指定socket选项SO_ERROR调用getsockopt来取得并清除;

15、  如果select返回可读，结果只读到0字节，什么情况？

某个套接字集合中没有准备好，可能会select内存用FD_CLR清该位为0.

16、keepalive 是什么东东？如何使用？

   可以主动探测socket是否可用

17、 大规模连接上来，并发模型怎么设计

18、DNS使用什么协议？

【解】DNS使用TCP和UDP协议，具体是：

DNS服务器间进行域传输的时候使用 TCP 53；

客户端查询DNS服务器时使用 UDP 53，但当DNS查询超过512字节，TC标志出现时，使用TCP发送。

这是因为以太网(Ethernet)数据帧的长度必须在46-1500字节之间，这是由以太网的物理特性决定的。这个数据帧长度被称为链路层的MTU（最大传输单元）—— 实际Internet上的标准MTU值为576字节，也就是说链路层的数据区（不包括链路层的头部和尾部）被限制在576字节，所以这也就是网络层IP数据报的长度限制。

因为IP数据报的首部为20字节，所以IP数据报的数据区长度最大为556字节。而这个556字节就是用来放TCP报文段或UDP数据报的。我们知道UDP数据报的首部8字节，所以UDP数据报的数据区最大长度为548字节。—— 如果UDP数据报的数据区大于这个长度，那么总的IP数据包就会大于MTU，这个时候发送方IP层就需要分片(fragmentation)，把数据报分成若干片，使每一片都小于MTU，而接收方IP层则需要进行数据报的重组。由于UDP的特性，当某一片数据传送中丢失时，接收方将无法重组数据报，从而导致丢弃整个UDP数据报。所以通常UDP的最大报文长度就限制为512字节或更小。

19、traceroute命令有什么作用？原理是什么？

【解】traceroute命令用于追踪从本机到指定主机的路由途径。
traceroute程序是利用 ICMP 及 IP 头部的 TTL（存活时间）来实现其功能的。每当数据包经过一个路由器，其存活时间就会减1。当其存活时间是0时，主机便取消数据包，并回复一个「ICMP time exceeded」数据包给发出者。
首先，traceroute发送一个TTL为1的数据包到目的地，当路径上的第一个路由器收到这个数据包时，将它的TTL减1。此时，TTL变为0了，所以该路由器会将此数据包丢掉，并送回一个「ICMP time exceeded」消息，traceroute 收到这个消息后，便知道这个路由器存在于这个路径上。接着traceroute 再送出另一个TTL是2 的数据包，发现第2个路由器……traceroute 每次将送出的数据包的TTL加1来发现另一个路由器，这个重复的动作一直持续到数据包抵达目的地。
当数据包恰好抵达目的地时，由于traceroute所设置的端口是一个一般应用程序都不会用的号码，所以该主机会回送一个「ICMP port unreachable」的消息，而当traceroute 收到这个端口不可达的ICMP消息时，便知道目的地已经到达了。

20、简述一下ping的原理。

【解】格式：ping 192.168.0.5
简单地说，ping就是给目标IP地址发送一个 ICMP 回显请求，并要求对方返回一个 ICMP 回显应答来确定两台网络机器是否连通，时延是多少。

在 ICMP 逐层封装的过程中，需要知道源IP、源MAC地址、目的IP、目的MAC地址，前三者是已知的，只需要获取目的MAC地址即可：

若在同一网段，只需要发送ARP广播；

若不在同一网段，发送ARP广播给交换机，交换机若没有缓存目的IP对应的MAC地址，它会再转发该ARP广播包。

C/C++相关

1 虚析构、模板和宏

【答】在多态中，当使用基类指针或引用操作派生类对象时，如果不把析构函数定义为 visual 函数，则 delete 销毁对象时，只会调用基类的析构函数，不会调用实际派生类对象的析构函数，这样可能造成内存泄露。

2 虚函数实现机制

答：每个对象中存有一份虚函数表，且该表可以继承。表中存放的是虚函数地址。当子类实例化的时候，子类中重写的虚函数地址会覆盖虚表中父类虚函数的地址。因此，父类指针（引用）去调用子类的对象的时候，在虚表中找到的函数地址是重写后的函数地址。

4 extern 关键字有什么用

声明外部变量，在C++文件中调用C方式编译的函数。

5 malloc和new的区别，能否malloc(1.2G)

new是运算符，malloc()是一个库函数；

new会调用构造函数，malloc不会；

new返回指定类型指针，malloc返回void*指针；

new会自动计算需分配的空间，malloc不行；

new可以被重载，malloc不能。

Linux内存地址划分如下：（内核高端3-4G地址映射到物理地址的0-1G处在此不做展开说明）

通过以上介绍，对本文初提出的问题得到答案：

用户态总共可访问的空间是3G，所以申请3G空间肯定越界了。注意：Linux在申请空间时并不是一次给予要求的所有空间，在需要时通过缺页异常按页进行分配。此外malloc申请空间在heap中，具体能申请的最大值还要看stack已占据的大小，heap中已经被分配的大小等因素决定。

6申请4G内存

用文件映射内存的方法，mmap（）函数实现。

7、菱形继承

用虚继承的方法。

8、      memmove实现

注意分两种情况，内存覆盖的情况，内存无覆盖的情况。

9、      函数调用入栈顺序、返回值

VC中函数参数调用入栈顺序是从右至左。原因是C支持可变参数长度，从右至左即使参数个数变化，编译器可以知道参数的总个数。返回值存放在寄存器中。

10、BBR

11、怎么定位跑飞

用coredump，如果产生了core文件：gdb ./test core1517 然后进行backtrace（bt命令）

程序跑飞常见的原因：

1，声明的指针没初始化，系统默认指向随机内存空间

2，数组溢出，即访问数组时下界超出申请的内存空间大小

3，堆栈溢出，即分配的堆栈空间不足

4，使用隐性声明的函数

5，给程序分配的DDR空间不足或者超过DDR的地址空间范围

6，页表映射错误

12、字节对齐

如果没有 #pragma pack宏，结构体的总大小,也就是sizeof的结果,.必须是其内部最大成员的整数倍.不足的要补齐.

13、bitmap

14、*（int *） 0  = 0 报错，操作空指针

15、char *(*a)[3][4]  sizeof(a) = 4

16、（int）(int *)0+4  16位编译器 8，32位编译器 16

17、去掉字符串的空格并返回空格个数

18、字符串反转

//注意串尾的结尾符号。

void Reverse(char *s){

    int n =strlen(s); //没有将结尾符号算进去。

    for(inti=0,j=n-1;i<j;i++,j--){

        char c=s[i];

        s[i]=s[j];

        s[j]=c;

    }

}

19、static、 const

 static表示的是静态的。类的静态成员函数、静态成员变量是和类相关的，而不是和类的具体对象相关的。即使没有具体对象，也能调用类的静态成员函数和成员变量。一般类的静态函数几乎就是一个全局函数，只不过它的作用域限于包含它的文件中。

      在C++中，static静态成员变量不能在类的内部初始化。

     static成员函数主要目的是作为类作用域的全局函数。不能访问类的非静态数据成员。类的静态成员函数没有this指针，这导致：1、不能直接存取类的非静态成员变量，调用非静态成员函数2、不能被声明为virtual

      在C++中，const成员变量也不能在类定义处初始化，只能通过构造函数初始化列表进行，并且必须有构造函数。

     const数据成员 只在某个对象生存期内是常量，而对于整个类而言却是可变的。

     cosnt成员函数主要目的是防止成员函数修改对象的内容。即const成员函数不能修改成员变量的值，但可以访问成员变量。当方法成员函数时，该函数只能是const成员函数。

20、大端与小端的概念？各自的优势是什么？

【答】大端与小端是用来描述多字节数据在内存中的存放顺序，即字节序。大端（Big Endian）是指低地址端存放高位字节，小端（Little Endian）是指低地址端存放低位字节。

Big Endian：符号位的判定固定为第一个字节，容易判断正负。

Little Endian：长度为1，2，4字节的数，排列方式都是一样的，数据类型转换非常方便。

21、指针和引用的区别？

指针是一个实体，而引用仅是个别名；

引用使用时无需解引用(*)，指针需要解引用；

引用只能在定义时被初始化一次，之后不可变，而指针可变；

引用没有const，指针有const；

引用不能为空，指针可以为空；

从内存分配上看，指针变量需分配内存，引用则不需要；

sizeof(引用)得到所指对象的大小，sizeof(指针)得到指针本身的大小；

指针和引用的自增(++)运算意义不一样。

22、C++的内存分区？

【答】C++的内存分区共有五个：

栈区（stack）：主要存放函数参数以及局部变量，由系统自动分配释放。

堆区（heap）：由用户通过 malloc/new 手动申请，手动释放。

全局/静态区：存放全局变量、静态变量；程序结束后由系统释放。

字符串常量区：字符串常量就放在这里，程序结束后由系统释放。

代码区：存放程序的二进制代码。

23、C++对象的内存布局。

【答】影响对象大小的有如下因素：

① 成员变量

② 虚函数（产生虚函数表）

③ 单一继承（只继承于一个类）

④ 多重继承（继承多个类）

⑤ 重复继承（继承的多个父类中其父类有相同的超类）

⑥ 虚拟继承（使用virtual方式继承，为了保证继承后父类的内存布局只会存在一份）

当然，还会有编译器的影响（比如优化），还有字节对齐的影响。

在单继承的情况下，内存布局：

虚函数表在最前面（被重写的虚函数在虚函数表中得到更新）

成员变量根据其继承和声明的顺序依次放在后面

在多重继承的情况下，内存布局：

每个父类都有自己的虚表。（子类自己的虚函数被放在第一个父类的虚表后）

内存布局中，其父类布局依次按照声明顺序排列。

在虚继承的情况下，内存布局：

无论是单虚继承还是多虚继承，需要有一个虚基类表来记录虚继承关系，所以此时子类需要多一个虚基类表指针；而且只需要一个即可。

24、栈溢出的原因及解决办法。

【答】栈的大小一般默认为1M左右，导致栈溢出的常见原因有两个：

函数调用层次过深，每调用一次就压一次栈。

局部变量占用空间太大。

解决办法：

增加栈内存（例如命令：ulimit -s 32768）

使用堆，比如动态申请内存、static修饰。

25、内存泄漏怎么产生的？如何避免？

【答】我们所说的内存泄漏一般是指堆内存的泄漏，也就是程序在运行过程中动态申请的内存空间不再使用后没有及时释放，导致那块内存不能被再次使用。
更广义的内存泄漏还包括未对系统资源的及时释放，比如句柄、socket等没有使用相应的函数释放掉，导致系统资源的浪费。
解决方法：

养成良好的编码习惯和规范，记得及时释放掉内存或系统资源。

重载new和delete，以链表的形式自动管理分配的内存。

使用智能指针。

26、堆和栈的区别？

栈由编译器自动分配释放，存放函数参数、局部变量等。而堆由程序员手动分配和释放；

栈是向低地址扩展的数据结构，是一块连续的内存的区域。而堆是向高地址扩展的数据结构，是不连续的内存区域；

栈的默认大小为1M左右，而堆的大小可以达到几G，仅受限于计算机系统中有效的虚拟内存。

27、const的含义及实现机制，比如：const inti,是怎么做到i只可读的？  

这些在编译期间完成，编译器可能使用常数直接替换掉对此变量的引用。

28、OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。

OFFSETOF(s, m)的宏定义，s是结构类型，m是s的成员，求m在s中的偏移量。(注意字节对齐)

#define OFFSET(s, m) ((size_t) &((s *)0)->m)

ANSI C标准允许任何值为0的常量被强制转换成任何一种类型的指针，并且转换结果是一个NULL指针，因此((s*)0)的结果就是一个类型为s*的NULL指针。如果利用这个NULL指针来访问s的成员当然是非法的，但&(((s*)0)->m)的意图并非想存取s字段内容，而仅仅是计算当结构体实例的首址为((s*)0)时m字段的地址。聪明的编译器根本就不生成访问m的代码，而仅仅是根据s的内存布局和结构体实例首址在编译期计算这个(常量)地址，这样就完全避免了通过NULL指针访问内存的问题。

29、valitale的含义。

volatile 的意思是“易失的，易改变的”。这个限定词的含义是向编译器指明变量的内容可能会由于其他程序的修改而变化。通常在程序中申明了一个变量时，编译器会尽量把它存放在通用寄存器中，例如ebx。当CPU把其值放到ebx中后就不会再关心对应内存中的值。若此时其他程序（例如内核程序或一个中断）修改了内存中它的值，ebx中的值并不会随之更新。为了解决这种情况就创建了volatile限定词，让代码在引用该变量时一定要从指定位置取得其值。

一般说来，volatile用在如下的几个地方： 
1、中断服务程序中修改的供其它程序检测的变量需要加volatile； 
2、多任务环境下各任务间共享的标志应该加volatile； 
3、存储器映射的硬件寄存器通常也要加volatile说明，因为每次对它的读写都可能由不同意义； 

例如： 
volatile   int   i=10; 
int   a   =   i; 
。。。//其他代码，并未明确告诉编译器，对i进行过操作 
int   b   =   i; 
volatile   指出   i是随时可能发生变化的，每次使用它的时候必须从i的地址中读取，因而编译器生成的 
汇编代码会重新从i的地址读取数据放在b中。而优化做法是，由于编译器发现两次从i读数据的代码之间 
的代码没有对i进行过操作，它会自动把上次读的数据放在b中。而不是重新从i里面读。这样以来，如果 
i是一个寄存器变量或者表示一个端口数据就容易出错，所以说volatile可以保证对特殊地址的稳定访问 。 
注意，在vc6中，一般调试模式没有进行代码优化，所以这个关键字的作用看不出来。下面通过插入汇编 
代码，测试有无volatile关键字，对程序最终代码的影响： 
首先用classwizard建一个win32   console工程，插入一个voltest.cpp文件，输入下面的代码： 
#include   <stdio.h> 
void   main() 
{ 
  int   i=10; 
  int   a   =   i; 
  printf( "i=   %d\n ",a); 
               //下面汇编语句的作用就是改变内存中i的值，但是又不让编译器知道 
  __asm   { 
    mov                  dword   ptr   [ebp-4],   20h 
  } 
  int   b   =   i; 
  printf( "i=   %d\n ",b); 
} 
然后，在调试版本模式运行程序，输出结果如下： 
i   =   10 
i   =   32 
然后，在release版本模式运行程序，输出结果如下： 
i   =   10 
i   =   10 
输出的结果明显表明，release模式下，编译器对代码进行了优化，第二次没有输出正确的i值。

linux以及操作系统相关

1      内存池实现

经典的内存池（Memory Pool）技术，是一种用于分配大量大小相同的小对象的技术。通过该技术可以极大加快内存分配/释放过程。既然针对是特定对象的内存池，所以内存池一般设置为类模板，根据不同的对象来进行实例化。内存池（memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当我们申请内存空间时，首先到我们的内存池中查找合适的内存块，而不是直接向操作系统申请，优势在于：

1、比malloc/free进行内存申请/释放的方式快

2、不会产生或很少产生堆碎片

3、可避免内存泄漏

（1）先申请一块连续的内存空间，该段内存空间能够容纳一定数量的对象。

（2）每个对象连同一个指向下一个对象的指针一起构成一个内存节点（Memory Node）。各个空闲的内存节点通过指针来形成一个链表，链表的每一个内存节点都是一块可供分配的内存空间。

（3）某个内存节点一旦分配出去，就将从链表中去除。

（4）一旦释放了某个内存节点的空间，又将该节点重新加入自由内存节点链表。

（5）如果一个内存块的所有内存节点分配完毕，若程序继续申请新的对象空间，则会再次申请一个内存块来容纳新的对象。新申请的内存块会加入内存块链表中。

2 进程间通信机制

管道、信号、信号量、套接字、消息队列、共享内存

3进程与线程的区别，共享的数据

简而言之,一个程序至少有一个进程,一个进程至少有一个线程。进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

    线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

5 进程的内存空间

6、软链接、硬链接

ln是linux中又一个非常重要命令，它的功能是为某一个文件在另外一个位置建立一个同步的链接.当我们需要在不同的目录，用到相同的文件时，我们不需要在每一个需要的目录下都放一个必须相同的文件，我们只要在某个固定的目录，放上该文件，然后在其它的目录下用ln命令链接（link）它就可以，不必重复的占用磁盘空间。

·        硬链接：与普通文件没什么不同，inode 都指向同一个文件在硬盘中的区块

·        软链接：保存了其代表的文件的绝对路径，是另外一种文件，在硬盘上有独立的区块，访问时替换自身路径。

7、共享内存 mmap 、shmc

共享内存区域是被多个进程共享的一部分物理内存。如果多个进程都把该内存区域映射到自己的虚拟地址空间，则这些进程就都可以直接访问该共享内存区域，从而可以通过该区域进行通信。共享内存是进程间共享数据的一种最快的方法，一个进程向共享内存区域写入了数据，共享这个内存区域的所有进程就可以立刻看到其中的内容。这块共享虚拟内存的页面，出现在每一个共享该页面的进程的页表中。但是它不需要在所有进程的虚拟内存中都有相同的虚拟地址。 

1、mmap是在磁盘上建立一个文件，每个进程地址空间中开辟出一块空间进行映射。而对于shm而言，shm每个进程最终会映射到同一块物理内存。shm保存在物理内存，这样读写的速度要比磁盘要快，但是存储量不是特别大。

2、相对于shm来说，mmap更加简单，调用更加方便，所以这也是大家都喜欢用的原因。

3、另外mmap有一个好处是当机器重启，因为mmap把文件保存在磁盘上，这个文件还保存了操作系统同步的映像，所以mmap不会丢失，但是shmget就会丢失

注意：共享内存并没有提供进程同步机制。

int shmget(key_t key, size_t size, intshmflg)  创建共享内存 shmflg 一般设置为 IPC_CREAT| 0666

 6   ＝   4   ＋   2   ，表示   读＋写。 如果是   7   ＝   4   ＋   2   ＋   1   ，表示   读＋写＋执行。 另，0666   每一位表示一种类型的权限，比如，第一个0是表示八进制,第一个表示拥有者的权限，第二个6表示同组权限，第3个6表示他人的权限。

void *shmat(int shmid, const void *shmaddr, intshmflg) 把共享内存区对象映射到调用进程的地址空间，返回好的共享内存地址

int shmdt(const void *shmaddr)  断开共享内存连接

int shmctl(int shmid, int cmd, struct shmid_ds*buf)  完成对共享内存的状态控制

8、哪几种锁，条件变量

互斥锁、读写锁。

互斥锁用于上锁，条件变量用于等待，条件变量的使用是与互斥锁共通使用的。

互斥锁，我要对一块共享数据操作，但是我怕同时你也操作，那就乱套了，所以我要加锁，这个时候我就开始操作这块共享数据，而你进不了临界区，等我操作完了，把锁丢掉，你就可以拿到锁进去操作了。 

条件变量，我要看一块共享数据里某一个条件是否达成，我很关心这个，如果我用互斥锁，不停的进入临界区看条件是否达成，这简直太悲剧了，这样一来，我醒的时候会占CPU资源，但是却干不了什么事，只是频繁的看条件是否达成，而且这对别人来说也是一种损失，我每次加上锁，别人就进不了临界区干不了事了。好吧，轮询总是痛苦的，咱等别人通知吧，于是条件变量出现了，我依旧要拿这个锁，进了临界区，看到了共享数据，发现，咦，条件还不到，于是我就调用pthread_cond_wait(),先把这个锁丢了，好让别人可以去对共享数据做操作，然后呢？然后我就睡了，直到特定的条件发生，别人修改完了共享数据，给我发了个消息，我又重新拿到了锁，继续干俺要干的事情了……

9、同步与互斥

 互斥是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。

10、     动态加载dll和静态加载dll的区别

静态加载：当lib文件（导入库文件）不存在时，exe运行会报错。一旦加载就一直驻留在应用程序的地址空间，运行速度快。
动态加载：不需要lib文件，需要用到DLL的时后才通过loadlibrary函数引入，用完可通过freelibrary函数卸载。内存空间占用少，支持热更新。

11、     一个进程由哪些方面构成

程序段、数据段、进程控制块PCB.

PCB(process control block)，进程控制块，是我们学习操作系统后遇到的第一个数据结构描述，它是对系统的进程进行管理的重要依据，和进程管理相关的操作无一不用到PCB中的内容。一般情况下，PCB中包含以下内容：

（1）进程标识符（内部，外部）
（2）处理机的信息（通用寄存器，指令计数器，PSW，用户的栈指针）。
（3）进程调度信息（进程状态，进程的优先级，进程调度所需的其它信息，事件）
（4）进程控制信息（程序的数据的地址，资源清单，进程同步和通信机制，链接指针）

进程状态机：

（1）运行(running)态：进程占有处理器正在运行。

（2）就绪(ready)态：进程具备运行条件，等待系统分配处理器以便运行。

（3）等待(wait)态：又称为阻塞(blocked)态或睡眠(sleep)态，指进程不具备运行条件，正在等待某个事件的完成。

12、     守护、僵尸、孤儿进程的概念

守护进程：运行在后台的一种特殊进程，独立于控制终端并周期性地执行某些任务。

僵尸进程：一个进程 fork 子进程，子进程退出，而父进程没有 wait/waitpid子进程，那么子进程的进程描述符仍保存在系统中，这样的进程称为僵尸进程。

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，这些子进程称为孤儿进程。（孤儿进程将由 init 进程收养并对它们完成状态收集工作）

14、linux下你常用的命令有哪些？Linux ps命令，以及看内存当前使用状态的命令

【答】ll、cp、rm、mkdir、rmdir、pwd（显示当前路径）、touch、ln、cat、less、more、vim、tar、rz、sz 、df（查看磁盘使用）、du（文件占用磁盘大小）、free(查看内存使用)、top（任务管理器，系统启动时间，进程总数，CPU消耗等）、sar、netstat、iostat、ps ，kill(杀死进程) ，chmod、ifconfig、ping、telnet、netstat、tcpdump、ipcs、ipcrm、  pmap –d、 man（查看函数说明）、find

·        Linux netstat命令详解

·        netstat显示网络相关的信息，如网络连接，路由表(-r)，接口状态 
-a (all) 显示全部信息 
-n 拒绝别名，能用数字的都用数字

·        Linux tcpdump命令详解 
对网络上的数据包进行截获的包分析工具。

·        Linuxipcs命令与ipcrm命令的用法详解 
ipcs提供进程间通信方式的信息，包括共享内存，信号量，消息队列。 
-a 输出所有 
-m 共享内存 
-q 消息队列 
-s 信号

ipcrm移除一个消息对象、或者共享内存、或者信号量 
ipcrm用法（小写是id标识） 
ipcrm -M shmkey 移除用shmkey创建的共享内存段 
ipcrm -m shmid 移除用shmid标识的共享内存段 
ipcrm -Q msgkey 移除用msqkey创建的消息队列 
ipcrm -q msqid 移除用msqid标识的消息队列 
ipcrm -S semkey 移除用semkey创建的信号 
ipcrm -s semid 移除用semid标识的信号

15、系统调用与库函数的区别？

系统调用：操作系统为用户程序与硬件设备进行交互提供的一组接口，发生在内核地址空间。

库函数：把一些常用的函数编写完放到一个文件里，编写应用程序时调用，这是由第三方提供的，发生在用户地址空间。

在移植性方面，不同操作系统的系统调用一般是不同的，移植性差；而在所有的ANSI C编译器版本中，C库函数是相同的。

在调用开销方面，系统调用需要在用户空间和内核环境间切换，开销较大；而库函数调用属于“过程调用”，开销较小。

简单点说，库函数就是系统调用的上层封装，为了让应用程序在使用时更加方便。

16、死锁产生的四个条件，死锁发生后怎么检测和恢复？

【答】死锁的四个必要条件：

互斥条件：一个资源每次只能被一个进程使用。

请求与保持条件：一个进程在申请新的资源的同时保持对原有资源的占有。

不剥夺条件:进程已获得的资源，在未使用完之前，不能强行剥夺。

循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

死锁发生后：

检测死锁：首先为每个进程和每个资源指定一个唯一的号码，然后建立资源分配表和进程等待表。

解除死锁：当发现有进程死锁后，可以直接撤消死锁的进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止。

17、进程调度算法有哪些？Linux使用的什么进程调度方法？

【解】进程调度算法有下面几种：

先来先服务

短作业优先

时间片轮转

基于优先级

18、core产生的原因，如何调试定位问题？

【答】原因大致有：

内存访问越界

非法指针

堆栈溢出

调试：如果产生了core文件：gdb ./test core1517 然后进行backtrace（bt命令）；如果没有core文件，查看dmesg。

19、阻塞IO、非阻塞IO、同步IO、异步IO的区别？

阻塞IO（blocking IO）：线程阻塞以等待数据，然后将数据从内核拷贝到进程，返回结果之后才解除阻塞状态。也就是说两个阶段都被block了。

非阻塞IO（non-blocking IO）：当对一个非阻塞socket执行读操作时，如果kernel中的数据还没有准备好，那么它并不会block用户进程，而是立刻返回一个error。用户进程需要不断地主动进行read操作，一旦数据准备好了，就会把数据拷贝到用户内存。也就是说，第一阶段并不会阻塞线程，但第二阶段拷贝数据还是会阻塞线程。

同步IO（synchronous IO）：POSIX中的同步IO定义是—— A synchronous I/O operation causes the requestingprocess to be blocked until that I/O operation completes。也就是说同步IO在IO操作完成之前会阻塞线程，按照这个定义，之前所述的blocking IO，non-blocking IO，IO multiplexing都属于synchronous IO。（non-blocking IO也属于同步IO是因为它在真正拷贝数据时也会阻塞线程）

异步IO（asynchronous IO）：POSIX中的异步IO定义是—— An asynchronous I/O operation does not cause therequesting process to be blocked。在linux异步IO中，用户进程发起read操作之后，直接返回，去做其它的事。而另一方面，从kernel的角度，当它受到一个asynchronous read之后，kernel会等待数据准备完成，然后将数据拷贝到用户内存，当这一切都完成之后，kernel会给用户进程发送一个signal，告诉它read操作完成了。也就是说两个阶段都不会阻塞线程。它就像是用户进程将整个IO操作交给了他人（kernel）完成，然后他人做完后发信号通知。在此期间，用户进程不需要去检查IO操作的状态，也不需要主动的去拷贝数据。

20、分时系统与实时系统的区别？

分时系统：系统把CPU时间分成很短的时间片，轮流地分配给多个作业。优点：对多个用户的多个作业都能保证足够快的响应时间，并且有效提高了资源的利用率。

实时系统：系统对外部输入的信息，能够在规定的时间内（截止期限）处理完毕并做出反应。优点：能够集中地及时地处理并作出反应，高可靠性，安全性。

21、除了sleep之外，usleep()也是linux系统调用，它号称自己是微秒级的，你相信它真的有这么快吗？为什么？

【解】usleep实际上达不到微秒级，主要是因为linux是分时系统，由于进程调度（上下文切换）和系统时间中断精度的原因。

22、怎么确定内存中栈的生长方向

考察对程序内存分配的理解。内存中栈主要用来存放局部变量、函数参数、返回值等。

正确的做法是，定义两个函数a和b，a打印出它的参数的地址并调用b，b打印出它的参数的地址，根据地址的增大或是减少来判断。

23. gdb调试时如何找到出错的地方

1、得到包含调试信息的二进制文件

   G++ test.c – o test –g

2.进入调试状态

  Gdb test

3、list <linenum>/<function> 列出源程序代码

4、run（缩写r）、break（缩写b）、next（缩写n）命令控制程序的运行，并使用print（缩写p）命令打印程序中的变量。用bt来显示函数调用路径。用set命令来改变变量的值. set var i= 8

infothreads 显示当前可调试的所有线程，每个线程会有一个GDB为其分配的ID，后面操作线程的时候会用到这个ID。前面有*的是当前调试的线程。

threadID 切换当前调试的线程为指定ID的线程。

在gdb中用break命令来设置断点，设置断点的方法包括：

·        break <function>

在进入指定函数时停住，C++中可以使用class::function或function(type, type)格式来指定函数名。

·        break <linenum>

在指定行号停住。

·        break +offset / break -offset

在当前行号的前面或后面的offset行停住，offiset为自然数。

·        break filename:linenum

在源文件filename的linenum行处停住。

·        break filename:function

在源文件filename的function函数的入口处停住。

·        break *address

在程序运行的内存地址处停住。

·        break

break命令没有参数时，表示在下一条指令处停住。

·        break ... if <condition>

“...”可以是上述的break<linenum>、break +offset /break –offset中的参数，condition表示条件，在条件成立时停住。比如在循环体中，可以设置break if i=100，表示当i为100时停住程序。

查看断点时，可使用info命令，如infobreakpoints [n]、info break [n]（n表示断点号）

24. 你知道负载吗？其实就是load。

  Top 命令

     25、 32位系统一个进程最多多少堆内存

1、         创建一个进程时，操作系统会为该进程分配一个 4GB 大小的虚拟 进程地址空间。之所以是 4GB ，是因为在 32 位的操作系统中，一个指针长度是 4 字节，而 4 字节指针的寻址能力是从 0x00000000~0xFFFFFFFF ，最大值 0xFFFFFFFF 表示的即为 4GB 大小的容量。
2、每个进程只能访问自己虚拟地址空间中的数据，无法访问别的进程中的数据，通过这种方法实现了进程间的地址隔离。
3、4GB 的虚拟地址被分成了 4 部分： NULL 指针区、用户区、64KB 禁入区、内核区。应用程序能使用的只是用户区而已，大约 2GB 左右 ( 最大可以调整到 3GB) 。内核区为 2GB ，内核区保存的是系统线程调度、内存管理、设备驱动等数据，这部分数据供所有的进程共享，但应用程序是不能直接访问的。

     26、  写一个c程序辨别系统是64位 or 32位

根据指针占用内存大小判断，8字节是64位，4字节是32位。

   27、   写一个c程序辨别系统是大端or小端字节序

网络字节序采用的是大端法。

主机字节序不同的CPU采用的方法不一样，可以通过代码来查看自己主机的字节序。

大端法：高位字节排放在内存低地址端，低位字节排放在内存的高地址端。

小端法：低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。

看一个unsigned short 数据，它占2个字节，给它赋值0x1234。

若采用的大端法，则其低地址端应该存放的是0x12；

若采用的小端法，则其低地址端应该存放的是0x34；

可以通过联合体来获得其高低地址的数据。

测试主机字节序的代码：

·        共享内存的使用实现原理（必考必问，然后共享内存段被映射进进程空间之后，存在于进程空间的什么位置？共享内存段最大限制是多少？）

·        c++进程内存空间分布（注意各部分的内存地址谁高谁低，注意栈从高道低分配，堆从低到高分配）

·        ELF是什么？其大小与程序中全局变量的是否初始化有什么关系（注意.bss段）

·        使用过哪些进程间通讯机制，并详细说明（重点）

·        makefile编写，虽然比较基础，但是会被问到

·         多线程和多进程的区别（重点面试官最最关心的一个问题，必须从cpu调度，上下文切换，数据共享，多核cup利用率，资源占用，等等各方面回答，然后有一个问题必须会被问到：哪些东西是一个线程私有的？答案中必须包含寄存器，否则悲催）

·        信号：列出常见的信号，信号怎么处理？

·         i++是否原子操作？并解释为什么？？？？？？？

·        说出你所知道的各类linux系统的各类同步机制（重点），什么是死锁？如何避免死锁（每个技术面试官必问）

·        列举说明linux系统的各类异步机制

·        exit()_exit()的区别？

·        如何实现守护进程？

·         linux的内存管理机制是什么？

·        补充一个坑爹坑爹坑爹坑爹的问题：系统如何将一个信号通知到进程？（这一题哥没有答出来）

·         各类库函数必须非常熟练的实现

·         哪些库函数属于高危函数，为什么？（strcpy等等）

·          一个String类的完整实现必须很快速写出来（注意：赋值构造，operator=是关键）

·         sizeof一个类求大小（注意成员变量，函数，虚函数，继承等等对大小的影响）

·        stl各容器的实现原理（必考）

      c语言：

      宏定义和展开（必须精通）

      位操作（必须精通）

      指针操作和计算（必须精通）

      内存分配（必须精通）

      sizeof必考

算法与数据结构 （手写代码实现）

1、hash如何取模，避免冲突

hash是依据关键码值(Key value)而直接进行訪问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来訪问记录，以加快查找的速度。

1.直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）

2.数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3.平方取中法：取keyword平方后的中间几位作为散列地址。

4.折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。

5.随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。

6. 除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) =key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，若p选的不好，easy产生同义词。

    冲突避免：开放定址法、数组链表法。

2      、map的实现机制是怎么样的啊

底层实现基于红黑树实现的。一种自平衡二叉查找树。

2、vector的删除和插入  vector和list的区别

vector <int>st;

vector <int>::iterator it = st.begin();

st.insert(it,10);   在开始位置插入元素10 。

st.erase(it);   删除开始位置的数据。

Vector内存连续，随机访问效率高。

List 内存不连续，在首尾插入、删除效率高，随机访问速度慢。

3、单链表翻转（两个指针如何实现）、查找、删除、插入以及双向链表、有序链表合并

三指针实现：

Typedef struct node {

Int data;

Struct node *next;

}List;

Void ListReverse(List *head){

List *p;

List *q;

List *r;

If(head ==NULL || head->next == NULL)

Return ;

P = head;

q = head->next;

head->next = NULL;

while(q){

r = q->next;

q->next = p;

p = q;

q  = r;

}

Head = p;

}

两指针实现：

5、常见排序算法的实现以及稳定性（快排跟归并考的很多），快排复杂度推导

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。

1.    T（n）≤2T（n/2） +n，T（1）=0  

2.    T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n  

3.    T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n  

4.    ……  

5.    T（n）≤nT（1）+（log2n）×n= O(nlogn) 

也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为 ，最终其时间复杂度为O(n2)。

快速排序平均需要大约2NlnN次比较，来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单：假设C_N为快速排序平均花在比较上的时间，初始C₀=C₁=0，对于N>1的情况，有：其中N+1是分割时的比较次数， 表示将序列分割为0，和N-1左右两部分的概率为1/N, 划分为1，N-2左右两部分的概率也为1/N，都是等概率的。然后对上式左右两边同时乘以N，整理得到：

然后，对于N为N-1的情况：

两式相减，然后整理得到：

然后左右两边同时除以N(N+1)，得到:

可以看到，这是一个递归式，我们将 递归展开得到：

然后处理一下得到：

就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。

可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

6、 二分查找（注意边界条件）

7、 链表判断是否有环，环的入口，两个链表是否相交（快慢指针）。

一个比较经典的问题，判断两个链表是否相交，如果相交找出他们的交点。

思路：

1、碰到这个问题，第一印象是采用hash来判断，将两个链表的节点进行hash，然后判断出节点，这种想法当然是可以的。

2、当然采用暴力的方法也是可以的，遍历两个链表，在遍历的过程中进行比较，看节点是否相同。

3、第三种思路是比较奇特的，在编程之美上看到的。先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？

这样进行转换后就可以从链表头部进行判断了，其实并不用。通过简单的了解我们就很容易知道，如果新链表是有环的，那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的，从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。

下图是一个简单的演示：

这种方法可以判断两个链表是否相交，但不太容易找出他们的交点。

4、仔细研究两个链表，如果他们相交的话，那么他们最后的一个节点一定是相同的，否则是不相交的。因此判断两个链表是否相交就很简单了，分别遍历到两个链表的尾部，然后判断他们是否相同，如果相同，则相交；否则不相交。示意图如下：

判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1，第二个问len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可。

下面给出一个简单的实现：

typedefstruct node_t

{

int data;//data

struct node_t *next;//next

}node;

node*find_node(node *head1, node *head2)

{

if(NULL == head1 ||NULL == head2)

{

return NULL;//如果有为空的链表，肯定是不相交的

}

node *p1, *p2;

p1 = head1;

p2 = head2;

int len1 = 0;

int len2 =0;

int diff = 0;

while(NULL !=p1->next)

{

p1 = p1->next;

len1++;

}

while(NULL !=p2->next)

{

p2 = p2->next;

len2++;

}

if(p1 != p2) //如果最后一个节点不相同,返回NULL

{

return NULL;

}

diff = abs(len1 -len2);

if(len1 > len2)

{

p1 = head1;

p2 = head2;

}

else

{

p1 = head2;

p2 = head1;

}

for(int i=0;i<diff; i++)

{

p1 = p1->next;

}

while(p1 != p2)

{

p1 = p1->next;

p2 = p2->next;

}

return p1;

}

通过上面的操作就可以找到两个链表的交点了。

5、总结

上面的几种方法中最后一种是比较不错的，当然hash也是可以的。

问题的延伸：

如果原来的两个链表中有环怎么处理？

1、先判断是否有环

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)

 1bool isExitsLoop(list *head)

 2 {

 3    list *slow = head, *fast = head;

 4

 5    while ( fast && fast->next )

 6    {

 7         slow = slow->next;

 8         fast = fast->next->next;

 9         if ( slow == fast ) break;

10     }

11

12     return !(fast == NULL || fast->next ==NULL);

13 }

8vector/map/multimap/unordered_map/unordered_multimap的底层数据结构，以及几种map容器如何选择？

【答】底层数据结构：vector基于数组，map/multimap基于红黑树，unordered_map/unordered_multimap基于哈希表。
根据应用场景进行选择：

map/unordered_map 不允许重复元素

multimap/unordered_multimap允许重复元素

map/multimap底层基于红黑树，元素自动有序，且插入、删除效率高

unordered_map/unordered_multimap底层基于哈希表，故元素无序，查找效率高。

4. 统计10万个单词中出现频率最高的1000个

10万个单词完全可以内存中放下，所以可以使用hashmap，单词作为key，value为该单词的计数，对这10万个单词进行统计。统计完后，用一个最小堆找出计数最多的那1000个单词。具体可参考码农的Top K算法详细解析。

5. 求1000亿个数中的最大1000个

假设内存为4G，显然不足以把这1000亿个数都存入。可以把这它们划分为落干个区间，对应地存储到若干个文件中，使得每个区间中不超过10亿个数，若超过则对该区间再进行划分。

然后对这些区间内的数进行统计，假设前N个区间中数的总数X1，且X1<1000，而前N＋1个区间中数的总数为X2，且X2>1000，则最大1000个数为前N个区间内的数加上第N＋1个区间中的前1000-X1个数。

10、10亿个整数，随机生成，可重复，求最大的前1万个。  分治法+hash+多路归并排序

10、 指定一个数组，求2个数的和等于指定的和（某一个数），如果是3,4,5，n个等于个的和（某一个数）呢？（可以看作背包问题）

  解法一

 一个直接的解法就是穷举：从数组中任意取出两个数字，计算两者之和是否为给定的数字。 显然其时间复杂度为N（N-1）/2即O（N^2）。这个算法很简单，写起来也很容易，但是效率不高。一般在程序设计里面，要尽可能降低算法的时间和空间复杂度，所以需要继续寻找效率更高的解法

 解法二

还可以换个角度来考虑问题，假设已经有了这个数组的任意两个元素之和的有序数组（长为N^2）。那么利用二分查找法，只需用O（2*log2N）就可以解决这个问题。当然不太可能去计算这个有序数组，因为它需要O（N^2）的时间。但这个思考仍启发我们，可以直接对两个数字的和进行一个有序的遍历，从而降低算法的时间复杂度。

首先对数组进行排序，时间复杂度为（N*log2N）。

 然后令i= 0，j= n-1，看arr[i]+ arr[j] 是否等于Sum，如果是，则结束。如果小于Sum，则i= i + 1；如果大于Sum，则j = j – 1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，时间复杂度为O（N）。两步加起来总的时间复杂度O（N*log2N），下面这个程序就利用了这个思想，代码如下所示：

int getSumNum(int[] arr,int Sum)，   //arr为数组，Sum为和

{

               int i,j;

               for(i = 0, j = n-1; i < j ; )

               {

                               if(arr[i] + arr[j] == Sum)

                                              return ( i , j );

                               else if(arr[i] + arr[j] < Sum)

                                              i++;

                               else

                                              j--;

               }

               return ( -1 , -1 );

}

 扩展问题

1、如果把这个问题中的“两个数字”改成“三个数字”或“任意个数字”时，你的解是什么呢？

三个数字：首先还是先对数组进行排序，然后从i=0到n-1进行遍历，遍历arr[i]时，在调用上面的函数getSumNum(arr, Sum-arr[i])即可。

12、手写代码，判断两个树时候相同（结构相同，内容相同）。

13、大整数加、减、乘、除、求模运算实现

1、大数加法

    两个大数我们可以用数组来保存，然后在数组中逐位进行相加，再判断该位相加后是否需要进位，为了方便计算，我们将数字的低位放在数组的前面，高位放在后面。

下面是两个正的大整数相加算法的C语言参考代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3

 4#define MAX 1000    // 大数的最大位数 

 5

 6 

 7/*

 8  大数加法

 9  参数：

10  num1为第一个大数，用字符数组保存

11  num2为第二个大数

12  sum数组保存相加的结果  即：num1+num2=sum

13  返回值：返回数组sum的有效长度，即计算结果的位数

14  */

15int Addition(char num1[], char num2[], int sum[])

16 {

17     int i, j, len;

18     int n2[MAX] = {0};

19     int len1 = strlen (num1); // 计算数组num1的长度，即大数的位数

20     int len2 = strlen (num2); // 计算数组num2的长度，即大数的位数

21

22     len = len1>len2 ? len1 :len2; // 获取较大的位数

23     //将num1字符数组的数字字符转换为整型数字，且逆向保存在整型数组sum中，即低位在前，高位在后

24     for (i = len1-1, j = 0; i >= 0; i--, j++)

25         sum[j] = num1[i] - '0';

26     // 转换第二个数

27     for (i = len2-1, j = 0; i >= 0; i--, j++)

28         n2[j] = num2[i] - '0';

29     // 将两个大数相加

30     for (i = 0; i <= len; i++)

31     {

32         sum[i] += n2[i];  // 两个数从低位开始相加

33         if (sum[i] > 9)  // 判断是否有进位

34         {   // 进位

35             sum[i] -= 10;

36             sum[i+1]++;

37         }

38     }

39     if(sum[len] != 0) // 判断最高位是否有进位

40         len++;

41     return len;  // 返回和的位数

42 }

43

44int main()

45 {

46     int i, len;

47     int sum[MAX] = {0}; // 存放计算的结果，低位在前，高位在后，即sum[0]是低位

48     char num1[] = "1234567891234567891234"; // 第一个大数

49     char num2[] = "2345678912345678913345"; // 第二个大数

50     len = Addition(num1, num2,sum);    // 两数相加

51     printf("%s\n  +\n%s\n =\n", num1, num2);

52     // 反向输出求和结果

53     for (i = len-1; i >= 0; i--)

54         printf("%d", sum[i]);

55     printf("\n");

56     return0;

57 }

2、大数减法

    相减算法也是从低位开始减的。先要判断被减数和减数哪一个位数长，若被减数位数长是正常的减法；若减数位数长，则用被减数减去减数，最后还要加上负号；当两数位数长度相等时，最好比较哪一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。

下面是C语言参考代码：

  1 #include<stdio.h>

  2 #include<string.h>

  3

  4#define MAX 1000    // 大数的最大位数 

  5

  6 

  7/*

  8  大数减法

  9  参数：

 10  num1为被减数，用字符数组保存

 11  num2为减数

 12  sum数组保存相减的结果   即：num1-num2=sum

 13  返回值：返回数组sum的有效长度，即计算结果的位数

 14 */

 15int Subtraction(char num1[], char num2[], int sum[])

 16 {

 17    int i, j, len, blag;

 18    char *temp;

 19    int n2[MAX] = {0};

 20    int len1 = strlen(num1); // 计算数组num1的长度，即大数的位数

 21    int len2 = strlen(num2); // 计算数组num2的长度，即大数的位数

 22    

 23    // 在进行减法之前要进行一些预处理

 24    blag = 0; // 为0表示结果是正整数，为1表示结果是负整数

 25    if(len1 < len2) // 如果被减数位数小于减数

 26    {

 27         blag = 1; // 标记结果为负数

 28         // 交换两个数，便于计算

 29         temp = num1;

 30         num1 = num2;

 31         num2 = temp;

 32         len = len1;

 33         len1 = len2;

 34         len2 = len;

 35    }

 36    elseif(len1 ==len2) // 如果被减数的位数等于减数的位数

 37    { 

 38         // 判断哪个数大

 39         for(i = 0; i < len1; i++)

 40         {

 41             if(num1[i] == num2[i])

 42                 continue;

 43             if(num1[i] > num2[i])

 44             {

 45                 blag = 0; // 标记结果为正数

 46                 break;

 47             }

 48             else

 49             {

 50                 blag = 1; // 标记结果为负数

 51                 // 交换两个数，便于计算

 52                 temp = num1;

 53                 num1 = num2;

 54                 num2 = temp;

 55                 break;

 56             }

 57         }

 58    }

 59    len = len1>len2 ? len1 : len2; // 获取较大的位数

 60     //将num1字符数组的数字转换为整型数且逆向保存在整型数组sum中，即低位在前，高位在后

 61    for (i = len1-1, j = 0; i >= 0; i--, j++)

 62         sum[j] = num1[i] - '0';

 63    // 转换第二个数

 64    for (i = len2-1, j = 0; i >= 0; i--, j++)

 65         n2[j] = num2[i] - '0';

 66    // 将两个大数相减

 67    for (i = 0; i <= len; i++)

 68    {

 69         sum[i] = sum[i] - n2[i]; // 两个数从低位开始相减

 70         if (sum[i] < 0)  // 判断是否有借位

 71         {   // 借位

 72             sum[i] += 10;

 73             sum[i+1]--;

 74         }

 75    }

 76    // 计算结果长度

 77    for (i = len1-1; i>=0 && sum[i] == 0; i--)

 78         ;

 79    len = i+1;

 80    if(blag==1)

 81    {

 82         sum[len] = -1; // 在高位添加一个-1表示负数

 83         len++;

 84    }

 85    return len;   // 返回结果的位数

 86 }

 87

 88int main()

 89 {

 90    int i, len;

 91    int sum[MAX] = {0}; // 存放计算的结果，低位在前，高位在后，即sum[0]是低位

 92    char num1[] = "987654321987654321"; // 第一个大数

 93    char num2[] = "123456789123456789"; // 第二个大数

 94    len = Subtraction(num1, num2, sum);   // 两数相减

 95    // 输出结果

 96    printf("%s\n  -\n%s\n  =\n", num1, num2);

 97    if(sum[i=len-1] < 0) // 根据高位是否是-1判断是否是负数

 98    {

 99         printf("-"); // 输出负号

100         i--;

101     }

102     for (; i >= 0; i--)

103         printf("%d", sum[i]);

104     printf("\n");

105     return0;

106 }

3、大数乘法

    首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。

    计算的过程基本上和小学生列竖式做乘法相同。为了编程方便，并不急于处理进位，而是将进位问题留待最后统一处理。

    总结一个规律: 即一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i+j 位上。这里i, j 都是从右往左，从0 开始数。
    ans[i+j] = a[i]*b[j];

    另外注意进位时要处理，当前的值加上进位的值再看本位数字是否又有进位；前导清零。

下面是C语言的两个正大数相乘的参考代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3

 4#define MAX 1000    // 大数的最大位数 

 5

 6 

 7/*

 8  大数乘法

 9  参数：

10  num1为第一个因数，用字符数组保存

11  num2为第二个因数

12  sum数组保存相乘的结果  即：num1*num2=sum

13  返回值：返回数组sum的有效长度，即计算结果的位数

14  */

15int Multiplication(char num1[],char num2[], int sum[])

16 {

17     int i, j, len, len1, len2;

18     int a[MAX+10] = {0};

19     int b[MAX+10] = {0};

20     int c[MAX*2+10] = {0};

21    

22     len1 = strlen(num1);

23     for(j = 0, i = len1-1; i >= 0; i--) //把数字字符转换为整型数

24         a[j++] = num1[i]-'0';

25     len2 = strlen(num2);

26     for(j = 0, i = len2-1; i >= 0; i--)

27         b[j++] = num2[i]-'0';

28    

29     for(i = 0; i < len2; i++)//用第二个数乘以第一个数,每次一位

30     {

31         for(j = 0; j < len1; j++)

32         {

33             c[i+j] += b[i] * a[j]; //先乘起来,后面统一进位

34         }

35     }

36    

37     for(i=0; i<MAX*2; i++) //循环统一处理进位问题

38     {

39         if(c[i]>=10)

40         {

41             c[i+1]+=c[i]/10;

42             c[i]%=10;

43         }

44     }

45

46     for(i = MAX*2; c[i]==0 && i>=0; i--); //跳过高位的0

47     len = i+1; // 记录结果的长度

48     for(; i>=0; i--)

49         sum[i]=c[i];

50     return len;

51 }

52

53int main()

54 {

55     int i, len;

56     int sum[MAX*2+10] = {0}; // 存放计算的结果，低位在前，高位在后，即sum[0]是低位

57     char num1[] = "123456789123456789"; // 第一个大数

58     char num2[] = "123456789123456789"; // 第二个大数

59     len = Multiplication(num1,num2, sum);

60     // 输出结果

61     printf("%s\n  *\n%s\n =\n", num1, num2);

62     for(i = len-1; i>=0; i--)

63         printf("%d", sum[i]);

64     printf("\n");

65     return0;

66 }

4、大数除法

    大数除法是四则运算里面最难的一种。不同于一般的模拟，除法操作不是模仿手工除法，而是利用减法操作来实现的。其基本思想是反复做除法，看从被除数里面最多能减去多少个除数，商就是多少。逐个减显然太慢，要判断一次最多能减少多少个整数(除数)的10的n次方。

以7546除以23为例：

    先用7546减去23的100倍，即减去2300，可以减3次，余下646，此时商就是300(300=100*3)；

    然后646减去23的10倍，即减去230，可以减2次，余下186，此时商就是320(320=300+10*2)；

    然后186减去23，可以减8次，余下2，此时商就是328 (328=320+1*8)；

    因为2除以23的结果小于1，而我们又不用计算小数点位，所以不必再继续算下去了。

下面是C语言的两个正大数相除的参考代码，计算结果中没有小数：

  1 #include<stdio.h>

  2 #include<string.h>

  3#define MAX 1000   // 大数的最大位数 

  4

  5// 注：

  6// 本代码在以下博客代码中进行修改：

  7//http://www.cnblogs.com/javawebsoa/archive/2013/08/01/3231078.html

  8//

  9

 10

 11/*

 12  函数SubStract功能：

 13  用长度为len1的大整数p1减去长度为len2的大整数p2

 14  结果存在p1中，返回值代表结果的长度

 15  不够减：返回-1 ， 正好够：返回0

 16*/

 17int SubStract(int *p1, int len1, int *p2, int len2)

 18 {

 19     int i;

 20     if(len1 < len2)

 21        return -1;

 22     if(len1 == len2 )

 23    {                        // 判断p1 > p2

 24        for(i = len1-1; i >= 0; i--)

 25        {

 26            if(p1[i] > p2[i])   // 若大，则满足条件，可做减法

 27                 break;

 28            elseif(p1[i] < p2[i]) // 否则返回-1

 29                 return -1;

 30        }

 31     }

 32     for(i = 0; i <= len1-1; i++) // 从低位开始做减法

 33     {

 34        p1[i] -= p2[i];         // 相减

 35        if(p1[i] < 0)           // 若是否需要借位

 36        {   // 借位

 37            p1[i] += 10;

 38            p1[i+1]--;

 39        }

 40     }

 41     for(i = len1-1; i >= 0; i--) // 查找结果的最高位

 42     {

 43        if( p1[i] )             //最高位第一个不为0

 44            return (i+1);       //得到位数并返回

 45     }

 46     return0;                   //两数相等的时候返回0

 47 }

 48

 49

 50/*

 51  大数除法---结果不包括小数点

 52  num1 被除数

 53  num2 除数

 54  sum  商，存放计算的结果，即：num1/num2=sum

 55  返回数组sum的有效长度，即商的位数

 56*/

 57int Division(char num1[], char num2[], char sum[])

 58 {

 59     int k, i, j;

 60     int len1, len2, len=0;     //大数位数

 61     int dValue;                //两大数相差位数

 62     int nTemp;                 //Subtract函数返回值

 63     int num_a[MAX] = {0};     //被除数

 64     int num_b[MAX] = {0};     //除数

 65     int num_c[MAX] = {0};     //商

 66

 67    len1 = strlen(num1);       //获得大数的位数

 68    len2 = strlen(num2);

 69    

 70     //将数字字符转换成整型数，且翻转保存在整型数组中

 71     for( j = 0, i = len1-1; i >= 0; j++, i-- )

 72        num_a[j] = num1[i] - '0';

 73     for( j = 0, i = len2-1; i >= 0; j++, i-- )

 74        num_b[j] = num2[i] - '0';

 75

 76     if( len1 < len2 )          //如果被除数小于除数，直接返回-1，表示结果为0

 77     {

 78        return -1;

 79     }

 80    dValue = len1 - len2;      //相差位数

 81     for (i = len1-1; i >= 0; i--)   //将除数扩大，使得除数和被除数位数相等

 82     {

 83        if (i >= dValue)

 84            num_b[i] = num_b[i-dValue];

 85        else                         //低位置0

 86            num_b[i] = 0;

 87     }

 88    len2 = len1;

 89     for(j = 0; j <= dValue; j++ )    //重复调用，同时记录减成功的次数，即为商

 90     {

 91        while((nTemp = SubStract(num_a, len1, num_b+j, len2-j)) >= 0)

 92        {

 93            len1 = nTemp;            //结果长度

 94            num_c[dValue-j]++;       //每成功减一次，将商的相应位加1

 95        }

 96     }

 97     // 计算商的位数，并将商放在sum字符数组中

 98     for(i = MAX-1; num_c[i] == 0 && i >= 0; i-- ); //跳过高位0，获取商的位数

 99     if(i >= 0)

100         len = i + 1; // 保存位数

101     for(j = 0; i >= 0; i--, j++)     // 将结果复制到sum数组中

102         sum[j] = num_c[i] + '0';

103     sum[j] = '\0';   // sum字符数组结尾置0

104     return len;     // 返回商的位数

105 }

106

107

108int main()

109 {

110     int i;

111     int len;                // 商的位数

112     char num1[MAX] = "1234567899876543210";   // 第一个大数

113     char num2[MAX] = "20160415123025";             // 第二个大数

114     char sum[MAX] = {0};    // 计算结果

115

116     //scanf("%s", num1);      //以字符串形式读入大数

117     //scanf("%s", num2);

118    

119     len = Division(num1, num2,sum);

120    

121     //输出结果

122     printf("%s\n ÷\n%s\n  =\n", num1, num2);

123     if( len>=0 )

124     {

125         for(i = 0; i < len; i++ )

126             printf("%c", sum[i]);

127     }

128     else

129     {

130         printf("0");

131     }

132     printf("\n");

133    

134     return0;

135 }

13、     判断一个整数是否是2的整数次幂.(n&(n-1))

第一种

2   10

4   100

8   1000

。。。。。

发现规律没有，2的n次方变成二进制后首位为1，其余位都为0。

所以嘞，我们讨巧的可以这么做，假设输入的为int型：

15、B+树

16、 最长递增子序列（nlogn的算法）

最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。

代码如下：

#include<iostream>

#include<vector>

usingnamespace std;

int maxSubSum(const vector<int> & arr,int &begin,int &end){

    int maxSum=0;

    int currSum=0;

    int newbegin=0;

    for(int i=0;i<arr.size();++i){

        currSum+=arr[i];

        if(currSum>maxSum){

            maxSum=currSum;

            begin=newbegin;

            end=i;

        }

        if(currSum<0){

            currSum=0;

            newbegin=i+1;

        }

    }

    return maxSum;

}

最长公共子串问题的基本表述为：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

对于该问题，直观的思路就是问题要求什么就找出什么。要子串，就找子串；要相同，就比较每个字符；要最长就记录最长。所以很容易就可以想到如下的解法。

 1int longestCommonSubstring_n3(conststring& str1, conststring& str2)

 2 {  

 3    size_t size1 = str1.size();

 4    size_t size2 = str2.size();

 5    if (size1 == 0 || size2 == 0) return0;

 6 

 7    // the start position of substring in original string

 8    int start1 = -1;

 9    int start2 = -1;

10     // the longest length of commonsubstring

11     int longest = 0;

12 

13     // record how many comparisons thesolution did;

14     // it can be used to know whichalgorithm is better

15     int comparisons = 0;

16 

17     for (int i = 0; i < size1; ++i)

18     {

19         for (int j = 0; j < size2; ++j)

20         {

21             // find longest length of prefix

22             int length = 0;

23             int m = i;

24             int n = j;

25             while(m < size1 && n < size2)

26             {

27                 ++comparisons;

28                 if (str1[m] != str2[n]) break;

29 

30                 ++length;

31                 ++m;

32                 ++n;

33             }

34 

35             if (longest < length)

36             {

37                 longest = length;

38                 start1 = i;

39                 start2 = j;

40             }

41         }

42     }

43 #ifdef IDER_DEBUG

44     cout<< "(first, second, comparisions) =("

45         << start1 << ", " << start2 << ", " << comparisons

46         << ")" << endl;

47#endif

48     return longest;

49 }

既然最长公共子串是最长公共子序列的变体，那么最长公共子串是不是也可以用动态规划来求解呢？

我们还是像之前一样“从后向前”考虑是否能分解这个问题，在最大子数组和中，我们也说过，对于数组问题，可以考虑“如何将arr[0,...i]的问题转为求解arr[0,...i-1]的问题”，类似最长公共子序列的分析，使用dp[i][j]表示X[0-i]与Y[0-j]的最长公共子串长度，因为要求子串连续，所以对于X[i]与Y[j]来讲，它们要么与之前的公共子串构成新的公共子串；要么就是不构成公共子串。故状态转移方程

X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1

X[i] != Y[j]，dp[i][j] = 0

对于初始化，i==0或者j==0，如果X[i] == Y[j]，dp[i][j] = 1；否则dp[i][j] = 0。

代码如下：

17 、跳台阶问题

一个8*8的方格子，A点在左下角，B点在右上角，求A点到B点的最短路径有多少条。

　　答：从图中可以看出，A点到B点的最短路径为16，即A点横走8小格，纵走8小格才能最快到达B点，这是排列组合的问题，即从最短路径16中选取8个横走的小格子(或者从最短路径16中选取8个纵走的小格子)。所以从A点到B点的最短路径条数，直接可以算出来，即为：

代码如下：

int pathNum(int step,int row)

{

   Inttemp1,temp2,temp3,num;

 Temp1=1;temp2 =1;tmp3 =1;

  For(inti=1;i<=row;r++)

    Temp1*=I;

 For(inti=1;i<=step – row;i++)

    Temp2*=I;

For(int i=1;i<=row;i++)

   Temp3*=I;

Num = temp1 /(temp2*temp3);

Return num;

}

18、 已知一个单向键表，但不知道它的头指针，给出链表中一个节点的指针，并且已知该结点的后续节点不为空，要求删除该结点

这个题咋看之下无从入手，因为不知道头指针，就无法获得那个节点的前置节点。这时候就得打破常规的思维了，删除一个节点，其实就是让它的后续节点取代它。

Node *temp = p->next;

memcpy(p, temp, sizeof(Node));

free(temp);

19、C++ STL中vector内存用尽后，为啥每次是两倍增长，而不是3倍或其他倍数？

【解】 1， 2， 4， 8， 16， 32，……可以看到，每次需要申请的空间都无法用到前面释放的空间。所以其实2倍并不是最佳增长倍数，最佳增长倍数大约为黄金分割 1.618。例如：Java中的ArrayList每次扩容为1.5倍。

20  vector怎么实现动态空间分布

如果没有空间容纳新的元素，容器不可能简单的将其添加到内存的其他位置，因为vector的元素必须连续存储。因此容器必须分配新的空间来保存已用的元素和新的元素。将已有元素从旧位置移动到新空间，然后添加新元素，释放旧空间。申请的空间是成倍增涨的。

  21 hash， 任何一个技术面试官必问（例如为什么一般hashtable的桶数会取一个素数？如何有效避免hash结果值的碰撞）

      是为了减少哈希冲突。

22、100亿个数，求最大的1万个数，并说出算法的时间复杂度。

先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。

优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起再找出最终的结果。

23、将一个4字节的整数的二进制表示中的001替换为011，输出替换后的整数。

24、将一个数组右移几位，比如数组为1 2 3 4，右移一位即为4 1 2 3。

 解法一：辅助空间法，思路很简单，就是另外开辟一块和原来数组一样大小的空间。然后先把原来数组的最后面的m个元素复制到新数组的前面，然后再把原来数组的前面的元素复制到新数组的后面，最后再把新数组的全部元素复制到原来的数组中，即可。 该方法很容易被想到，但是需要额外的辅助空间。

 解法二：三步操作法。

  第一步：将原来数组全部反序。

         第二步：再将前m个元素反序。

第三步：最后将后面的元素反序。

解法二不需要额外的辅助空间，是更好的解法。

25、输入一个表示十六进制的字符串，转换为十进制的整数输出。

26、 在两个有序数组中找出共有元素

若已知同一个数组中没有重复的元素，则可以使用归并排序，然后在排序后的结果查找重复元素。若同一数组中可能存在重复元素，则不能使用归并排序。

另一个方法是使用bitmap，先扫描数组A，把其中出现的元素在bitmap中赋值为1，然后扫描数组B，若某元素在bitmap中已为1，则输出该元素。

 二分查找大家都很熟悉，但如果给出的数组a可能进行了循环移位，如［1 2 3 4］变成了［2 3 4 1］（是否移位，移了多少位都不知道），能否写一个程序，快速找出数组中是否存在某元素n

我最初的想法是，遍历数组，找出移位的点，然后判断n属于哪个区间，进而在那个区间中对n进行二分查找。

但是面试官提示我，原本二分查找的时间复杂度是O(lgn)，而遍历数组的时间复杂度是O(n)，时间复杂度增加太多，能不能找到一个不改变时间复杂度的算法。

思考之后我发现，查找移位点其实可以用二分查找来实现，这样整体时间复杂度就不会增加了。移位点s的特征是：在它左边的元素比在它右边的元素大。可以用以下方法找到移位点：区间的头为b，尾为e，中间点为m；若a[b]<=a[e]，那么该区间中不存在移位点。若a[b]>a[m]，则移位点在该区间的左半段；若a[m]>a[e]，则移位点在该区间的右半段。

回家后我再思考这个问题，发现上面的方法可以更简化，那就是把判断移位点和查找元素n的过程结合在一起。

对于一段区间be，中间点为m。若a[b]<a[e]，说明不存在移位点，可以直接在这段区间上用二分查找查找n；若存在移位点，则m和s把整个区间分为三段，得小心判断n属于哪个区间，然后把范围缩小，直到该范围中不存在移位点。

intbinSearch(int*a, intlen, intn)

{

    if( len<= 0)

        return-1;

    intb =0;

    inte =len - 1;

    if(a[b]== n)

        returnb;

    elseif(a[e]== n)

        returne;

    intm =(b + e) / 2;

    while(b<m)

    {

        if(a[b]>= a[e])  // be区间中存在移位点

        {

            if(a[m]>= a[b])        // 移位点在me区间中

            {

                if(n> a[m] || n< a[b])

                    b= m;

                elseif(n ==a[m])

                    returnm;

                elseif(n ==a[b])

                    returnb;

                else

                    e= m;

            }

            elseif(a[m]<= a[e])   // 移位点在bm区间中

            {

                if(n> a[e] || n< a[m])

                    e= m;

                elseif(n ==a[m])

                    returnm;

                elseif(n ==a[e])

                    returne;

                else

                    b= m;

            }

        }

        else               // be区间中不存在移位点，直接用二分查找

        {

            if(n<a[m])

                e= m;

            elseif(n ==a[m])

                returnm;

            else

                b= m;

        }

        m = (b +e) / 2;

    }

    return-1;

}

这道题包括和面试官讨论及写出代码，总共花了快一个小时，它给我的感触是，对于陌生的算法，最好的办法是先把思路用伪代码写出来，写的时候不考虑条件怎样成立、边界处理等细节，确定了整体思路后，再写出代码并考虑细节问题。在写代码的时候，需要注意考虑特殊情况：数组为空，数组中只有一个元素，数组中只有两个元素，数组中元素都一样，要增加、删除或查找的是首尾元素等。

27、给定两个数组a和b，求所有在a数组中不在b数组的元素；

28、未知大小的文件，翻转整个文件

  29、各类排序：大根堆的实现，快排（如何避免最糟糕的状态？），bitmap的运用等等

其他
1 红黑树的性质以及插入和删除

2 如果内存中有个cache存储qq号和最近登录时间问怎么样做hit和淘汰

3 shell读文件并把文件的内容输出到控制台

While read line

do

    echo$line

done< $file

4. 某文件的第二列内容为数字，请用awk求出这些数字的和

awk 'BEGIN{sum = 0;} {sum += $2;} END{print sum;}'$file

5. 按层次遍历二叉树

要点：使用队列

voidlayerOrder(BTree *tree)

{

    if(tree == NULL)

        return;

    queue<BTree*> q;

    q.push(tree);

    BTree *p = NULL;

    while(!q.empty())

    {

        p= q.front();

        visit(p)；

        q.pop();

        if(p->lchild != NULL)

            q.push(p->lchild);

        if(p->rchild != NULL)

            q.push(p->rchild)；

    }

}

6、问题:有两个文件,各放了100万个QQ号,请找出两个文件中相同的QQ号,用SHELL脚本实现。

#!/bin/sh
touch c.txt
for string1 in `cat a.txt`
do
for string2 in `cat b.txt`
do
if [ "$string1" -eq "$string2" ]
then
echo $string1 >> c.txt
fi
done
done

7、C/C++方向：有N个大小为G的存储单元，用户在不断上传数据，每次上传数据的大小v是随机的，请写一个系统，把上传的数据分配给各个存储单元，使得每个存储单元的使用率和写负责相对均衡，要考虑以下两个初始状态： (1) 每个存储单元的剩余空间相同。 (2) 每个存储单元的剩余空间相差很大.

8、千万级的用户，提供一个服务，该服务有很多模块，现在有一个底层模块需要优化，问怎么实现，在不影响其他服务模块以及用户体验的情况下。（面IEG）

  9、最有难度的一个题目：一个每秒百万级访问量的互联网服务器，每个访问都有数据计算和I/O操作，如果让你设计，你怎么设计？

10、设计一个洗牌的算法，并说出算法的时间复杂度。