Welcome to this GitHub repository that provides a comprehensive collection of Data Structures and Algorithms (DSA) concepts along with solutions to common coding questions. Additionally, it includes various React.js projects to demonstrate practical implementations and usage of these DSA concepts in real-world scenarios.
- Time Complexity Contraints Table
- Problem Solving Techniques
- JavaScript Event Loop Diagram
- Repository Setup Guide
I am a fresher looking for an SDE Role. I am a Google Summer of Code 2021 participant with skills in Web Development and Machine Learning. I have also worked on various projects, such as MQTT servers using Flutter.
| Contraints | Time Complexity |
|---|---|
| 1018 | O(logN) |
| 108 | O(N) |
| 106 | O(NlogN) |
| 104 | O(N2) |
| 500 | O(N3) |
| 85-90 | O(N4) |
| 20 | O(2N) |
| 11 | O(N!) |
If your goal is to design an algorithm yourself, one of the things it is important to realize is the expected running time of your algorithm. Usually, you can guess it from the problem statement (specifically, from the subsection called constraints) as follows. Modern computers perform roughly 108 β109 operations per second. So, if the maximum size of a dataset in the problem description is π = 105 , then most probably an algorithm with quadratic running time is not going to fit into time limit (since for π = 105 , π2 = 1010 ) while a solution with running time π(π log π) will fit. However, an π(π2 ) solution will fit if π is up to 103 = 1000, and if π is at most 100, even π(π3 ) solutions will fit. In some cases, the problem is so hard that we do not know a polynomial solution. But for π up to 18, a solution with π(2π π2 ) running time will probably fit into the time limit.
When you have access to the solution for smaller instances of a given problem, you can use recursive or dynamic programming techniques to construct the solution to the original problem efficiently. This involves breaking the problem into smaller subproblems and solving them independently before combining their solutions to solve the larger problem.
Divide and Conquer involves breaking the problem into two or more smaller and independent subproblems and then solving the original problem using the solutions to these subproblems. It's particularly useful for problems that can be easily solved when broken down into simpler components.
For certain problems, you can split the input or execution into multiple cases and solve each case independently. This approach is helpful when different cases require different strategies to reach a solution.
Sometimes, a problem can be subsumed by a more general problem that is easier to solve. If you can identify such a generalization, you can solve the more general problem and then map the solution back to the original problem.
Consider whether there are specific data structures that directly map to the given problem. Choosing appropriate data structures can significantly simplify the problem-solving process.
Starting with a brute-force solution, you can iteratively refine it to improve its efficiency and effectiveness. This involves formalizing the brute-force approach and then optimizing it step by step.
Finding solutions to small concrete instances of the problem can help you understand the patterns and properties that can be generalized to solve arbitrary instances of the problem.
If you encounter a problem that bears similarities to another problem with a known solution, you can use the known solution as a subroutine to solve the current problem.
You can describe the problem using graphs and utilize existing graph algorithms to solve it efficiently. This approach is particularly useful for problems with graph-like structures.
Expressing the relationships and constraints in the problem using equations can provide valuable insights into the problem's nature and lead to an analytical solution.
Introducing new elements or modifications to the problem can help you approach a solution more effectively. This could involve transforming the problem or adding additional constraints.
If you find a slightly different problem that can be solved easily, you can try to map it back to your original problem, thus solving the initial problem indirectly.
In some cases, the problem can be decomposed into subproblems that can be solved independently and concurrently on different machines, leveraging parallel computing power.
Save intermediate results or solutions to avoid redundant computations and look them up when needed, which can significantly speed up the overall solving process.
Exploit any symmetry in the input or solution space to reduce the search space and optimize the problem-solving process.
- Install Docker.
- Install Dev-container.
- Run the following commands in the terminal:
sudo groupadd docker
sudo usermod -aG docker $USER- Start Docker:
sudo systemctl start docker- Build Docker Image for Linux:
sudo docker build . -t <ImageName>- Start the Docker Image:
sudo docker run -it --rm -v `pwd`:/work <ImageName/Id>- Directly run Step 1: Script Change User Permission:
chmod u+x run.sh
sed -i -e 's/\r$//' run.sh(Change your Docker name in run.sh)
- Directly run Step 2: After the first time, follow step 2 only:
./run.sh- List the Docker Image:
sudo docker container ls- Stop the Docker Image:
sudo docker stop container_IDdocker build . -t <ImageName/Id>docker run -it --rm -v ${pwd}:/work <ImageName/Id>Finally, open files in Remote Server Vscode using the Remote Vscode Extension. Install C++ and Cmake extensions for a smooth development experience.
Check Total Files:
git ls-files | wc -l
git ls-files "./*.json" | wc -lCaution: Always keep your date and time updated for both operating systems.