面试_微软面试100题全部答案

给你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

int n = strlen(str); i=len-1; while (i

while (k>=0 && str[j--] == sub[k--]) ;

if (k<0) return j+1; if (i+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++

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];