FreeOZ论坛

标题: Optiver笔试失败，贴面经 [打印本页]
作者: runninghare    时间: 23-8-2012 18:42
提示: 作者被禁止或删除, 无法发言 标题: Optiver笔试失败，贴面经
登陆已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的最小节点。例如下图：
[attach]241764[/attach]
   当n=6的时候，应该返回值为7的节点。要求不准用递归。

4. 编程题：给定两个按字母序排列好的字符串，要求返回第三个字串，包含且仅包含在这两个字串中出现的公共字符，不能有重复。
   实现函数：std::string GetCommon(const std::string & str1, const std::string & str2)
   例： str1为"efllow", str2为"aglop", 需返回"lo"或"ol"
   分析自己算法的复杂度

5. 编程题：给定类:
   class Date {
     int Year;
     int Month;
     int Day;
   };
   编写函数 Date& AddDays(Date &date, int NumDays)返回增加NumDays之后的日期

6. 读代码：
int Recursive(list<int> elementlist, int k) {
        int pivot = elementlist[0];
        list<int>[] element = new list<int>(2);
        int item;
        
        foreach (item in elementlist) {
                if (item < pivot) {
                        add item into element[0];
                } else {
                        add item into element[1];
                }
        }

        if (element[0].count == k-1) {
                return pivot;
        }

        for (int i=0; i<2; ++i) {
                if (element[ i ].count>k) {
                        Recursive(element[ i ],k);
                }
                k = k-element[ i ].count-1;
        }
}

问：1） k的取值范围
   2） 如果elementlist为{3,1,12,5,8,10}，那么当k=3时，Recursive的运行结果
   3） 简述这段代码在做什么

牛人们探讨一下。本人数据结构和纸上写程序功力尚浅。真心希望之后去Optiver的兄弟们不要挂在笔试上。

[ 本帖最后由 runninghare 于 23-8-2012 19:04 编辑 ]
作者: nowaybutgo    时间: 23-8-2012 18:59
题目有点难哦，谢谢分享。
作者: simon_pan    时间: 23-8-2012 19:07
编程题还行，不知道智力题是个什么水平。
作者: mattmilisa    时间: 23-8-2012 19:17
数据结构的问题谁还记得
作者: alicezeng    时间: 23-8-2012 19:18
牛人们探讨一下呀。
作者: runninghare    时间: 23-8-2012 19:39
提示: 作者被禁止或删除, 无法发言 标题: 回复 #3 simon_pan 的帖子
也不算是智力题，是逻辑推理题，对阅读是个考验。如果题目是中文的话谁都能过的。
作者: lyle_w    时间: 23-8-2012 21:23
完全日不懂，纯帮顶。
LZ加油，道路虽然曲折，但要相信前途一定是光明的
作者: ayuanx    时间: 24-8-2012 00:28
I've gotta say, these tests are new graduate oriented.
作者: tristone    时间: 24-8-2012 00:41
原帖由 ayuanx 于 24-8-2012 00:28 发表

                               
登录/注册后可看大图

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


是说题目太幼稚么？
作者: planetkeeper    时间: 24-8-2012 08:25
同意，都是基本的数据结构题
作者: topliu    时间: 24-8-2012 15:04
标题: 谢谢分享
谢谢分享！
能记住这么多题目，记忆力很好啊

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

实际工作中能用上binary search就不错了，一句话，面试期间水平是最高的，工作时间越长，算法就越忘得多。
其实很多大公司要求code写的越简单越易读越好，浪费一点空间时间复杂度没关系，好维护就OK。
作者: ayuanx    时间: 24-8-2012 15:13
原帖由 tristone 于 24-8-2012 00:41 发表

                               
登录/注册后可看大图



是说题目太幼稚么？

不是说太幼稚，而是说拿这些笔试工作经验很多的面试者不合适，难道你不这样觉得？与实际工作脱节太多
作者: planetkeeper    时间: 24-8-2012 15:17
原帖由 topliu 于 24-8-2012 15:04 发表

                               
登录/注册后可看大图

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

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

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

对java,web适用
用c/c++多少对性能有要求，尤其是嵌入式
作者: workinvm    时间: 24-8-2012 16:03
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    时间: 24-8-2012 16:06
原帖由 workinvm 于 24-8-2012 16:03 发表

                               
登录/注册后可看大图

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


不需要，只要一个loop就够了。因为不是遍历。
作者: tristone    时间: 24-8-2012 16:08
6 是个partition sort + 查找第n大元素
作者: workinvm    时间: 24-8-2012 16:11
原帖由 tristone 于 24-8-2012 16:06 发表

                               
登录/注册后可看大图



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

是的，我搞错了，二叉查找树不需要遍历。
作者: topliu    时间: 26-8-2012 21:06
标题: 回复 #16 tristone 的帖子
我怎么觉得是第ｎ小元素呢
作者: runninghare    时间: 28-8-2012 21:53
提示: 作者被禁止或删除, 无法发言
原帖由 workinvm 于 24-8-2012 16:03 发表

                               
登录/注册后可看大图

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


多谢分享！字符串那道题这样做行吗？如果一个字符串里有同样的字符，不是值也为2了？
作者: toy    时间: 29-8-2012 13:40
标题: 赞 楼主记忆力惊人那
6题
[1,count]
5
第n小元素
作者: my_dream    时间: 29-8-2012 14:27
lz能这么清晰的记住这些题目已经很强啦
这些确实比较适合应届生，在学校时学的内容，工作后都扔啦
作者: arpar    时间: 29-8-2012 16:11
……8年没编过程的人惭愧地飘过……只见满屏似曾相识的词儿，不过都忘光光了，呵呵
作者: yuliya123123    时间: 29-8-2012 16:44
看到题目，不由想起几年前刚毕业的时候找工作的情况，在学校做的东西研究的性质多，开发的少。当时恶补了一阵子coding，做梦都是些代码和算法，往事不堪回首啊。后来虽然拿到了若干嵌入式C/C++的offer，但是对此一直心有余悸，到公司的第一天就申请转了research岗。现在看到这些满屏的似曾相似又宛如不识，开始发愁到oz怎么找工作了。java从来没有碰过，C/C++也很少实际历练，怎么办呢？oz应该不需要做什么业务研究、平台需求的人啊。
作者: workinvm    时间: 29-8-2012 23:49
原帖由 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    时间: 30-8-2012 15:39
提示: 作者被禁止或删除, 无法发言
原帖由 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    时间: 30-8-2012 15:44
是外行，感谢LZ 分享，帮顶！
作者: kuafu    时间: 15-11-2012 13:31
标题: 看来trading公司的面试流程大同小异
现在楼主......，
此外，顶起来为了更多C/C++看到本贴。
作者: cais    时间: 15-11-2012 21:47
原帖由 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    时间: 15-11-2012 21:59
第三题，不需要递归。
是我小看了题目了。多谢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    时间: 15-11-2012 22:29
原帖由 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的记忆力真强啊。
作者: rickxbx    时间: 16-11-2012 01:36
标题: 回复 #29 cais 的帖子
Please use your algorithm to calculate Get(5) for the below tree:

           6
         /    \
      4       7
作者: LindaLee    时间: 16-11-2012 01:58
有人说,现在IT这个行业的面试已经被google和微软带坏了, 面试就考数据结构,算法,刁钻的问题. 其实这些东西在工作中真正用到的有多少呢?
作者: cais    时间: 16-11-2012 08:22
原帖由 rickxbx 于 16-11-2012 02:36 发表

                               
登录/注册后可看大图

Please use your algorithm to calculate Get(5) for the below tree:

           6
         /    \
      4       7

我错了。向左走的时候也要比较val。改一下。
作者: nihaowohao    时间: 16-11-2012 11:16
原帖由 LindaLee 于 16-11-2012 02:58 发表

                               
登录/注册后可看大图

有人说,现在IT这个行业的面试已经被google和微软带坏了, 面试就考数据结构,算法,刁钻的问题. 其实这些东西在工作中真正用到的有多少呢?


借用你的“语法”说一说国内的高考：
有人说,现在大学招生考试已经被北大和清华带坏了, 高考出题偏重数学,古汉语中的刁钻问题. 其实这些东西在大多高校读书期间真正用到的有多少呢?

目前的高考虽不是完美的，但就国情而言还有比其更好的选拔制度吗？
试问在没有科学考核学生综合能力的机制中，高考题“不刁钻”怎么能拉开报考人分差进而择优录取呢？
作者: nihaowohao    时间: 16-11-2012 11:36
原帖由 LindaLee 于 16-11-2012 02:58 发表

                               
登录/注册后可看大图

有人说,现在IT这个行业的面试已经被google和微软带坏了, 面试就考数据结构,算法,刁钻的问题. 其实这些东西在工作中真正用到的有多少呢?


不妨把雇主面试看做是：雇主通过简历及求职信对应聘者的工作经验认可后，在超过录用人数的合格应聘者中挑选善于应对“刁钻问题”之人的一个程序。

一些应聘者认为的“刁钻问题”，可能面试官认为是基础知识或能力问题。
作者: rickxbx    时间: 16-11-2012 16:33
标题: 回复 #33 cais 的帖子
呵呵, 我那个例子还是得不到需要的结果
作者: cais    时间: 16-11-2012 20:26
原帖由 rickxbx 于 16-11-2012 17:33 发表

                               
登录/注册后可看大图

呵呵, 我那个例子还是得不到需要的结果

这题陷阱真多啊。下次我就改用这题来面人好了。
我又改了一下，你看对不对？
作者: rickxbx    时间: 16-11-2012 20:44
标题: 回复 #37 cais 的帖子
这样貌似没有什么问题了，可以写的通俗易懂一点：
  while (node != NULL)
{
     if ( n <= node->val )
     {
         candidate = node; node = node->left;
     }
     else
          node = node->right;
  }
作者: audreybest    时间: 18-8-2013 12:51
rickxbx 发表于 16-11-2012 20:44

                               
登录/注册后可看大图

这样貌似没有什么问题了，可以写的通俗易懂一点：
  while (node != NULL)
{

嗯。这个解法正确~~~
作者: audreybest    时间: 18-8-2013 13:31
rickxbx 发表于 16-11-2012 20:44

                               
登录/注册后可看大图

这样貌似没有什么问题了，可以写的通俗易懂一点：
  while (node != NULL)
{

哦，有一点不对，n=node->val的时候，应该走右枝而不是左枝。
作者: finger|regnif    时间: 18-8-2013 13:56
以前一个中介发给我的SHL中的一个pdf
作者: finger|regnif    时间: 18-8-2013 14:13
第三题见过好多次了. 刚毕业时第一家公司考的就是这个. 我一直以为是折半查找.

第四题刚开始想是把一个字符串里的字符都存到hash表, 再遍历第二个字符串到hash表里找, n+n. 后来看了下24楼. 发现hash表不就是26bits大就可以了吗 (编程珠玑?)

这种笔试提前看一下 <<程序员面试攻略>> 应该靠谱.  http://book.douban.com/subject/2348812/
作者: audreybest    时间: 18-8-2013 17:22
finger|regnif 发表于 18-8-2013 13:56

                               
登录/注册后可看大图

以前一个中介发给我的SHL中的一个pdf

多谢分享。不过我考的比这个难点。
作者: audreybest    时间: 18-8-2013 17:23
finger|regnif 发表于 18-8-2013 14:13

                               
登录/注册后可看大图

第三题见过好多次了. 刚毕业时第一家公司考的就是这个. 我一直以为是折半查找.

第四题刚开始想是把一个字 ...

我是存到数组里的。hash之类的模板可以直接用？那。。。
作者: audreybest    时间: 18-8-2013 17:30
workinvm 发表于 29-8-2012 23:49

                               
登录/注册后可看大图

是的，我里面有写，如果有重复要做个小处理。具体的说，只要把加改成或就可以了。扫描第一个字符串时或bi ...

“如果要得到重复字符串只要找到连续两个非0的位置为2的就是重复字符串。”

如果用你的方法，没法得到重复字符串的。比如 bfijk和abfi。位置为2的不是连续的。
作者: happy218    时间: 29-9-2013 20:41
谢谢分享！
作者: eastlake    时间: 30-9-2013 22:22
太难了，不会编程的IT飘过~~
作者: clarkli    时间: 25-1-2015 13:56
看起来题目难度介于Leetcode的easy和medium之间
作者: jimmyking    时间: 25-1-2015 15:16
面试的时候准备准备还会做，现在又忘了。。。
作者: coremedy    时间: 26-1-2015 16:50
workinvm 发表于 24-8-2012 17:03
1. HASH 时间复杂度为 O(1)
平衡二叉树 为 O(log2n)
HASH 在插入时会有冲突，当杂凑函数写的不好时，会牺 ...

4的解法很不错。用类似bitmap的方法O(n)打完收工。我一开始傻了居然想用Set，那肯定要O(nlgn)以上了。
作者: xrzedane    时间: 12-2-2015 21:31
我也投这个公司了，不过是infrasturcture的职位，简历就没通过…
作者: 狮子的眼睛    时间: 18-7-2015 17:49
本帖最后由 狮子的眼睛 于 18-7-2015 18:07 编辑

removed , please ignore.
作者: 狮子的眼睛    时间: 18-7-2015 17:51
本帖最后由 狮子的眼睛 于 18-7-2015 18:06 编辑

removed , please ignore
作者: 狮子的眼睛    时间: 18-7-2015 17:54
本帖最后由 狮子的眼睛 于 18-7-2015 18:06 编辑

Removed, please ignore



欢迎光临 FreeOZ论坛 (https://www.freeoz.org/ibbs/) Powered by Discuz! X3.2