May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 10357|回复: 30
收起左侧

two sigma 1.4 onsite面经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

1. ABC小哥面的. visit 1point3acres.com for more.
逆波兰表达式的OOD,数组删除子树
2. 一个白大叔,给的名片上写的还是harvard教parallel computing的teaching fellow,MIT编程竞赛最佳project,小学开始programming,很屌的样子。。。
两个timestamp流输出差值小于一定范围的pair,访问网页慢如何查原因
3. 一个国人姐姐
wildcard matching
和其他面经一样要尽量多写testcase,要用unit test,我用的Python,怎么写test忘了。。还当场又查了下写的

几点提一下:
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的扣分点了。。

评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 又见紫风铃 发表于 2016-1-5 04:02:16 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
Reverse Polish Notation
  1. from abc import abstractmethod
  2. class Token(object):. 1point3acres.com/bbs
  3.     @abstractmethod
  4.     def isValue(self):
  5.         pass

  6.     @abstractmethod-google 1point3acres
  7.     def execute(self, stack):
  8.         pass
  9. .1point3acres缃
  10. class Operand(Token):
  11.     def __init__(self, value=None):
  12.         self.value = value
  13. -google 1point3acres
  14.     def isValue(self):
  15.         return True

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

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

  20. . 1point 3acres 璁哄潧
  21.     def execute(self, stack):-google 1point3acres
  22.         stack.append(self.value)

  23. class Operator(Token):
  24.     def __init__(self, mark=None, cal=None):
  25.         self.mark = mark.鐣欏璁哄潧-涓浜-涓夊垎鍦
  26.         self.cal = cal

  27.     def isValue(self):
  28.         return False. Waral 鍗氬鏈夋洿澶氭枃绔,

  29.     def getOperation(self):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.         return self.mark

  31.     def execute(self, stack):
  32.         try:
  33.             num2 = stack.pop()
  34.             num1 = stack.pop(). 1point 3acres 璁哄潧
  35.         except:. Waral 鍗氬鏈夋洿澶氭枃绔,
  36.             print 'Invalid notation!'
  37.             raise

  38.         res = self.cal(num1, num2)
  39.         stack.append(res)
  40. . 1point 3acres 璁哄潧
  41. class OperationFactory(object):
  42.     def __init__(self):.1point3acres缃
  43.         self.map = {}
  44.         self.map['+'] = lambda x, y: x+y
  45.         self.map['-'] = lambda x, y: x-y
  46.         self.map['*'] = lambda x, y: x*y
  47.         self.map['/'] = lambda x, y: x/y if x*y>0 else -(abs(x)/abs(y)). 1point 3acres 璁哄潧

  48.     def create(self, s):
  49.         if s not in self.map:. 鍥磋鎴戜滑@1point 3 acres
  50.             return Operand(int(s))
  51.         else:
  52.             return Operator(s, self.map[s]). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  53. if __name__ == "__main__":. from: 1point3acres.com/bbs
  54.     inputList = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
  55.     # inputList = ['10', '3', '+', '7', '-']
  56.     factory = OperationFactory()
  57.     stack = []. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  58.     for i in inputList:
  59.         token = factory.create(i)
  60.         token.execute(stack)-google 1point3acres

  61.     print stack
复制代码

Delete substree. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. From 1point 3acres bbs


  7. def deleteNode(nodes, index):. 1point3acres.com/bbs
  8.     nodes[index].valid = False
  9.     nodes[index].visited = True
  10.     for i in range(len(nodes)):. from: 1point3acres.com/bbs
  11.         if nodes[i].visited:. 1point 3acres 璁哄潧
  12.             continue
  13.         search(nodes, i)

  14. def search(nodes, index):
  15.     if nodes[index].parentIndex == -1 or nodes[index].visited:
  16.         nodes[index].visited = True. From 1point 3acres bbs
  17.         return nodes[index].valid. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.     nodes[index].visited = True
  19.     nodes[index].valid = search(nodes, nodes[index].parentIndex)
  20.     return nodes[index].valid

  21. A = Node(-1, 'A')
  22. B = Node(4, 'B')
  23. C = Node(1, 'C')
  24. D = Node(1, 'D')
  25. E = Node(4, 'E')
  26. F = Node(6, 'F')
  27. G = Node(3, 'G')
  28. nodes = [C, B, G, D, A, F, E]. 鍥磋鎴戜滑@1point 3 acres
  29. deleteNode(nodes, 0)
  30. for i in range(len(nodes)):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  31.     print nodes[i].value, nodes[i].valid
复制代码


Timestamp Stream Pairs

  1. from threading import Thread
  2. import threading
  3. . Waral 鍗氬鏈夋洿澶氭枃绔,
  4. class Stream:
  5.     def __init__(self, nums):
  6.         self.nums = nums
  7.         self.index = 0

  8.     def getNext(self):
  9.         if self.index < len(self.nums):
  10.             self.index += 1
  11.             return self.nums[self.index-1]
  12.         else:
  13.             raise
  14. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15. res = []
  16. q1 = []. Waral 鍗氬鏈夋洿澶氭枃绔,
  17. q2 = []
  18. threadLock = threading.Lock()

  19. def calculatePairs(q1, q2, value): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.     q1.append(value)
  21.     # print q1, q2-google 1point3acres
  22.     while q2 and value - q2[0] >= 1:
  23.         q2.pop(0)
  24.     for num in q2:
  25.         if abs(num - value) < 1:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  26.             res.append((value, num))

  27. s1 = Stream([0.2, 1.4, 3.0])
  28. s2 = Stream([2.0, 2.1, 4.5])
  29. def Q1Thead(s):. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.     while True:
  31.         try:
  32.             value = s.getNext(). more info on 1point3acres.com
  33.             threadLock.acquire()
  34.             calculatePairs(q1, q2, value)
  35.             threadLock.release()
  36.         except:
  37.             break

  38. def Q2Thead(s):
  39.     while True:
  40.         try:
  41.             value = s.getNext(). 1point 3acres 璁哄潧
  42.             threadLock.acquire()
  43.             calculatePairs(q2, q1, value). Waral 鍗氬鏈夋洿澶氭枃绔,
  44.             threadLock.release()
  45.         except:
  46.             break

  47. try:
  48.     new_thread1=Thread(target = Q1Thead, args = (s1,)). from: 1point3acres.com/bbs
  49.     new_thread1.setDaemon(True)
  50.     new_thread1.start(). 1point3acres.com/bbs
  51.     new_thread2=Thread(target = Q2Thead, args = (s2,)).鏈枃鍘熷垱鑷1point3acres璁哄潧
  52.     new_thread2.setDaemon(True)
  53.     new_thread2.start()
  54. except:
  55.    print "Error: unable to start thread"

  56. print res
复制代码
. 1point 3acres 璁哄潧

Wildcard Matching

  1. class Solution(object):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.     def isMatch(self, s, p):. 1point3acres.com/bbs
  3.         """. 鍥磋鎴戜滑@1point 3 acres
  4.         :type s: str
  5.         :type p: str
  6.         :rtype: bool
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.         """
  8.         sIndex = pIndex = 0
  9.         sMatch = 0
    . visit 1point3acres.com for more.
  10.         pStar = -1
  11.         while sIndex < len(s):
  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. From 1point 3acres bbs
  17.                 pStar = pIndex
  18.                 pIndex += 1. 1point3acres.com/bbs
  19.             elif pStar != -1:
  20.                 sMatch += 1
  21.                 sIndex = sMatch
  22.                 pIndex = pStar + 1
  23.             else:
  24.                 return False
  25.         
  26.         while pIndex < len(p) and p[pIndex] == '*':.1point3acres缃
  27.             pIndex += 1
  28.         
  29.         return pIndex == len(p)
复制代码

评分

2

查看全部评分

回复 支持 4 反对 0

使用道具 举报

kaywsy 发表于 2016-1-5 04:12:27 | 显示全部楼层
关注一亩三分地微博:
Warald
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

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.1point3acres缃
没有,这不是我现场写的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
应该是第二面挂的。很牛的白哥哥对人要求一般也比较严苛。

要看人吧?有些人很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. from: 1point3acres.com/bbs
话说怎么写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 的?. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

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. more info on 1point3acres.com

.1point3acres缃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]这一对了吗?

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-28 09:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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