免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 回復 發帖

1

微軟等資料結構+演算法面試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 ... cb6835a63dc9_9.html)
     互聯網總是能給人帶來驚喜。前幾日,一位現居美國加州的名叫阿財的朋友發來一封郵件,並把他自己做的全部100題的答案一併發予給我,自此,便似遇見了知己。十分感謝。
     任何東西只有分享出來才更顯其價值。本只需貼出後面40題的答案,因為前60題的答案本人早已整理上傳至網上,但多一種思路多一種參考亦未嘗不可。特此,把阿財的答案再稍加整理番,然後把全部100題的答案現今都貼出來。若有任何問題,歡迎不吝指正。謝謝。
    上千上萬的人都關注過此100題,且大都都各自貢獻了自己的思路,或回復於微軟100題維護地址上,或回復於本博客內,人數眾多,無法一一標明,特此向他們諸位表示敬意和感謝。謝謝大家,諸君的努力足以影響整個互聯網,咱們已經迎來一個分享互利的新時代。
•        微軟面試100題全部答案
    更新:有朋友反應,以下的答案中思路過於簡略,還是這句話,一切以程式師程式設計藝術系列(多種思路,多種比較,細細讀之自曉其理)為准(我沒怎麼看阿財的這些答案,因為程式設計藝術系列已經說得足夠清晰了。之所以把阿財的這份答案分享出來,一者,程式設計藝術系列目前還只寫到了第二十二章,即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 = j;
    if (a < 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) 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. ★用一種演算法來顛倒一個連結表的順序。現在在不用遞迴式的情況下做一遍。
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] = 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;
  }
  return k;
}
★不用乘法或加法增加8 倍。現在用同樣的方法增加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>=s) i--;
  if (!helper(a, i+1, e-1))
    return 0;
  int k = l;
  while (a[e]<a && 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 題:
題目(微軟):
輸入一顆二元樹,從上往下按層列印樹的每個結點,同一層中按照從左往右的順序列印。
例如輸入
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) 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 = n % base;
   digit = (n % (base * 10)) - suffix;
   prefix = (n - suffix - digit*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 = a;
  for (i=1;i<n; i++) {
    acc = acc[i-1]+a;
  }
  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[j] 的值代表編號為i,j 的隊伍中更強的一支。
所以w[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+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, prefixHash, suffixHash);
    graph[0] = 0;
  }
  memset(inDegree, 0, sizeof(int)*n);
  for (i=0; i<n; i++) {
     for (j=0; j<n; j++) {
       if (suffixHash==prefixHash[j] && strncmp(strs+1, strs[j], m) == 0) {
         if (i==j) return 0; // there is a self loop, return false.
         graph[0] ++;
         graph[graph[i*n]] = j;
         inDegree[j] ++;
       }
     }
  }
  return longestPath(graph, n);
}
/**
* 1. do topological sort, record index 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 != 0) continue;
    memset(parent, -1, n*sizeof(int));
    memset(d, MAX_PATH, n*sizeof(int));
    d = 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]]!=0 && finished[graph[s]]==0) {
      return 0; //gray node, a back edge;
    }
    if (visited[graph[s]] == 0) {
      visited[graph[s]] = 1;
      dfs(graph, graph[s]);
    }   
  }
  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 as the lowest vertex that can be reached from i and i’s successor nodes. For each edge i, if low = 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[] is the out edges, g[0] is the edge count, g[1...g[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 == 0) {
      visited = ++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]] == 0) {
      out++;
      visited[g[s]] = ++cnt;
      int clow = dfs(g, cuts, n, g[s], root);
      if (clow < low) low = clow;
    } else {
      if (low > visit[g[s]]) {
        low = visit[g[s]];
      }
    }
  }
  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>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;
  for (m=n; m>=2; m--) {
    if (sum mod m != 0) continue;
    int aux[n]; for (i=0; i<n; i++) aux = 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 != 0) continue;
    aux = groupId;
    if (testShares(a, n, m, sum, groupsum, aux, goal-a, groupId)) {
      return 1;
    }
    aux = 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. set ds[j] = a, or append a at the end of ds
    int s=0, t=dsl-1;
    while (s<=t) {
      int m = s+(t-s)/2;
      if (ds[m] < a) {
        t = m - 1;
      } else {
        s = m + 1;
      }
    }
    // now s must be at the first ds[j]<a, or at the end of ds[]
    ds[s] = a;
    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 == ds[j]) { j --; }
    else if (a < ds[j]) { ds[j--] = a; }
  }  
  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) {
  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.二元樹的深度。
題目:輸入一棵二元樹的根結點,求該樹的深度。
從根結點到葉結點依次經過的結點(含根、葉結點)形成樹的一條路徑,最長路徑的長度為
樹的深度。
例如:輸入二元樹:
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, the position of i’th number, dpos the number in s is the dpos’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, dpos=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 = -d;
  }
}
int findFirstAvailable(char s[], byte d[], int pos[], int n) {
  for (int i=n-1; i>1; i--) {
    if (s[pos] > s[pos+d[pos]]) return pos;
  }  
  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 & 1)==0) i++;
  if (i==n) return;
  swap(a, i++, j++);
  while (i<n) {
    if ((a & 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 = 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.
返回列表