Uber-NY Onsite “噢你很懂design?“【一亩三分地论坛面经版】 - Powered by Discuz!


Uber-NY Onsite "噢你很懂design?"【一亩三分地论坛面经版】 - Powered by Discuz!
1,常见题-Design spotify,主要在问playlist和shuffle list功能。
>player,playlist,song这些类要怎么搭配比较合适,自由发挥。常见的OOD设计。
>如何让用户之间分享playlist做到最快,让用户之间通信而不是找中央服务器拿,进程间通信(IPC)和线程间通信(ITC)的常见实现(这里wiki一下,总有几个你熟的名词)。
1,会走一次中央服务器,但是这个中央服务器不存数据,只负责转发请求到目标用户。


>想增加一个shuffle功能,自动随机排序当前list里的歌,这个shuffle怎么写。经典的knuth洗牌算法,写在白板上。
http://massivealgorithms.blogspot.com/2015/07/fisher-yates-shuffle-wikipedia-free.html

>用户想shuffle之后回到之前那个版本,如何处理。要把每一次shuffle的结果存起来。用map或者链表存可以快速存取。用户还想删除当前shuffle的版本的话,写个简单的双链表删除当前node并且更新位置即可。

>设计一个函数goto(int step),让用户可以返回到某个shuffle次数之后的结果(比如用户在100万次shuffle后的版本,想回到50万次shuffle的版本,吓得我当时尾巴都掉了)。我先提到继续用map,用consistency hashing来减少rehash的麻烦。对方说不太可行,因为复杂度还是太高,但是consistency hashing的方向是对的。
>>然后totally lost,开始丢buzzword,说amazon的dynamo有个ring结构可以进一步压缩rehashing的工作量或者linkedin的voldemort可以加速大数据的读取和存储,redis的跳表结构可以压缩空间使用,可以用多级cache或者LRU cache来增加读取速度。全部都不满意,而且scale越来越大,用户shuffle的次数可以billion级,用户的歌单可以billion级等等。最后跪求提示,在暗示下意识到可以改造随机数生成器,在洗牌算法里用我提供的seed进行随机数生成,这样只需要存对应次数的seed。对方表示认可,但是依然可以优化,时间不够了。丢名词的那几分钟,简直就是被慢慢摩擦的过程。

2,因为你再consistent hashing,当上千亿个用户shuffle上千亿次,每个歌单有上千亿首歌的时候(是的,我当时吓得瓜子都掉了,总之他的意思就是你别想把shuffle结果全部存下来),你无论如何不能把这些shuffle结果都存下来。做一个特殊的伪随机数生成器,直接根据shuffle步数生成固定的随机数来shuffle,才是可行的办法。. more info on 1point3acres.com


二轮:一个做前端的小哥,而且是很前端的前端。

1,count and say。
>我直接作死说我做过(其实是太过自信了),让小哥卡了几分钟,好像是他唯一的用来考非前端的题。然后说改设计吧。也许不应该让他这么没面子,毕竟也是做过CTO的人啊,也许吧。

2,常见题-facebook friends recommendation。
>首先朋友之间的关系如何存储。常规的sql乃至常规的nosql(比如mongodb)为什么不适合这个模型(因为关系会互相嵌套,为了处理这些嵌套,开发过程也会很繁琐),如何解决-使用graph db。因为我在fb做过了解他们的TAO架构,所以稍微说了下,可以把朋友关系存在边上,这样本身node就只是用户就足够了,提取关系时也可以很轻松的batch 操作。常见的开源的就是neo4j,可以看看他们的自我介绍和应用场景。也可以看看fb的engineering blog对于tao的介绍。
>然后如何进行推荐,从最基本的bfs开始说,每个用户为起点,bfs出去到距离2的时候停下,这个bfs不记录visited,单纯看有有多少用户和当前用户距离为2(就是有一个共同好友),所以把结果打印出来,重复出现最多的几个用户就是最适合推荐的。. 1point3acres.com/bbs
>>follow up,如何提高效率,当用户数大到一定程度时?这里就是典型的MR应用,因为每次记录都是(用户名,1)这样,把所有的加起来就是典型的reduce步骤。如何提高反复处理的效率,可以缓存结果,也可以用spark这种基于运算而非基于数据的模型,把运算传递给数据。说简单了就是传统的Hadoop的优缺点分析。
>>>再follow up,如何对新增的用户进行快速的处理,如何对距离3甚至关系更远的用户进行分析?这里开始就要谈到collaborative filtering和相关的开源库比如Apache Mahout了,然后瞎扯了可以用spark streaming来进行流式处理,对方来兴趣了,问我spark streaming的discretized stream如何适用到这个题目,卒。

3,问完设计,上机写个简单的类似字典搜索。给你代表字典的list<string>和代表输入的list<string>,把输入字符串里所有出现在字典里的部分大写(对,就是breaking bad的片尾staff表那样)。
>现在想起来,估计是有陷阱的。我当时太开心,就说好吧我们来写吧。几分钟写完,还装逼地说我们来写个JUnit test吧。其实这些都是intern面试之后积累的,因为他们家面试经常让你开自己的ide,写完了自己写个junit test来assert equal。
>test写完,准备run之前,问了一句,你是想我按了run看错误去debug,还是先我肉眼debug一下再run呢。对方笑了笑说都行。。。现在想起来,我选错答案了。
>然后跑出错,debug,又出错,再debug,两轮快速迭代,增加了2个边界检查,通过。对方要求我发代码给他看看,开心发完之后就聊天了。现在想起来,我应该主动要求把代码再优化下的,傻逼兮兮又被按在地上摩擦了吧,自己还不知道。

三轮:一个前Google大牛,上来就把我简历丢开说我们聊聊uber吧。

1,常见常见题-Design Uber。
>https://cnodejs.org/topic/557b9cff16839d2d53936242,建议各位先把这个里面的那张图看下,那个基本就是正确的目前Uber在用的模型,有这个概念,但是千万不要去硬记那些名词。
>上面模型里的mongodb是错的,千万别说mongodb,可以去搜下为什么初创公司发展之后都要脱离mongodb。其他大部分都是正确的,也是他们现在在用的数据。
>http://highscalability.com/blog/ ... arket-platform.html,这里讲得更详细,关于目前的架构。然并卵,别死记硬背。这个网站本身有很多不同大网站的architecture的分析,都可以看,但是别硬背名词。

>先从最基本的用户验证开始问,我看太多科技博客以为上来就问我大架构的东西。结果一开始迷惑了一阵子直奔dispatching service,傻到回答别人说http是stateless,tcp是stateful这种奇怪的答案。其实就回答一个POST请求就好了。网络层7栈结构我都能背了,还在这里犯这种傻,我对不起老师。. From 1point 3acres bbs
>验证之后,如何不需要进行后续验证,这里可以说cache下用户的登录状态,也可以让用户在post请求里加入生成的密匙,就像OAuth那样。对方似乎对OAuth类的做法不是很满意,"可以是可以,算一种办法吧"。
>用户要给服务器发送什么信息。物理地址,请求的车型,当地时间。可以JSON也可以CSV,序列化后加密发送。问我CSV和JSON的优缺点。
>>follow up,问我知道不知道RPC,我说了解一点比如thrift但是基本没用过。然后问我这里如何应用,我说可以用JSON-RPC类的库来进行序列化以及加密,这样可以提高用户模块和服务器模块的协作性。对方不是很满意我说不出thrift的一些优缺点或者细节。

>用户点下请求后,服务器如何选择最合适的司机并且通知他们。根据trip time,wait time还有trip fare以及司机availability(car pool的话,现在在载人的司机也是可以的)进行判断。司机数据可以按照城市进行Sharding,考虑到有大小城市,可以多个小城市的shard放在一起,一个大城市的shard使用一个节点。让我聊这样shard的问题,提到跨城市的trip可能会导致切换shard,这种很低效。

不过多个小城市可以用一个shard,一个大城市用一个shard,这样就解决了城市流量不同需要不同级别的服务器的问题。毕竟shard本质还是服务器partition。

uber的chief architecture今年有个讲座也提到了,按城市shard是老方案,但是后来发现城市规模差别很大,不同城市负载差别也很大。他们也考虑过,多个小城市sharding到一个,但是。。"this is really hard to manage"。然后他们已经rewrite from scratch了。
.1point3acres缃�
不过这种面试本来就是一个trade off的过程,可以先把这个方法说一下,然后分析缺点。顺理成章过渡到他们现在的方案,也就是shard by geo id (per geo id ~3-6 km2)

当时的情况下,我和这个老司机说,shard是一个办法,然后每个城市一个shard处理起来很不好,需要更细分的shard(准备扯到依赖google s2 library的geo-sharding)。老司机和我说,单城市可以是可以的,可以大城市一个shard,小城市多个共享一个shard,然后我当时觉得再继续说geo-sharding意义也不大(因为本来就是我主动展开的话题,而且老司机明显心不在焉了)。而且之前他问我如何通过物理坐标判断用户在哪个geo-id就没回答好,再扯一次就是找死。-google 1point3acres

我的确是准备了geo-shard的东西,而且还有很多其他的东西,

>>follow up,在大量用户请求和大量司机可用的情况下,如何提高效率。这里我又犯傻,直接说他们目前在用的那个supply demand模型。根本不懂还卖弄就是被按在地上摩擦。其实这就是个基本的生产者消费者的模型,分布式+message queue谈到了就好了。他们家的supply demand的主要作用其是和price有关。

>如何保证一个司机不会发给两个不同的用户。这里可以上锁,但是要考虑怎么用锁,是处理这个请求的thread拿个锁,还是记录在用户相关的缓存数据里,然后要如何锁,是锁住数据库里的一个object,还是修改一个变量。这里我又傻逼地说了几句就开始说,哎呀你们家之前用php,因为php的多线程,线程间通讯不够好所以出过一个司机给两个用户的事,后来不是改成single thread的nodejs,然后用ringpop来轮排操作保证ITC以及IPC了还有原子性了嘛。其实人家想听到的是更本质的东西,而不是这些花哨的名词吧。

3,没有线程保护好,比如他们早期用php(which is multi-thread based)的时候,在简陋的thread lock之下,就出现过1个司机已经发配给一个用户之后,这个司机在几乎同时(他被lock之前),又发给了另外一个用户。他们现在的解决方案干脆用单线程的node.js配合一个类似dynamo的ringpop(可以搜下这个ringpop)来维护thread safe。


>data center爆了怎么办。一直有一台config server,爆了就把请求转移到backup server。backup server可以定期复制数据过来。爆的那段时间里丢失的in flight data,可以通过在司机和用户手机上预存一部分数据,重新连接后验证两边的数据,如果不一致就从用户和司机手机上请求最新的数据。这就是uber的做法,他可能意识到了我复习过,"噢很有意思嘛,我们的做法很类似呢"。

>旅途开始了之后,怎么把用户和司机的状态更新好。这里一台update server和司机通信,另外一台和用户通信就可以。

>旅途结束后,如何搞定payment。这里要用RPC类的办法去调用其他micro service(比如business service),然后这个请求发过去之后,如何保证付款一定能成功。这里我说可以用个简单的message queue,并且带有consume at least once的特性,比如kafka这样。

>>follow up,kafka是怎么实现的,怎么存的。我只想起来kafka是producer, broker, consumer分离,使用linux的page cache进行存储和page swap,并且consumer会guarantee consume once。对方似乎不是很满意。没实际用过kafka,大概不能明白核心科技吧。

payment的处理时consume at least once吗?不太对吧,还是我理解错了?我怎么觉得是consume at most once呢?
比如处理一个付款,我理解的是,付款失败是可以接受的。但是不能超过一次。比如付款10块钱,如果付款执行超过一次,付了20或者30,这显然是消费者不能接受的吧。

噢我强调的重点是说这个payment,如果服务器down掉了,之后恢复了还是能够处理的,就是至少会处理一次,或者说一定能够处理。因为他问我的问题就是,如果payment service模块down了,那个payment要如何处理,所以就要有一个guarantee of delivery在,我就用kafka的这个consume at least once(相对于其他mq的可能完全丢失而言)

at most once的那一面是另外一个design concern,我当时没说到。你说的也是很make sense的,如果问到了你可以修改措辞说是guarantee of delivery,而不是consume at least once。感谢指摘。

我觉得你说的没什么问题。 就是要需要一个consume at least once的queue在那里。 至于dedup,braintree本身就会做同样的事情。 同时可以自己建立一个dedup的机制。 不过,我在想如果kafka快被撑爆了怎么办?
-- Maybe consume at least once is better, we can run check and refund user if we charge user more than once.

四轮:hiring manager,大大牛,纯culture fit。
1,why uber。常见问题,自己想吧,谈钱也没事,大家都懂。
2,why uber want you。继续常见问题,自己想吧,答实在点,大家都忙。
3,自己做过的最喜欢的项目,自己的三个缺点,三个优点,这都是常见的了。
3,自由提问。我问了why I want to join uber,what can I expect to be in 5 years if at Uber,what can I get here in 2 years。看反应应该不是烂问题,不过我自己回想是觉得有些装逼了,还好这里人人逼格都非常高.

他们目前一个很大重心是开发自己的技术和重构现有代码,所以如果只是会用一些市面上的老技术和知道很浅的细节的话,其实Uber NY来说是没啥意思的。好几个工业界前辈看了这个面经,都说我对buzzword的解释太浅了

4,他们目前一个很大重心是开发自己的技术和重构现有代码,所以如果只是会用一些市面上的老技术和知道很浅的细节的话,其实Uber NY来说是没啥意思的。好几个工业界前辈看了这个面经,都说我对buzzword的解释太浅了,所以面试官的感觉也应该是一样的吧。
How Uber Scales Their Real-Time Market Platform
Read full article from Uber-NY Onsite "噢你很懂design?"【一亩三分地论坛面经版】 - Powered by Discuz!

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