marcelocoelho1/algorithms

Algorithm Repository

This repository serves as study material to help achieve my goals. Contributions from others are welcome. The repository is currently focused on Java programming language, but I plan to include implementations in other commonly used languages as well.

Fundamental algorithms and concepts

The repository's initial focus is on fundamental algorithms and concepts frequently asked in big tech company interviews, as derived from the book "Cracking the Coding Interview" by Gayle Laakmann McDowell. It follows the book's division:

Data Structures

• Linked Lists
• Trees, Tries, and Graphs
• Stacks and Queues
• Heaps
• Vectors/ArrayLists
• Hash Tables

Algorithms

• Breadth-First Search
• Depth-First Search
• Binary Search
• Merge Sort
• Quick Sort

Concepts

• Bit Manipulation
• Memory (Stack vs. Heap)
• Recursion
• Dynamic Programming
• Big O Time & Space Complexity

Understanding how to use and implement these topics effectively, including their time and space complexity, is crucial.

Problem-Solving Approach

The problem-solving approach used in this repository is derived from the book "Cracking the Coding Interview." It provides a structured methodology to efficiently solve coding problems. When approaching a problem, it is recommended to follow the following step-by-step process:

1. Listen: Pay close attention to all the information provided in the problem description. Every detail might be important for devising an optimal algorithm.

2. Example: Analyze the examples given in the problem. Check if they are special cases or if they are large enough to cover the general problem. Debug your example and try to understand the problem thoroughly.

3. Brute Force: Start by developing a brute-force solution for the problem. Don't worry about efficiency at this stage. State a naive algorithm and estimate its runtime complexity. This step will provide a starting point for optimization.

4. Optimize: Once you have a brute-force solution, optimize it by following these strategies:

   • Look for any unused information in the problem. Utilize all available data.
   • Solve the problem manually on an example and analyze your thought process. How did you arrive at the solution?
   • Solve the problem "incorrectly" to understand the shortcomings of your algorithm. Can you fix those issues?
   • Consider making time vs. space tradeoffs. Hash tables and other data structures can be useful in certain cases.

5. Walkthrough: After optimizing the algorithm, walk through your approach in detail. Make sure you understand each step before starting the implementation.

6. Implement: Write clean and modular code based on the optimal algorithm. Refactor and improve the code as needed to enhance its readability and maintainability.

7. Test: Test your code thoroughly using the following order:

   1. Conceptual test: Walk through your code as if you were conducting a detailed code review.
   2. Test unusual or non-standard code sections.
   3. Focus on hot spots, such as arithmetic operations or handling null nodes.
   4. Start with small test cases, as they are faster to execute and can be equally effective.
   5. Test special cases and edge cases to ensure the algorithm handles them correctly.

Remember to carefully fix any bugs you encounter during testing, making sure your code is correct and performs as expected.

Contributing

Contributions to this repository are highly appreciated. If you have algorithm implementations or improvements, please feel free to submit a pull request. Contributions do not need to be limited to Java; implementations in other commonly used languages are also welcome.