Interview Misc Part 2


http://qsxuan.com/articles/1506.html
单链表找倒数第k个结点
剑指Offer上的原题。然而我当时想不起来了。于是说了几个不是最优解的解。
给一个由0和1组成的矩阵,求最大的全1方阵
一开始用前缀和写了个 O(n3) 的,后来又用dp写了个 O(n2) ,顺利过关
给一颗二叉搜索树,现在让你将每个结点值变为初始树中大于等于它的值的和
这道题考察的就是二叉搜索树的中序遍历。一开始没想到,还sb的用了一发线段树,不过面试官一步步提出更高的要求。于是顺利想出正解。
设计一个秒杀系统
先问的多线程的实现细节,然后问大并发量下的系统设计。因为之前看过《大型网站技术架构 核心原理与案例分析》中的案例,于是按照记忆大概设计了下,不过并没有很完美。
给一个标准表A,其中有订单项,如订单id,用户id,金额,一个错误表B,皆为表A中的数据,不过有缺失或者金额错误,问怎么找出缺失和错误的项
小数据量时用两个HashMap即可解,之后改为大数据量。
先提出用外存排序的方法,之后面试官一步步加强限制,最后改为用hash将表A,B分段,然后对每个小段利用小数据时的方法解。
给单独一个表A,数据量很大,格式同上一个问题,然后让求出消费总额最大的前600个用户,做一个排行榜
一开始没听到是总额,于是说用堆排,之后面试官又重说了一遍问题。。。
于是参考上一题的解法,按用户id对表A进行分段,之后分段统计,再对每段进行堆排,取前600个,最后再合并,合并的时候参考归并排序,每次取每段堆顶最大值。
二面基本全是算法,所以很顺利的通过了,之后问面试官,他说他是搞搜索的。 

三面

一上来先闲聊
说说你了解的百度
用过百度哪些产品(期间说了贴吧)
之后第一个技术问题就让我懵逼了。
设计一个贴吧
想了一会,就按我项目的结构设计了一发,之后开始问数据库的细节,哪些表可以拆分,怎么拆。还出了个SQL题
之后问了下一面最后的SQL题,让再写一遍。
然后问二面的秒杀系统,现在有没有更好的设计方案,还好我二面回去之后就重新看了一下案例,于是按书上的方案设计了一发
之后又开始闲聊模式
什么时候可以来实习
你认为你有什么优势
你最有成就感的一件事
你有什么想问的

http://www.1point3acres.com/bbs/thread-161198-1-1.html
google(onsite据):-google 1point3acres
(1)type url后会发生哪些事,建一个数据结构表示html, 就是设计tree吧,多个child然后还有一些其他的methods像next之类的
(2)设计一个数据结构表示matrix可以无限scale的那种,然后有sum, set等methods吧,我是想到hashmap做的(3)挂肯定在这一轮,先问了下hashmap原理然后问了一个情景用线段树(wtf,作为ee的我只是听过,然后纯乱扯),然后一道算法题,至今未没想明白,求地里大神知道,给一个string很长很长,找一个substring能不能除36余1,“agda4685766986579868687669686786786;?adfff7323” 有substring除36余1,substring只能有数字,但可以很长很长,可以远大于long的范围

G的那道题感觉应该只要记一下对于每个字符,以这个字符为结尾的substring模36的所有余数,然后从前往后递推就行了,复杂度是36*n


private static boolean div36mod1(String s) {
                Set<Integer> remains = new HashSet<>();
                
                int pre = 0;
                // 写完发现正序也可以,代码应该很类似,可能会稍微复杂一点。但正序可以适用于data stream. 会比较好。
                for(int i=s.length()-1; i>=0; i--) {. 鍥磋鎴戜滑@1point 3 acres
                        int n = s.charAt(i)-'0';
                        if(n == 1)  //  1 char, (1)
                                return true;
                        if((n*10+pre)%36 == 1) //  2 char (37, 73)
                                return true;

                        Set<Integer> temp = new HashSet<>();
                        temp.add(n);
                        temp.add((n*10+pre)%36);
                        pre = n;

                        // 3 and more char case: critical point is : (a*10^n)%36 = (a*28)%36
                        // at most 0, 2-35 can be in the set. so time is still linear.
                        for(Integer r : remains) {
                                int t = (n*28 + r)%36;
                                if(t == 1). visit 1point3acres.com for more.
                                        return true;
                                temp.add(t);
                        }
                        remains = temp;
                }
                return false;
        }

(4)regular expression match(终于一道leetcode题)和另一道比较简单的bfs的题

pure storage(onsite据):
  一轮oa,一轮电面(经典virtual function),onsite经典的4道的题,但是细节应该会因个人而不同,bar挺高的地里也没听谁拿到offer,推的学长也说要4个yes还要有一个strong yes才行,对bug free挺看重的,c++面最好,我是用c++面的其它的也行。
epic之前发过了
mathworks(2面据) 之前发过
zillow(2面据)
(1)strlen 用recursion写, 一开始写了个用substr的,O(n^2), 然后写了个O(n)的.(2)2D array 里找pair 那个题目
(3)1到100的序列中有4个missing number,把这4个数找出来
(4)reverse 字符串的单词顺序
citrix(2面据).
  两次都是基本上是基础概念,os, networking, 数据结构,c语言的知识,就做了一道reverse linkedlist用c写
yahoo(2面据)
  面的前端,css, html, javascript, 做了一道nodejs的作业,然后2面又问了些基础概念和nodejs,他家确实按组招人,很久才有回复,都垂死挣扎了真心差评
snapchat(1面据) 
  这个自己sb的很,google跪了后没啥心情,big integer算面筋题,自己没写过,写好了后,followup有负的情况写的很不好
zenefits(1面据) 之前发过
bloomberg(1面据) 之前发过
indeed(1面据)
   这个也是自己sb的很,reverse那道算面筋题,自己没写过,corner case几个没考虑到,然后还有语法错误,貌似小哥有复制粘贴没跑出来,跪的把自己恶心到了,太渣了自己
redfin(1面据). 鍥磋鎴戜滑@1point 3 acres
http://www.1point3acres.com/bbs/thread-210335-1-1.html
问的东西非常的统计,他们家确实挺难准备的。
1. R coding。Extract, Transform, Filter
2. How to correct online Survey response bias? Why there is bias?
3. Chi-square test in depth
4. Confidence Interval, standard error

Microsoft:. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
1. 简历
2. Given power, how to calculate sample size
3. Coding. Two sum

Facebook:
1.简历
2.SQL coding. Group by 啥的
3. Why number of likes in facebook page increase? 

Jump Trading:
1. MLE
2. Poisson process.
3. Derive E[x] of Poisson distribution. more info on 1point3acres.com
4.一道dynamic programming的coding。。当时直接懵逼. 1point 3acres 璁哄潧
-google 1point3acres
Two sigam:
1. OA老题
2. X,Y ~ N(0,1), correlation of (X+Y, X)?
3. find min element in an array? On average, how many times update the temporary min in the function? 
. visit 1point3acres.com for more.
Adobe:
1.简历
2. MLE of logistic regression·
3. Coding. Calculate Power(a,n)

Nvidia:.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
1.基本就是问问简历
2. 一些deep learning的问题。What is LSTM? Why LSTM is useful?

http://www.1point3acres.com/bbs/thread-212719-1-1.html
1. Appboy
HR面: 自我介绍,介绍实习,最大challenge
OA: Data Stream, get min, max, median, mode.
On campus: Missing ranges, 有个bug没fix,跪
. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
2. NetSuite
On campus: Anagrams, Topo sort. Topo sort有一个test case没过,跪。

3. Grubhub
On campus: 聊了聊实习做的东西,刚好面试官也是做这个的,聊的还算match。之后做了valid palindrome. 不知道为啥跪了

4. Amazon Robotics
On campus: 全程behaviors. 跪。

5. Addepar 
这家公司有点意思,里面的人很厉害,很多ACM的,Founder是Palantir的founder,CEO也是Palantir出来的。
HR: 随便聊聊
电面一: Wildcard matching. recursion + dp电面二: 面试官Havard数学本科。给一个矩阵,判断1组成的图形圆不圆,圆的程度自己定义(崩)。 举例:

这个看上去就很圆
000111000. from: 1point3acres.com/bbs 
011111110-google 1point3acres
111111111
011111110
000111000

这个就一点都不圆
0010101010101
0001010111010
1110000001010
0101001001010

6. Meraki
电面一: 碰到过最好的面试官,非常友好,给的提示恰到好处,能引导你思考。题目: 给一些会阻塞的sockets, 改成异步non-blocking,不能用多线程。勉强写出来,有两个小bug,跪。

7. VMWare
面的是Propel那个项目。OA不说了,地里太多了。
Onsite: 碰到了坑爹的印度人,跪,果断口气强硬地向HR举报。. 1point 3acres 璁哄潧

8. A9
HR面: 聊简历,why A9,之后HR说出差去了,再都没回复。Glassdoor上这家评价都是这样,HR不理人,说安排面试就没了下文。-google 1point3acres
. From 1point 3acres bbs
9. Aetion. 1point3acres.com/bbs
电面: 聊聊天,聊了他家的融资情况。算是刚融了A轮,投资人不肯透露。今年准备从20人扩张到100人。
OA: Can an array be sorted after at most one swap?. fOnsite: Withdraw

10. Signac
电面: 两个人和你聊天
OA: 忘了。。
电面: Withdraw

11. LiveIntent
HR: What is encapsulation, inheritance, abstraction, polymorphism? What is MVC? What is Interface and abstract class? difference? What compensation do you expect?
电面: 介绍背景,iOS开发,Swift,React-Native,React,why do you like React。 我说React是MVC中的V,面试官硬要说是C,争了几句,懒得说了。让我深入说说React,我说我只会用。讲讲什么是异步,异步的好处。JavaScript里的异步是怎么实现的 (Callback, promise, await). 浏览器里输入url后发生什么。HTTP全称是什么(wtf?? hypertext transfer protocol),为什么要叫这个?(语义化) 讲讲HTTPS,SSL全称是啥,讲讲它是怎么加密的。REST的全称是什么(wtf),这些词是什么意思,是怎么实现的。有哪些HTTP methods。我总是在提语义化,他让我除了语义化,说说GET和POST的区别,各自优缺点,表单提交用GET行不行。他家只想要能迅速干活的人,跪。

顺便说下,他家HR问我期望工资。我看glassdoor上他家平均8w多,就想开个10w,结果说成了10k。HR说what? 我说:是的,就是10k。。。。 (马德我就开10k你都不让我过)


12. Bina. From 1point 3acres bbs
HR: 讲简历和实习。
OA: Design一个简单的Excel。电面一: 记不清了,Binary tree的题目,lc上没有,挺难的,hard难度。
电面二: Withdraw

13. APT
On campus 1: Find two indices in an integer array, such that after sorting the numbers between these two indices(inclusive), the whole array can be sorted.On campus 2: design一些图的算法,最短路之类的Onsite: Withdraw

他家的工程师都挺聪明的,bar挺高。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�


14. Mathworks
电面1: Hiring manager. Talked about internship. Most chanllenging project. If one project you can do it again, what do you want to improve.
电面2: 一些JavaScript的语法问题,口述一些简单的算法题,怎么做unit test,OO的一些概念。. from: 1point3acres.com/bbs 
Onsite: Withdraw.


15. DoorDash
HR面: 聊简历和实习。
电面一: Missing ranges, sort with precision. 秒电面二: unique paths, find minimum in rotated sorted array,秒 (10分钟后hr就给了结果,super positive feedback)
Video 1: 一大堆behaviors
Video 2: Spiral Matrix
Video 3: 国人大哥,中文聊,聊了聊他家融资情况和前景。Binary tree BFS, level order traversal, linked list cycle, length of cycle两天后给了offer,HR说super super positive feedback.

再来聊一下他家。他家每一步都特别快,基本都是隔天通知下一步。不在乎思路,写代码写完就行。外卖领域占了最多的市场份额,现有200+ employees, 60个左右工程师,一半以上是stanford和Berkeley的,反正我碰到了三个Stanford的面试官。个人觉得他家现金不多,跟Uber打起来会吃亏。三个Founder全是ABC,Stanford+FB出身。前景的话,我觉得最好就是被Uber收购吧。


16. Yelp. from: 1point3acres.com/bbs 
OA: 地里很多,不说了
HR:忘了
电面: Why Yelp(面实习时就跪在了这个问题上,这次岂能再跪一次,给了一个自认为不错的回答。面试官说这是他听过最好的回答,他非常喜欢).  写代码给了一个新题,没见过,不难,讲起来有点麻烦,不说了。
Onsite: 1. 一个做安全的工程师,我就趁机聊了聊当天早上DDos攻击DNS服务器的事,聊了聊XSS, xsrf等攻击,聊了聊他家的开源项目和文化。做了Valid Palindrome.Onsite 2. 三姐,design load balancer. (跪,面试官根本不讲需求)Onsite 3. 白人经理,有点push,做了two sum.
Onsite 4: 三哥,easy题。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�

来说说他家。太注重文化,个人觉得有些过头了。有意思的是,他家有位聋哑工程师,公司给他配备了两名手语工程师,实时给他做手语翻译,也算是一种人文关怀吧。
.1point3acres缃�
17. Uber
电面: 题不难,但要先从头写一个BST的class,然后再写算法的主要逻辑,总共二十多分钟,了解题意,写了五六十行代码,然后fix语法错误,跑几个test case,有bug,来不及fix了。。跪。


18. Zillow
这家的具体题目不说了,都是面经题。实习时去过Onsite,跪了。这次面完第二天一上班HR就打电话给了offer。
非常喜欢这家,文化很好,技术和impact都不错,面了10个面试官,全部非常好!他家几乎没有印度人,work-life balance非常好,给的package非常好,我猜在Seattle除了FB,应该是new grad的最高package了,甩了Amazon一条街。而且照他家HR的意思,你再开价就行。.鏈枃鍘熷垱鑷�1point3acres璁哄潧


19. Microsoft
On Campus: 中国大叔,在微软呆了18年,出了一个怪题,不说了,崩。面试体验非常差,面试官非常mean。
. visit 1point3acres.com for more.

20. Google
实习时过了面试,所以做了OA直接去Onsite。因为拿了Offer,就不说具体题目了。大部分是面经或lc。
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴

21. LinkedIn
Recruiter聊完后说会有一轮HR面,之后就把我拒了。。

. 1point 3acres 璁哄潧
22. Amazon
OA2做完后(MST有两个test case美国)给了Onsite,放着没理,结果两周后给了offer。。还邀请去HQ参观。。。结果飞机晚点了。。就不去了。。。

-google 1point3acres
23. Facebook
电面和Onsite只有一题不是面经题或lc原题。签了Offer,不说题目了。


24. Samsung Research America
OA: 地里有,不说了。
电面: k combination prime sum, 类似于combination sum,只不过要求所有的加数为质数。用python耍赖,节省了很多行数。onsite和电面的面试官一起吃午饭,我说我给的解法非常impressive,他没想到python还可以这么写。。
Onsite 1: 一个和GUI有关的算法题,最好懂点基本的GUI。Onsite 2: Implement queue using stacks
Onsite 3: 三哥,人特别好。security problems(session), design problem, distributed problem. Longest palindrome,问我会不会O(n)的算法,我说不会。BST to balanced BST,我说不会,给点hint,他说我也不会。。。哈哈哈。。Onsite 4: 经理,韩国人,聊了45分钟。。
Onsite 5: Reverse Linked List. 第二题是一个略复杂的题目,可以简化为用Comparator sort后,求longest increasing subsequence. 不让用python,只能用java8的lambda继续耍赖。。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
面完第二天给了offer。说说他家,面的是Knox组,面试体验很好,每个人都很友好,包括印度人,经理人也很好。做的东西也比较新,impact也较大,package一般,因为没有stock(HR说给了他们能给的最高package)。


25. Apple
电面: 给了几段java代码,读懂然后改写。然后给了一个Trie Tree,改写。. Waral 鍗氬鏈夋洿澶氭枃绔�,
Onsite: 实在飞不动了,我想去NYC面,HR说只能去cupertino面,就withdraw了。

26. Coursera. Waral 鍗氬鏈夋洿澶氭枃绔�,
全是面经题。个人觉得,注重文化是好事,但太注重文化的公司,容易走偏,like over-fitting.

27. LeEco
他家奇葩事很多,mitbbs上很多。. more info on 1point3acres.com
电面: Withdraw.

28. Thumbstack, PureStorage等。。。 没做OA

还有一些很棒的公司没投,Snapchat,Dropbox,Houzz。尤其是Dropbox,以后有缘再试吧。
[Google]Return all divisors of n 返回n的所有除数
其实就是Prime Factorization, 只是code略有不同.  然后这个不是O(n) 算法, 是伪多项式的算法, 因为input和n本身的大小有关系.
与Prime Factorization的区别就是中间第二个if, 多加了个除数, 仅此而已
2
3
4
5
6
7
8
9
10
11
public static List<Integer> getAllDivisors(int n) {
List<Integer> divisors = new ArrayList<Integer>();
for (int denominator = 1; denominator <=Math.sqrt(n); denominator++)
if (n % denominator == 0) {
divisors.add(denominator);
if (denominator * denominator != n)
divisors.add(n / denominator);
}
Collections.sort(divisors);
return divisors;
}
http://blog.csdn.net/whuwangyi/article/details/43112895
第一轮问research和behavioral questions。
第二轮是Game of life,一个二维数组里,每个元素有生和死两个状态,根据周围元素的生死情况按规则进行状态转换。Follow up就是对大的file操作,而非内存中的数组。基本属于纯实现题目,很简单。
第三轮 实现web crawler。follow up是网页抓取和网页解析的异步实现。其实就是异步实现BFS。我用了三个queue去实现,除开一个本身BFS需要的queue,另外用了两个BlockedQueue,不知道对不对。

第四轮实现两个函数,int allocate()和void release(intid),每调用一次allocate返回的id需要unique,为1到N之间的一个整数。如果release以后,就可以继续被allocate。之前用array+hashmap,达到O(1)时间和O(N)空间。后来被告知空间用得太多,map空间效率低,最后用了bitmap。这题其实和实现文件系统的metadata区域比较类似,不过最后居然是用时间换空间,有点让我诧异。

第五轮系统设计:对分布式的server,获取对每台server各种信息汇总后的time series。非常的open-ended,反正把各种系统设计原理都用上就行了。

然后40分钟问了四个问题,根本没时间做完。第一题是LeetCode原题,next permutation,秒之。不过烙印一开是怀疑我的思路,后来费不少力气才说服。
第二题是实现hash map,指明非要用chaining的方法,CC150上应该有,也秒之

之后让我实现concurrent map,有点实现读者写者问题的感觉,没时间写完。

还剩5分钟的时候又问如何在chaining的机制下实现load factor,实在不会,后来发现答案其实解法刁钻。其实三哥也就进来了一个月,感觉牛逼哄哄的,做题的时候一直在旁边指手画脚,比如算法设计的时候一开始很容易声明一些多余的参数,等题目探索完了其实往往也就一目了然,自然最后会去掉,可是三哥中途非要指着说认为某参数不必要,严重影响了自己探索问题的乐趣和连续性。另外我也严重怀疑他如果不看标答,是否能够一开始就知道某个参数是最后不必要的,

要求设计一个数据结构,满足insert(int key),remove(int key)和int getMostFrequentKey()。对于同一个key,每次被insert,计数加1;每次被remove,计数减1;然后需要取最大count的key。要求所有操作都是O(1)复杂度。
这题首先通过尝试排除掉map+maxHeap的组合,然后又联想streaming max等各种尝试。后经过提示数据结构需要保持部分的排序性质(如果保证完全排序,插入删除操作是不可能O(1)的)。考虑到需要统计的count是整数,我就想到了bucket sort,另外联系类似LRU设计思想(doubly linked list + hash map),设计出了如下结构:
class Node {
         int key;
         int count;
class Bucket {
         Set<Node>set;        // All the nodes with equal count.
         Bucket prev;
         Bucket next;
}
Bucket head;
HashMap<Integer: key, Node: node>
虽然这个解被证明是可行的,但总感觉自己的设计有点过于复杂。做完这题后,脑力废去大半。。。

第三轮设计一个游戏,从起点到终点有两条不重合的长度相等的路径,每沿着当前路径走一步,需要耗费一定体力,如果切换到另一路径的相同位置,也需要耗费一些体力。每次只能继续往前或者切换路径,要求打印出消耗最少体力的路径。

其实就是一个一般难度的DP问题,不过这个年代还考DP的真不多了。

后来讨论了functional programming,要求给一个链表和一个filter函数指针,输出一个filter后的新链表,只能用递归写。其实iterative转recursive也不难。

之后跟我讨论kmeans的并行实现,然后让我猜另一种clustering算法。我猜了hierarchical clustering和density-based,结果都没猜对,最后告诉我是想让我答EM算法。狂汗啊,我压根就没有把EM放到clustering分类里面。最后跟我聊了下最大似然估计。统计方面的东西自己不怎么懂,有些郁闷:自己明明面的infrastructure team,可是这货怎么总往machine learning上聊呢?这new grad要求也太全面了。。。
第四个人主要聊背景是否跟team match,题目只出了个power set,算是最后放松了下。

Twitter:
1.      质数问题变种。
2.      各种sampling的问题,大数据的,分布式的。
3.      LeetCode原题:Clone alinked list with random pointers。
4.      设计如何分布式存储tweets,包括保持排序性质什么的。
5.      字符串匹配问题,都还没涉及到什么fancy的方法例如KMP什么的时间就完了。
6.      设计一个Timer class。
 估计由于我的项目经历,很多问题最后都延伸到了分布式实现和用MapReduce实现
http://www.1point3acres.com/bbs/thread-154959-1-1.html
Input: power of 2: 比如 8,2,4,4,4
以及一个target number t.
是否存在一个subsequence, 加起来等于t. 


warmup倒是好说,我想只要先将input中每个元素的个数数出来(因为每个数都是2^k次方,所以这个统计表可以用一个数组来记录),然后用greedy的方式,从t中不断减去“统计表中最大的小于t”的数字m即可,每减一次同时也将m从统计表中除去。如果最后t能减到0,则说明存在一个subsequence,否则不存在。建立统计表需要O(N)时间(N是数组长度),循环相减最多进行N次,所以总时间复杂度就是O(N)。

followup 1:
如果input可以有负的power of 2呢? 比如 8,-2,-4,-4,4
(hint: 有个很巧妙的解)

“很巧妙的解法” 在这里. http://mathb.in/47550
巧妙解法没法用在 followup 2上就是了...
Consider we want to check if there exist integers x1,,xn such that ixiui, such that
i=1n2ixi=t
Here i0ui for all i.
Let yi=xii, then this is equivalent to check if there exist integers y1,,yn such that 0yiuii, such that
i=1n2iyi=ti=1n2ii
which we already know how to solve.
followup 2:
假如给你k个target number t_1,...,t_k. 然后你要找到k个disjoint subsequence, 使得它们的和各为t_1,...,t_k呢?

https://reeestart.wordpress.com/2016/06/23/google-reason-to-crash-from-the-same-input/
概念题:问对于相同的input,有时计算机也会crash,为什么?
[Solution]
  1. 程序中有随机数。
  2. 变量或数组没有初始化,导致每次随机分配的值不同,有可能overflow。c++就是很好的例子。Java一般没有这样的情况。
  3. 有external dependency。比如某个变量和当前时间有关,或者依赖其他程序,而其他程序的输出每次都不一天。
  4. hash table或者heap的iterator,没有确定的顺序。
  5. distributed system的network有变化,或者因为load balancer的存在,每次程序被schedule到不同的机器上,上一次的机器成功执行了程序,但是这次的机器却down了。
[LiveRamp]设计一个Key-Value Store
这是我面LiveRamp的面试题:这题是电面,所以只用说清楚思路, 但是用嘴说一个分布式系统的思路实在太困难了, 而且对面小哥貌似是伯克利的,我说一段,他就问一段,节奏太快,面的感觉不好,后来写了封感谢信,人家推荐我学一下伯克利的CS162,Link:http://cs162.eecs.berkeley.edu/.知耻近乎勇, 赶紧看了一下. 真是很好的课. 特别是Phase3到Phase4.建议大家有时间看看.
面试的过程是这样的:
第一个问题是: 请设计一个Key-Value Store for 1mb data. 我脑子都不转就说HashMap<Key,Value>, 然后聊了一下时间复杂度,还有重复怎么办, 注意put操作默认是override value的.
讨论了五分钟后, 接着问, What if the size of data increase to 1tb, 我说不能HashMap了, 因为HashMap是存在内存中的, 这么大的data存不进去, 丢了也不好办, 所以就开始分布式设计了, 但是我考虑了一下, 1tb的data存本地硬盘就好了, 所以我说, 存在硬盘里,但是考虑到存的是stable storage里,而不是普通的硬盘, 做个RAID什么的…然后聊了聊怎么存取, 简单说就是用key划分一下目录层级什么的.
又过了十五分钟后, 问如果有1pb data 怎么办, 这个果断开始分布式了, 我当时是按照着dynamo的概念说的, 但是在讨论trade off的时候, 明显没有对方熟悉一些概念和设计模式, 所以就挂了.
CommerceHub面试
开始扔了一个作业过来, 让我两天就交, 我这边又答辩,又工作, 真是累死人了. 作业很简单, 就是实现一个数据仓库, 需要注意一下多线程同步访问的问题. Code: https://github.com/gaoyike/CommerceHub
交了后三天收到电面, 然后就开始各种不靠谱. 面我的是一个2016的新SDE, 问的题是, 让你设计一个300 room的旅店, 然后就没了, 我从底层开始讲设计, 一直讲到分布式. 对面一直嗯嗯嗯, 结果问我一个问题: 你用什么IDE….  我突然就愣了, 我说我用intellij idea, 他说, 有意思, 你继续…然后我讲怎么rollback, 怎么做memcache, 然后又一阵嗯嗯嗯, 然后问我, 如果系统死机, 或者很慢, 你怎么办, 我说加cache, 然后做冗余, 我越来越觉得我面的不是SDE….最后一个问题彻底击垮了我: 如果用户一直说很慢, 你首先检查什么部分. 我说我先看log服务器, 然后dump内存. 看看是不是哪里有bug. 对面说, 有意思….我操 ‘有意思’…..

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts