微軟算法面試題

1、反轉一個鏈表。循環算法。

1 List reverse(List l) {

2 if(!l) return l;

3 list cur = ;

4 list pre = l;

5 list tmp;

6 = null;

7 while ( cur ) {

8 tmp = cur;

9 cur = ;

10 = pre

11 pre = tmp;

12 }

13 return tmp;

14 }

2、反轉一個鏈表。遞歸算法。

1 List resverse(list l) {

2 if(!l || !) return l;

3

4 List n = reverse();

5 = l;

6 =null;

7 }

8 return n;

9 }

3、廣度優先遍歷二叉樹。

1 void BST(Tree t) {

2 Queue q = new Queue();

3 e(t);

4 Tree t = e();

5 while(t) {

6 tln(e);

7 e();

8 e(t);

9 t = e();

10 }

11 }

----------------------

1class Node {

2 Tree t;

3 Node next;

4 }

5class Queue {

6 Node head;

7 Node tail;

8 public void enque(Tree t){

9 Node n = new Node();

10 n.t = t;

11 if(!tail){

12 tail = head = n;

13 } else {

14 = n;

15 tail = n;

16 }

17 }

18 public Tree deque() {

19 if (!head) {

20 return null;

21 } else {

22 Node n = head;

23 head = ;

24 return n.t;

25 }

26}

4、輸出一個字符串所有排列。注意有重複字符。

1char[] p;

2void perm(char s[], int i, int n){

3 int j;

4 char temp;

5 for(j=0;j<n;++j){< p="">

6 if(j!=0 && s[j]==s[j-1]);

7 elseif(s[j]!='@'){

8 p[i]=s[j];

9 s[j]='@';

10 if(i==n-1){

11 p[n]='';

12 printf("%s", p);

13 }else{

14 perm(s,i+1,n);

15 }

16 s[j]=p[i];

17 }

18 }

19}

--------------------------

1void main() {

2 char s[N];

3 sort(s);

4 perm(s,0,strlen(s));

5}

5、輸入一個字符串，輸出長型整數。

1 long atol(char *str){

2 char *p = str;

3 long l=1;m=0;

4 if (*p=='-') {

5 l=-1;

6 ++p;

7 }

8 while(isDigit(*p)){

9 m = m*10 + p;

10 ++p;

11 }

12 if(!p) return m*l;

13 else return error;

14}

6、判斷一個鏈表是否有循環。

1 int isLoop(List l) {

2 if ( ! l) return - 1 ;

3 List s = ;

4 while (s && s != l) {

5 s = ;

6 }

7 if ( ! s) return - 1 ;

8 else reutrn 1 ;

9 }

-----------

1int isLoop(List l){

2 if(!l) return 0;

3 p=;

4 wihle(p!=l&&p!=null) {

5 =l;

6 l=p;p=;

7 }

8 if(p=l) return 1;

9 return 0;

10}

實際上，在我的面試過程中，還問到了不破壞結構的其他算法。

我的答案是從鏈表頭開始遍歷，如果節點next指針指向自身，則循環存在;否則將next指針指向自身，遍歷下一個節點。直至next指針為空，此時鏈表無循環。

7、反轉一個字符串。

1 void reverse( char * str) {

2 char tmp;

3 int len;

4 len = strlen(str);

5 for ( int i = 0 ;i < len / 2 ; ++ i) {

6 tmp = char [i];

7 str[i] = str[len - i - 1 ];

8 str[len - i - 1 ] = tmp;

9 }

10 }

8、實現strstr函數。

1int strstr(char[] str, char[] par){

2 int i=0;

3 int j=0;

4 while(str[i] && str[j]){

5 if(str[i]==par[j]){

6 ++i;

7 ++j;

8 }else{

9 i=i-j+1;

10 j=0;

11 }

12 }

13 if(!str[j]) return i-strlen(par);

14 else return -1;

15}

9、實現strcmp函數。

1int strcmp(char* str1, char* str2){

2 while(*str1 && *str2 && *str1==*str2){

3 ++str1;

4 ++str2;

5 }

6 return *str1-*str2;

7}

10、求一個整形中1的位數。

1 int f( int x) {

2 int n = 0 ;

3 while (x) {

4 ++ n;

5 x &= x - 1 ;

6 }

7 return n;

8 }

11、漢諾塔問題。

1void tower(n,x,y,z){

2 if(n==1) move(x,z);

3 else {

4 tower(n-1, x,z,y);

5 move(x,z);

6 tower(n-1, y,x,z);

7 }

8}

12、三柱漢諾塔最小步數。

1 int f3(n) {

2 if (f3[n]) return f3[n];

3 else {

4 if (n == 1 ) {

5 f3[n] = 1 ;

6 return 1 ;

7 }

8 f3[n] = 2 * f3(n - 1 ) + 1 ;

9 return f3[n];

10 }

11 }

四柱漢諾塔最小步數。

1int f4(n){

2 if(f4[n]==0){

3 if(n==1) {

4 f4[1]==1;

5 return 1;

6 }

7 min=2*f4(1)+f3(n-1);

8 for(int i=2;i<n;++i){< p="">

9 u=2*f4(i)+f3(n-i);

10 if(u

11 }

12 f4[n]=min;

13 return min;

14 } else return f4[n];

15}

13、在一個鏈表中刪除另一個鏈表中的元素。

1void (List m, List n) {

2 if(!m || !n) return;

3 List pre = new List();

4 =m;

5 List a=m, b=n,head=pre;

6 while(a && b){

7 if(e < e) {

8 a=;

9 pre=;

10 }else if(e > e){

11 b=;

12 }else{

13 a=;

14 =a;

15 }

16 }

17 m=;

18}

14、一個數組，下標從0到n，元素為從0到n的整數。判斷其中是否有重複元素。

1int hasDuplicate(int[] a, int n){

2 for(int i=0;i<n;++i){< p="">

3 while(a[i]!=i && a[i]!=-1){

4 if(a[a[i]]==-1) return 1;

5 a[i]=a[a[i]];

6 a[a[i]]=-1;

7 }

8 if(a[i]==i) {a[i]=-1;}

9 }

10 return 0;

11}

15、判斷一顆二叉樹是否平衡。

1int isB(Tree t){

2 if(!t) return 0;

3 int left=isB();

4 int right=isB(t);

5 if( left >=0 && right >=0 && left - right <= 1 || left -right >=-1)

6 return (left<right)? p="" +="" 1);<="" left="" :="" right="">

7 else return -1;

8}

9

16、返回一顆二叉樹的深度。

1int depth(Tree t){

2 if(!t) return 0;

3 else {

4 int a=depth(t);

5 int b=depth();

6 return (a>b)?(a+1):(b+1);

7 }

8}

17、兩個鏈表，一升一降。合併為一個升序鏈表。

1 List merge(List a, List d) {

2 List a1 = reverse(d);

3 List p = q = new List();

4 while ( a && a1 ) {

5 if (e < e) {

6 = a;

7 a = ;

8 } else {

9 = a1;

10 a1 = ;

11 }

12 p = ;

13 }

14 if (a) = a;

15 elseif(a1) = a1;

16 return ;

17 }

18、將長型轉換為字符串。

1char* ltoa(long l){

2 char[N] str;

3 int i=1,n=1;

4 while(!(l/i<10)){i*=10;++n}

5 char* str=(char*)malloc(n*sizeof(char));

6 int j=0;

7 while(l){

8 str[j++]=l/i;

9 l=l%i;

10 i/=10;

11 }

12 return str;

13}

19、用一個數據結構實現

1 if (x == 0) y = a;

2 else y = b;

1 j[] = {a,b};

2 y=j[x];

20、在雙向鏈表中刪除指定元素。

1void del(List head, List node){

2 List pre=new List();

3 = head;

4 List cur = head;

5 while(cur && cur!=node){

6 cur=;

7 pre=;

8 }

9 if(!cur) return;

10 List post = ;

11 =;

12 =;

13 return;

14}

21、不重複地輸出升序數組中的元素。

1 void outputUnique( char [] str, int n) {

2 if (n <= 0 ) return ;

3 elseif(n == 1 ) putstr[ 0 ]);

4 else {

5 int i = 0 ,j = 1 ;

6 putstr[ 0 ]);

7 while (j < n) {

8 if (str[j] !== str[i]) {

9 putstr[j]);

10 i = j;

11 }

12 ++ j;

13 }

14 }

15 }

22、面試過程中我還遇到了下面幾題：

1、如何刪除鏈表的倒數第m的`元素?我的方法是先用pre指針從鏈表頭開始步進m，新建pst節點next指針指向頭節點，cur指針指向頭節點，然後pre，cur，post三個指針一起步進，當pre指向鏈表結尾的時候cur指向倒數第m個元素，最後利用pst指針刪除cur指向元素。

2、如何判斷一個字符串是對稱的?如a，aa，aba。設置頭尾指針同時向中間比較靠齊直至相遇。

3、如何利用2函數找出一個字符串中的所有對稱子串?以子串頭指針和尾指針為循環變量設置兩個嵌套的循環以找出所有子串，對每個子串應用2函數。