DataStructuresandAlgorithm
π
this repository. It motivates me.
If you appreciate my work, please Why companies like Amazon, Microsoft, Google focuses on Data Structures and Algorithms
If youβre preparing for a tech interview of any big tech company like Adobe, Amazon, Microsoft, Google, etc. β most probably, you would have known about the importance of Data Structures and Algorithms to crack these interviews. Yes, most of the interviews for technical roles in these companies are focused on measuring the Data Structures and Algorithms knowledge of the candidates.
There are multiple reasons why Product Based Companies place so much emphasis on Data Structures and Algorithms as stated below:
 Data Structures and Algorithms demonstrate the problemsolving ability of a candidate. There is no room to craft elaborate stories and this means that either the candidate can solve the problem or they canβt.
 Questions based on Data Structures and Algorithms can be scaled up or down according to the knowledge level of the candidate. This means that a variety of candidates can be tested using roughly the same problems.
 Data Structures and Algorithms are used to test the analytical skills of the candidates as they are a useful tool to pick out the underlying algorithms in realworld problems and solve them efficiently.
 Data Structures and Algorithms are the fundamentals of Software Development. They remain the same no matter what new technology is used and that puts the focus on the problem rather than the technology in the interview process.
 Introduction to Git
 Introduction to Programming
 Types of languages
 Flowcharts & Pseudocode
 Flow of the program
 Time & Space Complexity

Array
 Introduction
 Memory management
 Input and Output
 ArrayList Introduction
 Sorting
 Insertion Sort
 Selection Sort
 Bubble Sort
 Count Sort
 Radix Sort
 Searching
 Linear Search
 Binary Search
 Modified Binary Search
 Two Pointer
 Subarray Questions

Strings
 Introduction
 How Strings work
 Comparison of methods
 Operations in Strings
 StringBuilder in java

Maths for DSA
 Introduction
 Complete Bitwise Operators
 Prime numbers
 HCF / LCM
 Sieve of Eratosthenes
 Newton's Square Root Method
 Number Theory
 Euclidean algorithm
 Advanced Concepts for CP (later in the course)
 Bitwise + DP
 Extended Euclidean algorithm
 Modulo Properties
 Modulo Multiplicative Inverse
 Linear Diophantine Equations
 Fermatβs Theorem
 Wilson's Theorem
 Lucas Theorem
 Chinese Remainder Theorem

Functions
 Introduction
 Solving the above math problems in code
 Scoping in Java
 Shadowing
 Variable Length Arguments

Recursion
 Introduction
 Why recursion?
 Flow of recursive programs  stacks
 Convert recursion to iteration
 Tree building of function calls
 Tail recursion

Sorting:
 Merge Sort
 Quick Sort
 Cyclic Sort

Backtracking
 Sudoku Solver
 NQueens
 NKnights
 Maze problems
 Recursion String Problems
 Recursion Array Problems
 Recursion Pattern Problems
 Subset Questions

Space and Time Complexity Analysis
 Introduction
 Comparisons of various cases
 Solving Linear Recurrence Relations
 Solving Divide and Conquer Recurrence Relations
 BigO, BigOmega, BigTheta Notations
 Get equation of any relation easily  best and easiest approach
 Complexity discussion of all the problems we do
 Space Complexity
 Memory Allocation of various languages
 NPCompleteness and Hardness

Object Oriented Programming
 Introduction
 Classes & its instances
 this keyword in Java
 Properties
 Inheritance
 Abstraction
 Polymorphism
 Encapsulation
 Overloading & Overriding
 Static & NonStatic
 Access Control
 Interfaces
 Abstract Classes
 Singleton Class
 final, finalize, finally
 Exception Handling

Stacks & Queues
 Introduction
 Interview problems
 Push efficient
 Pop efficient
 Queue using Stack and Vice versa
 Circular Queue

Linked List
 Introduction
 Fast and slow pointer
 Cycle Detection
 Single and Doubly LinkedList
 Reversal of LinkedList

Dynamic Programming
 Introduction
 Recursion + Recursion DP + Iteration + Iteration Space Optimized
 Complexity Analysis
 0/1 Knapsack
 Subset Questions
 Unbounded Knapsack
 Subsequence questions
 String DP

Trees
 Introduction
 Binary Trees
 Binary Search Trees
 DFS
 BFS
 AVL Trees
 Segment Tree
 Fenwick Tree / Binary Indexed Tree
 Square Root Decomposition

Heaps
 Introduction
 Theory
 Priority Queue
 Two Heaps Method
 kway merge
 top k elements
 interval problems

HashMap
 Introduction
 Theory  how it works
 Comparisons of various forms
 Limitations and how to solve
 Map using LinkedList
 Map using Hash
 Chaining
 Probing
 HuffmanEncoder
 Tries

Graphs
 Introduction
 BFS
 DFS
 Working with graph components
 Minimum Spanning Trees
 Kruskal Algorithm
 Prims Algorithm
 Dijkstraβs shortest path algorithm
 Topological Sort
 Bellman ford
 A* pathfinding Algorithm
What basic data structures and algorithms should one learn before starting competitive programming?
 Basic data sturctures (arrays, queues, linked lists, etc.).
 Bit manipulation.
 Advanced data structures:
 UnionFind Disjoint Sets.
 Segment Tree.
 Binary Indexed Tree (a.k.a Fenwik Tree).
 Graph.
 Tree
 Skip Lists.
 Some self balanced Binary Search trees (e.g. Red Black Trees).
 Brute force and it's tricks and advanced techniques (such as, pruning, bitmasks, meet in the middle, iterative deepining etc.)
 Binary Search (not only the basic code).
 Greedy.
 Dynamic programming and it's tricks and optimisations (Knuth optimisation, convex hull optimisation, bitmasks, etc.).
 Graph algorithms:
 Traversal (DFS & BFS) algorithms and how to use them.
 Finding Connected Components.
 Flood Fill.
 Topological Sorting (the famous algorithm uses DFS but you should also know Kahn's algorithm that uses BFS as it has much applications).
 Bipartite Check.
 Finding Strongly Connected Components.
 Kruskal's and Prim's algorithms for finding the Minimum Spanning Tree of a graph and the variants of the problem.
 Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) Problem with out negaitive cycles.
 BellmanFord's algorithm for solving the SSSP problem with negative sycles.
 FloydWarshall's algorithm for solving the All Pairs Shortest Path (APSP) problem and it's variants.
 Network Flow problem (all it's algorithms, variants and the problems reducable to it). 9 Mathematics:
 You should be familiar with the BigInteger class in Java (maybe write your own if you are in love with C++).
 Some Combinatorics.
 Number Theory (all what you can learn about it).
 Probability Theory.
 FloydCycle detection algorithm.
 Game Theory (especially impartial games and SpragueGrundy Theorem).
 Strings:
 Basic Manipulation.
 ZAlgorithm for finding a pattern in a text.
 KnuthMorrisPratt Algorithm for finding a pattern in a text.
 Hashing and RabinKarp Algorithm for finding a pattern in a text.
 Trie data structure.
 AhoCorasick Algorithm for finding multiple patterns in a text.
 Suffix Array data structure.
 Suffix Automaton data structure.
 Computational Geometry Algorithms.
Steps to post your solutions
In order to sumbit the solution to the respective questions, you need to follow the following steps.
 Firstly, you need to fork the repository CompetitiveProgrammingandDSA.
 Every week we'll be posting 67 questions inside the /Questions folder inside the questions.md file. These questions will be classified into different levels of difficulties.
 In order to submit the solution to the respective questions, you need to create a file for that particular question inside the /solutions folder. Say, you want to post the solution to question 1 in java, create a file named solution_1.java. The naming convention is solution_number.(your_language) . Obviously, you can write in the programming language of your choice.
 Now, since you have done your changes, next step would be to commit them.
 Lastly, you have to create a pull request. Keep base repo as the CODE++ original repo and the head repo as your forked one. Give a suitable name to the PR. Finally click on Create Pull Request.
 The solution with the best time and space complexity will be merged into the original repository.
Important  Every now and then, usually before creating a pull request to post your solutions, please create a reverse pull request(i,e, keep base repo as your forked one and the head repo as the CODE++ original repo) so that your forked repo gets updated wrt original repo. Or, you can simply click on Fetch upstream in your forked repo.