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、一個(gè)數(shù)列：-1 2 -3 4 -5 6 …詢問q次，每次詢問區(qū)間[l,r]的區(qū)間和,輸出每個(gè)詢問的答案
第1個(gè)和第2個(gè)加起來為1，第3，4個(gè)加起來也為1…
所以前i項(xiàng)和為：
i/2+(i&1)*i;
區(qū)間和可以用前i項(xiàng)和算出來了
3、const的含義及實(shí)現(xiàn)機(jī)制,比如: const int 1,是怎么做到i只可讀的?
const用來說明所定義的變量是只讀的。
這些在編譯期間完成,編譯器可能使用常數(shù)直接替換掉對(duì)此變量的引用。
4、TCP三次握手的過程, accept發(fā)生在三次握手哪個(gè)階段？
accept發(fā)生在三次握手之后。
第一次握手:客戶端發(fā)送syn包(syn=j)到服務(wù)器。
第二次握手:服務(wù)器收到syn包,必須確認(rèn)客戶的sY(ack=j+1),同時(shí)自己也發(fā)送一個(gè)ASK包(ask=k)。
第三次握手:客戶端收到服務(wù)器的SYN+ACK包,向服務(wù)器發(fā)送確認(rèn)包ACK(ack=k+1)。
握手完成后,客戶端和服務(wù)器就建立了tcp連接。這時(shí)可以調(diào)用 accept函數(shù)獲得此連接。
5、用UDP協(xié)議道訊時(shí)怎樣得知目標(biāo)機(jī)是否獲得了數(shù)據(jù)包?
可以在每個(gè)數(shù)據(jù)包中插入一個(gè)唯一的ID,比如 timestamp或者遞增的int。
發(fā)送方在發(fā)送數(shù)據(jù)時(shí)將此ID和發(fā)送時(shí)間記錄在本地。
接收方在收到數(shù)據(jù)后將ID再發(fā)給發(fā)送方作為回應(yīng)。
發(fā)送方如果收到回應(yīng),則知道接收方已經(jīng)收到相應(yīng)的數(shù)據(jù)包;如果在指定時(shí)間內(nèi)沒有收到回應(yīng),則數(shù)據(jù)包可能丟失,需要重復(fù)上面的過程重新發(fā)送一次,直到確定對(duì)方收到。
6、如何輸出源文件的標(biāo)題和目前執(zhí)行行的行數(shù)?
printf(“The file name:%dn”,?FILE);
printf(“The current line No: %d\n”,?LINE);
ANSI C標(biāo)準(zhǔn)預(yù)定義宏;
LINE
FILE
DATE
TIME
STDC?當(dāng)要求程序嚴(yán)格遵循ANSC標(biāo)準(zhǔn)時(shí)該標(biāo)識(shí)符被賦值為1
cplusplus?當(dāng)編寫C+程序時(shí)該標(biāo)識(shí)符被定義
7、希爾,冒泡,快速,插入哪個(gè)平均速度最快?
快速排序
快速排序、歸并排序和基數(shù)排序在不同情況下都是最快最有用的
8、騰訊服務(wù)器每秒有2W個(gè)QQ號(hào)同時(shí)上線,找出5min內(nèi)重新登入的qq號(hào)并打印出來。
如果空間足夠大,可以定義一個(gè)大的數(shù)組a[qq號(hào)],初始為零然后.這個(gè)qq號(hào)登陸了
就a[qq號(hào)]++
最后統(tǒng)計(jì)大于等于2的QQ號(hào)
這個(gè)用空間來代替時(shí)間
不成熟的想法
2w x 300s
所以用6000.000個(gè)桶。刪除超時(shí)的算法后面說,所以平均桶的大小是1
假設(shè)qq號(hào)碼一共有1010個(gè),所以每個(gè)桶裝的q號(hào)碼是1010/(6*10~6)個(gè),
這個(gè)是插入時(shí)候的最壞效率(插入同個(gè)桶的時(shí)候是順序查找插入位置的)
qq的節(jié)點(diǎn)結(jié)構(gòu)和上面大家討論的基本一樣,增加一個(gè)指針指
向輸出列表,后面說
struct QQstruct {undefinednum_type qqnum,timestamp last_logon_time,QQstruct *pre,QQstruct *next,OutPutlist *out //用于free節(jié)點(diǎn)的時(shí)候,順便更新下輸出列表}
另外增加兩個(gè)指針列表
第一個(gè)大小300的循環(huán)鏈表,自帶一個(gè)指向 QQStruct的域,循環(huán)存300秒內(nèi)的qq指針。
時(shí)間一過就fee掉,所以保證所有桶占用的空閭在2wX30以內(nèi).
第二個(gè)是輸出列表,就是存放題目需要輸出的節(jié)點(diǎn)。
如果登陸的用戶,5分鐘內(nèi)完全沒有重復(fù)的話,每秒free2w個(gè)節(jié)點(diǎn)
不過在free的時(shí)候,要判斷一下時(shí)間是不是真的超時(shí),因?yàn)榘压?jié)點(diǎn)入桶的時(shí)候,遇到重復(fù)的,
會(huì)更新一下最后登陸的時(shí)間。當(dāng)然啦,這個(gè)時(shí)候,要把這個(gè)q號(hào)碼放到需要輸出的列表里面
9、請(qǐng)描述C++的內(nèi)存管理方式.
在c++中內(nèi)存主要分為5個(gè)存儲(chǔ)區(qū)：
棧（Stack）：局部變量，函數(shù)參數(shù)等存儲(chǔ)在該區(qū)，由編譯器自動(dòng)分配和釋放.棧屬于計(jì)算機(jī)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，進(jìn)棧出棧有相應(yīng)的計(jì)算機(jī)指令支持，而且分配專門的寄存器存儲(chǔ)棧的地址，效率分高，內(nèi)存空間是連續(xù)的，但棧的內(nèi)存空間有限。
堆(Heap)：需要程序員手動(dòng)分配和釋放（new,delete），屬于動(dòng)態(tài)分配方式。內(nèi)存空間幾乎沒有限制，內(nèi)存空間不連續(xù)，因此會(huì)產(chǎn)生內(nèi)存碎片。操作系統(tǒng)有一個(gè)記錄空間內(nèi)存的鏈表，當(dāng)收到內(nèi)存申請(qǐng)時(shí)遍歷鏈表，找到第一個(gè)空間大于申請(qǐng)空間的堆節(jié)點(diǎn)，將該節(jié)點(diǎn)分配給程序，并將該節(jié)點(diǎn)從鏈表中刪除。一般，系統(tǒng)會(huì)在該內(nèi)存空間的首地址處記錄本次分配的內(nèi)存大小，用于delete釋放該內(nèi)存空間。
全局/靜態(tài)存儲(chǔ)區(qū):全局變量，靜態(tài)變量分配到該區(qū)，到程序結(jié)束時(shí)自動(dòng)釋放，包括DATA段（全局初始化區(qū)）與BSS段（全局未初始化段）。其中，初始化的全局變量和靜態(tài)變量存放在DATA段，未初始化的全局變量和靜態(tài)變量存放在BSS段。BSS段特點(diǎn)：在程序執(zhí)行前BSS段自動(dòng)清零，所以未初始化的全局變量和靜態(tài)變量在程序執(zhí)行前已經(jīng)成為0.
文字常量區(qū)：存放常量，而且不允許修改。程序結(jié)束后由系統(tǒng)釋放。
程序代碼區(qū)：存放程序的二進(jìn)制代碼
10、hash表的實(shí)現(xiàn)，包括STL中的哈希桶長(zhǎng)度常數(shù)。
hash表的實(shí)現(xiàn)主要涉及兩個(gè)問題：散列函數(shù)和碰撞處理。
1）hash function （散列函數(shù)）。最常見的散列函數(shù)：f(x) = x % TableSize .
2）碰撞問題（不同元素的散列值相同）。解決碰撞問題的方法有許多種，包括線性探測(cè)、二次探測(cè)、開鏈等做法。SGL版本使用開鏈法，使用一個(gè)鏈表保持相同散列值的元素。
雖然開鏈法并不要求表格大小必須為質(zhì)數(shù)，但SGI STL仍然以質(zhì)數(shù)來設(shè)計(jì)表格大小，并且將28個(gè)質(zhì)數(shù)（逐漸呈現(xiàn)大約兩倍的關(guān)系）計(jì)算好，以備隨時(shí)訪問，同時(shí)提供一個(gè)函數(shù)，用來查詢?cè)谶@28個(gè)質(zhì)數(shù)之中，“最接近某數(shù)并大于某數(shù)”的質(zhì)數(shù)。
11、hash表如何rehash，怎么處理其中保存的資源.
先想想為什么需要rehash:
因?yàn)椋?dāng)loadFactor（負(fù)載因子）<=1時(shí)，hash表查找的期望復(fù)雜度為O(1). 因此，每次往hash表中添加元素時(shí)，我們必須保證是在loadFactor <1的情況下，才能夠添加。
模仿C++的vector擴(kuò)容方式，Hash表中每次發(fā)現(xiàn)loadFactor==1時(shí)，就開辟一個(gè)原來桶數(shù)組的兩倍空間（稱為新桶數(shù)組），然后把原來的桶數(shù)組中元素全部轉(zhuǎn)移過來到新的桶數(shù)組中。注意這里轉(zhuǎn)移是需要元素一個(gè)個(gè)重新哈希到新桶中的。
12、redis的主從復(fù)制怎么做的?
Redis舊版復(fù)制功能只有同步和命令傳播。新版復(fù)制功能加入了部分同步的功能。
1）同步：
2）命令傳播：
當(dāng)主服務(wù)器會(huì)將自己執(zhí)行的寫命令，也即是造成主從服務(wù)器不一致的那條寫命令，發(fā)送給從服務(wù)器執(zhí)行，當(dāng)從服務(wù)器執(zhí)行了相同的寫命令之后，主從服務(wù)器將再次回到一致狀態(tài)。
3）部分同步：（斷線后重復(fù)制）
復(fù)制偏移量：通過對(duì)比主從服務(wù)器的復(fù)制偏移量，程序可以很容易地知道主從服務(wù)器是否處于一致狀態(tài)。
復(fù)制積壓緩沖區(qū)：主服務(wù)保存最近的寫命令到復(fù)制積壓緩沖區(qū)，是一個(gè)先進(jìn)先出隊(duì)列
服務(wù)器運(yùn)行ID：從服務(wù)器記錄上次同步的主服務(wù)器的Id。
13、程序什么時(shí)候應(yīng)該使用線程，什么時(shí)候單線程效率高
1 耗時(shí)的操作使用線程，提高應(yīng)用程序響應(yīng)
2 并行操作時(shí)使用線程，如C/S架構(gòu)的服務(wù)器端并發(fā)線程響應(yīng)用戶的請(qǐng)求。
3 多CPU系統(tǒng)中，使用線程提高CPU利用率
4 改善程序結(jié)構(gòu)。一個(gè)既長(zhǎng)又復(fù)雜的進(jìn)程可以考慮分為多個(gè)線程，成為幾個(gè)獨(dú)立或半獨(dú)立的運(yùn)行部分，這樣的程序會(huì)利于理解和修改。
其他情況都使用單線程。
14、內(nèi)存的分配方式有幾種?
1)從靜態(tài)存儲(chǔ)區(qū)域分配。內(nèi)存在程序編譯的時(shí)候就已經(jīng)分配好，這塊內(nèi)存在程序的整個(gè)運(yùn)行期間都存在。例如全局變量。
2)在棧上創(chuàng)建。在執(zhí)行函數(shù)時(shí)，函數(shù)內(nèi)局部變量的存儲(chǔ)單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時(shí)這些存儲(chǔ)單元自動(dòng)被釋放。棧內(nèi)存分配運(yùn)算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限。
3)從堆上分配，亦稱動(dòng)態(tài)內(nèi)存分配。程序在運(yùn)行的時(shí)候用malloc或new申請(qǐng)任意多少的內(nèi)存，程序員自己負(fù)責(zé)在何時(shí)用free或delete釋放內(nèi)存。動(dòng)態(tài)內(nèi)存的生存期由我們決定，使用非常靈活，但問題也最多。
15、設(shè)計(jì)DNS服務(wù)器中cache的數(shù)據(jù)結(jié)構(gòu)。
要求設(shè)計(jì)一個(gè)DNS的Cache結(jié)構(gòu)，要求能夠滿足每秒5000以上的查詢，滿足IP數(shù)據(jù)的快速插入，查詢的速度要快。（題目還給出了一系列的數(shù)據(jù)，比如：站點(diǎn)數(shù)總共為5000萬，IP地址有1000萬，等等）
DNS服務(wù)器實(shí)現(xiàn)域名到IP地址的轉(zhuǎn)換。
每個(gè)域名的平均長(zhǎng)度為25個(gè)字節(jié)（估計(jì)值），每個(gè)IP為4個(gè)字節(jié)，所以Cache的每個(gè)條目需要大概30個(gè)字節(jié)。
總共50M個(gè)條目，所以需要1.5G個(gè)字節(jié)的空間?？梢苑胖迷趦?nèi)存中。（考慮到每秒5000次操作的限制，也只能放在內(nèi)存中。）
可以考慮的數(shù)據(jù)結(jié)構(gòu)包括hash_map，字典樹，紅黑樹等等。
16、如何找出字典中的兄弟單詞。給定一個(gè)單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞?，F(xiàn)在給定一個(gè)字典，用戶輸入一個(gè)單詞，如何根據(jù)字典找出這個(gè)單詞有多少個(gè)兄弟單詞？
使用hash_map和鏈表。
首先定義一個(gè)key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。
使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。
開始時(shí)，先遍歷字典，將每個(gè)單詞都按照key加入到對(duì)應(yīng)的鏈表當(dāng)中。當(dāng)需要找兄弟單詞時(shí)，只需求取這個(gè)單詞的key，然后到hash_map中找到對(duì)應(yīng)的鏈表即可。
這樣創(chuàng)建hash_map時(shí)時(shí)間復(fù)雜度為O(n)，查找兄弟單詞時(shí)時(shí)間復(fù)雜度是O(1)。
17、找出第k大的數(shù)字所在的位置。寫一段程序，找出數(shù)組中第k大小的數(shù)，輸出數(shù)所在的位置。例如{2，4，3，4，7}中，第一大的數(shù)是7，位置在4。第二大、第三大的數(shù)都是4，位置在1、3隨便輸出哪一個(gè)均可。
先找到第k大的數(shù)字，然后再遍歷一遍數(shù)組找到它的位置。所以題目的難點(diǎn)在于如何最高效的找到第k大的數(shù)。
我們可以通過快速排序，堆排序等高效的排序算法對(duì)數(shù)組進(jìn)行排序，然后找到第k大的數(shù)字。這樣總體復(fù)雜度為O(NlogN)。
我們還可以通過二分的思想，找到第k大的數(shù)字，而不必對(duì)整個(gè)數(shù)組排序。從數(shù)組中隨機(jī)選一個(gè)數(shù)t，通過讓這個(gè)數(shù)和其它數(shù)比較，我們可以將整個(gè)數(shù)組分成了兩部分并且滿足，{x,xx,…,t}<{y,yy,…}。
在將數(shù)組分成兩個(gè)數(shù)組的過程中，我們還可以記錄每個(gè)子數(shù)組的大小。這樣我們就可以確定第k大的數(shù)字在哪個(gè)子數(shù)組中。
然后我們繼續(xù)對(duì)包含第k大數(shù)字的子數(shù)組進(jìn)行同樣的劃分，直到找到第k大的數(shù)字為止。
平均來說，由于每次劃分都會(huì)使子數(shù)組縮小到原來1/2，所以整個(gè)過程的復(fù)雜度為O(N)。
18、給一個(gè)奇數(shù)階N幻方,填入數(shù)字1,2,3.N^N,使得橫豎斜方向上的和都相同
#inc1ude
#include
#include
usingnamespace std;
int main()
{
int n;
cin>>n;
int i;
int **Matr = new int *[n]; //動(dòng)態(tài)分配二維數(shù)組
for(i=0;i<n;++i)
Matr[i]=new int[n]: //動(dòng)態(tài)分配二維
數(shù)組
//j=n/2代表首行中間數(shù)作為起點(diǎn),即1所在位置
int j=n/2,num=1: //初始值
i=0;
while(num!=n*n+1) {
//往右上角延升, 若超出則用%轉(zhuǎn)移到左下角
Matr [(i%n+n)%n][(j%n+n)%n]=num;
//斜行的長(zhǎng)度和n是相等的,超出則轉(zhuǎ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;
}
