微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題全部答案集錦

作者：July、阿財(cái)。
時(shí)間：二零一一年十月十三日。

• 引言

???? 無(wú)私分享造就開(kāi)源的輝煌。

???? 今是二零一一年十月十三日，明日14日即是本人剛好開(kāi)博一周年。在一周年之際，特此分享出微軟面試全部100題答案的完整版，以作為對(duì)本博客所有讀者的回饋。

???? 一年之前的10月14日，一個(gè)名叫July （頭像為手冢國(guó)光）的人在一個(gè)叫csdn的論壇上開(kāi)帖分享微軟等公司數(shù)據(jù)結(jié)構(gòu)+算法面試100題，自此，與上千網(wǎng)友一起做，一起思考，一起解答這些面試題目，最終成就了一個(gè)名為：結(jié)構(gòu)之法算法之道的編程面試與算法研究并重的博客，如今，此博客影響力逐步滲透到海外，及至到整個(gè)互聯(lián)網(wǎng)。

???? 在此之前，由于本人笨拙，這微軟面試100題的答案只整理到了前60題（第1-60題答案可到本人資源下載處下載：http://v_july_v.download.csdn.net/），故此，常有朋友留言或來(lái)信詢問(wèn)后面40題的答案。只是因個(gè)人認(rèn)為：一、答案只是作為一個(gè)參考，不可太過(guò)依賴；二、常常因一些事情耽擱（如在整理最新的今年九月、十月份的面試題：九月騰訊，創(chuàng)新工場(chǎng)，淘寶等公司最新面試十三題、十月百度，阿里巴巴，迅雷搜狗最新面試十一題）；三、個(gè)人正在針對(duì)那100題一題一題的寫(xiě)文章，多種思路，不斷優(yōu)化，即成程序員編程藝術(shù)系列（詳情，參見(jiàn)文末）。自此，后面40題的答案遲遲未得整理。且個(gè)人已經(jīng)整理的前60題的答案，在我看來(lái)，是有諸多問(wèn)題與弊端的，甚至很多答案都是錯(cuò)誤的。

? ? (微軟10題永久討論地址：http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9_9.html)

???? 互聯(lián)網(wǎng)總是能給人帶來(lái)驚喜。前幾日，一位現(xiàn)居美國(guó)加州的名叫阿財(cái)?shù)呐笥寻l(fā)來(lái)一封郵件，并把他自己做的全部100題的答案一并發(fā)予給我，自此，便似遇見(jiàn)了知己。十分感謝。
???? 任何東西只有分享出來(lái)才更顯其價(jià)值。本只需貼出后面40題的答案，因?yàn)榍?0題的答案本人早已整理上傳至網(wǎng)上，但多一種思路多一種參考亦未嘗不可。特此，把阿財(cái)?shù)拇鸢冈偕约诱矸?#xff0c;然后把全部100題的答案現(xiàn)今都貼出來(lái)。若有任何問(wèn)題，歡迎不吝指正。謝謝。

??? 上千上萬(wàn)的人都關(guān)注過(guò)此100題，且大都都各自貢獻(xiàn)了自己的思路，或回復(fù)于微軟100題維護(hù)地址上，或回復(fù)于本博客內(nèi)，人數(shù)眾多，無(wú)法一一標(biāo)明，特此向他們諸位表示敬意和感謝。謝謝大家，諸君的努力足以影響整個(gè)互聯(lián)網(wǎng)，咱們已經(jīng)迎來(lái)一個(gè)分享互利的新時(shí)代。

• 微軟面試100題全部答案

?? ?更新：有朋友反應(yīng)，以下的答案中思路過(guò)于簡(jiǎn)略，還是這句話，一切以程序員編程藝術(shù)系列（多種思路，多種比較，細(xì)細(xì)讀之自曉其理）為準(zhǔn)（我沒(méi)怎么看阿財(cái)?shù)倪@些答案，因?yàn)榫幊趟囆g(shù)系列已經(jīng)說(shuō)得足夠清晰了。之所以把阿財(cái)?shù)倪@份答案分享出來(lái)，一者，編程藝術(shù)系列目前還只寫(xiě)到了第二十二章，即100題之中還只詳細(xì)闡述了近30道題；二者，他給的答案全部是用英文寫(xiě)的，這恰好方便國(guó)外的一些朋友參考；三者是為了給那一些急功近利的、浮躁的人一份速成的答案罷了）。July、二零一一年十月二十四日更新。

? ? 當(dāng)然，讀者朋友有任何問(wèn)題，你也可以跟阿財(cái)聯(lián)系，他的郵箱地址是：kevinn9#gmail.com ?(把#改成@)。

1.把二元查找樹(shù)轉(zhuǎn)變成排序的雙向鏈表
題目：
輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
ANSWER:
This is a traditional problem that can be solved using recursion.
For each node, connect the double linked lists created from left and right child node to form a full list.

/**
?* @param root The root node of the tree
?* @return The head node of the converted list.
?*/
BSTreeNode * treeToLinkedList(BSTreeNode * root) {
? BSTreeNode * head, * tail;
? helper(head, tail, root);
? return head;
}

void helper(BSTreeNode *& head, BSTreeNode *& tail, BSTreeNode *root) {
? BSTreeNode *lt, *rh;
? if (root == NULL) {
??? head = NULL, tail = NULL;
??? return;
? }
? helper(head, lt, root->m_pLeft);
? helper(rh, tail, root->m_pRight);
? if (lt!=NULL) {
??? lt->m_pRight = root;
??? root->m_pLeft = lt;
? } else? {
??? head = root;
? }
? if (rh!=NULL) {
??? root->m_pRight=rh;
??? rh->m_pLeft = root;
? } else {
??? tail = root;
? }
}

2.設(shè)計(jì)包含min 函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min 函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push 以及pop 的時(shí)間復(fù)雜度都是O(1)。
ANSWER:
Stack is a LIFO data structure. When some element is popped from the stack, the status will recover to the original status as before that element was pushed. So we can recover the minimum element, too.

struct MinStackElement {
? int data;
? int min;
};

struct MinStack {
? MinStackElement * data;
? int size;
? int top;
}

MinStack MinStackInit(int maxSize) {
? MinStack stack;
? stack.size = maxSize;
? stack.data = (MinStackElement*) malloc(sizeof(MinStackElement)*maxSize);
? stack.top = 0;
? return stack;
}
void MinStackFree(MinStack stack) {
? free(stack.data);
}
void MinStackPush(MinStack stack, int d) {
? if (stack.top == stack.size) error(“out of stack space.”);
? MinStackElement* p = stack.data[stack.top];
? p->data = d;
? p->min = (stack.top==0?d : stack.data[top-1]);
? if (p->min > d) p->min = d;
? top ++;
}
int MinStackPop(MinStack stack) {
? if (stack.top == 0) error(“stack is empty!”);
? return stack.data[--stack.top].data;
}
int MinStackMin(MinStack stack) {
? if (stack.top == 0) error(“stack is empty!”);
? return stack.data[stack.top-1].min;
}

3.求子數(shù)組的最大和
題目：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
因此輸出為該子數(shù)組的和18。
ANSWER:
A traditional greedy approach.
Keep current sum, slide from left to right, when sum < 0, reset sum to 0.

int maxSubarray(int a[], int size) {
? if (size<=0) error(“error array size”);
? int sum = 0;
? int max = - (1 << 31);
? int cur = 0;
? while (cur < size) {
??? sum += a[cur++];
??? if (sum > max) {
????? max = sum;
??? } else if (sum < 0) {
????? sum = 0;
??? }
? }
? return max;
}

4.在二元樹(shù)中找出和為某一值的所有路徑
題目：輸入一個(gè)整數(shù)和一棵二元樹(shù)。
從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如輸入整數(shù)22 和如下二元樹(shù)
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12 和10, 5, 7。
二元樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
ANSWER:
Use backtracking and recurison. We need a stack to help backtracking the path.
struct TreeNode {
? int data;
? TreeNode * left;
? TreeNode * right;
};

void printPaths(TreeNode * root, int sum) {
? int path[MAX_HEIGHT];
? helper(root, sum, path, 0);
}

void helper(TreeNode * root, int sum, int path[], int top) {
? path[top++] = root.data;
? sum -= root.data;
? if (root->left == NULL && root->right==NULL) {
??? if (sum == 0) printPath(path, top);
? } else {
??? if (root->left != NULL) helper(root->left, sum, path, top);
??? if (root->right!=NULL) helper(root->right, sum, path, top);
? }
? top --;
? sum += root.data; ? ?//....
}

5.查找最小的k 個(gè)元素
題目：輸入n 個(gè)整數(shù)，輸出其中最小的k 個(gè)。
例如輸入1，2，3，4，5，6，7 和8 這8 個(gè)數(shù)字，則最小的4 個(gè)數(shù)字為1，2，3 和4。
ANSWER:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes...
Only gives the siftup and siftdown function.

/**
?*@param i the index of the element in heap a[0...n-1] to be sifted up
void siftup(int a[], int i, int n) {
? while (i>0) {
??? int j=(i&1==0 ? i-1 : i+1);
??? int p=(i-1)>>1;
??? if (j<n && a[j]<a[i]) i = j;
??? if (a[i] < a[p]) swap(a, i, p);
??? i = p;
? }?
}
void siftdown(int a[], int i, int n) {?
? while (2*i+1<n){
??? int l=2*i+1;
??? if (l+1<n && a[l+1] < a[l]) l++;
??? if (a[l] < a[i]) swap(a, i, l);
??? i=l;
? }
}

第6 題
騰訊面試題：
給你10 分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù)
要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。
上排的十個(gè)數(shù)如下：
【0，1，2，3，4，5，6，7，8，9】
舉一個(gè)例子，
數(shù)值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出現(xiàn)了6 次，1 在下排出現(xiàn)了2 次，
2 在下排出現(xiàn)了1 次，3 在下排出現(xiàn)了0 次....
以此類推..
ANSWER:
I don’t like brain teasers. Will skip most of them...

第7 題
微軟亞院之編程判斷倆個(gè)鏈表是否相交
給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。
為了簡(jiǎn)化問(wèn)題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。
問(wèn)題擴(kuò)展：
1.如果鏈表可能有環(huán)列?
2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?
ANSWER:
struct Node {
? int data;
? int Node *next;
};
// if there is no cycle.
int isJoinedSimple(Node * h1, Node * h2) {
? while (h1->next != NULL) {
??? h1 = h1->next;
? }
? while (h2->next != NULL) {
??? h2 = h2-> next;
? }
? return h1 == h2;
}

// if there could exist cycle
int isJoined(Node *h1, Node * h2) {
? Node* cylic1 = testCylic(h1);
? Node* cylic2 = testCylic(h2);
? if (cylic1+cylic2==0) return isJoinedSimple(h1, h2);
? if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0;
? Node *p = cylic1;
? while (1) {
??? if (p==cylic2 || p->next == cylic2) return 1;
??? p=p->next->next;
??? cylic1 = cylic1->next;
??? if (p==cylic1) return 0;
? }
}

Node* testCylic(Node * h1) {
? Node * p1 = h1, *p2 = h1;
? while (p2!=NULL && p2->next!=NULL) {
??? p1 = p1->next;
??? p2 = p2->next->next;
??? if (p1 == p2) {
????? return p1;
??? }
? }
? return NULL;
}

第8 題
此貼選一些比較怪的題，，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。
1.有兩個(gè)房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個(gè)開(kāi)關(guān)，
這兩個(gè)房間是分割開(kāi)的，從一間里不能看到另一間的情況。
現(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個(gè)開(kāi)關(guān)控制的。
有什么辦法呢？
ANSWER:
Skip.

2.你讓一些人為你工作了七天，你要用一根金條作為報(bào)酬。金條被分成七小塊，每天給出一
塊。
如果你只能將金條切割兩次，你怎樣分給這些工人?
ANSWER:
1+2+4;

3. ★用一種算法來(lái)顛倒一個(gè)鏈接表的順序。現(xiàn)在在不用遞歸式的情況下做一遍。
ANSWER:
Node * reverse(Node * head) {
? if (head == NULL) return head;
? if (head->next == NULL) return head;
? Node * ph = reverse(head->next);
? head->next->next = head;
? head->next = NULL;
? return ph;
}
Node * reverseNonrecurisve(Node * head) {
? if (head == NULL) return head;
? Node * p = head;
? Node * previous = NULL;
? while (p->next != NULL) {
??? p->next = previous;
??? previous = p;
??? p = p->next;
? }
? p->next = previous;
? return p;
}
★用一種算法在一個(gè)循環(huán)的鏈接表里插入一個(gè)節(jié)點(diǎn)，但不得穿越鏈接表。
ANSWER:
I don’t understand what is “Chuanyue”.
★用一種算法整理一個(gè)數(shù)組。你為什么選擇這種方法?
ANSWER:
What is “Zhengli?”
★用一種算法使通用字符串相匹配。
ANSWER:
What is “Tongyongzifuchuan”... a string with “*” and “?”? If so, here is the code.
int match(char * str, char * ptn) {
? if (*ptn == ‘\0’) return 1;
? if (*ptn == ‘*’) {
??? do {
????? if (match(str++, ptn+1)) return 1;
??? } while (*str != ‘\0’);
??? return 0;
? }
? if (*str == ‘\0’) return 0;
? if (*str == *ptn || *ptn == ‘?’) {
??? return match(str+1, ptn+1);
? }
? return 0;
}

★顛倒一個(gè)字符串。優(yōu)化速度。優(yōu)化空間。
void reverse(char *str) {
? reverseFixlen(str, strlen(str));
}
void reverseFixlen(char *str, int n) {
? char* p = str+n-1;
? while (str < p) {
??? char c = *str;
??? *str = *p; *p=c;
? }???
}
★顛倒一個(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，
實(shí)現(xiàn)速度最快，移動(dòng)最少。
ANSWER:
Reverse the whole string, then reverse each word. Using the reverseFixlen() above.
void reverseWordsInSentence(char * sen) {
? int len = strlen(sen);
? reverseFixlen(sen, len);
? char * p = str;
? while (*p!=’\0’) {
??? while (*p == ‘ ‘ && *p!=’\0’) p++;
??? str = p;
??? while (p!= ‘ ‘ && *p!=’\0’) p++;
??? reverseFixlen(str, p-str);
? }
}
★找到一個(gè)子字符串。優(yōu)化速度。優(yōu)化空間。
ANSWER:
KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access the auxiliary array. Otherwise an hashmap or bst may be needed. Lets assume it’s an ASCII string.
int bm_strstr(char *str, char *sub) {
? int len = strlen(sub);
? int i;
? int aux[256];
? memset(aux, sizeof(int), 256, len+1);
? for (i=0; i<len; i++) {
??? aux[sub[i]] = len - i;
? }
? int n = strlen(str);
? i=len-1;
? while (i<n) {
??? int j=i, k=len-1;
??? while (k>=0 && str[j--] == sub[k--])
????? ;
??? if (k<0) return j+1;
??? if (i+1<n)
????? i+=aux[str[i+1]];
??? else
????? return -1;
? }
}
However, this algorithm, as well as BM, KMP algorithms use O(|sub|) space. If this is not acceptable, Rabin-carp algorithm can do it. Using hashing to fast filter out most false matchings.
#define HBASE 127
int rc_strstr(char * str, char * sub) {
? int dest= 0;
? char * p = sub;
? int len = 0;
? int TO_REDUCE = 1;
? while (*p!=’\0’) {
??? dest = HBASE * dest + (int)(*p);
??? TO_REDUCE *= HBASE;
??? len ++;
? }
? int hash = 0;
? p = str;
? int i=0;
? while (*p != ‘\0’) {
??? if (i++<len) hash = HBASE * dest + (int)(*p);
??? else hash = (hash - (TO_REDUCE * (int)(*(p-len))))*HBASE + (int)(*p);
??? if (hash == dest && i>=len && strncmp(sub, p-len+1, len) == 0) return i-len;
??? p++;
? }
? return -1;
}
★比較兩個(gè)字符串，用O(n)時(shí)間和恒量空間。
ANSWER:
What is “comparing two strings”? Just normal string comparison? The natural way use O(n) time and O(1) space.
int strcmp(char * p1, char * p2) {
? while (*p1 != ‘\0’ && *p2 != ‘\0’ && *p1 == *p2) {
??? p1++, p2++;
? }
? if (*p1 == ‘\0’ && *p2 == ‘\0’) return 0;
? if (*p1 == ‘\0’) return -1;
? if (*p2 == ‘\0’) return 1;
? return (*p1 - *p2); // it can be negotiated whether the above 3 if’s are necessary, I don’t like to omit them.
}
★假設(shè)你有一個(gè)用1001 個(gè)整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1 到1000(包括1000)之間。此外，除一個(gè)數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對(duì)這個(gè)數(shù)組做一次處理，用一種算法找出重復(fù)的那個(gè)數(shù)字。如果你在運(yùn)算中使用了輔助的存儲(chǔ)方式，那么你能找到不用這種方式的算法嗎?
ANSWER:
Sum up all the numbers, then subtract the sum from 1001*1002/2.
Another way, use A XOR A XOR B = B:
int findX(int a[]) {
? int k = a[0];
? for (int i=1; i<=1000;i++)
??? k ~= a[i]~i;
? }
? return k;
}

★不用乘法或加法增加8 倍。現(xiàn)在用同樣的方法增加7 倍。
ANSWER:
n<<3;
(n<<3)-n;

第9 題
判斷整數(shù)序列是不是二元查找樹(shù)的后序遍歷結(jié)果
題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹(shù)的后序遍歷的結(jié)果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹(shù)的后序遍歷結(jié)果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒(méi)有哪棵樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。
ANSWER:
This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed from mid/post/pre order results. This seems similar. For the problems related to (binary) trees, recursion is the first choice.
In this problem, we know in post-order results, the last number should be the root. So we have known the root of the BST is 8 in the example. So we can split the array by the root.
int isPostorderResult(int a[], int n) {
? return helper(a, 0, n-1);
}
int helper(int a[], int s, int e) {
? if (e==s) return 1;
? int i=e-1;
? while (a[e]>a[i] && i>=s) i--;
? if (!helper(a, i+1, e-1))
??? return 0;
? int k = l;
? while (a[e]<a[i] && i>=s) i--;
? return helper(a, s, l);
}

第10 題
翻轉(zhuǎn)句子中單詞的順序。
題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。
句子中單詞以空格符隔開(kāi)。為簡(jiǎn)單起見(jiàn)，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
Answer:
Already done this. Skipped.

第11 題
求二叉樹(shù)中節(jié)點(diǎn)的最大距離...
如果我們把二叉樹(shù)看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，
我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。
寫(xiě)一個(gè)程序，
求一棵二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
ANSWER:
This is interesting... Also recursively, the longest distance between two nodes must be either from root to one leaf, or between two leafs. For the former case, it’s the tree height. For the latter case, it should be the sum of the heights of left and right subtrees of the two leaves’ most least ancestor.
The first case is also the sum the heights of subtrees, just the height + 0.

int maxDistance(Node * root) {
? int depth;
? return helper(root, depth);
}
int helper(Node * root, int &depth) {
? if (root == NULL) {
??? depth = 0; return 0;
? }
? int ld, rd;
? int maxleft = helper(root->left, ld);
? int maxright = helper(root->right, rd);
? depth = max(ld, rd)+1;
? return max(maxleft, max(maxright, ld+rd));
}

第12 題
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case 等關(guān)鍵字以及條件判斷語(yǔ)句
（A?B:C）。
ANSWER:
1+..+n=n*(n+1)/2=(n^2+n)/2
it is easy to get x/2, so the problem is to get n^2
though no if/else is allowed, we can easilly go around using short-pass.
using macro to make it fancier:

#define? T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i)

int foo(int n){
? int r=n;
? T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31);
? return r >> 1;
}

第13 題：
題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k 個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0 個(gè)結(jié)點(diǎn)為鏈表的尾指針。
鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
Answer:
Two ways. 1: record the length of the linked list, then go n-k steps. 2: use two cursors.
Time complexities are exactly the same.
Node * lastK(Node * head, int k) {
? if (k<0) error(“k < 0”);
? Node *p=head, *pk=head;
? for (;k>0;k--) {
??? if (pk->next!=NULL) pk = pk->next;
??? else return NULL;
? }
? while (pk->next!=NULL) {
??? p=p->next, pk=pk->next;
? }
? return p;
}

第14 題：
題目：輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字，
在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。
要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。
例如輸入數(shù)組1、2、4、7、11、15 和數(shù)字15。由于4+11=15，因此輸出4 和11。
ANSWER:
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.
void find2Number(int a[], int n, int dest) {
? int *f = a, *e=a+n-1;
? int sum = *f + *e;
? while (sum != dest && f < e) {
??? if (sum < dest) sum = *(++f);
??? else sum = *(--e);
? }
? if (sum == dest) printf(“%d, %d\n”, *f, *e);
}

第15 題：
題目：輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，
即在轉(zhuǎn)換后的二元查找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。
用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
定義二元查找樹(shù)的結(jié)點(diǎn)為：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
ANSWER:
This is the basic application of recursion.
PS: I don’t like the m_xx naming convension.
void swap(Node ** l, Node ** r) {
? Node * p = *l;
? *l = *r;
? *r = p;
}

void mirror(Node * root) {
? if (root == NULL) return;
? swap(&(root->left), &(root->right));
? mirror(root->left);
? mirror(root->right);
}

void mirrorIteratively(Node * root) {
? if (root == NULL) return;
? stack<Node*> buf;
? buf.push(root);
? while (!stack.empty()) {
??? Node * n = stack.pop();
??? swap(&(root->left), &(root->right));
??? if (root->left != NULL) buf.push(root->left);
??? if (root->right != NULL) buf.push(root->right);
? }
}

第16 題：
題目（微軟）：
輸入一顆二元樹(shù)，從上往下按層打印樹(shù)的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
例如輸入
8
/ \
6 10
/ \ / \
5 7 9 11
輸出8 6 10 5 7 9 11。
ANSWER:
The nodes in the levels are printed in the similar manner their parents were printed. So it should be an FIFO queue to hold the level. I really don’t remember the function name of the stl queue, so I will write it in Java...
void printByLevel(Node root) {
? Node sentinel = new Node();
? LinkedList<Node> q=new LinkedList<Node>();
? q.addFirst(root); q.addFirst(sentinel);
? while (!q.isEmpty()) {
??? Node n = q.removeLast();
??? if (n==sentinel) {
????? System.out.println(“\n”);
????? q.addFirst(sentinel);
??? } else {
????? System.out.println(n);
????? if (n.left() != null) q.addFirst(n.left());
????? if (n.right()!=null) q.addFirst(n.right());
???? }???
? }
}

第17 題：
題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。
分析：這道題是2006 年google 的一道筆試題。
ANSWER:
Again, this depends on what is “char”. Let’s assume it as ASCII.
char firstSingle(char * str) {
? int a[255];
? memset(a, 0, 255*sizeof(int));
? char *p=str;
? while (*p!=’\0’) {
??? a[*p] ++;
??? p++;
? }
? p = str;
? while (*p!=’\0’) {
??? if (a[*p] == 1) return *p;
? }
? return ‘\0’; // this must the one that occurs exact 1 time.
}

第18 題：
題目：n 個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0 開(kāi)始，
每次從這個(gè)圓圈中刪除第m 個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)
字）。
當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第m 個(gè)數(shù)字。
求出在這個(gè)圓圈中剩下的最后一個(gè)數(shù)字。
July：我想，這個(gè)題目，不少人已經(jīng)見(jiàn)識(shí)過(guò)了。
ANSWER:
Actually, although this is a so traditional problem, I was always to lazy to think about this or even to search for the answer.(What a shame...). Finally, by google I found the elegant solution for it.
The keys are:
1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n
2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th element instead of 0, so the answer is (f(n-1, m)+k+1)%n
3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n.
finally, f(1, m) = 0;
Now this is a O(n) solution.
int joseph(int n, int m) {
? int fn=0;
? for (int i=2; i<=n; i++) {
??? fn = (fn+m)%i;? }
? return fn;
}
hu...長(zhǎng)出一口氣。。。

第19 題：
題目：定義Fibonacci 數(shù)列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數(shù)列的第n 項(xiàng)。
分析：在很多C 語(yǔ)言教科書(shū)中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fibonacci 作為例子。
因此很多程序員對(duì)這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。
ANSWER:
This is the traditional problem of application of mathematics...
let A=
{1 1}
{1 0}
f(n) = A^(n-1)[0,0]
this gives a O(log n) solution.
int f(int n) {
? int A[4] = {1,1,1,0};
? int result[4];
? power(A, n, result);
? return result[0];
}

void multiply(int[] A, int[] B, int _r) {
? _r[0] = A[0]*B[0] + A[1]*B[2];
? _r[1] = A[0]*B[1] + A[1]*B[3];
? _r[2] = A[2]*B[0] + A[3]*B[2];
? _r[3] = A[2]*B[1] + A[3]*B[3];
}

void power(int[] A, int n, int _r) {
? if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }
? int tmp[4];
? power(A, n>>1, _r);
? multiply(_r, _r, tmp);
? if (n & 1 == 1) {
??? multiply(tmp, A, _r);
? } else {
??? memcpy(_r, tmp, 4*sizeof(int));
? }
}

第20 題：
題目：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。
例如輸入字符串"345"，則輸出整數(shù)345。
ANSWER:
This question checks how the interviewee is familiar with C/C++? I’m so bad at C/C++...

int atoi(char * str) {
? int neg = 0;
? char * p = str;
? if (*p == ‘-’) {
??? p++; neg = 1;
? } else if (*p == ‘+’) {
??? p++;
? }
? int num = 0;
? while (*p != ‘\0’) {
??? if (*p>='0' && *p <= '9') {
????? num = num * 10 + (*p-’0’);
??? } else {
????? error(“illegal number”);
??? }
??? p++;
? }
? return num;
}
PS: I didn’t figure out how to tell a overflow problem easily.

第21 題
2010 年中興面試題
編程求解：
輸入兩個(gè)整數(shù)n 和m，從數(shù)列1，2，3.......n 中隨意取幾個(gè)數(shù),
使其和等于m ,要求將其中所有的可能組合列出來(lái).
ANSWER
This is a combination generation problem.
void findCombination(int n, int m) {
? if (n>m) findCombination(m, m);
? int aux[n];
? memset(aux, 0, n*sizeof(int));
? helper(m, 0, aux);
}
void helper(int dest, int idx, int aux[], int n) {
? if (dest == 0)
??? dump(aux, n);
? if (dest <= 0 || idx==n) return;
? helper(dest, idx+1, aux, n);
? aux[idx] = 1;
? helper(dest-idx-1, idx+1, aux, n);
? aux[idx] = 0;
}
void dump(int aux[], int n) {
? for (int i=0; i<n; i++)
??? if (aux[i]) printf(“%3d”, i+1);
? printf(“\n”);
}
PS: this is not an elegant implementation, however, it is not necessary to use gray code or other techniques for such a problem, right?

第22 題：
有4 張紅色的牌和4 張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C 三人額頭上貼任意兩張牌，A、B、C 三人都可以看見(jiàn)其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A 說(shuō)不知道，B 說(shuō)不知道，C 說(shuō)不知道，然后A 說(shuō)知道了。
請(qǐng)教如何推理，A 是怎么知道的。如果用程序，又怎么實(shí)現(xiàn)呢？
ANSWER
I dont’ like brain teaser. As an AI problem, it seems impossible to write the solution in 20 min...

It seems that a brute-force edge cutting strategy could do. Enumerate all possibilities, then for each guy delete the permutation that could be reduced if failed (for A, B, C at 1st round), Then there should be only one or one group of choices left.

But who uses this as an interview question?

第23 題：
用最簡(jiǎn)單，最快速的方法計(jì)算出下面這個(gè)圓形是否和正方形相交。"
3D 坐標(biāo)系原點(diǎn)(0.0,0.0,0.0)
圓形:
半徑r = 3.0
圓心o = (*.*, 0.0, *.*)
正方形:
4 個(gè)角坐標(biāo);
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
ANSWER
Crap... I totally cannot understand this problem... Does the *.* represent any possible number?

第24 題：
鏈表操作，
（1）.單鏈表就地逆置，
（2）合并鏈表
ANSWER
Reversing a linked list. Already done.

What do you mean by merge? Are the original lists sorted and need to be kept sorted? If not, are there any special requirements?
I will only do the sorted merging.

Node * merge(Node * h1, Node * h2) {
? if (h1 == NULL) return h2;
? if (h2 == NULL) return h1;
? Node * head;
? if (h1->data>h2->data) {
??? head = h2; h2=h2->next;
? } else {
??? head = h1; h1=h1->next;
? }
? Node * current = head;
? while (h1 != NULL && h2 != NULL) {
??? if (h1 == NULL || (h2!=NULL && h1->data>h2->data)) {
????? current->next = h2; h2=h2->next; current = current->next;
??? } else {
????? current->next = h1; h1=h1->next; current = current->next;
??? }
? }
? current->next = NULL;
? return head;
}

第25 題：
寫(xiě)一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回，
并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr 所指內(nèi)存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr 后，函數(shù)將返回9，
outputstr 所指的值為123456789
ANSWER:

int continumax(char *outputstr, char *inputstr) {
? int len = 0;
? char * pstart = NULL;
? int max = 0;
? while (1) {
??? if (*inputstr >= ‘0’ && *inputstr <=’9’) {
????? len ++;
??? } else {
????? if (len > max) pstart = inputstr-len;
????? len = 0;
??? }
??? if (*inputstr++==’\0’) break;
? }
? for (int i=0; i<len; i++)
??? *outputstr++ = pstart++;
? *outputstr = ‘\0’;
? return max;
}
26.左旋轉(zhuǎn)字符串
題目：
定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。
如把字符串a(chǎn)bcdef 左旋轉(zhuǎn)2 位得到字符串cdefab。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。
要求時(shí)間對(duì)長(zhǎng)度為n 的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。
ANSWER
Have done it. Using reverse word function above.

27.跳臺(tái)階問(wèn)題
題目：一個(gè)臺(tái)階總共有n 級(jí)，如果一次可以跳1 級(jí)，也可以跳2 級(jí)。
求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。
這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy 等比較重視算法的公司
都曾先后選用過(guò)個(gè)這道題作為面試題或者筆試題。
ANSWER
f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2, let f(0) = 1, then f(n) = fibo(n-1);

28.整數(shù)的二進(jìn)制表示中1 的個(gè)數(shù)
題目：輸入一個(gè)整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個(gè)1。
例如輸入10，由于其二進(jìn)制表示為1010，有兩個(gè)1，因此輸出2。
分析：
這是一道很基本的考查位運(yùn)算的面試題。
包括微軟在內(nèi)的很多公司都曾采用過(guò)這道題。
ANSWER
Traditional question. Use the equation xxxxxx10000 & (xxxxxx10000-1) = xxxxxx00000
Note: for negative numbers, this also hold, even with 100000000 where the “-1” leading to an underflow.
int countOf1(int n) {
? int c=0;
? while (n!=0) {
??? n=n & (n-1);
??? c++;
? }
? return c;
}
another solution is to lookup table. O(k), k is sizeof(int);

int countOf1(int n) {
??? int c = 0;
??? if (n<0) { c++; n = n & (1<<(sizeof(int)*8-1)); }
??? while (n!=0) {
????? c+=tab[n&0xff];
????? n >>= 8;
??? }
??? return c;
}

29.棧的push、pop 序列
題目：輸入兩個(gè)整數(shù)序列。其中一個(gè)序列表示棧的push 順序，
判斷另一個(gè)序列有沒(méi)有可能是對(duì)應(yīng)的pop 順序。
為了簡(jiǎn)單起見(jiàn)，我們假設(shè)push 序列的任意兩個(gè)整數(shù)都是不相等的。
比如輸入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一個(gè)pop 系列。
因?yàn)榭梢杂腥缦碌膒ush 和pop 序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
這樣得到的pop 序列就是4、5、3、2、1。
但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。
ANSWER
This seems interesting. However, a quite straightforward and promising way is to actually build the stack and check whether the pop action can be achieved.

int isPopSeries(int push[], int pop[], int n) {
stack<int> helper;
int i1=0, i2=0;
while (i2 < n) {
while (stack.empty() || stack.peek() != pop[i2]) {
if (i1<n)?
stack.push(push[i1++]);
else
return 0;
while (!stack.empty() && stack.peek() == pop[i2]) {
stack.pop(); i2++;
}
}
}
return 1;
}

30.在從1 到n 的正數(shù)中1 出現(xiàn)的次數(shù)
題目：輸入一個(gè)整數(shù)n，求從1 到n 這n 個(gè)整數(shù)的十進(jìn)制表示中1 出現(xiàn)的次數(shù)。
例如輸入12，從1 到12 這些整數(shù)中包含1 的數(shù)字有1，10，11 和12，1 一共出現(xiàn)了5 次。
分析：這是一道廣為流傳的google 面試題。
ANSWER
This is complicated... I hate it...
Suppose we have N=ABCDEFG.
if G<1, # of 1’s in the units digits is ABCDEF, else ABCDEF+1
if F<1, # of 1’s in the digit of tens is (ABCDE)*10, else if F==1: (ABCDE)*10+G+1, else (ABCDE+1)*10
if E<1, # of 1’s in 3rd digit is (ABCD)*100, else if E==1: (ABCD)*100+FG+1, else (ABCD+1)*100
… so on.
if A=1, # of 1 in this digit is BCDEFG+1, else it’s 1*1000000;
so to fast access the digits and helper numbers, we need to build the fast access table of prefixes and suffixes.

int countOf1s(int n) {
? int prefix[10], suffix[10], digits[10]; //10 is enough for 32bit integers
? int i=0;
? int base = 1;
? while (base < n) {
?? suffix[i] = n % base;
?? digit[i] = (n % (base * 10)) - suffix[i];
?? prefix[i] = (n - suffix[i] - digit[i]*base)/10;
??? i++, base*=10;
? }
? int count = 0;
? base = 1;
? for (int j=0; j<i; j++) {
??? if (digit[j] < 1) count += prefix;
??? else if (digit[j]==1) count += prefix + suffix + 1;
??? else count += prefix+base;
??? base *= 10;
? }
? return count;
}

31.華為面試題：
一類似于蜂窩的結(jié)構(gòu)的圖，進(jìn)行搜索最短路徑（要求5 分鐘）
ANSWER
Not clear problem. Skipped. Seems a Dijkstra could do.

int dij

32.
有兩個(gè)序列a,b，大小都為n,序列元素的值任意整數(shù)，無(wú)序；
要求：通過(guò)交換a,b 中的元素，使[序列a 元素的和]與[序列b 元素的和]之間的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
ANSWER
If only one swap can be taken, it is a O(n^2) searching problem, which can be reduced to O(nlogn) by sorting the arrays and doing binary search.
If any times of swaps can be performed, this is a double combinatorial problem.
In the book <<beauty of codes>>, a similar problem splits an array to halves as even as possible. It is possible to take binary search, when SUM of the array is not too high. Else this is a quite time consuming brute force problem. I cannot figure out a reasonable solution.

33.
實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法：
給一串很長(zhǎng)字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3 這些都要找出來(lái)
其實(shí)就是類似一些和諧系統(tǒng)。。。。。
ANSWER
Not a clear problem. Seems a bitset can do.

34.
實(shí)現(xiàn)一個(gè)隊(duì)列。
隊(duì)列的應(yīng)用場(chǎng)景為：
一個(gè)生產(chǎn)者線程將int 類型的數(shù)入列，一個(gè)消費(fèi)者線程將int 類型的數(shù)出列
ANSWER
I don’t know multithread programming at all....

35.
求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫(xiě)出算法;(2)分析時(shí)間復(fù)雜度;(3)用C 寫(xiě)出關(guān)鍵代碼
ANSWER
This is the traditional problem in Programming Pearls. However, the best result is too complicated to achieve. So lets do the suboptimal one. O(n^3) solution.
1) We have know that the similar problem for 1 dim array can be done in O(n) time. However, this cannot be done in both directions in the same time. We can only calculate the accumulations for all the sublist from i to j, (0<=i<=j<n) for each array in one dimension, which takes O(n^2) time. Then in the other dimension, do the tradtional greedy search.
3) To achieve O(n^2) for accumulation for each column, accumulate 0 to i (i=0,n-1) first, then calcuate the result by acc(i, j) = acc(0, j)-acc(0,i-1)

//acc[i*n+j] => acc(i,j)
void accumulate(int a[], int n, int acc[]) {
? int i=0;
? acc[i] = a[i];
? for (i=1;i<n; i++) {
??? acc[i] = acc[i-1]+a[i];
? }
? for (i=1; i<n; i++) {
??? for (j=i; j<n; j++) {
????? acc[i*n+j] = acc[j] - acc[i-1];
??? }
? }
}

第36 題-40 題（有些題目搜集于CSDN 上的網(wǎng)友，已標(biāo)明）：
36.引用自網(wǎng)友：longzuo
谷歌筆試：
n 支隊(duì)伍比賽，分別編號(hào)為0，1，2。。。。n-1，已知它們之間的實(shí)力對(duì)比關(guān)系，
存儲(chǔ)在一個(gè)二維數(shù)組w[n][n]中，w[i][j] 的值代表編號(hào)為i，j 的隊(duì)伍中更強(qiáng)的一支。
所以w[i][j]=i 或者j，現(xiàn)在給出它們的出場(chǎng)順序，并存儲(chǔ)在數(shù)組order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是4 對(duì)3， 5 對(duì)8。.......
勝者晉級(jí)，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對(duì)5,直至出現(xiàn)第一名
編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和用于輸出比賽名次的數(shù)組result[n]，
求出result。
ANSWER
This question is like no-copying merge, or in place matrix rotation.
* No-copying merge: merge order to result, then merge the first half from order, and so on.
* in place matrix rotation: rotate 01, 23, .. , 2k/2k+1 to 02...2k, 1,3,...2k+1...
The two approaches are both complicated. However, notice one special feature that the losers’ order doesn’t matter. Thus a half-way merge is much simpler and easier:

void knockOut(int **w, int order[], int result[], int n) {
? int round = n;
? memcpy(result, order, n*sizeof(int));
? while (round>1) {
??? int i,j;
??? for (i=0,j=0; i<round; i+=2) {
????? int win= (i==round-1) ? i : w[i][i+1];
????? swap(result, j, win);
????? j++;
??? }
? }
}

37.
有n 個(gè)長(zhǎng)為m+1 的字符串，
如果某個(gè)字符串的最后m 個(gè)字符與某個(gè)字符串的前m 個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，
問(wèn)這n 個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。
ANSWER
This is identical to the problem to find the longest acylic path in a directed graph. If there is a cycle, return false.
Firstly, build the graph. Then search the graph for the longest path.

#define MAX_NUM 201
int inDegree[MAX_NUM];
int longestConcat(char ** strs, int m, int n) {
? int graph[MAX_NUM][MAX_NUM];
? int prefixHash[MAX_NUM];
? int suffixHash[MAX_NUM];?
? int i,j;
? for (i=0; i<n; i++) {
??? calcHash(strs[i], prefixHash[i], suffixHash[i]);
??? graph[i][0] = 0;
? }
? memset(inDegree, 0, sizeof(int)*n);
? for (i=0; i<n; i++) {
???? for (j=0; j<n; j++) {
?????? if (suffixHash[i]==prefixHash[j] && strncmp(strs[i]+1, strs[j], m) == 0) {
???????? if (i==j) return 0; // there is a self loop, return false.
???????? graph[i][0] ++;
???????? graph[i][graph[i*n]] = j;
???????? inDegree[j] ++;
?????? }
???? }
? }
? return longestPath(graph, n);
}

/**
?* 1. do topological sort, record index[i] in topological order.
?* 2. for all 0-in-degree vertexes, set all path length to -1, do relaxation in topological order to find single source shortest path.
?*/

int visit[MAX_NUM];
int parent[MAX_NUM];
// -1 path weight, so 0 is enough.
#define MAX_PATH 0
int d[MAX_NUM];

int longestPath(int graph[], int n) {
? memset(visit, 0, n*sizeof(int));
? if (topSort(graph) == 0) return -1; //topological sort failed, there is cycle.

? int min = 0;
?
? for (int i=0; i<n; i++) {
??? if (inDegree[i] != 0) continue;
??? memset(parent, -1, n*sizeof(int));
??? memset(d, MAX_PATH, n*sizeof(int));
??? d[i] = 0;
??? for (int j=0; j<n; j++) {
????? for (int k=1; k<=graph[top[j]][0]; k++) {
??????? if (d[top[j]] - 1 < d[graph[top[j]][k]]) { // relax with path weight -1
????????? d[graph[top[j]][k]] = d[top[j]] - 1;
????????? parent[graph[top[j]][k]] = top[j];
????????? if (d[graph[top[j]][k]] < min) min = d[graph[top[j]][k]];
??????? }?
????? }
??? }
? }
? return -min;
}

int top[MAX_NUM];
int finished[MAX_NUM];
int cnt = 0;
int topSort(int graph[]){
? memset(visit, 0, n*sizeof(int));
? memset(finished, 0, n*sizeof(int));
? for (int i=0; i<n; i++) {
??? if (topdfs(graph, i) == 0) return 0;
? }
? return 1;
}
int topdfs(int graph[], int s) {
? if (visited[s] != 0) return 1;
? for (int i=1; i<=graph[s][0]; i++) {
??? if (visited[graph[s][i]]!=0 && finished[graph[s][i]]==0) {
????? return 0; //gray node, a back edge;
??? }
??? if (visited[graph[s][i]] == 0) {
????? visited[graph[s][i]] = 1;
????? dfs(graph, graph[s][i]);
??? }??
? }
? finished[s] = 1;
? top[cnt++] = s;
? return 1;
}

Time complexity analysis:

Hash calculation: O(nm)
Graph construction: O(n*n)
Toplogical sort: as dfs, O(V+E)
All source longest path: O(kE), k is 0-in-degree vetexes number, E is edge number.
As a total, it’s a O(n*n+n*m) solution.
A very good problem. But I really doubt it as a solve-in-20-min interview question.

38.
百度面試：
1.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個(gè)較輕的，使用x 次天平，
最多可以從y 個(gè)小球中找出較輕的那個(gè)，求y 與x 的關(guān)系式。
ANSWER:
x=1, y=3: if a=b, c is the lighter, else the lighter is the lighter...
do this recursively. so y=3^x;

2.有一個(gè)很大很大的輸入流，大到?jīng)]有存儲(chǔ)器可以將其存儲(chǔ)下來(lái)，
而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m 個(gè)記錄。
ANSWER

That is, keep total number count N. If N<=m, just keep it.
For N>m, generate a random number R=rand(N) in [0, N), replace a[R] with new number if R falls in [0, m).

3.大量的URL 字符串，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度
ANSWER
1. Use hash map if there is enough memory.
2. If there is no enough memory, use hash to put urls to bins, and do it until we can fit the bin into memory.

39.
網(wǎng)易有道筆試：
(1).
求一個(gè)二叉樹(shù)中任意兩個(gè)節(jié)點(diǎn)間的最大距離，
兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，
比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)
雜度。
ANSWER
Have done this.
(2).
求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，
有向圖不再連通，描述算法。
ANSWER
Do dfs, record low[i] as the lowest vertex that can be reached from i and i’s successor nodes. For each edge i, if low[i] = i and i is not a leaf in dfs tree, then i is a cut point. The other case is the root of dfs, if root has two or more children ,it is a cut point.

/**
* g is defined as: g[i][] is the out edges, g[i][0] is the edge count, g[i][1...g[i][0]] are the other end points.
*/
int cnt = 0;
int visited[MAX_NUM];
int lowest[MAX_NUM];
void getCutPoints(int *g[], int cuts[], int n) {
? memset(cuts, 0, sizeof(int)*n);
? memset(visited, 0, sizeof(int)*n);
? memset(lowest, 0, sizeof(int)*n);
? for (int i=0; i<n; i++) {
??? if (visited[i] == 0) {
????? visited[i] = ++cnt;
????? dfs(g, cuts, n, i, i);
? }
}

int dfs(int *g[], int cuts[], int n, int s, int root) {
? int out = 0;
? int low = visit[s];
? for (int i=1; i<=g[s][0]; i++) {
??? if (visited[g[s][i]] == 0) {
????? out++;
????? visited[g[s][i]] = ++cnt;
????? int clow = dfs(g, cuts, n, g[s][i], root);
????? if (clow < low) low = clow;
??? } else {
????? if (low > visit[g[s][i]]) {
??????? low = visit[g[s][i]];
????? }
??? }
? }
? lowest[s] = low;
? if (s == root && out > 1) {
??? cuts[s] = 1;
? }
? return low;
}

40.百度研發(fā)筆試題
引用自：zp155334877
1)設(shè)計(jì)一個(gè)棧結(jié)構(gòu)，滿足一下條件：min，push，pop 操作的時(shí)間復(fù)雜度為O(1)。
ANSWER
Have done this.

2)一串首尾相連的珠子(m 個(gè))，有N 種顏色(N<=10)，
設(shè)計(jì)一個(gè)算法，取出其中一段，要求包含所有N 中顏色，并使長(zhǎng)度最短。
并分析時(shí)間復(fù)雜度與空間復(fù)雜度。
ANSWER
Use a sliding window and a counting array, plus a counter which monitors the num of zero slots in counting array. When there is still zero slot(s), advance the window head, until there is no zero slot. Then shrink the window until a slot comes zero. Then one candidate segment of (window_size + 1) is achieved. Repeat this. It is O(n) algorithm since each item is swallowed and left behind only once, and either operation is in constant time.
int shortestFullcolor(int a[], int n, int m) {
? int c[m], ctr = m;
? int h=0, t=0;
? int min=n;
? while (1) {
???? while (ctr > 0 && h<n) {
?????? if (c[a[h]] == 0) ctr --;
?????? c[a[h]] ++;
?????? h++;
???? }
???? if (h>=n) return min;
???? while (1) {
?????? c[a[t]] --;
?????? if (c[a[t]] == 0) break;
?????? t++;
???? }
???? if (min > h-t) min = h-t;
???? t++; ctr++;
? }
}

3)設(shè)計(jì)一個(gè)系統(tǒng)處理詞語(yǔ)搭配問(wèn)題，比如說(shuō)中國(guó)和人民可以搭配，
則中國(guó)人民人民中國(guó)都有效。要求：
*系統(tǒng)每秒的查詢數(shù)量可能上千次；
*詞語(yǔ)的數(shù)量級(jí)為10W；
*每個(gè)詞至多可以與1W 個(gè)詞搭配
當(dāng)用戶輸入中國(guó)人民的時(shí)候，要求返回與這個(gè)搭配詞組相關(guān)的信息。
ANSWER
This problem can be solved in three steps:
1. identify the words
2. recognize the phrase
3. retrieve the information
Solution of 1: The most trivial way to efficiently identify the words is hash table or BST. A balanced BST with 100 words is about 17 levels high. Considering that 100k is not a big number, hashing is enough.
Solution of 2: Since the phrase in this problem consists of only 2 words, it is easy to split the words. There won’t be a lot of candidates. To find a legal combination, we need the “matching” information. So for each word, we need some data structure to tell whether a word can co-occur with it. 100k is a bad number -- cannot fit into a 16bit digit. However, 10k*100k is not too big, so we can simply use array of sorted array to do this. 1G integers, or 4G bytes is not a big number, We can also use something like VInt to save a lot of space. To find an index in a 10k sorted array, 14 comparisons are enough.
Above operation can be done in any reasonable work-station's memory very fast, which should be the result of execution of about a few thousands of simple statements.
Solution of 3: The information could be to big to fit in the memory. So a B-tree may be adopted to index the contents. Caching techniques is also helpful. Considering there are at most 10^9 entries, a 3 or 4 level of B-tree is okay, so it will be at most 5 disk access. However, there are thousands of requests and we can only do hundreds of disk seeking per second. It could be necessary to dispatch the information to several workstations.

41.求固晶機(jī)的晶元查找程序
晶元盤(pán)由數(shù)目不詳?shù)拇笮∫粯拥木гM成，晶元并不一定全布滿晶元盤(pán)，
照相機(jī)每次這能匹配一個(gè)晶元，如匹配過(guò)，則拾取該晶元，
若匹配不過(guò)，照相機(jī)則按測(cè)好的晶元間距移到下一個(gè)位置。
求遍歷晶元盤(pán)的算法求思路。
ANSWER
Dont understand.

42.請(qǐng)修改append 函數(shù)，利用這個(gè)函數(shù)實(shí)現(xiàn)：
兩個(gè)非降序鏈表的并集，1->2->3 和2->3->5 并為1->2->3->5
另外只能輸出結(jié)果，不能修改兩個(gè)鏈表的數(shù)據(jù)。
ANSWER
I don’t quite understand what it means by “not modifying linked list’s data”. If some nodes will be given up, it is weird for this requirement.

Node * head(Node *h1, Node * h2) {
? if (h1==NULL) return h2;
? if (h2==NULL) return h1;
? Node * head;
? if (h1->data < h2->data) {
??? head =h1; h1=h1->next;
? } else {
??? head = h2; h2=h2->next;
? }
? Node * p = head;
? while (h1!=NULL || h2!=NULL) {
??? Node * candi;
??? if (h1!=NULL && h2 != NULL && h1->data < h2->data || h2==NULL) {
??????? candi = h1; h1=h1->next;
????? } else {
??????? candi = h2; h2=h2->next;
????? }
??? }
??? if (candi->data == p->data) delete(candi);
??? else {
?????? p->next = candi; p=candi;
??? }
? return head;
}

43.遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹(shù)的前序遍歷。
ANSWER
void preorderRecursive(TreeNode * node) {
? if (node == NULL) return;
? visit(node);
? preorderRecursive(node->left);
? preorderRecursive(node->right);
}

For non-recursive traversals, a stack must be adopted to replace the implicit program stack in recursive programs.

void preorderNonrecursive(TreeNode * node) {
? stack<TreeNode *> s;
? s.push(node);
? while (!s.empty()) {
??? TreeNode * n = s.pop();
??? visit(n);
??? if (n->right!=NULL) s.push(n->right);
??? if (n->left!=NULL) s.push(n->left);
? }
}

void inorderNonrecursive(TreeNode * node) {
? stack<TreeNode *> s;
? TreeNode * current = node;
? while (!s.empty() || current != NULL) {
??? if (current != NULL) {
????? s.push(current);
????? current = current->left;
??? } else {
????? current = s.pop();
????? visit(current);
????? current = current->right;
??? }
? }
}

Postorder nonrecursive traversal is the hardest one. However, a simple observation helps that the node first traversed is the node last visited. This recalls the feature of stack. So we could use a stack to store all the nodes then pop them out altogether.
This is a very elegant solution, while takes O(n) space.
Other very smart methods also work, but this is the one I like the most.

void postorderNonrecursive(TreeNode * node) {
? // visiting occurs only when current has no right child or last visited is his right child
? stack<TreeNode *> sTraverse, sVisit;
? sTraverse.push(node);
? while (!sTraverse.empty()) {
??? TreeNode * p = sTraverse.pop();
??? sVisit.push(p);
??? if (p->left != NULL) sTraverse.push(p->left);
??? if (p->right != NULL) sTraverse.push(p->right);
? }
? while (!sVisit.empty()) {
??? visit(sVisit.pop);
? }
}

44.騰訊面試題：
1.設(shè)計(jì)一個(gè)魔方（六面）的程序。
ANSWER
This is a problem to test OOP.
The object MagicCube must have following features
1) holds current status
2) easily doing transform
3) judge whether the final status is achieved
4) to test, it can be initialized
5) output current status

public class MagicCube {
? // 6 faces, 9 chips each face
? private byte chips[54];
? static final int X = 0;
? static final int Y = 1;
? static final int Z = 1;
? void transform(int direction, int level) {
??? switch direction: {
????? X : { transformX(level); break; }
????? Y : { transformY(level); break; }
????? Z : { transformZ(level); break; }
????? default: throw new RuntimeException(“what direction?”);
??? }
??? void transformX(int level) { … }
??? }
? }
? // really tired of making this...
}

2.有一千萬(wàn)條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。
請(qǐng)用5 分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前10 條。
ANSWER
10M msgs, each at most 140 chars, that’s 1.4G, which can fit to memory.
So use hash map to accumulate occurrence counts.
Then use a heap to pick maximum 10.

3.收藏了1 萬(wàn)條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似）
ANSWER
What a SB interviewer... The company name should be claimed and if I met such a interviewer, I will contest to HR. The purpose of interview is to see the ability of communication. This is kind of single side shutdown of information exchange.
My first answer will be doing edit distance to the url and every candidate. Then it depends on what interviewer will react. Other options includes: fingerprints, tries...

45.雅虎：
1.對(duì)于一個(gè)整數(shù)矩陣，存在一種運(yùn)算，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）
某一個(gè)元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個(gè)全零矩陣經(jīng)過(guò)上述運(yùn)算得到。
ANSWER
A assignment problem. Two ways to solve. 1: duplicate each cell to as many as its value, do Hungarian algorithm. Denote the sum of the matrix as M, the edge number is 2M, so the complexity is 2*M*M; 2: standard maximum flow. If the size of matrix is NxN, then the algorithm using Ford Fulkerson algorithm is M*N*N.
too complex... I will do this when I have time...

2.一個(gè)整數(shù)數(shù)組，長(zhǎng)度為n，將其分為m 份，使各份的和相等，求m 的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m 的最大值為3
ANSWER
Two restrictions on m, 1) 1 <= m <= n; 2) Sum(array) mod m = 0
NOTE: no hint that a[i]>0, so m could be larger than sum/max;
So firstly prepare the candidates, then do a brute force search on possible m’s.
In the search , a DP is available, since if f(array, m) = OR_i( f(array-subset(i), m) ), where Sum(subset(i)) = m.

int maxShares(int a[], int n) {
? int sum = 0;
? int i, m;
? for (i=0; i<n; i++) sum += a[i];
? for (m=n; m>=2; m--) {
??? if (sum mod m != 0) continue;
??? int aux[n]; for (i=0; i<n; i++) aux[i] = 0;
??? if (testShares(a, n, m, sum, sum/m, aux, sum/m, 1)) return m;
? }
? return 1;
}

int testShares(int a[], int n, int m, int sum, int groupsum, int[] aux, int goal, int groupId) {
? if (goal == 0) {
??? groupId++;
??? if (groupId == m+1) return 1;
? }
? for (int i=0; i<n; i++) {
??? if (aux[i] != 0) continue;
??? aux[i] = groupId;
??? if (testShares(a, n, m, sum, groupsum, aux, goal-a[i], groupId)) {
????? return 1;
??? }
??? aux[i] = 0;
? }
}

Please do edge cutting yourself, I’m quite enough of this...

46.搜狐：
四對(duì)括號(hào)可以有多少種匹配排列方式？比如兩對(duì)括號(hào)可以有兩種：（）（）和（（））
ANSWER:
Suppose k parenthesis has f(k) permutations, k is large enough. Check the first parenthesis, if there are i parenthesis in it then, the number of permutations inside it and out of it are f(i) and f(k-i-1), respectively. That is
f(k) = Sum_i=[0,k-1]_(f(i)*f(k-i-1));
which leads to the k’th Catalan number.

?

47.創(chuàng)新工場(chǎng)：
求一個(gè)數(shù)組的最長(zhǎng)遞減子序列比如{9，4，3，2，5，4，3，2}的最長(zhǎng)遞減子序列為{9，5，
4，3，2}
ANSWER:
Scan from left to right, maintain a decreasing sequence. For each number, binary search in the decreasing sequence to see whether it can be substituted.

int[] findDecreasing(int[] a) {
? int[] ds = new int[a.length];
? Arrays.fill(ds, 0);
? int dsl = 0;
? int lastdsl = 0;
? for (int i=0; i<a.length; i++) {
??? // binary search in ds to find the first element ds[j] smaller than a[i]. set ds[j] = a[i], or append a[i] at the end of ds
??? int s=0, t=dsl-1;
??? while (s<=t) {
????? int m = s+(t-s)/2;
????? if (ds[m] < a[i]) {
??????? t = m - 1;
????? } else {
??????? s = m + 1;
????? }
??? }
??? // now s must be at the first ds[j]<a[i], or at the end of ds[]
??? ds[s] = a[i];
??? if (s > dsl) { dsl = s; lastdsl = i; }
? }
? // now trace back.
? for (int i=lastdsl-1, j=dsl-1; i>=0 && j >= 0; i--) {
??? if (a[i] == ds[j]) { j --; }
??? else if (a[i] < ds[j]) { ds[j--] = a[i]; }
? }?
? return Arrays.copyOfRange(ds, 0, dsl+1);
}

48.微軟：
一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。
ANSWER:
The key is that, from the middle point of the array, half of the array is sorted, and the other half is a half-size shifted sorted array. So this can also be done recursively like a binary search.

int shiftedBinarySearch(int a[], int k) {
? return helper(a, k, 0, n-1);
}

int helper(int a[], int k, int s, int t) {
? if (s>t) return -1;
? int m = s + (t-s)/2;
? if (a[m] == k) return m;
? else if (a[s] >= k && k > a[m]) return helper(a, k, s, m-1);
? else return helper(a, k, m+1, e);
}

49.一道看上去很?chē)樔说乃惴嬖囶}：
如何對(duì)n 個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
ANSWER:
So a comparison sort is not allowed. Counting sort’s space complexity is O(n).
More ideas must be exchanged to find more conditions, else this is a crap.

50.網(wǎng)易有道筆試：
1.求一個(gè)二叉樹(shù)中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是這兩個(gè)節(jié)點(diǎn)間邊
的個(gè)數(shù)，
比如某個(gè)孩子節(jié)點(diǎn)和父節(jié)點(diǎn)間的距離是1，和相鄰兄弟節(jié)點(diǎn)間的距離是2，優(yōu)化時(shí)間空間復(fù)
雜度。
ANSWER:
Have done this before.

2.求一個(gè)有向連通圖的割點(diǎn)，割點(diǎn)的定義是，
如果除去此節(jié)點(diǎn)和與其相關(guān)的邊，有向圖不再連通，描述算法。
ANSWER:
Have done this before.
-------------------------------------------------------------------
51.和為n 連續(xù)正數(shù)序列。
題目：輸入一個(gè)正數(shù)n，輸出所有和為n 連續(xù)正數(shù)序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個(gè)連續(xù)序列1-5、4-6 和7-8。
分析：這是網(wǎng)易的一道面試題。
ANSWER:
It seems that this can be solved by factorization. However, factorization of large n is impractical!

Suppose n=i+(i+1)+...+(j-1)+j, then n = (i+j)(j-i+1)/2 = (j*j - i*i + i + j)/2
=> j^2 + j + (i-i^2-2n) = 0 => j=sqrt(i^2-i+1/4+2n) - 1/2
We know? 1 <= i < j <= n/2 + 1
So for each i in [1, n/2], do this arithmetic to check if there is a integer answer.

int findConsecutiveSequence(int n) {
? int count = 0;
? for (int i=1; i<=n/2; i++) {
??? int sqroot = calcSqrt(4*i*i+8*n-4*i+1);
??? if (sqroot == -1) continue;
??? if ((sqroot & 1) == 1) {
????? System.out.println(i+”-” + ((sqroot-1)/2));
????? count ++;
??? }
? }
? return count;
}
Use binary search to calculate sqrt, or just use math functions.

52.二元樹(shù)的深度。
題目：輸入一棵二元樹(shù)的根結(jié)點(diǎn)，求該樹(shù)的深度。
從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為
樹(shù)的深度。

例如：輸入二元樹(shù)：
10
/ \
6 14
/ / \
4 12 16
輸出該樹(shù)的深度3。
二元樹(shù)的結(jié)點(diǎn)定義如下：
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode *m_pLeft; // left child of node
SBinaryTreeNode *m_pRight; // right child of node
};
分析：這道題本質(zhì)上還是考查二元樹(shù)的遍歷。

ANSWER:
Have done this.

53.字符串的排列。
題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。
例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c 所能排列出來(lái)的所有字符串
abc、acb、bac、bca、cab 和cba。
分析：這是一道很好的考查對(duì)遞歸理解的編程題，
因此在過(guò)去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。
ANSWER:
Full permutation generation. I will use another technique that swap two neighboring characters each time. It seems that all the characters are different. I need to think about how to do it when duplications is allowed. Maybe simple recursion is better for that.

void generatePermutation(char s[], int n) {
? if (n>20) { error(“are you crazy?”); }
? byte d[n];
? int pos[n], dpos[n];? // pos[i], the position of i’th number, dpos[i] the number in s[i] is the dpos[i]’th smallest
? qsort(s);? // I cannot remember the form of qsort in C...
? memset(d, -1, sizeof(byte)*n);?
? for (int i=0; i<n; i++) pos[i]=i, dpos[i]=i;

? int r;
? while (r = findFirstAvailable(s, d, pos, n)) {
??? if (r== -1) return;
??? swap(s, pos, dpos, d, r, r+d[r]);
??? for (int i=n-1; i>dpos[r]; i--)
????? d[i] = -d[i];
? }
}
int findFirstAvailable(char s[], byte d[], int pos[], int n) {
? for (int i=n-1; i>1; i--) {
??? if (s[pos[i]] > s[pos[i]+d[pos[i]]]) return pos[i];
? }?
? return -1;
}

#define aswap(ARR, X, Y) {int t=ARR[X]; ARR[X]=ARR[y]; ARR[Y]=t;}
void swap(char s[], int pos[], int dpos[], byte d[], int r, int s) {
? aswap(s, r, s);
? aswap(d, r, s);
? aswap(pos, dpos[r], dpos[s]);
? aswap(dpos, r, s);
}

Maybe full of bugs. Please refer to algorithm manual for explansion.
Pros: Amotized O(1) time for each move. Only two characters change position for each move.
Cons: as you can see, very complicated. Extra space needed.

54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面。
題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分，
所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為O(n)。
ANSWER:
This problem makes me recall the process of partition in quick sort.

void partition(int a[], int n) {
? int i=j=0;
? while (i < n && (a[i] & 1)==0) i++;
? if (i==n) return;
? swap(a, i++, j++);
? while (i<n) {
??? if ((a[i] & 1) == 1) {
????? swap(a, i, j++);
??? }
??? i++;
? }
}

55. 題目：類CMyString 的聲明如下：
class CMyString
{
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
CMyString& operator = (const CMyString& str);
private:
char* m_pData;
};
請(qǐng)實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)，要求異常安全，即當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行賦值時(shí)發(fā)生異常，對(duì)
象的狀態(tài)不能改變。
ANSWER
Pass...

56.最長(zhǎng)公共字串。
題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，
則字符串一稱之為字符串二的子串。
注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。
請(qǐng)編寫(xiě)一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。
例如：輸入兩個(gè)字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。
分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃
題，因此一些重視算法的公司像MicroStrategy 都把它當(dāng)作面試題。
ANSWER:
Standard DP...
lcs(ap1, bp2) = max{ lcs(p1,p2)+1, lcs(p1, bp2), lcs(ap1, p2)}

int LCS(char *p1, char *p2) {
? int l1= strlen(p1)+1, l2=strlen(p2)+1;
? int a[l1*l2];
? for (int i=0; i<l1; i++) a[i*l2] = 0;
? for (int i=0; i<l2; i++) a[i] = 0;
? for (int i=1; i<l1; i++) {
??? for (int j=1; j<l2; j++) {
????? int max = MAX(a[(i-1)*l2+l1], a[i*l2+l1-1]);
????? if (p1[i-1] == p2[j-1]) {
??????? max = (max > 1 + a[(i-1)*l2+j-1]) ? max : 1+a[(i-1)*l2+j-1];
????? }
??? }
? }
? return a[l1*l2-1];
}

57.用倆個(gè)棧實(shí)現(xiàn)隊(duì)列。
題目：某隊(duì)列的聲明如下：
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
Stack<T> m_stack1;
Stack<T> m_stack2;
};
分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。
因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列。
相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，
因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器，
我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。
ANSWER
Traditional problem in CLRS.
void appendTail(const T& node) {
? m_stack1.push(node);
}
T getHead() {
? if (!m_stack2.isEmpty()) {
??? return m_stack2.pop();
? }
? if (m_stack1.isEmpty()) error(“delete from empty queue”);
? while (!m_stack1.isEmpty()) {
??? m_stack2.push(m_stack1.pop());
? }
? return m_stack2.pop();
}

58.從尾到頭輸出鏈表。
題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。
該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。
ANSWER
Have answered this...

59.不能被繼承的類。
題目：用C++設(shè)計(jì)一個(gè)不能被繼承的類。
分析：這是Adobe 公司2007 年校園招聘的最新筆試題。
這道題除了考察應(yīng)聘者的C++基本功底外，還能考察反應(yīng)能力，是一道很好的題目。
ANSWER:
I don’t know c++.
Maybe it can be done by implement an empty private default constructor.

60.在O（1）時(shí)間內(nèi)刪除鏈表結(jié)點(diǎn)。
題目：給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。鏈表結(jié)點(diǎn)的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：這是一道廣為流傳的Google 面試題，能有效考察我們的編程基本功，還能考察我們
的反應(yīng)速度，
更重要的是，還能考察我們對(duì)時(shí)間復(fù)雜度的理解。
ANSWER:
Copy the data from tobedeleted’s next to tobedeleted. then delete tobedeleted. The special case is tobedelete is the tail, then we must iterate to find its predecessor.
The amortized time complexity is O(1).

-------------------------------------------------------------------------
61.找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字
題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。
請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
分析：這是一道很新穎的關(guān)于位運(yùn)算的面試題。
ANSWER:
XOR.

62.找出鏈表的第一個(gè)公共結(jié)點(diǎn)。
題目：兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
鏈表的結(jié)點(diǎn)定義為：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，
因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。
ANSWER:
Have done this.

63.在字符串中刪除特定的字符。
題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入”They are students.”和”aeiou”， 則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。
分析：這是一道微軟面試題。在微軟的常見(jiàn)面試題中，與字符串相關(guān)的題目占了很大的一部
分，因?yàn)閷?xiě)程序操作字符串能很好的反映我們的編程基本功。
ANSWER:
Have done this? Use a byte array / character hash to record second string. then use two pointers to shrink the 1st string.

64. 尋找丑數(shù)。
題目：我們把只包含因子2、3 和5 的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8 都是丑數(shù)，
但14 不是，因?yàn)樗蜃?。習(xí)慣上我們把1 當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第1500 個(gè)丑數(shù)。
分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說(shuō)google 曾經(jīng)采用過(guò)這道題。
ANSWER:
TRADITIONAL.

Use heap/priority queue.
int no1500() {
? int heap[4500];
? heap[0] = 2; heap[1] = 3; heap[2] = 5;
? int size = 3;
? for (int i=1; i<1500; i++) {
??? int s = heap[0];
??? heap[0] = s*2; siftDown(heap, 0, size);
??? heap[size] = s*3; siftUp(heap, size, size+1);
??? heap[size+1] = s*5; siftUp(heap, size+1, size+2);
??? size+=2;
? }
}

void siftDown(int heap[], int from, int size) {
? int c = from * 2 + 1;
? while (c < size) {
??? if (c+1<size && heap[c+1] < heap[c]) c++;
??? if (heap[c] < heap[from]) swap(heap, c, from);
??? from = c; c=from*2+1;
? }
}
void siftUp(int heap[], int from, int size) {
? while (from > 0) {
??? int p = (from - 1)? / 2;
??? if (heap[p] > heap[from]) swap(heap, p, from);
??? from = p;
? }
}

65.輸出1 到最大的N 位數(shù)
題目：輸入數(shù)字n，按順序輸出從1 最大的n 位10 進(jìn)制數(shù)。比如輸入3，則輸出1、2、3 一直到最大的3 位數(shù)即999。
分析：這是一道很有意思的題目。看起來(lái)很簡(jiǎn)單，其實(shí)里面卻有不少的玄機(jī)。
ANSWER:
So maybe n could exceed i32? I cannot tell where is the trick...
Who will output 2*10^9 numbers...

66.顛倒棧。
題目：用遞歸顛倒一個(gè)棧。例如輸入棧{1, 2, 3, 4, 5}，1 在棧頂。
顛倒之后的棧為{5, 4, 3, 2, 1}，5 處在棧頂。
ANSWER:
Interesting...

void reverse(Stack stack) {
? if (stack.size() == 1) return;
? Object o = stack.pop();
? reverse(stack);
? putToBottom(stack, o);
}

void putToBottom(Stack stack, Object o) {
? if (stack.isEmpty()) {
??? stack.push(o);
??? return;
? }
? Object o2 = stack.pop();
? putToBottom(stack, o);
? stack.push(o2);
}

67.倆個(gè)閑玩娛樂(lè)。
1.撲克牌的順子
從撲克牌中隨機(jī)抽5 張牌，判斷是不是一個(gè)順子，即這5 張牌是不是連續(xù)的。2-10 為數(shù)字本身，A 為1，J 為11，Q 為12，K 為13，而大小王可以看成任意數(shù)字。
ANSWER:
// make king = 0
boolean isStraight(int a[]) {
? Arrays.sort(a);
? if (a[0] > 0) return checkGaps(a, 0, 4, 0);
? if (a[0] == 0 && a[1] != 0) return checkGaps(a, 1, 4, 1);
? return checkGaps(a, 2, 4, 2);
}

boolean checkGaps(int []a, int s, int e, int allowGaps) {
? int i=s;
? while (i<e) {
??? allowGaps -= a[i+1] - a[i] - 1;
??? if (allowGaps < 0) return false;
??? i++;
? }
? return true;
}

2.n 個(gè)骰子的點(diǎn)數(shù)。把n 個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n，
打印出S 的所有可能的值出現(xiàn)的概率。
ANSWER:
All the possible values includes n to 6n. All the event number is 6^n.
For n<=S<=6n, the number of events is f(S, n)
f(S,n) = f(S-6, n-1) + f(S-5, n-1) + … + f(S-1, n-1)
number of events that all dices are 1s is only 1, and thus f(k, k) = 1, f(1-6, 1) = 1, f(x, 1)=0 where x<1 or x>6, f(m, n)=0 where m<n
Can do it in DP.

void listAllProbabilities(int n) {
? int[][] f = new int[6*n+1][];
? for (int i=0; i<=6*n; i++) {
??? f[i] = new int[n+1];
? }
? for (int i=1; i<=6; i++) {
??? f[i][1] = 1;
? }
? for (int i=1; i<=n; i++) {
??? f[i][i] = 1;
? }
? for (int i=2; i<=n; i++) {
??? for (int j=i+1; j<=6*i; j++) {
????? for (int k=(j-6<i-1)?i-1:j-6; k<j-1; k++)
??????? f[j][i] += f[k][i-1];
??? }
? }
? double p6 = Math.power(6, n);
? for (int i=n; i<=6*n; i++) {
??? System.out.println(“P(S=”+i+”)=”+((double)f[i][n] / p6));
? }
}

?

68.把數(shù)組排成最小的數(shù)。
題目：輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來(lái)排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的
一個(gè)。
例如輸入數(shù)組{32, 321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。
請(qǐng)給出解決問(wèn)題的算法，并證明該算法。
分析：這是09 年6 月份百度的一道面試題，
從這道題我們可以看出百度對(duì)應(yīng)聘者在算法方面有很高的要求。
ANSWER:
Actually this problem has little to do with algorithm...
The concern is, you must figure out how to arrange to achieve a smaller figure.
The answer is, if ab < ba, then a < b, and this is a total order.

String smallestDigit(int a[]) {
? Integer aux[] = new Integer[a.length];
? for (int i=0; i<a.length; a++) aux[i] = a[i];
? Arrays.sort(aux, new Comparator<Integer>(){
??? int compareTo(Integer i1, Integer i2) {
????? return (“”+i1+i2).compare(“”+i2+i1);
??? }
? });
? StringBuffer sb = new StringBuffer();
? for (int i=0; i<aux.length, i++) {
??? sb.append(aux[i]);
? }
? return sb.toString();
}

69.旋轉(zhuǎn)數(shù)組中的最小元素。
題目：把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)
排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，
輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個(gè)旋轉(zhuǎn)，該數(shù)
組的最小值為1。
分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時(shí)間復(fù)雜度顯然是O(N)。但這個(gè)思路沒(méi)有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。
ANSWER
This is like the shifted array binary search problem. One blind point is that you may miss the part that the array is shifted by 0(or kN), that is not shifted.

int shiftedMinimum(int a[], int n) {
? return helper(a, 0, n-1);
}

int helper(int a[], int s, int t) {
? if (s == t || a[s] < a[t]) return a[s];
? int m = s + (t-s)/2;
? if (a[s]>a[m]) return helper(a, s, m);
? else return helper(a, m+1, t);
}

70.給出一個(gè)函數(shù)來(lái)輸出一個(gè)字符串的所有排列。
ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)，
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth 的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，也需要一定的靈感，有興趣最好看看。
ANSWER:
Have done this.

71.數(shù)值的整數(shù)次方。
題目：實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)，求base 的exponent 次方。
不需要考慮溢出。
分析：這是一道看起來(lái)很簡(jiǎn)單的問(wèn)題。可能有不少的人在看到題目后30 秒寫(xiě)出如下的代碼：
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
ANSWER

…

double power(double base, int exp) {
? if (exp == 1) return base;
? double half = power(base, exp >> 1);
? return (((exp & 1) == 1) ? base : 1.0) * half * half;
}

72. 題目：設(shè)計(jì)一個(gè)類，我們只能生成該類的一個(gè)實(shí)例。
分析：只能生成一個(gè)實(shí)例的類是實(shí)現(xiàn)了Singleton 模式的類型。
ANSWER
I’m not good at multithread programming... But if we set a lazy initialization, the “if” condition could be interrupted thus multiple constructor could be called, so we must add synchronized to the if judgements, which is a loss of efficiency. Putting it to the static initialization will guarantee that the constructor only be executed once by the java class loader.
public class Singleton {
? private static Singleton instance = new Singleton();
? private synchronized Singleton() {
? }
? public Singleton getInstance() {
??? return instance();
? }
}
This may not be correct. I’m quite bad at this...

73.對(duì)策字符串的最大長(zhǎng)度。
題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫(xiě)過(guò)判斷一個(gè)字符串是不是對(duì)稱的函數(shù)，這個(gè)題目可以看成是該函數(shù)的
加強(qiáng)版。
ANSWER
Build a suffix tree of x and inverse(x), the longest anagram is naturally found.
Suffix tree can be built in O(n) time so this is a linear time solution.

74.數(shù)組中超過(guò)出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半，找出這個(gè)數(shù)字。
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google 在內(nèi)的多家公司都
曾經(jīng)采用過(guò)這個(gè)題目。要幾十分鐘的時(shí)間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應(yīng)和較強(qiáng)的邏輯思維能力。
ANSWER
Delete every two different digits. The last one that left is the one.
int getMajor(int a[], int n) {
? int x, cnt=0;
? for (int i=0; i<n; i++) {
??? if (cnt == 0) {
????? x = a[i]; cnt++;
??? } else if (a[i]==x) {
????? cnt ++;
??? } else {
????? cnt --;
??? }????
? }
? return x;
}

75.二叉樹(shù)兩個(gè)結(jié)點(diǎn)的最低共同父結(jié)點(diǎn)
題目：二叉樹(shù)的結(jié)點(diǎn)定義如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入二叉樹(shù)中的兩個(gè)結(jié)點(diǎn)，輸出這兩個(gè)結(jié)點(diǎn)在數(shù)中最低的共同父結(jié)點(diǎn)。
分析：求數(shù)中兩個(gè)結(jié)點(diǎn)的最低共同結(jié)點(diǎn)是面試中經(jīng)常出現(xiàn)的一個(gè)問(wèn)題。這個(gè)問(wèn)題至少有兩個(gè)
變種。
ANSWER
Have done this. Do it again for memory...
TreeNode* getLCA(TreeNode* root, TreeNode* X, TreeNode *Y) {
? if (root == NULL) return NULL;
? if (X == root || Y == root) return root;
? TreeNode * left = getLCA(root->m_pLeft, X, Y);
? TreeNode * right = getLCA(root->m_pRight, X, Y);
? if (left == NULL) return right;
? else if (right == NULL) return left;
? else return root;
}

76.復(fù)雜鏈表的復(fù)制
題目：有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext 指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibling 指向鏈表中的任一結(jié)點(diǎn)或者NULL。其結(jié)點(diǎn)的C++定義如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下圖是一個(gè)含有5 個(gè)結(jié)點(diǎn)的該類型復(fù)雜鏈表。

圖中實(shí)線箭頭表示m_pNext 指針，虛線箭頭表示m_pSibling 指針。為簡(jiǎn)單起見(jiàn)，指向NULL 的指針沒(méi)有畫(huà)出。請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。
分析：在常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)上稍加變化，這是一種很新穎的面試題。
要在不到一個(gè)小時(shí)的時(shí)間里解決這種類型的題目，我們需要較快的反應(yīng)能力，
對(duì)數(shù)據(jù)結(jié)構(gòu)透徹的理解以及扎實(shí)的編程功底。
ANSWER
Have heard this before, never seriously thought it.

The trick is like this: take use of the old pSibling, make it points to the new created cloned node, while make the new cloned node’s pNext backup the old pSibling.

ComplexNode * Clone(ComplexNode* pHead) {
? if (pHead == NULL) return NULL;
? preClone(pHead);
? inClone(pHead);
? return postClone(pHead);
}

void preClone(ComplexNode* pHead) {
? ComplexNode * p = new ComplexNode();
? p->m_pNext = pHead->m_pSibling;
? pHead->m_pSibling = p;
? if (pHead->m_pNext != NULL) preClone(pHead->m_pNext);
}

void inClone(ComplexNode * pHead) {
? ComplexNode * pSib = pNew->m_pNext;
? if (pSib == NULL) { pNew->m_pSibling = NULL; }
? else { pNew->m_pSibling = pSib->m_pSibling; }
? if (pHead->m_pNext != NULL) inClone(pHead->m_pNext);
}

ComplexNode * postClone(ComplexNode * pHead) {
? ComplexNode * pNew = pHead->m_pSibling;
? ComplexNode * pSib = pNew->m_pNext;
? if (pHead->m_pNext != NULL) {
??? pNew->m_pNext = pHead->m_pNext->m_pSibling;
??? pHead->m_pSibling = pSib;
??? postClone(pHead->m_pNext);
? } else {
??? pNew->pNext = NULL;
??? pHead->m_pSibling = NULL;
? }
? return pNew;
}

?

77.關(guān)于鏈表問(wèn)題的面試題目如下：
1.給定單鏈表，檢測(cè)是否有環(huán)。
使用兩個(gè)指針p1,p2 從鏈表頭開(kāi)始遍歷，p1 每次前進(jìn)一步，p2 每次前進(jìn)兩步。如果p2 到
達(dá)鏈表尾部，說(shuō)明無(wú)環(huán)，否則p1、p2 必然會(huì)在某個(gè)時(shí)刻相遇(p1==p2)，從而檢測(cè)到鏈表中有環(huán)。
2.給定兩個(gè)單鏈表(head1, head2)，檢測(cè)兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)。如果head1==head2，那么顯然相交，直接返回head1。否則，分別從head1,head2 開(kāi)始遍歷兩個(gè)鏈表獲得其長(zhǎng)度len1 與len2，假設(shè)len1>=len2，那么指針p1 由head1 開(kāi)始向后移動(dòng)len1-len2 步，指針p2=head2，下面p1、p2 每次向后前進(jìn)一步并比較p1p2 是否相等，如果相等即返回該結(jié)點(diǎn)，否則說(shuō)明兩個(gè)鏈表沒(méi)有交點(diǎn)。
3.給定單鏈表(head)，如果有環(huán)的話請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。
運(yùn)用題一，我們可以檢查鏈表中是否有環(huán)。如果有環(huán)，那么p1p2 重合點(diǎn)p 必然在環(huán)中。從p 點(diǎn)斷開(kāi)環(huán)，方法為：p1=p, p2=p->next, p->next=NULL。此時(shí)，原單鏈表可以看作兩條單鏈表，一條從head 開(kāi)始，另一條從p2 開(kāi)始，于是運(yùn)用題二的方法，我們找到它們的第一個(gè)交點(diǎn)即為所求。
4.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p->next!=NULL)指針，刪除該結(jié)點(diǎn)。辦法很簡(jiǎn)單，首先是放p 中數(shù)據(jù),然后將p->next 的數(shù)據(jù)copy 入p 中，接下來(lái)刪除p->next即可。
5.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p 前面插入一個(gè)結(jié)點(diǎn)。辦法與前者類似，首先分配一個(gè)結(jié)點(diǎn)q，將q 插入在p 后，接下來(lái)將p 中的數(shù)據(jù)copy 入q中，然后再將要插入的數(shù)據(jù)記錄在p 中。

78.鏈表和數(shù)組的區(qū)別在哪里？
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生，誰(shuí)比較仔細(xì)，誰(shuí)獲勝的機(jī)會(huì)就大。
ANSWER
1. Besides the common staff, linked list is more abstract and array is usually a basic real world object. When mentioning “l(fā)inked list”, it doesn’t matter how it is implemented, that is, as long as it supports “get data” and “get next”, it is a linked list. But almost all programming languages provides array as a basic data structure.
2. So array is more basic. You can implement a linked list in an array, but cannot in the other direction.

79.
1.編寫(xiě)實(shí)現(xiàn)鏈表排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法？
ANSWER
For linked list sorting, usually mergesort is the best choice. Pros: O(1) auxilary space, compared to array merge sort. No node creation, just pointer operations.
Node * linkedListMergeSort(Node * pHead) {
? int len = getLen(pHead);
? return mergeSort(pHead, len);
}

Node * mergeSort(Node * p, int len) {
? if (len == 1) { p->next = NULL; return p; }
? Node * pmid = p;
? for (int i=0; i<len/2; i++) {
??? pmid = pmid->next;
? }
? Node * p1 = mergeSort(p, len/2);
? Node * p2 = mergeSort(pmid, len - len/2);
? return merge(p1, p2);
}
Node * merge(Node * p1, Node * p2) {
? Node * p = NULL, * ph = NULL;
? while (p1!=NULL && p2!=NULL) {
??? if (p1->data<p2->data) {
????? if (ph == NULL) {ph = p = p1;}
????? else { p->next = p1; p1 = p1->next; p = p->next;}
??? } else {
????? if (ph == NULL) {ph = p = p2;}
????? else { p->next = p2; p2 = p2->next; p = p->next;}
??? }
? }
? p->next = (p1==NULL) ? p2 : p1;
? return ph;
}

?

2.編寫(xiě)實(shí)現(xiàn)數(shù)組排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法？
ANSWER
Actually, it depends on the data. If arbitrary data is given in the array, I would choose quick sort. It is asy to implement, fast.

3.請(qǐng)編寫(xiě)能直接實(shí)現(xiàn)strstr()函數(shù)功能的代碼。
ANSWER
Substring test? Have done this.

80.阿里巴巴一道筆試題
問(wèn)題描述:
12 個(gè)高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對(duì)應(yīng)的第一排的人
高,問(wèn)排列方式有多少種?
這個(gè)筆試題,很YD,因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深。
ANSWER
Must be
1 a b … …
c d e … …
c could be 2th to 7th ( has to be smaller than d, e... those 5 numbers),
so f(12) = 6 f(10) = 6* 5 f(8) = 30 * 4f(6) = 120*3f(4) = 360*2f(2) = 720

81.第1 組百度面試題
1.一個(gè)int 數(shù)組，里面數(shù)據(jù)無(wú)任何限制，要求求出所有這樣的數(shù)a[i]，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。能否只用一個(gè)額外數(shù)組和少量其它空間實(shí)現(xiàn)。
ANSWER
Sort the array to another array, compare it with the original array, all a[i] = b[i] are answers.

2.一個(gè)文件，內(nèi)含一千萬(wàn)行字符串，每個(gè)字符串在1K 以內(nèi)，要求找出所有相反的串對(duì)，如abc 和cba。
ANSWER
So we have ~10G data. It is unlikely to put them all into main memory. Anyway, calculate the hash of each line in the first round, at the second round calculate the hash of the reverse of the line and remembers only the line number pairs that the hashes of the two directions collides. The last round only test those lines.

3.STL 的set 用什么實(shí)現(xiàn)的？為什么不用hash？
ANSWER
I don’t quite know. Only heard of that map in stl is implemented with red-black tree. One good thing over hash is that you don’t need to re-hash when data size grows.

82.第2 組百度面試題
1.給出兩個(gè)集合A 和B，其中集合A={name}，
集合B={age、sex、scholarship、address、...}，
要求：
問(wèn)題1、根據(jù)集合A 中的name 查詢出集合B 中對(duì)應(yīng)的屬性信息；
問(wèn)題2、根據(jù)集合B 中的屬性信息（單個(gè)屬性，如age<20 等），查詢出集合A 中對(duì)應(yīng)的name。
ANSWER
SQL? Not a good defined question.

2.給出一個(gè)文件，里面包含兩個(gè)字段{url、size}，即url 為網(wǎng)址，size 為對(duì)應(yīng)網(wǎng)址訪問(wèn)的次數(shù)
要求：
問(wèn)題1、利用Linux Shell 命令或自己設(shè)計(jì)算法，查詢出url 字符串中包含“baidu”子字符串對(duì)應(yīng)的size 字段值；
問(wèn)題2、根據(jù)問(wèn)題1 的查詢結(jié)果，對(duì)其按照size 由大到小的排列。
（說(shuō)明：url 數(shù)據(jù)量很大，100 億級(jí)以上）
ANSWER
1. shell: gawk ‘ /baidu/ { print $2 } ’ FILE
2. shell: gawk ‘ /baidu/ {print $2}’ FILE | sort -n -r

83.第3 組百度面試題
1.今年百度的一道題目
百度筆試：給定一個(gè)存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。
要求：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度為O（n）。
ANSWER
Have done this.
2.百度筆試題
用C 語(yǔ)言實(shí)現(xiàn)函數(shù)void * memmove(void *dest, const void *src, size_t n)。memmove 函數(shù)的功能是拷貝src 所指的內(nèi)存內(nèi)容前n 個(gè)字節(jié)到dest 所指的地址上。
分析：
由于可以把任何類型的指針賦給void 類型的指針, 這個(gè)函數(shù)主要是實(shí)現(xiàn)各種數(shù)據(jù)類型的拷貝。
ANSWER
//To my memory, usually memcpy doesn’t check overlap, memmove do
void * memmove(void * dest, const void * src, size_t n) {
? if (dest==NULL || src == NULL) error(“NULL pointers”);
? byte * psrc = (byte*)src;
? byte * pdest = (byte*)dest;
? int step = 1;
? if (dest < src + n) {
??? psrc = (byte*)(src+n-1);
??? pdest = (byte*)(dest+n-1);
??? step = -1;
? }
? for (int i=0; i<n; i++) {
??? pdest = psrc;
??? pdest += step; psrc += step;
? }
}

84.第4 組百度面試題
2010 年3 道百度面試題[相信，你懂其中的含金量]
1.a~z 包括大小寫(xiě)與0~9 組成的N 個(gè)數(shù), 用最快的方式把其中重復(fù)的元素挑出來(lái)。
ANSWER
By fastest, so memory is not the problem, hash is the first choice. Or trie will do.
Both run in O(Size) time, where size is the total size of the imput.

2.已知一隨機(jī)發(fā)生器，產(chǎn)生0 的概率是p，產(chǎn)生1 的概率是1-p，現(xiàn)在要你構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造0 和1 的概率均為1/2；構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造1、2、3 的概率均為1/3；...，構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造1、2、3、...n 的概率均為1/n，要求復(fù)雜度最低。
ANSWER
Run rand() twice, we got 00, 01, 10 or 11. If it’s 00 or 11, discard it, else output 0 for 01, 1 for 10.

Similarly, assume C(M, 2) >= n and C(M-1, 2) < n. Do M rand()’s and get a binary string of M length. Assign 1100...0 to 1, 1010...0 to 2, ...

3.有10 個(gè)文件，每個(gè)文件1G，
每個(gè)文件的每一行都存放的是用戶的query，每個(gè)文件的query 都可能重復(fù)。
要求按照query 的頻度排序.
ANSWER
If there is no enough memory, do bucketing first. For each bucket calculate the frequency of each query and sort. Then combine all the frequencies with multiway mergesort.

85.又見(jiàn)字符串的問(wèn)題
1.給出一個(gè)函數(shù)來(lái)復(fù)制兩個(gè)字符串A 和B。字符串A 的后幾個(gè)字節(jié)和字符串B 的前幾個(gè)字節(jié)重疊。分析：記住，這種題目往往就是考你對(duì)邊界的考慮情況。
ANSWER
Special case of memmove.

2.已知一個(gè)字符串，比如asderwsde,尋找其中的一個(gè)子字符串比如sde 的個(gè)數(shù)，如果沒(méi)有返回0，有的話返回子字符串的個(gè)數(shù)。
ANSWER
ANSWER
int count_of_substr(const char* str, const char * sub) {
? int count = 0;
? char * p = str;
? int n = strlen(sub);
? while ( *p != ‘\0’ ) {
??? if (strncmp(p, sub, n) == 0) count ++;
??? p++;
? }
? return count;
}

Also recursive way works. Possible optimizations like Sunday algorithm or Rabin-Karp algorithm will do.

86.
怎樣編寫(xiě)一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹(shù)中？
分析:本題考察二叉搜索樹(shù)的建樹(shù)方法，簡(jiǎn)單的遞歸結(jié)構(gòu)。關(guān)于樹(shù)的算法設(shè)計(jì)一定要聯(lián)想到遞歸，因?yàn)闃?shù)本身就是遞歸的定義。而，學(xué)會(huì)把遞歸改稱非遞歸也是一種必要的技術(shù)。畢竟，遞歸會(huì)造成棧溢出，關(guān)于系統(tǒng)底層的程序中不到非不得以最好不要用。但是對(duì)某些數(shù)學(xué)問(wèn)題，就一定要學(xué)會(huì)用遞歸去解決。
ANSWER
This is the first question I’m given in a google interview.

Node * array2Tree(int[] array) {
? return helper(array, 0, n-1);
}

Node * helper(int[] array, int start, int end) {
? if (start > end) return NULL;
? int m = start + (end-start)/2;
? Node * root = new Node(array[m]);
? root->left = helper(array, start, m-1);
? root->right = helper(array, m+1, end);
? return root;
}

87.
1.大整數(shù)數(shù)相乘的問(wèn)題。（這是2002 年在一考研班上遇到的算法題）
ANSWER
Do overflow manually.
final static long mask = (1 << 31) - 1;
ArrayList<Integer> multiply(ArrayList <Integer> a, ArrayList<Integer> b) {
? ArrayList<Integer> result = new ArrayList<Integer>(a.size()*b.size()+1);
? for (int i=0; i<a.size(); i++) {
??? multiply(b, a.get(i), i, result);
? }
? return result;
}
void multiply(ArrayList<Integer> x, int a, int base, ArrayList<Integer> result) {
? if (a == 0) return;
? long overflow = 0;
? int i;
? for (i=0; i<x.size(); i++) {
??? long tmp = x.get(i) * a + result.get(base+i) + overflow;
??? result.set(base+i, (int)(mask & tmp));
??? overflow = (tmp >> 31);
? }
? while (overflow != 0) {
??? long tmp = result.get(base+i) + overflow;
??? result.set(base+i, (int) (mask & tmp));
??? overflow = (tmp >> 31);
? }
}

2.求最大連續(xù)遞增數(shù)字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
ANSWER
Have done this.

3.實(shí)現(xiàn)strstr 功能，即在父串中尋找子串首次出現(xiàn)的位置。
（筆試中常讓面試者實(shí)現(xiàn)標(biāo)準(zhǔn)庫(kù)中的一些函數(shù)）
ANSWER
Have done this.

88.2005 年11 月金山筆試題。編碼完成下面的處理函數(shù)。
函數(shù)將字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改變非'*'字符的先后順序，函數(shù)返回串中字符'*'的數(shù)量。如原始串為：ab**cd**e*12，處理后為*****abcde12，函數(shù)并返回值為5。（要求使用盡量少的時(shí)間和輔助空間）
ANSWER
It’s like partition in quick sort. Just keep the non-* part stable.

int partitionStar(char a[]) {
? int count = 0;
? int i = a.length-1, j=a.length-1; // i for the cursor, j for the first non-* char
? while (i >= 0) {
??? if (a[i] != ‘*’) {
????? swap(a, i--, j--);
??? } else {
????? i--; count ++;
??? }
? }
? return count;?
}

89.神州數(shù)碼、華為、東軟筆試題
1.2005 年11 月15 日華為軟件研發(fā)筆試題。實(shí)現(xiàn)一單鏈表的逆轉(zhuǎn)。
ANSWER
Have done this.

2.編碼實(shí)現(xiàn)字符串轉(zhuǎn)整型的函數(shù)（實(shí)現(xiàn)函數(shù)atoi 的功能），據(jù)說(shuō)是神州數(shù)碼筆試題。如將字符串”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0
ANSWER
int atoi(const char * a) {
? if (*a==’+’) return atoi(a+1);
? else if (*a==’-’) return - atoi(a+1);
? char *p = a;
? int c = 0;
? while (*p >= ‘0’ && *p <= ‘9’) {
??? c = c*10 + (*p - ‘0’);
? }
? return c;
}

3.快速排序（東軟喜歡考類似的算法填空題，又如堆排序的算法等）
ANSWER
Standard solution. Skip.

4.刪除字符串中的數(shù)字并壓縮字符串。如字符串”abc123de4fg56”處理后變?yōu)椤盿bcdefg”。注意空間和效率。（下面的算法只需要一次遍歷，不需要開(kāi)辟新空間，時(shí)間復(fù)雜度為O(N)）
ANSWER
Also partition, keep non-digit stable.
char * partition(const char * str) {
? char * i = str;? // i for cursor, j for the first digit char;
? char * j = str;
? while (*i != ‘\0’) {
??? if (*i > ‘9’ || *i < ‘0’) {
????? *j++ = *i++;
??? } else {
????? *i++;
??? }
? }
? *j = ‘\0’;
? return str;
}

5.求兩個(gè)串中的第一個(gè)最長(zhǎng)子串（神州數(shù)碼以前試題）。
如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。
ANSWER
Use suffix tree. The longest common substring is the longest prefix of the suffixes.
O(n) to build suffix tree. O(n) to find the lcs.

90.
1.不開(kāi)辟用于交換數(shù)據(jù)的臨時(shí)空間，如何完成字符串的逆序
(在技術(shù)一輪面試中，有些面試官會(huì)這樣問(wèn))。
ANSWER
Two cursors.

2.刪除串中指定的字符
（做此題時(shí)，千萬(wàn)不要開(kāi)辟新空間，否則面試官可能認(rèn)為你不適合做嵌入式開(kāi)發(fā)）
ANSWER
Have done this.

3.判斷單鏈表中是否存在環(huán)。
ANSWER
Have done this.

91
1.一道著名的毒酒問(wèn)題
有1000 桶酒，其中1 桶有毒。而一旦吃了，毒性會(huì)在1 周后發(fā)作。現(xiàn)在我們用小老鼠做實(shí)驗(yàn)，要在1 周內(nèi)找出那桶毒酒，問(wèn)最少需要多少老鼠。
ANSWER
Have done this. 10 mices.

2.有趣的石頭問(wèn)題
有一堆1 萬(wàn)個(gè)石頭和1 萬(wàn)個(gè)木頭，對(duì)于每個(gè)石頭都有1 個(gè)木頭和它重量一樣，
把配對(duì)的石頭和木頭找出來(lái)。
ANSWER
Quick sort.

92.
1.多人排成一個(gè)隊(duì)列,我們認(rèn)為從低到高是正確的序列,但是總有部分人不遵守秩序。如果說(shuō),前面的人比后面的人高(兩人身高一樣認(rèn)為是合適的), 那么我們就認(rèn)為這兩個(gè)人是一對(duì)“搗亂分子”,比如說(shuō),現(xiàn)在存在一個(gè)序列:
176, 178, 180, 170, 171
這些搗亂分子對(duì)為
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,現(xiàn)在給出一個(gè)整型序列,請(qǐng)找出這些搗亂分子對(duì)的個(gè)數(shù)(僅給出搗亂分子對(duì)的數(shù)目即可,不用具體的對(duì))
要求：
輸入:
為一個(gè)文件(in)，文件的每一行為一個(gè)序列。序列全為數(shù)字，數(shù)字間用”,”分隔。
輸出：
為一個(gè)文件(out)，每行為一個(gè)數(shù)字，表示搗亂分子的對(duì)數(shù)。
詳細(xì)說(shuō)明自己的解題思路，說(shuō)明自己實(shí)現(xiàn)的一些關(guān)鍵點(diǎn)。
并給出實(shí)現(xiàn)的代碼，并分析時(shí)間復(fù)雜度。
限制：
輸入每行的最大數(shù)字個(gè)數(shù)為100000 個(gè)，數(shù)字最長(zhǎng)為6 位。程序無(wú)內(nèi)存使用限制。
ANSWER
The answer is the swap number of insertion sort. The straightforward method is to do insertion sort and accumulate the swap numbers, which is slow: O(n^2)

A sub-quadratic solution can be done by DP.

f(n) = f(n-1) + Index(n)
Index(n), which is to determine how many numbers is smaller than a[n] in a[0..n-1], can be done in log(n) time using BST with subtree size.

93.在一個(gè)int 數(shù)組里查找這樣的數(shù)，它大于等于左側(cè)所有數(shù)，小于等于右側(cè)所有數(shù)。直觀想法是用兩個(gè)數(shù)組a、b。a[i]、b[i]分別保存從前到i 的最大的數(shù)和從后到i 的最小的數(shù)，一個(gè)解答：這需要兩次遍歷，然后再遍歷一次原數(shù)組，將所有data[i]>=a[i-1]&&data[i]&lt;=b[i]的data[i]找出即可。給出這個(gè)解答后，面試官有要求只能用一個(gè)輔助數(shù)組，且要求少遍歷一次。
ANSWER
It is natural to improve the hint... just during the second traversal, do the range minimum and picking together. There is no need to store the range minimums.

94.微軟筆試題
求隨機(jī)數(shù)構(gòu)成的數(shù)組中找到長(zhǎng)度大于=3 的最長(zhǎng)的等差數(shù)列, 輸出等差數(shù)列由小到大:
如果沒(méi)有符合條件的就輸出
格式：
輸入[1,3,0,5,-1,6]
輸出[-1,1,3,5]
要求時(shí)間復(fù)雜度，空間復(fù)雜度盡量小
ANSWER
Firstly sort the array. Then do DP: for each a[i], update the length of the arithmetic sequences. That’s a O(n^3) solution. Each arithmetic sequence can be determined by the last item and the step size.

95.華為面試題
1 判斷一字符串是不是對(duì)稱的，如：abccba
ANSWER
Two cursors.

2.用遞歸的方法判斷整數(shù)組a[N]是不是升序排列
ANSWER
boolean isAscending(int a[]) {
? return isAscending(a, 0);
}
boolean isAscending(int a[], int start) {
? return start == a.length - 1 || isAscending(a, start+1);
}

96.08 年中興校園招聘筆試題
1．編寫(xiě)strcpy 函數(shù)
已知strcpy 函數(shù)的原型是
char *strcpy(char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。不調(diào)用C++/C 的字符串庫(kù)函數(shù)，請(qǐng)編寫(xiě)函數(shù)strcpy
ANSWER
char *strcpy(char *strDest, const char *strSrc) {
? if (strSrc == NULL) return NULL;
? char *i = strSrc, *j = strDest;
? while (*i != ‘\0’) {
??? *j++ = *i++;
? }
? *j = ‘\0’;
? return strDest;
}
Maybe you need to check if src and dest overlaps, then decide whether to copy from tail to head.

最后壓軸之戲，終結(jié)此微軟等100 題系列V0.1 版。
那就，
連續(xù)來(lái)幾組微軟公司的面試題，讓你一次爽個(gè)夠：
======================
97.第1 組微軟較簡(jiǎn)單的算法面試題
1.編寫(xiě)反轉(zhuǎn)字符串的程序，要求優(yōu)化速度、優(yōu)化空間。
ANSWER
Have done this.

2.在鏈表里如何發(fā)現(xiàn)循環(huán)鏈接？
ANSWER
Have done this.

3.編寫(xiě)反轉(zhuǎn)字符串的程序，要求優(yōu)化速度、優(yōu)化空間。
ANSWER
Have done this.

4.給出洗牌的一個(gè)算法，并將洗好的牌存儲(chǔ)在一個(gè)整形數(shù)組里。
ANSWER
Have done this.

5.寫(xiě)一個(gè)函數(shù)，檢查字符是否是整數(shù)，如果是，返回其整數(shù)值。
（或者：怎樣只用4 行代碼編寫(xiě)出一個(gè)從字符串到長(zhǎng)整形的函數(shù)？）
ANSWER
Char or string?
have done atoi;

98.第2 組微軟面試題
1.給出一個(gè)函數(shù)來(lái)輸出一個(gè)字符串的所有排列。
ANSWER
Have done this...

2.請(qǐng)編寫(xiě)實(shí)現(xiàn)malloc()內(nèi)存分配函數(shù)功能一樣的代碼。
ANSWER
Way too hard as an interview question...
Please check wikipedia for solutions...

?

3.給出一個(gè)函數(shù)來(lái)復(fù)制兩個(gè)字符串A 和B。字符串A 的后幾個(gè)字節(jié)和字符串B 的前幾個(gè)字節(jié)重疊。
ANSWER
Copy from tail to head.

4.怎樣編寫(xiě)一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹(shù)中？
ANSWER
Have done this.

5.怎樣從頂部開(kāi)始逐層打印二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)？請(qǐng)編程。
ANSWER
Have done this...

6.怎樣把一個(gè)鏈表掉個(gè)順序（也就是反序，注意鏈表的邊界條件并考慮空鏈表）？
ANSWER
Have done this...

99.第3 組微軟面試題
1.燒一根不均勻的繩，從頭燒到尾總共需要1 個(gè)小時(shí)。現(xiàn)在有若干條材質(zhì)相同的繩子，問(wèn)如何用燒繩的方法來(lái)計(jì)時(shí)一個(gè)小時(shí)十五分鐘呢？
ANSWER
May have done this... burn from both side gives ? hour.

2.你有一桶果凍，其中有黃色、綠色、紅色三種，閉上眼睛抓取同種顏色的兩個(gè)。抓取多少個(gè)就可以確定你肯定有兩個(gè)同一顏色的果凍？（5 秒-1 分鐘）
ANSWER
4.

3.如果你有無(wú)窮多的水，一個(gè)3 公升的提捅，一個(gè)5 公升的提捅，兩只提捅形狀上下都不均
勻，問(wèn)你如何才能準(zhǔn)確稱出4 公升的水？（40 秒-3 分鐘）
ANSWER
5 to 3 => 2
2 to 3, remaining 1
5 to remaining 1 => 4

一個(gè)岔路口分別通向誠(chéng)實(shí)國(guó)和說(shuō)謊國(guó)。
來(lái)了兩個(gè)人，已知一個(gè)是誠(chéng)實(shí)國(guó)的，另一個(gè)是說(shuō)謊國(guó)的。
誠(chéng)實(shí)國(guó)永遠(yuǎn)說(shuō)實(shí)話，說(shuō)謊國(guó)永遠(yuǎn)說(shuō)謊話。現(xiàn)在你要去說(shuō)謊國(guó)，
但不知道應(yīng)該走哪條路，需要問(wèn)這兩個(gè)人。請(qǐng)問(wèn)應(yīng)該怎么問(wèn)？（20 秒-2 分鐘）
ANSWER
Seems there are too many answers.
I will pick anyone to ask: how to get to your country? Then pick the other way.

100.第4 組微軟面試題，挑戰(zhàn)思維極限
1.12 個(gè)球一個(gè)天平，現(xiàn)知道只有一個(gè)和其它的重量不同，問(wèn)怎樣稱才能用三次就找到那個(gè)
球。13 個(gè)呢？（注意此題并未說(shuō)明那個(gè)球的重量是輕是重，所以需要仔細(xì)考慮）（5 分鐘-1 小時(shí)）
ANSWER
Too complicated. Go find brain teaser answers by yourself.

2.在9 個(gè)點(diǎn)上畫(huà)10 條直線，要求每條直線上至少有三個(gè)點(diǎn)？（3 分鐘-20 分鐘）

3.在一天的24 小時(shí)之中，時(shí)鐘的時(shí)針、分針和秒針完全重合在一起的時(shí)候有幾次？都分別是什么時(shí)間？你怎樣算出來(lái)的？（5 分鐘-15 分鐘）

30
終結(jié)附加題：
微軟面試題，挑戰(zhàn)你的智商
==========
說(shuō)明：如果你是第一次看到這種題，并且以前從來(lái)沒(méi)有見(jiàn)過(guò)類似的題型，
并且能夠在半個(gè)小時(shí)之內(nèi)做出答案，說(shuō)明你的智力超常..）
1.第一題. 五個(gè)海盜搶到了100 顆寶石，每一顆都一樣大小和價(jià)值連城。他們決定這么分：
抽簽決定自己的號(hào)碼（1、2、3、4、5）
首先，由1 號(hào)提出分配方案，然后大家表決，當(dāng)且僅當(dāng)超過(guò)半數(shù)的人同意時(shí)，
按照他的方案進(jìn)行分配，否則將被扔進(jìn)大海喂鯊魚(yú)
如果1 號(hào)死后，再由2 號(hào)提出分配方案，然后剩下的4 人進(jìn)行表決，
當(dāng)且僅當(dāng)超過(guò)半數(shù)的人同意時(shí)，按照他的方案進(jìn)行分配，否則將被扔入大海喂鯊魚(yú)。
依此類推
條件：每個(gè)海盜都是很聰明的人，都能很理智地做出判斷，從而做出選擇。
問(wèn)題：第一個(gè)海盜提出怎樣的分配方案才能使自己的收益最大化？
Answer:
A traditional brain teaser.
Consider #5, whatever #4 proposes, he won’t agree, so #4 must agree whatever #3 proposes. So if there are only #3-5, #3 should propose (100, 0, 0). So the expected income of #3 is 100, and #4 and #5 is 0 for 3 guy problem. So whatever #2 proposes, #3 won’t agree, but if #2 give #4 and #5 $1, they can get more than 3-guy subproblem. So #2 will propose (98, 0, 1, 1). So for #1, if give #2 less than $98, #2 won’t agree. But he can give #3 $1 and #4 or #5 $2, so this is a (97, 0, 1, 2, 0) solution.

2.一道關(guān)于飛機(jī)加油的問(wèn)題，已知：
每個(gè)飛機(jī)只有一個(gè)油箱，
飛機(jī)之間可以相互加油（注意是相互，沒(méi)有加油機(jī)）
一箱油可供一架飛機(jī)繞地球飛半圈，
問(wèn)題：
為使至少一架飛機(jī)繞地球一圈回到起飛時(shí)的飛機(jī)場(chǎng)，至少需要出動(dòng)幾架飛機(jī)？
（所有飛機(jī)從同一機(jī)場(chǎng)起飛，而且必須安全返回機(jī)場(chǎng)，不允許中途降落，中間沒(méi)有飛機(jī)場(chǎng)）

Pass。ok，微軟面試全部100題答案至此完。

-------------------------------------------------------------------------------------------------------------------------------

出處：http://blog.csdn.net/v_july_v/article/details/6870251

總結(jié)

以上是生活随笔為你收集整理的微软等数据结构+算法面试100题全部答案集锦的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。