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