/system-design-algorithms

Advanced data structure and algorithm for system design,系统设计需要了解的算法

MIT LicenseMIT

System design algorithms

Algorithm you should know for preparing system design interview. For example, Learn Geohash / S2 Geometry algorithm for "How to design Uber like system?"

Sponsor

海外兔 - 程序员求职课程,入职不成功不收费

How to contribute

The algorithm and its resources should:

  1. Can answer a system design question. For instance, Building a complete Tweet index can answer "How to implement Twitter search" or "How to implement hashtag in Twitter".
  2. Free to read or watch.
  3. Text would be better than videos.

Requirements

  • Know when to use ☑️
  • Know how it works

Table of contents

  • Bloom filter
  • Frugal Streaming ☑️
  • Geohash / S2 Geometry ☑️
  • HyperLogLog
  • Leaky bucket / Token bucket ✅
  • Lossy Counting ☑️
  • Operational transformation ☑️
  • Quadtree / Rtree ☑️
  • Ray casting ☑️
  • Reverse index
  • Rsync algorithm
  • Trie algorithm

Bloom filter

A Bloom filter is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.

Frugal Streaming

Frugal Streaming uses only one unit of memory per group to compute a quantile for each group

Geohash / S2 Geometry

Geohash can used by 1) dating apps to find romantic matches within a particular cell, and to create chat apps.2) Find nearby locations, and identify places of interest, restaurants, shops and accommodation establishments in an area. 3) Geohashers go on global expeditions to meet people and explore new places.

HyperLogLog

HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset.

Leaky bucket / Token bucket

A mechanism to control the amount and the rate of the traffic sent to the network

Lossy Counting

The lossy count algorithm is an algorithm to identify elements in a data stream whose frequency count exceed a user-given threshold.

Operational transformation

Operational transformation (OT) is a technology for supporting a range of collaboration functionalities in advanced collaborative software systems.

Quadtree / Rtree

Ray casting

Ray casting is the most basic of many computer graphics rendering algorithms that use the geometric algorithm of ray tracing. Given a point with longitude and latitude, return the Country of the point.

Reverse index

Reverse Index: a reverse index is an index of keywords which stores records of documents that contain the keywords in the list.

Rsync algorithm

The rsync algorithm is a technique for reducing the cost of a file transfer by avoiding the transfer of blocks that are already at the destination.

Trie algorithm

Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length)