Posted on 2008-03-20 21:17
Fox 阅读(4094)
评论(52) 编辑 收藏 引用 所属分类:
G游戏编程
Author: Fox
昨天越俎代庖面试了一个家伙。
看完了他的笔试题目，感觉后背有点凉，但这些东西看看也就过去了，说实话，那些C++的题目多少有点BT。
但我一直觉得DS的东西，如果你当初学的时候是很认真学习过并思考过的，其实是不需要去记忆的，所以我就问了一个关于稳定排序和不稳定排序的问题。我想，只要你理解了各种排序算法的思想，很easy。
只是这哥们儿忘记了什么是稳定排序，我还以为他把快速排序、堆排序当作稳定排序只是没记住。看来，老师从小教育的"一道题目你即使不会也要尽量去答"这种思想遗毒颇深。如果抱着这种思想做程序员，公司多半要垮掉。
想一想稳定排序的概念吧：两个同值元素（不知为什么，我一直记得严老师书上用的是49，看来我还是在读死书、死读书，最后可能会读书死L）在排序前后相对位置保持不变，即本来在前面的还在前面（所谓"尘归尘，土归土"，看来最近思想有点消极，难怪没有激情L）。再想想各种排序的思想，我们很容易得到这样的结论：最普通的O(n2)的算法，一个一个从前比到后，自然不会影响到同值元素的相对位置，而O(nlogn)的算法，由于多路比较，可能导致本来相对位于后面的元素先比较和移动，造成不稳定。这样一想，自然知道简单的插入、选择、归并排序都是稳定的，而改进的高效率的算法则不稳定。
后面另一个同事在询问他做的Demo的事情，因为是DX的东西，我不懂，没插嘴，就随便看他的简历。
看到其中一项，有提到他曾经给大一、大二的学生做过C++培训。我本没打算提他笔试中的C++部分的，但既然曾经为人师表（因为我曾经做过学生、也做过老师），C++基础掌握到这种程度就不对了。尤其对于一个空的C++类默认生成哪些成员函数居然写的一塌糊涂（友情提示：你也不用BS他，如果你没有看过Lippman的《Inside of the C++ Object Model》，建议你先不要发言J）。
我一般对语言特性不太敢发表观点（因为我的C++基础不扎实L），但我对简单的算法或思想小有兴趣（没有你想象中那么高）。可是，笔试中唯一的一个需要coding的题目他又没写。我只好说，C++的东西你掌握怎么样我也可以不看，但这个memcpy的实现，你怎么也得有点想法吧？不然怎么去写代码呢？刚好在面他之前，还和同事讨论过memcpy的问题（如果你给出one byte by one byte的实现会遭BS的J，因为你居然没有考虑过计算机系统本身的数据处理）。
本来还想问他一个关于sizeof()的问题，后来觉得也没什么必要，关于union的对齐，要按照单位最长的成员对齐这一点自己都觉得有点BT就算了。
其实，我想说的是，很多东西，你不能认为你掌握的很好（除非你真的掌握的很好），所谓很好，拿C++来说，就是把你认为你好的地方，你可以不翻其他东西，把它写下来，基本跟ISO C++保持90%以上的相似度就可以了。当然，这样说有点贱了。
毕竟，做游戏程序员（其他也差不多吧）需要的是：
带着激情去编码，带着虚心去学习，带着挑战去交流，带着压力去工作。
激情，能让你的思维满具创意，代码极其飘逸；
虚心，能让你的知识不断积累，从而达到厚积薄发；
挑战，能让你的团队充满活力，交流活泼严谨；
压力，能让你的心态保持平衡，胜不妄喜，败不惶馁。
因为自己这两周心态受到非智力因素干扰，日子过得有点浑噩。写下来，主要是为了放松一下，也提醒自己。
不怕无知，但怕无畏。
-----------------------------------------------------------------
PS：补记于2008/03/26
还是把上午写的一个mymemcpy放上来吧。里面没有对des < src + len的重叠情况进行讨论，因为大致google了一下，似乎很少人这样做（倒不是因为不能实现）。
void *mymemcpy( void *src, void *des, size_t len )
{
char *tempsrc = (char *)src;
char *tempdes = (char *)des;
size_t offset = len / 4;
for( size_t i=0; i<offset; ++i )
{
*(unsigned long *)tempdes = *(unsigned long *)tempsrc;
tempdes += sizeof(unsigned long);
tempsrc += sizeof(unsigned long);
}
offset = len - len % 4;
for( size_t i=0; i<offset; ++i )
{
*tempdes++ = *tempsrc++;
}
return des;
}
刚才想求证一下memcpy在地址重叠的情况下，是否会考虑从后往前copy的情况。结果看到云风的blog上很早的一篇文章，也是讲memcpy的，角度不同。
我想澄清一点，我写这篇blog的初衷只是总结几个技术问题，因此就没有把面试的前因后果讲一下，反倒让很多朋友误解，以为我怎么怎么样了。
事实情况是，这几个问题都是本来的笔试题目当中的，面试的TX从上午10:00前后做到11:30过，等我和另一个同事13点过去的时候，我一直没怎么说话。只是在一边看他的简历和题目，文中已经说了，是看到他的简历之后才提的问题。当时是有10道左右的C++题目，他做对的其实只有一道。
而且，我在提问题的时候也都将问题跟他一起分析了的（除了memcpy之外），自我感觉说话还是很得体的，写文章的风格是另一码事儿。
我没有丝毫瞧不起这位TX的意思，也完全没有显摆的想法。
PS
：忽然想到自己最近为什么癖性十足，因为最近在关注一个家伙的
Blog
，如果不侵权，我想用用他的
Blog
的名字《
不许联想
》，作者是带三个表的王小峰（《三联生活周刊》记者）。所以，如果有人想拍我，建议先看看他的东西，学习一下措辞
J
。一个同事，说天涯也行，我个人觉得天涯有点相互吹捧的味道。
恶心，但没有恶意
J
。