References

  1. Leetcode post
  2. Github Source

Steps to System Design Interview

  1. Clarify Requirements
    • Ask lots of questions
    • Very important step
    • Spend good amount of time on this step
  2. Adjust scope and state assumptions
    • Can limit scope to simplify and explain that you will come back to it at a later time
  3. Back of the envelope calculations
    • This should set upper bounds on the high level design
  4. High Level Design
    • Do drawings at this time
    • Keep it high level and explain trade offs
    • There is no one right answer
    • Stay in scope but try to leave room for future scale and features
  5. Detailed Design
    • Discuss failure scenarios, how redundancy is provided, bottle necks,
    • Discuss prevention of issues like thundering herd, hotspots, single point of failures etc
    • Focus on security as well in this step

Algorithms and their Usage

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.

Consistent Hashing

It is used to evenly divide work among a bunch of resources while giving flexibility for resources to be added or removed. Mostly used in database sharding.

Geohash / S2 Geometry

Geohash can be 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.

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 exceeds 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)

Frugal Streaming

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

Count-Min Sketch

Count frequency in a stream of data. Approximate algorithm similar to bloom filter.

Least Recently Used (LRU)

Very popular eviction algorithm for caches or other resources.

B-Trees

Self balancing tree used in systems where the contents of the tree cannot completely fit in main memory. The data structure is designed to reduce amount of disk accesses. It is heavily used in MySQL to keep track of indexes.

Merkle Tree

Merkle tree or hash tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers. They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks.

  • Used in Bitcoin implementation
  • Apache Cassandra uses Merkle trees to detect inconsistencies between replicas of entire databases.
  • Introduction to Merkle Trees

Honorable Mentions