微軟等數據結構+算法面試100題全部答案集錦

作者：July、阿財。
時間：二零一一年十月十三日。

• 引言

無私分享造就開源的輝煌。

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

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

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

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

互聯網總是能給人帶來驚喜。前幾日，一位現居美國加州的名叫阿財的朋友發來一封郵件，并把他自己做的全部100題的答案一并發予給我，自此，便似遇見了知己。十分感謝。
任何東西只有分享出來才更顯其價值。本只需貼出后面40題的答案，因為前60題的答案本人早已整理上傳至網上，但多一種思路多一種參考亦未嘗不可。特此，把阿財的答案再稍加整理番，然后把全部100題的答案現今都貼出來。若有任何問題，歡迎不吝指正。謝謝。

上千上萬的人都關注過此100題，且大都都各自貢獻了自己的思路，或回復于 微軟100題維護地址 上，或回復于本博客內，人數眾多，無法一一標明，特此向他們諸位表示敬意和感謝。謝謝大家，諸君的努力足以影響整個互聯網，咱們已經迎來一個分享互利的新時代。

• 微軟面試100題全部答案

最新整理的全部100題的答案參見如下（重復的，以及一些無關緊要的題目跳過。且因尊重阿財，未作過多修改。因此， 有些答案是還有問題的 ，最靠譜的答案以 程序員編程藝術系列 為準，亦可參考個人之前整理的前60題的答案：

• 第1題-20題答案： http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx ；
• 第21-40題答案： http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx ；
• 第41-60題答案： http://blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx 。

更新 ：有朋友反應，以下的答案中思路過于簡略，還是這句話，一切以 程序員編程藝術系列 （多種思路，多種比較，細細讀之自曉其理）為準（ 我沒怎么看阿財的這些答案，因為編程藝術系列已經說得足夠清晰了。 之所以把阿財的這份答案分享出來， 一者 ，編程藝術系列目前還只寫到了第二十二章，即100題之中還只詳細闡述了近30道題； 二者 ，他給的答案全部是用英文寫的，這恰好方便國外的一些朋友參考； 三者 是為了給那一些急功近利的、浮躁的人一份速成的答案罷了 ）。July、二零一一年十月二十四日更新。

當然，讀者朋友有任何問題，你也可以跟阿財聯系，他的郵箱地址是： kevinn9#gmail.com (把#改成@)。

1.把二元查找樹轉變成排序的雙向鏈表
題目：
輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的結點，只調整指針的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹節點的數據結構如下：
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.設計包含min 函數的棧。
定義棧的數據結構，要求添加一個min 函數，能夠得到棧的最小元素。
要求函數min、push 以及pop 的時間復雜度都是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.求子數組的最大和
題目：
輸入一個整形數組，數組里有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，
因此輸出為該子數組的和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.在二元樹中找出和為某一值的所有路徑
題目：輸入一個整數和一棵二元樹。
從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
打印出和與輸入整數相等的所有路徑。
例如輸入整數22 和如下二元樹
10
/ \
5 12
/ \
4 7
則打印出兩條路徑：10, 12 和10, 5, 7。
二元樹節點的數據結構定義為：
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 個元素
題目：輸入n 個整數，輸出其中最小的k 個。
例如輸入1，2，3，4，5，6，7 和8 這8 個數字，則最小的4 個數字為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 分鐘時間，根據上排給出十個數，在其下排填出對應的十個數
要求下排每個數都是先前上排那十個數在下排出現的次數。
上排的十個數如下：
【0，1，2，3，4，5，6，7，8，9】
舉一個例子，
數值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出現了6 次，1 在下排出現了2 次，
2 在下排出現了1 次，3 在下排出現了0 次....
以此類推..
ANSWER:
I don’t like brain teasers. Will skip most of them...

第7 題
微軟亞院之編程判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設倆個鏈表均不帶環。
問題擴展：
1.如果鏈表可能有環列?
2.如果需要求出倆個鏈表相交的第一個節點列?
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 題
此貼選一些比較怪的題，，由于其中題目本身與算法關系不大，僅考考思維。特此并作一題。
1.有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關，
這兩個房間是分割開的，從一間里不能看到另一間的情況。
現在要求受訓者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關控制的。
有什么辦法呢？
ANSWER:
Skip.

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

3. ★用一種算法來顛倒一個鏈接表的順序?，F在在不用遞歸式的情況下做一遍。
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;
}
★用一種算法在一個循環的鏈接表里插入一個節點，但不得穿越鏈接表。
ANSWER:
I don’t understand what is “Chuanyue”.
★用一種算法整理一個數組。你為什么選擇這種方法?
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;
}

★顛倒一個字符串。優化速度。優化空間。
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;
}
}
★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，
實現速度最快，移動最少。
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);
}
}
★找到一個子字符串。優化速度。優化空間。
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;
}
★比較兩個字符串，用O(n)時間和恒量空間。
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.
}
★假設你有一個用1001 個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1 到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重復的那個數字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?
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 倍?，F在用同樣的方法增加7 倍。
ANSWER:
n<<3;
(n<<3)-n;

第9 題
判斷整數序列是不是二元查找樹的后序遍歷結果
題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回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 題
翻轉句子中單詞的順序。
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。
句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
Answer:
Already done this. Skipped.

第11 題
求二叉樹中節點的最大距離...
如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節點之間邊的個數。
寫一個程序，
求一棵二叉樹中相距最遠的兩個節點之間的距離。
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 等關鍵字以及條件判斷語句
（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 題：
題目：輸入一個單向鏈表，輸出該鏈表中倒數第k 個結點。鏈表的倒數第0 個結點為鏈表的尾指針。
鏈表結點定義如下：
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 題：
題目：輸入一個已經按升序排序過的數組和一個數字，
在數組中查找兩個數，使得它們的和正好是輸入的那個數字。
要求時間復雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。
例如輸入數組1、2、4、7、11、15 和數字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 題：
題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，
即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。
用遞歸和循環兩種方法完成樹的鏡像轉換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
定義二元查找樹的結點為：
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 題：
題目（微軟）：
輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。
例如輸入
7
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 題：
題目：在一個字符串中找到第一個只出現一次的字符。如輸入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 個數字（0,1,…,n-1）形成一個圓圈，從數字0 開始，
每次從這個圓圈中刪除第m 個數字（第一個為當前數字本身，第二個為當前數字的下一個數
字）。
當一個數字刪除后，從被刪除數字的下一個繼續刪除第m 個數字。
求出在這個圓圈中剩下的最后一個數字。
July：我想，這個題目，不少人已經見識過了。
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...長出一口氣。。。

第19 題：
題目：定義Fibonacci 數列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數列的第n 項。
分析：在很多C 語言教科書中講到遞歸函數的時候，都會用Fibonacci 作為例子。
因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。
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 題：
題目：輸入一個表示整數的字符串，把該字符串轉換成整數并輸出。
例如輸入字符串"345"，則輸出整數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 年中興面試題
編程求解：
輸入兩個整數n 和m，從數列1，2，3.......n 中隨意取幾個數,
使其和等于m ,要求將其中所有的可能組合列出來.
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 張藍色的牌，主持人先拿任意兩張，再分別在A、B、C 三人額頭上貼任意兩張牌，A、B、C 三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A 說不知道，B 說不知道，C 說不知道，然后A 說知道了。
請教如何推理，A 是怎么知道的。如果用程序，又怎么實現呢？
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 題：
用最簡單，最快速的方法計算出下面這個圓形是否和正方形相交。"
3D 坐標系原點(0.0,0.0,0.0)
圓形:
半徑r = 3.0
圓心o = (*.*, 0.0, *.*)
正方形:
4 個角坐標;
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 題：
寫一個函數,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出連續最長的數字串，并把這個串的長度返回，
并把這個最長數字串付給其中一個函數參數outputstr 所指內存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr 后，函數將返回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.左旋轉字符串
題目：
定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。
如把字符串abcdef 左旋轉2 位得到字符串cdefab。請實現字符串左旋轉的函數。
要求時間對長度為n 的字符串操作的復雜度為O(n)，輔助內存為O(1)。
ANSWER
Have done it. Using reverse word function above.

27.跳臺階問題
題目：一個臺階總共有n 級，如果一次可以跳1 級，也可以跳2 級。
求總共有多少總跳法，并分析算法的時間復雜度。
這道題最近經常出現，包括MicroStrategy 等比較重視算法的公司
都曾先后選用過個這道題作為面試題或者筆試題。
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.整數的二進制表示中1 的個數
題目：輸入一個整數，求該整數的二進制表達中有多少個1。
例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。
分析：
這是一道很基本的考查位運算的面試題。
包括微軟在內的很多公司都曾采用過這道題。
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 序列
題目：輸入兩個整數序列。其中一個序列表示棧的push 順序，
判斷另一個序列有沒有可能是對應的pop 順序。
為了簡單起見，我們假設push 序列的任意兩個整數都是不相等的。
比如輸入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一個pop 系列。
因為可以有如下的push 和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 的正數中1 出現的次數
題目：輸入一個整數n，求從1 到n 這n 個整數的十進制表示中1 出現的次數。
例如輸入12，從1 到12 這些整數中包含1 的數字有1，10，11 和12，1 一共出現了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.華為面試題：
一類似于蜂窩的結構的圖，進行搜索最短路徑（要求5 分鐘）
ANSWER
Not clear problem. Skipped. Seems a Dijkstra could do.

int dij

32.
有兩個序列a,b，大小都為n,序列元素的值任意整數，無序；
要求：通過交換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.
實現一個挺高級的字符匹配算法：
給一串很長字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3 這些都要找出來
其實就是類似一些和諧系統。。。。。
ANSWER
Not a clear problem. Seems a bitset can do.

34.
實現一個隊列。
隊列的應用場景為：
一個生產者線程將int 類型的數入列，一個消費者線程將int 類型的數出列
ANSWER
I don’t know multithread programming at all....

35.
求一個矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時間復雜度;(3)用C 寫出關鍵代碼
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 上的網友，已標明）：
36.引用自網友：longzuo
谷歌筆試：
n 支隊伍比賽，分別編號為0，1，2。。。。n-1，已知它們之間的實力對比關系，
存儲在一個二維數組w[n][n]中，w[i][j] 的值代表編號為i，j 的隊伍中更強的一支。
所以w[i][j]=i 或者j，現在給出它們的出場順序，并存儲在數組order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是4 對3， 5 對8。.......
勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細分，即可以隨便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4 對5,直至出現第一名
編程實現，給出二維數組w，一維數組order 和用于輸出比賽名次的數組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 個長為m+1 的字符串，
如果某個字符串的最后m 個字符與某個字符串的前m 個字符匹配，則兩個字符串可以聯接，
問這n 個字符串最多可以連成一個多長的字符串，如果出現循環，則返回錯誤。
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.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用x 次天平，
最多可以從y 個小球中找出較輕的那個，求y 與x 的關系式。
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.有一個很大很大的輸入流，大到沒有存儲器可以將其存儲下來，
而且只輸入一次，如何從這個輸入流中隨機取得m 個記錄。
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 字符串，如何從中去除重復的，優化時間空間復雜度
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.
網易有道筆試：
(1).
求一個二叉樹中任意兩個節點間的最大距離，
兩個節點的距離的定義是這兩個節點間邊的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間復
雜度。
ANSWER
Have done this.
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，
有向圖不再連通，描述算法。
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.百度研發筆試題
引用自：zp155334877
1)設計一個棧結構，滿足一下條件：min，push，pop 操作的時間復雜度為O(1)。
ANSWER
Have done this.

2)一串首尾相連的珠子(m 個)，有N 種顏色(N<=10)，
設計一個算法，取出其中一段，要求包含所有N 中顏色，并使長度最短。
并分析時間復雜度與空間復雜度。
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)設計一個系統處理詞語搭配問題，比如說中國和人民可以搭配，
則中國人民人民中國都有效。要求：
*系統每秒的查詢數量可能上千次；
*詞語的數量級為10W；
*每個詞至多可以與1W 個詞搭配
當用戶輸入中國人民的時候，要求返回與這個搭配詞組相關的信息。
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.求固晶機的晶元查找程序
晶元盤由數目不詳的大小一樣的晶元組成，晶元并不一定全布滿晶元盤，
照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，
若匹配不過，照相機則按測好的晶元間距移到下一個位置。
求遍歷晶元盤的算法求思路。
ANSWER
Dont understand.

42.請修改append 函數，利用這個函數實現：
兩個非降序鏈表的并集，1->2->3 和2->3->5 并為1->2->3->5
另外只能輸出結果，不能修改兩個鏈表的數據。
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.遞歸和非遞歸倆種方法實現二叉樹的前序遍歷。
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.設計一個魔方（六面）的程序。
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.有一千萬條短信，有重復，以文本文件的形式保存，一行一條，有重復。
請用5 分鐘時間，找出重復出現最多的前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 萬條url，現在給你一條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.對于一個整數矩陣，存在一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）
某一個元素也加一，現給出一正數矩陣，判斷其是否能夠由一個全零矩陣經過上述運算得到。
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.一個整數數組，長度為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.搜狐：
四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（（））
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.創新工場：
求一個數組的最長遞減子序列比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{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.微軟：
一個數組是由一個遞減數列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數組中查找某一個數。
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.一道看上去很嚇人的算法面試題：
如何對n 個數進行排序，要求時間復雜度O(n)，空間復雜度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.網易有道筆試：
1.求一個二叉樹中任意兩個節點間的最大距離，兩個節點的距離的定義是這兩個節點間邊
的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間復
雜度。
ANSWER:
Have done this before.

2.求一個有向連通圖的割點，割點的定義是，
如果除去此節點和與其相關的邊，有向圖不再連通，描述算法。
ANSWER:
Have done this before.
-------------------------------------------------------------------
51.和為n 連續正數序列。
題目：輸入一個正數n，輸出所有和為n 連續正數序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個連續序列1-5、4-6 和7-8。
分析：這是網易的一道面試題。
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) {
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.二元樹的深度。
題目：輸入一棵二元樹的根結點，求該樹的深度。
從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為
樹的深度。

例如：輸入二元樹：
10
/ \
6 14
/ / \
4 12 16
輸出該樹的深度3。
二元樹的結點定義如下：
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
};
分析：這道題本質上還是考查二元樹的遍歷。

ANSWER:
Have done this.

53.字符串的排列。
題目：輸入一個字符串，打印出該字符串中字符的所有排列。
例如輸入字符串abc，則輸出由字符a、b、c 所能排列出來的所有字符串
abc、acb、bac、bca、cab 和cba。
分析：這是一道很好的考查對遞歸理解的編程題，
因此在過去一年中頻繁出現在各大公司的面試、筆試題中。
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.調整數組順序使奇數位于偶數前面。
題目：輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分，
所有偶數位于數組的后半部分。要求時間復雜度為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;
};
請實現其賦值運算符的重載函數，要求異常安全，即當對一個對象進行賦值時發生異常，對
象的狀態不能改變。
ANSWER
Pass...

56.最長公共字串。
題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，
則字符串一稱之為字符串二的子串。
注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。
請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
例如：輸入兩個字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它們的最長公共子串，則輸出它們的長度4，并打印任意一個子串。
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經典的動態規劃
題，因此一些重視算法的公司像MicroStrategy 都把它當作面試題。
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.用倆個棧實現隊列。
題目：某隊列的聲明如下：
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;
};
分析：從上面的類的聲明中，我們發現在隊列中有兩個棧。
因此這道題實質上是要求我們用兩個棧來實現一個隊列。
相信大家對棧和隊列的基本性質都非常了解了：棧是一種后入先出的數據容器，
因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數據容器，
我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。
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.從尾到頭輸出鏈表。
題目：輸入一個鏈表的頭結點，從尾到頭反過來輸出每個結點的值。鏈表結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。
該題以及它的變體經常出現在各大公司的面試、筆試題中。
ANSWER
Have answered this...

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

60.在O（1）時間內刪除鏈表結點。
題目：給定鏈表的頭指針和一個結點指針，在O(1)時間刪除該結點。鏈表結點的定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
函數的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：這是一道廣為流傳的Google 面試題，能有效考察我們的編程基本功，還能考察我們
的反應速度，
更重要的是，還能考察我們對時間復雜度的理解。
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.找出數組中兩個只出現一次的數字
題目：一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。
請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n)，空間復雜度是O(1)。
分析：這是一道很新穎的關于位運算的面試題。
ANSWER:
XOR.

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

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

64. 尋找丑數。
題目：我們把只包含因子2、3 和5 的數稱作丑數（Ugly Number）。例如6、8 都是丑數，
但14 不是，因為它包含因子7。習慣上我們把1 當做是第一個丑數。求按從小到大的順序的第1500 個丑數。
分析：這是一道在網絡上廣為流傳的面試題，據說google 曾經采用過這道題。
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 位數
題目：輸入數字n，按順序輸出從1 最大的n 位10 進制數。比如輸入3，則輸出1、2、3 一直到最大的3 位數即999。
分析：這是一道很有意思的題目。看起來很簡單，其實里面卻有不少的玄機。
ANSWER:
So maybe n could exceed i32? I cannot tell where is the trick...
Who will output 2*10^9 numbers...

66.顛倒棧。
題目：用遞歸顛倒一個棧。例如輸入棧{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.倆個閑玩娛樂。
1.撲克牌的順子
從撲克牌中隨機抽5 張牌，判斷是不是一個順子，即這5 張牌是不是連續的。2-10 為數字本身，A 為1，J 為11，Q 為12，K 為13，而大小王可以看成任意數字。
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 個骰子的點數。把n 個骰子扔在地上，所有骰子朝上一面的點數之和為S。輸入n，
打印出S 的所有可能的值出現的概率。
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.把數組排成最小的數。
題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的
一個。
例如輸入數組{32, 321}，則輸出這兩個能排成的最小數字32132。
請給出解決問題的算法，并證明該算法。
分析：這是09 年6 月份百度的一道面試題，
從這道題我們可以看出百度對應聘者在算法方面有很高的要求。
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.旋轉數組中的最小元素。
題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個
排好序的數組的一個旋轉，
輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數
組的最小值為1。
分析：這道題最直觀的解法并不難。從頭到尾遍歷數組一次，就能找出最小的元素，時間復雜度顯然是O(N)。但這個思路沒有利用輸入數組的特性，我們應該能找到更好的解法。
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.給出一個函數來輸出一個字符串的所有排列。
ANSWER 簡單的回溯就可以實現了。當然排列的產生也有很多種算法，去看看組合數學，
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth 的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數學功底，也需要一定的靈感，有興趣最好看看。
ANSWER:
Have done this.

71.數值的整數次方。
題目：實現函數double Power(double base, int exponent)，求base 的exponent 次方。
不需要考慮溢出。
分析：這是一道看起來很簡單的問題?？赡苡胁簧俚娜嗽诳吹筋}目后30 秒寫出如下的代碼：
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. 題目：設計一個類，我們只能生成該類的一個實例。
分析：只能生成一個實例的類是實現了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.對策字符串的最大長度。
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數，這個題目可以看成是該函數的
加強版。
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.數組中超過出現次數超過一半的數字
題目：數組中有一個數字出現的次數超過了數組長度的一半，找出這個數字。
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google 在內的多家公司都
曾經采用過這個題目。要幾十分鐘的時間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。
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.二叉樹兩個結點的最低共同父結點
題目：二叉樹的結點定義如下：
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入二叉樹中的兩個結點，輸出這兩個結點在數中最低的共同父結點。
分析：求數中兩個結點的最低共同結點是面試中經常出現的一個問題。這個問題至少有兩個
變種。
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.復雜鏈表的復制
題目：有一個復雜鏈表，其結點除了有一個m_pNext 指針指向下一個結點外，還有一個m_pSibling 指向鏈表中的任一結點或者NULL。其結點的C++定義如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下圖是一個含有5 個結點的該類型復雜鏈表。

圖中實線箭頭表示m_pNext 指針，虛線箭頭表示m_pSibling 指針。為簡單起見，指向NULL 的指針沒有畫出。請完成函數ComplexNode* Clone(ComplexNode* pHead)，以復制一個復雜鏈表。
分析：在常見的數據結構上稍加變化，這是一種很新穎的面試題。
要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應能力，
對數據結構透徹的理解以及扎實的編程功底。
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.關于鏈表問題的面試題目如下：
1.給定單鏈表，檢測是否有環。
使用兩個指針p1,p2 從鏈表頭開始遍歷，p1 每次前進一步，p2 每次前進兩步。如果p2 到
達鏈表尾部，說明無環，否則p1、p2 必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環。
2.給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。如果head1==head2，那么顯然相交，直接返回head1。否則，分別從head1,head2 開始遍歷兩個鏈表獲得其長度len1 與len2，假設len1>=len2，那么指針p1 由head1 開始向后移動len1-len2 步，指針p2=head2，下面p1、p2 每次向后前進一步并比較p1p2 是否相等，如果相等即返回該結點，否則說明兩個鏈表沒有交點。
3.給定單鏈表(head)，如果有環的話請返回從頭結點進入環的第一個節點。
運用題一，我們可以檢查鏈表中是否有環。如果有環，那么p1p2 重合點p 必然在環中。從p 點斷開環，方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，一條從head 開始，另一條從p2 開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。
4.只給定單鏈表中某個結點p(并非最后一個結點，即p->next!=NULL)指針，刪除該結點。辦法很簡單，首先是放p 中數據,然后將p->next 的數據copy 入p 中，接下來刪除p->next即可。
5.只給定單鏈表中某個結點p(非空結點)，在p 前面插入一個結點。辦法與前者類似，首先分配一個結點q，將q 插入在p 后，接下來將p 中的數據copy 入q中，然后再將要插入的數據記錄在p 中。

78.鏈表和數組的區別在哪里？
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點，現在公司招人的競爭可能就在細節上產生，誰比較仔細，誰獲勝的機會就大。
ANSWER
1. Besides the common staff, linked list is more abstract and array is usually a basic real world object. When mentioning “linked 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.編寫實現鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？
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.編寫實現數組排序的一種算法。說明為什么你會選擇用這樣的方法？
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.請編寫能直接實現strstr()函數功能的代碼。
ANSWER
Substring test? Have done this.

80.阿里巴巴一道筆試題
問題描述:
12 個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人
高,問排列方式有多少種?
這個筆試題,很YD,因為把某個遞歸關系隱藏得很深。
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.一個int 數組，里面數據無任何限制，要求求出所有這樣的數a[i]，其左邊的數都小于等于它，右邊的數都大于等于它。能否只用一個額外數組和少量其它空間實現。
ANSWER
Sort the array to another array, compare it with the original array, all a[i] = b[i] are answers.

2.一個文件，內含一千萬行字符串，每個字符串在1K 以內，要求找出所有相反的串對，如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 用什么實現的？為什么不用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.給出兩個集合A 和B，其中集合A={name}，
集合B={age、sex、scholarship、address、...}，
要求：
問題1、根據集合A 中的name 查詢出集合B 中對應的屬性信息；
問題2、根據集合B 中的屬性信息（單個屬性，如age<20 等），查詢出集合A 中對應的name。
ANSWER
SQL? Not a good defined question.

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

83.第3 組百度面試題
1.今年百度的一道題目
百度筆試：給定一個存放整數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數。
要求：空間復雜度O(1)，時間復雜度為O（n）。
ANSWER
Have done this.
2.百度筆試題
用C 語言實現函數void * memmove(void *dest, const void *src, size_t n)。memmove 函數的功能是拷貝src 所指的內存內容前n 個字節到dest 所指的地址上。
分析：
由于可以把任何類型的指針賦給void 類型的指針, 這個函數主要是實現各種數據類型的拷貝。
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 包括大小寫與0~9 組成的N 個數, 用最快的方式把其中重復的元素挑出來。
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.已知一隨機發生器，產生0 的概率是p，產生1 的概率是1-p，現在要你構造一個發生器，使得它構造0 和1 的概率均為1/2；構造一個發生器，使得它構造1、2、3 的概率均為1/3；...，構造一個發生器，使得它構造1、2、3、...n 的概率均為1/n，要求復雜度最低。
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 個文件，每個文件1G，
每個文件的每一行都存放的是用戶的query，每個文件的query 都可能重復。
要求按照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.又見字符串的問題
1.給出一個函數來復制兩個字符串A 和B。字符串A 的后幾個字節和字符串B 的前幾個字節重疊。分析：記住，這種題目往往就是考你對邊界的考慮情況。
ANSWER
Special case of memmove.

2.已知一個字符串，比如asderwsde,尋找其中的一個子字符串比如sde 的個數，如果沒有返回0，有的話返回子字符串的個數。
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.
怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？
分析:本題考察二叉搜索樹的建樹方法，簡單的遞歸結構。關于樹的算法設計一定要聯想到遞歸，因為樹本身就是遞歸的定義。而，學會把遞歸改稱非遞歸也是一種必要的技術。畢竟，遞歸會造成棧溢出，關于系統底層的程序中不到非不得以最好不要用。但是對某些數學問題，就一定要學會用遞歸去解決。
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.大整數數相乘的問題。（這是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.求最大連續遞增數字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
ANSWER
Have done this.

3.實現strstr 功能，即在父串中尋找子串首次出現的位置。
（筆試中常讓面試者實現標準庫中的一些函數）
ANSWER
Have done this.

88.2005 年11 月金山筆試題。編碼完成下面的處理函數。
函數將字符串中的字符'*'移到串的前部分，前面的非'*'字符后移，但不能改變非'*'字符的先后順序，函數返回串中字符'*'的數量。如原始串為：ab**cd**e*12，處理后為*****abcde12，函數并返回值為5。（要求使用盡量少的時間和輔助空間）
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.神州數碼、華為、東軟筆試題
1.2005 年11 月15 日華為軟件研發筆試題。實現一單鏈表的逆轉。
ANSWER
Have done this.

2.編碼實現字符串轉整型的函數（實現函數atoi 的功能），據說是神州數碼筆試題。如將字符串”+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.刪除字符串中的數字并壓縮字符串。如字符串”abc123de4fg56”處理后變為”abcdefg”。注意空間和效率。（下面的算法只需要一次遍歷，不需要開辟新空間，時間復雜度為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.求兩個串中的第一個最長子串（神州數碼以前試題）。
如"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.不開辟用于交換數據的臨時空間，如何完成字符串的逆序
(在技術一輪面試中，有些面試官會這樣問)。
ANSWER
Two cursors.

2.刪除串中指定的字符
（做此題時，千萬不要開辟新空間，否則面試官可能認為你不適合做嵌入式開發）
ANSWER
Have done this.

3.判斷單鏈表中是否存在環。
ANSWER
Have done this.

91
1.一道著名的毒酒問題
有1000 桶酒，其中1 桶有毒。而一旦吃了，毒性會在1 周后發作?，F在我們用小老鼠做實驗，要在1 周內找出那桶毒酒，問最少需要多少老鼠。
ANSWER
Have done this. 10 mices.

2.有趣的石頭問題
有一堆1 萬個石頭和1 萬個木頭，對于每個石頭都有1 個木頭和它重量一樣，
把配對的石頭和木頭找出來。
ANSWER
Quick sort.

92.
1.多人排成一個隊列,我們認為從低到高是正確的序列,但是總有部分人不遵守秩序。如果說,前面的人比后面的人高(兩人身高一樣認為是合適的), 那么我們就認為這兩個人是一對“搗亂分子”,比如說,現在存在一個序列:
176, 178, 180, 170, 171
這些搗亂分子對為
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,現在給出一個整型序列,請找出這些搗亂分子對的個數(僅給出搗亂分子對的數目即可,不用具體的對)
要求：
輸入:
為一個文件(in)，文件的每一行為一個序列。序列全為數字，數字間用”,”分隔。
輸出：
為一個文件(out)，每行為一個數字，表示搗亂分子的對數。
詳細說明自己的解題思路，說明自己實現的一些關鍵點。
并給出實現的代碼，并分析時間復雜度。
限制：
輸入每行的最大數字個數為100000 個，數字最長為6 位。程序無內存使用限制。
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.在一個int 數組里查找這樣的數，它大于等于左側所有數，小于等于右側所有數。直觀想法是用兩個數組a、b。a[i]、b[i]分別保存從前到i 的最大的數和從后到i 的最小的數，一個解答：這需要兩次遍歷，然后再遍歷一次原數組，將所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。給出這個解答后，面試官有要求只能用一個輔助數組，且要求少遍歷一次。
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.微軟筆試題
求隨機數構成的數組中找到長度大于=3 的最長的等差數列, 輸出等差數列由小到大:
如果沒有符合條件的就輸出
格式：
輸入[1,3,0,5,-1,6]
輸出[-1,1,3,5]
要求時間復雜度，空間復雜度盡量小
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 判斷一字符串是不是對稱的，如：abccba
ANSWER
Two cursors.

2.用遞歸的方法判斷整數組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．編寫strcpy 函數
已知strcpy 函數的原型是
char *strcpy(char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。不調用C++/C 的字符串庫函數，請編寫函數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.

最后壓軸之戲，終結此微軟等100 題系列V0.1 版。
那就，
連續來幾組微軟公司的面試題，讓你一次爽個夠：
======================
97.第1 組微軟較簡單的算法面試題
1.編寫反轉字符串的程序，要求優化速度、優化空間。
ANSWER
Have done this.

2.在鏈表里如何發現循環鏈接？
ANSWER
Have done this.

3.編寫反轉字符串的程序，要求優化速度、優化空間。
ANSWER
Have done this.

4.給出洗牌的一個算法，并將洗好的牌存儲在一個整形數組里。
ANSWER
Have done this.

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

98.第2 組微軟面試題
1.給出一個函數來輸出一個字符串的所有排列。
ANSWER
Have done this...

2.請編寫實現malloc()內存分配函數功能一樣的代碼。
ANSWER
Way too hard as an interview question...
Please check wikipedia for solutions...

3.給出一個函數來復制兩個字符串A 和B。字符串A 的后幾個字節和字符串B 的前幾個字節重疊。
ANSWER
Copy from tail to head.

4.怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？
ANSWER
Have done this.

5.怎樣從頂部開始逐層打印二叉樹結點數據？請編程。
ANSWER
Have done this...

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

99.第3 組微軟面試題
1.燒一根不均勻的繩，從頭燒到尾總共需要1 個小時?，F在有若干條材質相同的繩子，問如何用燒繩的方法來計時一個小時十五分鐘呢？
ANSWER
May have done this... burn from both side gives ? hour.

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

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

一個岔路口分別通向誠實國和說謊國。
來了兩個人，已知一個是誠實國的，另一個是說謊國的。
誠實國永遠說實話，說謊國永遠說謊話?，F在你要去說謊國，
但不知道應該走哪條路，需要問這兩個人。請問應該怎么問？（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 組微軟面試題，挑戰思維極限
1.12 個球一個天平，現知道只有一個和其它的重量不同，問怎樣稱才能用三次就找到那個
球。13 個呢？（注意此題并未說明那個球的重量是輕是重，所以需要仔細考慮）（5 分鐘-1 小時）
ANSWER
Too complicated. Go find brain teaser answers by yourself.

2.在9 個點上畫10 條直線，要求每條直線上至少有三個點？（3 分鐘-20 分鐘）

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

30
終結附加題：
微軟面試題，挑戰你的智商
==========
說明：如果你是第一次看到這種題，并且以前從來沒有見過類似的題型，
并且能夠在半個小時之內做出答案，說明你的智力超常..）
1.第一題. 五個海盜搶到了100 顆寶石，每一顆都一樣大小和價值連城。他們決定這么分：
抽簽決定自己的號碼（1、2、3、4、5）
首先，由1 號提出分配方案，然后大家表決，當且僅當超過半數的人同意時，
按照他的方案進行分配，否則將被扔進大海喂鯊魚
如果1 號死后，再由2 號提出分配方案，然后剩下的4 人進行表決，
當且僅當超過半數的人同意時，按照他的方案進行分配，否則將被扔入大海喂鯊魚。
依此類推
條件：每個海盜都是很聰明的人，都能很理智地做出判斷，從而做出選擇。
問題：第一個海盜提出怎樣的分配方案才能使自己的收益最大化？
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.一道關于飛機加油的問題，已知：
每個飛機只有一個油箱，
飛機之間可以相互加油（注意是相互，沒有加油機）
一箱油可供一架飛機繞地球飛半圈，
問題：
為使至少一架飛機繞地球一圈回到起飛時的飛機場，至少需要出動幾架飛機？
（所有飛機從同一機場起飛，而且必須安全返回機場，不允許中途降落，中間沒有飛機場）

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

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

• 后記

2010已過，如今個人早已在整理2011最新的面試題，參見如下：

• 微軟、谷歌、百度等公司經典面試100題[第1-60題] （微軟100題第二版前60題）
• 微軟、Google等公司非常好的面試題及解答[第61-70題] （微軟100題第二版第61-70題）
• 十道海量數據處理面試題與十個方法大總結 （十道海量數據處理面試題）
• 海量數據處理面試題集錦與Bit-map詳解 （十七道海量數據處理面試題）
• 九月騰訊，創新工場，淘寶等公司最新面試十三題 （2011年度9月最新面試30題）
• 十月百度，阿里巴巴，迅雷搜狗最新面試十一題 （2011年度十月最新面試題集錦）

一切的詳情，可看此文： 橫空出世，席卷Csdn--評微軟等數據結構+算法面試100題 （在此文中，你能找到與微軟100題所有一切相關的東西）。資源下載和維護地址分別如下所示：

• 所有的資源下載（題目+答案）地址： http://v_july_v.download.csdn.net/ 。
• 本微軟等100 題系列V0.1 版，永久維護地址： http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html 。

歡迎，任何人，就以上任何內容，題目與答案思路，或其它任何問題、與我聯系。本人郵箱： zhoulei0907@yahoo.cn 。

更新：本微軟公司面試 100題的全部答案日前已經上傳 資源，所有讀者可到此處下載： http://download.csdn.net/detail/v_JULY_v/3685306 。2011.10.15。

程序員編程藝術第一~二十七章集錦與總結

• 第一章、左旋轉字符串
• 第二章、字符串是否包含問題
• 第三章、尋找最小的k個數
• 第三章續、Top K算法問題的實現
• 第三章再續：快速選擇SELECT算法的深入分析與實現
• 三之三續、求數組中給定下標區間內的第K?。ù螅┰?
• 第四章、現場編寫類似strstr/strcpy/strpbrk的函數
• 第五章、尋找滿足條件的兩個或多個數
• 第六章、求解500萬以內的親和數
• 第七章、求連續子數組的最大和
• 第八章、從頭至尾漫談虛函數
• 第九章、閑話鏈表追趕問題
• 第十章、如何給10^7個數據量的磁盤文件排序
• 第十一章、最長公共子序列（LCS）問題
• 第十二~十五章：數的判斷，中簽概率，IP訪問次數，回文問題（初稿）
• 第十六~第二十章：全排列，跳臺階，奇偶排序，第一個只出現一次等問題
• 第二十一~二十二章：出現次數超過一半的數字，最短摘要的生成
• 第二十三、四章：楊氏矩陣查找，倒排索引關鍵詞Hash不重復編碼實踐
• 第二十五章：Jon Bentley：90%無法正確實現二分查找
• 第二十六章：基于給定的文檔生成倒排索引的編碼與實踐
• 第二十七章：不改變正負數之間相對順序重新排列數組

作者聲明：本人July 對以上所有任何內容和資料享有版權，轉載請注明作者本人July 及出處。
向你的厚道致敬。謝謝。二零一一年十月十三日、以諸君為傲。

微軟面試100題2010年版全部答案集錦（含下載地址）