算法日记

面经题：

给定一个Doubly Linked List,以及一个装有node指针的array，其中只含有list node的子集。如果把前后连续的node，算作一个block，求有多少个block？（用个图好理解一点）

思路：用一个Hash set，把array中所有的node加入其中，然后遍历array，对于当前node，向左右查找next和prev所指向的node，并把它们从hash set移除。这样一来，只要找到一个node，就可以把整个block从set中移除。在这个过程中，count++，并最终返回。总体的时间复杂度，应该是O(N), N是array的长度。尽管for loop种嵌套了while loop，但是array中的元素，每个只会遍历一次。在它被移除后，即使再被遍历到，也不会再进入while循环。

系统设计题：如何设计一个社交媒体上的图片ID？

PostgreSQL其实有添加Unique ID的功能，但是因为有了sharding，想要ID成为Global Unique ID就必须另行设计。这里的ID有三个基本需求：

1.产生的数据ID需是可以按时间排序的。（比如对一列图片数据的ID进行排序，可以不需要提取太多图片本身的信息）

2.理想的ID是64位的。（这样索引更小，存储也更优，像Redis）

3.系统要尽量少的引用“可变动因素”——在很少工程师的情况下还可以扩张Instagram的很大一部分原因就是，我们相信简单易懂的方案。

Solution 1: Web应用层生成ID

比如MongoDB自动生成的objectId，或者直接使用UUIDs。

Pro:

1.每个应用线程独立生成ID，最小的降低ID生成的失败和竞争。

2.如果用时间戳作为ID的起始部分，那么ID可以按时间排序。

Con:

1.通常需要更多的存储空间（96位或者更多）来确保ID的合理唯一性。

2.一些UUID类型完全是随机的，无法排序。

Solution 2:通过单独的service来产生ID

Twitter的Snowflake，是一个Thrift服务，使用了Zookeeper来协调各个结点并且产生64位的唯一ID。

Pro：

1. Snowflake的ID只有64位，是UUID的一半。

2.可以放时间戳到ID开头，从而可以按时间排序。

3.分布式系统的concensus机制，例如Raft，保证了系统结点不会挂掉。

Con：

增加了复杂性，而且引入了更多的“可变动因素”（如ZooKeeper, Snowflake服务器）到系统构架中。

Solution 3:数据库Ticket服务器

利用数据库自带的自增特性来确保唯一性。Flicker采用这一方法，不过还用了两台ticket数据库（一个生成偶数，一个生成奇数）来避免单点失败。

Pro：

数据库好理解，带有易预测的可扩张功能。

Con：

1.最终会出现数据写入的瓶颈（尽管Flicker称在高扩展下没有问题）。

2.需要管理多的两台服务器（或者EC2实例）。

3.如果单独使用数据库，会出现单点失效。如果使用多个数据库，则不能保证ID可以按时间排序。（这也是为什么不适用于这道题的原因）

我们采用Solution 2，因为它最符合数据库sharding的需求。PostgreSQL中有一个Schema功能。这并不是数据库table的schema，而是PostgreSQL的逻辑分组。每一个PostgreSQL数据库都有好几个schema，每一个schema都有一到多个表。表名在没个schema中都是唯一的，而不是每个数据库，默认情况下，PostgreSQL会把所有数据都放在一个叫“public”的schema中。

在我们的系统中每个“逻辑”分片都是一个PostgreSQL schema，每个分片的表（比如照片的“点赞”功能）都存在每个schema中。

ID设计：

每个ID都由下面几个部分组成：

41位的毫秒级时间（用于产生41年的ID）

13位用来表示逻辑分片的ID

10位的自增序列，模上1024，意味着每个分片每毫秒可以产生1024个ID

我们就得到了我们的ID，我们把这个id作为insert中的RETURNING返回给应用层。完成了！我们得到了应用中唯一的主键，这个ID还有一个好处是，ID中包含了分片ID可以用来轻松映射到对应的shard。

Most people quit because they look how far they have to go, not how far they have come. -Anonymous