首页 > 剑指offer > [转]简记微软实习生面试
2014
03-02

[转]简记微软实习生面试

首先介绍下自己:小硕,2015年毕业,北邮,模式识别方向,本科是学通信的,计算机初等水平吧,熟练使用C++,了解STL吧,C#/Java/Python/R也都用过,面比较广,码农低等水准,复杂的算法看懂就不错了…(文章长些,不喜勿喷)

2014年刚开学,实验时开学后没什么任务,年假里看了些安卓的书,于是花费5天用Andengine开发了一款小游戏,纯属自娱自乐了,“暗兽器”(象狮虎豹那种)。2月20号的时候,师兄要收简历说帮阿里巴巴内推实习,顿时就感觉慌了,什么知识也没有准备,劣性不该,想干什么做什么…匆忙做了份简历发给了师兄。24号的时候发现论坛上微软招实习生的消息,软件开发,简历也都有了就投了一份,然后生活照旧,写写程序,看看书,还有实验室的小活。

26号下午,收到了微软的电话,内容很简单,说我们看到了你的简历,希望明天见面聊聊。我问地址,他说微软研究院自己查吧,很好找…说话很可亲,聊聊嘛,我说时间可以,然后就屁颠地挂了电话,继续写实验室的层次聚类的一个程序。吃完晚饭,感觉明天就要面试了,第一次找实习还是很紧张的,好好准备下吧,看看C++准备点什么,于是先上网搜了下别人的面经,顿时就吓坏了,看到了这个:
http://blog.csdn.net/uestcleo/article/details/7556364

还看到了这个:
http://topic.yingjiesheng.com/mianshi/jingyan/2012/0420/422268.html

等等吧,看完后精神顿时高涨了很多,心里那个委屈啊(本科我怎么没学计算机了,学那些大学物理、电磁场、高频什么的现在也用不到啊),总之,还没去感觉自己就要挂了,主要是我还什么也没准备呢,开学一直没想这事啊。赶快指定了计划:看遍以前的C++笔记、看完数据结构(查找和图有几节没学)、看点操作系统吧,忙碌了一晚上,第二天中午又继续看了3个小时,又分析了下上面那些网页里的微软面试题。看着就害怕…下午1点就硬着头皮出发了。

到微软1点50多,在前台等了一会,来了个技术人员(一面面试官)把我带了进去,17楼,出楼梯,说等会,我去那套题…,看来真不是只聊聊,被电话骗了吧。找了个房间,递给我题,面试官说你做着,20分钟我过来,说着他看看表:诶,正好2点整。我也看了下表,咦,这不明明是2:02嘛。。。看看卷子20分钟15道题,只有一个想法了:挂了。

说一下题目吧,整个试卷是以C#为主吧,可能每个部门不一样,但能感觉出来C#都很基础,不难,只要真正学过C#的(不要像我只在C#中写过点处理程序),了解下C#的底层,至少4道题应该没问题。话说回来,可惜我没真正学过,C#的还有ASP.NET的我就直接放弃了,只回答了下C++中知道的,当然最后C#的也蒙了点。
1.抽象类和接口的区别?
1、抽象类是类,它的子类不能再继承其它类了,但可以实现一个和多个接口。接口不是类,它的子接口可以继承多个接口。
2、抽象类中是可以有不用abstract修饰的方法,而接口中只能有抽象方法,即方法都要用abstract修饰。
3、抽象类可以实现接口,而接口是不能继承或实现抽象类的。

2.进程和线程的区别和关系?
进程是资源分配的基本单位,线程基本上不拥有资源;线程是程序执行的基本单位,进程创建时一般只有一个线程,需要时可由这个线程创建其他线程;一个进程可以有多个线程,它们共享进程资源,在进程的空间中并发活动。

3.UDP和TCP协议的区别?
TCP是面向连接的,可靠传输,适于传输大量数据;UDP是面向非连接的不可靠传输,适于小量数据的传输。

4.异步的概念和实现方式?
当一个异步过程调用发出后,调用者不能立刻得到结果。实际处理这个调用的部件在完成后,通过状态、通知和回调来通知调用者。

执行部件和调用者通过三种途径返回结果:状态、通知和回调。可以使用哪一种依赖于执行部件的实现,除非执行部件提供多种选择,否则不受调用者控制。如果执行部件用状态来通知,那么调用者就需要每隔一定时间检查一次,效率就很低(有些初学多线程编程的人,总喜欢用一个循环去检查某个变量的值,这其实是一种很严重的错误)。如果是使用通知的方式,效率则很高,因为执行部件几乎不需要做额外的操作。至于回调函数,其实和通知没太多区别。

5. .NET的内存回收机制?
每次当开发人员使用 new 运算符创建对象时,运行库都从托管堆为该对象分配内存。新创建的对象被放在上次创建的对象之后。垃圾回收器保存了一个指针,该指针总是指向托管堆中最后一个对象之后的内存空间。

当垃圾回收器的指针指向托管堆以外的内存空间时,就需要回收内存中的垃圾了。在这个过程中,垃圾回收器首先假设在托管堆中所有的对象都需要被回收。然后它在托管堆中寻找被根对象引用的对象(根对象就是全局,静态或处于活动中的局部变量以及寄存器指向的对象),找到后将它们加入一个有效对象的列表中,并在已经搜索过的对象中寻找是否有对象被新加入的有效对象引用。直到垃圾回收器检查完所有的对象后,就有一份根对象和根对象直接或间接引用了的对象的列表,而其它没有在表中的对象就被从内存中回收。

6.堆和栈的区别?

栈区由编译器自动分配释放,存放函数的参数值,局部变量的值等。堆区一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。
C#中值类型存放在堆栈中,引用类型存放在托管堆上。

7.泛型的概念和泛型类型

这里问的应该是C#的,我不太了解,回答的C++的泛型编程:通过模板实现同一算法,并使其适用于不同的数据类型。(容器)类型有:string、vector、list、queue等。

8.考虑有个数据库表manager(employee_name,manger_name)表示职员被那个经理管理,现在要找到直接或间接被某个经理管理的雇员?

这是《数据库系统概念》书中第四章的递归查询,可惜星号部分,看的时候一扫而过,只写了四个字:递归查询。其实程序应该是:

with recursive empl(employee_name,manager_name) as 
( 
select employee_name,manager_name 
from manager  where manager_name = 'XXX' 
union
select manager.employee_name,empl.manager_name
from maneger,empl
where manager.manager_name =empl. employee_name
)
select * from empl;

9.按指定位置交换字符串两部分的位置比如:函数输入(“abcde”, 2) 输出”cdeab”

int SwapStr(char* input, int pos)
{
     char* p = input+pos;
     int nLen = strlen(input);
     //对输入数据检查
     if (input==NULL || nLen<pos)
     {return -1;}
     char* temp= new char[pos+1];
     if (temp == NULL) return -1;
     memcpy(temp, input, pos);
     temp[pos]='\0';
     memcpy(input, p, nLen-pos);
     memcpy(input+nLen-pos, temp, pos);
     delete[] temp;
     temp = NULL;
     return 0;
}

10.给定链表的头指针和一个结点指针,在O(1)时间内删除该结点,链表结点的定义如下:

struct ListNode 
{ 
    int m_nKey; 
    ListNode* m_pNext; 
};

函数的声明如下:void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted);

void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted) 
{ 
    if (NULL != pToBeDeleted->m_pNext) 
    { 
        ListNode *pRealDeleted = pToBeDeleted->m_pNext; 

        pToBeDeleted->m_nKey = pRealDeleted->m_nKey; 

        pToBeDeleted->m_pNext = pRealDeleted->m_pNext; 

        delete pRealDeleted; 
    } 
    else 
    { 
        ListNode *pNode = pListHead; 
        while (NULL != pNode) 
        { 
            if (pNode->m_pNext == pToBeDeleted) 
            { 
                pNode->m_pNext = NULL; 
                delete pToBeDeleted; 
                break; 
            } 
            pNode = pNode->m_pNext; 
        } 
    } 
}

大致就记得这些题目了,感觉还是都比较基础,就是时间不够…,当时的感觉就是要挂了,赶快放我走吧。二十分钟后,开始面试,面试官很严肃,有些题只是简单写了几个字,本以为面试时会问试卷的题目,结果提都没提考卷的题目,看见了一堆错号…改完试卷继续面试,说下面试题目。

什么是时间复杂度和空间复杂度?答:时间复杂度就是随着问题规模n的增大,算法运行时间的增长率;空间复杂度就是算法的空间需求。

是不是数据越多,空间复杂度越大?答:不是,针对某个问题,算法的空间复杂度只和实现中所需的辅助变量有关。不知道答得对不对,总之,面试官是面无表情,继续追问。

怎么降低时间复杂度?答:针对某个问题,采用不同的算法就会有不同的时间运行效率,比如快排在大多场合就优于简单排序。

继续被问:同一个算法呢?答:减少循环的使用,减少循环的嵌套,将多维数组尽可能拆分为1维数组。

面试官笑笑:咱们假设这个程序不是比较2的程序员写的,是专家写的?答:不知道,没有遇到过(我也不是专家啊)。

然后面试官说好,咱们谈谈你做的项目吧,我说给你简历,他说不用了,你就说说吧。心里顿时感觉我快走了,面试官很不屑啊。我说了做的项目,问了我搜索引擎的一个问题,答得还可以吧,然后就面试结束了,让我等下一个面试官。心里想微软面试官真的不错,即使我自己都鄙视自己了,他还要走个流程,让我面完再Pass掉。

稍等片刻,我把简历赶快从包里拿出来了,想待会可能有用。第二个面试官来了,我说这是我的简历,他说不用…这次他带了笔记本,然后问我项目,我说了我研究生一直跟着老师做的863项目,但他并没有太大兴趣,只是说,这个很多人都再做。然后问,其他的呢?我又说了几个自己接的私活,他问的特别多,非常有兴趣,他直接就说:这是你自己接的私活吧,实验室接的任务没有这么明确的商业目的的。然后询问了我做着两个私活过程中的解决方法,基本是我回顾了一下当时做程序时所遇到的各种问题,采取的各个方案。后面的聊天非常开心,他说分析能力不错,但看你的答题,编程很不理想啊…介绍了他们的工作,希望我能去,还留了他的联系方式。180度大转弯,回来给他发了封邮件,问下一步安排,说HR will contact you later。

28号收到了HR的电话,基本就是咨询下我的情况,安排Onbroad时间,Mentor去美国了等他回来,三月中旬后就可以去实习了。不懂的知识太多了,想起三字经:“幼不学,老何为!”。

这是我研究生第一次实习面试,还是比较“青涩”吧,大致总结下这次面试的经验吧:

1.微软的面试官都比较简单,凡事从简,直截了当,很少给人一种亲和感,交谈有时压抑了些(也可能是我跟不上他们吧)。

2.微软的面试题比较简单,仔细想想网上其他的面试题也是很简单的,无非是思路巧妙一些,看看程序员面试宝典、编程之美什么的基本都有(我要开始看了),但是面还是比较广的。

3.普适面试场合上,要跟着面试官的思路走,自己认为重要的可能不是他感兴趣的;面试官感兴趣的就是他看重的,就要多介绍、多说。

转自:http://www.cnblogs.com/houkai/p/3576459.html


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept