发个面经攒人品求过
今早刚面的，recruiter说的是hm聊天，结果面试开始突然发来了个link说interviewer想要code，所以突然变成了技术面，然后并没有准备，不过还好题很简单，但是由于电话不清楚，所以沟通上还是有些问题。下面是具体内容：
上来介绍background，然后为什么想跳槽
電話打來直接做題(只有一題)，完全沒問過去經驗/自我介紹
We want to measure a metric called User Active Minutes (UAM). User active minutes for a given user is defined as the count of the number of distinct minutes in which the user takes some action on Twitter. Multiple actions in the same minute are only counted as one minute. We would like a histogram of the number of users who spend X minutes on Twitter, for different
values of X, given 30 days of raw logs and an interval size in minutes.
The raw logs are in the format: [user_id, epoch timestamp]. Each row represents an action a user took on Twitter. The logs are ordered chronologically. Duplicates are possible.
Write code to compute the histogram of UAMs across our user base.
Example:
Raw logs
[1, 1518290973]
[2, 1518291032]
[3, 1518291095]
[1, 1518291096]
[4, 1518291120]
[3, 1518291178]
[1, 1518291200]
[1, 1518291200]
Interval size
2
Resulting histogram
[2 , 2]
2 users spend 0 - 1 minutes on Twitter
2 users spend 2 - 3 minutes on Twitter
是按照bucket sort做的
interval=2的意思是取两个一分钟统计是，如果等于三 應該是0-2 3-5 6-8
Follower up:
如果數據很大怎辦？MapReduce
感覺面試過程/氣氛一切良好，面試官也似乎滿意我的回答，結果2天后通知掛了
有人知道為什麼嗎…
报个我的
题目其实很简单 设计一个class 有两个function record_event(event, time) 和 get_event_count(event, startTime, endTime) 其实就是record event记录一下这个event在这个时间点触发了 get_event_count就是给定这个event 找到在start和end之间触发的次数
很快做完以后 对方开始follow up 如果这个event很多 那肯定不能存在memory里面 怎么办 如何support twitter size的user 怎么保证 record_event不被block 如何确保没有data loss, database挂了怎么办 bla bla…
我就有点震惊 这不是initial phone screen嘛 怎么有这么多system design question。。。
我也是这题
我面的纽约的revenue组。然而还是稍微有点出入，当时刚拿到有点懵，感觉处理起来挺麻烦。
但是更复杂了一点，精度是参数提供的，可以是 天 小时 分钟。
大概半个小时时候写完了代码，最基本的处理，没有什么花样。估计比较复杂没有写test。然后问了半个小时的follow up， 各种细节。大概就是想要更快就预处理，内存不够就存文件或者数据库，一个机器不够就sharding（hashing， cold/hot partition），sharding的优缺点，如果不能放到数据库内存放不下怎么办，答太老的数据放到s3如果用到再取。
总结：
小哥反馈给的不是很足，老是OK，估计疯狂忙着记笔记。我老是怀疑自己给出的答案不是他想要的，就一直要反馈。这个还是挺重要的。这个也面超时了，感觉是问的爽了没有留时间给我问问题，就又拖了十分钟吧。没听错的话，电话里就说了可以来onsite。感觉不错，面试官很有水平，聊得很开心。
报个挂经
力叩772 - Basic Calculator III https://leetcode.com/problems/basic-calculator-iii/
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces.
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12
这题一开始被问想说是个easy题，用stack就好。
后来发现有点複杂细节很多，没能在时间内写完…
参考
报个过经
友好的面试官，考了calculator.
跟lc不完全一样 好像是只有+和（）
和robinhood面经里提到的很像
用了stack做
总体不是很难 主要面试官态度很和蔼
说你有个Log文档， 记录一个spotify的账户使用情况， 这个账户被很多家人共享了，然后每个人只能做两种操作Play和Pause。
每行log文件格式如下：
操作时间， play,pause, 用户ID
//06:01:43 Play 1
//06:02:43 Pause 1
//06:03:43 Play 1
//08:05:21 Play 2
//08:09:33 Pause 1
//12:33:21 Pause 2
//13:12:10 Play 3
//14:12:10 Pause 3
//00:00:00 Pause All
求这个账户一天总共的活跃时间
比如
//06:01:43 Play 1
//06:02:43 Play 2
//06:03:43 Pause 1
//08:05:21 Pause 2
这个账户总活跃时间就是从06:01:43-08:05:21
Edge Case，如果有个用户只点了Play，没有点Pause的话，那么log最后一行有个Pause All，会让当天所有没有Pause的用户暂定，并且记录时间
LZ当时给了merge interval的nlogn解法，被告知不是最优解。
其实可以用一个int cout=0;来记录当前在听音乐的人数，有人play就count++，当count==1记录起始时间。有人pause就减一，为零时计算时间。O(n)
刚刚挂掉Twitter电面的电话，Recuiter说是A面，刚接电话就大喊“你好啊A很高兴接到您的电话”，然后对面说“你好，我是B”：--------） ～人中超长～
我一开始以为类似于利口刘伞吴，就直接打开利口放一边结果发现差别还是有点大的
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
}
enum Granularity {
MINUTE, HOUR, DAY
}
interface CountingService {
public void recordEvent(String eventType, long timeInMillis);
public long[] getEventCounts(Granularity granularity, String eventType, long startTime, long endTime);
}
}
让你实现一个class实现这俩函数
第一个function
recordEvent(eventType, timeInMillis)：记录一下有新的twitter进来，不用返回啥
eventType: 可能是 push啊 post啊 reply啊之类的
timeInMillis: UNIX time
第二个function
getEventCounts(granularity, eventType, startTime, endTime): 返回一个list，根据granularity分成很多时间段，每个元素是内对应eventType的twitter个数
granularity： 分解粒度
eventType：可能是 push啊 post啊 reply啊之类的，也可能是null
startTime：时间窗起点
endTime：时间窗末点，不一定比starttime大
请问面试者提供了什么信息呢，啥都没有，就只有上面那几行代码，啥都不解释的 ：-------- ） ～人中超长～
光问这些要实现啥参数啥意思有什么corner case就有十分钟，支支吾吾的小哥也说不出来个啥，上面我自己总结的，也是到最后十分钟才终于完全清楚题意
有了start/end，然后按照grad分成一个list，输出每一个window里面的count
第一次尝试：
Map套List套Map，Map<timeInMillis, List<Map<eventType, count>>>
的确是有点复杂，写着写着就写不下去了，也是没太弄清题意的时候就慌着开始写了
第二次尝试：
Map套List，Map<timeInMillis, List>
为啥会有这种想法呢，因为人家没解释eventType啥意思我以为就是event，走上歧途因为没有反馈所以很久才自己发现这个问题
第三次尝试：
Map套List，Map<eventType, List>
给了example，我说能work但很费时，然后小哥问了一下time complexity，直接问怎么improve
第四次尝试：
Map套Map，Map<eventType, Map<timeInMillis, count>>
我自己是觉着这个是OK，反正那哥们没反馈，时间不够只implement了一半
面前半程就很积极不停问问题啊，说思路啊，一边写码一边说啊，然后对面死寂
后半程就实在鸡血不起来了，双方死寂刚刚挂掉
找朋友内推了蓝鸟，很快就收到了recruiter的邮件。时间线如下：
整体感觉蓝鸟非常有效率。对了，组是湾区和西雅图split的，面的是西雅图的职位。等onsite完再回来更新吧
店面： 要求实现一个VersionedHashMap
保存每次变动的历史记录, 每次put的时候版本加1， 然后要实现下面三个api
get(key)
put(key, value)
getAtVersion(Key, VersionNumber)
可以直接用无版本号的爪哇自带哈希表, 只要自己实现版本部分的逻辑就可以
有点像 https://leetcode.com/problems/snapshot-array/ 或者 Google onsite面经
ads 组 假设给一个input root， 里面有多个directory和文件
design class表示file system 和 file
需要找到root下所有文件 比较这些文件是否相同(文件内容相同 不是filename extension) 做group 不能character by character比较
我就是弄个tree用trie树做 不过这个好像不是他最期望的答案
目测已挂~
这是一个需要senior来指导一堆new grad的组，买广告的，做backend的
美国小哥是隔壁组的。
忘了题号但好像以前见过。
题目是，每行规定150个字，我们输入一条很长的string，怎么切。
每行最后要加页数，例如：XXX（1/3）
我说这个页数很tricky，美国小哥说假设我们只有单数页码，先把单数页的代码写了出来。自己跑test case，发现bug 改掉。
然后follow up，没写代码但激情讨论怎么处理多页的情况。给了好多hint
先是假设不会有超级长的文章，就是那个页数沾满了一行中太多地方连一个单词都放不下。
然后是问，怎么猜页数，我就说，除个150吧，小哥说其实可以除144（这个是单数页的limit，上限，可以降loop的次数）
文章in string format，你要把它分成多少行/页，随便你怎么看。只是马甲。就是把长string分成规定大小，然后还得加页码，页码所占的位置也算在每页的size里
然后做法就是再loop几遍来finalize每行到底多少个字母。
最后问了一下复杂度，我说这个到底要loop几遍好像不能定哦，因为每次有可能把一个单词分到下一页什么然后又得改什么的。
小哥说其实2到3遍即可，第一遍如果猜中了magnitude的话，第二遍只用调数字，如果第一遍没猜中，才会run 3次。
感觉小哥好腻害～
学到不少东西～
拿到了onsite
报个电面挂经。问题是对于一个链表，链表里的元素可能是数字或者一个新的链表。求实现iterator，但问题所用数据结构及接口让自己定义。磕磕绊绊做出来了，但是接口定义什么的感觉被challenge不少。
推特广告组，跟雇人经理聊了，安排了电面，细节如下：
两道题
（1）设计一个跟踪用户看广告，点击广告，以及下载应用的系统。
（2）蠡口 幺叁玖：分词之壹
时候面试官显然不是特别满意，说HR会在一个星期内通知。
Twitter属于Recruiter跟进比较快的公司了，网上看到好的在官网海投后就直接联系了第一轮Hiring Manager Phone Screen，没有什么技术方面的，主要是聊背景，职位和发展，比较behavioral。隔天就通知技术店面，约了一周之后，但当中HR连续通知换了好几个小哥面试官，Twitter的攻城狮看来都挺忙的。
店面当天一共一个小时，用的CodePair，简单寒暄两句之后直接开始一道是Binary Tree，说如果你站在树根右侧往上看，求看到的Node之和，理解下来就是求右侧子树的Node之和
另一道是给一个int array，shift left k element https://leetcode.com/problems/rotate-array/
最后还留了几分钟Q&A。整个过程还比较顺利，上午面的，下午Recruiter就通知Pass了
写个class又这3功能
add(start, end) 加 time interval
contain(timePoint) 查这个时间点在不在已经加过的interval里
remove(start,end) 移除interval
我一开始说用bitset，大哥好像不知道bitset一直说space不好。。
然后说time也不好，那我说用线段树。
大哥说你先写简单点的解法，但是space要比bitset好。我说那circular array嘛？大哥说你就先存一下开始和结束时间。
于是我就写了，写着写着自己绕进去了，挂了。
这题类似LC 715 https://leetcode.com/problems/range-module/solution/
void add(int start, int end)
void remove(int start, int end)
bool exist(int val)
报一个两周之前的蓝鸟实习店面挂经 hr联系的 real-time computing组面试官国人小哥
店面题很简单 BFS 镜像树(follow up in place) 判断图有环
最后一道没写出来挂了
还有两道非常简单的忘记了 一个小时没bq
这题本质就是 meeting room II，input已经sort好了，不需要再sort。
求最大的room数。
难道允许有duplicate？
不然第三次尝试就是可行解，默认输入已经sort好了😁