ALGORITHM YOU SHOULD KNOW for PREPARING SYSTEM DESIGN INTERVIEW 💡
🔺REQUIREMENTS :-
KNOW WHEN TO USE
KNOW HOW IT WORKS
◾1) BLOOM FILTER
It is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.
- use case :: Build a Web crawler
◾2) FRUGAL STREAMING
It uses only one unit of memory per group to compute a quantile for each group.
-use case :: Find the nth percentile of the data stream.
◾3) GEOHASH/ S2 GEOMETRY
A collection of efficient yet exact mathematical predicates for testing relationships among geometric primitives.
-use case :: Location-based search results with DynamoDb and Geohash.
◾4) HYPERLOGLOG
It is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset.
-use case :: privacy-preserving traffic heat map for the city.
◾5) LEAKY BUCKET/ TOKEN BUCKET
A mechanism to control the amount and the rate of the traffic sent to the network.
-use case :: Design a scalable rate-limiting algorithm.
◾6) LOSSY COUNT
It is used to identify elements in a data stream whose frequency count exceeds a user-given threshold.
-use case :: Frequency count over the data streams.
◾7) OPERATIONAL TRANSFORMATION
It is used for supporting a range of collaboration functionalities in advanced collaborative software systems.
-use case :: Handling editing collision in Google docs.
◾8) QUADTREE/ RTREE
It is a two-dimensional analog of octrees and is most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
-use case :: Find nearby interest points
◾9) RAY CASTING
It is the most basic of many computer graphics rendering algo that uses geometric algo of ray tracing.
-use case :: Using longitude and latitude, return the Country of the point.
◾10) REVERSE INDEX
It is an index of keywords that stores records of documents that contain keywords in the list.
-use case: Building a complete Tweet index.
◾11) RSYNC ALGORITHM
Used for reducing the cost of a file transfer by avoiding the transfer of blocks that are already at the destination.
-use case :: Streaming file Sync
◾12) TRIE ALGORITHM
Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length)
-use case :: Autocomplete features using Trie
13) STRING BUFFER
-use case :: Banking transactions because it follows thread synchronisation
13) STRING BUILDER
-use case :: BOOKMYSHOW OR IRCTC ticket booking because it NOT following thread synchronisation
collab credit - windsoon / ansh /Aman
#software #design #google #systemdesign #backend #backenddeveloper #softwareengineer #algorithms
🔺REQUIREMENTS :-
KNOW WHEN TO USE
KNOW HOW IT WORKS
◾1) BLOOM FILTER
It is a data structure designed to tell you, rapidly and memory-efficiently, whether an element is present in a set.
- use case :: Build a Web crawler
◾2) FRUGAL STREAMING
It uses only one unit of memory per group to compute a quantile for each group.
-use case :: Find the nth percentile of the data stream.
◾3) GEOHASH/ S2 GEOMETRY
A collection of efficient yet exact mathematical predicates for testing relationships among geometric primitives.
-use case :: Location-based search results with DynamoDb and Geohash.
◾4) HYPERLOGLOG
It is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset.
-use case :: privacy-preserving traffic heat map for the city.
◾5) LEAKY BUCKET/ TOKEN BUCKET
A mechanism to control the amount and the rate of the traffic sent to the network.
-use case :: Design a scalable rate-limiting algorithm.
◾6) LOSSY COUNT
It is used to identify elements in a data stream whose frequency count exceeds a user-given threshold.
-use case :: Frequency count over the data streams.
◾7) OPERATIONAL TRANSFORMATION
It is used for supporting a range of collaboration functionalities in advanced collaborative software systems.
-use case :: Handling editing collision in Google docs.
◾8) QUADTREE/ RTREE
It is a two-dimensional analog of octrees and is most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
-use case :: Find nearby interest points
◾9) RAY CASTING
It is the most basic of many computer graphics rendering algo that uses geometric algo of ray tracing.
-use case :: Using longitude and latitude, return the Country of the point.
◾10) REVERSE INDEX
It is an index of keywords that stores records of documents that contain keywords in the list.
-use case: Building a complete Tweet index.
◾11) RSYNC ALGORITHM
Used for reducing the cost of a file transfer by avoiding the transfer of blocks that are already at the destination.
-use case :: Streaming file Sync
◾12) TRIE ALGORITHM
Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length)
-use case :: Autocomplete features using Trie
13) STRING BUFFER
-use case :: Banking transactions because it follows thread synchronisation
13) STRING BUILDER
-use case :: BOOKMYSHOW OR IRCTC ticket booking because it NOT following thread synchronisation
collab credit - windsoon / ansh /Aman
#software #design #google #systemdesign #backend #backenddeveloper #softwareengineer #algorithms