2014微软实习生面试经历

4月28号结束了最后的三面。等了一个多月，这个月初才收到了offer通知。由于三个面试官都没有要求我对面试内容保密，所以如今就将自己面试微软的整个过程记录为博文，供以后的面试者作为參考。转载请注明出处:http://blog.csdn.net/xiefubao。

     开学的时候了解到微软今年在西安没有宣讲会和笔试现场，以为微软不准备在西安招人了。后来才在官网看到今年是网上笔试。大概是3月底投的简历，中文简历早就准备好了，当时暂时赶了一份非常粗糙的英文简历。四月初收到了第一轮笔试的通知。第一轮笔试2个小时，四道英文编程题目，难度要比ACM简单。当时做的比較遗憾的是第三题，预处理数据写了个n^2的算法，仅仅得了10分，当时还以为超时了就没管，后来听说院里有个同学第三题全然暴力写了个n^3的程序竟然拿了100分，sigh，或许当时再继续查下程序的bug笔试就能够至少拿300分了，各种囧，，，只是还是在四月中旬收到了第二次在线測试的通知。第二次測试分为两类题，一类是数学能力測试题：都是一些非常easy的统计类的数学题，可是题目比較多，大概不到一分钟就得做一道，有的还要用到计算器去算结果。还有一类是语言能力測试：语文中学就不太好，最怕这个了。大概就是先给一段话A，然后再给一段话B，依据A推断B正确错误还是不确定，时间也比較紧。

   大概四月20号收到了24号面试的通知，是在线面试。然后就去网上看了好多微软的面经。  

   一面的面试官是个JJ，尽管仅仅能听到对方声音，可是感觉应该非常年轻。一面微软JJ非常和蔼可亲，喜欢笑，这也多少降低了点我的紧张程度。一上来我大概介绍了下自己，然后微软JJ開始问我问题：第一个笼统地问了一句假设程序输出错误的结果，我会怎么检错。依据平时做题的经历，我说假设是在oj上交题目，我会依据返回的结果是WA、TLE还是RE等等类型去查看程序可能存在的bug，balabala....（感觉非常naive，依据JJ问的当时也想不到该怎么回答）。后来JJ说假设程序输入数据不变，代码不变，可是多次执行的结果不一样可能会是什么原因，（说实话，相对于详细算法，我自己是比較怕这样的开放的问题的）。憋了半天，大概说了几种可能性：程序用了new， malloc等申请堆内存的命令，程序调用了获取系统时间函数，程序读取网络或文件里数据，程序用了随机算法等。可是JJ一直让我说下去，后来真想不到其它的了，姐姐就换了问题。结束后发现有个非常关键非常明显的多线程当时没说（预计这个点扣分不少）。

     后来JJ就给了一个详细的题目：给一个汉字字符串和拼音字符串，问怎样推断汉字字符串和拼音字符串是否匹配。

一眼看，认为好简单，我说首先要有每一个汉字读音的数据存储，然后汉字和拼音字符串从左向右扫一遍，假设有一个没匹配上就说明不能匹配。JJ说会有多音字，瞬间认为刚才自己又naive了。我就说那就搜索吧，遇到多音字的话就尝试每种走法，每条路走不通就回溯。然后JJ问我这样的方法大概的时间复杂度，我说理论上最差会是指数级的时间复杂度，可是实际应该不会有那种极限的数据。我感觉和扫一遍差点儿相同，由于多音字走不下去就会非常快回溯回来，不会走太深。然后JJ就让我開始把这个代码在白板上写出来。当时懵了一下，白板相当于没有tab键的txt啊。我问JJ可不能够在本地的IDE上写，JJ说能够。读入数据我说不是关键，就主要写了那个dfs搜索函数，写的过程中JJ还说出去买了个东西。以下是当时写的代码的主要部分：

map<char,vector<string>> maps;

string s1,s2;

bool dfs(int t1,int t2)
{
    if(t1==s1.size()&&t2==s2.size())
        return true;
    if(t1==s1.size()&&t2!=s2.size())
        return false;
    if(t1!=s1.size()&&t2==s2.size())
        return false;
    map<char,vector<string> >::iterator p=maps.find(s1[t1]);
    for(int i=0; i<p->second.size(); i++)
    {
        string tool=p->second[i];
        bool flag=1;
        for(int i=0; i<tool.size(); i++)
            if(s2[t2+i]!=tool[i])
            {
                flag=false;
                break;
            }
        if(flag&&(dfs(t1+1,t2+tool.size())))
            return true;
    }
    return false;
}

然后JJ问我代码的时间复杂度，我说的和刚才的分析差点儿相同，最差指数级，平均应该是O(n)。后来就说了点其它与技术无关的东西就结束了。后来和BW的讨论中发现，事实上写的那个代码加个二维数组的记忆化就能够避免理论上的指数级复杂度（平时写了那么多记忆化搜索的题目，关键的这次面试竟然没想到，或许JJ一直问复杂度就等我说那个优化呢）。有了这次教训，以后面试时肯定会注意要更加冷静思考，还要想想面试官问每一个问题的用意，敏感地察觉到面试官的引导方向。

      二面的面试官是个GG。GG说话非常有条理，有时信号不太好还能够感觉到GG在说问题时候，有益放慢语速以让我听清楚。二面问的问题都比較碎，可能有个别已经记不得了，就写自己记得的吧。

    他先问了个如果性的问题，就是有一个新闻公布平台，每时每刻最多仅仅能有一个用户在发信息，问我会怎样实现。一听有点摸不准GG的核心在哪，不会就是问怎样避免相互排斥的吧。硬着头皮，我说用一个公布信息的锁，一个用户发完信息后才干够把锁释放，而发信息之前必须先获得这个锁。然后GG也没说啥就换问题了。以下问了这样一个问题：有个不定长的整型数组，每一个整数在1-1000之间，问怎样去重。（心中一阵窃喜，怎么问这么简单的问题）。我向GG确认了此问题核心是去重而不是怎样处理数组不定长之后就说出了开一个1000长度bool类型数组用来去重的方法，时间复杂度是O(n)(已经达到下限不可能再优化了)。GG说方法是正确的，然后问我有没有办法优化空间复杂度。又懵了，O(n)的空间复杂度还能够优化？难道O(1)，O(0)?后来说了还能够先排序然后去重，空间就优化到了O(0),可是时间添加到了nlogn。GG仅仅说了句这是个优化空间的办法就又换问题了。（至今想想当时秀逗的自己bit位优化空间都给忘了，而GG说优化空间的时候也一定等的是这种方法啊，囧）。

   然后GG问了个几何问题：给两个三角形，问怎样推断两个三角形是否有重叠部分。做过ACM里的简单计算几何题目的应该都能够秒掉这道题吧。然后我就说了自己的解法：分为两种重叠情况：

    一、推断是否存在嵌套的情况（推断是否一个三角形的三个点都在还有一个三角形里面）。然后我说了推断一个点是否在一个三角形内部的办法:顺时针计算此点与三条线段的有向角度和，三角形内部的话和是360度，外部点会得到0度。

    二、假设不存在嵌套的情况，那么两个三角形有重叠部分则必有线段相交。这时两两推断线段是否相交就能够了。然后我就说了推断两条线段相交的方法：假设两条线段AB与CD相交，则点A、B必在直线CD两側，同一时候点C、D必在直线AB两側。推断两点A、B是否在直线CD两側的办法：求AC和AD向量的叉积和BC和BD向量的叉积相乘，结果是负数就说明A,B在CD两側，得到正数说明在同側，0的话就说明至少有一个在直线CD上。说完后GG肯定了我的方法并换了问题。

  在微软的各种技术面中，当场敲代码好像是不能少的。二面GG最后一个问题是编程题：一个二叉树的根节点定义为第0层，写一个函数，输入根节点地址和m，实现保存第m层节点的数据的任务。非常基础的一个递归题目，写完交过去后GG说能够了就结束了二面。

以下是二面代码的关键部分：

struct node
{
    node *left,*right;
    int value;
};
vector<int> vec;
void dfs(node* p,int m)
{
    if(p==NULL)
        return ;
    if(m==0)
    {
        vec.push_back(p->value);
        return ;
    }
    dfs(p->left,m-1);
    dfs(p->right,m-1);
}

  二面后的第二天收到了三面通知，时间是在28号下午。

  三面的面试官还是个GG，他说他是西电的，离我们学校不远。因为这次三面GG主动开了视频功能，我就也开了自己的视频功能，这样能够相互看到对方（事实上最好别开，看到对方会变得更加紧张，这是我的亲身感觉）。上来GG还开了几句玩笑，可能是让面试者放松下来好发挥吧。可是自己好像一直比較紧张（当时清晰地知道这将是自己的生死面）。開始十几分钟大概就闲聊几句，GG问了简历上的几个点，我也大概说了下自己的大学生活。后来聊完后，GG说按微软的惯例，程序是一定要写的。然后问我是否知道大数乘法（这是ACM里比較基础的工具），我说曾经用数组写过模拟大数运算的模版，重载过+-*/等符号。然后他说这次要写用字符串来模拟大数乘法。我说我没写过这个，可是应该能够写出来（当时真的感觉非常虚，怕写不好，差点拒绝下来，可是感觉拒绝写差点儿相同就意味着被淘汰了，就硬着头皮答应了下来）。然后三面GG给了我我函数声明，关了他的声音说给我半个小时让写，可是我一直在他的监视下的。我大概在纸上画了画，思路清晰后開始写，大概10多分钟写完了，然而一直出不来结果，有的数据输入后输出的还是乱码，一直调到了20多分钟时候才出了正确结果。測的几组结果都正确后，就叫面试GG说写完了。GG让通过邮箱发过去。可是发送邮件有个延迟，他说在这延迟时间里让我先说说自己程序的思想。我就说了起来，blablabla。。。后来GG问怎么还没收到邮件，脑子一懵，自己仅仅顾说了，竟然没先发邮件，太囧了，赶紧发过去，GG当时也笑着说自己也犯过这种囧事。发完后，我才发现输入0*0程序返回了空字符串，连忙改了一下又发了一遍。以下是当时第二遍发的代码的关键部分：

char ans[1000];
char* add_big_integer(char* value1, char* value2)
{
    int len1=strlen(value1);
    int len2=strlen(value2);
    memset(ans,0,sizeof ans);
    reverse(value1,value1+len1);
    reverse(value2,value2+len2);
    for(int i=0; i<len1; i++)
        for(int j=0; j<len2; j++)
        {
            int tool=(value1[i]-'0')*(value2[j]-'0');
            int t=i+j;
            if(ans[t]==0)
                ans[t]='0'+tool%10;
            else
                ans[t]+=tool%10;
            if(ans[t+1]==0)
                ans[t+1]='0'+tool/10;
            else
                ans[t+1]+=tool/10;
            int res=0;
            while(ans[t]>'9')
            {
                res=(ans[t]-'0')/10;
                ans[t]='0'+(ans[t]-'0')%10;
                ans[t+1]+=res;
                t++;
            }
        }
    int len=strlen(ans);
    while(ans[len-1]=='0')
    {
        ans[len-1]=0;
        len--;
        if(len==1)
            break;
    }
    reverse(ans,ans+len);
    return ans;
}
char s1[1001];
char s2[1001];
int main()
{
    while(scanf("%s%s",s1,s2)==2)
        printf("%s",add_big_integer(s1,s2));
    return 0;
}

然后GG说假设我来測自己的程序会用什么样的数据，我大概说了会用0这种边界数据（明显刚才0*0就出错了），还会用负数相乘（跟GG说了自己的程序没处理负数的情况，可是非常好改动，就開始推断下符号即可，GG说没有关系）。然后GG继续问我会输入什么样的数据，期间声音信号不好GG还用打字的途径让我继续补充这个问题的回答。自己也真想不到要用啥数据(当时想的是多试几组数据呗，差点儿相同就应该没错了吧。可是肯定不能这样讲)。后来面试官GG一直往那上面引导，最后还是他自己说了出来:说假设输入0000000123456789乘上还有一个数这种数据，函数里会不会有非常多无用计算（当时一直没想到这个，GG一说出来我直接感觉就要跪了）。我说是的，假设有这种数据，在输入的时候还要处理下以去掉前缀0。后来面试GG也没再问啥，就问我有没有什么问题，我就问了一下三面后大概几天通知结果，GG说一周左右人力资源部会有通知。然后就寒暄挂掉了。

   面试前自己在网上看了好多微软面经，如今仅以此文供以后的学弟妹參考吧。