一亩三分地论坛

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

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

Twitter新鲜onsite面经

[复制链接] |试试Instant~ |关注本帖
Luna_gln 发表于 2016-5-19 12:17:36 | 显示全部楼层 |阅读模式

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

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

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

x
5月17号刚刚twitter san francisco面试完回来,今天就收到了拒信也是很心酸,特来回馈地里:
所有的面试官开始都会花10-15分钟介绍一下自己的组并了解一下你的背景信息。.鐣欏璁哄潧-涓浜-涓夊垎鍦

1. 一个印度大叔,engineering manager级别的,leetcode原题:https://leetcode.com/problems/coin-change/


2. 一个印度小哥,senior engineer,比如有字典里有{cat, bat, pat, twitter},现在给你一个string s和一个integer k, 比如说“eat", 2, 让你找出所以与s的edit distance为k的string并输出来。这里就输出[cat, bat, pat].用trie数做。
3. 一个白人小哥,说话超快。问了查重,给你一个数组和一个数n, 数组里的数由1-n组成。现在让你找出重复的数,in-space, nlogn的时间复杂。用二分查找。先找出重复的数在1-n/2还是n/2 + 1 - n. 这样不段缩小范围,最后得到结果。
4. 可能是一个abc吧,之前做startup,后来被twitter收购了。问了系统设计的题,shorten url.
5. 白人妹子。第一题: https://leetcode.com/problems/word-break/,第二题:忘了,想起来再补充吧

大米~~

@刘琦627

评分

2

查看全部评分

 楼主| Luna_gln 发表于 2016-5-24 10:17:00 | 显示全部楼层
jiebour 发表于 2016-5-24 09:54
公司快倒闭了。。。。

这样想想我心里就好受些了哈哈
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2016-5-19 12:47:46 | 显示全部楼层
第二题你输出的string的edit distance明明是1啊。。。。
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-5-19 13:18:23 来自手机 | 显示全部楼层
嗯对,我没写清楚不好意思,他其实问了两个,一个是输出prefix相同的所有string,然后是输出所有edit distance 为k的string
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-19 13:41:43 | 显示全部楼层
感谢分享。问一下楼主第三天是sorted吗?另外可不可以直接全部加起来的和减去 1 到n-1的和?
回复 支持 反对

使用道具 举报

zxcnn 发表于 2016-5-19 14:31:21 | 显示全部楼层
楼主是new grad吗?
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-5-21 23:14:13 | 显示全部楼层
Mark6 发表于 2016-5-19 13:41
感谢分享。问一下楼主第三天是sorted吗?另外可不可以直接全部加起来的和减去 1 到n-1的和?

不是sort,是每次取中间值,然后所有的数比较,计算出比中间值小的数的个数和比中间值大的个数,如果哪一边个数多的话,就说明重复的数出现在这一边,这样就可以继续只对这半边做运算,所以时间复杂度就是nlgn了
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-5-21 23:14:36 | 显示全部楼层
zxcnn 发表于 2016-5-19 14:31
楼主是new grad吗?

是呀是呀
回复 支持 反对

使用道具 举报

zxcnn 发表于 2016-5-22 10:41:18 | 显示全部楼层

请问是找的内推吗?内推后会有邮件回复吗?
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-5-24 04:22:16 | 显示全部楼层
zxcnn 发表于 2016-5-22 10:41
请问是找的内推吗?内推后会有邮件回复吗?

是找的内推,好像没有,没过几天直接给的oa
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-5-24 05:00:07 | 显示全部楼层
sophie629 发表于 2016-5-24 04:44
楼主是哪里没答好么?还是 答得还可以竟然拒了。。

是啊,我也挺纳闷的,题目都做出来了,也都聊得挺开心,但是回来不久就给发了据信,还说不能给feedback。要是有过来人,也想讨教一下这种情况是怎么回事。之前看glassdoor上也有人反应过这种情况。
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-5-24 09:54:04 | 显示全部楼层
Luna_gln 发表于 2016-5-24 05:00 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
是啊,我也挺纳闷的,题目都做出来了,也都聊得挺开心,但是回来不久就给发了据信,还说不能给feedback。 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
公司快倒闭了。。。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-24 22:28:50 | 显示全部楼层
Luna_gln 发表于 2016-5-21 23:14
不是sort,是每次取中间值,然后所有的数比较,计算出比中间值小的数的个数和比中间值大的个数,如果哪一 ...

喔喔,那是lc 287哈。。
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-5-24 22:32:19 | 显示全部楼层
Luna_gln 发表于 2016-5-24 05:00
是啊,我也挺纳闷的,题目都做出来了,也都聊得挺开心,但是回来不久就给发了据信,还说不能给feedback。 ...

patpat,我也是第二天收到了拒信。。不给feedback。。没事,面完就不管了吧。。
回复 支持 反对

使用道具 举报

皮蛋豆腐 发表于 2016-5-24 22:39:11 | 显示全部楼层
第二题就是airbnb的k edit distance嘛,twitter出这么难的题,招的到人么我在想?除了第二题,其他都还行。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
naive解法,求出list里所有word和target的edit distance,O(kn^2)。然后用trie剪枝优化,时间复杂度一样。正好写过这题,发过来给大家参考一下。

  1. from collections import defaultdict
  2. class TrieNode:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.     def __init__(self, w=''):
  4.         self.dp = [0]
  5.         self.word = w
  6.         self.children = defaultdict()

  7.         # convert from edit distance equation:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.         # let dp[i][j] denotes the shortest edit distance from word1[:i] to word2[:j]. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.         # if word1[i] == word2[j]: dp[i][j] = dp[i-1][j-1]
  10.         # else dp[i][j] = dp[i-i][j-1] + 1 : replace
  11.         #               or dp[i][j-1] + 1: remove
  12.         #               or dp[i-1][j] + 1: insert
  13. class EditDistance:
  14.     def find_words_with_k_ed(self, dict, target, k):
  15.         # find all words in the dictionary whose edit distance are no more than k with the target word. more info on 1point3acres.com
  16.         # build trie. 鍥磋鎴戜滑@1point 3 acres
  17.         # if target[i] == word[i]: cur_trienode.dp[i] = previous_trienode.dp[i-1]
  18.         # else: cur_trienode.dp[i] = min(previous_trienode.dp[i-1], cur_trienode.dp[i-1], previous_trienode.dp[i]) + 1
  19.         # if cur_trienode.dp[i] > k: break. more info on 1point3acres.com
  20.         root = TrieNode()
  21.         root.dp = range(len(target)+1)
  22.         res = []
  23.         for w in dict:
  24.             cur = root
  25.             for i, c in enumerate(w):
  26.                 if c not in cur.children:
  27.                     if i == len(w) - 1: child = TrieNode(w).鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.                     else: child = TrieNode(). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  29.                     cur.children[c] = child
  30.                     cur = child. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.                 else: cur = cur.children[c]

  32.         for w in dict:
  33.             cur_node = root-google 1point3acres
  34.             prev_node = root-google 1point3acres
  35.             for j, w_char in enumerate(w):
  36.                 cur_node = cur_node.children[w_char]
  37.                 cur_node.dp[0] = j + 1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  38.                 if len(cur_node.dp) != len(target)+1:
  39.                     for i, t_char in enumerate(target):
  40.                         prev_dp = prev_node.dp[i]
  41.                         if t_char == w_char:. 鍥磋鎴戜滑@1point 3 acres
  42.                             cur_node.dp.append(prev_dp)
  43.                         else:
  44.                             min_dist = min(prev_node.dp[i], cur_node.dp[i], prev_node.dp[i+1]) + 1
  45.                             cur_node.dp.append(min_dist).1point3acres缃
  46.                 if cur_node.word != '' and cur_node.dp[-1] <= k:
  47.                     res.append(cur_node.word)
  48.                 prev_node = cur_node
  49.         return res

  50. s=EditDistance()
  51. dict = ['hello', 'hella', 'hellu', 'helli', 'dillo', 'dhleo', 'ajleo']
  52. target = 'ell'
  53. similar_words = s.find_words_with_k_ed(dict, target, 2). From 1point 3acres bbs
  54. assert similar_words == ['hello', 'hella', 'hellu', 'helli']



  55. . from: 1point3acres.com/bbs




  56. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


复制代码
回复 支持 反对

使用道具 举报

wangzhe890703 发表于 2016-6-1 05:36:59 | 显示全部楼层
请问楼主 twitter的hr最后是电话还是邮件通知的面试结果啊
回复 支持 反对

使用道具 举报

 楼主| Luna_gln 发表于 2016-8-29 13:20:52 | 显示全部楼层
wangzhe890703 发表于 2016-6-1 05:36
请问楼主 twitter的hr最后是电话还是邮件通知的面试结果啊

邮件通知的面试结果
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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