1、微软面试题集锦链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-2-3-4-5 通过反转后成为5-4-3-2-1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：struct linka int data; linka* next;void reverse(linka*& head) if(head =NULL) return; linka*pre, *cur, *ne; pre=head; cur=head-next; w
2、hile(cur) ne = cur-next; cur-next = pre; pre = cur; cur = ne; head-next = NULL; head = pre;还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：linka* reverse(linka* p,linka*& head) if(p = NULL | p-next = NULL) head
3、=p; return p; else linka* tmp = reverse(p-next,head); tmp-next = p; return p; 判断两个数组中是否存在相同的数字给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C+实现代码如下：bool findcommon(int a,int size1,int b,int size2) int i; for(i=0;isize1;i+) i
4、nt start=0,end=size2-1,mid; while(start=end) mid=(start+end)/2; if(ai=bmid) return true; else if (aibmid) end=mid-1; else start=mid+1; return false;后来发现有一个 O(n)算法。因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进 。推进的规则是比较两个 数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
5、bool findcommon2(int a, int size1, int b, int size2) int i=0,j=0; while(isize1 & jbj) j+; if(aibj) i+; return false;最大子序列问题：给定一整数序列A1， A2，. An （可能有负数），求A1An的一个子序列AiAj，使得Ai到Aj的和最大例如：整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度
6、会达到O(n3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是Ai . Aj的和，那么Sum(i, j+1) = Sum(i, j) + Aj+1。利用这一个递推，我们就可以得到下面这个算法：int max_sub(int a,int size) int i,j,v,max=a0; for(i=0;isize;i+)
7、 v=0; for(j=i;jmax) max=v; return max;那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现：int max_sub2(int a, int size) int i,max=0,temp_sum=0; for(i=0;imax) max=temp_sum; else if(temp_sumnext=NULL) return head; do p1=p1-next; p2=p2-next-next; while(p2 & p2-next); return p1;按单词反转字符串并不是简单的字符串反转，而是按给定字符串里的单词将字符串倒转过来，
8、就是说字符串里面的单词还是保持原来的顺序，这里的每个单词用空格分开。例如：Here is 经过反转后变为： is Here如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次。这样每个单词又恢复了原来的顺序。char* reverse_word(const char* str) int len = strlen(str); char* restr = new charlen+1; strcpy(restr,str); int i,j; for(i=
9、0,j=len-1;ij;i+,j-) char temp=restri; restri=restrj; restrj=temp; int k=0; while(klen) i=j=k; while(restrj!= & restrj!=0 ) j+; k=j+1; j-; for(;iN2-N3-N4-N5-N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。struct link int data; link* next;bool
10、IsLoop(link* head) link* p1=head, *p2 = head; if (head =NULL | head-next =NULL) return false; do p1= p1-next; p2 = p2-next-next; while(p2 & p2-next & p1!=p2); if(p1 = p2) return true; else return false;删除数组中重复的数字问题：一个动态长度可变的数字序列，以数字0为结束标志，要求将重复的数字用一个数字代替，例如：将数组 1,1,1,2,2,2,2,2,7,7,1,5,5,5,0 转变成1,2,7
11、,1,5,0问题比较简单，要注意的是这个数组是动态的。所以避免麻烦我还是用了STL的vector。#include #include using namespace std;/remove the duplicated numbers in an intger array, the array was end with 0;/e.g. 1,1,1,2,2,5,4,4,4,4,1,0 -1,2,5,4,1,0void static remove_duplicated(int a, vector& _st) _st.push_back(a0); for(int i=1;_st_st.size()-
12、1!=0;i+) if(ai-1!=ai) _st.push_back(ai); 当然如果可以改变原来的数组的话，可以不用STL，仅需要指针操作就可以了。下面这个程序将修改原来数组的内容。void static remove_duplicated2(int a) if(a0=0 | a=NULL) return; int insert=1,current=1; while(acurrent!=0) if(acurrent!=acurrent-1) ainsert=acurrent; insert+; current+; else current+; ainsert=0;字符串反转我没有记错的话
13、是一道MSN的笔试题，网上无意中看到的，拿来做了一下。题目是这样的，给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。例如：输入： 第一个字符串: This is zhuxinquans Chinese site: 子串: zhuxinquan输出： nc/moc.zhuxinquan.www/:ptth :etis esenihC szhuxinquan si sihT一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转。我用的方法是用一遍扫描数组的方法。扫描中如果发现子串，就将
14、子串倒过来压入堆栈。最后再将堆栈里的字符弹出，这样子串又恢复了原来的顺序。源代码如下：#include #include #include using namespace std;/reverse the string s1 except the substring token.const char* reverse(const char* s1, const char* token) assert(s1 & token); stack stack1; const char* ptoken = token, *head = s1, *rear = s1; while (*head != 0)
15、while(*head!= 0 & *ptoken = *head) ptoken+; head+; if(*ptoken = 0)/contain the token const char* p; for(p=head-1;p=rear;p-) stack1.push(*p); ptoken = token; rear = head; else stack1.push(*rear); head=+rear; ptoken = token; char * return_v = new charstrlen(s1)+1; int i=0; while(!stack1.empty() return
16、_vi+ = stack1.top(); stack1.pop(); return_vi=0; return return_v;int main(int argc, char* argv) coutThis is zhuxinquans Chinese site: coutreverse(This is zhuxinquans Chinese site: return 0;如何判断一棵二叉树是否是平衡二叉树问题：判断一个二叉排序树是否是平衡二叉树这里是二叉排序树的定义解决方案：根据平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。首先编写一个计算二叉树深度的函
17、数，利用递归实现。templatestatic int Depth(BSTreeNode* pbs) if (pbs=NULL) return 0; else int ld = Depth(pbs-left); int rd = Depth(pbs-right); return 1 + (ld rd ? ld : rd); 下面是利用递归判断左右子树的深度是否相差1来判断是否是平衡二叉树的函数：templatestatic bool isBalance(BSTreeNode* pbs) if (pbs=NULL) return true; int dis = Depth(pbs-left) -
18、 Depth(pbs-right); if (dis1 | disleft) & isBalance(pbs-right);strstr()的简单实现strstr(s1,s2)是一个经常用的函数，他的作用就是在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。下面是这个函数的一个简单实现：static const char* _strstr(const char* s1, const char* s2) assert(s2 & s1); const char* p=s1, *r=s2; while(*p!=0) while(*p+=*r+); if(*r=0) return p
19、; else r=s2; p=+s1; return NULL;Whats the output?char *GetMemory(void)char p = hello world;return p;void Test(void)char *str = NULL;str = GetMemory();printf(str);/ input = 123456, 1+2+3+4+5+6 = 21, 3 int add(int num) int tmpInt = num; int sum = 0; for(;tmpInt10) tmp = add(tmp); return tmp; 找到字符串中由相同
20、字符以不同顺序组成的单词Write a function to find all anagrams in the string containing words separated by spaces. The function shall print anagrams on separate lines. So if input is:tester spot street stop foo testeroutput shall be:tester street testerspot stop#define MAX = 26#define MAX_WORD = 100char * G_strP
21、arse;int G_count;int G_current_Index;int mapMAX_WORDMAX ;typedef struct Node int index; Node * pNext; mchar * getNext() char * pWord = null; while(G_strParsecount+ = ); pWord = G_strParseG_count; if(*pWord != NULL) while(G_strParseG_count+ != | G_strParse != NULL); G_current_Index +; return pWord;vo
22、id deepParse(char * pWord) int i; for(i = 0; pWordi != NULL; i+) mapG_current_Index -1pWordi - 97+; void compareMap() for(int i = 0; i G_count; i+) for(int j = i + 1; j G_count; j+) for(int k=0; k MAX; k+) if(mapik != mapjk) void parser(char * strParse) char * pWord = NULL; G_strParse = strParse; G_
23、count = 0; G_current_Index = 0; while(pWord = getNext() )!= NULL) deepParse(pWord); G_count = G_current_Index; compareMap();int ADD(int a, int b)1,20,01,610, 51000, 956-1,100-555, 222002的31次方1, 2的31次方12的31次方1，2的31次方12的31次方1,，2的31次方12的31次方1, 1Fill Table Row(its a IQ test question)Here is a table include the 2 rows. And the cells in the first row have been filled with 04. Now you need to fill the cells in the second row with integer. It m
