一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 12920|回复: 31
收起左侧

two sigma 1.4 onsite面经

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

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

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

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

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

1. ABC小哥面的
逆波兰表达式的OOD,数组删除子树
2. 一个白大叔,给的名片上写的还是harvard教parallel computing的teaching fellow,MIT编程竞赛最佳project,小学开始programming,很屌的样子。。。
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

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,我没说出来.1point3acres缃
3. 第一和第三面要上机,vim的快捷键用得不熟,还被指正了。。不知道这个是不是也算在bar的扣分点了。。

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 又见紫风铃 发表于 2016-1-5 04:02:16 | 显示全部楼层
Reverse Polish Notation
  1. from abc import abstractmethod
  2. class Token(object):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.     @abstractmethod
  4.     def isValue(self):
  5.         pass

  6.     @abstractmethod
  7.     def execute(self, stack):
  8.         pass

  9. class Operand(Token):
  10.     def __init__(self, value=None):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  11.         self.value = value

  12.     def isValue(self):
  13.         return True

  14.     def getValue(self):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.         return self.value

  16.     def setValue(self, x):
  17.         self.value = x.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

  20. class Operator(Token):
  21.     def __init__(self, mark=None, cal=None):
  22.         self.mark = mark
  23.         self.cal = cal
  24. . From 1point 3acres bbs
  25.     def isValue(self):
  26.         return False.1point3acres缃

  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.         res = self.cal(num1, num2).鐣欏璁哄潧-涓浜-涓夊垎鍦
  37.         stack.append(res)

  38. class OperationFactory(object):
  39.     def __init__(self):
  40.         self.map = {}
  41.         self.map['+'] = lambda x, y: x+y
  42.         self.map['-'] = lambda x, y: x-y
  43.         self.map['*'] = lambda x, y: x*y 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  44.         self.map['/'] = lambda x, y: x/y if x*y>0 else -(abs(x)/abs(y))

  45.     def create(self, s):. from: 1point3acres.com/bbs
  46.         if s not in self.map:
  47.             return Operand(int(s))
  48.         else:
  49.             return Operator(s, self.map[s])

  50. if __name__ == "__main__":
  51.     inputList = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
  52.     # inputList = ['10', '3', '+', '7', '-']
  53.     factory = OperationFactory(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  54.     stack = []
  55.     for i in inputList:
  56.         token = factory.create(i)
  57.         token.execute(stack)
  58. . visit 1point3acres.com for more.
  59.     print stack
复制代码

Delete substree
  1. class Node:. visit 1point3acres.com for more.
  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. def deleteNode(nodes, index):
  8.     nodes[index].valid = False
  9.     nodes[index].visited = True
  10.     for i in range(len(nodes)):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         if nodes[i].visited:
  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. 鍥磋鎴戜滑@1point 3 acres
  17.         return nodes[index].valid. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.     nodes[index].visited = True. visit 1point3acres.com for more.
  19.     nodes[index].valid = search(nodes, nodes[index].parentIndex)
  20.     return nodes[index].valid

  21. A = Node(-1, 'A'). more info on 1point3acres.com
  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'). from: 1point3acres.com/bbs
  27. G = Node(3, 'G')
  28. nodes = [C, B, G, D, A, F, E]
  29. deleteNode(nodes, 0). Waral 鍗氬鏈夋洿澶氭枃绔,
  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. class Stream:
  4.     def __init__(self, nums):. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.         self.nums = nums. From 1point 3acres bbs
  6.         self.index = 0

  7.     def getNext(self): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         if self.index < len(self.nums):
  9.             self.index += 1
  10.             return self.nums[self.index-1]. Waral 鍗氬鏈夋洿澶氭枃绔,
  11.         else:
  12.             raise

  13. res = []
  14. q1 = []
  15. q2 = []. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16. threadLock = threading.Lock(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17. . from: 1point3acres.com/bbs
  18. def calculatePairs(q1, q2, value):
  19.     q1.append(value)
  20.     # print q1, q2
  21.     while q2 and value - q2[0] >= 1:
  22.         q2.pop(0)
  23.     for num in q2:. 1point 3acres 璁哄潧
  24.         if abs(num - value) < 1:
  25.             res.append((value, num))
  26. . visit 1point3acres.com for more.
  27. s1 = Stream([0.2, 1.4, 3.0])
  28. s2 = Stream([2.0, 2.1, 4.5])
  29. def Q1Thead(s):. From 1point 3acres bbs
  30.     while True:. visit 1point3acres.com for more.
  31.         try:
  32.             value = s.getNext()
  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()
  42.             threadLock.acquire()
  43.             calculatePairs(q2, q1, value)
  44.             threadLock.release()
  45.         except:
  46.             break

  47. try:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.     new_thread1=Thread(target = Q1Thead, args = (s1,))
  49.     new_thread1.setDaemon(True)
  50.     new_thread1.start(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  51.     new_thread2=Thread(target = Q2Thead, args = (s2,))
  52.     new_thread2.setDaemon(True)
  53.     new_thread2.start()
  54. except:
  55.    print "Error: unable to start thread"

  56. print res
复制代码


Wildcard Matching

  1. class Solution(object):. 1point 3acres 璁哄潧
  2.     def isMatch(self, s, p):
  3.         """-google 1point3acres
  4.         :type s: str
  5.         :type p: str
  6.         :rtype: bool
  7.         """
  8.         sIndex = pIndex = 0-google 1point3acres
  9.         sMatch = 0
  10.         pStar = -1
  11.         while sIndex < len(s):. 1point3acres.com/bbs
  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] == '*':.鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.                 sMatch = sIndex
  17.                 pStar = pIndex
  18.                 pIndex += 1. visit 1point3acres.com for more.
  19.             elif pStar != -1:
  20.                 sMatch += 1. From 1point 3acres bbs
  21.                 sIndex = sMatch
  22.                 pIndex = pStar + 1
  23.             else:
  24.                 return False
  25.         
  26.         while pIndex < len(p) and p[pIndex] == '*':
  27.             pIndex += 1
  28.         
  29.         return pIndex == len(p)
复制代码

评分

2

查看全部评分

回复 支持 5 反对 0

使用道具 举报

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

使用道具 举报

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,是准备的时候自己写了一遍,现场写的基本也是差不多的。-google 1point3acres
想用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%成功率。
. 1point3acres.com/bbs
补充内容 (2016-1-5 04:41):. 1point 3acres 璁哄潧
听说他们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 | 显示全部楼层
删除子树那题可以用别的语言吗?-google 1point3acres
听说给的代码是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. from: 1point3acres.com/bbs
Reverse Polish Notation

Delete substree

求问一下楼主那道timestamp的题,对于-google 1point3acres
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 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-20 09:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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