1、给定一个字符串A和字符串B，写一函数实现在字符串A中查找字符串B首次出现的位置，如果查找不成功，则返回-1（蛮力法、KMP算法）。
解：
（1）函数strstr()的实现
-
char sstrstr(const char *haystack, const char *needle)
-
{
-
assert(needle != NULL && haystack != NULL);
-
-
while(*haystack != '\0')
-
{
-
int i = 0;
-
while(true)
-
{
-
char an = *(haystack + i);
-
char bm = *(needle + i);
-
if(bm == '\0')
-
{
-
return haystack;
-
}
-
if(an == bm)
-
{
-
i++;
-
}
-
else
-
{
-
break;
-
}
-
}
-
haystack++;
-
}
-
//若needle == '\0'，则返回haystack；反之，则查找失败
-
return *needle == '\0' ? haystack : NULL;
- }
-
//获取next数组
-
void get_next(cosnt char *ptn, int *next)
-
{
-
assert(ptn != NULL && next != NULL);
-
-
int i = 0;
-
int j = -1;
-
next[0] = -1;
-
int plen = strlen(ptn);
-
-
while(i < plen)
-
{
-
if(j == -1 || ptn[i] == ptn[j])
-
{
-
i++;
-
j++;
-
if(ptn[i] != ptn[j])
-
{
-
next[i] = j;
-
}
-
else
-
{
-
next[i] = next[j];
-
}
-
}
-
else
-
{
-
j = next[j];
-
}
-
}
-
}
-
//kmp匹配
-
int kmp_search(const char *src, const char *ptn, int *next, int pos)
-
{
-
int i = pos;
-
int j = 0;
-
if(src == NULL || ptn == NULL)
-
{
-
return -1;
-
}
-
int slen = strlen(src);
-
int plen = strlen(ptn);
-
if(pos < 0 || pos > slen)
-
{
-
return -1;
-
}
-
-
while(i < slen && j < plen)
-
{
-
if(j == -1 || src[i] == ptn[j])
-
{
-
i++;
-
j++;
-
}
-
else
-
{
-
//当匹配失效时，直接用p[j_next]与s[i]比较
-
j = next[j];
-
}
-
}
-
if(j >= plen)
-
{
-
return i - plen; //返回下标，从0开始
-
}
-
else
-
{
-
return -1;
-
}
- }
2、给定两个有序链表，将这两个有序链表合并成一个有序链表.（归并排序的思想，但是需注意的时此处为链表，指针操作稍微复杂些）
解：
具体代码如下所示。
-
ListNode *mergeTwoLists(ListNode *first, ListNode *second)
-
{
-
ListNode *node = NULL;
-
ListNode **p = &node;
-
-
while(first && second)
-
{
-
if(first->value <= second->value)
-
{
-
*p = first;
-
first = first->next;
-
}
-
else
-
{
-
*p = second;
-
second = second->next;
-
}
-
p = &((*p)->next);
-
}
-
if(first)
-
{
-
*p = first;
-
}
-
if(second)
-
{
-
*p = second;
-
}
-
return node;
- }
3、给定两个长度相同的有序的数组，求这两个数组的中位数（使用递归实现，比较数组A和B的中位数大小，若A的中位数大于B的中位数，则这来两个数组的中位数必定在A的前半部分和在B的后半部分，反之则在A的后半部分和B的前半部分，依次而推即可得到最终的整个中位数，注意细节）
解：
（1）将两个数组进行合并，然后取其中位数，代码略。
（2）二分的思想。
4、面向程序设计的五个基本原则。
解：
略。
5、TCP是如何实现流量控制的？（使用了窗口对流量实现控制）
解：
（1）TCP利用滑动窗口实现流量控制。
如果发送方把数据发送的太快，接收方可能会来不及接收，这就会造成数据的丢失。
所谓流量控制就是让发送方的发送速率不要太快，要让接收方来得及接收。
利用滑动窗口机制可以很方便地在TCP连接上实现对发送方的流量控制。
设A向B发送数据，在连接建立时，B告诉A：“我的接收窗口是rwnd=400”（这里的rwnd表示receive window）。因此，发送方的发送窗口不能超过接收方给出的接收窗口的数值。请注意，TCP的窗口单位是字节，不是报文段。
从图中可以看出，B进行了三次流量控制。第一次把窗口减少到了rwnd = 300，第二次又减少到了rwnd=100，最后减少到rwnd=0，即不允许发送方再发送数据了。这种使发送方暂停发送的状态将持续到主机B重新发送一个新的窗口值为止。
TCP为每一个连接设有一个持续计时器。只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器。若持续计时器设置的时间到期，就发送一个零窗口探测报文段（携1字节数据），那么收到这个报文段的一方就重新设置持续计时器。
必须考虑传输速率
可以用不同的机制来控制TCP报文段的发送时机。如TCP维持一个变量，它等于最大报文段长度MSS。只要缓存中存放的数据达到MSS字节时，就组装成一个TCP报文段发送出去；由发送方的应用进程指明要求发送报文段，即TCP支持的推送操作；发送方的一个计时器到期，这时就把已有的缓存数据装入报文段发送出去。
Nagle算法：若发送应用进程把要发送的数据逐个字节地送到TCP的发送缓存，则发送方就把第一个数据字节先发送出去，把后面到达的数据字节都缓存起来。当发送方接收到第一个数据字符的确认后，再把发送缓存中的所有数据组成一个报文段发送出去，同时继续对随后到达的数据进程缓存。只有在收到对前一个报文段的确认后才继续发送下一个报文段。当数据到达较快而网络速率较慢时，用这样的方法可明显地减少所用的网络带宽。
TCP的拥塞控制
拥塞：即对资源的需要超过了可用的资源。
拥塞控制：防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制所要做的都有一个前提：网络能够承受现有的网络负荷。拥塞控制是一个全局性的过程。
流量控制：指点对点通信量的控制，是端到端的问题。流量控制所要做的就是抑制发送端法发送数据的速率，以便使接收端来不及接收。
几种拥塞控制方法
慢启动、拥塞避免、快速重传、快速恢复。
慢启动和拥塞避免
发送方维持一个拥塞窗口的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地变化。发送方让自己的发送窗口等于拥塞窗口。
发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减少一些，以减少注入到网络中的分组数。
慢启动算法：当主机开始发送数据时，如果立即把所有的数据注入到网络，那么就有可能引起网络拥塞，因为现在并不清楚网络的负荷情况。因此，较好的方法是先探测下，即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口的数值。通常在刚刚开始发送报文段的时候，先把拥塞窗口cwnd设置为一个最大报文段MSS的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送方的拥塞窗口cwnd，可以使分组注入到网络的速率更加合理。
每经过一个传输过程，拥塞窗口cwnd就加倍。一个传输轮次所经历过的时间就是往返时间RTT。
另外，慢启动的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方再开始时只发送一个报文段，然后在逐渐增大cwnd。
为了防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置一个慢启动阈值ssthresh状态变量。慢启动阈值ssthresh的用法如下：
拥塞避免算法：让拥塞窗口cwnd缓慢地增长，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按现行规律缓慢增长，比慢启动算法的拥塞窗口增长速率缓慢得多。
无论是慢启动阶段还是拥塞避免阶段，只要发送方判断网络出现拥塞（其根据是没有收到确认），就要把慢启动阈值ssthresh设置为出现拥塞时的发送方窗口值的一半。然后把拥塞窗口cwnd重新设置为1，执行慢启动算法。
强调：拥塞避免并非指完全能够避免了拥塞。只是使网络比较不容易出现拥塞。
另外还有快速重传和快速恢复机制。
6、进程和线程之间的区别。
解：
（1）进程是程序的一次执行，是系统资源分配的基本单位。而线程是系统调度的基本单位。
（2）进程消耗的系统资源比较多，而线程基本不消耗系统资源，进程有自己的地址空间，不共享存储区域，而线程则共享其属主进程的地址空间，共享同一存储区域。
（3）一个程序至少有一个进程，而一个进程至少有一个线程。线程是轻量型进程。
7、大量电影播放日志文件统计出前100个播放次数最多的电影名称
解：
分而治之的思想。
（1）将大的日志文件hash(电影名称)%n（n根据实际情况而定），这样产生了n个小文件，这n个小文件的每一个都可以放入内存的；
（2）对每一个小文件进行统计其所包含的每部电影出现的次数，同时求出每个小文件中播放次数最多的100部电影；
（3）对这n个小文件取出的n个100部电影进行统计，可以用最大堆，从而求出整个大的日志文件中前100次播放次数最多的电影名称。