微软等数据结构+算法面试100题全部答案集锦【上】@慕课网原创_慕课网

更新：有朋友反应，以下的答案中思路过于简略，还是这句话，一切以程序员编程艺术系列（多种思路，多种比较，细细读之自晓其理）为准（我没怎么看阿财的这些答案，因为编程艺术系列已经说得足够清晰了。之所以把阿财的这份答案分享出来，一者，编程艺术系列目前还只写到了第二十二章，即100题之中还只详细阐述了近30道题；二者，他给的答案全部是用英文写的，这恰好方便国外的一些朋友参考；三者是为了给那一些急功近利的、浮躁的人一份速成的答案罢了）。

1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode m_pLeft; // left child of node
BSTreeNode m_pRight; // right child of node
};
ANSWER:
This is a traditional problem that can be solved using recursion.
For each node, connect the double linked lists created from left and right child node to form a full list.

/**

@param root The root node of the tree
@return The head node of the converted list.
/
BSTreeNode treeToLinkedList(BSTreeNode root) {
BSTreeNode head, * tail;
helper(head, tail, root);
return head;
}

void helper(BSTreeNode & head, BSTreeNode & tail, BSTreeNode root) {
BSTreeNode lt, *rh;
if (root == NULL) {
head = NULL, tail = NULL;
return;
}
helper(head, lt, root->m_pLeft);
helper(rh, tail, root->m_pRight);
if (lt!=NULL) {
lt->m_pRight = root;
root->m_pLeft = lt;
} else {
head = root;
}
if (rh!=NULL) {
root->m_pRight=rh;
rh->m_pLeft = root;
} else {
tail = root;
}
}

2.设计包含min 函数的栈。
定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。
要求函数min、push 以及pop 的时间复杂度都是O(1)。
ANSWER:
Stack is a LIFO data structure. When some element is popped from the stack, the status will recover to the original status as before that element was pushed. So we can recover the minimum element, too.

struct MinStackElement {
int data;
int min;
};

struct MinStack {
MinStackElement * data;
int size;
int top;
}

MinStack MinStackInit(int maxSize) {
MinStack stack;
stack.size = maxSize;
stack.data = (MinStackElement) malloc(sizeof(MinStackElement)maxSize);
stack.top = 0;
return stack;
}
void MinStackFree(MinStack stack) {
free(stack.data);
}
void MinStackPush(MinStack stack, int d) {
if (stack.top == stack.size) error(“out of stack space.”);
MinStackElement* p = stack.data[stack.top];
p->data = d;
p->min = (stack.top==0?d : stack.data[top-1]);
if (p->min > d) p->min = d;
top ++;
}
int MinStackPop(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[--stack.top].data;
}
int MinStackMin(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[stack.top-1].min;
}

3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
ANSWER:
A traditional greedy approach.
Keep current sum, slide from left to right, when sum < 0, reset sum to 0.

int maxSubarray(int a[], int size) {
if (size<=0) error(“error array size”);
int sum = 0;
int max = - (1 << 31);
int cur = 0;
while (cur < size) {
sum += a[cur++];
if (sum > max) {
max = sum;
} else if (sum < 0) {
sum = 0;
}
}
return max;
}

4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22 和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12 和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode m_pLeft; // left child of node
BinaryTreeNode m_pRight; // right child of node
};
ANSWER:
Use backtracking and recurison. We need a stack to help backtracking the path.
struct TreeNode {
int data;
TreeNode left;
TreeNode right;
};

void printPaths(TreeNode * root, int sum) {
int path[MAX_HEIGHT];
helper(root, sum, path, 0);
}

void helper(TreeNode * root, int sum, int path[], int top) {
path[top++] = root.data;
sum -= root.data;
if (root->left == NULL && root->right==NULL) {
if (sum == 0) printPath(path, top);
} else {
if (root->left != NULL) helper(root->left, sum, path, top);
if (root->right!=NULL) helper(root->right, sum, path, top);
}
top --;
sum += root.data; //....
}

5.查找最小的k 个元素
题目：输入n 个整数，输出其中最小的k 个。
例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。
ANSWER:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes...
Only gives the siftup and siftdown function.

/*
@param i the index of the element in heap a[0...n-1] to be sifted up
void siftup(int a[], int i, int n) {
while (i>0) {
int j=(i&1==0 ? i-1 : i+1);
int p=(i-1)>>1;
if (j<n && a[j]<a[i]) i = j;
if (a[i] < a[p]) swap(a, i, p);
i = p;
}
}
void siftdown(int a[], int i, int n) {
while (2i+1<n){
int l=2i+1;
if (l+1<n && a[l+1] < a[l]) l++;
if (a[l] < a[i]) swap(a, i, l);
i=l;
}
}

第6 题
腾讯面试题：
给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出现了6 次，1 在下排出现了2 次，
2 在下排出现了1 次，3 在下排出现了0 次....
以此类推..
ANSWER:
I don’t like brain teasers. Will skip most of them...

第7 题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
ANSWER:
struct Node {
int data;
int Node next;
};
// if there is no cycle.
int isJoinedSimple(Node h1, Node * h2) {
while (h1->next != NULL) {
h1 = h1->next;
}
while (h2->next != NULL) {
h2 = h2-> next;
}
return h1 == h2;
}

// if there could exist cycle
int isJoined(Node h1, Node h2) {
Node cylic1 = testCylic(h1);
Node cylic2 = testCylic(h2);
if (cylic1+cylic2==0) return isJoinedSimple(h1, h2);
if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0;
Node *p = cylic1;
while (1) {
if (p==cylic2 || p->next == cylic2) return 1;
p=p->next->next;
cylic1 = cylic1->next;
if (p==cylic1) return 0;
}
}

Node testCylic(Node h1) {
Node p1 = h1, p2 = h1;
while (p2!=NULL && p2->next!=NULL) {
p1 = p1->next;
p2 = p2->next->next;
if (p1 == p2) {
return p1;
}
}
return NULL;
}

第8 题
此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
ANSWER:
Skip.

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一
块。
如果你只能将金条切割两次，你怎样分给这些工人?
ANSWER:
1+2+4;

★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
ANSWER:
Node reverse(Node head) {
if (head == NULL) return head;
if (head->next == NULL) return head;
Node ph = reverse(head->next);
head->next->next = head;
head->next = NULL;
return ph;
}
Node reverseNonrecurisve(Node head) {
if (head == NULL) return head;
Node p = head;
Node previous = NULL;
while (p->next != NULL) {
p->next = previous;
previous = p;
p = p->next;
}
p->next = previous;
return p;
}
★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
ANSWER:
I don’t understand what is “Chuanyue”.
★用一种算法整理一个数组。你为什么选择这种方法?
ANSWER:
What is “Zhengli?”
★用一种算法使通用字符串相匹配。
ANSWER:
What is “Tongyongzifuchuan”... a string with “” and “?”? If so, here is the code.
int match(char str, char ptn) {
if (ptn == ‘\0’) return 1;
if (ptn == ‘’) {
do {
if (match(str++, ptn+1)) return 1;
} while (str != ‘\0’);
return 0;
}
if (str == ‘\0’) return 0;
if (str == ptn || ptn == ‘?’) {
return match(str+1, ptn+1);
}
return 0;
}

★颠倒一个字符串。优化速度。优化空间。
void reverse(char str) {
reverseFixlen(str, strlen(str));
}
void reverseFixlen(char str, int n) {
char p = str+n-1;
while (str < p) {
char c = str;
str = p; p=c;
}
}
★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
ANSWER:
Reverse the whole string, then reverse each word. Using the reverseFixlen() above.
void reverseWordsInSentence(char sen) {
int len = strlen(sen);
reverseFixlen(sen, len);
char p = str;
while (p!=’\0’) {
while (p == ‘ ‘ && p!=’\0’) p++;
str = p;
while (p!= ‘ ‘ && p!=’\0’) p++;
reverseFixlen(str, p-str);
}
}
★找到一个子字符串。优化速度。优化空间。
ANSWER:
KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access the auxiliary array. Otherwise an hashmap or bst may be needed. Lets assume it’s an ASCII string.
int bm_strstr(char str, char *sub) {
int len = strlen(sub);
int i;
int aux[256];
memset(aux, sizeof(int), 256, len+1);
for (i=0; i<len; i++) {
aux[sub[i]] = len - i;
}
int n = strlen(str);
i=len-1;
while (i<n) {
int j=i, k=len-1;
while (k>=0 && str[j--] == sub[k--])
;
if (k<0) return j+1;
if (i+1<n)
i+=aux[str[i+1]];
else
return -1;
}
}
However, this algorithm, as well as BM, KMP algorithms use O(|sub|) space. If this is not acceptable, Rabin-carp algorithm can do it. Using hashing to fast filter out most false matchings.

define HBASE 127

int rc_strstr(char str, char sub) {
int dest= 0;
char p = sub;
int len = 0;
int TO_REDUCE = 1;
while (p!=’\0’) {
dest = HBASE dest + (int)(p);
TO_REDUCE = HBASE;
len ++;
}
int hash = 0;
p = str;
int i=0;
while (p != ‘\0’) {
if (i++<len) hash = HBASE dest + (int)(p);
else hash = (hash - (TO_REDUCE (int)((p-len))))HBASE + (int)(p);
if (hash == dest && i>=len && strncmp(sub, p-len+1, len) == 0) return i-len;
p++;
}
return -1;
}
★比较两个字符串，用O(n)时间和恒量空间。
ANSWER:
What is “comparing two strings”? Just normal string comparison? The natural way use O(n) time and O(1) space.
int strcmp(char p1, char p2) {
while (p1 != ‘\0’ && p2 != ‘\0’ && p1 == p2) {
p1++, p2++;
}
if (p1 == ‘\0’ && p2 == ‘\0’) return 0;
if (p1 == ‘\0’) return -1;
if (p2 == ‘\0’) return 1;
return (p1 - p2); // it can be negotiated whether the above 3 if’s are necessary, I don’t like to omit them.
}
★假设你有一个用1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1 到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
ANSWER:
Sum up all the numbers, then subtract the sum from 1001*1002/2.
Another way, use A XOR A XOR B = B:
int findX(int a[]) {
int k = a[0];
for (int i=1; i<=1000;i++)
k ~= a[i]~i;
}
return k;
}

★不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。
ANSWER:
n<<3;
(n<<3)-n;

第9 题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
ANSWER:
This is an interesting one. There is a traditional question that requires the binary tree to be re-constructed from mid/post/pre order results. This seems similar. For the problems related to (binary) trees, recursion is the first choice.
In this problem, we know in post-order results, the last number should be the root. So we have known the root of the BST is 8 in the example. So we can split the array by the root.
int isPostorderResult(int a[], int n) {
return helper(a, 0, n-1);
}
int helper(int a[], int s, int e) {
if (e==s) return 1;
int i=e-1;
while (a[e]>a[i] && i>=s) i--;
if (!helper(a, i+1, e-1))
return 0;
int k = l;
while (a[e]<a[i] && i>=s) i--;
return helper(a, s, l);
}

第10 题
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
Answer:
Already done this. Skipped.

第11 题
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
ANSWER:
This is interesting... Also recursively, the longest distance between two nodes must be either from root to one leaf, or between two leafs. For the former case, it’s the tree height. For the latter case, it should be the sum of the heights of left and right subtrees of the two leaves’ most least ancestor.
The first case is also the sum the heights of subtrees, just the height + 0.

int maxDistance(Node root) {
int depth;
return helper(root, depth);
}
int helper(Node root, int &depth) {
if (root == NULL) {
depth = 0; return 0;
}
int ld, rd;
int maxleft = helper(root->left, ld);
int maxright = helper(root->right, rd);
depth = max(ld, rd)+1;
return max(maxleft, max(maxright, ld+rd));
}

第12 题
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条件判断语句
（A?B:C）。
ANSWER:
1+..+n=n*(n+1)/2=(n^2+n)/2
it is easy to get x/2, so the problem is to get n^2
though no if/else is allowed, we can easilly go around using short-pass.
using macro to make it fancier:

define T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i)

int foo(int n){
int r=n;
T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31);
return r >> 1;
}

第13 题：
题目：输入一个单向链表，输出该链表中倒数第k 个结点。链表的倒数第0 个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode m_pNext;
};
Answer:
Two ways. 1: record the length of the linked list, then go n-k steps. 2: use two cursors.
Time complexities are exactly the same.
Node lastK(Node head, int k) {
if (k<0) error(“k < 0”);
Node p=head, *pk=head;
for (;k>0;k--) {
if (pk->next!=NULL) pk = pk->next;
else return NULL;
}
while (pk->next!=NULL) {
p=p->next, pk=pk->next;
}
return p;
}

第14 题：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。
ANSWER:
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.
void find2Number(int a[], int n, int dest) {
int f = a, e=a+n-1;
int sum = f + e;
while (sum != dest && f < e) {
if (sum < dest) sum = (++f);
else sum = (--e);
}
if (sum == dest) printf(“%d, %d\n”, f, e);
}

第15 题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/\ /\
5 7 9 11
输出：
8
/ \
10 6
/\ /\
11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode m_pLeft; // left child of node
BSTreeNode m_pRight; // right child of node
};
ANSWER:
This is the basic application of recursion.
PS: I don’t like the m_xx naming convension.
void swap(Node l, Node r) {
Node p = l;
l = r;
*r = p;
}

void mirror(Node * root) {
if (root == NULL) return;
swap(&(root->left), &(root->right));
mirror(root->left);
mirror(root->right);
}

void mirrorIteratively(Node root) {
if (root == NULL) return;
stack<Node> buf;
buf.push(root);
while (!stack.empty()) {
Node * n = stack.pop();
swap(&(root->left), &(root->right));
if (root->left != NULL) buf.push(root->left);
if (root->right != NULL) buf.push(root->right);
}
}

第16 题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
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, 255sizeof(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] + A1B[2];
_r1 = A[0]B1 + A1B[3];
_r[2] = A[2]B[0] + A[3]B[2];
_r[3] = A[2]B1 + A[3]B[3];
}

void power(int[] A, int n, int _r) {
if (n==1) { memcpy(A, _r, 4sizeof(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, 4sizeof(int));
}
}

第20 题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。
ANSWER:
This question checks how the interviewee is familiar with C/C++? I’m so bad at C/C++...

int atoi(char str) {
int neg = 0;
char p = str;
if (p == ‘-’) {
p++; neg = 1;
} else if (p == ‘+’) {
p++;
}
int num = 0;
while (p != ‘\0’) {
if (p>='0' && p <= '9') {
num = num 10 + (*p-’0’);
} else {
error(“illegal number”);
}
p++;
}
return num;
}
PS: I didn’t figure out how to tell a overflow problem easily.

第21 题
2010 年中兴面试题
编程求解：
输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,
使其和等于m ,要求将其中所有的可能组合列出来.
ANSWER
This is a combination generation problem.
void findCombination(int n, int m) {
if (n>m) findCombination(m, m);
int aux[n];
memset(aux, 0, n*sizeof(int));
helper(m, 0, aux);
}
void helper(int dest, int idx, int aux[], int n) {
if (dest == 0)
dump(aux, n);
if (dest <= 0 || idx==n) return;
helper(dest, idx+1, aux, n);
aux[idx] = 1;
helper(dest-idx-1, idx+1, aux, n);
aux[idx] = 0;
}
void dump(int aux[], int n) {
for (int i=0; i<n; i++)
if (aux[i]) printf(“%3d”, i+1);
printf(“\n”);
}
PS: this is not an elegant implementation, however, it is not necessary to use gray code or other techniques for such a problem, right?

第22 题：
有4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。
请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？
ANSWER
I dont’ like brain teaser. As an AI problem, it seems impossible to write the solution in 20 min...

It seems that a brute-force edge cutting strategy could do. Enumerate all possibilities, then for each guy delete the permutation that could be reduced if failed (for A, B, C at 1st round), Then there should be only one or one group of choices left.

But who uses this as an interview question?

第23 题：
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。"
3D 坐标系原点(0.0,0.0,0.0)
圆形:
半径r = 3.0
圆心o = (., 0.0, .)
正方形:
4 个角坐标;
1:(., 0.0, .)
2:(., 0.0, .)
3:(., 0.0, .)
4:(., 0.0, .)
ANSWER
Crap... I totally cannot understand this problem... Does the . represent any possible number?

第24 题：
链表操作，
（1）.单链表就地逆置，
（2）合并链表
ANSWER
Reversing a linked list. Already done.

What do you mean by merge? Are the original lists sorted and need to be kept sorted? If not, are there any special requirements?
I will only do the sorted merging.

Node merge(Node h1, Node h2) {
if (h1 == NULL) return h2;
if (h2 == NULL) return h1;
Node head;
if (h1->data>h2->data) {
head = h2; h2=h2->next;
} else {
head = h1; h1=h1->next;
}
Node * current = head;
while (h1 != NULL && h2 != NULL) {
if (h1 == NULL || (h2!=NULL && h1->data>h2->data)) {
current->next = h2; h2=h2->next; current = current->next;
} else {
current->next = h1; h1=h1->next; current = current->next;
}
}
current->next = NULL;
return head;
}

第25 题：
写一个函数,它的原形是int continumax(char outputstr,char intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr 所指内存。
例如："abcd12345ed125ss123456789"的首地址传给intputstr 后，函数将返回9，
outputstr 所指的值为123456789
ANSWER:

int continumax(char outputstr, char inputstr) {
int len = 0;
char pstart = NULL;
int max = 0;
while (1) {
if (inputstr >= ‘0’ && inputstr <=’9’) {
len ++;
} else {
if (len > max) pstart = inputstr-len;
len = 0;
}
if (inputstr++==’\0’) break;
}
for (int i=0; i<len; i++)
outputstr++ = pstart++;
outputstr = ‘\0’;
return max;
}
26.左旋转字符串
题目：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。
ANSWER
Have done it. Using reverse word function above.

27.跳台阶问题
题目：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。
求总共有多少总跳法，并分析算法的时间复杂度。
这道题最近经常出现，包括MicroStrategy 等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。
ANSWER
f(n)=f(n-1)+f(n-2), f(1)=1, f(2)=2, let f(0) = 1, then f(n) = fibo(n-1);

28.整数的二进制表示中1 的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
分析：
这是一道很基本的考查位运算的面试题。
包括微软在内的很多公司都曾采用过这道题。
ANSWER
Traditional question. Use the equation xxxxxx10000 & (xxxxxx10000-1) = xxxxxx00000
Note: for negative numbers, this also hold, even with 100000000 where the “-1” leading to an underflow.
int countOf1(int n) {
int c=0;
while (n!=0) {
n=n & (n-1);
c++;
}
return c;
}
another solution is to lookup table. O(k), k is sizeof(int);

int countOf1(int n) {
int c = 0;
if (n<0) { c++; n = n & (1<<(sizeof(int)*8-1)); }
while (n!=0) {
c+=tab[n&0xff];
n >>= 8;
}
return c;
}

29.栈的push、pop 序列
题目：输入两个整数序列。其中一个序列表示栈的push 顺序，
判断另一个序列有没有可能是对应的pop 顺序。
为了简单起见，我们假设push 序列的任意两个整数都是不相等的。
比如输入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一个pop 系列。
因为可以有如下的push 和pop 序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
这样得到的pop 序列就是4、5、3、2、1。
但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。
ANSWER
This seems interesting. However, a quite straightforward and promising way is to actually build the stack and check whether the pop action can be achieved.

int isPopSeries(int push[], int pop[], int n) {
stack<int> helper;
int i1=0, i2=0;
while (i2 < n) {
while (stack.empty() || stack.peek() != pop[i2]) {
if (i1<n)
stack.push(push[i1++]);
else
return 0;
while (!stack.empty() && stack.peek() == pop[i2]) {
stack.pop(); i2++;
}
}
}
return 1;
}

30.在从1 到n 的正数中1 出现的次数
题目：输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。
例如输入12，从1 到12 这些整数中包含1 的数字有1，10，11 和12，1 一共出现了5 次。
分析：这是一道广为流传的google 面试题。
ANSWER
This is complicated... I hate it...
Suppose we have N=ABCDEFG.
if G<1, # of 1’s in the units digits is ABCDEF, else ABCDEF+1
if F<1, # of 1’s in the digit of tens is (ABCDE)10, else if F==1: (ABCDE)10+G+1, else (ABCDE+1)10
if E<1, # of 1’s in 3rd digit is (ABCD)100, else if E==1: (ABCD)100+FG+1, else (ABCD+1)100
… so on.
if A=1, # of 1 in this digit is BCDEFG+1, else it’s 1*1000000;
so to fast access the digits and helper numbers, we need to build the fast access table of prefixes and suffixes.

int countOf1s(int n) {
int prefix[10], suffix[10], digits[10]; //10 is enough for 32bit integers
int i=0;
int base = 1;
while (base < n) {
suffix[i] = n % base;
digit[i] = (n % (base 10)) - suffix[i];
prefix[i] = (n - suffix[i] - digit[i]base)/10;
i++, base=10;
}
int count = 0;
base = 1;
for (int j=0; j<i; j++) {
if (digit[j] < 1) count += prefix;
else if (digit[j]==1) count += prefix + suffix + 1;
else count += prefix+base;
base = 10;
}
return count;
}

31.华为面试题：
一类似于蜂窝的结构的图，进行搜索最短路径（要求5 分钟）
ANSWER
Not clear problem. Skipped. Seems a Dijkstra could do.

int dij

32.
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b 中的元素，使[序列a 元素的和]与[序列b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
ANSWER
If only one swap can be taken, it is a O(n^2) searching problem, which can be reduced to O(nlogn) by sorting the arrays and doing binary search.
If any times of swaps can be performed, this is a double combinatorial problem.
In the book <<beauty of codes>>, a similar problem splits an array to halves as even as possible. It is possible to take binary search, when SUM of the array is not too high. Else this is a quite time consuming brute force problem. I cannot figure out a reasonable solution.

33.
实现一个挺高级的字符匹配算法：
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1**3*2 ,12***3 这些都要找出来
其实就是类似一些和谐系统。。。。。
ANSWER
Not a clear problem. Seems a bitset can do.

34.
实现一个队列。
队列的应用场景为：
一个生产者线程将int 类型的数入列，一个消费者线程将int 类型的数出列
ANSWER
I don’t know multithread programming at all....

35.
求一个矩阵中最大的二维矩阵(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C 写出关键代码
ANSWER
This is the traditional problem in Programming Pearls. However, the best result is too complicated to achieve. So lets do the suboptimal one. O(n^3) solution.
1) We have know that the similar problem for 1 dim array can be done in O(n) time. However, this cannot be done in both directions in the same time. We can only calculate the accumulations for all the sublist from i to j, (0<=i<=j<n) for each array in one dimension, which takes O(n^2) time. Then in the other dimension, do the tradtional greedy search.
3) To achieve O(n^2) for accumulation for each column, accumulate 0 to i (i=0,n-1) first, then calcuate the result by acc(i, j) = acc(0, j)-acc(0,i-1)

//acc[in+j] => acc(i,j)
void accumulate(int a[], int n, int acc[]) {
int i=0;
acc[i] = a[i];
for (i=1;i<n; i++) {
acc[i] = acc[i-1]+a[i];
}
for (i=1; i<n; i++) {
for (j=i; j<n; j++) {
acc[in+j] = acc[j] - acc[i-1];
}
}
}

第36 题-40 题（有些题目搜集于CSDN 上的网友，已标明）：
36.引用自网友：longzuo
谷歌笔试：
n 支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，
存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j 的队伍中更强的一支。
所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是4 对3， 5 对8。.......
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4 对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和用于输出比赛名次的数组result[n]，
求出result。
ANSWER
This question is like no-copying merge, or in place matrix rotation.

No-copying merge: merge order to result, then merge the first half from order, and so on.
in place matrix rotation: rotate 01, 23, .. , 2k/2k+1 to 02...2k, 1,3,...2k+1...
The two approaches are both complicated. However, notice one special feature that the losers’ order doesn’t matter. Thus a half-way merge is much simpler and easier:

void knockOut(int *w, int order[], int result[], int n) {
int round = n;
memcpy(result, order, nsizeof(int));
while (round>1) {
int i,j;
for (i=0,j=0; i<round; i+=2) {
int win= (i==round-1) ? i : w[i][i+1];
swap(result, j, win);
j++;
}
}
}

37.
有n 个长为m+1 的字符串，
如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接，
问这n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
ANSWER
This is identical to the problem to find the longest acylic path in a directed graph. If there is a cycle, return false.
Firstly, build the graph. Then search the graph for the longest path.

define MAX_NUM 201

int inDegree[MAX_NUM];
int longestConcat(char * strs, int m, int n) {
int graph[MAX_NUM][MAX_NUM];
int prefixHash[MAX_NUM];
int suffixHash[MAX_NUM];
int i,j;
for (i=0; i<n; i++) {
calcHash(strs[i], prefixHash[i], suffixHash[i]);
graph[i][0] = 0;
}
memset(inDegree, 0, sizeof(int)n);
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
if (suffixHash[i]==prefixHash[j] && strncmp(strs[i]+1, strs[j], m) == 0) {
if (i==j) return 0; // there is a self loop, return false.
graph[i][0] ++;
graph[i][graph[i*n]] = j;
inDegree[j] ++;
}
}
}
return longestPath(graph, n);
}

/**

1. do topological sort, record index[i] in topological order.
1. for all 0-in-degree vertexes, set all path length to -1, do relaxation in topological order to find single source shortest path.
  */

int visit[MAX_NUM];
int parent[MAX_NUM];
// -1 path weight, so 0 is enough.

define MAX_PATH 0

int d[MAX_NUM];

int longestPath(int graph[], int n) {
memset(visit, 0, n*sizeof(int));
if (topSort(graph) == 0) return -1; //topological sort failed, there is cycle.

int min = 0;

for (int i=0; i<n; i++) {
if (inDegree[i] != 0) continue;
memset(parent, -1, nsizeof(int));
memset(d, MAX_PATH, nsizeof(int));
d[i] = 0;
for (int j=0; j<n; j++) {
for (int k=1; k<=graph[top[j]][0]; k++) {
if (d[top[j]] - 1 < d[graph[top[j]][k]]) { // relax with path weight -1
d[graph[top[j]][k]] = d[top[j]] - 1;
parent[graph[top[j]][k]] = top[j];
if (d[graph[top[j]][k]] < min) min = d[graph[top[j]][k]];
}
}
}
}
return -min;
}

int top[MAX_NUM];
int finished[MAX_NUM];
int cnt = 0;
int topSort(int graph[]){
memset(visit, 0, nsizeof(int));
memset(finished, 0, nsizeof(int));
for (int i=0; i<n; i++) {
if (topdfs(graph, i) == 0) return 0;
}
return 1;
}
int topdfs(int graph[], int s) {
if (visited[s] != 0) return 1;
for (int i=1; i<=graph[s][0]; i++) {
if (visited[graph[s][i]]!=0 && finished[graph[s][i]]==0) {
return 0; //gray node, a back edge;
}
if (visited[graph[s][i]] == 0) {
visited[graph[s][i]] = 1;
dfs(graph, graph[s][i]);
}
}
finished[s] = 1;
top[cnt++] = s;
return 1;
}

Time complexity analysis:

Hash calculation: O(nm)
Graph construction: O(nn)
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(nn+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

Use hash map if there is enough memory.
If there is no enough memory, use hash to put urls to bins, and do it until we can fit the bin into memory.
网易有道笔试：
(1).
求一个二叉树中任意两个节点间的最大距离，
两个节点的距离的定义是这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复
杂度。
ANSWER
Have done this.
(2).
求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，
有向图不再连通，描述算法。
ANSWER
Do dfs, record low[i] as the lowest vertex that can be reached from i and i’s successor nodes. For each edge i, if low[i] = i and i is not a leaf in dfs tree, then i is a cut point. The other case is the root of dfs, if root has two or more children ,it is a cut point.

/**

g is defined as: g[i][] is the out edges, g[i][0] is the edge count, g[i][1...g[i][0]] are the other end points.
/
int cnt = 0;
int visited[MAX_NUM];
int lowest[MAX_NUM];
void getCutPoints(int g[], int cuts[], int n) {
memset(cuts, 0, sizeof(int)n);
memset(visited, 0, sizeof(int)n);
memset(lowest, 0, sizeof(int)*n);
for (int i=0; i<n; i++) {
if (visited[i] == 0) {
visited[i] = ++cnt;
dfs(g, cuts, n, i, i);
}
}

int dfs(int *g[], int cuts[], int n, int s, int root) {
int out = 0;
int low = visit[s];
for (int i=1; i<=g[s][0]; i++) {
if (visited[g[s][i]] == 0) {
out++;
visited[g[s][i]] = ++cnt;
int clow = dfs(g, cuts, n, g[s][i], root);
if (clow < low) low = clow;
} else {
if (low > visit[g[s][i]]) {
low = visit[g[s][i]];
}
}
}
lowest[s] = low;
if (s == root && out > 1) {
cuts[s] = 1;
}
return low;
}