微软亚洲研究院2013年实习生招聘笔试题，以及我，作为一个学渣给出的部分答案和分析
我突然想起邹神说过在人人写算法博客。。来试试会是什么效果。
昨天翔神给我发信息说 今天十点一起走啊，我最近脑袋总被门夹。晃过一眼立马提取出 “十点一” 三个字作为关键字并智能改变了顺序变成了十一点。。。于是我们组大部队人马出发后我才起床。慌慌张张的打印了笔试通知单，准备书笔水。。在火车站排531路排了40分钟。最后又是压点进入了考场。
不说废话了，开始讲微软的笔试。题型是不定项选择题，一共二十道，满分一百分，难度分三个段，第一段是1-7题，全部答对得3分，部分对得2分，只要有错误选项就的-2分，不答得0分。接下来两个难度梯度对应得分分别为5 3 -3 0，和13,7，-7,0。
13分的题只有两道。笔试奇葩的地方就是选错会扣分，这个太慎 人了。。会都不敢选。。。而且英文题目，很多单词不认识。有些语句也读不懂什么意思。。
下面开始20道题
1 应该是微软的下马威吧，一道题连问题带答案, 不认识的单词比认识的都多。大概是 calling convension(s) supports supportvariable-lenth parametter (eg:printf) 答案分别是A cdecl B stdcall C pascall D fastcall。
这题大家基本都没选。但是当时我不知道哪儿来的勇气。。就得瑟了一下，我一想提示 eg printf 再看题目 那个单词里面有 变量长度，参数，我就猜想肯定是和参数的调用有关的，printf函数和stdcall的函数调用都是从右向左压栈 并且参数个数可以是任意指定的。 想了想反正错了就扣两分，不能以开场就没了士气，就选上了。 出来上网查查，stdcall应该是正确的，fastcall是错误的。剩下那俩我就不太清楚了。
2 之后这些三分题基本就很水了
二题考C++的虚函数和类型兼容规则，单纯的只考这两个考点，但是谷哥说他错了。。灰作为软院最牛叉的C选手之一。。一向看不惯我的C++代码风格。。虽然最近他开始恶补C++了。。
代码
#include<iostream>
#include<cstdio>
using namespace std;
class A
{
public:
virtual void f(){cout<<"A::f()"<<endl;}
void f()const{cout<<"A::f()const"<<endl;}
};
class B:public A
{
public:
void f(){cout<<"B::f()"<<endl;}
void f()const {cout<<"B:f()"<<endl;}
};
void g(const A * a)
{
a->f();
}
int main()
{
A * a=new B();
a->f();
g(a);
delete a;
return 0;
}
A类声明 f函数是虚函数 所以后面子类自动的f函数都是虚函数 因为a指针指向B对象 所以调用f时 是看B类的虚函数表 自然执行B的f函数
g函数是类型软件规则的典型，所有A的子类指针都会转换成A的指针去调用A的const f函数
运行结果
3 基础题 difference between array and linked list
A search complexity when both sorted 这个肯定错啊，有序的数组用二分查找是log(n) 链表要从头找是 O(n)
B Dynamic add/remove 这个肯定正确，最大的区别就在添加和删除元素么
C random access efficient 这个也对吧，随机读取效率显然是数组高
D data storage type 这个应该也对 数组连续存储 链表不连续
4 操作系统题 我最大的软肋了。。这题其实应该不难，但是作为一个操作系统挂科的学渣。。我是临时突击看了一下进程和线程。最后只敢选了C选项，Thread must belong to a process。这个应该是对的，A选项说 one application in OS must have one process but not necessary to have one Thread 这个说操作系统中一个应用只能有一个进程 但是不必须只能有一个线程 这个应该是错的，想想 打开QQ 或者迅雷，在任务管理器里会出现 多个进程的。
剩下两个答案太长了 来不及超了。。
所以说接下来的任务应该是恶补OS了。。
5 比较难的题 这个应该错的人挺多的
#include<iostream>
using namespace std;
int main()
{
int x=10;
int y=10;
x=x++;
y=++y;
printf("%d %d\n",x,y);
cout<<x<<endl;
return 0;
}
看完立马觉得是 11 11.但是 x++ 和 ++y 是在赋值语句的右边，自增符号在赋值语句后面是不改变自增变量的值的 所以改变的仅仅是y的那条赋值语句 答案是 10 11. 我以前看过这个 但是当时在场上 总觉得有点不对劲 但是又不确定，最后选的啥也忘了。。。
我记得有一条代码风格 就是不要在语句里嵌套写 ++ 和 -- 因为经常会出现奇怪的问题，而且会增加代码复杂度 看来 真是啊。。
6 在java 和C# 代码中 如下定义
Int [][] myarray=new int [3][]{
new int [3]{5,6,7}
new int [5]{6,9,7,8,3}
new int [2]{3,2} }问 myarray[2][2] 返回什么
头三个选项我不记得了，最后一个是overlow java 和C# 基本不会。，猜了一下编译器的最优分配机制，觉得太冒险了，这题没敢选，求java大神指导一下，。
7 水题 选const int a ； int const ；int const * a；三个选项
这没什么好说的，课本上讲常量的地方 看过就知道了
8 挺难的 下面代码的输出结果
#include<iostream>
using namespace std;
class A
{
public: long a;
};
class B :public A
{
public: long b;
};
void seta(A * data,int idx)
{
data[idx].a=2;
}
int main()
{
B data[4];
for(int i=0;i<4;++i)
{
data[i].a=1;
data[i].b=1;
seta(data,i);
}
for(int i=0;i<4;++i)
{
cout<<data[i].a<<data[i].b;
}
return 0;
}
一般看了肯定觉得是21212121 但是仔细想想 微软的笔试题啊，这种题肯定有陷阱。。想了下前面已经很得瑟了 这个题目就没敢选。
刚才本地运行了一下 答案是22221111 也就是说 输出的前两个元素的a b 都是2 。但是我不知道是函数修改了前两个元素 还是因为 输出时 栈地址分配的问题。。这个真不简单，当时想了想 没敢选。。跪求大神指导了@邹 @苏
9 原来题目意思就是 有1000瓶液体 其中有一瓶有毒 剩下都没毒 看不出来哪瓶是有毒的 现在有小白鼠，问你最少需要多少只小白鼠才能知道哪瓶有毒。这个就是典型的二进制思想了。我看过一本书说程序员应该对进制持有平等的看法，十进制仅仅是被世界广为采用的一种方法而已，其实每个进制都是平等的。思路就是 把液体用二进制编号从0到 999 然后找出10只小鼠，编号0-9 对于每一瓶液体，在哪个位上编号是1 就给对应位的小白鼠喝这瓶液体 最后死的那几只小白鼠对应编号是1 活的对应是0 然后这个号就是有毒的瓶子编号
所以2的10次方1024 足够表示1000瓶 疼出来说是9 还讲的很有道理，。好吓我。。最后发现是疼错了。。 据说翔神本来选的10后来脑袋被驴踢了一下 又改成999了。。神都有犯错的时候啊。
10
下面几个选项 哪些在C程序中返回1
A 是main函数正确结束时应该返回的值，这个应该不会有人选吧。，return 0写了上千遍了。。
B return 7&1 不解释 肯定对
C char * str=”microsoft”; return str==”microsoft”; 这个经过刚才的本地测试证明 也是对的，但是当时我纠结了好久没敢选，就在想 str是指针。。其实这样的生命 str 就是一个字符常量 是存在data段的。。
后悔啊。。
D 这个没什么问题 “microsoft”==”microsoft”;肯定对的
11 题意是 int F,G,X;F=X/2;G=X>>1;但是F和G不相等；
这个题还算简单 X肯定是负数 然后随便选一个 负数 写出补码 再看移位后的数 注意负数移位 左边补1 最后看是F比G大1
12
3*4的grid 中有多少 rectangle 这个我就数啊数，肯定是大小从小到大来啊 最后数到50多个了。一看答案 只有60一个 大的了 就选了60 但是还有个选项是none of above 现在很蛋疼会不会是那个啊。。
13
一条线能把一个平面分成两份，两条线分4份 现在问100条线最多分多少 没有平行 没有三点共线，题目里错了一个单词 three打成tree了。。这个我当时觉得很吊啊，最后也没推。出来请教了一下翔神 翔神说他初中就会。。。尼玛了。。。后来想想 确实也不难就是一个简单的推导 f(n)=f(n-1)+n ;f(0)=1; 多画几条线 想想就发现了。。当时觉得自己智商拙计 这么一看就很吊的智商题肯定想不出来。。最后计算结果应该是5051；。。
14 这道题。。最想干死自己的一道题。稳定排序 晃了一眼就过。不知道怎么的就把selection sort 勾上了。 考试前 我姑凉还叮嘱我：“一定要细心啊”。。结果还是出现了这种状况。。
常用的 冒泡归并稳定。快，堆，希尔，选择 都不稳定 这一脑瘫 8分没了。。
15mvc设计模式 我感觉C选项看起来很真，就选了
就是那个controller is the linking between users and the system。接受用处输入调用模型什么的。。这个完全是蒙，设计模式是啥我都不知道。。但是刚查了一下 对了。。 就算和那道脑袋被驴踢了 的题抵消了吧
16 水题 中序和前序 中序和后序 两种 可以确定一棵树。数据结构考试应该考过。必须有中序
17数据库 sql语句 挺简单的 表结构我也忘了 终点是一个 autherid 一个是什么num sql语句执行应该先是 group by autherid 然后having sum(num) <8 然后只有id是2的 他有两本书 更新一下 改变了两行
18一个字符串 各字符都不相同 最多有多少不同的子串
也不知道是不是我理解错了题意，如果就是这么简单的话就是n*(n+1)/2 吧
19 13分的送分题啊。。
这个就是20 最短路。不用dijkstra 不用bellman_ford 不用sfpa，看两眼就看出来了。图一共才几个节点，暴力都行。。
出来流氓吓唬我说19 尼玛真吓死我了。。
20
这个以前看过 但是当时没想出来 大难只要在3的3次方内就可以 就是ABCD 我没选D 自己推出了前三个 正推最后一个 收卷了。
其实也怪自己 我答案还有20分钟 没检查 就爱开始抄题，想把这份题带出来。。因为当时觉得过应该没有问题吧。现在想想后悔了。。。一个学渣一贯的思维，就是过了就行了。。其实后二十分钟检查一下 那道selection sort 起码能选对。。最后一题应该也推出来了。。
既然付出牺牲 把题目带出来。。就放到博客给大家共享了。。
其实微软这种公司，去凑个热闹就可以了。。我这类学渣还是不报任何希望的 就是想体验一下大公司应聘的排场而已。。如果过了笔试。能参加面试的话，应该已经算很荣幸了。
我感觉应该是流氓，彬哥和苏神 包揽大连区 前三甲吧。。
