一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6158|回复: 38
收起左侧

3.7 Facebook Onsite

  [复制链接] |试试Instant~ |关注本帖
lotustree86 发表于 2016-3-9 16:05:41 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Pass在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
这周一面的facebook
1. 半轮culture flt, project deep dive. 算法题是convert binary tree to linked list.
2. Coding: (1)跟number of islands 非常类似,只是变成matrix里是各种颜色,用字母表示,让统计每种颜色的number of connected component,用dfs就可以解决。另一个道题实在是想不起来了:(,想起来后会补充到下面。
3. System Design: Design URL Shortening service.
4. Coding. 先出了一个题是convert binary tree to doubly linked list.我说第一轮做过了非常类似的题。然后就直接写了他的Backup problem.leetcode 211 原题, add and search word.

所有的算法题面试官都会问你空间时间复杂度,worst case, best case, avg case都要知道。


补充内容 (2016-3-10 02:44):
终于想起另一个算法题了,check if a binary tree is mirrored,就是与根节点镜像对称。


补充内容 (2016-3-10 02:45):
最后一轮的follow up是如何利用trie做google 的type ahead feature。我的做法是每个trie node加一个weight,和维护一个top n words priority queue for his subtree。

评分

12

查看全部评分

本帖被以下淘专辑推荐:

 楼主| lotustree86 发表于 2016-3-10 18:02:34 | 显示全部楼层
guixi107 发表于 2016-3-10 03:37
congrats to lz 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

two quick questions:
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1. Singly, ListNode convertBT(TreeNode node);

我觉得你问得几个问题都非常好。我跟面试官的交流过程是这样的
1. 首先我跟面试官确认的是requirement,至于web service来讲就是API:
(a) Url shortenUrl(Url longUrl), which is write request
(b) Url getLongUrl(Url shortUrl), which is read request

2. 接着我就跟面试官问capacity流量问题,也就是类似于你问得qps,我就问是有多大的traffic,面试官说要很大的流量,比如能够支持twitter上面tiny url的流量。. From 1point 3acres bbs
从系统设计的角度要求就是要production ready:it needs to be scalable , high available, and high performance.
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3. 接下来我就分析你所提到的read/write heavy问题,通过分析以及我们的经验可以推理,tiny url service的read/write ratio肯定很高,也就是它是一个read heavy system。从用户的角度来分析需求,对于read request,你肯定希望反应越快越好,而且以下场景是设计者需要考虑到的,某些hot url的qps肯定非常高,你一定希望read reqeust to be very scalalbe for large qps. 对于write request来讲,首先我们可以想象的是它的qps不会高到哪里去,用户在产生tiny url时多等一秒半秒的并不会太影响用户体验,但是对于read request就不一样了,你肯定希望它反应越快越好,但是write request对于consistency的要求却是非常高的,也就是你不希望不同的long url generate the same short url,race condition or short url collisions should be avoided。从系统设计的角度就可以得到这样的具体需求
(a)read request: highly scalable, high performance, high availability.
  (b)  write request: consistency. 1point 3acres 璁哄潧

经过以上的交流基本上这个系统的具体需求就出来了,然后就是着手design,如何从架构的角度来满足以上的需求。你说提到的架构基本跟我一样,但是后台database,我建议用key-value nosql database, key is tiny url, value is long url.原因很简单,SQL database is not designed for high scalable, high available purpose.而且它的强项ACID, Transactional,以及处理join relational table,除了consistency/transactional,我们是用不上的,反而带来performance等问题。key-value store is a perfect match for us.
所以我的系统架构基本是这样子的: load balancer -> web server -> distributed cache -> key-value store.

现在我们来考虑以上架构是否能够满足提到的需求。
(1) read request
Scalability: 由于我们的service是stateless的,web server之间share nothing,所以通过load balancer,web server这一块是非常容易horizontal scalable的,然后继续往后看,由于cache的帮忙,很大程度上会解决高QPS的问题,但是我们仍然希望他能够尽量大的take read request,并且可以解决hot spot 的问题,如果所有的请求都由一个data store 来处理,这个明显不scalable.这个时候能我们其实就可以考虑data paritition了,也就是用多个data store 实现负载均衡。很容易想到consistent hashing,我们可以基于short url再说一次hashing, 将read request distribute 到data store on the hashing ring.这样子数据库也解决了scalability的问题了。. 1point3acres.com/bbs

Availability: 这个的重点仍然实在数据库上,web server 的可用性比较简单,down掉一两台机子没啥事儿,考虑到area data center outage,也就是多在几个数据中心部署就可以了。data store的高可用性就是replication,有两种方式: master-slave和 peer to peer,我们的应用场景master slave特别合适,为什么,因为前面说了,这个系统是read heavy, master 和slave both can take read request,but only master can take write request, 而且对于写操作,master 必须保证所有的slave都完成了同样的写操作才算是一次成功的write request.这个就可以避免刚产生的tiny url,不会出现read reqeust 返回not found. p2p也可以实现同样的功能,但是复杂度大一些,这里没有这个必要。

Performance: 这个其实经过以上的设计问题就不大了,得利于cache的帮忙,这个应该问题不大。至于move data closer to the user这种方案好像队tiny url这种场景用处不大,因为毕竟数据量小,如果是video/image这时候就可以考虑cdn这类的了。

(2)Write reqeust
前面提到了consistency,也就是说我们怎么保证写操作的atomicity。这里有两种方式
(a)pessimistic locking: 就是所有的写操作都要先acquire a lock, and then perform write, at last release the lock,可以看到每一次的写操作都要先拿到所,所有的操作都serialized,明显性能是不太好的。 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  (b) optimistic locking:这种方式是数据库里的每一条记录都有一个etag,你可以想象成timestamp,在update request需要attach一个etag,系统会检查这个etag跟现在的是否一样,一样的话就会perform update,否则就会失败,你重新读数据然后再更新。基本原理就是atomic compare and set,write request的etag你可以就是认为是空。这种方式再有高并发的update操作时性能比较差。

比较以上两种方式,我倾向与第二种,因为前面提到,写操作本设就不是heavy的,另一个主要原因是long url hash to tiny url的算法应该会保证产生collision的概率非常低,但是我们还不得不处理collision的情况,所以第二种方式完全perfect.

经过以上几步基本上这个系统就可以满足需求了。由于一开始的时候我还提到过analytcs的问题,所以follow up还有问我如何做analytics,这基本就是如何做data driven web service的问题了,是big data的领域,让我实现 top n hot url. 今天太晚了,明天看看有时间可以稍微介绍一下这个。

评分

8

查看全部评分

回复 支持 11 反对 0

使用道具 举报

 楼主| lotustree86 发表于 2016-3-11 07:40:57 | 显示全部楼层
guixi107 发表于 2016-3-11 03:24
大赞

lz太厉害了,崇拜啊

CAP理论要搞懂,各种论坛上大家都推荐的狗家三驾马车的paper最后都看一下,亚麻的dynamo db的论文也可以看一下啊。

另外我觉得有一本微软自己出的电子版的一本书特别有用,其实很简单,但是对于理解分布式系统设计的一些基本概念特别有用,极力推荐 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

https://msdn.microsoft.com/en-us/library/dn271399.aspx

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

joetan1986 发表于 2016-3-9 23:28:11 | 显示全部楼层
楼主可否介绍一下背景?几年工作经验?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-10 02:48:59 | 显示全部楼层
joetan1986 发表于 2016-3-9 23:28
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷楼主可否介绍一下背景?几年工作经验?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
EE Master,三年多点的工作经验。
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-3-10 03:37:43 | 显示全部楼层
congrats to lz

two quick questions:
(1) first round, do you need convert to single linked list or double linked list, would you please provide the function signature?

(3) third round about the design tiny url service, how to answer it?
--what kind of assumption.clarification needed to be made? read heavy write heavy, and what's the qps?
--what kind of archtecture to propose? load balancer, app server, memcached, mysql?
--do you need provide estimation on how many app servers, or cache servers or dbs?
--do you need provide algorithm on how to generate short url based on long url?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
thanks
回复 支持 反对

使用道具 举报

joetan1986 发表于 2016-3-10 12:32:57 | 显示全部楼层
lotustree86 发表于 2016-3-10 02:48
EE Master,三年多点的工作经验。
-google 1point3acres
cong!FB不是freeze了么?楼主是内推的?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-10 15:33:59 | 显示全部楼层
joetan1986 发表于 2016-3-10 12:32. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
cong!FB不是freeze了么?楼主是内推的?

是内推的,我朋友说没有freeze呀。
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-3-10 16:13:51 | 显示全部楼层
LZ是EE master, 那你跳槽之前是做CS的吗?还是就是做EE的?FB看重过去的项目经验吗?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-10 16:56:01 | 显示全部楼层
daniel_hl 发表于 2016-3-10 16:13
LZ是EE master, 那你跳槽之前是做CS的吗?还是就是做EE的?FB看重过去的项目经验吗?
-google 1point3acres
在一家出名的养老软件公司工作三年,不过我呆的几个组都不是养老的,项目还不错。第一年做非常底层的kernel, driver的活儿,后来有将近两年的web service, big data相关项目,学到了不少东西。

对于有工作经验的candidate, FB只一轮专门聊project deep dive和culture fit,这个现在几乎所有的公司都会问吧。你需要把你最喜欢的项目了解的非常清楚,architecture, end-to-end working scenario, 自己负责的部分,以及做的contribution,技术细节都要非常非常清楚。

至于你问的"着重过去的项目经验",如果你是指经验match会有加分,不相关会减分,这个我觉得不用担心。communication远比经验重要的,如果你能把一个面试官不了解的项目解释的非常清楚,这个我觉得反而是非常加分的。
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-3-11 03:19:48 | 显示全部楼层
lotustree86 发表于 2016-3-10 16:56
在一家出名的养老软件公司工作三年,不过我呆的几个组都不是养老的,项目还不错。第一年做非常底层的kern ...

非常感谢!
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-3-11 03:24:37 | 显示全部楼层
lotustree86 发表于 2016-3-10 16:56
在一家出名的养老软件公司工作三年,不过我呆的几个组都不是养老的,项目还不错。第一年做非常底层的kern ...

大赞. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

lz太厉害了,崇拜啊. 鍥磋鎴戜滑@1point 3 acres

有推荐的system design的资料吗?
(自己看了些buzz words, 距离lz的分析和设计差很远。)
回复 支持 反对

使用道具 举报

vivian88 发表于 2016-3-12 02:40:32 | 显示全部楼层
楼主的system design过程很清晰啊,学习了
回复 支持 反对

使用道具 举报

garnett2148 发表于 2016-3-12 03:57:26 | 显示全部楼层
大赞楼主分析和思路!请问楼主面的时候面试官也是按照这个思路和你一起走下来的么?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-12 05:49:54 | 显示全部楼层
garnett2148 发表于 2016-3-12 03:57
大赞楼主分析和思路!请问楼主面的时候面试官也是按照这个思路和你一起走下来的么?
. from: 1point3acres.com/bbs
嗯,基本差不多,当然没有我现在写的这么organized。
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-3-12 14:27:19 | 显示全部楼层
convert binary tree to doubly linked list.

这题考官有没有要求用 非递归 写啊?
回复 支持 反对

使用道具 举报

闲庭听雨 发表于 2016-3-12 14:37:06 | 显示全部楼层
楼主厉害!佩服!
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-12 15:15:47 | 显示全部楼层
duduhaha 发表于 2016-3-12 14:27
convert binary tree to doubly linked list.

这题考官有没有要求用 非递归 写啊?

没有,这轮没那么多时间
回复 支持 反对

使用道具 举报

FISHERFISH 发表于 2016-3-30 05:23:04 | 显示全部楼层
LZ 写的好棒....我现在也在你以前的公司, 算是核心组 不过是硬件的 busy work 向你学习这种精神!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 14:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表