福建网站建设公司排名,海南省建设信息官方网站,生活分类网站建设,设计欣赏心得体会微软等数据结构算法面试100题全部答案集锦作者#xff1a;July、阿财。时间#xff1a;二零一一年十月十三日。引言无私分享造就开源的辉煌。今是二零一一年十月十三日#xff0c;明日14日即是本人刚好开博一周年。在一周年之际#xff0c;特此分享出微软面试全部100题答案…微软等数据结构算法面试100题全部答案集锦作者July、阿财。时间二零一一年十月十三日。引言 无私分享造就开源的辉煌。 今是二零一一年十月十三日明日14日即是本人刚好开博一周年。在一周年之际特此分享出微软面试全部100题答案的完整版以作为对本博客所有读者的回馈。 一年之前的10月14日一个名叫July 头像为手冢国光的人在一个叫csdn的论坛上开帖分享微软等公司数据结构算法面试100题自此与上千网友一起做一起思考一起解答这些面试题目最终成就了一个名为结构之法算法之道的编程面试与算法研究并重的博客如今此博客影响力逐步渗透到海外及至到整个互联网。 在此之前由于本人笨拙这微软面试100题的答案只整理到了前60题第1-60题答案可到本人资源下载处下载http://v_july_v.download.csdn.net/故此常有朋友留言或来信询问后面40题的答案。只是因个人认为一、答案只是作为一个参考不可太过依赖二、常常因一些事情耽搁如在整理最新的今年九月、十月份的面试题九月腾讯创新工场淘宝等公司最新面试十三题、十月百度阿里巴巴迅雷搜狗最新面试十一题三、个人正在针对那100题一题一题的写文章多种思路不断优化即成程序员编程艺术系列。自此后面40题的答案迟迟未得整理。且个人已经整理的前60题的答案在我看来是有诸多问题与弊端的甚至很多答案都是错误的。 互联网总是能给人带来惊喜。前几日一位现居美国加州的名叫阿财的朋友发来一封邮件并把他自己做的全部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.aspx1.把二元查找树转变成排序的双向链表题目输入一棵二元查找树将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点只调整指针的指向。10/ \6 14/ \ / \4 8 12 16转换成双向链表46810121416。首先我们定义的二元查找树节点的数据结构如下struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *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_pRightrh; 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.top0?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 (size0) 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 nodeBinaryTreeNode *m_pLeft; // left child of nodeBinaryTreeNode *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-rightNULL) { 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 个。例如输入1234567 和8 这8 个数字则最小的4 个数字为123 和4。ANSWER:This is a very traditional question...O(nlogn): cat I_FILE | sort -n | head -n KO(kn): do insertion sort until k elements are retrieved.O(nklogn): 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 upvoid siftup(int a[], int i, int n) { while (i0) { int j(i10 ? i-1 : i1); int p(i-1)1; if (jn 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*i1n){ int l2*i1; if (l1n a[l1] a[l]) l; if (a[l] a[i]) swap(a, i, l); il; }}第6 题腾讯面试题给你10 分钟时间根据上排给出十个数在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下【0123456789】举一个例子数值: 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00 在下排出现了6 次1 在下排出现了2 次2 在下排出现了1 次3 在下排出现了0 次....以此类推..ANSWER:I don’t like brain teasers. Will skip most of them...第7 题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针比如h1h2判断这俩个链表是否相交。为了简化问题我们假设俩个链表均不带环。问题扩展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 cycleint isJoined(Node *h1, Node * h2) { Node* cylic1 testCylic(h1); Node* cylic2 testCylic(h2); if (cylic1cylic20) return isJoinedSimple(h1, h2); if (cylic10 cylic2!0 || cylic1!0 cylic20) return 0; Node *p cylic1; while (1) { if (pcylic2 || p-next cylic2) return 1; pp-next-next; cylic1 cylic1-next; if (pcylic1) 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:124;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, ptn1)) return 1; } while (*str ! ‘\0’); return 0; } if (*str ‘\0’) return 0; if (*str *ptn || *ptn ‘?’) { return match(str1, ptn1); } return 0;}★颠倒一个字符串。优化速度。优化空间。void reverse(char *str) { reverseFixlen(str, strlen(str));}void reverseFixlen(char *str, int n) { char* p strn-1; while (str p) { char c *str; *str *p; *pc; } }★颠倒一个句子中的词的顺序比如将“我叫克丽丝”转换为“克丽丝叫我”实现速度最快移动最少。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, len1); for (i0; ilen; i) { aux[sub[i]] len - i; } int n strlen(str); ilen-1; while (in) { int ji, klen-1; while (k0 str[j--] sub[k--]) ; if (k0) return j1; if (i1n) iaux[str[i1]]; 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 127int 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 i0; while (*p ! ‘\0’) { if (ilen) hash HBASE * dest (int)(*p); else hash (hash - (TO_REDUCE * (int)(*(p-len))))*HBASE (int)(*p); if (hash dest ilen strncmp(sub, p-len1, 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 i1; i1000;i) k ~ a[i]~i; } return k;}★不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。ANSWER:n3;(n3)-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 (es) return 1; int ie-1; while (a[e]a[i] is) i--; if (!helper(a, i1, e-1)) return 0; int k l; while (a[e]a[i] is) 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, ldrd));}第12 题题目求12…n要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句A?B:C。ANSWER:1..nn*(n1)/2(n^2n)/2it is easy to get x/2, so the problem is to get n^2though 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 (1i)) X(Yi)int foo(int n){ int rn; 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 (k0) error(“k 0”); Node *phead, *pkhead; for (;k0;k--) { if (pk-next!NULL) pk pk-next; else return NULL; } while (pk-next!NULL) { pp-next, pkpk-next; } return p;}第14 题题目输入一个已经按升序排序过的数组和一个数字在数组中查找两个数使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字输出任意一对即可。例如输入数组1、2、4、7、11、15 和数字15。由于41115因此输出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, *ean-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 nodeBSTreeNode *m_pLeft; // left child of nodeBSTreeNode *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; stackNode* 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 题题目微软输入一颗二元树从上往下按层打印树的每个结点同一层中按照从左往右的顺序打印。例如输入78/ \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(); LinkedListNode qnew LinkedListNode(); q.addFirst(root); q.addFirst(sentinel); while (!q.isEmpty()) { Node n q.removeLast(); if (nsentinel) { 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 *pstr; 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%n2) after the first round, we start from k1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k1)th element instead of 0, so the answer is (f(n-1, m)k1)%n3) 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 fn0; for (int i2; in; i) { fn (fnm)%i; } return fn;}hu...长出一口气。。。第19 题题目定义Fibonacci 数列如下/ 0 n0f(n) 1 n1\ f(n-1)f(n-2) n2输入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 (n1) { memcpy(A, _r, 4*sizeof(int)); return; } int tmp[4]; power(A, n1, _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 (*p0 *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从数列123.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来.ANSWERThis is a combination generation problem. void findCombination(int n, int m) { if (nm) 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 || idxn) return; helper(dest, idx1, aux, n); aux[idx] 1; helper(dest-idx-1, idx1, aux, n); aux[idx] 0;}void dump(int aux[], int n) { for (int i0; in; i) if (aux[i]) printf(“%3d”, i1); 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 是怎么知道的。如果用程序又怎么实现呢ANSWERI 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, *.*)ANSWERCrap... I totally cannot understand this problem... Does the *.* represent any possible number?第24 题链表操作1.单链表就地逆置2合并链表ANSWERReversing 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-datah2-data) { head h2; h2h2-next; } else { head h1; h1h1-next; } Node * current head; while (h1 ! NULL h2 ! NULL) { if (h1 NULL || (h2!NULL h1-datah2-data)) { current-next h2; h2h2-next; current current-next; } else { current-next h1; h1h1-next; current current-next; } } current-next NULL; return head;}第25 题写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)功能在字符串中找出连续最长的数字串并把这个串的长度返回并把这个最长数字串付给其中一个函数参数outputstr 所指内存。例如abcd12345ed125ss123456789的首地址传给intputstr 后函数将返回9outputstr 所指的值为123456789ANSWER: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 i0; ilen; i) *outputstr pstart; *outputstr ‘\0’; return max;}26.左旋转字符串题目定义字符串的左旋转操作把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n 的字符串操作的复杂度为O(n)辅助内存为O(1)。ANSWERHave done it. Using reverse word function above.27.跳台阶问题题目一个台阶总共有n 级如果一次可以跳1 级也可以跳2 级。求总共有多少总跳法并分析算法的时间复杂度。这道题最近经常出现包括MicroStrategy 等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。ANSWERf(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。分析这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。ANSWERTraditional question. Use the equation xxxxxx10000 (xxxxxx10000-1) xxxxxx00000Note: for negative numbers, this also hold, even with 100000000 where the “-1” leading to an underflow.int countOf1(int n) { int c0; while (n!0) { nn (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 (n0) { c; n n (1(sizeof(int)*8-1)); } while (n!0) { ctab[n0xff]; 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 1push 2push 3push 4poppush 5poppoppoppop这样得到的pop 序列就是4、5、3、2、1。但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。ANSWERThis 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) { stackint helper; int i10, i20; while (i2 n) { while (stack.empty() || stack.peek() ! pop[i2]) if (i1n) 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 的数字有11011 和121 一共出现了5 次。分析这是一道广为流传的google 面试题。ANSWERThis is complicated... I hate it...Suppose we have NABCDEFG.if G1, # of 1’s in the units digits is ABCDEF, else ABCDEF1if F1, # of 1’s in the digit of tens is (ABCDE)*10, else if F1: (ABCDE)*10G1, else (ABCDE1)*10if E1, # of 1’s in 3rd digit is (ABCD)*100, else if E1: (ABCD)*100FG1, else (ABCD1)*100… so on.if A1, # of 1 in this digit is BCDEFG1, 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 i0; 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 j0; ji; j) { if (digit[j] 1) count prefix; else if (digit[j]1) count prefix suffix 1; else count prefixbase; base * 10; } return count;}31.华为面试题一类似于蜂窝的结构的图进行搜索最短路径要求5 分钟ANSWERNot clear problem. Skipped. Seems a Dijkstra could do.int dij32.有两个序列a,b大小都为n,序列元素的值任意整数无序要求通过交换a,b 中的元素使[序列a 元素的和]与[序列b 元素的和]之间的差最小。例如:var a[100,99,98,1,2, 3];var b[1, 2, 3, 4,5,40];ANSWERIf 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.实现一个挺高级的字符匹配算法给一串很长字符串要求找到符合要求的字符串例如目的串1231******3***2 ,12*****3 这些都要找出来其实就是类似一些和谐系统。。。。。ANSWERNot a clear problem. Seems a bitset can do.34.实现一个队列。队列的应用场景为一个生产者线程将int 类型的数入列一个消费者线程将int 类型的数出列ANSWERI don’t know multithread programming at all....35.求一个矩阵中最大的二维矩阵(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)写出算法;(2)分析时间复杂度;(3)用C 写出关键代码ANSWERThis 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, (0ijn) 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 (i0,n-1) first, then calcuate the result by acc(i, j) acc(0, j)-acc(0,i-1)//acc[i*nj] acc(i,j)void accumulate(int a[], int n, int acc[]) { int i0; acc[i] a[i]; for (i1;in; i) { acc[i] acc[i-1]a[i]; } for (i1; in; i) { for (ji; jn; j) { acc[i*nj] acc[j] - acc[i-1]; } }}第36 题-40 题有些题目搜集于CSDN 上的网友已标明36.引用自网友longzuo谷歌笔试n 支队伍比赛分别编号为012。。。。n-1已知它们之间的实力对比关系存储在一个二维数组w[n][n]中w[i][j] 的值代表编号为ij 的队伍中更强的一支。所以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。ANSWERThis 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/2k1 to 02...2k, 1,3,...2k1...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 (round1) { int i,j; for (i0,j0; iround; i2) { int win (iround-1) ? i : w[i][i1]; swap(result, j, win); j; } }}37.有n 个长为m1 的字符串如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配则两个字符串可以联接问这n 个字符串最多可以连成一个多长的字符串如果出现循环则返回错误。ANSWERThis 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 201int 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 (i0; in; i) { calcHash(strs[i], prefixHash[i], suffixHash[i]); graph[i][0] 0; } memset(inDegree, 0, sizeof(int)*n); for (i0; in; i) { for (j0; jn; j) { if (suffixHash[i]prefixHash[j] strncmp(strs[i]1, strs[j], m) 0) { if (ij) 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 i0; in; i) { if (inDegree[i] ! 0) continue; memset(parent, -1, n*sizeof(int)); memset(d, MAX_PATH, n*sizeof(int)); d[i] 0; for (int j0; jn; j) { for (int k1; kgraph[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 i0; in; i) { if (topdfs(graph, i) 0) return 0; } return 1;}int topdfs(int graph[], int s) { if (visited[s] ! 0) return 1; for (int i1; igraph[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(VE)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*nn*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:x1, y3: if ab, c is the lighter, else the lighter is the lighter...do this recursively. so y3^x;2.有一个很大很大的输入流大到没有存储器可以将其存储下来而且只输入一次如何从这个输入流中随机取得m 个记录。ANSWERThat is, keep total number count N. If Nm, just keep it.For Nm, generate a random number Rrand(N) in [0, N), replace a[R] with new number if R falls in [0, m).3.大量的URL 字符串如何从中去除重复的优化时间空间复杂度ANSWER1. 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优化时间空间复杂度。ANSWERHave done this.(2).求一个有向连通图的割点割点的定义是如果除去此节点和与其相关的边有向图不再连通描述算法。ANSWERDo 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 i0; in; 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 i1; ig[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.百度研发笔试题引用自zp1553348771)设计一个栈结构满足一下条件minpushpop 操作的时间复杂度为O(1)。ANSWERHave done this.2)一串首尾相连的珠子(m 个)有N 种颜色(N10)设计一个算法取出其中一段要求包含所有N 中颜色并使长度最短。并分析时间复杂度与空间复杂度。ANSWERUse 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 h0, t0; int minn; while (1) { while (ctr 0 hn) { if (c[a[h]] 0) ctr --; c[a[h]] ; h; } if (hn) 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 个词搭配当用户输入中国人民的时候要求返回与这个搭配词组相关的信息。ANSWERThis problem can be solved in three steps:1. identify the words2. recognize the phrase3. retrieve the informationSolution 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-stations 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.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成晶元并不一定全布满晶元盘照相机每次这能匹配一个晶元如匹配过则拾取该晶元若匹配不过照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。ANSWERDont understand.42.请修改append 函数利用这个函数实现两个非降序链表的并集1-2-3 和2-3-5 并为1-2-3-5另外只能输出结果不能修改两个链表的数据。ANSWERI 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 (h1NULL) return h2; if (h2NULL) return h1; Node * head; if (h1-data h2-data) { head h1; h1h1-next; } else { head h2; h2h2-next; } Node * p head; while (h1!NULL || h2!NULL) { Node * candi; if (h1!NULL h2 ! NULL h1-data h2-data || h2NULL) { candi h1; h1h1-next; } else { candi h2; h2h2-next; } } if (candi-data p-data) delete(candi); else { p-next candi; pcandi; } } return head;}43.递归和非递归俩种方法实现二叉树的前序遍历。ANSWERvoid 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) { stackTreeNode * 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) { stackTreeNode * 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 stackTreeNode * 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.设计一个魔方六面的程序。ANSWERThis is a problem to test OOP.The object MagicCube must have following features1) holds current status2) easily doing transform3) judge whether the final status is achieved4) to test, it can be initialized5) output current statuspublic 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 条。ANSWER10M 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。面试官不解释何为相似ANSWERWhat 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.对于一个整数矩阵存在一种运算对矩阵中任意元素加一时需要其相邻上下左右某一个元素也加一现给出一正数矩阵判断其是否能够由一个全零矩阵经过上述运算得到。ANSWERA 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 的最大值比如{32436} 可以分成{32436} m1;{3,6}{2,4,3} m2{3,3}{2,4}{6} m3 所以m 的最大值为3ANSWERTwo restrictions on m, 1) 1 m n; 2) Sum(array) mod m 0NOTE: 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 (i0; in; i) sum a[i]; for (mn; m2; m--) { if (sum mod m ! 0) continue; int aux[n]; for (i0; in; 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 m1) return 1; } for (int i0; in; 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.创新工场求一个数组的最长递减子序列比如{94325432}的最长递减子序列为{95432}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 i0; ia.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 s0, tdsl-1; while (st) { 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 ilastdsl-1, jdsl-1; i0 j 0; i--) { if (a[i] ds[j]) { j --; } else if (a[i] ds[j]) { ds[j--] a[i]; } } return Arrays.copyOfRange(ds, 0, dsl1);}48.微软一个数组是由一个递减数列左移若干位形成的比如{432165}是由{654321}左移两位形成的在这种数组中查找某一个数。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 (st) 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, m1, 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由于123454567815所以输出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 ni(i1)...(j-1)j, then n (ij)(j-i1)/2 (j*j - i*i i j)/2 j^2 j (i-i^2-2n) 0 jsqrt(i^2-i1/42n) - 1/2We know 1 i j n/2 1So 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 i1; in/2; i) { int sqroot calcSqrt(4*i*i8*n-4*i1); 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 nodeSBinaryTreeNode *m_pLeft; // left child of nodeSBinaryTreeNode *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 (n20) { 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 i0; in; 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, rd[r]); for (int in-1; idpos[r]; i--) d[i] -d[i]; }}int findFirstAvailable(char s[], byte d[], int pos[], int n) { for (int in-1; i1; i--) { if (s[pos[i]] s[pos[i]d[pos[i]]]) return pos[i]; } return -1;}#define aswap(ARR, X, Y) {int tARR[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 ij0; while (i n (a[i] 1)0) i; if (in) return; swap(a, i, j); while (in) { 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;};请实现其赋值运算符的重载函数要求异常安全即当对一个对象进行赋值时发生异常对象的状态不能改变。ANSWERPass... 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, l2strlen(p2)1; int a[l1*l2]; for (int i0; il1; i) a[i*l2] 0; for (int i0; il2; i) a[i] 0; for (int i1; il1; i) { for (int j1; jl2; j) { int max MAX(a[(i-1)*l2l1], a[i*l2l1-1]); if (p1[i-1] p2[j-1]) { max (max 1 a[(i-1)*l2j-1]) ? max : 1a[(i-1)*l2j-1]; } } } return a[l1*l2-1];}57.用俩个栈实现队列。题目某队列的声明如下templatetypename T class CQueue{public:CQueue() {}~CQueue() {}void appendTail(const T node); // append a element to tailvoid deleteHead(); // remove a element from headprivate:StackT m_stack1;StackT m_stack2;};分析从上面的类的声明中我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了栈是一种后入先出的数据容器因此对队列进行的插入和删除操作都是在栈顶上进行队列是一种先入先出的数据容器我们总是把新元素插入到队列的尾部而从队列的头部删除元素。ANSWERTraditional 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;};分析这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。ANSWERHave 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.在O1时间内删除链表结点。题目给定链表的头指针和一个结点指针在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 i1; i1500; i) { int s heap[0]; heap[0] s*2; siftDown(heap, 0, size); heap[size] s*3; siftUp(heap, size, size1); heap[size1] s*5; siftUp(heap, size1, size2); size2; }}void siftDown(int heap[], int from, int size) { int c from * 2 1; while (c size) { if (c1size heap[c1] heap[c]) c; if (heap[c] heap[from]) swap(heap, c, from); from c; cfrom*21; }}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 为1J 为11Q 为12K 为13而大小王可以看成任意数字。ANSWER:// make king 0boolean 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 is; while (ie) { allowGaps - a[i1] - 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 nS6n, 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 x1 or x6, f(m, n)0 where mn Can do it in DP.void listAllProbabilities(int n) { int[][] f new int[6*n1][]; for (int i0; i6*n; i) { f[i] new int[n1]; } for (int i1; i6; i) { f[i][1] 1; } for (int i1; in; i) { f[i][i] 1; } for (int i2; in; i) { for (int ji1; j6*i; j) { for (int k(j-6i-1)?i-1:j-6; kj-1; k) f[j][i] f[k][i-1]; } } double p6 Math.power(6, n); for (int in; i6*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 i0; ia.length; a) aux[i] a[i]; Arrays.sort(aux, new ComparatorInteger(){ int compareTo(Integer i1, Integer i2) { return (“”i1i2).compare(“”i2i1); } }); StringBuffer sb new StringBuffer(); for (int i0; iaux.length, i) { sb.append(aux[i]); } return sb.toString();}69.旋转数组中的最小元素。题目把一个数组最开始的若干个元素搬到数组的末尾我们称之为数组的旋转。输入一个排好序的数组的一个旋转输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转该数组的最小值为1。分析这道题最直观的解法并不难。从头到尾遍历数组一次就能找出最小的元素时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性我们应该能找到更好的解法。ANSWERThis 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, m1, 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 模式的类型。ANSWERI’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。分析可能很多人都写过判断一个字符串是不是对称的函数这个题目可以看成是该函数的加强版。ANSWERBuild 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 在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题除了较好的编程能力之外还需要较快的反应和较强的逻辑思维能力。ANSWERDelete every two different digits. The last one that left is the one.int getMajor(int a[], int n) { int x, cnt0; for (int i0; in; 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;};输入二叉树中的两个结点输出这两个结点在数中最低的共同父结点。分析求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。ANSWERHave 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)以复制一个复杂链表。分析在常见的数据结构上稍加变化这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目我们需要较快的反应能力对数据结构透彻的理解以及扎实的编程功底。ANSWERHave 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 必然会在某个时刻相遇(p1p2)从而检测到链表中有环。2.给定两个单链表(head1, head2)检测两个链表是否有交点如果有返回第一个交点。如果head1head2那么显然相交直接返回head1。否则分别从head1,head2 开始遍历两个链表获得其长度len1 与len2假设len1len2那么指针p1 由head1 开始向后移动len1-len2 步指针p2head2下面p1、p2 每次向后前进一步并比较p1p2 是否相等如果相等即返回该结点否则说明两个链表没有交点。3.给定单链表(head)如果有环的话请返回从头结点进入环的第一个节点。运用题一我们可以检查链表中是否有环。如果有环那么p1p2 重合点p 必然在环中。从p 点断开环方法为p1p, p2p-next, p-nextNULL。此时原单链表可以看作两条单链表一条从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.链表和数组的区别在哪里分析主要在基本概念上的理解。但是最好能考虑的全面一点现在公司招人的竞争可能就在细节上产生谁比较仔细谁获胜的机会就大。ANSWER1. 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.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法ANSWERFor 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 i0; ilen/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-datap2-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 (p1NULL) ? p2 : p1; return ph;} 2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法ANSWERActually, 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()函数功能的代码。ANSWERSubstring test? Have done this.80.阿里巴巴一道笔试题问题描述:12 个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?这个笔试题,很YD,因为把某个递归关系隐藏得很深。ANSWERMust 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) 72081.第1 组百度面试题1.一个int 数组里面数据无任何限制要求求出所有这样的数a[i]其左边的数都小于等于它右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。ANSWERSort the array to another array, compare it with the original array, all a[i] b[i] are answers.2.一个文件内含一千万行字符串每个字符串在1K 以内要求找出所有相反的串对如abc 和cba。ANSWERSo 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 用什么实现的为什么不用hashANSWERI 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 中的属性信息单个属性如age20 等查询出集合A 中对应的name。ANSWERSQL? Not a good defined question.2.给出一个文件里面包含两个字段{url、size}即url 为网址size 为对应网址访问的次数要求问题1、利用Linux Shell 命令或自己设计算法查询出url 字符串中包含“baidu”子字符串对应的size 字段值问题2、根据问题1 的查询结果对其按照size 由大到小的排列。说明url 数据量很大100 亿级以上ANSWER1. shell: gawk ‘ /baidu/ { print $2 } ’ FILE2. shell: gawk ‘ /baidu/ {print $2}’ FILE | sort -n -r 83.第3 组百度面试题1.今年百度的一道题目百度笔试给定一个存放整数的数组重新排列数组使得数组左边为奇数右边为偶数。要求空间复杂度O(1)时间复杂度为On。ANSWERHave 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 dovoid * memmove(void * dest, const void * src, size_t n) { if (destNULL || src NULL) error(“NULL pointers”); byte * psrc (byte*)src; byte * pdest (byte*)dest; int step 1; if (dest src n) { psrc (byte*)(srcn-1); pdest (byte*)(destn-1); step -1; } for (int i0; in; i) { pdest psrc; pdest step; psrc step; }}84.第4 组百度面试题2010 年3 道百度面试题[相信你懂其中的含金量]1.a~z 包括大小写与0~9 组成的N 个数, 用最快的方式把其中重复的元素挑出来。ANSWERBy 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要求复杂度最低。ANSWERRun 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 的频度排序.ANSWERIf 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 的前几个字节重叠。分析记住这种题目往往就是考你对边界的考虑情况。ANSWERSpecial case of memmove. 2.已知一个字符串比如asderwsde,寻找其中的一个子字符串比如sde 的个数如果没有返回0有的话返回子字符串的个数。ANSWERANSWERint 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.怎样编写一个程序把一个有序整数数组放到二叉树中分析:本题考察二叉搜索树的建树方法简单的递归结构。关于树的算法设计一定要联想到递归因为树本身就是递归的定义。而学会把递归改称非递归也是一种必要的技术。毕竟递归会造成栈溢出关于系统底层的程序中不到非不得以最好不要用。但是对某些数学问题就一定要学会用递归去解决。ANSWERThis 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, m1, end); return root;}87.1.大整数数相乘的问题。这是2002 年在一考研班上遇到的算法题ANSWERDo overflow manually. final static long mask (1 31) - 1;ArrayListInteger multiply(ArrayList Integer a, ArrayListInteger b) { ArrayListInteger result new ArrayListInteger(a.size()*b.size()1); for (int i0; ia.size(); i) { multiply(b, a.get(i), i, result); } return result;}void multiply(ArrayListInteger x, int a, int base, ArrayListInteger result) { if (a 0) return; long overflow 0; int i; for (i0; ix.size(); i) { long tmp x.get(i) * a result.get(basei) overflow; result.set(basei, (int)(mask tmp)); overflow (tmp 31); } while (overflow ! 0) { long tmp result.get(basei) overflow; result.set(basei, (int) (mask tmp)); overflow (tmp 31); }}2.求最大连续递增数字串如“ads3sl456789DF3456ld345AA”中的“456789”ANSWERHave done this.3.实现strstr 功能即在父串中寻找子串首次出现的位置。笔试中常让面试者实现标准库中的一些函数ANSWERHave done this.88.2005 年11 月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符*移到串的前部分前面的非*字符后移但不能改变非*字符的先后顺序函数返回串中字符*的数量。如原始串为ab**cd**e*12处理后为*****abcde12函数并返回值为5。要求使用尽量少的时间和辅助空间ANSWERIt’s like partition in quick sort. Just keep the non-* part stable.int partitionStar(char a[]) { int count 0; int i a.length-1, ja.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 日华为软件研发笔试题。实现一单链表的逆转。ANSWERHave done this.2.编码实现字符串转整型的函数实现函数atoi 的功能据说是神州数码笔试题。如将字符串”123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0ANSWERint atoi(const char * a) { if (*a’’) return atoi(a1); else if (*a’-’) return - atoi(a1); char *p a; int c 0; while (*p ‘0’ *p ‘9’) { c c*10 (*p - ‘0’); } return c;}3.快速排序东软喜欢考类似的算法填空题又如堆排序的算法等ANSWERStandard solution. Skip.4.删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。下面的算法只需要一次遍历不需要开辟新空间时间复杂度为O(N)ANSWERAlso 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。ANSWERUse 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.不开辟用于交换数据的临时空间如何完成字符串的逆序(在技术一轮面试中有些面试官会这样问)。ANSWERTwo cursors.2.删除串中指定的字符做此题时千万不要开辟新空间否则面试官可能认为你不适合做嵌入式开发ANSWERHave done this.3.判断单链表中是否存在环。ANSWERHave done this.911.一道著名的毒酒问题有1000 桶酒其中1 桶有毒。而一旦吃了毒性会在1 周后发作。现在我们用小老鼠做实验要在1 周内找出那桶毒酒问最少需要多少老鼠。ANSWERHave done this. 10 mices.2.有趣的石头问题有一堆1 万个石头和1 万个木头对于每个石头都有1 个木头和它重量一样把配对的石头和木头找出来。ANSWERQuick sort.92.1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的), 那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176, 178, 180, 170, 171这些捣乱分子对为176, 170, 176, 171, 178, 170, 178, 171, 180, 170, 180, 171,那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)要求输入:为一个文件(in)文件的每一行为一个序列。序列全为数字数字间用”,”分隔。输出为一个文件(out)每行为一个数字表示捣乱分子的对数。详细说明自己的解题思路说明自己实现的一些关键点。并给出实现的代码并分析时间复杂度。限制输入每行的最大数字个数为100000 个数字最长为6 位。程序无内存使用限制。ANSWERThe 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]找出即可。给出这个解答后面试官有要求只能用一个辅助数组且要求少遍历一次。ANSWERIt 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]要求时间复杂度空间复杂度尽量小ANSWERFirstly 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 判断一字符串是不是对称的如abccbaANSWERTwo cursors.2.用递归的方法判断整数组a[N]是不是升序排列ANSWERboolean isAscending(int a[]) { return isAscending(a, 0);}boolean isAscending(int a[], int start) { return start a.length - 1 || isAscending(a, start1);}96.08 年中兴校园招聘笔试题1编写strcpy 函数已知strcpy 函数的原型是char *strcpy(char *strDest, const char *strSrc);其中strDest 是目的字符串strSrc 是源字符串。不调用C/C 的字符串库函数请编写函数strcpyANSWERchar *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.编写反转字符串的程序要求优化速度、优化空间。ANSWERHave done this.2.在链表里如何发现循环链接ANSWERHave done this.3.编写反转字符串的程序要求优化速度、优化空间。ANSWERHave done this.4.给出洗牌的一个算法并将洗好的牌存储在一个整形数组里。ANSWERHave done this.5.写一个函数检查字符是否是整数如果是返回其整数值。或者怎样只用4 行代码编写出一个从字符串到长整形的函数ANSWERChar or string?have done atoi;98.第2 组微软面试题1.给出一个函数来输出一个字符串的所有排列。ANSWERHave done this...2.请编写实现malloc()内存分配函数功能一样的代码。ANSWERWay too hard as an interview question... Please check wikipedia for solutions... 3.给出一个函数来复制两个字符串A 和B。字符串A 的后几个字节和字符串B 的前几个字节重叠。ANSWERCopy from tail to head.4.怎样编写一个程序把一个有序整数数组放到二叉树中ANSWERHave done this.5.怎样从顶部开始逐层打印二叉树结点数据请编程。ANSWERHave done this...6.怎样把一个链表掉个顺序也就是反序注意链表的边界条件并考虑空链表ANSWERHave done this...99.第3 组微软面试题1.烧一根不均匀的绳从头烧到尾总共需要1 个小时。现在有若干条材质相同的绳子问如何用烧绳的方法来计时一个小时十五分钟呢ANSWERMay have done this... burn from both side gives ½ hour. 2.你有一桶果冻其中有黄色、绿色、红色三种闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻5 秒-1 分钟ANSWER4.3.如果你有无穷多的水一个3 公升的提捅一个5 公升的提捅两只提捅形状上下都不均匀问你如何才能准确称出4 公升的水40 秒-3 分钟ANSWER5 to 3 22 to 3, remaining 15 to remaining 1 4一个岔路口分别通向诚实国和说谎国。来了两个人已知一个是诚实国的另一个是说谎国的。诚实国永远说实话说谎国永远说谎话。现在你要去说谎国但不知道应该走哪条路需要问这两个人。请问应该怎么问20 秒-2 分钟ANSWERSeems 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 小时ANSWERToo 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。 欢迎任何人就以上任何内容题目与答案思路或其它任何问题、与我联系。本人邮箱zhoulei0907yahoo.cn。 更新本微软公司面试100题的全部答案日前已经上传资源所有读者可到此处下载http://download.csdn.net/detail/v_JULY_v/3685306。2011.10.15。作者声明:本人July 对以上所有任何内容和资料享有版权转载请注明作者本人July 及出处。向你的厚道致敬。谢谢。二零一一年十月十三日、以诸君为傲。转载于:https://www.cnblogs.com/v-July-v/archive/2011/10/13/2214114.html
