一亩三分地论坛

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

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

two sigma 1.4 onsite面经

[复制链接] |试试Instant~ |关注本帖
又见紫风铃 发表于 2016-1-5 03:59:14 | 显示全部楼层 |阅读模式

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

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

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

x
都是原题,也基本都做出来了,可能有一个小bug被指出过,但还是只面了半天就被赶走了,本来也没有要去,bar感觉还是相当高的,当是在NYC downtown高楼欣赏风景了吧
我在沙发把我的code附上好了

1. ABC小哥面的
逆波兰表达式的OOD,数组删除子树
2. 一个白大叔,给的名片上写的还是harvard教parallel computing的teaching fellow,MIT编程竞赛最佳project,小学开始programming,很屌的样子。。。
两个timestamp流输出差值小于一定范围的pair,访问网页慢如何查原因
3. 一个国人姐姐
wildcard matching
和其他面经一样要尽量多写testcase,要用unit test,我用的Python,怎么写test忘了。。还当场又查了下写的
. From 1point 3acres bbs
几点提一下:
1. 在问访问网页慢查原因的问题上估计扣分比较多,挂的最大原因可能就是这个吧。从client,network, server, database几个方面说可能导致慢的问题倒没什么,然后细说到怎么experiment验证为什么是哪一部分的问题之类的就开始瞎扯面试官不太满意了,然后还有server side怎么handle million级qps之类的问题,不同地方的dns怎么对应不同server的ip的问题感觉都回答得不好。感觉整个system, architecture相关的知识还是欠缺了,都只知道一点,一细问就不会了,特别是实际怎么检测问题基本上不知道。
2. wildcard matching直接上了近似O(m+n)的方法,面试官问我是不是见过,我老实交代见过了,因为这个方法不好想,然后说了又更容易理解的二维dp的方法。这个写得比较快,面试官就让我写了随机生成string和pattern的函数,感觉都挺满意的。然后还有时间就让我详细解释了wildcard matching的算法。。感觉解释得不是太清晰,可能她有点觉得我像是背答案的吧(确实多少有点是背了的。。。)这个可能也扣分了。然后诱导我说这种方法是greedy,我没说出来
3. 第一和第三面要上机,vim的快捷键用得不熟,还被指正了。。不知道这个是不是也算在bar的扣分点了。。

评分

5

查看全部评分

 楼主| 又见紫风铃 发表于 2016-1-5 04:02:16 | 显示全部楼层
Reverse Polish Notation. 1point 3acres 璁哄潧
  1. from abc import abstractmethod
  2. class Token(object):
  3.     @abstractmethod
  4.     def isValue(self): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         pass

  6.     @abstractmethod. more info on 1point3acres.com
  7.     def execute(self, stack): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         pass
  9. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10. class Operand(Token):
  11.     def __init__(self, value=None):
  12.         self.value = value

  13.     def isValue(self):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.         return True

  15.     def getValue(self):
  16.         return self.value

  17.     def setValue(self, x):
  18.         self.value = x

  19.     def execute(self, stack):
  20.         stack.append(self.value)

  21. class Operator(Token):
  22.     def __init__(self, mark=None, cal=None):. 1point3acres.com/bbs
  23.         self.mark = mark
  24.         self.cal = cal

  25.     def isValue(self):-google 1point3acres
  26.         return False

  27.     def getOperation(self):
  28.         return self.mark

  29.     def execute(self, stack):
  30.         try:
  31.             num2 = stack.pop()
  32.             num1 = stack.pop()
  33.         except:
  34.             print 'Invalid notation!'
  35.             raise
  36. -google 1point3acres
  37.         res = self.cal(num1, num2)
  38.         stack.append(res)
  39. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40. class OperationFactory(object):
  41.     def __init__(self):
  42.         self.map = {}
  43.         self.map['+'] = lambda x, y: x+y
  44.         self.map['-'] = lambda x, y: x-y. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  45.         self.map['*'] = lambda x, y: x*y. 1point3acres.com/bbs
  46.         self.map['/'] = lambda x, y: x/y if x*y>0 else -(abs(x)/abs(y))

  47.     def create(self, s):
  48.         if s not in self.map:
  49.             return Operand(int(s))
  50.         else:
  51.             return Operator(s, self.map[s])

  52. if __name__ == "__main__":
  53.     inputList = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
  54.     # inputList = ['10', '3', '+', '7', '-']. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  55.     factory = OperationFactory()
  56.     stack = []
  57.     for i in inputList:. visit 1point3acres.com for more.
  58.         token = factory.create(i). Waral 鍗氬鏈夋洿澶氭枃绔,
  59.         token.execute(stack)

  60.     print stack
复制代码

Delete substree
  1. class Node:
  2.     def __init__(self, index, value, valid=True):
  3.         self.parentIndex = index
  4.         self.value = value
  5.         self.valid = valid
  6.         self.visited = False
  7. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  8. def deleteNode(nodes, index):
  9.     nodes[index].valid = False
  10.     nodes[index].visited = True
  11.     for i in range(len(nodes)):
  12.         if nodes[i].visited:-google 1point3acres
  13.             continue
  14.         search(nodes, i)
    .鏈枃鍘熷垱鑷1point3acres璁哄潧

  15. def search(nodes, index):. From 1point 3acres bbs
  16.     if nodes[index].parentIndex == -1 or nodes[index].visited:
  17.         nodes[index].visited = True
  18.         return nodes[index].valid
  19.     nodes[index].visited = True
  20.     nodes[index].valid = search(nodes, nodes[index].parentIndex)
  21.     return nodes[index].valid

  22. A = Node(-1, 'A')
  23. B = Node(4, 'B')
  24. C = Node(1, 'C')
  25. D = Node(1, 'D')
  26. E = Node(4, 'E')
  27. F = Node(6, 'F')
  28. G = Node(3, 'G')
  29. nodes = [C, B, G, D, A, F, E]
  30. deleteNode(nodes, 0)
  31. for i in range(len(nodes)):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.     print nodes[i].value, nodes[i].valid
复制代码


Timestamp Stream Pairs

  1. from threading import Thread
  2. import threading. From 1point 3acres bbs
  3. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4. class Stream:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.     def __init__(self, nums):
  6.         self.nums = nums
  7.         self.index = 0
  8. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     def getNext(self):
  10.         if self.index < len(self.nums):
  11.             self.index += 1
  12.             return self.nums[self.index-1]
  13.         else:
  14.             raise

  15. res = []
  16. q1 = []
  17. q2 = []
  18. threadLock = threading.Lock()

  19. def calculatePairs(q1, q2, value):
  20.     q1.append(value)
  21.     # print q1, q2
  22.     while q2 and value - q2[0] >= 1:
  23.         q2.pop(0)-google 1point3acres
  24.     for num in q2:
  25.         if abs(num - value) < 1:
  26.             res.append((value, num))
  27. . From 1point 3acres bbs
  28. s1 = Stream([0.2, 1.4, 3.0])
  29. s2 = Stream([2.0, 2.1, 4.5])
  30. def Q1Thead(s):
  31.     while True:. 鍥磋鎴戜滑@1point 3 acres
  32.         try:
  33.             value = s.getNext()
  34.             threadLock.acquire()
  35.             calculatePairs(q1, q2, value)
  36.             threadLock.release()
  37.         except:
  38.             break

  39. def Q2Thead(s):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  40.     while True:
  41.         try:
  42.             value = s.getNext().鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.             threadLock.acquire()
  44.             calculatePairs(q2, q1, value)
  45.             threadLock.release()
  46.         except:
  47.             break. 1point3acres.com/bbs

  48. try:
  49.     new_thread1=Thread(target = Q1Thead, args = (s1,))
  50.     new_thread1.setDaemon(True). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  51.     new_thread1.start()
  52.     new_thread2=Thread(target = Q2Thead, args = (s2,))
  53.     new_thread2.setDaemon(True)
  54.     new_thread2.start()
  55. except:
  56.    print "Error: unable to start thread"

  57. print res
复制代码
.1point3acres缃
-google 1point3acres
Wildcard Matching

  1. class Solution(object):
  2.     def isMatch(self, s, p):
  3.         """. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.         :type s: str. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5.         :type p: str
  6.         :rtype: bool. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.         """
  8.         sIndex = pIndex = 0
  9.         sMatch = 0
  10.         pStar = -1
  11.         while sIndex < len(s):. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.             if pIndex < len(p) and (p[pIndex] == s[sIndex] or p[pIndex] == '?'):
  13.                 sIndex += 1
  14.                 pIndex += 1
  15.             elif pIndex < len(p) and p[pIndex] == '*':. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 sMatch = sIndex
  17.                 pStar = pIndex
  18.                 pIndex += 1
  19.             elif pStar != -1:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.                 sMatch += 1
  21.                 sIndex = sMatch
  22.                 pIndex = pStar + 1
  23.             else:
  24.                 return False. From 1point 3acres bbs
  25.         
  26.         while pIndex < len(p) and p[pIndex] == '*':. more info on 1point3acres.com
  27.             pIndex += 1
  28.         
  29.         return pIndex == len(p)
复制代码

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

kaywsy 发表于 2016-1-5 04:12:27 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!
. from: 1point3acres.com/bbs
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

kaywsy 发表于 2016-1-5 04:12:57 | 显示全部楼层
上条手抖了,来给卓神点个赞~
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-1-5 04:32:03 | 显示全部楼层
楼主这些code如何来的?全都是现场写完。然后email给自己?有点厉害....国人姐姐呆很久了么?没呆很久估计也是地里的..所以才猜到楼主做过...用vim不成熟。应该会被记录下去的。我当时写java。写main method少个static都直接被指正..楼主加油。会有更好的offer。
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-5 04:35:58 | 显示全部楼层
leixiang5 发表于 2016-1-5 04:32
楼主这些code如何来的?全都是现场写完。然后email给自己?有点厉害....国人姐姐呆很久了么?没呆很久估计 ...

没有,这不是我现场写的code,是准备的时候自己写了一遍,现场写的基本也是差不多的。
想用text editor像atom, sublime这种都木有,eclipse木有python plugin,只有强行用vim了。。本来想复制的应该是yy,结果点成了dd,把一行删除了。。直接被鄙视了。。。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-1-5 04:40:51 | 显示全部楼层
又见紫风铃 发表于 2016-1-5 04:35
没有,这不是我现场写的code,是准备的时候自己写了一遍,现场写的基本也是差不多的。
想用text editor ...

这样啊。好吧。
加油!他他们onsite坚持到全天的也20%成功率。

补充内容 (2016-1-5 04:41):
听说他们onsite
回复 支持 反对

使用道具 举报

LYJALEX__ 发表于 2016-1-5 08:50:32 | 显示全部楼层
应该是第二面挂的。很牛的白哥哥对人要求一般也比较严苛。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-1-5 10:04:23 | 显示全部楼层
LYJALEX__ 发表于 2016-1-5 08:50
应该是第二面挂的。很牛的白哥哥对人要求一般也比较严苛。
. from: 1point3acres.com/bbs
要看人吧?有些人很nice的。很牛但是还是很谦虚。
回复 支持 反对

使用道具 举报

LYJALEX__ 发表于 2016-1-5 17:29:51 | 显示全部楼层
删除子树那题可以用别的语言吗?
听说给的代码是c语言?
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-5 21:27:42 | 显示全部楼层
LYJALEX__ 发表于 2016-1-5 17:29
删除子树那题可以用别的语言吗?
听说给的代码是c语言?

可以的,代码有c java和python三种版本的
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2016-1-5 23:02:10 | 显示全部楼层
话说怎么写Unit test啊,我以前写都是有模版照着改下就行了
回复 支持 反对

使用道具 举报

 楼主| 又见紫风铃 发表于 2016-1-5 23:29:56 | 显示全部楼层
sevenwonder 发表于 2016-1-5 23:02
话说怎么写Unit test啊,我以前写都是有模版照着改下就行了

我当时也就是在网上搜了下模板,然后改了下
回复 支持 反对

使用道具 举报

wssf 发表于 2016-1-5 23:59:09 | 显示全部楼层
只能用vim?这也太不人性化了。。
回复 支持 反对

使用道具 举报

tangvictor 发表于 2016-2-21 06:02:58 | 显示全部楼层
请问楼主删除子树那题是他提供代码?只有class TreeNode吗?
回复 支持 反对

使用道具 举报

芥末青豆 发表于 2016-3-31 09:50:03 | 显示全部楼层
楼主怎么写test wildcard matching 的函数的,使用了unit test 吗? 怎么自动生成original string 和 pattern string pair 的?
回复 支持 反对

使用道具 举报

qiuqiyuan 发表于 2016-5-11 02:11:36 | 显示全部楼层
楼主这个多线程的题目感觉好奇怪啊。
回复 支持 反对

使用道具 举报

seekingJob320 发表于 2016-5-20 02:59:25 | 显示全部楼层
谢谢楼主分享 能去onsite已经很厉害了
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-5-26 12:36:47 | 显示全部楼层
楼主上机是windows还是mac啊
回复 支持 反对

使用道具 举报

ivanml 发表于 2016-7-10 04:12:04 | 显示全部楼层
又见紫风铃 发表于 2016-1-5 04:02
Reverse Polish Notation

Delete substree

求问一下楼主那道timestamp的题,对于
s1 = Stream([0.2, 1.4, 3.0])
s2 = Stream([2.0, 2.1, 4.5])
如果calculate中,比较0.2和2.1时发现差值>1,然后就把2.1 pop掉了,那这样的话岂不是1.4进行比较的时候,就miss掉了[1.4, 2.1]这一对了吗?

还有能否详细解释下为什么要加锁呢,不加会发生什么情况呢?
谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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