一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 7835|回复: 76
收起左侧

Two Sigma onsite换题啦

[复制链接] |试试Instant~ |关注本帖
ybxsnail 发表于 2015-9-15 08:46:58 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@TwoSigma - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
上周去面了two sigma,之前看地里的面经,感觉好像每个都差不多,于是天真地以为我的也会是一样的,没想到啊。

虽然事后想想题都不难,而且还没design题,但是我这个一紧张就犯晕的毛病,很遗憾,最后还是只面了半天,哎。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一轮


开始问了问你为什么申请这个职位啊,一些项目之类的,然后就开始做题,第一题是leetcode原题,reverse polish notation那个,但是这里只有加减法,follow up是如果要增加其他的运算,怎么改现有的代码比较好?. visit 1point3acres.com for more.

第二题是给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复杂度,而且大小是确定好的,描述无能,举个例子:比如可以用array而不能用arraylist。。。我只知道用暴力法了,O(n2)复杂度,后来他让我优化,想了一下,但是没时间了,他就给了个不痛不痒的提示就就结束了。。。不知哪位大神能有更好的办法 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

第二轮

先是介绍了一下自己,说他从amazon跳过来的,已经七年了,为什么跳槽呢,因为amazon的同事老跳槽,感觉一点都不稳定,于是他也走了。。。然后让我问问题
. From 1point 3acres bbs
接着就是题了,给你两个independent queue,每个queue都存着timestamp,只能有getNext()来取queue里面的timestamp,每个timestamp只能被取一次,比较这两个queue里的timestamp,如果差值<1,print这两个timestamp。例如:
Q1 0.2, 1.4, 3.0
Q2 1.0 1.1, 3.5
output: (0.2, 1.0), (1.4, 1.0), (0.2, 1.1), (1.4, 1.1), (3.0, 3.5)
当时光是理解这道题就花了好长时间,愣是搞明白,理解能力捉急
. 鍥磋鎴戜滑@1point 3 acres

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷第三轮


这轮就是wildcard matching,没啥可说的了。最开始让我写test case,写了一堆,然后才让我写函数。要命的是很久没写这道题了,居然中间出了个bug,又饿又急,瞬间傻逼了,简直了。。。


面的时候就感觉不好,最后果然呵呵了。吃了个饭就滚蛋了。

不过two sigma的人都特别热情,特别好,不管是面试官还是hr,前台,这么好的公司大家一定要加油啊!

希望这些对大家有帮助,祝你们都能拿到offer,也希望我能尽快找到工作

评分

6

查看全部评分

victortang1210 发表于 2016-2-20 01:30:49 | 显示全部楼层

请问楼主,第一轮第二题delete Subtree题,楼主说每个node valid or not是不是意思就是删了的话就让node.valid=False?

我的方法是用两个hashtable。childrenDic是节点val对应它的孩子节点val,idxDic是节点val对应节点在array里的index,便于删除节点时直接令其not valid。用DFS开始将删除index的子树各节点not valid. 注释部分是test case,如有错误请告知。时间复杂度是每个节点都会走一遍O(n), 空间复杂度两个hashtable, 长度也最多是n, 所以O(n)。
  1. def delSubtree(A, index):
  2.   if A == None or len(A) == 0:
  3.     return A
  4. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.   childrenDic = dict()
  6.   idxDic = dict()

  7.   for i in range(len(A)):
  8.     node = A[i]
  9.     idxDic[node.val] = i
  10.     p = node.parent.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     if p:
  12.       if p.val not in childrenDic:
  13.         childrenDic[p.val] = []
  14.       childrenDic[p.val].append(node.val)

  15.   dfs(index, childrenDic, idxDic, A). 1point3acres.com/bbs
  16.   return A

  17. def dfs(index, childrenDic, idxDic, A):
  18.   A[idxDic[index]].valid = False
  19.   if index in childrenDic:
  20.     for i in childrenDic[index]:. visit 1point3acres.com for more.
  21.       dfs(i, childrenDic, idxDic, A)
  22. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  23. class TreeNode(object):
  24.   def __init__(self, val, parent):
  25.     self.val = val
  26.     self.parent = parent. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  27.     self.valid = True

  28. # a = TreeNode(1, None)
  29. # b = TreeNode(2, a)
  30. # c = TreeNode(3, a)
  31. # d = TreeNode(4, a). From 1point 3acres bbs
  32. # e = TreeNode(5, b)
  33. # f = TreeNode(6, b)
  34. # g = TreeNode(7, c). 鍥磋鎴戜滑@1point 3 acres

  35. # A = [g,f,b,a,c,d,e]

  36. # res = delSubtree(A, 2)
  37. # for i in res:. more info on 1point3acres.com
  38. #   if i.valid:
  39. #         print i.val
复制代码
回复 支持 1 反对 0

使用道具 举报

mikegrup 发表于 2015-9-26 23:35:48 | 显示全部楼层
minglotus 发表于 2015-9-15 17:07
问:.1point3acres缃
第二题是给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个数组里的,数 ...

应该不用union find,恐怕union find都只会追溯到root。最好的方法,想之前的几位说过,用HashMap保存每个节点的子节点,或者ArrayList<Integer,ArrayList<Integer>>也可以,空间O(n)。然后删除的时候recursive 删掉所有children。当然children也是有children的,同样的继续recursive
回复 支持 1 反对 0

使用道具 举报

cbwcs 发表于 2015-9-15 11:39:23 | 显示全部楼层
楼主摸摸头,谢谢分享经验,也在努力找工作中,转专业不容易,一起共勉!
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-15 12:43:31 | 显示全部楼层
第一题如果用hashmap把节点所有的孩子存下来,应该也算空间O(n)吧?请问面试官是怎么提示的?
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-15 13:53:20 | 显示全部楼层
cbwcs 发表于 2015-9-15 11:39
楼主摸摸头,谢谢分享经验,也在努力找工作中,转专业不容易,一起共勉!

嗯哪,我也是转专业,一起加油!
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-15 13:56:35 | 显示全部楼层
wenqiang88 发表于 2015-9-15 12:43
第一题如果用hashmap把节点所有的孩子存下来,应该也算空间O(n)吧?请问面试官是怎么提示的?

不能用hashmap或hashset之类的,空间在你定义的时候必须是确定的。因为在遍历的过程中你会不断往map里加节点所以大小是变化的
回复 支持 反对

使用道具 举报

tbu 发表于 2015-9-15 15:33:58 | 显示全部楼层
LZ是海投的么还是?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-15 16:53:04 | 显示全部楼层
拍拍, 加油哦。
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-9-15 17:07:26 | 显示全部楼层
问:
第二题是给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个数组里的,数组的每个元素就是一个节点,节点包含了它的index以及它的parent的index,而不是children的index哦,所以这棵树是从child指向parent的。最后是给我这个数组和一个节点的index,让我删除这个index以及它的子树,只能用O(n)的空间复杂度,而且大小是确定好的
答:可以用并查集吗?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-15 19:51:01 | 显示全部楼层
ybxsnail 发表于 2015-9-15 13:56
不能用hashmap或hashset之类的,空间在你定义的时候必须是确定的。因为在遍历的过程中你会不断往map里加 ...
. from: 1point3acres.com/bbs
那可以定义一个ArrayList[] 或者 ArrayList<Integer, ArrayList<Integer>>吗?
回复 支持 反对

使用道具 举报

yemingliang 发表于 2015-9-15 21:52:28 | 显示全部楼层
楼主第二题你是咋解的呢!可以自己new 一个queue来把 timestamp 存下来吗?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-15 22:16:36 | 显示全部楼层
yemingliang 发表于 2015-9-15 21:52. more info on 1point3acres.com
楼主第二题你是咋解的呢!可以自己new 一个queue来把 timestamp 存下来吗?

可以用system stack存
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 05:05:13 | 显示全部楼层
yemingliang 发表于 2015-9-15 21:52
楼主第二题你是咋解的呢!可以自己new 一个queue来把 timestamp 存下来吗?

差不多吧,我是把之前用过的timestamp存了一下,方便下次比较
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 05:06:14 | 显示全部楼层
minglotus 发表于 2015-9-15 17:07
问:.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题是给你一棵树,不是binary的,每个节点会有任意个children,然后这棵树是存在一个数组里的,数 ...

感觉可以,但我对并查集不是很熟悉呢
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 05:06:44 | 显示全部楼层
tbu 发表于 2015-9-15 15:33
LZ是海投的么还是?

我是找人内推的
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 05:06:57 | 显示全部楼层
hulahu 发表于 2015-9-15 16:53
拍拍, 加油哦。

嗯嗯,你也加油
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 05:10:13 | 显示全部楼层
wenqiang88 发表于 2015-9-15 19:51
那可以定义一个ArrayList[] 或者 ArrayList吗?

也不行吧,我最后用了一个array他才说可以
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-16 05:20:15 | 显示全部楼层
ybxsnail 发表于 2015-9-16 05:10
也不行吧,我最后用了一个array他才说可以

嗯,可以dfs, 然后用一个array保存中间状态
回复 支持 反对

使用道具 举报

minglotus 发表于 2015-9-16 07:59:57 | 显示全部楼层
ybxsnail 发表于 2015-9-16 05:06
感觉可以,但我对并查集不是很熟悉呢
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
soga~
请问所有的node是已经拓扑排序过的么?
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 11:20:41 | 显示全部楼层
wenqiang88 发表于 2015-9-16 05:20. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
嗯,可以dfs, 然后用一个array保存中间状态

不是很明白,这样的话复杂度是多少呢
回复 支持 反对

使用道具 举报

 楼主| ybxsnail 发表于 2015-9-16 11:22:10 | 显示全部楼层
minglotus 发表于 2015-9-16 07:59
soga~
请问所有的node是已经拓扑排序过的么?

没有排序过,你这么一说我想起来面试官还说数组的顺序的打乱的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 04:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表