Fact:
500 million files saved daily
public APIs
Linux platform
Sync
10月29：
题目大概就是用pattern p匹配字符串s。已知如下
p="abba", s="red blue blue red", true
p="aaaa", s="red red red red", true
p="abab", s="red blue blue red", false
p="abba", s="red red red red", false
然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
做题，还算顺利，做完以后问了复杂度。
以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行
，然后面试官让说说递归怎么做于是感到面试官应该希望听到递归的解法，于是就说
partition s呗，前一半跟p的前n-1个字母match，后一半跟第一问一样的检查是否可行
。面试官让写code，写啊写，写啊写，匹配的那个map的回溯总是写不对（不回溯空间
岂不爆掉了？），到最后看到面试官把错误的版本copy下来了。这是不是就算挂了…
8月25：
1. getHit(): return last 5 mins hit
2. hitLog(): called every time the page is loaded
2. hitLog(): called every time the page is loaded
8月22：
在 coderpad 上写。面试的人自称是F家跳到D家的，前半小时聊项目，二十分钟做了个
word break题,再十分钟聊team。
word break题,再十分钟聊team。
11月7
30分钟，只有一道题。DB的人很会卖萌，题目是用打油诗出的。。大意就是介绍了一下一年里面大月小月分别是哪几个月，告诉你19XX年某天是星期几，然后让你写code算一下从19YY年到20ZZ年有几个月是以星期天开始的。问题不难，注意一下闰年的问题就可以了，感觉风格好像小学奥数。。。LZ出于小奥后遗症，上来就把每个月天数除以7的余数直接写下来，而不是写的每月天数。。面试官看了我一眼，估计私下里觉得我很奇葩。。不过很快就码完了，剩下时间聊聊天，交流很愉快。
1个小时。LZ这次碰到了印度人，好在这人刚好是我大一时候的导师的助手（副导师，但是他当时是大四学生），虽然没说过话不过至少混了脸熟，所以没有特别紧张。也是只出了一题，大概是说一个人去买罐装汽水，只能一罐一罐或者一箱一箱地买。箱子有几种不同大小，比如一箱12罐，一箱6罐等等。这个input是个list。让输出所有买法（就是每种package买几个这样）。又是一道风格像极了小学奥数的题，小时候那种“5分，1角，5角”神马的找零钱问题做了不记得有多少。。同样没什么复杂算法，DP一下就可以了。LZ写完code，发现结果悲剧了，于是面试官过来和LZ一起找bug，找了一会儿，俩人都觉得没问题呀。又过了一会儿，他噗嗤一下差点乐出来，然后LZ发现自己写错了个indentation。。后来分析了一下running time，再聊了一会儿，时间就到了。
Onsite
一整天的面试啊面试，都是白板code。这之前LZ只去过F家的onsite，一整天就一个45分钟面试，剩下就是四处玩。这下可算来真的了。。全天3个tech面，每个1小时；最后还有一个非tech面。进去之后交代了两句就把LZ放在一个屋子里，说我一天呆在里面就行了，面完一轮会换下个人进来接着面。
第一面：给一个字典（里面有若干长度至少为3的单词），一串7位的电话号码。在电话上面的9键键盘，字母和数字之间有对应，求输出所有把号码转化为单词的结果。比如3767269可以对应D-R-O-P-B-O-X这样。LZ的解法就是先把字典做成3个HashMap，分别对应长度为3，长度为4，长度为7的单词。key对应号码，value对应一列单词。这样只要把电话号码拆解成7或者4+3或者3+4的格式就可以直接lookup了。之后又问如果电话号码不限于7怎么办，LZ的做法是先写个helper function算出所有的partition，然后字典做pre-computation的时候把一堆HashMap存到一个array里这样。最后lookup的时候做个Cartesian product。
第二面：给一个directory，求print出来所有duplicate files的名字，所有相同的files的名字都print在一行。记个HashMap，做个BFS就行了。然后还有个问题是说，假设是个很大的音乐库，20个G的，HashMap记不下怎么办。LZ给的办法是只看每个file的前1KB，最后在duplicate的一行里面再进完整文件的比较。
第三面：和第二面差不多，给个URL，求print出来所有能达到的链接。每个链接只print一次。也是BFS，注意存个HashMap避免链接之间互相loop。然后让写个多线程的version。
最后一面：就是和一个DBer聊聊天，问点问题。30分钟。LZ遇到了之前在on campus的时候一起吃过晚饭的一个DBer，他还记得我，于是聊了聊DB现况，发展趋势神马的。他在hoodie里面穿了一件很花的Hawaiian衬衫，打了一条同样很花的领带。据说是因为他们有个feature快要launch了，所以在那之前全组约定每天系领带^_^当然说是全组也就不到5个人。。
No comments:
Post a Comment