1CM

導(dǎo)航

<

2007年12月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

統(tǒng)計(jì)

隨筆 - 76
文章 - 0
評論 - 55
引用 - 0

公告

常用鏈接

留言簿(9)

隨筆檔案

相冊

搜索

閱讀排行榜

評論排行榜

微軟電話面試總結(jié)

---主要是如何答考試題---

微軟電話面試中不可缺少的部分，就是讓你在一段時(shí)間內(nèi)讓你寫代碼，面試時(shí)考官給你郵箱地址，并把考試題發(fā)到你的郵箱里。應(yīng)該如何答題，如果我的意見有問題請大家一起探討。

1．你的電腦上必須有編譯環(huán)境，并能做調(diào)試你寫的代碼。

2．接到考試題以后，先搞清楚問題，然后分析解決問題的思路。

3．如果在一定的時(shí)間內(nèi)未能完成答題，就面試結(jié)束之后，抓緊時(shí)間，把正確的答案給考官。這點(diǎn)是不是很明知的選擇請大家評論。

我接到的題目是：

有整形數(shù)組 {1，1，2，3，3，5} ，去掉重復(fù)數(shù)結(jié)果是{1，2，3，5}并返回個(gè)數(shù)4。

思路大家自己想想

int compact(int *p,int size)

{

int i,j;

int count = 1;

if(p == NULL) return -1;

if(size <= 0) return 0;

if(size == 1) return 1;

for(i = 1; i < size - 1;i++)

{

if(*(p + i) == *p) continue;

for(j = i+1;j<size;j++)

{

if(*(p+i) == *(p+j))

*(p+j) = *p;

}

for(i = 1; i < size;i++)

{

if(*(p+i) != *p)

*(p+count++)=*(p+i);

}

return count;

}

posted on 2007-12-18 11:47 1CM 閱讀(4441) 評論(14) 編輯收藏引用

你的函數(shù)開頭寫得不好。
參數(shù)正不正確，應(yīng)該是調(diào)用者保證的事。
比如：
void f1(int* p) {
if(0==p) {...}
...
}
void f2(int* p) {
if(0==p) {...}
f1(p);
}
void f3(int* p) {
if(0==p) {...}
f2(p);
}
你調(diào)用一次f3()就要重復(fù)判斷p三次，嚴(yán)重浪費(fèi)。
去掉各函數(shù)內(nèi)的“if(0==p) {...}”，在調(diào)用f3()前判斷一下參數(shù)的有效性，就可以節(jié)省兩次判斷。這就是有調(diào)用者保證。

作為函數(shù)的實(shí)現(xiàn)者，你要做的是用斷言assert保證參數(shù)正確性，因?yàn)樗辉赿ebug版本有效，release版本中不起作用。即能報(bào)錯(cuò)，又不影響效率。回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2007-12-19 11:30 南龍

@func
是的，有道理。不過第二個(gè)是對size進(jìn)行判斷，~~
if(p == NULL) return -1;
if(size <= 0) return 0;
if(size == 1) return 1; 回復(fù) 更多評論

# re: 微軟電話面試總結(jié)[未登錄] 2007-12-19 11:54 goodname

粗粗寫了一個(gè)，未詳加考慮，權(quán)當(dāng)拋磚引玉吧。

#include <stdio.h>
#include <assert.h>

int compact(int arr[],int size)
{
int i,j;
int count = 0;

for(i = 0;i<size;i++)
{
for(j=0;j<i && arr[j] != arr[i];j++) ;

if(j == i)
{
arr[count++] = arr[i];
}
}

return count;
}

int main()
{
int i;
int arr[] = {1,1,2,3,3,5};
int size;
int count;

size = sizeof(arr)/sizeof(arr[0]);
count = compact(arr,size);

assert(count <= size);

printf("count = %d\n",count);

for(i = 0;i<count;i++)
printf("arr[%d] = %d\n",i,arr[i]);

return 0;
}

應(yīng)該還有更好點(diǎn)的解法,也許可以使用goto效率還高些?
回復(fù) 更多評論

# re: 微軟電話面試總結(jié)[未登錄] 2007-12-19 12:48 goodname

使用一個(gè)循環(huán)的,
供大家參考吧
int compact(int arr[],int size)
{
int i = 0;
int count = 0;
int current = 0;

while(i<=count)
{
if(i == count)
{
i=0;
arr[count++] = arr[current++];
if(current >= size)
return count;
}
else if(arr[i] == arr[current])
{
i = 0;
current++;
if(current >= size)
return count;
}
else
{
i++;
}
}

return count;
} 回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2007-12-19 15:32 南龍

@goodname 寫的太好了，100分 ^_^
這樣如何？


int compact(int arr[],int size)
{
    int i;
    static int count = 0;
    static int curren =0;
    if(curren>=size) return count;
    for(i=0;i< curren && arr[i] != arr[curren];i++);
    if(i == curren)
        arr[count++] = arr[curren];
    curren++;
    compact(arr,size);
    return count;
}

回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2008-09-27 03:18 玄機(jī)逸士

我的程序如下，供參考。
說明：經(jīng)過InitialCompact運(yùn)算后，最多只有兩個(gè)數(shù)重復(fù)的情況，比如{1, 1, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 10} 會變成{1, 1, 2, 3, 5, 5, 10}，即肯定不會出現(xiàn)有三個(gè)數(shù)重復(fù)的情況，再運(yùn)行一次InitialCompact就不會再出現(xiàn)重復(fù)數(shù)字了。

為了可讀性，程序?qū)懙糜悬c(diǎn)啰嗦。還有很大的改善空間。:)

#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

int initialcompact(int*, int);
int compact(int*, int);

int main(int argc, char* argv[])
{
int i;
int a[] = {1, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 10};
int b = compact(a, 12);
printf("the number of compacted array element is: %d\n", b);
printf("the compacted array elements are: \n");
for(i = 0; i < b; i++)
printf("%d\n", a[i]);
return 0;
}

int initialcompact(int* p, int size)
{
assert(p != NULL);
for(int i=0; i < size; i++)
{
for(int j=1; j < size-1; j++)
{
if(p[i] == p[i+j])
{
for(int k = 0; k < size-i-j; k++)
{
p[i+j+k] = p[i+j+k+1];
}
size--;
}
}
}
return size;
}

int compact(int* p, int size)
{
assert(p != NULL);
size = initialcompact(p, size);
size = initialcompact(p, size);
return size;
} 回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2008-10-23 22:44 aimfaraway

題目給的是個(gè)單調(diào)不減數(shù)列,刪除單調(diào)序列的重復(fù)項(xiàng)可以這么做

#include <iostream.h>
int delete_d(int *A,int n)
{
int i=0;
for(int j=1;j<n;)
{
if(A[i]!=A[j])
{
A[++i]=A[j];
}

j++;
}

return i+1;
}
//test
int main()
{
int A[]={1,1,2,3,3,5,6,6,6,6};
int n =delete_d(A,10);
for(int i=0;i<n;i++)
cout<<A[i]<<" ";
return 0;
}

回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2008-12-17 12:07 guest

都是庸才啊. 回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2009-01-07 16:06 baolei

#include <stdio.h>
#include <assert.h>

int compact(int arr[],int size)
{
int i,j;
int count = 0;

for(i = 0;i<size;i++)
{
for(j=0;j<count && arr[j] != arr[i];j++)
{;}

if(j == count)
{//用 j < i, j == i 無故多執(zhí)行好多步
arr[count++] = arr[i];
}
}

return count;
}

int main()
{
int i;
int arr[] = {1,1,2,3,3,5};
int size;
int count;

size = sizeof(arr)/sizeof(arr[0]);
count = compact(arr,size);

assert(count <= size);

printf("count = %d\n",count);

for(i = 0;i<count;i++)
printf("arr[%d] = %d\n",i,arr[i]);

return 0;
} 回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2009-04-18 23:59 yinyueyouge

用hash表啊~~遍歷數(shù)組里面的每一個(gè)整數(shù)，插入hash表里面。這樣復(fù)雜度只是O（n)

或者用一個(gè)二元樹，遍歷數(shù)組里面每一個(gè)整數(shù)，插入二元樹里面。這樣復(fù)雜度是O(log n) 回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2009-04-19 00:02 yinyueyouge

若是單調(diào)不減數(shù)列, 那更簡單了，可以用時(shí)間復(fù)雜度O（n）和空間O(1) 完成。

遍歷數(shù)組里面的每一個(gè)元素，和前一個(gè)值比較。若是相等，咔嚓掉。若是大，繼續(xù)。
回復(fù) 更多評論

# re: 微軟電話面試總結(jié) 2010-04-23 23:52 supernavy

大家看這樣行嗎？

int compact(int[] array, int size) {
int i,j,count=0;
for(int i=0;i<size;i++) {
for(j=i+1;j<size&&array[j]==array[i];j++);
array[count++]=array[i];
i=j;
}
} 回復(fù) 更多評論

# re: 微軟電話面試總結(jié)[未登錄] 2011-04-29 00:03 jason

正解如下：一次循環(huán)，用兩個(gè)下標(biāo)就行，0~i的元素都是沒有重復(fù)的，i為最后一個(gè)沒有重復(fù)的元素，j從1開始，一旦發(fā)現(xiàn)一個(gè)元素與a[i]不一樣，就將a[j]和
a[i]交換。思路源自算法導(dǎo)論快排的寫法。
int unique(int *a, int size)
{
if (NULL == a)
return -1;
if (size <= 0)
return 0;
if (1 == size)
return 1;

int i,j;
int temp;

i = 0;
for (j=1; j<size; j++)
{
if (a[j] != a[i])
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
return i+1;
} 回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 微軟電話面試總結(jié) 2007-12-18 11:55 tip

# re: 微軟電話面試總結(jié) 2007-12-18 16:19 func