求Twitter onsite 经验 (分享些它家的题目)# JobHunting - 待字闺中
p*m
1 楼
我5月初要去Twitter onsite，面的是 Trust & Safety team
2轮电面都比较简单，2个engineers都很nice.
但听说onsite 难度会明显加大, 而且我网上能搜到的它家的题目不多，特别是onsite,
所以心里没底，来版上求经验。
希望有面试经验的同学能和我分享, 如果不方便帖出来，你也可以我站内发信或者
email: d********[email protected]
这是recruiter给我的schedule:
11:30am 去公司签到, 然后面7个人, 其中有个 team Product Manager。每轮45min,
第1轮是 lunch interview,
7轮分别有coding, Ph.D. research presentation, large-scale system design (这
个是open question)
下面是我搜集到的Twitter的题目，有些版上有过了，给后来的同学作参考。
如果你们有新的题, 也可以回在下面.
希望版上它家的信息能多些
+++++++++++++++++++++++++++++++++++++++++++++++++++
* Given a 8-bit string, determine how to find the most reoccuring character
Two ways to approach this.
Maintain a hash of characters (int array of 128 ascii characters) and then
incremement the count. At the end run through the array to find the highest
count instance.
Second method. Sort the string and then count the repeated character
instances. Maintain a highest counter while you count.
* 如何找出最热门的话题(根据tweets)。如果一个话题一直热门，我们不想考虑怎么办
* 如何抽取tweet上一个ID所关注的news，如何抽取这个ID喜欢什么topic
* Twitter实习第一轮电面总结
http://www.mitbbs.com/article/JobHunting/32044687_3.html
http://www.mitbbs.com/article/JobHunting/32065597_3.html
* 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。
* Given an unsorted linked list, remove all of the duplicate numbers
1->5->6->6->5->1
1->5->6
（要time O(n))
思路: 遍历每个节点, 只要遍历一遍即可. 因为第1次出现时, 保存在set中, 今后再出
现就删除
用2个指针, pre/cur. 若出现过的, 从链表中删除, pre.next = cur.next; cur = cur
.next;
用 set 保存出现过的int,
* 给定String，按序输出重复出现的字母。
Input: "TTwitter is nice"
Output: T t i e
* merge two sorted lists. 电面我遇到的原题
1)假设2者都是升序 2)最终结果是merge成1个list, 不用额外空间
比如, 1 -> 3 -> 9 -> 12
2 -> 4 -> 15
(不要用另外个链表, 而是in place merge)
* Find the first common ancestor in a tree
Node ca(root, p, q)
如果p,q在同一边, root = root.child, 即 return ca(root.child, p, q)
若不在同一边, 则 return root
* k-way merge: k个数组, 每个含n个元素, 已经排好序, 现在要把这k个数组 merge起
来, 里面含kn个元素, 也要排好序
follow-up, external sorting http://en.wikipedia.org/wiki/External_sorting
问题正式描述, 见Wikipedia. 因为数据量太大, 不能一次性放入内存中完成排序, 保
存在disk上,
sorted subfiles (每个数组, 都在disk上), 每次只能有一小部分(chunk)进入内存排
序. 结果都写入 a single larger file(也在disk上)
其主要用了 k-way merge 的思想
* Given an array with all elements sorted on each individual row and column
find the K-th smallest one
* given an array of numbers and a number k, find if two numbers in the array
add up to k. Running time, space complexity, standard questions
+++++++++++++++++++++++++++++++++++++++++++++++++++
2轮电面都比较简单，2个engineers都很nice.
但听说onsite 难度会明显加大, 而且我网上能搜到的它家的题目不多，特别是onsite,
所以心里没底，来版上求经验。
希望有面试经验的同学能和我分享, 如果不方便帖出来，你也可以我站内发信或者
email: d********[email protected]
这是recruiter给我的schedule:
11:30am 去公司签到, 然后面7个人, 其中有个 team Product Manager。每轮45min,
第1轮是 lunch interview,
7轮分别有coding, Ph.D. research presentation, large-scale system design (这
个是open question)
下面是我搜集到的Twitter的题目，有些版上有过了，给后来的同学作参考。
如果你们有新的题, 也可以回在下面.
希望版上它家的信息能多些
+++++++++++++++++++++++++++++++++++++++++++++++++++
* Given a 8-bit string, determine how to find the most reoccuring character
Two ways to approach this.
Maintain a hash of characters (int array of 128 ascii characters) and then
incremement the count. At the end run through the array to find the highest
count instance.
Second method. Sort the string and then count the repeated character
instances. Maintain a highest counter while you count.
* 如何找出最热门的话题(根据tweets)。如果一个话题一直热门，我们不想考虑怎么办
* 如何抽取tweet上一个ID所关注的news，如何抽取这个ID喜欢什么topic
* Twitter实习第一轮电面总结
http://www.mitbbs.com/article/JobHunting/32044687_3.html
http://www.mitbbs.com/article/JobHunting/32065597_3.html
* 和twitter很相关的一个问题，根据twitter的follow关系，如何efficiently找到所
有的connected components。有一个很大的文件，每行存一条follow关系的边。基本上
达到hash就差不多对了。会不断问细节，然后如何改进。
* Given an unsorted linked list, remove all of the duplicate numbers
1->5->6->6->5->1
1->5->6
（要time O(n))
思路: 遍历每个节点, 只要遍历一遍即可. 因为第1次出现时, 保存在set中, 今后再出
现就删除
用2个指针, pre/cur. 若出现过的, 从链表中删除, pre.next = cur.next; cur = cur
.next;
用 set 保存出现过的int,
* 给定String，按序输出重复出现的字母。
Input: "TTwitter is nice"
Output: T t i e
* merge two sorted lists. 电面我遇到的原题
1)假设2者都是升序 2)最终结果是merge成1个list, 不用额外空间
比如, 1 -> 3 -> 9 -> 12
2 -> 4 -> 15
(不要用另外个链表, 而是in place merge)
* Find the first common ancestor in a tree
Node ca(root, p, q)
如果p,q在同一边, root = root.child, 即 return ca(root.child, p, q)
若不在同一边, 则 return root
* k-way merge: k个数组, 每个含n个元素, 已经排好序, 现在要把这k个数组 merge起
来, 里面含kn个元素, 也要排好序
follow-up, external sorting http://en.wikipedia.org/wiki/External_sorting
问题正式描述, 见Wikipedia. 因为数据量太大, 不能一次性放入内存中完成排序, 保
存在disk上,
sorted subfiles (每个数组, 都在disk上), 每次只能有一小部分(chunk)进入内存排
序. 结果都写入 a single larger file(也在disk上)
其主要用了 k-way merge 的思想
* Given an array with all elements sorted on each individual row and column
find the K-th smallest one
* given an array of numbers and a number k, find if two numbers in the array
add up to k. Running time, space complexity, standard questions
+++++++++++++++++++++++++++++++++++++++++++++++++++
