微软、google  面试31题及答案

第1 题：

在从1 到n 的正数中1 出现的次数
题目：输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。
例如输入12，从1 到12 这些整数中包含1 的数字有1，10，11 和12，1 一共出现了5 次。
分析：这是一道广为流传的google 面试题。
ANSWER
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;
}

 

第2 题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
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());
}
}
}

 

第3 题：
把二元查找树转变成排序的双向链表
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
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;
}
}

第4 题

设计包含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;
}

 

第5 题：

Ps；我不知道如到底怎样容易地解决溢出问题
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"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;
}

第6 题：

求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为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;
}

第7 题

栈的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;
}

第8 题

在从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;
}

 

第9 题

在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数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; //....
}

第10 题

查找最小的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;
}
}

第11 题

左旋转字符串
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。
ANSWER
Have done it. Using reverse word function above.

第12题

跳台阶问题：一个台阶总共有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);

第13 题

整数的二进制表示中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;
}

 

第14题
给你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...

第15 题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如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;
}

第16 题
此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
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.

定义 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;
第17题
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回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);
}

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

第18 题
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
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));
}

第19 题
题目：求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;
}

第20题：
题目：输入一个单向链表，输出该链表中倒数第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;
}

第21 题：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是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, %dn”, f, e);
}

第22 题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
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);
}
}

第23题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
8
/
6 10
/ /
5 7 9 11
输出8 6 10 5 7 9 11。

层次上的节点以类似的方式打印出来，就像它们的父母打印出来的一样。所以应该是一个FIFO队列来保持这个级别。我真的不记得stl队列的函数名了，所以我要用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());
}
}
}

第24 题：
题目：在一个字符串中找到第一个只出现一次的字符。如输入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.
}

第25题：
题目：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;
}

第26题：
题目：定义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));
}
}

 

第27 题
编程求解：
输入两个整数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?

第28 题：
有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?

第29 题：
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。"
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?

第30 题：
链表操作，
（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;
}

第31题：
写一个函数,它的原形是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;
}

原文链接：http://www.jxszl.com/biancheng/C/445866.html