Prerequisite
- Basic knowledge of C++ (C++ Training Codes)
CPP Docs
- Link
- DSA Sheets
Day 1 - Array (PDF)
- Asymptotic Notation
- Big O
- Time Complexity
- Space Complexity
- Basic Notations
- O(1) - Constant
- O(log N) - Logarithmic
- O(N) - Linear
- O(N log N) - Linearithmic
- O(N2) - Quadratic
- O(N3) - Cubic
- O(2N) - Exponential
- O(NN) - Exponential
- Basics of Array
- Reverse the Array
# | Problem Name | Practice | Solution |
---|---|---|---|
1 | Reverse the array | GeeksForGeeks | solution |
2 | Reverse String | Leetcode | solution |
3 | Find the maximum and minimum element in an array | GeeksForGeeks | solution |
4 | Complete Sum | CodeStudio | solution |
Day 2 - STL (PDF)
- Standard Template Library (STL)
- Container
array
vector
list
stack
queue
set
map
- Iterator
begin()
end()
rbegin()
rend()
- Algorithm
swap()
min()
&max()
min_element()
&max_element()
minmax()
&minmax_element()
sort()
find()
search()
- Container
- Implement template array class
# | Problem Name | Practice | Solution |
---|---|---|---|
5 | Final Value of Variable After Performing Operations | Leetcode | solution |
6 | Maximum Number of Words Found in Sentences | Leetcode | solution |
7 | Shuffle String | Leetcode | solution |
8 | Check If It Is a Straight Line | Leetcode | solution |
Day 3 - Vector (PDF)
- STL vector
- Constructor
vector<type> v;
vector<type> v(size);
vector<type> v(size, fill_value);
- Methods
- Iterators
- begin()
- end()
- Capacity
- size()
- capacity()
- empty()
- Modifiers and Access
- operator[]
- push_back()
- pop_back()
- insert()
- swap()
- Iterators
- Constructor
# | Problem Name | Practice | Solution |
---|---|---|---|
9 | Value equal to index value | GeeksForGeeks | solution |
10 | Sort an array of 0s, 1s and 2s | GeeksForGeeks | solution |
11 | Cyclically rotate an array by one | GeeksForGeeks | solution |
12 | Palindromic Array | GeeksForGeeks | solution |
Day 4 - Pair (PDF)
- Implement template Pair class
- STL pair
# | Problem Name | Practice | Solution |
---|---|---|---|
13 | Move all negative elements to end | GeeksForGeeks | solution |
14 | Count Items Matching a Rule | LeetCode | solution |
15 | Kth Missing Positive Number | LeetCode | solution |
16 | Plus One | LeetCode | solution |
Day 5 - String & Numbers (PDF)
- Reverse string
- Reverse integer number
- String palindrome
- Integer palindrome
- Fibonacci series with recursion
- Fibonacci series with loop
# | Problem Name | Practice | Solution |
---|---|---|---|
17 | Number of Good Pairs | LeetCode | solution |
18 | How Many Numbers Are Smaller Than the Current Number | LeetCode | solution |
19 | Palindrome Number | LeetCode | solution |
20 | Fibonacci Number | LeetCode | solution |
21 | Reverse Integer | LeetCode | solution |
Day 6 - Bit Manipulation (PDF)
- Bitwise Operators
|
Bitwise OR operator- used to set bit to 1
&
Bitwise AND operator- used to set bit to 0
- used to get nth bit
~
Bitwise NOT operator- used to inverts the bits
<<
Bitwise left shift operator>>
Bitwise right shift operator
# | Problem Name | Practice | Solution |
---|---|---|---|
22 | Number of 1 Bits | Leetcode GeeksForGeeks | solution |
23 | Number of Steps to Reduce a Number to Zero | LeetCode | solution |
24 | Minimum Bit Flips to Convert Number | LeetCode | solution |
25 | Hamming Distance | LeetCode | solution |
26 | Complement of Base 10 Integer | LeetCode | solution |
27 | Binary Gap | LeetCode | solution |
28 | Reverse Bits | LeetCode | solution |
Day 7 - Bit Manipulation (PDF)
^
XOR Operator- data encryption
- data decryption
- find missing number from 1 - n range
- find non repeating number
- add 2 numbers without arithmetic operators
# | Problem Name | Practice | Solution |
---|---|---|---|
29 | Missing Number | LeetCode | solution |
30 | Find the Duplicate Number | LeetCode | solution |
31 | XOR Operation in an Array | LeetCode | solution |
32 | Decode XORed Array | LeetCode | solution |
33 | Single Number | LeetCode | solution |
34 | Counting Bits | LeetCode | solution |
35 | Count total set bits | GeeksForGeeks | solution |
36 | Power of Two | LeetCode / GeeksForGeeks | solution |
37 | Bit Difference | GeeksForGeeks | solution |
Day 8 - Bit Manipulation (PDF)
(num & 1) == 0
- Check if the integer is evenx = x & (1<<n)
- Get n-th bitx = x | (1<<n)
- Set n-th bitx = x & ~(1<<n)
- Unset n-th bitx = x ^ (1<<n)
- Toggle n-th bity = x & (-x)
ory = x & !(x-1)
- Get the rightmost 1's bity = x & (x-1)
- Unset rightmost 1's bit- Find the two non-repeating elements in an array of repeating elements
- swap numbers without temp variable
int a = 10;
int b = 20;
// method 1 : using arithmatic operator
a = a + b;
b = a - b;
a = a - b;
// method 2 : using bitwise operator
a = a ^ b;
b = a ^ b;
a = a ^ b;
# | Problem Name | Practice | Solution |
---|---|---|---|
38 | Find the two non-repeating elements in an array of repeating elements | LeetCode / GeeksForGeeks | solution |
39 | Find position of set bit | GeeksForGeeks | solution |
40 | Set all the bits in given range of a number | GeeksForGeeks | solution |
Day 9 - Sorting Algorithms (PDF)
- Sorting
- Time Complexity
- Space Complexity
- Stablity
- Recursion / Iterative
- Comparision Function
- Swap Function
- Selection Sort
- Time - O(N2)
- Space - O(1)
- Non Stable
- Iterative
- Inplace
void selectionSort(int arr[], int n){
int min_value, min_index;
for (int i = 0; i < n-1; i++){
min_value = arr[i];
min_index = i;
for (int j = i+1; j < n; j++){
if (arr[j] > min_value){
min_value = arr[j];
min_index = j;
}
}
swap(arr[i], arr[min_index]);
}
}
Day 10 - Sorting Algorithms (PDF)
- Bubble Sort
- Time - O(N2)
- Space - O(1)
- Stable
- Iterative
- Inplace
void bubbleSort(int arr[], int n){
for (int i = 0; i < n-1; i++){
bool flag = true;
for (int j = 0; j < n-1; j++){
if (arr[j] > arr[j+1]){
swap(arr[j],arr[j+1]);
flag = false;
}
}
if (flag) break;
}
}
- Insertion Sort
- Time - O(N2)
- Space - O(1)
- Stable
- Iterative
- Inplace
void insertionSort(int arr[], int n){
int val, j;
for (int i = 1; i < n; i++){
val = arr[i];
j = i;
while(j>0 && arr[j-1] > val){
arr[j] = arr[j-1];
j--;
}
arr[j] = val;
}
}
Day 11 - Sorting Algorithms (PDF)
- Merge 2 Sorted Array
- Merge Sort
- Time - O(N log N)
- Space - O(n)
- Stable
- Recursive
- Divide and conquer
void mergeSort(int arr[], int n){
if (n < 2) return;
int mid = n/2;
int left[mid];
int right[n - mid];
for (int i = 0; i < mid; i++){
left[i] = arr[i];
}
for (int i = mid; i < n; i++){
right[i-mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, n-mid);
margeArray(left, right, arr, mid, n-mid);
}
Day 12 - Sorting Algorithms (PDF)
- Quick Sort
- Time - Avg. - O(N log N), Worse - O(N2)
- Space - O(n)
- Stable
- Recursive
- Divide and conquer
int partition(int arr[], int start, int end){
int pivot = arr[end];
int j = start;
for (int i = start; i < end; i++){
if (arr[i] <= pivot){
swap(arr[i], arr[j]);
j++;
}
}
swap(arr[end], arr[j]);
return j;
}
void quickSort(int arr[], int start, int end){
if (start >= end) return; // base condition
int pivot = partition(arr, start, end);
quickSort(arr, start, pivot-1); // left arr
quickSort(arr, pivot+1, end); // right arr
}
Day 13 - Linked List (PDF)
- Implement Singly LinkedList
- Implement Node Class/Struct
- Implement functions
push_front()
push_back()
display()
size()
last()
class Node{
public:
int data;
Node* next;
Node(int data = 0, Node* next = nullptr) : data(data), next(next){}
}
Day 14 - Linked List (PDF)
- Implement Functions
pop_front()
pop_back()
search()
at()
Day 15 - Linked List (PDF)
- insert array element to list at back in O(N) time
- find mid element
- by using length (2 iteration)
- by using 2 (slow & fast) pointers (single iteration)
- find ith element from last
- by using length (2 iteration)
- by using 2 (slow & fast) pointers (single iteration)
# | Problem Name | Practice | Solution |
---|---|---|---|
41 | Middle of the Linked List | LeetCode | solution |
42 | Convert Binary Number in a Linked List to Integer | LeetCode | solution |
43 | Delete Node in a Linked List | LeetCode | solution |
44 | Remove Duplicates from Sorted List | LeetCode | solution |
Day 16 - Linked List (PDF)
- Reverse a Linked List
- by creating new list
- by stack
- by 3 pointers
- by push front same node
# | Problem Name | Practice | Solution |
---|---|---|---|
45 | Remove Linked List Elements | LeetCode | solution |
46 | Reverse Linked List | LeetCode | solution |
47 | Reverse Linked List II | LeetCode | solution |
Day 17 - Linked List (PDF)
- Loop Detection
- using map / set
- is cycle found
# | Problem Name | Practice | Solution |
---|---|---|---|
48 | Linked List Cycle | LeetCode | solution |
Day 18 - Linked List (PDF)
- Loop Detection
- return cycle node
- remove cycle
# | Problem Name | Practice | Solution |
---|---|---|---|
49 | Linked List Cycle II | LeetCode | solution |
Day 19 - Linked List (PDF)
- Check Palindrome in Linked List
- Reorder Linked List
# | Problem Name | Practice | Solution |
---|---|---|---|
50 | Palindrome Linked List | LeetCode | solution |
51 | Reorder List | LeetCode | solution |
Day 20 - Linked List (PDF)
- Merge Two Sorted Lists
- Add Two Numbers
# | Problem Name | Practice | Solution |
---|---|---|---|
52 | Merge Two Sorted Lists | LeetCode | solution |
53 | Add Two Numbers | LeetCode | solution |
Day 21 - Stack (PDF)
- Stack Interface
push()
pop()
top()
size()
empty()
- Stack Implementation
- array based stack
- linked list based stack
- Template Implementation of stack
# | Problem Name | Practice | Solution |
---|---|---|---|
54 | Implement Stack using Array | Work@Tech | solution |
55 | Implement Stack using Linked List | Work@Tech | solution |
56 | Valid Parentheses | LeetCode, Work@Tech | solution |
Day 22 - Queue (PDF)
- Queue Interface
push()
pop()
top()
size()
empty()
- Queue Implementation
- array based queue
- linked list based queue
- Template Implementation of queue
# | Problem Name | Practice | Solution |
---|---|---|---|
57 | Implement Queue using Array | Work@Tech | solution |
58 | Implement Queue using Linked List | Work@Tech | solution |
59 | Implement Queue using Stacks | LeetCode, Work@Tech | solution |
60 | Implement Stack using Queues | LeetCode, Work@Tech | solution |
Day 23 - Stack & Queue Problems (PDF)
- Min Stack
- Next Greater Element
# | Problem Name | Practice | Solution |
---|---|---|---|
61 | Implement Min Stack | LeetCode, Work@Tech | solution |
62 | Next Greater Element | Work@Tech | solution |
63 | Next Greater Element II | LeetCode | solution |
Day 24 - Stack & Queue Problems (PDF)
- Tower of Hanoi
- Expression resolution
- Infix
- Prefix
- Postfix
# | Problem Name | Practice | Solution |
---|---|---|---|
64 | Tower of Hanoi | GeeksForGeeks | solution |
65 | Postfix Notation | Work@Tech | solution |
Day 25 - Stack & Queue Problems (PDF)
- Infix to Postfix Conversion
- Simplify Directory Path
# | Problem Name | Practice | Solution |
---|---|---|---|
66 | Simplify Directory Path | Work@Tech | solution |
67 | Sliding Window Maximum | Work@Tech, LeetCode | solution |
Day 26 - Binary Tree (PDF)
- Binary Tree
- Structure of Binary Tree
- Traversal
- Inorder
- Preorder
- Postorder
- Number of Nodes in Tree
- Max Height of Tree
# | Problem Name | Practice | Solution |
---|---|---|---|
68 | Binary Tree Inorder Traversal | Work@Tech | solution |
69 | Binary Tree Preorder Traversal | Work@Tech | solution |
70 | Binary Tree Postorder Traversal | Work@Tech | solution |
71 | Maximum Depth of Binary Tree | Work@Tech | solution |
Day 27 - Binary Tree (PDF)
- Level Order Traversal
- Iterative Traversal
- Inorder
- Preorder
- Postorder
- Identical Binary Trees
- Symmetric Binary Tree
- Invert Binary Tree
- Diameter of Binary Tree
# | Problem Name | Practice | Solution |
---|---|---|---|
72 | Level Order of Binary Tree | Work@Tech | solution |
73 | Identical Binary Trees | Work@Tech | solution |
74 | Symmetric Binary Tree | Work@Tech | solution |
75 | Invert Binary Tree | Work@Tech | solution |
76 | Diameter of Binary Tree | Work@Tech | solution |
Day 28 - Binary Tree (PDF)
- Print each levels
- print ith level of tree
- zig-zeg order traversal
- using stack and queue
- using deque
# | Problem Name | Practice | Solution |
---|---|---|---|
77 | Binary Tree Zigzag Level Order Traversal | Work@Tech | solution |
Day 29 - Binary Tree (PDF)
- Left View of Tree
- Right View of Tree
- Build Tree link
# | Problem Name | Practice | Solution |
---|---|---|---|
78 | Left View of Binary Tree | Work@Tech | solution |
79 | Right View of Binary Tree | Work@Tech | solution |
Day 30 - Binary Tree (PDF)
- Top View of Tree
- Bottom View of Tree
# | Problem Name | Practice | Solution |
---|---|---|---|
80 | Top View of Binary Tree | Work@Tech | solution |
81 | Bottom View of Binary Tree | Work@Tech | solution |