DS-Algorithms

TOPICS

1. Mathematics
2. Bitwise Algorithms
3. Recursion
4. Arrays
5. Searching
6. Sorting
7. Matrix
8. Hashing
9. Strings
10. Linked List
11. Stack
12. Queue
13. Tree
14. Binary Search Tree
15. Heap
16. Graph
17. Greedy
18. BackTracking
19. Dynamic Programming
20. Graph (Advanced)
21. Trie

Mathematics

S.No.	Problem	Solution	Date	Reference

Bitwise Algorithms

S.No.	Problem	Solution	Date	References
1	Given a number N check if the k'th bit is set or not	🔑	20-05-19	-
2	Given a number N determine whether it is even or odd	🔑	20-05-19	-
3	Given a number N determine whether it is a power of 2 or not	🔑	20-05-19	-
4	Given a number N determine the number of set bits	🔑	20-05-19	-
5	Given an integer array that contains every number even number of times, except one number. Find that number.	🔑	20-05-19	A
6	Given an integer array that contains every number even number of times, except 2 numbers. Find the 2 numbers.	🔑	21-05-19	A
7	Given a number N determine the position of the first set bit	🔑	21-05-19	-
8	Given a String as input, generate it's PowerSet	🔑	21-05-19	-
9	Given a number N determine the position & value of the most significant digit	🔑	21-05-19	-
10	Given a number N determine the XOR of all numbers from 1 to N WITHOUT using Loops	🔑	21-05-19	A
11	Given a number N. Find the count of number of set bits from 1 to N	🔑	21-05-19	-
12	Given two numbers A and B. Count number of bits needed to be flipped to convert A to B	🔑	21-05-19	-

Recursion

S.No.	Problem	Solution	Date	References
1	Print numbers from 1 to N without using Loop	🔑	22-05-19	-
2	Print numbers from N to 1 without using Loop	🔑	22-05-19	-
3	Factorial	🔑	22-05-19	-
4 💡	Factorial with Tail Recursion	🔑	22-05-19	-
5 💡	Given a rope of length n and 3 values (a,b,c), we need to make maximum pieces such that every piece has length in set {a,b,c}	🔑	22-05-19	-
6	Josephus Problem	🔑	23-05-19	V1 V2 A1 A2
7	Print all subsets of a given set (string)	🔑	24-05-19	-
8	Given an integer set and a number, print all subsets whose sum is equal to given number			-
9	Given an unsorted array of N elements and an element X. The task is to write a recursive function to check whether the element X is present in the given array or not.			-
10	Given a string, the task is to write a recursive function to check if the given string is palindrome or not.			-
11	Tower of Hanoi			-

Arrays

S.No.	Problem	Solution	Date	References
1	Reversing an Array	C++	25-05-19	-
2 3 💡	Rotating an Array (Naive Approach) Rotating an Array (Efficient Approach)	C++ C++	25-05-19 25-05-19	- -
4 5 💡	Leaders in an Array (Naive Approach) O(n^2) Leaders in an Array (Efficient Approach) O(n)	C++ C++	26-05-19 26-05-19	- -
6 7 💡	Trapping Rainwater (Naive Approach) O(n^2) Trapping Rainwater (Efficient Approach) O(n)	C++ C++ JAVA	26-05-19 26-05-19	- -
8 💡	Stock Buy and Sell	C++	26-05-19	-
9 10	Reverse Arrays in Groups ((Naive Approach) O(n^2)) Reverse Arrays in Groups (Efficient Approach)	C++ C++	27-05-19 27-05-19	- -
11 💡	Maximum Occurred Integer in given Ranges	C++	28-05-19	-
12 💡	Frequencies of Array elements in a Given Range	C++	28-05-19	-
13 💡	Given an Array arr of n elements, Find the position of an element of which sum of elements on LHS is equal to sum of elements on RHS	C++	30-05-19	-
14	Smallest Positive Missing Number from 1 to N in an Array of Size N, which can store any number.	C++	30-05-19	-
15	Given an array, Find first continuous SubArray with Given Sum S	C++	04-05-19	GFG

Searching

S.No.	Problem	Solution	Date	References
1	Linear Search	🔑	01-06-19	-
2	Binary Search [Paytm]	🔑	02-06-19	-
3	Given a Sorted Array, find the number of occurrences of a given number	🔑	03-06-19	-
4	Given a Sorted Binary Array, find the number of 1's in it	🔑	04-06-19	-
5	Find Minimum Number in a sorted rotated array	🔑	05-06-19	-
6	Find two Repeated elements in an array of size N+2 which contains elements from 1 to N	🔑	05-06-19	-
7	Given a sorted array of N elements which contains consecutive elements, and one element is repeated number of times, Find the number and it's frequency.	🔑	05-06-19	-
8	Given an array of size N where all elements are distinct and a number K, Find the K'th smallest element [Microsoft, VMWare, Cisco]	🔑	05-06-19	-

Sorting

S.No.	Problem	Solution	Date	References
1	Bubble Sort	🔑	20/08/19	-
2	Selection Sort	🔑	21/08/19	-
3	Insertion Sort	🔑	21/08/19	-
4	Heap Sort	-	-	-
5	Merge Sort	🔑	22/08/19	-
6	Quick Sort	🔑	28/01/2020	-
7	Counting Sort	-	-	-
8	Cycle Sort	-	-	-
9	Radix Sort	-	-	-
10	Shell Sort	-	-	-
11	Inversion Count	🔑	29/01/2020	-
12	Union of 2 Sorted Arrays	🔑	01/02/2020	-
13	Intersection of 2 Sorted Arrays	🔑	01/02/2020	-
14	Count No of Triangles Possible	🔑	03-02-2020	GFG
15	3 Way Partitioning	🔑	03-02-2020	-
16	Find Triplets with 0 Sum	🔑	03-02-2020	(LEARNT=> How to use 2 pointer technique)
17	Problem based on Counting Sort	🔑	03-02-2020	-
18	Closest 0's 1's 2's	🔑	03-02-2020	-
19	Sort by Absolute Difference	🔑	04-02-2020	(LEARNT=> Sort an array based on another array using Comparator Interface)
20	Triplet Sum in Array	🔑	04-02-2020	(LEARNT=> How to use 2 pointer technique)

Matrix

S.No.	Problem	Solution	Date	References
1	Print the matrix in the Sanke Pattern	🔑	12-08-19	-
2	Transpose of a Matrix	🔑	12-08-19	-
3 💡	Rotate a Matrix	🔑	13-08-19	-
4 💡	Search an element in a row wise and column-wise sorted Matrix	🔑	13-08-19	-
5	Given a matrix Print the Boundary elements	🔑	14-08-19	-
6 💡	Given a matrix Print the elements in Spiral Order	🔑	-	-
7 💡	Matrix Multiplication	🔑	-	-
8 💡	Determinant of a Matrix	🔑	-	-
9	Implementation of a 2D Matrix (Using C++ Vectors)	🔑	-	-

Hashing

S.No.	Problem	Solution	Date	References
1	Given an array find the most frequent element.	🔑	02-08-19	-
2	Given an array find if there is a subarray with 0 sum.(Naive Solution O(n^2))	🔑	05-08-19	-
3	Given an array find if there is a subarray with 0 sum.(Optimal Solution O(n^2))	🔑	05-08-19	-
4	Given an array, print the frequency of every element.	🔑	02-08-19	-
5	Given an array and a sum x find if there is subarray where sum is aqual to x	🔑	06-08-19	-
6	Find the largest sub-array with given sum	🔑	06-08-19	-
7	Find the smallest sub-array with given sum	🔑	06-08-19	-
8	Find the largest sub-array with 0 sum	🔑	08-08-19	-
9	Find the smallest sub-array with 0 sum	🔑	08-08-19	-
10 💡	Given a binary array find length of the largest subarray having equal number of 0's and 1's	🔑	11-08-19	-
11	Given an unsorted array and a number x, find if there is a pair with sum x	🔑	09-08-19	-

Strings

S.No.	Problem	Solution	Date	References
1	Check if 2 Strings are ANAGRAMS of each other	🔑	24-07-19	-
2	Given a String find the first repeating character	🔑	24-07-19	-
3	Given a String Find the First Non-Repeating Character	🔑	25-07-19	-
4	Given a String Find the Lexicographic Rank of it among all its Permutations	🔑	25-07-19	-
5	Anagram Search	🔑	29-07-19	-
6	Pattern Searching (Naive String Matching Algorithm)	🔑	-	-
7	Pattern Searching (Rabin Karp Algorithm)	🔑	-	-
8	Pattern Searching (KMP(Knuth Morris Pratt) Algorithm)	🔑	-	-
9	Pattern Searching (Suffix Tree Algorithm)	🔑	-	-
10	Check whether 2 strings are rotations of each other or not	🔑	29-07-19	-

Linked List

S.No.	Problem	Solution	Date	References
1	Singly Linked List Implementation	🔑	06-06-19	-
2	Middle Element of a Linked List	🔑	09-06-19	-
3	kth element from the end of a Linked List	🔑	15-06-19	-
4	Reverse a Linked List (Iterative Approach)	🔑	17-06-19	-
5	Reverse a Linked List (Recursive Approach)	🔑	24-06-19	-
6	Detect Loop in a Linked List	🔑	25-06-19	-

Stack

S.No.	Problem	Solution	Date	References
1	Stack Implementation using Linked List	🔑	10-07-19	-
2	Check for Balanced Parenthesis	🔑	10-07-19	-
3	Stack Implementation using Queues	🔑	11-07-19	-
4	Stack Implementation using C++ STL	🔑	14-07-19	-
5	Implement 2 Stacks in an Array	🔑	16-07-19	-
6	Implement n Stacks using 1 Array	🔑	-	-
7	Print Reverse of linked List using Stack	🔑	16-07-19	-
8	Next Greater Element	🔑	18-07-19	-
9	Stock Span Problem	🔑	17-07-19	-
10	Previous Greater Element	🔑	19-07-19	-
11	Next Smaller Element	🔑	19-07-19	-
12	Previous Smaller Element	🔑	19-07-19	-
13	Remove Consecutive Duplicates	🔑	20-07-19	-
14	Remove Paired Duplicates	🔑	21-07-19	-
15	Print Minimum of Stack at each Pop Operation	🔑	21-07-19	-

Queue

S.No.	Problem	Solution	Date	References
1	Queue Implementation using Linked List	🔑	11-07-19	-

Tree

S.No.	Problem	Solution	Date	References
1	DFS Traversal(Java)	🔑	03-10-19	-
2	BFS or Level Order Traversal (Java)	🔑	13-11-19	-
3	Given a Binary Tree, print it's level order traversal such that each level is in new line	🔑	14-11-19	-
4	Given a Binary Tree, find it's height	🔑	14-11-19	-
5	Given a Binary Tree, check if it follows Children-Sum Property	🔑	15-11-19	-
6	Check if a Binary Tree is Balanced or Not (O(n^2))	🔑	15-11-19	-
7	Check if a Binary Tree is Balanced or Not (Optimal Solution O(n))	🔑	19-11-19	1 2
8	Given a Binary Tree, Print all nodes at level K	🔑	16-11-19	-
9	Given a Binary Tree, Check whether it is Binary Search Tree (BST) or not (Inefficient Method)	🔑	20-11-19	1
10	Given a Binary Tree, Check whether it is Binary Search Tree (BST) or not (Efficient Method)	🔑	21-11-19	1
11	Given a Binary Tree, Check whether it is Binary Search Tree (BST) or not (Using Inorder Traversal)	-	-	-
12	Given a Binary Tree, Convert it into a Double Linked List (In-Place)	-	-	-
13	Lowest Common Ancestor in a Binary Tree	-	-	-
14	Maximum Sum Root to Leaf Path	-	-	-
15	Finding the Diameter of Binary Tree	-	28-11-19	-
16	Check if given Preorder, Inorder and Postorder traversals are of same tree	-	-	-
17	Left View of Binary Tree - Iterative Method using Queue	🔑	24-11-19	1

Tire

S.No.	Problem	Solution	Date	References
1	Insertion and Search in Trie	JAVA	14-05-2020	-