Algorithm you should know before system design.

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

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

• Build a Web Crawler

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

• Find the nth percentile of the data stream

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.

• Location-based search results with DynamoDB and Geohash

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

• Everything You Need To Know About API Rate Limiting
• How to Design a Scalable Rate Limiting Algorithm

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

• Fast and Reliable Ranking in Datastore
• Frequency Counts over Data Streams
• How we built rate limiting capable of scaling to millions of domains
• Rate-limiting strategies and techniques

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

• How Google docs handle editing collisions
• Collaborative editing

• Spatial Indexing with Quadtrees
• Find nearby interest points

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.

• Ray Casting Algorithm

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

• How search engines work: Crawling, Indexing, Aand Ranking
• Building a complete Tweet index

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.

• Streaming File Synchronization

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

• How to Design an Autocomplete System
• Spell Checkers
• prefix matching words (IP Addresses, Phone Numbers)
• Auto-complete feature using Trie