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
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
One Diagram to Refer for Microservices Roadmap
Companies like Netflix, Amazon, and others have adopted the concept of microservices in their products due to large benefits offered by microservices.
As we understand, many developers want to know how they should start this journey. So I decided to make this journey clearer by defining a road map for this learning curve.
Container - A container is a standard unit of software that packages up code and all its dependencies so the application runs quickly and reliably from one computing environment to another.
Container orchestration automates containers' deployment, management, scaling, and networking. Enterprises that need to deploy and manage hundreds or thousands of LinuxĀ® containers and hosts can benefit from container orchestration.
Load balancer is a device that acts as a reverse proxy and distributes network or application traffic across several servers.
Load balancers are used to increase the capacity (concurrent users) and reliability of applications.
Monitoring and Alerting : In a microservice architecture, if you want to have a reliable application or service, you have to monitor the functionality, performance, communication, and any other aspect of your application in order to achieve a responsible application. Promethous is widely popular.
Distributed Tracking - when it comes to microservice architecture, a request may be passed through different services, which makes it difficult to debug and trace because the codebase is not in one place, so here distributed tracing tool can be helpful.
Message Broker - A message broker is software that facilitates the exchange of messages between applications, systems, and services.
Database - in most systems, we need to persist data, because we would need the data for further processes or reporting, etc.
Caching - Caching reduces latency in service-to-service communication of microservice architectures.
Cloud service provider -is a third-party company offering a cloud-based platform, infrastructure, application, or storage services.
API Management: API management is the process of designing, publishing, documenting, and analyzing APIs in a secure environment.
Application Gateway -An application gateway or application level gateway (ALG) is a firewall proxy that provides network security. It filters incoming node traffic to certain specifications, meaning only transmitted network application data is filtered.
Service Registration -A service registry is a database used to keep track of the available instances of each microservice in an application. The service registry needs to be updated each time a new service comes online and whenever a service is taken offline or becomes unavailable.
#microservices #microservicesarchitecture #database #nosql #architecture #systemdesign #java # #cloud #software #management #kubernetes #docker #deveops# #learning #learningeveryday
Companies like Netflix, Amazon, and others have adopted the concept of microservices in their products due to large benefits offered by microservices.
As we understand, many developers want to know how they should start this journey. So I decided to make this journey clearer by defining a road map for this learning curve.
Container - A container is a standard unit of software that packages up code and all its dependencies so the application runs quickly and reliably from one computing environment to another.
Container orchestration automates containers' deployment, management, scaling, and networking. Enterprises that need to deploy and manage hundreds or thousands of LinuxĀ® containers and hosts can benefit from container orchestration.
Load balancer is a device that acts as a reverse proxy and distributes network or application traffic across several servers.
Load balancers are used to increase the capacity (concurrent users) and reliability of applications.
Monitoring and Alerting : In a microservice architecture, if you want to have a reliable application or service, you have to monitor the functionality, performance, communication, and any other aspect of your application in order to achieve a responsible application. Promethous is widely popular.
Distributed Tracking - when it comes to microservice architecture, a request may be passed through different services, which makes it difficult to debug and trace because the codebase is not in one place, so here distributed tracing tool can be helpful.
Message Broker - A message broker is software that facilitates the exchange of messages between applications, systems, and services.
Database - in most systems, we need to persist data, because we would need the data for further processes or reporting, etc.
Caching - Caching reduces latency in service-to-service communication of microservice architectures.
Cloud service provider -is a third-party company offering a cloud-based platform, infrastructure, application, or storage services.
API Management: API management is the process of designing, publishing, documenting, and analyzing APIs in a secure environment.
Application Gateway -An application gateway or application level gateway (ALG) is a firewall proxy that provides network security. It filters incoming node traffic to certain specifications, meaning only transmitted network application data is filtered.
Service Registration -A service registry is a database used to keep track of the available instances of each microservice in an application. The service registry needs to be updated each time a new service comes online and whenever a service is taken offline or becomes unavailable.
#microservices #microservicesarchitecture #database #nosql #architecture #systemdesign #java # #cloud #software #management #kubernetes #docker #deveops# #learning #learningeveryday
š1
One Diagram to Remember for Cš¼š±š² Rš²šš¶š²šš
An essential step in the software development lifecycle is code review. Code reviews are powerful means to improve code quality, establish best practices, opportunity to learn, and knowledge sharing and mentoring, as well as promotes team cohesion.
What to look for in a code review? Try to look for things such as š±š²šš¶š“š» (does this integrate well with the rest of the system and are interactions of different components make sense), š³šš»š°šš¶š¼š»š®š¹š¶šš (does this change is what the developer intended), š°š¼šŗš½š¹š²š š¶šš (is this code more complex than it should be), š»š®šŗš¶š»š“ (is naming good?), š²š»š“. š½šæš¶š»š°š¶š½š¹š²š (solid, kiss, dry), šš²ššš (are different kinds of tests used appropriately, code coverage), šššš¹š² (does it follow style guidelines), š±š¼š°ššŗš²š»šš®šš¶š¼š», etc.
Code review is a conversation, not a queue of commands.
Code review checklist
A checklist helps you to create a structured approach to code reviews. Also, they remind you of all the quality checks you need to perform to approve code into the codebase.
š. š§šæš šš¼ šæš²šš¶š²š šš¼ššæ š¼šš» š°š¼š±š² š³š¶šæšš
Before sending a code to your colleagues, try to read and understand it first. Then, search for parts that confuse you.
š®. šŖšæš¶šš² š® ššµš¼šæš š±š²šš°šæš¶š½šš¶š¼š» š¼š³ ššµš®š š¶š š°šµš®š»š“š²š±
It should explain what changes were at a high level and why those changes were made.
šÆ. šššš¼šŗš®šš² ššµš®š š°š®š» šÆš² š®ššš¼šŗš®šš²š±
Leave to the system everything that can be automated,
PMD, FindBugs, and Checkstyle are the most popular open-source code analyzers,
Jenkins for CI-CD some code smells and bugs (SonarQube).
š°. šš¼š»'š šæšššµ
You need to understand what is changed in every line of it. Read multiple times if required, class by class.
š±. šš¼šŗšŗš²š»š šš¶ššµ šøš¶š»š±š»š²šš
Never mention the person (you), always focus on changes as questions or suggestions and leave at least one positive comment. Explain the "why" in your comments and suggestions for improving it.
š². šš½š½šæš¼šš² š£š„ ššµš²š» š¶šš š“š¼š¼š± š²š»š¼šš“šµ
Don't strive for perfection, but hold to high standards. Don't be a nitpicker.
š³. š š®šøš² šæš²šš¶š²šš šŗš®š»š®š“š²š®šÆš¹š² š¶š» šš¶šš²
We should limit the number of lines of code for review in one sitting. Our brains cannot process so much information at once. The ideal number of LOC is 200 to 400 lines of the core at one time, which is usually 60 to 90 minutes.
8) Review logic, not semicolons
Automation reduces the needless checks and let's you focus on the logic behind the changes rather than syntax errors and typos.
What is your code review process? What works for you, and what does not?
Image credit (Code Review Pyramid): Gunnar Morling
#softwareengineering #programming #systemdesign #developers #bestpractice #coders #software #review #codereview
An essential step in the software development lifecycle is code review. Code reviews are powerful means to improve code quality, establish best practices, opportunity to learn, and knowledge sharing and mentoring, as well as promotes team cohesion.
What to look for in a code review? Try to look for things such as š±š²šš¶š“š» (does this integrate well with the rest of the system and are interactions of different components make sense), š³šš»š°šš¶š¼š»š®š¹š¶šš (does this change is what the developer intended), š°š¼šŗš½š¹š²š š¶šš (is this code more complex than it should be), š»š®šŗš¶š»š“ (is naming good?), š²š»š“. š½šæš¶š»š°š¶š½š¹š²š (solid, kiss, dry), šš²ššš (are different kinds of tests used appropriately, code coverage), šššš¹š² (does it follow style guidelines), š±š¼š°ššŗš²š»šš®šš¶š¼š», etc.
Code review is a conversation, not a queue of commands.
Code review checklist
A checklist helps you to create a structured approach to code reviews. Also, they remind you of all the quality checks you need to perform to approve code into the codebase.
š. š§šæš šš¼ šæš²šš¶š²š šš¼ššæ š¼šš» š°š¼š±š² š³š¶šæšš
Before sending a code to your colleagues, try to read and understand it first. Then, search for parts that confuse you.
š®. šŖšæš¶šš² š® ššµš¼šæš š±š²šš°šæš¶š½šš¶š¼š» š¼š³ ššµš®š š¶š š°šµš®š»š“š²š±
It should explain what changes were at a high level and why those changes were made.
šÆ. šššš¼šŗš®šš² ššµš®š š°š®š» šÆš² š®ššš¼šŗš®šš²š±
Leave to the system everything that can be automated,
PMD, FindBugs, and Checkstyle are the most popular open-source code analyzers,
Jenkins for CI-CD some code smells and bugs (SonarQube).
š°. šš¼š»'š šæšššµ
You need to understand what is changed in every line of it. Read multiple times if required, class by class.
š±. šš¼šŗšŗš²š»š šš¶ššµ šøš¶š»š±š»š²šš
Never mention the person (you), always focus on changes as questions or suggestions and leave at least one positive comment. Explain the "why" in your comments and suggestions for improving it.
š². šš½š½šæš¼šš² š£š„ ššµš²š» š¶šš š“š¼š¼š± š²š»š¼šš“šµ
Don't strive for perfection, but hold to high standards. Don't be a nitpicker.
š³. š š®šøš² šæš²šš¶š²šš šŗš®š»š®š“š²š®šÆš¹š² š¶š» šš¶šš²
We should limit the number of lines of code for review in one sitting. Our brains cannot process so much information at once. The ideal number of LOC is 200 to 400 lines of the core at one time, which is usually 60 to 90 minutes.
8) Review logic, not semicolons
Automation reduces the needless checks and let's you focus on the logic behind the changes rather than syntax errors and typos.
What is your code review process? What works for you, and what does not?
Image credit (Code Review Pyramid): Gunnar Morling
#softwareengineering #programming #systemdesign #developers #bestpractice #coders #software #review #codereview