微软MSN面试1－合并相同的字符,开源盛世-源代码下载网,一切精彩开放源代码尽在开源盛世！,开源,源代码,源码,VC,VB,Delphi,MapX,GIS,PDA,EVC,EVB,MapInfo,Visual C++,Visual Basic,开放源代码

前言：
去上海面微软总共也也只写了两个程序，而且都写得不是很好，尤其是第一个，这个结果让我现在回忆起来也都觉得汗颜和遗憾啊，老实说，虽说的确是面试那天状态不很好，不过当场没有把一个完整的程序搞定这个事实多少让我觉得很没面子，真是觉得很不爽。这到还真是应了面试华为时那位老兄的话了：你没写过多少程序吧。话虽然比较刻薄，但是，自从面试中兴结束以后就真的很少做编程工作了，咳，看来以后路还真的很长啊，很多东西想到和做到完全是两个概念的

上午面的一道题老实说是很简单的，当然这个简单也只是我面完以后在吃饭的时候再想想的时候觉得的，当时面试的时候，由于前面的一个问题给弄得很难堪所以一拿到这个问题习惯的朝着hash表上面套，结果呢陷进去了不可自拔，现在想来都要骂自己傻了，呵呵。不是吗？

这道题目如下

//remove_duplicate_pack.cpp

//问题:一个动态长度可变的数字序列，以字符'0'结尾

//要求：将重复的数字用一个这样的数字代替，比如

//1,1,1,2,2,3,3,1,0--->1,2,3,1,0

//作者：MingGe
//时间:2006/1/20

#include <stack>

#include <iostream>

using namespace std;

bool remove_duplicate(int a[] , stack<int>& _val)

{

//_val.clear();

int i=0;

if (a[i]==0)

return false;

else

_val.push(a[i]);

while (!_val.empty() && _val.top()!=0)

{

int top=_val.top();

if (top!=a[i])

{

_val.push(a[i]);

}

++i;

}

_val.pop();

return true;

}

int main()

{

int a[]=

{1,1,1,2,2,3,3,1,0};

stack<int> ar;

stack<int> br;

remove_duplicate(a,ar);

while (ar.empty()==false)

{

br.push(ar.top());

ar.pop();

}

while (br.empty()==false)

{

cout<<br.top()<<",";

br.pop();

}

cout<<"0"<<endl;

return 0;

}

当然这程序是回来以后写的，只花了不到10分钟写出的，只是中间为到底使用vector还是用stack而考虑了一下。本质上这应该是个用堆栈解决的问题，但是纯粹从编程方面来看，有点犹豫，最后还是用stack，不过代价是得用两个stack进行输出了J

后记：

堆栈是一个先进后出的容器，那么它需要使用一个容器，STL中的vector是一个容器，但stack不是一个vector，他只是需要使用vector可以存储的功能而已。后来到网上查了查，发现原来STL里面的stack也是用vector实现的，采用的是最直接的继承的方式，不过是采用私有继承(private)，看看源码就知道

#include <iostream>

#include <vector>

using namespace std;

class stack : private vector<int>

{

public:

stack( void )

{ }

void Push( int Value )

{ push_back( Value ); }

int Pop( void )

{

int value = *rbegin();

pop_back();

return value;

}

bool Empty( void )

{ return empty(); }

};

其中stack使用了vector中的push_back,pop_back,empty,rbegin的功能来实现了自己的Push,Pop,Empty的接口和实现。Stack使用了vector。

换言之，所有vector里面的接口都不能用stack对象来调用了，只是在实现stack接口的时候会调用vector基类的接口而已，这个就是所谓的“实现继承”，相对于传统的is a 的接口继承了。当然实现这一点也可以采用组合或者说是聚合一个指针的方式，呵呵，扯远了

posted on 2006-01-20 05:51 MingGe 阅读(1705) 评论(23) 编辑收藏

<-- -->

# re: 微软MSN面试1－合并相同的字符 2006-01-21 04:59 pig

好像写错了吧？

这样pop和push,只是判断stack的top是否和下一个重复。

我觉得应该用hash
我的QQ3000079

# re: 微软MSN面试1－合并相同的字符 2006-01-22 04:50 MingGe

用hash实际上走进误区了，至少由于你不知道实际序列的长度使得这个hash函数不是很容易设计得很好
其实，我当时面试的时候就是一开始也是想到用hash函数来实现的，花了快半个小时还是没有真正搞定，和那个面试官就hash map里面的种种细节问题纠缠了一半天，完全是走进误区了:)

# re: 微软MSN面试1－合并相同的字符 2006-01-22 05:07 pig

哈哈，没看清楚题目。。

看清了真的很简单啊。。郁闷。。；（

# re: 微软MSN面试1－合并相同的字符 2006-01-27 02:17 sharang

为什么要用STL容器呢扫描一遍原来的数组就可以确定了啊

#include <iostream>
using namespace std;

int main(void)
{
int arr[]={1,1,1,2,2,3,3,1,0};
int i,j,k,t;
for (i=1,j=0,k=0; arr[i]; ++i)
{
if (arr[i]!=arr[j])
{
arr[++k]=arr[i];
j=i;
}
}
arr[++k]=0;
for (i=0; i<=k; ++i)
{
cout<<arr[i]<<endl;
}
return 0;
}

# re: 微软MSN面试1－合并相同的字符 2006-01-27 02:18 sharang

晕怎么贴代码的？

# re: 微软MSN面试1－合并相同的字符 2006-02-05 18:53 MingGe

To sharang
1.直接扫描一遍数组的确是可以的，但是对于这样一类问题，有时候直接使用stl容器也许想法更加简单，再面试的时候不容易出错(我指的是任何可能的错误，因为微软面试的时候对于这个要求还是蛮严格的)
算法复杂度往往更可以得到保证
2.至于怎么贴代码，呵呵，你可以使用高级评论，里面可以插入评论

# re: 微软MSN面试1－合并相同的字符 2006-02-20 01:07 疑惑

直接扫描有什么问题么？像这种题目，只要保证数组的边界不overflow,我觉得直接用数组没有任何问题。

当然，使用stl也未尝不可，但在时空及代码可移植性上稍有欠缺，在某些embedded system中是不能使用stl的。

此外，不管使用stl还是直接扫描数组，时间复杂度都是O(n);不会出现时间复杂度无法控制的现象

# re: 微软MSN面试1－合并相同的字符 2006-02-24 18:38 MingGe

你说的由道理,但是我这个人有点懒,习惯用现成的东西,而且直接使用数组还是有点风险的,因为这个下标很容易弄错,我以前吃过大亏,有点怕怕了~
呵呵,希望我的这种观点疑惑兄不要介意...

# re: 微软MSN面试1－合并相同的字符 2006-02-26 01:38 田文平(twpmail@163.com)

有没有这么麻烦居然用stack！！
很简单呀！
#include "stdafx.h"
#include "malloc.h"
#include "string.h"

int main()
{
char *p="111223310";
int i,j,len;
char c;
char *outptr;
len=strlen(p);
if (len>0)
  outptr=(char *)malloc(len);
else
  return (-1); //error
j=0;
for(i=0;i<len;i++)
{
  if (i==0)
  {
    c=p[i];
    outptr[j]=c;
j++;
  }
  else if (c!=p[i])
  {
c=p[i];
    outptr[j]=c;
j++;
  }
}
outptr[j]=0;
printf("%s",outptr);
return (0);
}

# re: 微软MSN面试1－合并相同的字符 2006-02-26 01:43 田文平(twpmail@163.com)

是不是不用stl等等的，微软的人会认为：不务实，什么都从开始写？
对面试有影响？随便问问？
微软是我做梦都向往的！

交个朋友呀！

# re: 微软MSN面试1－合并相同的字符 2006-02-26 02:03 田文平(twpmail@163.com)

写完才发现忘了释放free p；唉！

# re: 微软MSN面试1－合并相同的字符 2006-02-26 03:23 MingGe

这个题目我希望做最后一次的声明:
由于给定的这个序列其实表示的是接收的一帧信息,我们要做的相当于"解码"工作.特别要注意以下有两个限制条件(或者叫信息)
1)长度动态可变,这意味着靠长度这个变量赖控制循环是不现实的;
2)以字符"0"标识结束,也就是只要发现一个"0"就表示当前接收的一帧信息完毕.这个信息是最重要的信息.
前面的sharang,疑惑以及田文平的想法都是不完整的-在微软看来就是错误的.
我前面的留言,当时是因为时间较久了,我自己题目也忘了,所以就没有给出正确的回复.但是必须要说明的是,大家一定要看清楚限制条件!
我贴的那个代码是在面试完不久,思路就是面试那天的思路,应该是正确的.采用数组的方法固然有的时候比较简洁,但是,我建议,在比如象面试这种场合的时候最好用stl,因为,你至少可以集中精力把题目看清楚!

# re: 微软MSN面试1－合并相同的字符 2006-04-13 19:16 简单

#include<iostream>
int main()
{
    int a[]={1,1,1,2,2,3,3,1,0};
    int *p;
    p = a;

    while(*p!=0)
    {
      cout<<*p<<",";
      p++
    }

# re: 微软MSN面试1－合并相同的字符 2006-04-13 19:20 别傻了

#include<iostream>
int main()
{
    int a[]={1,1,1,2,2,3,3,1,0};
    int b,*p;
    p = a;

    while(*p!=0)
    {
      if(b!=*p) {
      b=*p;
      cout<<b<<",";
      p++;
      }
    }
}

# re: 微软MSN面试1－合并相同的字符 2006-04-15 02:06 capzhou@hotmail.com

我觉得这道题是不是加上一个“只可以在原来的数组上操作”才是考官的真实目的呀，我的算法如下：
bool remove_duplicate(int a[])
{
    int i,j;

    if(a[0]) return false;
    i=1, j=0;
    while(a[i] != 0)
    {
        if(a[i] == a[i-1-j]) j++;
        else a[i-j]=[i];
        i++;
    }

    if(j>0) return false;
    return true;
}
我想这个算法无论是时间还是空间都是最低的。可惜呀，本人没有msntc的面试机会。有没有人想交个朋友可以和我联系capzhou@hotmail.com

# re: 微软MSN面试1－合并相同的字符 2006-04-15 02:08 capzhou@hotmail.com

应该还要在末尾加上一个零
bool remove_duplicate(int a[])
{
    int i,j;

    if(a[0]) return false;
    i=1, j=0;
    while(a[i] != 0)
    {
        if(a[i] == a[i-1-j]) j++;
        else a[i-j]=[i];
        i++;
    }

    a[i-j]=0;
    if(j>0) return false;
    return true;
}

# re: 微软MSN面试1－合并相同的字符 2006-04-15 02:14 capzhou@hotmail.com

# re: 微软MSN面试1－合并相同的字符 2006-04-15 13:06 capzhou@hotmail.com

bool remove_duplicate(int a[])
{
    int i,j;

    if(!a[0]) return false;
    i=1, j=0;
    while(a[i])
    {
        if(a[i] == a[i-1-j]) j++;
        else a[i-j]=[i];
        i++;
    }

    a[i-j]=0;
    if(j>0) return false;
    return true;
}

软件：
文章：