1CM

  

微软电话面试总结

微软电话面试总结

---主要是如何答考试题---

微软电话面试中不可缺少的部分,就是让你在一段时间内让你写代码,面试时考官给你邮箱地址,并把考试题发到你的邮箱里。应该如何答题,如果我的意见有问题请大家一起探讨。

1.你的电脑上必须有编译环境,并能做调试你写的代码。

2.接到考试题以后,先搞清楚问题,然后分析解决问题的思路。

3.如果在一定的时间内未能完成答题,就面试结束之后,抓紧时间,把正确的答案给考官。这点是不是很明知的选择请大家评论。

 

我接到的题目是:

有整形数组 {112335} ,去掉重复数结果是{1235}并返回个数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 阅读(4373) 评论(14)  编辑 收藏 引用

评论

# re: 微软电话面试总结 2007-12-18 11:55 tip

用STL是不是很简单?  回复  更多评论   

# re: 微软电话面试总结 2007-12-18 16:19 func

你的函数开头写得不好。
参数正不正确,应该是调用者保证的事。
比如:
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);
}
你调用一次f3()就要重复判断p三次,严重浪费。
去掉各函数内的“if(0==p) {...}”,在调用f3()前判断一下参数的有效性,就可以节省两次判断。这就是有调用者保证。

作为函数的实现者,你要做的是用断言assert保证参数正确性,因为它只在debug版本有效,release版本中不起作用。即能报错,又不影响效率。  回复  更多评论   

# re: 微软电话面试总结 2007-12-19 11:30 南龙

@func
是的,有道理。不过第二个是对size进行判断,~~
if(p == NULL) return -1;
if(size <= 0) return 0;
if(size == 1) return 1;  回复  更多评论   

# re: 微软电话面试总结[未登录] 2007-12-19 11:54 goodname

粗粗写了一个,未详加考虑,权当抛砖引玉吧。

#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;
}

应该还有更好点的解法,也许可以使用goto效率还高些?
  回复  更多评论   

# re: 微软电话面试总结[未登录] 2007-12-19 12:48 goodname

使用一个循环的,
供大家参考吧
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;
}  回复  更多评论   

# re: 微软电话面试总结 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;
}
  回复  更多评论   

# re: 微软电话面试总结 2008-09-27 03:18 玄机逸士

我的程序如下,供参考。
说明:经过InitialCompact运算后,最多只有两个数重复的情况,比如{1, 1, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 10} 会变成{1, 1, 2, 3, 5, 5, 10},即肯定不会出现有三个数重复的情况,再运行一次InitialCompact就不会再出现重复数字了。

为了可读性,程序写得有点啰嗦。还有很大的改善空间。:)

#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;
}  回复  更多评论   

# re: 微软电话面试总结 2008-10-23 22:44 aimfaraway

题目给的是个单调不减数列,删除单调序列的重复项可以这么做

#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;
}

  回复  更多评论   

# re: 微软电话面试总结 2008-12-17 12:07 guest

都是庸才啊.  回复  更多评论   

# re: 微软电话面试总结 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 无故多执行好多步
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;
}  回复  更多评论   

# re: 微软电话面试总结 2009-04-18 23:59 yinyueyouge

用hash表啊~~遍历数组里面的每一个整数,插入hash表里面。这样复杂度只是O(n)

或者用一个二元树,遍历数组里面每一个整数,插入二元树里面。这样复杂度是O(log n)  回复  更多评论   

# re: 微软电话面试总结 2009-04-19 00:02 yinyueyouge

若是单调不减数列, 那更简单了,可以用时间复杂度O(n)和空间O(1) 完成。

遍历数组里面的每一个元素,和前一个值比较。若是相等,咔嚓掉。若是大,继续。
  回复  更多评论   

# re: 微软电话面试总结 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;
}
}  回复  更多评论   

# re: 微软电话面试总结[未登录] 2011-04-29 00:03 jason

正解如下:一次循环,用两个下标就行,0~i的元素都是没有重复的,i为最后一个没有重复的元素,j从1开始,一旦发现一个元素与a[i]不一样,就将a[j]和
a[i]交换。思路源自算法导论快排的写法。
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;
}  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理