1、有序链表合并
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
} else if (l2 == NULL) {
return l1;
} else {
if (l1->val <= l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
}
};
2、一个数列：-1 2 -3 4 -5 6 …询问q次，每次询问区间[l,r]的区间和,输出每个询问的答案
第1个和第2个加起来为1，第3，4个加起来也为1…
所以前i项和为：
i/2+(i&1)*i;
区间和可以用前i项和算出来了
3、const的含义及实现机制,比如: const int 1,是怎么做到i只可读的?
const用来说明所定义的变量是只读的。
这些在编译期间完成,編译器可能使用常数直接替换掉对此变量的引用。
4、TCP三次握手的过程, accept发生在三次握手哪个阶段？
accept发生在三次握手之后。
第一次握手:客户端发送syn包(syn=j)到服务器。
第二次握手:服务器收到syn包,必须确认客户的sY(ack=j+1),同时自己也发送一个ASK包(ask=k)。
第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=k+1)。
握手完成后,客户端和服务器就建立了tcp连接。这时可以调用 accept函数获得此连接。
5、用UDP协议道讯时怎样得知目标机是否获得了数据包?
可以在每个数据包中插入一个唯一的ID,比如 timestamp或者递增的int。
发送方在发送数据时将此ID和发送时间记录在本地。
接收方在收到数据后将ID再发给发送方作为回应。
发送方如果收到回应,则知道接收方已经收到相应的数据包;如果在指定时间内没有收到回应,则数据包可能丢失,需要重复上面的过程重新发送一次,直到确定对方收到。
6、如何输出源文件的标题和目前执行行的行数?
printf(“The file name:%dn”, FILE);
printf(“The current line No: %d\n”, LINE);
ANSI C标准预定义宏;
LINE
FILE
DATE
TIME
STDC 当要求程序严格遵循ANSC标准时该标识符被赋值为1
cplusplus 当编写C+程序时该标识符被定义
7、希尔,冒泡,快速,插入哪个平均速度最快?
快速排序
快速排序、归并排序和基数排序在不同情况下都是最快最有用的
8、腾讯服务器每秒有2W个QQ号同时上线,找出5min内重新登入的qq号并打印出来。
如果空间足够大,可以定义一个大的数组a[qq号],初始为零然后.这个qq号登陆了
就a[qq号]++
最后统计大于等于2的QQ号
这个用空间来代替时间
不成熟的想法
2w x 300s
所以用6000.000个桶。刪除超时的算法后面说,所以平均桶的大小是1
假设qq号码一共有1010个,所以每个桶装的q号码是1010/(6*10~6)个,
这个是插入时候的最坏效率(插入同个桶的时候是顺序查找插入位置的)
qq的节点结构和上面大家讨论的基本一样,增加一个指针指
向输出列表,后面说
struct QQstruct {undefinednum_type qqnum,timestamp last_logon_time,QQstruct *pre,QQstruct *next,OutPutlist *out //用于free节点的时候,顺便更新下输出列表}
另外增加两个指针列表
第一个大小300的循环链表,自带一个指向 QQStruct的域,循环存300秒内的qq指针。
时间一过就fee掉,所以保证所有桶占用的空闾在2wX30以内.
第二个是输出列表,就是存放题目需要输出的节点。
如果登陆的用户,5分钟内完全没有重复的话,每秒free2w个节点
不过在free的时候,要判断一下时间是不是真的超时,因为把节点入桶的时候,遇到重复的,
会更新一下最后登陆的时间。当然啦,这个时候,要把这个q号码放到需要输出的列表里面
9、请描述C++的内存管理方式.
在c++中内存主要分为5个存储区：
栈（Stack）：局部变量，函数参数等存储在该区，由编译器自动分配和释放.栈属于计算机系统的数据结构，进栈出栈有相应的计算机指令支持，而且分配专门的寄存器存储栈的地址，效率分高，内存空间是连续的，但栈的内存空间有限。
堆(Heap)：需要程序员手动分配和释放（new,delete），属于动态分配方式。内存空间几乎没有限制，内存空间不连续，因此会产生内存碎片。操作系统有一个记录空间内存的链表，当收到内存申请时遍历链表，找到第一个空间大于申请空间的堆节点，将该节点分配给程序，并将该节点从链表中删除。一般，系统会在该内存空间的首地址处记录本次分配的内存大小，用于delete释放该内存空间。
全局/静态存储区:全局变量，静态变量分配到该区，到程序结束时自动释放，包括DATA段（全局初始化区）与BSS段（全局未初始化段）。其中，初始化的全局变量和静态变量存放在DATA段，未初始化的全局变量和静态变量存放在BSS段。BSS段特点：在程序执行前BSS段自动清零，所以未初始化的全局变量和静态变量在程序执行前已经成为0.
文字常量区：存放常量，而且不允许修改。程序结束后由系统释放。
程序代码区：存放程序的二进制代码
10、hash表的实现，包括STL中的哈希桶长度常数。
hash表的实现主要涉及两个问题：散列函数和碰撞处理。
1）hash function （散列函数）。最常见的散列函数：f(x) = x % TableSize .
2）碰撞问题（不同元素的散列值相同）。解决碰撞问题的方法有许多种，包括线性探测、二次探测、开链等做法。SGL版本使用开链法，使用一个链表保持相同散列值的元素。
虽然开链法并不要求表格大小必须为质数，但SGI STL仍然以质数来设计表格大小，并且将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28个质数之中，“最接近某数并大于某数”的质数。
11、hash表如何rehash，怎么处理其中保存的资源.
先想想为什么需要rehash:
因为，当loadFactor（负载因子）<=1时，hash表查找的期望复杂度为O(1). 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <1的情况下，才能够添加。
模仿C++的vector扩容方式，Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。
12、redis的主从复制怎么做的?
Redis旧版复制功能只有同步和命令传播。新版复制功能加入了部分同步的功能。
1）同步：
2）命令传播：
当主服务器会将自己执行的写命令，也即是造成主从服务器不一致的那条写命令，发送给从服务器执行，当从服务器执行了相同的写命令之后，主从服务器将再次回到一致状态。
3）部分同步：（断线后重复制）
复制偏移量：通过对比主从服务器的复制偏移量，程序可以很容易地知道主从服务器是否处于一致状态。
复制积压缓冲区：主服务保存最近的写命令到复制积压缓冲区，是一个先进先出队列
服务器运行ID：从服务器记录上次同步的主服务器的Id。
13、程序什么时候应该使用线程，什么时候单线程效率高
1 耗时的操作使用线程，提高应用程序响应
2 并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求。
3 多CPU系统中，使用线程提高CPU利用率
4 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序会利于理解和修改。
其他情况都使用单线程。
14、内存的分配方式有几种?
1)从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量。
2)在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
3)从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。
15、设计DNS服务器中cache的数据结构。
要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。
总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
16、如何找出字典中的兄弟单词。给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词？
使用hash_map和链表。
首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。
使用链表将所有兄弟单词串在一起，hash_map的key为单词的key，value为链表的起始地址。
开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的key，然后到hash_map中找到对应的链表即可。
这样创建hash_map时时间复杂度为O(n)，查找兄弟单词时时间复杂度是O(1)。
17、找出第k大的数字所在的位置。写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
先找到第k大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第k大的数。
我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第k大的数字。这样总体复杂度为O(NlogN)。
我们还可以通过二分的思想，找到第k大的数字，而不必对整个数组排序。从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，{x,xx,…,t}<{y,yy,…}。
在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。
然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。
平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O(N)。
18、给一个奇数阶N幻方,填入数字1,2,3.N^N,使得橫竖斜方向上的和都相同
#inc1ude
#include
#include
usingnamespace std;
int main()
{
int n;
cin>>n;
int i;
int **Matr = new int *[n]; //动态分配二维数组
for(i=0;i<n;++i)
Matr[i]=new int[n]: //动态分配二维
数组
//j=n/2代表首行中间数作为起点,即1所在位置
int j=n/2,num=1: //初始值
i=0;
while(num!=n*n+1) {
//往右上角延升, 若超出则用%转移到左下角
Matr [(i%n+n)%n][(j%n+n)%n]=num;
//斜行的长度和n是相等的,超出则转至下一写信.
if (num%n==0) {
i++;
} else {
i--;
j++;
}
num++;
}
for (i=0;i<n;i++) {
for (j=0;j<n;++j) {
cout << setw((int)log10(n*n)+4)<<Matr[i][j]; //格式控制
cout <<endl<<endl;//格式控制
}
}
for (i=0; i<n; ++i) {
delete [] Matr[i];
}
return 1;
}
