NVidia Onsite 面经

原帖地址:一亩三分地

总共六个人,其中四轮是技术面,一轮是manager带着吃食堂,一轮是HR。

第一轮是印度姐姐,不过很挺nice的,先问了问简历上的东西,然后是编程题。题目比较简单,给一个随机数组,两个数,而且两个数一定会在数组里面出现,输出第一个数和第二个数的最短距离。第一个数一定要先出现,第二个数一定要后出现。很简单,记录第一个数最后一次出现的索引,遇到第二个数就算一下距离。

开始脑抽还想用个stack记索引,然后在印度姐姐的指引下抛弃了这个愚蠢的想法。

然后又问了问别的,具体我忘了。

第二轮是HR,应该是印度来的HR大哥,老严肃了。问了我还有啥offer或者面试吗。然后说了说NV家的福利,relo 9000刀,401k啥的。

第三轮是个白大哥,问了两个题。
1. 求出一个32bits整数的二进制里面有几个 1。 写完,问我还能优化吗,以及用什么例子测试。后来在他的指引下加了个当前数为0的时候跳出循环,返回结果。
2. 给一个文件输入,全是文本,统计符号频率,我说用hashtable,然后问我优化。ASCII的时候可以只用一个size 256的数组。然后又问我怎么优化,实在想不出来。最后他讲了一下他的想法,不过怎样都是O(n),也就不跟我纠结了。
3. 写SQL输出数据库里面所有的表名。象征性的写了个“select * from db.meta;” 然后说大概就是这个样子,不同数据库具体稍有不同。然后让我说说memory layout的stack和heap的区别。区别就是stack在函数调用完会自动回收,heap不会。然后问我回收heap会有啥问题。我说时间久了会有碎片,他说对,就是想听这个。接着就是开始闲聊了。

下面就是manager带着吃饭了,公司请,我顺便问了一下一下最近CES 2015 NV出的那个自动驾驶汽车的硬件和他的组有没有关系,他说有啊blabla,西班牙口音太重,没太懂。期间还讲了CEO把宝马借给他开的故事,还有一些其他技术相关的东西。吃完饭还问我个puzzle,由1000个小方块堆成的大立方体,然后把表面都涂了,问实际涂了几个。大概就是讨论一下几种方法,然后他说工作就是解决各种puzzle,编程只是手段什么的。

顺便说一下,NV家食堂不是免费的。不过好像比较便宜,好几样都是六块。

第五轮是个印度大哥,比较严肃。题目是输入括号的组数,返回所有可能的括号组合。比如输入是3,返回()()(), ((())), ()(()), (())(). 想了一会儿,写了个DFS递归的解。然后问我复杂度,想了半天,觉得是n^2,不过他觉得不是,其实我也不太自信,因为并不是每一层都会有二倍的分支。后来他说n^2也不算偏离的厉害。然后让我结合我的代码说说stack和heap。因为我的代码是python写的,我就说了说哪些变量肯定在heap里,哪些可以在stack里。

最后一轮好像是个原住民工程师,长辫子,带耳环,黄种人面孔。说话很快,但是口音清楚。题目写了个小纸片,贴在电脑上。编程题是找出两个list里面共有的元素。开始他举得例子都是单个字母,吓得我还以为找两个字符串的公共子序列呢。
我说了两个方法,一是都变成hashset,然后求交集。二是先排序,然后双指针比较。讨论了一下优缺点,让我写排序的版本。写完有个脑残bug,指针没有往后移动,在他的提示写对。
然后讨论两个问题。
1. 类似OpenGL这样的图形驱动需要在android设备上测试,测试方法是比较程序在android里面生成的图片和目标图片有没有差异。问怎么测试。撤了各种方法,什么用android虚拟机,测试过的程序和待测试的程序同时在android里跑,然后对比。android设备生成图片,通过网络或者其他方式发到电脑上。然后又问如果要比较视频怎么办,我说视频就是一连串的图片,前面说的都可以用,还可以对视频跳帧采样,减少对比的负担。
2. 写一个程序,目标是从一个路径复制文件到另一个路径,问我怎么写。上学期刚刚写过,还扣了四分之一分呢。我先说了一堆需要考虑的corner case,比如权限没有,文件不存在,源文件和目标文件是同一个文件什么的。接着在内存里开个buffer,然后一块块的复制。然后他问我复制当中有啥问题,我说复制的时候文件没了什么的。
3. 有一堆压缩的文件,有些行可能在多个文件里面出现,目标是删除重复的行。不可能解压缩所有文件到内存里或者硬盘里。问我有啥方法。我先说可以分别解压,扫描,然后在内存建立索引表。然后再分别扫描所有压缩文件,删除重复项。又问我如果内存放不下索引表怎么办,我说可以弄个类似数据库的东西把索引放到硬盘里面。又问我如果硬盘也放不下呢,想了想,我说可以用类似merge sort的方法一边排序,一边删除重复项目。
之后就是闲聊环节,聊了几分钟,到点儿把我带出大楼,面试就结束了。

补充内容 (2016-1-17 09:16):
字体怎么这么神奇,有没有版主给调一下。