Optiver笔试失败，贴面经

runninghare

登陆已4月有余，仍在继续seeking。国内一直从事EDA行业，只懂C/C++，编程水平一般，与坛子里动辄六七年的C++大牛不可同日而语，也做一些Perl，Linux Shell scripting，找工难啊！好羡慕那些做Java和C#的...每天至少两位数的职位放出来。

今天面试Optiver，笔试就fail了，题目主要是数据结构和编程（竟然让在WORD上写程序！），感觉其实并不算太坏，但还是fail了。看来这帮人还是要求很高，6倒题你有两道答不对，或者写出的算法没有优化，基本就可以回家了。

Optiver这家trading公司的面试流程如下：

1. 发给你一套SHL的网上智力题让你自己在家做，时间大约1个小时。很考验英文阅读速度，每道题都有时间限制（大约两分半），很像GRE的逻辑。
2. “邀请你”去公司笔试，就是在word上写答案和代码，闭卷，不准上网，手机关机，90分钟。
3. HR面试
4. 技术人员面试
5. Final面试

笔试一共六道题，我根据自己的记忆贴出来，希望能帮到也要去Optiver的兄弟。

1. 简述Hash和普通平衡二叉树的区别，你什么时候用Hash，什么时候用普通的平衡二叉树？
2. 运用多种数据结构实现FIFO，并指出性能差异。
3. 编程题：给定一棵二叉树，已知左子树节点值均小于根节点，右子树节点的值均大于根节点。已有：
   class Node {
   public:
     Node *left;
     Node *right;
     int val;
   };

写出函数：
   Node *GetNode(Node *root, int n)
   要求返回节点值大于n的最小节点。例如下图：

登录/注册后可看大图

nowaybutgo

题目有点难哦，谢谢分享。

simon_pan

编程题还行，不知道智力题是个什么水平。

mattmilisa

数据结构的问题谁还记得

alicezeng

牛人们探讨一下呀。

runninghare

也不算是智力题，是逻辑推理题，对阅读是个考验。如果题目是中文的话谁都能过的。

lyle_w

完全日不懂，纯帮顶。
LZ加油，道路虽然曲折，但要相信前途一定是光明的

ayuanx

I've gotta say, these tests are new graduate oriented.

tristone

原帖由 ayuanx 于 24-8-2012 00:28 发表

                               
登录/注册后可看大图

I've gotta say, these tests are new graduate oriented.

是说题目太幼稚么？

planetkeeper

同意，都是基本的数据结构题

topliu

谢谢分享！
能记住这么多题目，记忆力很好啊

能把简单的题目写的bug free其实也不是那么容易的。

实际工作中能用上binary search就不错了，一句话，面试期间水平是最高的，工作时间越长，算法就越忘得多。
其实很多大公司要求code写的越简单越易读越好，浪费一点空间时间复杂度没关系，好维护就OK。

ayuanx

原帖由 tristone 于 24-8-2012 00:41 发表

                               
登录/注册后可看大图

是说题目太幼稚么？

不是说太幼稚，而是说拿这些笔试工作经验很多的面试者不合适，难道你不这样觉得？与实际工作脱节太多

planetkeeper

原帖由 topliu 于 24-8-2012 15:04 发表

                               
登录/注册后可看大图

谢谢分享！
能记住这么多题目，记忆力很好啊

能把简单的题目写的bug free其实也不是那么容易的。

实际工作中能用上binary search就不错了，一句话，面试期间水平是最高的，工作时间越长，算法就越忘得多。
其 ...

对java,web适用
用c/c++多少对性能有要求，尤其是嵌入式

workinvm

1. HASH 时间复杂度为 O(1)
平衡二叉树 为 O(log2n)
HASH 在插入时会有冲突，当杂凑函数写的不好时，会牺牲较多内存，并增加时间复杂度。
HASH 通常有几种实现方式，开式寻址，2次hash，桶式存储
平衡二叉树不存在冲突问题，空间复杂度是确定的，缺陷在于插入删除和修改时需要调整平衡二叉树。
平衡二叉树有几种实现方式，AVL tree , black red tree.
一般在数据量较大且内存有限时应优先选择树形结构，平衡二叉树只是一个选项而已。而集合数据量较小，或内存足够是可考虑选择HASH，HASH的优点是速度快。
2. FIFO
可考虑顺序存储，链式存储和循环链表等多种数据结构
3.这个是典型的二叉排序树的查找，用递归实现程序最简洁，应该只要几行，用堆栈也可以实现
4. 由于两个字符串是排序好的，可以用一个字符数组 C[26] = {'a'..'z'} ,然后参考计数排序方法，对字符串1先扫描，
并在C数组中对于位置加1，然后对字符串2扫描，对应位置加1，然后扫描C，只要值为2，则为公共字符。这个算法的时间复杂度为O(n). 如果两个数组中有重复字符，则算法稍微改进一下即可。如果要得到重复字符串只要找到连续两个非0的位置为2的就是重复字符串。
5. 这个题的难度在于闰年的计算，因为闰年除了每四年一个闰年外，还有一个被400整除的问题，这个题如果不能google，比较麻烦。
先答这么多吧，呵呵。说实话题目虽然不是很难，但要在写字板上写出来，而且不出错，有难度，而且还是在面试时有时间限制，如果我去考也不一定能通过，楼主不要气馁，继续努力。

tristone

原帖由 workinvm 于 24-8-2012 16:03 发表

                               
登录/注册后可看大图

3.这个是典型的二叉排序树的查找，用递归实现程序最简洁，应该只要几行，用堆栈也可以实现..

不需要，只要一个loop就够了。因为不是遍历。

tristone

6 是个partition sort + 查找第n大元素

workinvm

原帖由 tristone 于 24-8-2012 16:06 发表

                               
登录/注册后可看大图

不需要，只要一个loop就够了。因为不是遍历。

是的，我搞错了，二叉查找树不需要遍历。

topliu

我怎么觉得是第ｎ小元素呢

runninghare

原帖由 workinvm 于 24-8-2012 16:03 发表

                               
登录/注册后可看大图

1. HASH 时间复杂度为 O(1)
平衡二叉树 为 O(log2n)
HASH 在插入时会有冲突，当杂凑函数写的不好时，会牺牲较多内存，并增加时间复杂度。
HASH 通常有几种实现方式，开式寻址，2次hash，桶式存储
平衡二叉树不存 ...

多谢分享！字符串那道题这样做行吗？如果一个字符串里有同样的字符，不是值也为2了？

toy

6题
[1,count]
5
第n小元素

my_dream

lz能这么清晰的记住这些题目已经很强啦
这些确实比较适合应届生，在学校时学的内容，工作后都扔啦

arpar

……8年没编过程的人惭愧地飘过……只见满屏似曾相识的词儿，不过都忘光光了，呵呵

yuliya123123

看到题目，不由想起几年前刚毕业的时候找工作的情况，在学校做的东西研究的性质多，开发的少。当时恶补了一阵子coding，做梦都是些代码和算法，往事不堪回首啊。后来虽然拿到了若干嵌入式C/C++的offer，但是对此一直心有余悸，到公司的第一天就申请转了research岗。现在看到这些满屏的似曾相似又宛如不识，开始发愁到oz怎么找工作了。java从来没有碰过，C/C++也很少实际历练，怎么办呢？oz应该不需要做什么业务研究、平台需求的人啊。

workinvm

原帖由 runninghare 于 28-8-2012 21:53 发表

                               
登录/注册后可看大图

多谢分享！字符串那道题这样做行吗？如果一个字符串里有同样的字符，不是值也为2了？

是的，我里面有写，如果有重复要做个小处理。具体的说，只要把加改成或就可以了。扫描第一个字符串时或bit0,扫描第二个字符串或 bit1.
然后判断3就可以。如果要取出完整字符串，而不是统计重复字符，要用一个 long 型分前后两个 int 分别加，前提是重复字符串数要小于4G。
总之有很多办法。当然也可以用两个指针交替执行，这样感觉要慢一些，而且两个指针在两个buffer里面来回切换，如果buffer比较大，将导致 cache miss 问题，也就是无法很好的利用到2级缓存，每次读数据都要去总线上去寻址，这样导致性能急剧下降，这些问题在传统的数据结构教材中都没有提到过，那种教材只讲软件算法优化，不考虑现代计算机硬件的相应优化技术，而真正在实际应用中，计算机硬件优化往往比提高算法性能来的简单并有效。

[ 本帖最后由 workinvm 于 30-8-2012 10:49 编辑 ]

runninghare

原帖由 workinvm 于 29-8-2012 23:49 发表

                               
登录/注册后可看大图

是的，我里面有写，如果有重复要做个小处理。具体的说，只要把加改成或就可以了。扫描第一个字符串时或bit0,扫描第二个字符串或 bit1.
然后判断3就可以。如果要取出完整字符串，而不是统计重复字符，要用一个 lon ...

我当时的思路是这样的：因为两个字符串都是排好序的，所以可以各用一个指针从头扫描，比较大小：
char *pa = string_a;
char *pb = string_b;

while (*pa!='\0' && *pb!='\0') {
if (*pa < *pb) {
  pa++;
} else if (*pa > *pb) {
  pb++;
} else {
  //put this char into output.
}
}

Carol_Wu

是外行，感谢LZ 分享，帮顶！

kuafu

现在楼主......，
此外，顶起来为了更多C/C++看到本贴。

cais

原帖由 runninghare 于 30-8-2012 16:39 发表

                               
登录/注册后可看大图

我当时的思路是这样的：因为两个字符串都是排好序的，所以可以各用一个指针从头扫描，比较大小：
char *pa = string_a;
char *pb = string_b;

while (*pa!='\0' && *pb!='\0') {
if (*pa < *pb) {
  pa++ ...

还要加两行处理重复的。因为是排好序的，所以只要记住上一个就好了。
我当时的思路是这样的：因为两个字符串都是排好序的，所以可以各用一个指针从头扫描，比较大小：
另外我把while里面的&& 换成||了。
char *pa = string_a;
char *pb = string_b;
char last = '\0';
while (*pa!='\0' || *pb!='\0') {
if (*pa < *pb) {
  pa++;
} else if (*pa > *pb) {
  pb++;
} else if (*pa != last) {
  printf(*pa);
  last = *pa;
}
}

cais

第三题，不需要递归。
是我小看了题目了。多谢rickxbx提醒。
基本思路是先向右找，找到一个比n大的节点a，就说明目标是在a的左子节点树里面，然后移到a->left，再递归。
因为要求不能用递归，其实用一个while loop重复也是一样。
最后等n->left是空的时候，n就是我们要找的了。
多谢rickxbx再次提醒。
找到一个比n大的节点，不一定目标就是a的左子节点树里面，可能是a本身。
这样就要先把a记住，最后再和左子节点树里面找到的比较一下。
Node *GetNode(Node *root, int n) {
  Node *node = root;
  Node *candidate = NULL;
  while (node != NULL) {
    while (node!=NULL && node->val <=n) {
      node = node->right;
    }
    if (node != NULL) {
      if (candidate == NULL || candidate->val > node->val) {
        candidate = node;
      }
      node = node->left;
    }
  }
  return candidate;
}

[ 本帖最后由 cais 于 16-11-2012 21:25 编辑 ]

cais

原帖由 toy 于 29-8-2012 14:40 发表

                               
登录/注册后可看大图

6题
[1,count]
5
第n小元素

这个应该是用跟quicksort类似的算法来算第n小元素。
关键的不同点是复杂度是O(n), 不是O(nlogn)。
其中最后一段lz应该是记错了，应该是直接 return Recursive(element, k)就好了。什么都不return不行啊。直接 return，才能是O(n)。
不过不得不说lz的记忆力真强啊。