面试持续了51分钟，一开始是简单聊些简历上的项目，接着提出了下面的四个问题：
1，给定一颗树，他的节点只有指向儿子的指针，没有指向父亲的指针，问给定任意两个结点A,B，求他们的最短路径？
   此题不难，一时紧张，卡在那里不知如何下手，但是我还是坚持跟他耗着先:-)——可以直接当作图用dijkstra算法。对曰：没有父节点的指针，无法向上走。这话激活了我的思维，最短路径不就是离A,B最近的公共父节点到A，B的路径嘛。那么问题已经转换成了寻找公共父节点，因为A,B无法向上走，所以，问题又转换成找到从根结点到A,B的那两条路径(树中，根结点到任意一结点的路径是唯一的!),然后寻找其公共父节点。
   那么如何搜索呢，我当初的想法是，不知道A,B节点的具体位置，宽搜相当与是一层一层往下找，平均最优。
对曰：那在叶子节点岂非十分耗时？我说没办法，平均考虑。对曰：为什么不先做个简单的判断，如果在叶子结点就直接深度？这话又激活了我的思维，于是我说可以综合考虑两种搜索算法，先可以尝试性的从A,B往下走，看看离根的距离，然后再与整棵树的层数做个比较，看离哪边近作相应的算法选择！此题结束》
2，写一个内存拷贝函数void memoryCopy(byte *source,byte *dest,int len)从source指针开始复制len个字节到dest指针处，问设计此函数会碰到那些问题。
   开始进入状态了，我在纸上一画，便答曰，如果两个内存区存在交叉区域，会出现数据丢失的情况。例子如下：
复制[1,10] ==> [6,15],首先[1,5]复制到[6,10]把原来的数据给填充掉了。原来[6,10]上的数据已经永久丢失...解决策略如果首尾相接，倒序复制，that's all。
3，用c语言模拟多态
   我没能嚣张太久，因为马上就碰到了这个问题，他是先让我描述下c跟ｊａｖａ的区别，然后蹦出这个题目。
一时傻眼，因为无从下手。对曰：来个具体例子吧：B类和C类继承A类，他们都有个方法叫fun(),现在只有A类的引用，但如果该实例实际上是B，C类则，调用B,C类的fun()函数。
。。。
几经周折，给出以下答案，但自己并不满意：
typedef struct A
{
  A类中的数据;
  B类中的数据;
  C类中的数据;
  int flag = 0;//0表示A类,1表示B类，2表示C类
}
fun(A *a)
{
    if(a.flag==0)
      执行ｊａｖａ中A.fun()中的代码。
    else if(a.flag==1)
      执行ｊａｖａ中B.fun()中的代码。
    else if(a.fla==2)
      执行ｊａｖａ中C.fun()中的代码。
}
4，让你改进以下库函数
init();
A();
B();
C();
D();
这是一个系列的函数，规定在第一次调用A,B,C,D时必须执行一次init函数，但之后就不需要执行了。一开始代码如下：
int flag = 1;
init();
A()
{
if(flag) {init();flag = 0;}
...
}
B,C,D函数同上。
现在要你改进这个库函数，去掉if(flag) {init();flag = 0;因为第一次执行后以后每次都要判断一次太浪费了。
此题用到函数指针，简单的说来，就是通过这个指针可以执行他指向的函数，并且可以更改指针指向的函数。
//伪代码如下,只更改A函数，其他类似：
函数指针 attr = A1;
A()
{
  执行attr指向的函数；
}
A1（）
{
   老版本A中的代码；
   attr = A2;
}
A2（）
{
   老版本中A的代码；
}
也许你会觉得此方法毫无意义，何必这么麻烦呢，但是在底层设计的函数或是一些压缩算法中都会被调用无数次，多一个判断带来的效率上的损失是无法估计的，精益求精。

后记：
   我是08浙大CS的考研学子，初试成绩出来后便忙着联系导师，搞的焦头烂额（牛的不理你，理你的不牛啊）！这是我的导师周昆教授给我举行的电话面试。电话面试前我们还聊了很多对计算机的看法，这是一次愉快的交流，因为我们有许多共识，当然我现在只是一个计算机的入门者,无法谈论太高层的东西。十分幸运，我成了周教授的首席弟子了（第一届研究生）同时周教授还给了我一个在微软亚洲研究院暑期实习的机会。

周昆教授简介：
1977年出生，现为微软亚洲研究院研究员，CAD&CG图形计算组，长江特聘学者。加入微软后，周昆博士主要从事计算机图形学基础算法，图形软件开发平台以及游戏技术的研究开发，目前已经持有近10项美国专利技术，其中有多项技术被应用在下一代Windows操作系统Longhorn，Windows底层图形系统DirectX，以及XBOX游戏开发平台。在微软工作3年时间，周昆博士已经在国际计算机图形学年会SIGGRAPH上发表5篇论文，其中包括2005年3篇第一作者的论文，刷新了SIGGRAPH 成立32年以来同一年内第一作者论文数的纪录。2007年回到浙江大学计算机科学与技术学院工作，继续从事计算机图形学与虚拟现实领域的相关研究。

评论