微软面试一百道题目.docx

第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 (aeai & i=s) i-; if (!helper(a, i+1, e-1) return 0; int k = l; while (ae=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, its 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=(n2+n)/2it is easy to get x/2, so the problem is to get n2though 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+=(Y 1;第13 题：题目：输入一个单向链表，输出该链表中倒数第k 个结点。链表的倒数第0 个结点为链表的尾指针。链表结点定义如下：struct ListNodeint 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;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 left), &(root-right); mirror(root-left); mirror(root-right);void mirrorIteratively(Node * root) if (root = NULL) return; stack 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 dont remember the function name of the stl queue, so I will write it in Java.void printByLevel(Node root) Node sentinel = new Node(); LinkedList q=new LinkedList(); 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”. Lets assume it as ASCII.char firstSingle(char * str) int a255; 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%n2) 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)%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 fn=0; for (int i=2; i1, _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+? Im 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 m) findCombination(m, m); int auxn; 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); auxidx = 1; helper(dest-idx-1, idx+1, aux, n); auxidx = 0;void dump(int aux, int n) for (int i=0; idatah2-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-datah2-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 所指的值为123456789ANSWER:int continumax(char *outputstr, char *inputstr) int len = 0; char * pstart = NULL; int max = 0; while (1) if (*inputstr = 0 & *inputstr max) pstart = inputstr-len; len = 0; if (*inputstr+=0) break; for (int i=0; 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 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 (n0) c+; n = n & (1= 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 序列。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) stack helper;int i1=0, i2=0;while (i2 n) while (stack.empty() | stack.peek() != popi2) if (i1n)stack.push(pushi1+);elsereturn 0;while (!stack.empty() & stack.peek() = popi2) 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 面试题。ANSWERThis is complicated. I hate it.Suppose we have N=ABCDEFG.if G1, # of 1s in the units digits is ABCDEF, else ABCDEF+1if F1, # of 1s in the digit of tens is (ABCDE)*10, else if F=1: (ABCDE)*10+G+1, else (ABCDE+1)*10if E1, # of 1s 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 its 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 prefix10, suffix10, digits10; /10 is enough for 32bit integers int i=0; int base = 1; while (base n) suffixi = n % base; digiti = (n % (base * 10) - suffixi; prefixi = (n - suffixi - digiti*base)/10; i+, base*=10; int count = 0; base = 1; for (int j=0; ji; j+) if (digitj 1) count += prefix; else if (digitj=1) count += prefix + suffix + 1; else count += prefix+base; 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(n2) 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 , 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.实现一个挺高级的字符匹配算法：给