Algo DS Book PDF
Algo DS Book PDF
Algo DS Book PDF
2
Aj’s Guide To algorithm and Data Structure in C/ C++
First Edition
3
Copyright information
All the content and graphics published in this e-book are the property of
www.prodevelopertutorial.com website and the author Ajay. The user of this e-book is
prohibited to reuse, retain, copy, distribute or republish any contents or a part of contents
of this e-book in any manner without written consent of the author. Please contact the
author at [email protected].
We strive to update the contents of our website and tutorials as timely and as precisely as
possible, however, the contents may contain inaccuracies or errors.
www.prodevelopertutorial.com provides no guarantee regarding the accuracy, timeliness or
completeness of our website or its contents including this tutorial. If you discover any errors
on our website or in this book, please notify us at [email protected]
4
Acknowledgements
I would like to thank my parents for everything that they have done for me. I would like to
thank my readers for believing in me and buying this book. I am sure that this book will
provide you enough information to crack any interview and start with competitive
programming.
5
Preface
Before you start with first chapter, please read the below few points which might be useful.
This book is for students, job seekers and professionals alike. This book has covered almost
90+ chapters on data structures and algorithms. All the chapters are explained in great
depth along with example for each topic accompanied with diagrams.
Prerequisites:
There are no pre requisites to study this book. But it is good to know any one programming
language. So that you will be able to understand the code.
Although you can read individual chapters, but I recommend you to study in the way that I
have written to get the best results. It is recommended that you copy the code from the
book and execute it in your system.
6
Index:
Copyright information
Acknowledgements
Preface
Introduction
Sorting Algorithms:
Searching Algorithm
Data structure tutorial 1: Stack Data structure and Implementation using arrays.
Data structure tutorial 2: Stack Data structure and Implementation using Linked List.
Data structure tutorial 3: Singly Linked List.
Data structure tutorial 4: Doubly Linked List [DLL] .
7
Data structure tutorial 5: Circular Singly Linked List.
Data structure tutorial 6: Circular Doubly Linked List.
Data structure tutorial 7: Queue Data Structure with implementation using arrays.
Data structure tutorial 8: Queue Data Structure with implementation using linked list.
Data structure tutorial 9: Circular Queues Data structure with Implementation using arrays.
Data structure tutorial 10: Circular Queue Data structure with Implementation using Linked
List.
8
2. Recursion
3. Dynamic programming approach
4. Backtracking approach
5. Greedy approach
6. Two pointer approach
String matching algorithms tutorial 1. Knuth Morris Pratt String matching algorithm
String matching algorithms tutorial 2. Rabin Karp algorithm
String matching algorithms tutorial 3. Boyer–Moore string-search algorithm
Knapsack Problem:
1. Fractional knapsack
2. Knapsack
Additional Problems:
9
1. Expectations on oncoming topics
2. Mistakes to avoid in an interview.
3. Tell me about yourself
4. Why should we hire you?
5. Why do you want to work for us?
6. What are your greatest strengths and weakness?
7. What are your greatest achievements/ accomplishments?
8. Any questions for us?
9. Where do you want to see yourself in 5 years?
10. How to you work under pressure?
11. How do you make important decisions?
12. What motivates you to do the best on job?
13. Do you prefer working alone or in a team?
14. What do you know about our company?
15. Are you planning for further studies?
16. What is your salary expectations?
10
Introduction
11
Chapter 1: Introduction to algorithm and their types.
When we think of algorithm, we think of a computer program that solves a problem. But, in
day to day life we come across many things that might define an algorithm. It might be your
daily routine when you go to college, or how you plan your weekends.
For example:
Daily we follow below set of steps like:
1. Getting up
2. Getting ready
3. Go to school/office
4. Have lunch
5. Come back to home have dinner
6. Go to sleep
If you take an example of ride sharing service, how does the system deicide that a cab near
to you should be allocated, or how does google maps will calculate the time take for you to
reach your destination accurately?
The solutions for all the above problems can be solved by using algorithms.
12
1. Algorithms will help you to solve a computational problem efficiently by applying
different methods.
2. It will help you to make your program run faster.
3. It will help you to clear interviews.
4. It will help you to become good at competitive programming.
In the series of chapters, we shall be looking at different types of algorithms and data
structures, that will help you to understand and able to solve different types of problems.
1. Brute force approach: In this approach we go through all the solutions to a problem.
As a problem can have multiple solutions, by using this approach, we might get to
the correct result, but lose efficiency.
2. Recursive approach: In this approach, we call the same function again and again. It is
important to have a base condition or exit condition to come out of recursion loop,
else it will go to infinite loop.
Care to be taken while using recursion as it uses more stack space, it might result in
MLE error [Memory limit exceeded] for some problems while doing competitive
programming.
4. Backtracking Algorithm: This algorithm is similar to DP, but the main difference is we
store the result in a Boolean matrix, to store if the previous step is true or false. If
the previous step is true, then we go ahead for the next step. If the previous step is
false, we change the approach and go in different direction. We shall see problems
on backtracking at the end of the book.
5. Greedy Approach: In this approach, we take the best solution for the present step
without considering in future there might be more efficient result.
6. Divide and Conquer: In this approach, we divide the input into smaller problems and
then we try to solve those problems to arrive at final result.
13
14
Chapter 2: Performance analysis of an algorithm: Space Complexity
2.1 Before we go to space complexity, let us understand why we need to calculate the
performance of an algorithm?
Consider 2 programmers “A” and “B”. Both of them submits 2 different solutions for the
same program. Now how do we decide which solution is efficient and performs better?
And also A’s program might perform better for small number of input but will not perform
when the input size increases.
Similarly, B’s program will not perform when the input size is small but will perform better
for large number of inputs.
Hence to determine which of the solution is better, we take a look at 2 important factors
that decide the performance of an algorithm:
1. Time complexity
2. Space Complexity
Space complexity is about calculating the amount of space consumed by algorithm during
the course of its execution.
15
In this method, the size of space consumed will not be increased with the increase of input
size.
For example:
Find the square of a number:
Pseudo code:
int getSquare (int n)
{
return (n * n)
}
Here we can solve the problem without consuming any extra space, hence the space
complexity is constant even if the input size increases.
Here the space consumed will be increased with the increase of input size.
For example:
But the variable arr[] is an array, it’s space consumption increases with the increase of input
size. i.e n.
16
As we can see in further chapters, we are interested in the performance of the algorithm,
for a greater value of “n”. Hence, we can ignore the constants, and come to a conclusion
that the total space complexity of the above algorithm is O(n).
Pseudo code:
int add_matrix( int a[m] [n], int b [m] [n], int m, int n)
{
for (i = 0; i< n; i++)
{
for(j = 0; j<n; j++)
{
c[i][j] = a[i][j] + b[i][j]
}
}
}
From the above code, we can see that:
But we have 3 matrix variables of size arr[m][n] space consumption increases with the
increase of input size. For one matrix will consume “n^2” space, for 3 it will consume
“3*n^2” space.
17
Chapter 3: Performance analysis of an algorithm: Time Complexity
3.1 Example 1
3.2 Example 2
3.3 Below are different types of time function available.
3.4 Increasing order of time consumption
In the last chapter we learnt on how to calculate space complexity. In this chapter we shall
learn on how to calculate time complexity.
3.1 Example 1:
Let us take the same previous example to calculate the sum of “n” numbers in the array and
how much time will it take to get the result.
Pseudo code:
int calculate_sum(int arr[], int length)
{
int total_sum = 0;
int i = 0;
The statement “int total_sum = 0;” will be executed 1 time. Hence 1 unit.
The statement “int i = 0;” will be executed 1 time. Hence 1 unit.
The statement “for( i= 0; i< len; i++)” will be executed “len+1” times. This is because, it will
also calculate till, after the condition is false.
Hence the total time taken to execute is = “2n+3”. For larger value of n, we ignore the
constants, hence the final time complexity is “O(n)” times.
3.2 Example 2:
18
Pseudo code:
int add_matrix( int a[m] [n], int b [m] [n], int m, int n)
{
for (i = 0; i< n; i++)
{
for(j = 0; j<n; j++)
{
c[i][j] = a[i][j] + b[i][j]
}
}
}
From the above code, we can see that:
The first for loop “for (i = 0; i< n; i++)” will be executed (n+1) time. Hence n+1 units.
The second for loop “for(j = 0; j<n; j++)will be executed n*(n+1) time. Hence n(n+1) units.
The third statement “c[i][j] = a[i][j] + b[i][j]” will be executed “n * n” times. Hence n^2 units.
i.e
2n^2 + 2n + 1
For larger value of “n” we ignore the constants, hence total time taken to execute is O(n^2).
Usually when we are trying to calculate the time complexity, we try to relate to the time
functions we know.
O(1)
O(n log n)
O(n)
O(n^2)
O(n^3)
O(2^n)
O(3^n)
O(n^n)
O(1) < O(n log n) < O(n) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n^n)
19
Chapter 4: Asymptotic Notations
AN are mathematical functions that are used to calculate running time and also the rate of
growth of an algorithm.
In the previous chapters we saw on how to analyze space and time complexity. With the
help of previous learnings, we shall see how to calculate asymptotic notations.
Running time refers to the time taken for the computer to run all the statements in an
algorithm.
Rate of growth refers to how the algorithm will behave when a large amount of input is
given.
From the above table we can see the order of growth for a logarithmic algorithm is lesser
than that of an exponential one. Hence if we have 2 algorithmic solutions, then we should
go for the one that consumes less time.
N^2: The running time is quadratic. They usually will be having 2 loops. Algorithms
like: Bubble sort, selection sort.
20
4.3 When we run a program, below are the list of points that will affect the running time:
1. Speed of computer
2. Compiler Used
3. Programming Language
4. Algorithm of choice
5. Types of input and output
6. Size of input and output
As we don’t have control over first 3 points, we ignore them. We concentrate on next 3
points.
1. When we have a time complexity of “O (n^2 + 3)”, we ignore the constant “3”, and
find the total time complexity as “O(n^2)”. This is because, we always want to know
how the algorithm will perform for a larger value of “n”. For example, if the value of
“n” is “10000”, then the constant “3” will be negligible. Hence we ignore it.
2. When we have a time complexity of “O(3n^2)”, we ignore the constant “3” and final
time complexity will be “O(n^2)”. This is because, different computer architecture
will be having different ways to handle the constant “3”. A faster computer will be
able to store the constant in the register and is able to access it faster. A slower
computer will hold it in memory hence is slower. As we are interested no the
algorithm performs not on how the hardware performs, we ignore that constant.
Big O: We use this notation to calculate the worst case and is called as tight upper
bound.
Let us understand Best, average and worst case with the help of an example:
Consider that we are searching for a key in list of 10 items. We search one by one, a
linear search.
Here Best-case will be, the key present at the first item itself.
21
Average case is, the key present somewhere in the middle of the 10 items. Worst case is
the key present at the last item.
22
Chapter 5: Asymptotic Notation Big O
To say a function f(n) is equal to O(g(n)), if there is a constant “C” and “n0” such that the
function f(n) will always be less that “c * g(n)”, can be written as “f(n) < c*g(n)”.
It means that the function f(n) will not go above the function g(n) for a large value of n.
Hence we can consider the function “g(n)” as upper bound for the function f(n).
We try to do this because, we know the rate of growth of the function “g(n)” [remember in
chapter 3] and hence we try to reduce the function “f(n)” to a known value of rate of
growth.
5.3 Example 1:
f(n) = 6n + 7
g(n) = n
So the function 6n + 7 will be equal to g(n), if we can find constants C and n0 such that 6n +
7 <= C*n for all n>= n0.
By analysis we get
When n =5 and C = 8, we can satisfy the condition
6n + 7 <= C * n For all n>= n0
23
6*5 + 7 <= 8 *5
37 <= 45 for all n >= 5
5.4 Example 2:
f(n) = 3n^2 + 4n + 7
g(n) = n^2
So like I said in previous topics, we try to reduce the function f(n) to known values of g(n), so
that it will easy for us to calculate the running time of the algorithm.
2. f(n) = 6n^3 + 2n^2+ 3 is of order O(n^3). Because for larger value of n, (2n^2 + 3)
will be negligible.
24
Chapter 6: Asymptotic Notation Big Omega and Theta
In the previous chapter we learnt about Big O notation, that defines tight upper bound. In
this chapter we shall see about Big Omega and Big Theta notation.
This notation is used to represent tight lower bound. Big omega can be defined as:
For a function f(n) is equal to Ω(g(n)) if there exist a constant C and n0 such that f(n) is
always greater than C(g(n)). i.e. f(n) > C(g(n)) or C(g(n)) < f(n).
Big theta is used to get the average case for a function. It can be defined as:
For a function f(n) is equal to Ø(n) if a function f(n) is greater than C1 g(n) and is less than
C2g(n) for all n>= 0. i.e. 0<= C1 g(n) <= f(n) <= C2 g(n).
25
26
Sorting Algorithms:
27
Sorting algorithm 1: Bubble sort
1.1 Introduction:
Bubble sort is a sorting algorithm. It will sort by checking if the present element is greater
the next element, if greater then it will swap the elements.
1. In bubble sort we use 2 for loops. Outer loop and one inner loop.
2. For every element from the outer loop, we iterate through the inner element every
time, and we compare the element from outer element to the element from the
inner array element. If it is greater than we swap the elements.
3. At the end of the first iteration, the largest element will be at the end, similarly at
the end of 2nd iteration 2nd highest element will be in n-1 position.
4. As we see that after every iteration highest element will be on the top, hence we call
it as bubble sort.
[ 3, 4, 1, 2, 8, 5 ]
first pass:
[ 3, 4, 1, 2, 8, 5 ] -> [ 3, 1, 4, 2, 8, 5 ]
28
again we will check if 8 > 5, true, swap
[ 3, 1, 2, 4, 8, 5 ] -> [ 3, 1, 2, 4, 5, 8 ]
Hence after first pass, the largest element will be at the end. And we can ignore comparing
the last element as it is the largest.
Second pass:
Third pass:
In third pass the result will be the same as all the elements have been sorted.
In bubble sort, we use 2 loops. Outer loop is to loop n times and inner loop for swapping.
As you can see above, after 2nd pass all the elements are in the sorted order. Hence we can
break the loop if no swapping done by the inner loop after third pass, hence saving the time.
#include<stdio.h>
29
for(index = 0 ; index < length ; index++)
{
printf("%d\n",array[index] );
}
}
void swap (int *num_1, int *num_2)
{
int temp = *num_1;
*num_1 = *num_2;
*num_2 = temp;
}
int main()
{
int length = 0;
int array[100];
int index = 0;
bubble_sort(array, length);
30
print_array(array, length);
1.5 Output:
From the above code, we can see that it always compares between 2 elements.
In the first pass, it will do n-1 comparisons
In the second pass, it will do n-2 comparisons
31
Sorting algorithm 2: Selection Sort
2.1 Introduction:
Selection sort is a sorting technique where the smallest element is taken from the array and
placed at the first, same steps are continued for rest of the elements.
Selection sort can also be thought as card playing game. We move the cards by choosing
smallest card at a time. At any point, we will be having 2 division, where the right hand will
have sorted list, left hand will be having un-sorted list.
1. Outer for loop: It is used to iterate all the array elements one by one.
2. Inner for loop: Here the element from the outer for loop is checked against all the
elements from inner for loop. If a smaller element is found, then that element will be
replaced with the index of outer for loop.
end for of i.
32
2.4 Understanding Selection Sort with an example
Pass 1:
Initially, we need to fill the index 0, with the smallest element. We first check the array. We
see that 1 is the least element and it is in index 2. Hence swap at index 0 and index 2. Below
is the result.
Pass 2:
As we have already placed lowest element in index 0, now we need to place 2nd lowest
element.
From the array we can see that 4 is the 2nd lowest element. Hence swap the elements at
index 1 and index 2, as shown below:
Pass 3:
At pass 3, we can see that element 6 is in it’s correct position. Hence we don’t do anything
in this pass.
33
Pass 4:
Pass 5 :
As you can see that the array is already sorted. Hence we do nothing.
34
#include<stdio.h>
int main()
{
int length = 0;
int array[100];
35
int index = 0;
selection_sort(array, length);
print_array(array, length);
(n-1) + (n-2) + . . . . + 2 + 1
(n(n-1))/2
O(n^2)
36
Sorting algorithm 3: Insertion Sort
3.1 Introduction:
In this tutorial we shall go through the concept of insertion sort and how to implement in C
language.
Here in the first pass, the smallest element will be in the first position. Second pass, second
smallest element will be in the 2nd position and so on.
37
3.4 Implementation of Insertion Sort in C
#include<stdio.h>
38
for(inner_loop_index = outer_loop_index - 1 ; inner_loop_index >= 0 ;
inner_loop_index --)
{
if(array [inner_loop_index + 1] < array[inner_loop_index])
{
swap(&array[inner_loop_index + 1], &array
[inner_loop_index]);
}
}
}
}
int main()
{
int length = 0;
int array[100];
int index = 0;
insertion_sort(array, length);
print_array(array, length);
39
2
3
4
5
40
Sorting algorithm 4: Merge Sort
4.1 Introduction
Divide: Divide the array into half. If the array has n elements, in the first level divide it by
n/2. Then take those 2 array again divide it by 2. Go on till you get only single elements.
Conquer: Sort the left part of the array and right part of the array recursively.
Combine: Combine the left part of the array and the right part of the array into single sorted
array.
Below is the image for merge sort performed for the array [40, 10, 5, 20, 15, 34, 7, 9]
Divide:
As we have 8 elements, the middle index will be 4. Hence we divide the array into 2 parts. If
you observe the code, once we divide the array, we recursively call the left part of the sub
array till it becomes sorted and then call the right part of the sub array.
Keeping that in mind we shall trace how the algorithm will work.
Then again, we have 4 elements, middle element is 2, again divide the left part of the array
as shown below:
41
Again we have 2 elements divide it as shown below:
As we have completed the left part, we go 1 level up and divide the right part as below:
Now the left and right part has been divided, we combine them into a sorted array as shown
below:
42
Now we split the right part of the sub array as shown:
43
Then we merge them as below:
44
Similarly we do the same for right sub array. While performing for the right sub array, we
again choose the left part of the right sub array and do the similar operation. The full
recursion tree will look like below:
Below I have mentioned the steps on how the dividing and conquer will occur.
45
Steps to perform merge sort:
To perform merge sort, we need 3 elements:
We need lowest and highest index to calculate the mid part of the index and divide the
array into two parts which later can be merged.
#include<stdio.h>
46
void print_array(int array[], int length)
{
int index = 0;
void merge_sorted_array( int array[], int low, int mid_index, int high)
{
int temp_array [100];
int i = low;
int j = mid_index + 1 ;
int k = low;
k++;
i++;
}
47
//copy the right part of the array to temp_array
k++;
j++;
}
int main()
{
int length = 0;
int array[100];
int index = 0;
48
}
merge_sort(array, 0, length - 1 );
print_array(array, length);
Total time taken for merge sort = Time taken to sort left half + Time taken to sort left half
+Time taken to merge left and right half.
Now we need to calculate the time taken for T(n/2). Replace n with n/2 in equation 1.
49
Now we need to find the value for T(n/4). Hence replace n with n/4 in equation 1, we get
T(n/4) = 2 T(n/8) + n/4.
Now again we need to calculate the value of T(n/8), by replacing in equation 1, and
replacing in equation 4 we get:
=2^4 * T (n/2^4) + 4n
50
Sorting algorithm 5: Quick Sort
5.1 Introduction
Quick Sort is a divide and conquer technique. Usually we use Quick Sort on a very large data
set.
Below is a brief on how this algorithm works:
To perform Quick sort, we need the help of “pivot element”. Pivot element holds an
important role in this algorithm.
51
Below are the points to be remembered while doing quick sort:
We take 2 variables, one pointing to the left end of the array and another pointing to the
right end of the array.
Then while comparing with the left pointer, we check if the element is less than the pivot
element. If it is less, we do nothing. If the element is greater than the pivot element we
swap the elements.
Similarly, while comparing with the right pointer, we check if the element is greater than the
pivot element. If the element is less than the pivot element, we swap the elements.
By doing the above 2 operations, we make sure that all the elements to the left of pivot
element are less and elements to right of pivot are greater. [Revisit these points once you
go through the example below].
Initially the left pointer will be pointing to left part of the array.
Pivot element also will be pointing to the left part of the array, as shown below:
We know that, all the elements to the right of the pivot element should be greater than the
pivot element and all the elements left of the pivot will be lesser than the pivot element.
52
Initially, the pivot is at the left, hence we start comparing from the right and move towards
left. To move an element towards left, that element should be less than the pivot element.
Hence we check below condition.
Now that the pivot element is at the right, we start comparing from left and move towards
right. For an element to be at right of pivot element, it should be greater than the pivot
element. hence we check below condition:
Hence we move the left pointer to the next element as shown below:
53
after comparing:
again check if arr[pilot] > arr[left], if(5 > 2) true. Hence increment left pointer to next index
as shown below:
Now agin, check if arr[pilot] > arr[left], if(5 > 6) false. Hence swap element 5 and 6.
54
Now check if arr[pilot] < arr[right], if(5 < 6) true. Decrement right pointer as shown below:
Now again check if arr[pilot] < arr[right], if(5 < 3) false. Hence swap pivot element and right
element as shown below:
As the pivot element moved from left to right, we start comparing from left and pivot
element.
check if arr[pilot] > arr[left], if(5 > 3) true. Increment left pointer
55
again check if arr[pilot] > arr[left], if(5 > 1) true. Increment left pointer.
Now that left and right pointer are pointing at the same element of the array, the element 5
is at the pivot element and is in the sorted position.
All the elements left of 5 are smaller and elements to right are larger than 5 as shown
below:
Again we shave to sort the left part and right part. Again the initial array will be like below:
56
as the pivot is at left, we compare with right pointer and move towards left.
Hence check if arr[pilot] < arr[right], if(4 < 1) False. Hence swap pivot and right element.
Now check if arr[pilot] > arr[left], if(4 > 1) true. Increment left pointer.
again check if arr[pilot] > arr[left], if(4 > 2) true. Increment left pointer by 1.
57
again check if arr[pilot] > arr[left], if(4 > 3) true. Increment left pointer by 1.
As both left and right pointer points to the same index, it means that element 4 is at it’s
correct position.
Hence again do the same quick sort for the left sub array “1, ,2 , 3”.
58
5.4 Implementation of Quick Sort in C
#include<stdio.h>
while(i < j)
{
while(array[i] <= array[pivot] && i < lower_index)
i++;
swap(&array[pivot], &array[j]);
return j;
59
void quick_sort (int array[], int lower_index, int upper_index)
{
int partition_index = 0;
if(lower_index < upper_index)
{
partition_index = partition(array, lower_index, upper_index);
quick_sort(array, lower_index, partition_index - 1);
quick_sort(array, partition_index + 1, upper_index);
}
}
int main()
{
int length = 0;
int array[100];
int index = 0;
quick_sort(array, 0, length-1);
print_array(array, length);
60
1
2
3
4
5
61
Sorting algorithm 6: Pigeonhole Sort
6.1 Introduction
Pigeonhole sort is an interesting algorithm that works on integer numbers not floating
value.
It works best when all the keys [elements in array] are unique.
Steps:
Suppose we have the array [8, 5, 4, 3, 2, 1]
Hence:
Max = 8
Min = 1
Range = [ 8 - 1] + 1 = 8 Holes.
pigeonholeArray [0, 0, 0, 0, 0, 0, 0, 0]
62
Pass 1:
i=0
index = a[0] - Min_value + 1
=8-1+1
=8
Hence place the element of a[0] in pigeonholeArray index 8
pigeonholeArray [0, 0, 0, 0, 0, 0, 0, 8]
Pass 2:
i=1
index = a[1] - Min_value + 1
=5-1+1
=5
Hence place the element of a[1] in pigeonholeArray index 5
pigeonholeArray [0, 0, 0, 0, 5, 0, 0, 8]
Pass 3:
i=2
pigeonholeArray [0, 0, 0, 4, 5, 0, 0, 8]
Pass 4:
i=3
pigeonholeArray [0, 0, 3, 4, 5, 0, 0, 8]
Pass 5:
i=4
pigeonholeArray [0, 2, 3, 4, 5, 0, 0, 8]
Pass 6:
i=5
pigeonholeArray [1, 2, 3, 4, 5, 0, 0, 8]
at the end copy the elements from the “pigeonhole Array” to original array, whose value is
greater than 0. Final resulting array will be a sorted one.
Final array[1, 2, 3, 4, 5, 8]
63
6.4 Implementation of Pigeonhole Sort in C
#include<stdio.h>
#define MAX_ELEMENTS 100
int max_element = 0;
int min_element = 0;
int itr;
int range = 0;
64
while (pigeonHoleArray[itr] > 0)
{
pigeonHoleArray[itr]--;
*temp_array++ = itr + min_element;
}
}
printf("%d", arr[itr] );
}
printf("\n");
int itr = 0;
pigeonHoleSort(arr, length);
printArray(arr, length);
return 0;
}
65
6.5 Output of the program
Output 2:
Enter number of elements of the array
7
Enter the elements
8
6
5
4
3
2
1
The sorted array is
1234568
66
Sorting algorithm 7: 3-Way Quicksort (Dutch National Flag) algorithm
7.1 Introduction
This is a very simple algorithm that works if there are only 3 different types of keys in an
array.
For example:
If we have an un-sorted array of 0, 1, 2 as shown {2, 0, 0, 1, 1, 2, 0, 2, 1}, easy
solution is to count the number of 0’s, 1’s and 2’s then put those many elements inside the
array, but this solution is not efficient.
To solve the array in least time complexity then we use “Dutch National Flag” algorithm.
In this algorithm, we consider one element will be in the middle. And the elements lesser
than the middle element will be moved towards left and the elements greater than the
middle element will be moved towards the right side.
Note: The middle element in some context is called as a pivot element. i.e in [0, 1, 2], 1 is
the pivot element.
Step 1:
Set low_index = 0, high_index = n – 1, mid_index = 0;
The mid variable is going to trace all the elements in the array.
Step 2:
We get a[mid] element and perform below steps
67
Case 2: If a[mid] == 2, Then move to the right, by swapping a[ mid_index ] and
a[high_index]. Then decrement high_index.
Note: In Case 2 we are not changing the value of mid_index. That is because the element
that got swapped with high_index might be 0. If it is 0, then we have to perform the
operation of taking 0 to the left side of the pivot element.
as arr[mid] = arr[0] = 2, you need to swap are[mid] with are[high] and decrease high index
by 1. It is as shown in image below:
Now arr[mid] = are[0] = 0. You need to increment both mid index and low index by 1 as
shown below:
68
Now arr[mid] = arr[1] =2. Swap arr[mid] with arr[high] and decrement high index as shown
below:
#include<stdio.h>
69
*num_1 = *num_2;
*num_2 = temp;
}
case 0:
swap(&arr[low_index], &arr[mid_index]);
low_index++; mid_index++;
break;
case 1:
mid_index++;
break;
case 2:
swap(&arr[mid_index], &arr[high_index]);
high_index--;
break;
}
int itr = 0;
70
}
printf("\n");
}
DutchNationalFlagSort(arr, length);
print_array(arr, length);
return 0;
}
71
Sorting algorithm 8: Cocktail Sort
8.1 Introduction
Cocktail sort can be considered as an extension to Bubble Sort Algorithm. As we know that
in a bubble sort algorithm the larger number will move towards the right of the list. Then
will again move towards the left of the list and again get the second largest element then
move towards the right.
This bubble sort algorithm can be further optimized with the help of Cocktail Sort. Here
instead of moving in one direction from left to right we move in the opposite direction right
to left. Hence, once we move the largest element towards the right, while returning back to
the initial position, we take the smallest element to the left.
Cocktail sort will be faster than bubble sort, but it will not change the complexity. The
complexity will be still O(n^2).
Pass 1:
Left to right:
{2, 6, 7, 4, 1, 8, 5, 3} 2 > 6? False
{2, 6, 4, 7, 1, 8, 5, 3} 6 > 4? True, swap
{2, 4, 6, 1, 7, 8, 5, 3} 6 > 1? True, swap
{2, 4, 1, 6, 7, 8, 5, 3} 6 > 7? False
{2, 4, 1, 6, 7, 5, 8, 3} 7 > 5? True, swap
{2, 4, 1, 6, 5, 7, 8, 3} 7 > 8? False
{2, 4, 1, 6, 5, 7, 8, 3} 8 > 3? True, swap
{2, 4, 1, 6, 5, 7, 3, 8}
72
{2, 4, 1, 3, 6, 5, 7, 8} 3 < 1? False
{2, 1, 4, 3, 6, 5, 7, 8} 1 < 2? True, swap
{1, 2, 4, 3, 6, 5, 7, 8}
Hence in the first pass, lowest element is at the left and highest element is at the right.
Pass 2:
Left to Right
{1, 2, 4, 3, 6, 5, 7, 8} 1 > 2? False
{1, 2, 4, 3, 6, 5, 7, 8} 2 > 4? False
{1, 2, 4, 3, 6, 5, 7, 8} 4 > 3? True, swap
{1, 2, 3, 4, 6, 5, 7, 8} 4 > 6? False
{1, 2, 3, 4, 6, 5, 7, 8} 6 > 5? True, swap
{1, 2, 3, 4, 5, 6, 7, 8} 6 > 7? False
Right to Left
{1, 2, 3, 4, 5, 6, 7, 8} 6 < 5? False
{1, 2, 3, 4, 5, 6, 7, 8} 5 < 4? False
{1, 2, 3, 4, 5, 6, 7, 8} 4 < 3? False
{1, 2, 3, 4, 5, 6, 7, 8} 3 < 2? False
{1, 2, 3, 4, 5, 6, 7, 8} 2 < 1? False
Our algorithm uses “is_swapped” variable to know if the array is sorted or not. A sorted
array need not do any swapping. Hence taking that as a basis we terminate the main loop.
// www.prodevelopertutorial.com
#include<stdio.h>
#include <stdbool.h> // for bool datatype in c
73
void CocktailSort(int arr[], int length)
{
int min_index = 0;
int max_index = length - 1;
bool is_swapped = true; // initially we know the array is unsorted, hence set it to
true
int itr = 0;
while(is_swapped)
{
// we set it to false, because in the previous iteration it might be true
is_swapped = false;
// sorting from left to right. At the end heigher element will be at the
right
for(itr = min_index; itr < max_index; itr++)
{
if (arr[itr] > arr[itr + 1])
{
swap(&arr[itr], &arr[itr +1 ]);
is_swapped = true; // we have swapped, hence
changing the flag
}
}
if(!is_swapped)
{
break; // if we did not swap the elements, then it is known that
the array is sorted.
}
// sorting from right to left. At the end lowest element will be at the left
for(itr = max_index - 1 ; itr >= min_index; itr--)
{
if (arr[itr] > arr[itr + 1])
{
swap(&arr[itr], &arr[itr +1 ]);
is_swapped = true; // we have swapped, hence
changing the flag
}
}
74
// increment the min_index, as lowest element will be at the left of the
array.
min_index ++;
}
int itr = 0;
int main()
{
print_array(arr, length);
75
Enter the length of the array 4
4
3
2
1
Sorted array is
1234
76
Sorting algorithm 9: Radix Sort
9.1 Introduction
9.2 Steps for performing Radix Sort
9.3 Understanding Radix Sort with an example
9.4 Implementation of Radix Sort in C
9.5 Output of the program
9.1 Introduction
Radix sort algorithm is an interesting sorting algorithm. Because this sort is not based on
comparison, rather than it is based on buckets.
Radix Sort is a linear sort algorithm. The number of passes depends upon the number of
digits in the maximum number in the array.
Hence we shall take 10 buckets labelled from 0 to 9 to store the sorted numbers.
Step 2: Then we shall take the max number in the given list. Then we shall start the
algorithm by taking the right most digit and start placing them in the suitable numbered
bucket.
Step 3: Once we have placed all the elements in the particular buckets, we shall take them
out and place them in sorted order according to their Least significant digit and thus the first
pass is completed.
Step 4: Then we shall repeat the step 2 and 3 till all the passes are completed.
Here, 100 is the highest element, and has 3 digits. Algorithm takes maximum of 3 passes.
As the highest element has 3 digits, hence we make all the elements in the array to have 3
digits. Resulting array is as shown below:
Pass 1:
{010, 015, 001, 060, 005, 100, 025, 050}
First we take the digits from one's place and place it in the according bucket.
77
0: 010, 060, 100, 050
1: 001,
2:
3:
4:
5: 015, 005, 025
6:
7:
8:
9:
Sorted array:
{010, 060, 100, 050, 001, 015, 005, 025}
Pass 2:
We take the 10's place and place it in the according bucket:
{010, 060, 100, 050, 001, 015, 005, 025}
Pass 3:
Finally, we take the 100'th place of all the digits.
{100, 001, 005, 010, 015, 025, 050, 060}
78
9.4 Implementation of Radix Sort in C
#include<stdio.h>
79
//copy output form temp array to original array
for (itr = 0; itr < length; itr++)
{
arr[itr] = result_array[itr];
}
digit_place *= 10;
int length = 0;
int array[100];
int index = 0;
RadixSort(array, length);
print_array(array, length);
80
return 0;
}
81
Sorting algorithm 10: Bucket Sort
1. The general idea is to divide the data based on buckets based on some criteria.
2. Then sort the buckets individually.
3. Concatenate those buckets.
The elements will be sorted.
The Number of buckets created is dependent on the programmer. In the below algorithm
we divide into 3 buckets.
#include <stdio.h>
#include <stdlib.h>
struct bucket
{
int count;
int* values;
};
82
{
struct bucket buckets[3];
int i, j, k;
for (i = 0; i < 3; i++)
{
buckets[i].count = 0;
buckets[i].values = (int*)malloc(sizeof(int) * n);
}
// Divide the unsorted elements among 3 buckets
// < 0 : first
// 0 - 10 : second
// > 10 : third
for (i = 0; i < n; i++)
{
if (array[i] < 0)
{
buckets[0].values[buckets[0].count++] = array[i];
}
else if (array[i] > 10)
{
buckets[2].values[buckets[2].count++] = array[i];
}
else
{
buckets[1].values[buckets[1].count++] = array[i];
}
}
for (k = 0, i = 0; i < 3; i++)
{
// Use Quicksort to sort each bucket individually
qsort(buckets[i].values, buckets[i].count, sizeof(int), &compareIntegers);
for (j = 0; j < buckets[i].count; j++)
{
array[k + j] = buckets[i].values[j];
}
k += buckets[i].count;
free(buckets[i].values);
}
}
int main() {
bucketSort(array, n);
83
for (k = 0; k<n; k++)
printf("%d \n", array[k]);
return 0;
}
-10
-9
-5
0
1
2
3
4
5
7
1000
1234
84
Sorting Algorithm 11: Counting Sort
11.1 Introduction
11.2 Steps for performing Counting Sort
11.3 Understanding Counting Sort with an example
11.4 Implementation of Counting Sort in C
11.5 Output of the program
11.6 Time complexity analysis of Counting Sort
11.1 Introduction
Counting sort algorithm is a linear sort algorithm. This algorithm is not based on comparing
the elements but rather counting of the elements.
Usually we use this algorithm with other algorithm for example radix sort algorithm.
Step 1: Find the minimum and maximum value from the array.
Step 2: Create a second array from the minimum value to maximum value.
Step 3: Increment the second array whenever we find a number from the first array.
Step 4: Once all the numbers will be written, take the sum [see in the pic below].
Step 5: Place the elements in the respective positions. You will get the sorted array.
Consider the below array, we shall sort this array using counting sort algorithm.
From the image above, we know that 4 is the smallest element and 15 is the largest
element.
85
Now create one more array to hold the elements from index 4 to 15 and also counting array
to hold the count as shown below:
Now, count the number of times each element is repeated. Al the elements are repeated
only once. Hence write 1 in their respective index as shown below;
86
Now create a sum count array that will hold the sum of counts for the given index. Initially it
will be as below:
Now add the index and write down the sum count as shown below:
Now we shave filled out sum count array, let’s sort the input with the help of counting sort.
87
Now, check the element from input array and get the value from sumCount array and place
it at its index.
For example,
The value for 14 in sumCount array is 6. Hence place 14 in index 6 in output array.
88
Similarly, do for all the elements we get sorted output as below:
#include<stdio.h>
#include<string.h>
89
{
int i = 0;
int main()
{
90
int length = 0;
int array[100];
int index = 0;
counting_sort(array, length);
print_array(array, length);
91
Sorting Algorithm 12: Shell Sort
12.1 Introduction
12.2 Steps for performing Shell Sort
12.3 Implementation of Shell Sort in C
12.4 Output of the program
12.5 Time complexity of Shell Sort
12.1 Introduction
Shell sort is also called as Diminishing increment sort, Comb sort, Gap sort invented
by Donald L. Shell.
In this algorithm is based on comparison, but instead of comparing and swapping adjacent
elements, it compares the elements that are having certain gap present between them.
There are many ways that one can select the gap. Below are some of the ways of gap
sequence are:
The example for shell sort will be discussed in Comb Sort Algorithm.
#include <stdio.h>
while(gap > 0) {
92
//now we will do the insertion sort of the gapped elements
i = gap;
//increase i
i++;
}
int main(void) {
int length = 0;
int array[100];
int index = 0;
93
{
scanf("%d", &array[index]);
}
shellSort(array, length);
print_array(array, length);
return 0;
}
94
Sorting algorithm 13: Topological Sort
In this chapter we shall learn about below topics:
13.1 Introduction
13.2 Steps for performing Topological Sort
13.3 Implementation of Topological Sort in C++
13.4 Time complexity of Topological Sort
13.1 Introduction
Topological sort is used on Directed Acyclic Graph. Here the sorting is done such that for
every edge u and v, for vertex u to v, u comes before vertex v in the ordering.
If the graph has a cycler if the graph us undirected graph, then topological sort cannot be
applied.
a, b, c
because “a” appears first, then “b”, then “c” in that order. Er shall see how to solve this by
using khan’s algorithm.
95
Step 1:
Find out the in degree of all the vertices. In degree means incoming nodes. Below image
shows in degree of all the vertices.
Step 2:
For the vertex with in degree 0, we start topological sorting from that node. We shave “1”
node as in degree as 0. Now write “1” as output and delete that node and all the nodes that
are outgoing from that node.
96
Again node “2” has in degree as 0. Take the node “2” and write in output. And delete all the
outgoing vertex from node 2.
Again choose vertex with in degree 0, I.e node “4” and write in output and delete it’s
outgoing edges.
Now again calculate the in degree. From the above image, the in degree for both of the
nodes are 0. Writ in any order as below:
97
This our result.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> adj_list[100];
vector<int> topological_sort;
int in_degree[100];
int n; // number of vertices
int m; // number of edges
void perform_topsort()
{
queue<int>q;
for(int i=1;i<=n;i++)
{
//get the vertex with indegree 0 and push into the queue
if(in_degree[i]==0) q.push(i);
}
while(!q.empty())
{
topological_sort.push_back(current_node);
for(int i=0;i<adj_list[current_node].size();i++)
{
int v =adj_list[current_node][i];
98
in_degree[v]--;
if(in_degree[v]==0)
{
q.push(v);
}
}
int main()
{
cout<<"Enter the number of vertices[n], number of edges[m]"<<endl;
cin>> n>> m;
topological_sort.clear();
memset(in_degree, 0, sizeof(in_degree));
perform_topsort();
if(topological_sort.size()!=n)
{
cout<<"Graph is not a DAG";
return 0;
}
99
cout<<topological_sort[i]<<"\n";
}
100
Sorting algorithm 14: Comb Sort
In this chapter we shall learn about below topics:
As you know bubble sort will sort adjacent elements, comb sort will use the gap to sort the
element.
Hence we compare first and last element. If the last element is less than that of the first
element, we swap the elements.
Form the above image, we can see that 1 is smaller than 8. Hence swap:
101
Now reduce the gap by 1.3. So 10/1.3 = 7. This will be pass 2. In pass 2, we compare all the
elements which has gap of 7 and perform similar check as shown below.
The below image will show you the sequence of steps performed form pass 2:
102
for pass 4 again reduce the gap by 1.3. i.e 5/1.3 = 3
we need to perform similar operation at the end of pass 4. the array will be as below:
103
again reduce the gap by 1.3 i.e 3/1.3 = 2. At the end of pass 5, the result will be:
#include<iostream>
104
//check the elements that are "gap" distance
for(int i = 0; i< length - gap; i++)
{
if(array[i] > array[ i + gap ])
{
swap(array[i], array[ i + gap ]);
flag = true;
}
}
}
}
int main()
{
int arr[] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};
combSort(arr, 10);
return 0;
}
14.4 Output:
105
Searching Algorithm
106
Searching Algorithm 1: Linear search or Sequential Search
1.1 Introduction
1.2 Understanding Linear Search with an example
1.3 Implementation of Linear Search in C
1.4 Output of the program
1.5. Time complexity of Linear Search
1.1 Introduction:
Linear search is a search algorithm, that checks for the key in a set of values one by one till it
reaches the end of all the elements.
For example:
consider the array [14, 96, 27, 5, 48], and we need to search for the number 48. Below are
the number of iterations necessary:
if key == a[0]
else if key == a[1]
else if key == a[2]
else if key == a[3]
else if key == a[4]
If the key is found we shall display the index of the key, else we return key not found.
Pseudo Code:
Input:
array
array_len
key
Algorithm:
for i = 0 to n-1
if (arr[i] == key)
107
return i
end if
end for
#include<stdio.h>
int i = 0;
int main()
{
int arr[5] = {10, 30, 48, 45, 78};
int arrayLen = 5;
//successful search
linearSearch(arr,arrayLen, key);
108
return 0;
}
109
Searching Algorithm 2: Binary search
2.1 Introduction
2.2 Steps to perform Binary search
2.3 Understanding Binary Search with an example
2.4 Implementation of Binary Search in C
2.5 Time complexity of Binary Search
2.1 Introduction
Binary search is a simple search technique that works on sorted array, either it can be
ascending or descending.
1. Binary search can be similar to searching a word in a dictionary. We open the book in
the middle and check if the name is found.
2. If the word is not found, depending upon the results we get we tend to move
forward or backward.
3. If the word is found, then we take the meaning of that word.
Program Design:
110
Case 1: When the key == array[mid]. In this case we exit the loop
Case 2: When key > array[mid]. In this case we move towards right half of the array.
Case3: When key < array[mid]. In this case we move towards left half of the array.
Example:
First Pass:
[8/2] = 4
is arr[4] == 2 ? No, and 2 < 5. Hence discard right half and move towards left half.
Second Pass:
[3/2] = 2
is arr[2] == 2 ? No, and 2 < 3. Hence discard right half and move towards left half.
Third Pass:
[1/2] = 1
is arr[1] == 2 ? Yes, hence our result.
#include<stdio.h>
int i = 0;
int min_index = 0;
int max_index = len-1;
111
return;
}
int main()
{
int arr[5] = {10, 30, 45, 48, 78};
int arrayLen = 5;
//successful search
binary_Search(arr,arrayLen, key);
return 0;
}
112
Hence n/ 2^k = 1
K = log n.
113
Searching Algorithm 3: Jump search
3.1 Introduction
3.2 Steps to perform Jump search
3.3 Understanding Jump Search with an example
3.4 Implementation of Jump Search in C++
3.5 Time complexity of Jump Search
3.1 Introduction
Jump search is an improvement over linear search. In linear search, we check the element
one by one till we find the key element, or till we reach the end of the array.
In jump search we jump block by block and check if the key element is inside the block. If
the key element is inside the block, we do a linear search in that block.
Key = 80
N = 13
Jump = SQRT(13) = 3
114
3.4. Implementation of Jump Search in C++
#include <cmath>
#include <vector>
115
// now do a linear search in the block
for(int i = start; i<end; i++)
{
if(arr[i] == key)
cout<<" The key is present in the array"<<endl;
return;
}
cout<<" The key is NOT in the array"<<endl;
}
int main()
{
int arr[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int key = 13;
int len = 15;
return 0;
}
116
Searching Algorithm 4: Interpolation Search
4.1 Introduction
4.2 Steps to perform Jump search
4.3 Understanding Jump Search with an example
4.4 Implementation of Jump Search in C++
4.5 Output of the program
4.6 Time complexity of Jump Search
4.1 Introduction
Interpolation search is an improvement to binary search. This will help to achieve better
time complexity.
As we have seen in the binary search chapter, we always take the middle index and based
on it, we shift towards left or right. But what if we have an option or a formula to
approximate the position of the key element?
Pass 0:
Initally all the elements will have below values:
low = 0
high = 7
arr[low] = 1
arr[high] = 8
With the help of above values we try to find an optimal position by using the above formula,
we get the position as 6.
117
AS arr[pos] = 7, which is the search key, we get the output.
#include<iostream>
#include <vector>
if (arr[pos] == key)
{
cout<<"The element is present"<<endl;
return ;
}
if (key > arr[pos])
low = pos + 1;
else
high = pos-1;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int len = 8;
int key = 7;
return 0;
}
118
4.5 Output of the program
119
Searching Algorithm 5: Exponential Search
5.1 Introduction
5.2 Steps to perform Exponential search
5.3 Understanding Exponential Search with an example
5.4 Implementation of Exponential Search in C++
5.5 Output of the program
5.6 Time complexity of Exponential Search
5.1 Introduction:
Exponential search is an improvement to binary search. We use this algorithm when we
have large amount of data.
In exponential search algorithm we use binary search. But the difference is, we get the
range of elements to search from and give that as input to binary search.
Initially we start with “1”. Then for each pass, we increase the gap 2 times every time.
Once we get our range, we give that range as input to binary search.
int bound = 1;
while (bound < size && arr[bound] < key)
{
//for every pass, increase the gap 2 times.
bound *= 2;
}
120
Initially the bound value will be 1 for pass 1
Then the bound value will be 2 for pass 2
Then the bound value will be 4 for pass 3
Now we know the exact range of elements where our key element is present.
Now we perform binary search on that range and return if we found the element or not.
#include<iostream>
#include <vector>
if (arr[mid] == key)
{
cout<<"Element found"<<endl;
return;
}
121
int bound = 1;
while (bound < size && arr[bound] <= key)
{
cout<<"Bound = "<<bound<<endl;
bound = bound*2;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int len = 8;
int key = 7;
return 0;
}
Element found
122
Searching Algorithm 6: Ternary Search
6.1 Introduction
6.2 Steps to perform Ternary search
6.3 Understanding Ternary Search with an example
6.4 Implementation of Ternary Search in C++
6.5 Output of the program
6.6 Time complexity of Ternary Search
6.1 Introduction:
Ternary Search is an divide and conquer algorithm.
Like in binary search, we always divide the array into 2 parts, in Ternary Search as the name
suggests we divide the array into 3 parts.
To make the array into 3 parts, we need to get 2 mid elements. For that we use below
formula:
Then we use below calculation to check if the key element is present or not.
1 if x == mid1, then the key element has been found at the index of mid1
2 if x == mid2, then the key element has been found at the index of mid2
3 if x < mid1, then the key element is in the first part of the array.
4 if x > mid2, then the key element is in the third part of the array.
5 else the element is in the second part of the array.
By doing so, we neglect 2/3rd part of the array and search the remaining 1/3 of the array for
each iteration.
123
[2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 25]
There are total of 12 elements, you need to find if the element 16 is present in the array or
not.
So
mid_1 = 0 + [12 - 0 ]/ 3 = 4
mid_2 = 12 - [12 - 0 ]/ 3 = 12 - 4 = 8
So 3 parts of array will be:
{2, 3, 4, 5}
{6, 7, 8, 10}
{12, 14, 16, 25}
Now, element 16 is greater than arr[mid_2]. Hence we know that the element is in 3rd part
of the array.
Now we need to concentrate on below array:
{12, 14, 16, 25}
#include<iostream>
int mid1 = 0;
int mid2 = 0;
124
mid2 = high - (high - low)/3;
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int len = 8;
int key = 7;
Element found
125
Time complexity is O(log3 n).
126
Basic Data Structures:
Data structure tutorial 1: Stack Data structure and Implementation using arrays.
Data structure tutorial 2: Stack Data structure and Implementation using Linked List.
Data structure tutorial 7: Queue Data Structure with implementation using arrays.
Data structure tutorial 8: Queue Data Structure with implementation using linked list.
Data structure tutorial 9: Circular Queues Data structure with Implementation using arrays.
Data structure tutorial 10: Circular Queue Data structure with Implementation using Linked
List.
127
Data structure tutorial 1: Introduction to Stack Data structure and Implementation using
arrays
Stack is a special type of data structure where in the elements are entered from one end
and are deleted from same end.
Stack is also called as Last In First Out data structure [LIFO]. Because the elements that are
entered Last will be removed at First.
1. push ():
128
We use push operation to insert an element into the stack. Here before pushing an element
into the stack, we should make sure that the stack is having enough space for that
operation.
That can be done by checking the present stack size and maximum stack size. If the present
stack size is less than maximum stack size, then we will insert the element and increment
the present stack size by one.
2. pop ():
We use pop to remove/delete an element from the stack. Before removing an element, we
need to check if the stack has some elements.
Removing elements from a stack having no elements will result in Stack Underflow.
129
3. display ()
Display method is used to display all the elements from the stack. If there are no elements,
then appropriate error message should be displayed.
1. Using arrays
2. Using Linked List
In this tutorial we shall see how to implement stack using arrays. In the next tutorial we
shall see how to implement stacks using linked list.
#include<stdio.h>
#include<stdlib.h>
#define STACK_SIZE 5
130
printf("Stack is full. Cannot insert more elements \n");
return;
}
top_index = top_index + 1;
stack_items[top_index] = item;
}
int main()
{
int deleted_item = 0;
131
int choice = 0;
top_index = -1;
for( ; ; )
{
printf("1. Push \n2. Pop \n3. Display \n4. Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter the item to be inserted\n");
scanf("%d", &item);
push();
break;
case 2:
deleted_item = pop();
if(deleted_item == -1)
{
printf("Stack is empty\n");
}
else
{
printf("Deleted Item =
%d\n",deleted_item );
}
break;
case 3:
display();
break;
default:
exit(0);
}
}
return 0;
}
132
1. Push
2. Pop
3. Display
4. Exit
3
Stack is empty
1. Push
2. Pop
3. Display
4. Exit
1
1. Push
2. Pop
3. Display
4. Exit
1
1. Push
2. Pop
3. Display
4. Exit
2
Deleted Item = 3
1. Push
2. Pop
3. Display
4. Exit
133
3
The contents of the stack are:
2
1. Push
2. Pop
3. Display
4. Exit
4
134
Data structure tutorial 2: Stack Implementation using Linked List
In this chapter we shall learn about below topics:
In the previous chapter we have seen introduction to stack and its implementation using
Arrays.
In this chapter we shall see how to implement stack using Linked List.
As till now we have not used LL, below are some Linked List [LL] Basics: In the next chapters
we shall learn more about Linked List.
A simple linked list will have a variable to hold the data and there should be a “self-
referential pointer”. A pointer that refers to the same structure is called as a “self-
referential pointer”.
struct node
{
int data;
struct node *next;
};
2.2 Let Us first see, how to insert elements into the stack using linked list.
As we know that we have to insert element at the start of the linked list. And the head
pointer should always point to the first element.
We do this in 4 steps:
135
Step 2: Update the data field of temp node with the value.
Step 3: Copy the address of first node to the “next” pointer of temp node.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
136
if(top == MaxSize)
{
return 1;
}
else
{
return 0;
}
}
void pop()
{
if(isempty())
{
printf("The stack is Empty!");
}
else
{
top--;
struct node* temp;
temp = head;
head = temp->next;
//freeing the memory consumed is important
free(temp);
}
}
if(IsFull())
{
137
printf("Stack is Full!\n");
}
else
{
top++;
}
}
void display()
{
int main()
{
int choice;
while(choice != 4)
{
printf("\t===================\n");
printf("\t\tSTACK\n");
printf("\t===================\n");
printf("Choose One\n\n");
printf("1)PUSH\n");
138
printf("2)POP\n");
printf("3)Display\n");
printf("4)Logout\n\n");
int option;
int a;
scanf("%d",&option);
switch(option)
{
case 1:
printf("Enter Number:\n");
scanf("%d",&a);
push(a);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
choice = 4;
break;
default:
printf("Wrong Input\n\n");
}
}
}
===================
STACK
===================
Choose One
1)PUSH
2)POP
3)Display
4)Logout
2
The stack is Empty!
===================
139
STACK
===================
Choose One
1)PUSH
2)POP
3)Display
4)Logout
3
===================
STACK
===================
Choose One
1)PUSH
2)POP
3)Display
4)Logout
1
Enter Number:
2
===================
STACK
===================
Choose One
1)PUSH
2)POP
3)Display
4)Logout
3
2
===================
STACK
===================
Choose One
1)PUSH
2)POP
3)Display
4)Logout
140
Data structure tutorial 3: Singly Linked List
In this chapter we shall learn about below topics:
Singly Linked list is a special data structure, which is a collection of zero or more nodes. The
node is a combination of data + link.
A Singly Linked List is a collection of zero or more nodes where each node has 2 or more
elements. One contains data and other contains the link to the next node.
141
From the above image we can infer following below points:
1. The list has 5 elements.
2. In the data section it holds the value 10, 20, 30, 40, 50.
3. In the link field, it holds the address of the next node.
4. The variable “head” holds the address of the first node.
5. The “link field” of the last element has “NULL”, to suggest that it is the end of the list.
142
2. Delete element from front end:
Deleting the element from the front end is simple.
143
3. Display all the data:
To display all the node data, take a temp node, and iterate through all the elements present
in the list. We take temp node because we don’t want to miss the head pointer.
Below is the code for SLL where the element is inserted at front end and deleted from front
end.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
144
// Insert the element at first
node insert_front (int value, node first_node)
{
//take a temp node and allocate memory
node temp_node = (node) malloc(sizeof(node));
//since we are inserting the value at first, the temp_node should point to the
first_node now.
temp_node->next = first_node;
//free first_node
free(first_node);
//return temp_node
return temp_node;
145
node temp_node;
if(first_node == NULL)
{
printf("The list is empty\n");
return;
}
int main()
{
node first_node = NULL;
int choice = 0;
int value = 0;
for( ; ; )
{
printf("1. Insert front \n2. Delete Front \n3. Display \n4. Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the value to be inserted\n");
scanf("%d", &value);
first_node = insert_front(value, first_node);
break;
case 2:
first_node = delete_front(first_node);
146
break;
case 3:
display(first_node);
break;
case 4:
exit(0);
}
}
1. Insert front
2. Delete Front
3. Display
4. Exit
1
Enter the value to be inserted
10
1. Insert front
2. Delete Front
3. Display
4. Exit
1
Enter the value to be inserted
20
1. Insert front
2. Delete Front
3. Display
4. Exit
1
Enter the value to be inserted
30
1. Insert front
2. Delete Front
3. Display
4. Exit
3
The contents of the list are:
30
20
10
1. Insert front
147
2. Delete Front
3. Display
4. Exit
2
The deleted value is 30
1. Insert front
2. Delete Front
3. Display
4. Exit
3
The contents of the list are:
20
10
1. Insert front
2. Delete Front
3. Display
4. Exit
4
148
Data structure tutorial 4: Doubly Linked List [DLL]
In this chapter we shall learn about below topics:
In the previous chapter we learnt about single linked list. In this chapter we shall learn about
Doubly Linked List.
Doubly Linked List is a special data structure, which is a collection of zero or more nodes.
Each node is made up of 3 parts, “prev_link + data + next_link”. As it is a Doubly linked list,
we need to store the address information for the previous node and the next node.
149
3. Data section holds the data
4. Head pointer always point to the first node
If the head element is not NULL, it means that there are already elements present. Hence
we do the following steps to insert at the rear.
150
2. Delete element with given key value.
To delete we follow below steps:
1. Take a temp pointer move to the point till you find the element equal to the key.
2. If the element is the lest element, then make the previous element’s next pointer to
NULL.
3. Else, do the following operations:
1. temp->prev->next = temp->next;
2. temp->next->prev = temp->prev;
4. Delete temp node.
3. Search an element.
To search an element, we do below steps:
151
2. Display the data
3. Move the temp pointer to next node
4. Do step 2 and 3 till you reach the end of LL.
#include<iostream>
using namespace std;
struct Node
{
int val;
Node *prev;
Node *next;
};
Node *head;
void remove(int x)
152
{
Node *temp = head;
while(temp->val != x)
{
temp = temp->next;
}
if(temp -> next == NULL)
{
temp->prev->next = NULL;
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
delete temp;
}
void search(int x)
{
Node *temp = head;
int found = 0;
while(temp != NULL)
{
if(temp->val == x)
{
cout<<"\nFound";
found = 1;
break;
}
temp = temp->next;
}
if(found==0)
{
cout<<"\nNot Found";
}
}
void display()
{
Node *temp =head;
while(temp !=NULL)
{
cout<< temp->val<<"\t";
temp = temp->next;
}
153
}
int main()
{
int choice, x;
do
{
cout<<"\n1. Insert";
cout<<"\n2. Delete";
cout<<"\n3. Search";
cout<<"\n4. Display";
cout<<"\n5. Exit";
cout<<"\n\nEnter you choice : ";
cin>>choice;
switch (choice)
{
case 1 : cout<<"\nEnter the element to be inserted at rear : ";
cin>>x;;
insert_rear(x);
break;
case 4 : display();
break;
}
}
while(choice != 5);
return 0;
}
1. Insert
2. Delete
154
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
155
2. Delete
3. Search
4. Display
5. Exit
Found
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
156
Data structure tutorial 5: Circular Singly Linked List
In this chapter we shall learn about below topics:
In the first chapter of Linked List we learnt about Singly Linked List. In this chapter we shall
learn about circular singly linked list.
The only addition is, the last node next pointer will point to the head node, hence making it
circular Linked List.
1. Insert at end
To insert a node at end, we do following steps:
2. Delete at end
157
To delete the node at the end, we perform the below steps:
1. If there is only 1 node, then delete the node.
2. Else traverse till the end of the list, make the “next” pointer of previous node point to the
head node.
3. Free the temp node.
3. Display
To display all the elements, take a temp pointer, so that we don’t lose the head node.
Then traverse the list till the end of the list.
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
158
current = current -> next;
void display()
{
if(head == NULL)
printf("\n Empty List");
else
{
159
struct Node *temp = head;
printf("Printing values\n");
while(temp -> next != head)
{
int main()
{
int value;
int logout = 0;
while(logout == 0)
{
printf("Choose any option:\n\n");
printf("1)Insert end\n");
printf("2)Delete tail\n");
printf("3)Display List\n");
printf("4)Exit\n");
int choice;
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter value:\n");
scanf("%d",&value);
insert_end(value);
break;
case 2:
delete_tail();
break;
case 3:
display();
break;
case 4:
logout = 1;
break;
}
}
160
}
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
1
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
2
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
3
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
1
Enter value:
4
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
161
3
Printing values
1
2
3
4
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
2
1)Insert end
2)Delete tail
3)Display List
4)Exit
3
Printing values
1
2
3
Choose any option:
1)Insert end
2)Delete tail
3)Display List
4)Exit
4
162
Data structure tutorial 6: Circular Doubly Linked List
In this chapter we shall learn about below topics:
In the previous chapter we saw how to create a Doubly Linked List. In this chapter we shall
learn about circular doubly linked list.
6.2 Operations performed on Circular Doubly Linked List that we are going to learn in this
tutorial.
1. Insert Rear
2. Delete element when a key is given
3. Display all the elements
1. Insert Rear
If there is only 1 node, then make prev pointer of new node to itself. Then assign the head
pointer to the new node. Then assign the next pointer of the new node to head node.
else
If there are other elements, then traverse till the last element. Then point the prev pointer
of the new node to the last node, then point the next pointer of the new node to the head
node.
#include<iostream>
using namespace std;
163
struct Node
{
int val;
Node *prev;
Node *next;
};
Node *head;
if(head == NULL)
{
//if the head is null
//assign the prev to newNode
newNode->prev = newNode;
}
else
{
//if the head is not null
// take a temp node to go to last node
Node* temp = head->prev;
164
temp->next = newNode;
}
}
void remove(int x)
{
if(head == NULL)
{
printf("\nList is Empty.\n");
return;
}
else
{
if(head->val == x)
{
//if the head value is equal to element to be deleted
if(head->next == head)
{
//if there is only 1 element
head=NULL;
}
else
{
Node* temp = head->prev;
head = head->next;
head->prev = temp;
temp->next = head;
}
return;
}
Node* temp = head->next;
while(temp != head && temp->val != x)
{
temp = temp->next;
}
if(temp == head)
{
printf("Value not found in list\n");
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
}
165
}
void search(int x)
{
Node *temp = head;
int found = 0;
do
{
if(temp->val == x)
{
cout<<"\nFound";
found = 1;
break;
}
temp = temp->next;
}while(temp != head);
if(found == 0)
{
cout<<"\nNot Found";
}
}
void display()
{
Node *temp = head;
do
{
cout<< temp->val<<"\t";
temp = temp->next;
}while(temp != head);
int main()
{
int choice, x;
do
{
cout<<"\n1. Insert";
cout<<"\n2. Delete";
cout<<"\n3. Search";
cout<<"\n4. Display";
cout<<"\n5. Exit";
166
cout<<"\n\nEnter you choice : ";
cin>>choice;
switch (choice)
{
case 1 : cout<<"\nEnter the element to be inserted at rear : ";
cin>>x;;
insert_rear(x);
break;
case 4 : display();
break;
}
}
while(choice != 5);
return 0;
}
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
167
Enter you choice : 1
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
168
5. Exit
1. Insert
2. Delete
3. Search
4. Display
5. Exit
169
Data structure tutorial 7: Introduction to Queue Data Structure
In this chapter we shall learn about below topics:
A queue is a data structure where the elements are inserted from one end and are deleted
from the other end.
The place where the elements are inserted is called as rear end, and the place where the
elements are deleted is called as front end.
Hence the element that is inserted first is the first element to be deleted.
170
From the above image, we can see that first 2 positions are empty. But if we try to insert an
element, the program will throw us “queue full” message, because it cannot access the
front elements. Thus wasting space.
To overcome this problem, we use “Circular Queue”. We shall study about it in next
chapters.
171
As you can see from the above image, initially, “front” pointer will be at index 0 and “rear”
pointer will be at index -1.
Once we start inserting the elements, we start to increment “rear” pointer keeping “front”
pointer as it is.
172
Delete: Delete element in the front end.
As you can see from the image above, now we update the “front” pointer when we remove
the elements.
Overflow: Check if queue is having space, while inserting a new element, else will result in
overflow.
Underflow: Check if queue is empty and we try to delete an element, will result in
underflow.
#include<stdio.h>
#include<stdlib.h>
#define QUEUE_SIZE 5
173
void InsertQueue()
{
if (rear_end == QUEUE_SIZE -1)
{
printf("Queue is full\n\n");
return;
}
rear_end += 1;
queue_elements[rear_end] = queue_item;
}
int DeleteQueue()
{
if (front_end > rear_end)
{
return -1;
}
else
{
return queue_elements[front_end++];
}
}
void DisplayQueue()
{
int i = 0;
int main()
{
int choice = 0;
174
front_end = 0;
rear_end = -1;
for( ; ; )
{
printf("1. Insert \n2. Delete \n3. Display \n4. Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter the item to be inserted\n");
scanf("%d", &queue_item);
InsertQueue();
break;
case 2:
queue_item = DeleteQueue();
if(queue_item == -1)
{
printf("Queue is empty\n");
}
else
{
printf("Deleted Item =
%d\n",queue_item );
}
break;
case 3:
DisplayQueue();
break;
default:
exit(0);
}
}
return 0;
}
175
1. Insert
2. Delete
3. Display
4. Exit
3
Queue is empty
1. Insert
2. Delete
3. Display
4. Exit
1
176
1. Insert
2. Delete
3. Display
4. Exit
4
177
Data structure tutorial 8: Queue Data Structure implementation using linked list in C
In this chapter we shall learn about below topics:
In previous chapter we have seen how to implement queue using arrays. In this chapter we
shall see how to implement queue using linked list [LL].
One major implementation difference here is that, instead of taking 2 pointers like “rear”
and “front”, using LL we can manage using one “head” pointer, that will always point to the
start of the list. And manipulate using that pointer.
We shall see how we insert and delete elements from queue from below steps.
Step 3: If the list is not empty, take a “curr” pointer and navigate till the end of the list.
Step 4: Then point the “next” pointer of “curr” to the “temp” node.
178
Taking a “curr” pointer and navigating to the end of Queue
To delete an element from the front end of the queue we perform below steps.
Step 1: Take a temp pointer to the head of the list, so that we don’t loose the head pointer.
Step 3: Delete the node pointed by temp pointer and free the memory to avoid memory
leak.
179
Delete the node hold by temp pointer
#include<stdio.h>
#include<stdlib.h> //for memory allocation functions
};
180
//take a temp node to hold the value
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->data = value;
temp->next = NULL;
while(curr->next != NULL)
{
curr = curr->next;
}
curr->next=temp;
}
}
//free temp
free(temp);
void display()
{
struct node *temp = head;
if(temp == NULL)
{
printf("List is Empty\n");
}
else
{
while(temp != NULL)
{
printf("Displaying Data:\t");
printf("%d \n",temp->data);
181
temp = temp->next;
}
}
}
int main()
{
int choice;
while(choice!=4)
{
printf("\t\tQUEUE Using LinkedList\n");
printf("Choose One\n\n");
printf("1)Enqueue\n");
printf("2)Dequeue\n");
printf("3)Display\n");
printf("4)Logout\n\n");
int option;
int value;
scanf("%d",&option);
switch(option)
{
case 1:
printf("Enter Number:\n");
scanf("%d",&value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
choice=4;
break;
default:
printf("Wrong Input\n\n");
}
}
return 0;
}
182
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
1
Enter Number:
1
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
1
Enter Number:
2
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
1
Enter Number:
3
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
1
Enter Number:
4
QUEUE Using LinkedList
Choose One
183
1)Enqueue
2)Dequeue
3)Display
4)Logout
3
Displaying Data: 1
Displaying Data: 2
Displaying Data: 3
Displaying Data: 4
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
2
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
3
Displaying Data: 2
Displaying Data: 3
Displaying Data: 4
QUEUE Using LinkedList
Choose One
1)Enqueue
2)Dequeue
3)Display
4)Logout
184
Data structure tutorial 9: Circular Queues Data structure introduction and Implementation
using arrays.
In this chapter we shall learn about below topics:
In the previous chapter we have seen the implementation of simple queue using Array and
Linked List [LL]. But we have also seen a disadvantage while using simple queue is that we
will not be able to fully utilize the empty spaces. Hence to utilize the space efficiently we
should Circular Queues.
Definition:
A circular linked list, the elements in the queue can be inserted in the empty spaces at the
front of the queue hence using the empty spaces efficiently.
In circular queue, the front will be pointing at 0 and rear pointer will be pointing at the
maximum index size of the queue. We will be using modulus “%” operator to know the
empty spaces that have left.
When an element is inserted at the rear end, we use below formula to calculate it’s index.
Similarly, when an element is deleted from front_ end we use below formula it’s calculate
the index:
Assume MAX_QUEUE_SIZE = 4;
Initially:
front_ end will be at index 0
rear_ end will be at index 3
185
Enter 10:
front_ end will be at index 0
rear_ end = [ 3 + 1] % 4 = 0
[10, , , ]
Enter 20:
front_ end will be at index 0
rear_ end = [ 0 + 1] % 4 = 1
[10, 20, , ]
Enter 30:
front_ end will be at index 0
rear_ end = [ 1+ 1] % 4 = 2
Enter 40:
front_ end will be at index 0
rear_ end = [ 2 + 1] % 4 = 3
Delete 10
Enter 50:
front_ end will be at index 1
rear_ end = [ 3 + 1] % 4 = 0
Check if there is any element at index '0'. If no element enters 50.
186
Hence element will be inserted at index 0
depending upon the result, the rear pointer will update accordingly.
1. Insert ():
This function is used to insert elements into the queue.
2. Delete ():
This function is used to delete element from the queue.
187
3. Display ():
In this function we will display the queue elements.
#include<stdio.h>
#include<stdlib.h>
#define QUEUE_SIZE 5
queue_item = queue_elements[front_end];
return queue_item;
188
}
int main()
{
int choice = 0;
front_end = 0;
rear_end = -1;
element_count = 0;
for( ; ; )
{
printf("1. Insert \n2. Delete \n3. Display \n4. Exit\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter the item to be inserted\n");
scanf("%d", &queue_item);
InsertQueue();
break;
189
case 2:
queue_item = DeleteQueue();
if(queue_item == -1)
{
printf("Queue is empty\n");
}
else
{
printf("Deleted Item =
%d\n",queue_item );
}
break;
case 3:
DisplayQueue();
break;
default:
exit(0);
}
}
return 0;
}
190
Data structure tutorial 10: Implementation of Circular Queue using Linked List
In this chapter we shall learn about below topics:
In the previous chapter we have seen the implementation of Circular Queue using arrays. In
this chapter we shall see how to implement Circular Queue using Circular Singly Linked List.
As we are using circular singly linked list, there is no need to compute the index where the
element should be inserted.
“front” pointer will always point at the beginning of LL. This pointer will be used to delete
the element.
“rear” pointer will always point at the end of LL. This pointer will be used to insert an
element.
191
As you can see from the image above, we increase the rear pointer and keep the front
pointer still, while we are inserting the elements.
As you can see from the above image, we increase the front pointer and keep the rear
pointer still, while we are deleting the elements.
As we are using 2 pointers, we don’t need to compute the index to be inserted, like we did
in the array implementation.
192
10.3. Implementation of Circular Queue using Linked List
#include<iostream>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
newNode->data = val;
newNode->next = NULL;
newNode->next = front;
rear = newNode;
}
}
void dequeue()
{
Node *n;
n = front;
front = front->next;
193
delete(n);
}
void display()
{
Node *ptr;
ptr = front;
do
{
cout<< ptr->data <<" ";
ptr = ptr->next;
}while(ptr != rear->next);
cout<<endl;
cout<<endl;
int main(void)
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
enqueue(60);
display();
dequeue();
display();
return 0;
}
10.4 Output
10 20 30 40 50 60
20 30 40 50 60
194
Trees Data Structure Tutorials:
Tree data structure tutorial 12. Performing minimum Range query in Segment Tree and
implementation
195
Tree data structure tutorial 1. Tree Data Structure Introduction
In this chapter you are going to learn about below topics:
Trees are non-linear data structures. They are used to represent hierarchical relationships.
It is a very interesting data structure. Data Structure like array, Linked List, Stack, Queue is
linear data structure. They have a logical start and logical end.
1. Pre-Order traversal
2. In-Order traversal
3. Post-Order traversal
196
As we know that a tree is a collection of nodes and edges.
Nodes are usually represented as circular in shape. But they can also be represented in
different shape as shown below:
Edge or a path is represented by a straight line. As in tree, you can traverse from top to
bottom, there is no need to use arrow lines.
1. Parent Node
197
In the above image, A is the parent for both “B” and “C” nodes.
B is the parent node for “D”.
2. Child Node:
3. Siblings:
All the nodes or children which have a common parent are collectively known as siblings.
4. Forest:
Set of independent trees are called as forest.
198
5. Leaf node:
A node with no child is called as leaf node.
6. Internal Nodes:
The nodes with at least one child can be called as internal nodes.
From the image above, “A”, “B”, “D” are ancestors for “G”. And “G” is the descendant for all
the above nodes.
1. Index of a book can be considered as a tree. A book is organized into several chapters,
each chapter is divided into sections and sub sections.
2. File system in Unix or Linux. The file system will start from a root, then it will branch out
according to requirement.
199
2. A tree with “n” nodes will be having exactly “n-1” edges.
Depth of a node:
The depth of a node is the length of the path from root to that node.
i.e the number of edges from root to that node.
Height of a node:
Height of a node is the longest path from that node to a leaf node.
200
From the image above,
The height of node “D” is 2. Because D -> F -> G
Height of a Tree:
The height of a tree is defined as the height of root node.
Hence from the above image, the height of the tree is 4. Because A -> B -> D -> F -> G
201
Tree data structure tutorial 2. Introduction to Binary Tree
In this chapter we shall learn about:
As a node can have a maximum of 2 children, the child to the left is called as left child and to
the right is called as right child.
A node can have both left and right children or only left or right child.
202
A node with no child is called as leaf node.
Example
203
Hence from the image above, we can infer that the maximum number of nodes at a
particular level is 2^i. Where “i” is the level.
At level 0, 2^0 = 1
At level 1, 2^1 = 2 at max 2 nodes
At level 2, 2^2 = 4 at max 4 nodes
At level 3, 2^3 = 8 at max 8 nodes
Hence the total number of nodes in a perfect binary tree will be 2^(num of level) -1;
Hence the total number of nodes for a level 4 perfect binary tree will have 2^4 -1 = 15
nodes.
204
Tree data structure tutorial 3. Binary Tree Traversal
In this chapter we shall learn about:
A tree traversal can be defined as the process of visiting each node exactly once in some
order.
As we know that trees are non-linear data structure, we start from root node. Then we have
2 possible directions, i.e. to go left or to go right.
This type of traversal holds good for both trees and graphs. [We shall discuss graph in next
chapter]. In this chapter we shall learn related to trees.
In Breadth first traversal, we shall visit all the nodes at the same level before visiting the
nodes at the next level.
205
In Breadth First approach, we should start from Level 0, then cover all the nodes in that
level, then go to the next level.
So first we visit the root node at level 0. The root node value is “10”. Then we go to level 1,
and then visit the nodes from left to right. Then nodes at level 1 are “11” “12”.
Now we completed level 1, then visit level 2. The nodes at level 2 are “13” “14” “15” “16”.
Now we visit level 3. The nodes at level 3 are “17” “18” “19” “20” “21” “22” “23” “24”.
When we combine all the nodes from all the level we get:
“10” “11” “12” “13” “14” “15” “16” “17” “18” “19” “20” “21” “22” “23” “24”.
In this approach, once we get a child, we would complete the whole sub tree of that child
before going to the next child.
In our example, “10” is the root node. If we select “11” child, then we need to complete all
the nodes present in that “11” sub tree. Then we should go to Right Sub Tree. Likewise we
traverse all the nodes in the tree.
206
Depending on how we traverse we have 3 options.
In total we have 6 possible permutations. But above 3 are the commonly used strategies.
To remember the traversal easily, if we consider root as “D” as in data, left as “L” and right
as “R” we get:
Pre Order Traversal: DLR
In Order Traversal: LDR
Post Order Traversal: LRD
In this type of traversal, we visit the root node first, then visit left node, then right node.
First visit the root node “10”, then go to left sub tree “11”, then again “13” has a child “17”,
visit it.
Hence we have visited all the nodes to the left.
“10” “11” “13” “17”.
There are no left sub tree to visit. Hence go one level up i.e “13”. “13” node, left sub tree is
completed. But we did not complete right sub tree. Hence visit it i.e “18”.
Now we have completed node “13”. Go one level up to “11”. As we have visited left sub
tree, go to right sub tree i.e “14”.
207
“10” “11” “13” “17” “18” “14”.
Now we have completed the left sub tree of root node. Now we go to right sub tree of root
node.
Now we go to “12” node. Node “12” has a left node “15” visit it. Then Node “15” does not
have left sub tree, but has a right sub tree visit it i.e “22”.
“12” “15” “22”
Now that we have complete node “15” go one level up to node “12”. Visit all the nodes at
right sub tree. i.e “16” “24”.
Hence the total order of visiting of all the nodes in pre order traversal is
“10” “11” “13” “17” “18” “14” “12” “15” “22” “16” “24”
In this traversal we visit left sub tree, then root then right sub tree.
In our example, we start with root node “10”, traverse to left i.e “11”, then “13”, then “17”.
As “17” node doesn’t have any left sub tree, start with that, then visit it’s root i.e “13”, then
to its right, i.e “18”.
Hence we get
“17” “13” “18”.
Then go one level up, to node “11”, as we have visited left sub tree, go to right i.e “14”.
“17” “13” “18” “11” “14”.
Then go to right sub tree “12”, in that go to left sub tree “15”, as “15” does not have left sub
tree, visit right sub tree “22”
Hence we get “15”, “22”
Go one level up “12”, then visit right sub tree “16” “24”
In post order traversal, we visit the left sub tree first, then right sub tree, then to the root
node.
208
In our example, we first go to 10 -> 11 -> 13 -> 17.
First we visit 17 node, then 18, then 13.
Note: Now we don’t visit the root node, we need to go to right sub tree.
“17”, “18”, “13”, “14”, “11” ,“22”, “15”, “24”, “16”, “12”, “10”
209
Tree data structure tutorial 4. Binary Search Tree Introduction
In this tutorial we shall learn about following topics:
Binary Search Tree [BST] is a tree, where the data will be placed in a particular order.
Because of this kind if organization, it will help to insert and search the data efficiently.
In a binary tree, for each node, if the value of all the nodes in left sub tree is lesser and the
value of all the nodes in the right sub tree is greater, then such binary tree is called as Binary
Search Tree.
Definition: A Binary Tree in which for each node, the value of all the nodes in the left sub
tree is lesser or equal and value of all the nodes in right sub tree is greater, then such a
binary tree is called as Binary search tree.
From the above image, “15”is the root node. The value of the nodes at left sub tree is lesser
than the root node and right sub tree is greater than the root node.
Now, if we consider the sub tree at node “10”, left node has less value and right node has
higher value.
Consider the below tree. The value to be searched is 12. Below are the steps that we follow
to search for element 12.
210
First check the root node, in our case, the element 12 is less than the root node. Hence
move towards left.
Then check the value of new node i.e 10. As 12 is greater than 10, move towards right.
211
4.4 Now let us see, how to insert an element in BST
Start from the root node, “15”. As the value “19” is greater than root node “15”, we move
towards right side of the tree.
Now we have reached node “20”. As “19” is lesser than “20”, we move towards left to node
18.
Now “19” is greater than “18”, we insert it to the right of node “18”.
212
213
Tree data structure tutorial 5. Implementation of BST in C++
#include<iostream>
#include<vector>
#include<string>
struct Node
{
int data;
Node *left;
Node *right;
};
214
}
215
int getHeight(Node *root)
{
if (!root)
return 0;
return 1 + max(getHeight(root->left) , getHeight(root->right));
}
216
else
{
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
delete temp;
}
return node;
}
int main()
{
root = insert(10, root);
root = insert(30, root);
root = insert(20, root);
root = insert(50, root);
root = insert(60, root);
root = insert(25, root);
root = insert(15, root);
217
Node *min_value = findMin(root);
cout<<"\nThe minimum value is "<< min_value->data <<endl;
if(isBalanced(root))
cout<<"\nThe tree is balanced"<<endl;
else
cout<<"\nThe tree not is balanced"<<endl;
remove(root, key);
cout<<"\nThe key "<<key<<" has been deleted"<<endl;
return 0;
Output:
218
The key 60 is present
219
Tree data structure tutorial 6. Implementation of Binary tree in C++
Implement below operations on Binary Tree
1. Insert Operation
2. Find Min
3. Find Max
4. In-order Traversal
5. Pre-order Traversal
6. Post-order Traversal
7. Get height of the tree
8. Check if the tree is a balanced tree
9. Delete entire tree
10. Find given key
#include<iostream>
#include<vector>
#include<string>
#include<queue>
struct Node
{
int data;
Node *left;
Node *right;
Node(int x)
{
data = x;
left = NULL;
right = NULL;
}
};
220
inorder(root->right);
}
221
// Remove current node and enqueue its children
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
return false;
}
return result;
}
222
// Find the maximum value in left sub-tree
int lres = findMin(root->left);
return result;
}
int main()
{
root = new Node(1);
/*
1
*/
223
root -> left = new Node(2);
root -> right = new Node(3);
/*
1
/ \
2 3
*/
root -> left -> left = new Node(4);
/*
1
/ \
2 3
/
4
*/
224
cout<<"\nThe height of the tree is = "<< getHeight(root)<<endl;
if(isBalanced(root))
cout<<"\nThe tree is balanced"<<endl;
else
cout<<"\nThe tree not is balanced"<<endl;
Output:
Deleting node = 16
Deleting node = 15
Deleting node = 4
225
Deleting node = 6
Deleting node = 5
Deleting node = 8
Deleting node = 2
Deleting node = 3
Deleting node = 1
226
Tree data structure tutorial 7. TRIE Data structure
In this chapter we shall look at following things:
7.1. Introduction to TRIE
7.2. Insertion
7.3. Search
7.4. Auto complete
TRIE stands for reTrival. It is based on tree data structure, where a single node will store a
single alphabet, and we can search for strings or words by traversing down a branch of the
tree.
TRIE data structure is very efficient in storing a key value pair. The nodes in a path will act as
the key and once the key is found, we get the value.
For example, in designing a phonebook, to retrieve phone number for a person, we use TRIE
data structure. Here we can use Name of the person as key, and the mobile number as
value.
When we are doing a google search, it will automatically suggest the search string. This
feature employs TRIE implementation.
Similar to tree data structure, TRIE will also have an empty root to start with.
The number of child nodes will always depend on the number of the total possible values.
Suppose we want to store words; we have 26 available alphabets. Hence each node will
hold 26 possible values.
227
As you see in the image above, there is a root node to start with. Each node will have
elements from A to Z. But It will store only 1 element.
Ant
All
Also
Bat
Ball
From the image above, we can see that, each node will have 26 different places. And each
node can hold one character.
228
So how the words will be inserted into TRIE?
In the above words “all” “also”, these 2 share the same prefix. Similarly, “bat” “ball” will
share the same prefix. Hence trie will take this as an advantage, and we build a tree as
shown in the image.
struct node
{
bool isEnd;
struct node *child[ALPHABETS];
}*head
As you can see in the structure above, we have a child node that holds 26 characters. Then a
Boolean variable to check if the node is the end node or not.
The working of insert, search and auto complete has been provided in the code.
#include<iostream>
#include<string>
#include<vector>
#include<fstream>
#define ALPHABETS 26
229
//function to insert whole word
void insert(string word)
{
if(word.empty())
return;
current = current->child[word[i]-'a'];
}
current->isEnd = true;
}
230
}
cout << "\n";
}
for(int i=0; i<26; i++)
{
if(tmp->child[i] != NULL)
{
word.push_back((char)i+'a');
print_all(tmp->child[i],word);
word.pop_back();
}
}
}
if(prefix.length() == 0)
{
cout << "please enter valid prefix " << "\n";
return;
}
node *current = head;
for(int i=0; i < prefix.length(); i++)
{
if(current->child[prefix[i]-'a'] == NULL)
{
cout << "prefix does not exist" << "\n";
return;
}
word.push_back(prefix[i]);
current = current->child[prefix[i]-'a'];
}
cout << "The words present with the prfix is as follows:" << "\n";
print_all(current,word);
}
int main()
{
init();
string s = "ajay";
insert(s);
s = "tea";
231
insert(s);
s = "bat";
insert(s);
s = "cat";
insert(s);
s = "ball";
insert(s);
s = "background";
insert(s);
s = "bachelorette";
insert(s);
if(search("ajay"))
printf("found ajay\n");
else
printf("Not found ajay\n");
if(search("background"))
printf("found background\n");
else
printf("not found background\n");
auto_complete("ba");
return 0;
}
Output:
found ajay
found background
The words present with the prefix is as follows:
bachelorette
background
ball
bat
232
Tree data structure tutorial 8. Heaps
In this chapter we shall have a look at:
8.2 Heaps can be divided into 2 types. Based on the type the property will differ. The 2
types of heap are:
1. Min heap
2. Max Heap
1. Min heap:
In minimum heap, the value of the parent node will always be less than or equal to their
child node in entire tree.
2. Max heap:
In this type of heap, the value of parent node will always be greater than or equal to their
child node in the entire tree
233
As heap is also a tree, a single parent can have many children. But usually in practice, we see
a node [parent node] having at most 2 children. Hence such type of heap is called as “Binary
Heap”.
8.3 Below are the operations that are performed on a binary heap:
Although heaps are tree based algorithm, they are implemented using arrays. C++ standard
library provides algorithms to create and manipulate heaps.
Similarly, to know the parent index for a child, it can be found by using the formula:
Parent_index = (child_index -1)/2
Then we rebuild heap to place the new element at its correct position.
234
1. Start with the bottom node.
2. Get the parent node.
3. If the child node is greater than the parent node, swap the elements else quit.
Now let us see how to remove max element from the heap:
To remove the element from heap, swap the first and last element of the array/heap.
Decrement the “bottom” of the array, thus removing the element.
Then rebuild the heap/array to restructure the newly formed array by following below
steps.
#include<iostream>
int get_parent(int i)
{
return (i-1)/2;
}
235
// get right child
int right_child(int i)
{
return (2*i + 2);
}
if (smallest != i)
{
swap(&ptr_heap_arr[i], &ptr_heap_arr[smallest]);
min_heapify(smallest);
}
}
236
//heapify the new tree
min_heapify(0);
return root;
}
void insert_element(int k)
{
if (current_heap_size == max_heap_capacity)
{
cout << "\n max heap capacity has been reached";
return;
}
current_heap_size++;
int i = current_heap_size - 1;
ptr_heap_arr[i] = k;
int main()
{
min_heap(11);
insert_element(3);
insert_element(2);
insert_element(14);
insert_element(6);
insert_element(7);
insert_element(35);
cout <<extractMin() << " ";
return 0;
}
8.5. Output
237
Tree data structure tutorial 9. Priority Queue
In this chapter we shall have a look at:
In this chapter we shall learn about priority queue and it’s implementation using Linked list
in C language.
For example:
1. A process with higher priority needs to be executed first than the process with lower
priority.
2. During printing job of 100 pages, if there is priority for a particular document, then the
printer has to pause the ongoing job and start printing the high priority job.
#include "stdio.h"
#include "stdlib.h"
238
int priority;
struct Node* next;
};
//head node
struct Node* head = NULL;
else
{
while(p->next!=NULL && p->next->priority <= priority)
p = p->next;
239
temp->next = p->next;
p->next = temp;
}
}
int dequeue()
{
struct Node *tmp;
int item;
if( isempty() )
{
printf("\nQueue Underflow\n");
return -1;
}
else
{
tmp=head;
item=tmp->data;
head=head->next;
free(tmp);
}
return item;
}
int main()
{
//lower the priority value, higher the priority
enqueue(4,34);
enqueue(1,25);
enqueue(6,98);
enqueue(2,87);
enqueue(3,67);
enqueue(5,23);
traverse();
9.5 Output:
240
Data = 67 and it's priority is = 3
Data = 34 and it's priority is = 4
Data = 23 and it's priority is = 5
Data = 98 and it's priority is = 6
highest priority element is = 25
241
Tree data structure tutorial 10. AVL tree introduction and its implementation
In this chapter we shall learn about below topics:
A tree to be called as BST if the elements to its left are lower than the parent value and the
elements to its right are greater than the parent value. And duplicate values are not allowed
in BST.
Consider the elements {1, 2, 3}. The BST can be constructed in different ways, depending
upon the position of the elements.
For example:
242
1. If the elements are {1, 2, 3} the BST can be as below:
As you see, depending upon the position of the elements, the tree structure changes. But if
you use AVL tree, the tree structure will remain same, we shall see further in this chapter.
243
If the balancing factor is not in the range {-1, 0, 1}, then we need to make it balanced.
As you might have guessed from above naming convention, we do the rotation depending
upon the type of imbalance found. We shall learn about those rotations one by one below:
Insert 3
Insert 2
The balance factor for leaf node “2” will be zero. The balance factor for node with value “3”
is 1. Because, it has only right child of height 1. Now also it is an AVL tree.
Insert 1.
244
Balance factor for leaf node with value “1” is 0.
Balance factor node with value “2” is 1, as it has only right child
Balance factor node with value “3” is 2, as it has 2 right children. Hence the tree is not
balanced.
The imbalance has occurred in Left Left child. Hence we say LL rotation. In this case, we
need to rotate right side with middle node “2” as root
245
After rotation
Insert 1
Insert 2
Insert 3
246
Now there is an imbalance, in Right Right. Hence do a left rotation 2.
247
10.5 Left Right Imbalance Rotation
To make it AVL balanced, you need to rotate it 2 times. One is Left rotation; another time is
Right Rotation.
248
10.6 Right Left Imbalance Rotation
To make it AVL balanced, you need to rotate it 2 times. One is Right rotation; another time
is Left Rotation.
249
First rotate Left. Below is the final AVL tree.
As you see from above 4 rotations, the final AVL tree is the same.
Left Right Imbalance Rotation -> Do Left rotation, then Right Rotation.
Right Left Imbalance Rotation -> Do Right Rotation, then left Rotation.
#include "stdio.h"
#include "stdlib.h"
250
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
temp->height = 1;
return temp;
}
return node->height;
}
b->left = a;
a->right = temp;
a->height = get_max_height(get_height(a->left),get_height(a->right))+1;
b->height = get_max_height(get_height(b->left),get_height(b->right))+1;
return b;
}
251
struct Node* temp = b->right;
b->right = a;
a->left = temp;
a->height = get_max_height(get_height(a->left),get_height(a->right))+1;
b->height = get_max_height(get_height(b->left),get_height(b->right))+1;
return b;
}
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
else
return root;
root->height = get_max_height(get_height(root->left),get_height(root->right))+1;
// LL imbalance case
if(balance > 1 && data < root->left->data)
return RightRotate(root);
// RR imbalance case
if(balance < -1 && data > root->right->data)
return LeftRotate(root);
252
// LR imbalance case
if(balance > 1 && data > root->left->data)
{
root->left = LeftRotate(root->left);
return RightRotate(root);
}
// RL imbalance case
if(balance < -1 && data < root->right->data)
{
root->right = RightRotate(root->right);
return LeftRotate(root);
}
return root;
}
int main()
{
struct Node* root = NULL;
root = insert(root,5);
root = insert(root,10);
root = insert(root,15);
root = insert(root,30);
root = insert(root,14);
root = insert(root,24);
root = insert(root,3);
return 0;
}
10.8 Output
15 10 5 3 14 30 24
253
Tree data structure tutorial 11. Introduction to Segment Trees
In this chapter we shall learn about below topics:
Segment tree is a special tree that is based on ranges. In this chapter we shall learn about
basics of segment tree. In the next chapter we shall learn about the implementation and
also about Lazy Propagation.
Usually segment trees are used to find solution to the problems based on the range query in
the array.
We shall learn in-depth of both of the types, by seeing the generic solution and also with
segment tree solution.
In the above array, there are 9 elements and you are asked to find the sum of elements
from index 2 to 5.
i.e 5 + 1 + 2 + 3 = 11
254
But if you are asked to find the sum from index 0 to 8, this will be the worst case. You will
need to run the loop for all the elements. Hence it will take O(n) time.
We shall see how to build a segment tree for the array elements above.
At the minimum, a segment tree can be constructed by keeping all the elements of the array
as leaf node and then constructing from bottom to top.
In the series of steps below, we shall see how we can construct segment tree for sum range
query.
Now we shall make the sum of the range [0, 1] [2, 3] [4, 5] [6, 7] [8]
Now, we shall calculate the sum for the range [0, 3] [4, 7] [8].
As we have already have calculated sum for sub range, it’s just matter of adding those sub
ranges.
255
Now we shall calculate the range for [4, 8].
256
This is how we build segment tree for sum range query. Now if you were to get the sum of
range [0, 3], then you can directly get the sum = 12. This can be done for O(logn) time at
worst case.
You are asked to find the minimum element from the range 3 to 6. The answer will be 1. But
if you are to find the min element in the whole array, and the min element is at the end of
the array, it will take O(n) time at worst case.
Similar to previous section, make all the elements of the array as leaf node. As shown
below.
Now we shall find the shortest value for the range [0, 1] [2, 3] [4, 5] as shown below:
257
Now we shall find the shortest value for the range [0, 3].
Now we shall find the shortest range for whole array [0, 5]. Thus completing the segment
tree for shortest value in the range.
258
That’s all for this chapter. In the next chapter we shall know in depth on creating segment
tree and the steps involved in querying for range values.
259
Tree data structure tutorial 12: Performing minimum Range query in Segment Tree and
implementation
In this chapter we shall learn about below topics:
In the previous chapter we learnt on conceptual level on creating a segment tree. In this
chapter we shall learn on actually how to implement and search for range queries.
1. Partial Overlap
2. Total Overlap
3. No – Overlap
4. Construct Segment Tree
In the first section we shall learn the different methods to perform range queries. In the
next section we shall see how to construct a segment tree.
Point to be noted here is, the range query is performed with respect to the search query
range. What is that? We shall see further.
1. Partial overlap
2. Total Overlap
3. No-overlap
Now we shall try to understand the above 3 methods by taking simple examples.
260
Consider the parent range is “0-6” and we need to find min in the range of “3-4”. Here we
can say that the query is a partial overlap for the parent range. It doesn’t matter if the
parent range “0-6” in total overlap for search range “3-4”.
Here the search range should overlap the parent. We look overlap with respect to search
query. When we have partial overlap, we look at both left and right child.
As you can see in the above image, the query range totally overlap the parent range.
12.3 No Overlap
Consider the parent range “0-2” and query range “3-4”, there is no overlap. In this case we
return Int_Max stating that there is no overlap of search query with parent query.
261
Now that we have a brief idea of the 3 rules, we shall take an example and understand them
better.
At first “3-5” is a partial overlap of “0-5”. Hence we need to check both left and right
children.
262
First we shall go to left child.
Here the node with min query index of [0, 3] is a partial overlap for the search query [3, 5].
Hence we again check for left and right children for that node.
Again we take left child with min query index of [0, 1]. As [0, 1] is no-overlap for the query
range of [3, 5] we return INT_MAX.
Now we shall go to right child for the node [0, 3]. The right child is [2, 3], as it is a partial
overlap return 1.
263
Now at the parent node of query [0, 3], we have to choose the min of both left and right
child. i.e min(INT_MAX, 1). Return 1.
Now we check the right child of the parent node with query [0, 5]. The right child is [4, 5].
This is a partial overlap for our search query [3, 5]. Hence return 5.
264
At the parent node of query [0, 5], choose the min of left child and right child. i.e min [1, 5]
is 1.
In the previous section we saw to how query in a segment tree. In this section we shall see
how to build a segment tree.
A segment tree at it’s basic, is an array. We calculate the min value and place them at
appropriate index. Let us understand with help of an example.
265
The segment tree will be:
Hence the total number of spaces needed for segment tree, given an array is
Size_of_array * 2 – 1.
In our example, the size of array is 4. Hence the total size required for segment tree is “4 *
2 -1 = 7”.
266
Now for any parent, to get to left child use “ 2 * i + 1”
#include <iostream>
using namespace std;
void build_min_tree(int arr[], int* tree_min, int start, int end, int ind)
{
if(start == end)
{
tree_min[ind]=arr[start];
return;
}
int mid = (start+end)/2;
build_min_tree(arr, tree_min, start, mid, 2*ind);
build_min_tree(arr,tree_min, mid+1, end, 2*ind+1);
tree_min[ind] = min(tree_min[2*ind],tree_min[2*ind+1]);
int min_in_range(int l, int r, int index, int start, int end ,int* tree_min)
{
if(end<l || start>r) return INT_MAX; //no overlap case
if(l<=start && r>=end) return tree_min[index]; //total overlap case
int mid = (start+end)/2;
return min(min_in_range(l, r, 2*index, start, mid, tree_min), min_in_range(l, r,
2*index+1, mid+1, end, tree_min));
}
int main()
{
int n;
cout<<"Enter number of elements \n";
cin >> n;
int arr[n];
267
cout<<"Enter "<<n <<"elements\n";
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}
int tree_min[4*n];
build_min_tree(arr, tree_min, 0, n-1, 1);
int l;
int r;
cout << "Enter lower range and higher range to perform min range query:" <<
endl;
cin >> l >> r;
cout << "Minimum Number in range : " << min_in_range(l,r,1,0,n-1,tree_min) <<
endl;
return 0;
}
12.6 Output
268
Tree data structure tutorial 13. Lazy propagation of segment trees with example
In this chapter we shall learn about below topics:
Before we understand what is lazy propagation, we shall understand the need for lazy
propagation.
Consider the array below and the corresponding segment tree for min element range query.
Segment Tree:
269
Now suppose you need to increment all the elements from the range [0, 3] by 2, then you
need to go till the leaf node and then update all the values as shown below:
After the update you need to calculate the smallest element in all the ranges as shown
below:
270
Here we are updating till the leaf node. Consider that you have a large amount of update
query then the performance will take a hit. Hence we are using lazy propagation.
In lazy propagation we take another array of same length and initialize with NULL or
INT_MAX.
When we reach certain index in the segment tree array, we check the value in the lazy tree
array. If the value is NULL, we don’t do any operation. If it has other than NULL value, then
we update all the children from that part of the index.
increment [0, 3] by 2
increment [0, 3] by 1
increment [1, 1] by 2
271
As [0, 5] is a partial overlap for [0, 3], then traverse both left and right.
Now for the left child [0, 3] is a complete overlap for our update query. Now what you need
to do is to update the value at that node and then in the lazy array, update the value to be
incremented to its children as shown below:
272
Point to be noted is that we are not updating till the end of the array. We are just updating
till we reach the total overlap and stop there and then update the lazy array with the value
to be incremented.
Now also we follow the same steps as above. Increment the segment till [0, 3] range by 1
and then add 1 to its children in the lazy array.
To reach [1, 1] we need to traverse [0, 5], [0, 3], [0, 1], [1,1], [2, 3]. This is shown in below
image 52
Now when we reach at the range [0, 1], we check the lazy tree, and see that there is value
that is other than NULL. Hence we need to update the value in the segment tree. And send
the value of the update to its children.
273
Now update the same for the range [2, 3] and send the value to its children.
Now we need to update [1, 1] range. Hence we increment the value of the range [0, 1] in
the segment tree.
274
Note that we are updating [1,1]. Hence we only need to update the children of [0, 1], as [2,
3] is no overlap condition, we don’t need to update it’s children.
275
As [3, 4] is a partial overlap for [2, 3] we go till the child of [2, 3] and update the value from
the lazy propagation tree.
From the above tree we get the min value in the range [3, 4] which is 4.
276
Tree data structure tutorial 14. Fenwick trees and implementation
Problem Statement:
2 + 3 + 1 + 5 = 11.
The simple way to do it by using brute force approach. i.e to add all the elements from the
starting index to ending index.
Yes, take another array where you can store the sum of previous index elements.
For example:
But there is a problem here. What if you update the value at index 2, to add “1” to it?
277
Then you need to add “1” to all the elements after index 2
But if you update at the index ‘0’, then it will take O(n) time to update all the values.
Fenwick tree is based on the fact that all the numbers can be represented by 2^n. Hence the
algorithm will take advantage of this to make queries faster.
Fenwick tree will be useful for 2 operations. These operations we shall see in this chapter
also.
= 40 + 22 + 1
278
= 63
So what we do is, we have these ranges pre computed. So when we get a range to calculate
the sum, we first need to add those pre computed values.
As you can see in the image above, we can infer below 3 points:
So we computed our level 0. Next is level 1, we calculate the same from starting of the gap.
Before doing that, lets mark the index that we have calculated the values for.
While filling the gap, we need to consider the gaps that are continuous.
279
From the image the index [3, 3] is having only 1 gap. Hence we calculate 2^0 = 1.
Again the gap starts from the index [5], it is having continuous 3 gaps. Hence we calculate
2^0, 2^1. We don’t need to calculate 2^2 because it’s length is 4 and our gap is not that
much long. Hence we leave it there.
Now we look at the index [7, 7] as it is only 1 gap, we calculate only 2^0.
Next gap is from Index 9 to 14. Here again we calculate the value starting from 2 ^0.
280
Now again we start from index 11. As it is only 1 gap we write as it is.
Next index is 13, the gap is 2. Hence we do 2^0, 2^1 sum range. It can be shown as below:
Now that we have covered all the index, we can perform sum range query.
Now we want to know for the sum for range 13. We can write as
Sum (13) = range [1, 8] + range [9, 12] + range [13, 13]/
281
We just need to add the highlighted value and we get our result “63”.
Now how does this actually help us? Let me make it easier for you.
If you observe the index of 13 in binary is “1101”. When you flip the last digit “1” to “0”, you
get the next index to be added i.e. “1100”. Now again you flip the last “1” to “0”, you get
“1000” the index next number to add.
In our example:
X = 13 = 00001101
-X = -13 = 11110011
282
X & -X = 00000001
Starting from index 5 add 2. If we are not using Fenwick tree, we need to add 2 to all the
ranges starting from index 5.
Then we shall update all the ranges that are right side to index 5. As we have only one range
[5, 6] we update that.
283
After the index 6, there is no continuous range related to 5. Hence we go one level up and
update all the ranges.
Basically we add the last set bit to know the next index to be updated.
#include <stdio.h>
284
int get_sum(int i)
{
int sum = FWtree[i];
while(i)
{
i -= (i & (-i));
sum += FWtree[i];
}
return sum;
}
int main()
{
int my_array[] = {1, 3, 2, 4, 5 ,8, 6, 5 ,0, 3, 4, 3, 2, 2};
init_fw_tree(my_array, 0, 13);
return 0;
}
Output:
285
The sum of all the numbers in the array is = 48
The new sum after updating 5 th index with value 8 is = 56
286
Graph Data Structure Tutorials:
Graph data structure tutorial 5. Graph Traversal using Stack and Queue
287
Graph data structure tutorial 1. Graph Introduction
In this chapter we shall learn about:
Graph like trees is a non-linear data structure. Like trees, graph is also made of collection of
nodes/vertices and edges. But unlike trees, graph will not have any root node. In fact, you
can start to traverse from any node and move in any direction.
1. All the nodes are connected with each other by using edges
2. There is no root node, hence we can start visiting from any node.
3. There is no hierarchical data, hence we can visit from any node to any node having an
edge between those 2 nodes.
4. There can be multiple ways to reach 2 points.
Graph Definition:
A graph G is an ordered pair of a set of “V” vertices and a set of “E” edges.
G = (V, E)
288
Identify the vertices from the below graph image
Vertices V = { A, B, C, D, E}
An edge can be defined as the path between 2 vertices. Here edges can be of 2 types.
Directed edge and Un-Directed edge. The above image is of un-directed type. In further
chapter we shall study about directed edges.
1. Undirected Graph:
A graph with undirected edges is called as undirected graph. The edges are called as
undirected edges.
2. Directed Graph:
289
A graph with all the directed edges is called as directed graph or di graph.
3. Weighted Graph
If the edges are labelled, then it is called as weighted graph. Both directed and undirected
graph can have a weighted edge.
4. Cyclic Graph
A directed graph with at least one cycle is called as cyclic graph.
5. Acyclic Graph
A directed graph with no cycle is called as acyclic graph
6. Connected Graph
A graph will be called as connected graph, if there exist one path that connects all the
vertices.
290
7. Self-Loop Graph
A graph is called as self-loop graph, if there is only 1 vertex and has a cycle, then it is called
as self-loop graph.
8. Disconnected Graph
A graph will be called as disconnected graph, if there is no path between 2 vertices.
Note:
A graph can have both directed and undirected edges at the same time. But in this series,
we shall learn about the graph that are either directed or undirected.
291
Graph data structure tutorial 2. Graph Representation Adjacency Matrix
In this chapter we shall learn about:
2.1 Introduction
2.2 Understanding of Graph Representation adjacency matrix with an example
2.3 Implementation
2.4 Output
2.1 Introduction:
In this tutorial we shall see how to store a graph with the help of a matrix.
The idea is to take 2D array of size V * V, then mark the index as “1” if there exist an edge
between those 2 vertices.
292
Now we shall choose the edge “A”, we fill “1” for all the nodes it is connected. As the graph
is undirected, if there is a path from A->B, then there is a path between B->A. So adjacency
matrix for vertex “A” is as shown below:
Time taken to find all the nodes that are adjacent to the given node?
If we want to know the adjacent node for the vertex “A”, then we just search the “A” index
and check if the value is 0 or 1.
293
Here to represent the adjacency, we give the weight of the edge. And if there are no
connection, then we give a very large value like infinity.
Here memory consumption is O(V^2). For a very large value of V, the memory consumption
will be very high.
Hence we need to find a more efficient way to represent a graph. We can do it with the help
of Adjacency List.
#include <iostream>
int main()
{
int V = 5; // we create a 5x5 matrix
int i;
int j;
int choice;
294
int adj[V][V];
2.4 Output:
295
2
Adjacency Matrix is
10000
01100
01100
00011
00011
296
Graph data structure tutorial 3. Graph Representation Adjacency List
In this chapter we shall learn about:
3.1 Introduction
3.2 Representation in Linked List
3.3 Now why do we use Linked List to represent Adjacency Lists?
3.4 Implementation of Graph Representation using Adjacency Lists using C++
3.5 Output
3.1 Introduction:
In the previous chapter we have seen representing graph using Adjacency Matrix. The
drawback is that it consumes large amount of space if the number of vertices increases.
Hence in this chapter we shall look at more efficient way of representing of the graph, using
Adjacency Lists.
In this representation, we use Linked List for representing the adjacency. For any particular
vertex, we create a list of all the vertices it is adjacent to as shown below:
Example:
From the above image, we can say that Vertex “A” is adjacent to vertex “C” “E” “B”.
But by using Linked List, addition, deletion of a vertex or edge can be easily done.
Now let us see with an example how to represent graph using adjacency lists.
297
The adjacency matrix will be as shown below:
#include<iostream>
struct AdjList
{
AdjListNode *head; //pointer to head node of list
298
};
struct Graph
{
int V;
AdjList *arr;
};
299
}
while(root!=NULL)
{
cout<<root->data<<" -> ";
root=root->next;
}
cout<<endl;
}
}
int main()
{
//create a new graph
int totalVertices=4;
Graph *graph;
graph = createGraph(totalVertices);
//connect edges
addEdge(graph,0,3);
addEdge(graph,0,1);
addEdge(graph,2,3);
addEdge(graph,1,3);
addEdge(graph,2,3);
printGraph(graph);
}
3.5 Output
1 -> 3 ->
3 -> 0 ->
300
Adjacency list of vertex 2
3 -> 3 ->
301
Graph data structure tutorial 4. Graph Traversal
In the previous chapter we learnt about tree traversal. In this chapter we shall learn about
graph traversal.
As the name suggests, we take a node and follow deep in the node and then stop if we
reach a dead end. Then we backtrack to the starting node and then check if there are other
nodes that are left out.
Now, let’s select a starting node. Let it be “A”. You can select any starting node.
From “A” we ca either go to node “C” or node “B”. We shall go to node “C”. Mark that node
as visited [in green].
302
From “C” we can go to node “D”, Then from node “D” to node “E”.
Now we have reached at the end. Hence we backtrack to the previous node and check if
there are any other nodes that have not been visited. As only node that is unvisited is “B”,
we backtrack till “A”.
303
Now, from “A” we see that node “B” has not been visited . then visit it.
A C D E B
So initially we shall start with node “A”, then traverse to node “B” then to “C” then to “D”.
304
Then backtrack to “C”, now “G” node is unvisited. Visit it.
Now backtrack to node “G” to “C” to “B” to “A”. Then visit “F”.
305
Now again backtrack to “A”, then visit “E”.
A, B, C, D, G, F, E
For example:
306
Here as we have started the traversal from Node “C, we cannot reach “A” and “B”. hence
we restart the traversal from “A” then reach “B”.
C D E A B
307
In previous section we have looked at graph traversal using DFS. In this section we shall look
at graph traversal using BFS.
In Breadth First Search traversal we go level by level. Consider the example below:
308
A C B D E
309
Graph data structure tutorial 5. Graph Traversal using Stack and Queue
In previous chapter we learnt about graph traversal in general. In this chapter we shall learn
how to do graph traversal using Stack and Queue.
As in DFS traversal we take a node and go in depth, till we find that there is no further path.
Then we backtrack to each visited nodes and check if it has any unvisited adjacent nodes. By
doing so, we tend to follow DFS traversal.
So to backtrack, we take the help of stack data structure. As you know in stack is based on
last in first out, it will help us to backtrack one node by another.
For this to work, we shall have a stack and another array to maintain the nodes that have
been visited.
310
Step 1: Let us visit node ‘a’ and insert it into the stack and mark that node as visited. And
print it in output.
Step 2: Let us visit node ‘c’ and insert it into the stack and mark that node as visited, and
print it in output.
Step 3: Let us visit node ‘d’ and insert it into the stack and mark that node as visited, and
print it in output.
311
Step 4: Let us visit node ‘e’ and insert it into the stack and mark that node as visited, and
print it in output.
Step 5: Now we see that node ‘e’ is not having any further nodes to explore, hence with the
help of the stack, we backtrack.
Then we pop node ‘d’, then check if there are any adjacent nodes to it, as the graph is
directed, it don’t have any adjacent nodes.
Now pop node ‘c’, and check if it has any adjacent unvisited node. It don’t have any
Now pop node ‘a’ and check if it has any adjacent unvisited node. It has node ‘b’ as
unvisited node. Visit it and write it in output.
312
Then the output will be
ACDEB
In BFS traversal we do level by level. Hence we use queue data structure to achieve this.
Below are the steps for BFS traversal using queue.
313
In BFS also, we need a queue and an array to hold the visited elements. Initially both will be
empty.
Step 1: we visit node ‘a’ then go to its adjacent nodes and write it in queue and mark them
as visited.
As there are no further adjacent nodes for ‘a’, pop from the queue and write it in output.
Step 2:
Now visit node ‘c’ and check if it has adjacent nodes. It has node ‘d’ as its adjacent node.
Write it in queue and make it as visited. As there is no other adjacent nodes, pop node ‘c’
from queue and write in output.
314
Step 3:
Now visit node ‘b’, check if it has any adjacent node. It has node ‘d’, but it is already visited.
Hence pop from queue and write in O/P
Step 4:
Now visit node ‘d’. Check it has any adjacent node that is not visited. It has node ‘e’, insert in
queue and mark it as visited. Pop ‘d’ from queue.
Since all the nodes has been visited, pop e from queue. Hence we get the solution as below:
315
Note:
DFS:
We us stack to backtrack when we hit a dead end, while backtracking we check if any node
has any unvisited adjacent node and if it is there, we make it as visited.
BFS:
Here we visit a node, we insert that node, and all other adjacent nodes to it into the queue.
Then while pop the element from queue, we check if there is any unvisited adjacent nodes
for the popped out node. By doing so we get to BFS traversal.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
visited[s] = true;
cout<<" "<< s;
316
void BFS(vector <int >adj[],int s,int n)
{
bool visited[n];
memset(visited,0, sizeof(visited));
visited[s] = 1;
queue <int >Q;
Q.push(s);
while(!Q.empty())
{
int v = Q.front();
Q.pop();
cout<<" "<<v;
int v = 5;
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 4, 2);
addEdge(adj, 2, 3);
317
DFS(adj,0, visited);
cout<<endl<<endl;
return 0;
}
Output:
DFS traversal =
01234
BFS traversal =
01423
318
Graph data structure tutorial 6. Bipartite graph
In this tutorial we shall learn about bipartite graph.
Definition:
A graph G(V, E) is called as bipartite graph if all the vertices (V) can be divided into 2 distinct
disjoint non empty sets V1 and V2 such that every edge in the graph connects a vertex in V1
and vertex in V2, so that no edge in graph connects 2 vertices in the same set.
By seeing above graph, we can divide all the vertices into 2 sets as:
S1 = {A, C}
S2 = {B, D}
As you can see that there are 2 distinct non-empty sets and no 2 vertices of the same set are
connected.
319
Here you can see that each vertex from one set is connected by every other vertex in other
set.
Example 2:
The above graph, we can divide al the vertices into 2 sets as:
S1 = {A, D, G}
S2 = {B, C, F, E}
A graph is called complete bipartite graph if all the vertices from set 1 are connected to all
other vertices of from set 2.
320
As above both vertex “a” and vertex “b” from SET 1 are connected to all other vertices of
SET 2.
321
Graph data structure tutorial 7. Graph colouring problem
In general graph colouring or edge colouring problem we need to assign colour to vertices in
such a way that no edge link two vertices with the same colour.
Here graph a is valid. But graph b is invalid because, there is an edge between vertex “b”
and vertex “c” that have the same colour.
Graph colouring algorithms are used in many areas, including scheduling application.
Now coming to our topic of 2 colour graph problem. What is the need to study this
problem now?
In the previous section we learnt about bipartite graph. For a graph to be bipartite it should
be a 2 colour graph. Hence if we can prove that a graph can be coloured by only 2 colours,
then that graph is a bipartite graph.
It’s simple. Choose a starting vertex, and give it a colour say “red”.
Now make all its neighbour have other colour say “green”.
322
And all the neighbouring vertex of the “green” colour vertex, colour it “red”.
The image below shows step by step procedure for 2 colour graph problem.
In the above image, we have coloured the graph using only 2 colours.
So to check if the graph is bipartite, we check if the graph is 2 colourable and also it should
not contain odd cycle.
323
Graph data structure tutorial 8. Isomorphic Graph
Definition:
2 graph G1 and G2 are said to be isomorphic if there exist a match between their vertices
and edges such that their incidence relationship is preserved.
If two edges e1 and e2 have a common vertex V1, the edges are called incidence
relationship.
324
1. They both have same number of edges
2. They both have same number of vertices
3. All the vertices has same degree.
Now that we shave satisfied the properties, let’s check if they are isomorphic.
In the graph G2, if we invert the vertex “b” and “c”, then it will equivalent to graph V1 as
shown below.
G1 (a, b) = G2 (a, c)
G1 (a, d) = G2 (a, d)
G1 (d, c) = G2 (d, b)
G1 (b, c) = G2 (c, b)
325
Example 2: Check if the graph is isomorphic.
Here the vertices are 4, but, edges for graph G1 are 3 and for G2 are 4. Hence the 2 graphs
are not isomorphic.
326
Graph data structure tutorial 9. Euler Graph
A path which starts and ends at same vertex is called as Euler Path. It means, you need to
visit all the edges only one.
Here we started at vertex 1 and traversed all the edges only once and ended at vertex 1
again.
327
Below are the conditions for a graph to be a Euler Graph:
In a graph, if we are able to visit all the edges, but cannot return to the starting vertex is
called as semi Euler graph.
Example
Here we have visited all the edges, but did not return at the starting edge. Hence it is a semi
Euler graph.
All the vertices have even degree, except for 2 vertices, it will have odd degree.
328
Graph data structure tutorial 10. Hamiltonian Graph
In this tutorial we shall learn about Hamiltonian graph.
Definition:
A graph that contains Hamiltonian circuit is called as Hamiltonian graph.
A path that passes through every vertex exactly once is called as Hamiltonian circuit. It
should return to the original starting vertex.
Example:
Hamiltonian Path:
If there is a path that starting from a vertex and visits all the vertices, but cannot return to
the initial vertex. This is called as Hamiltonian path.
Example:
329
If we follow the path a -> b -> c -> d -> e. Here we visited all the vertices only once, but
cannot return to the initial vertex. This is called as Hamiltonian path.
330
Different types of problem solving technique
2. Recursion
4. Backtracking approach
5. Greedy approach
331
Introduction to Brute force approach with example
In this chapter we shall learn about:
Brute force approach can also be called as exhaustive search. Basically brute force means
you go through all the possible solutions.
It is one of the easiest way to solve a problem. But in terms of time and space complexity
will take a hit.
Problem statement:
You are given a string “s” and s pattern “p”, you need to check if the pattern is there in the
string.
S = “prodevelopertutorial”
P = “rial”
332
Here the first character of the string and first character of the pattern is a mismatch. Hence
we move to next character and check again.
If you can see from the above image, the first character is a match in both of the strings,
hence we move to the next character. Here the next character is a mismatch. Hence we shift
the search string to the next character.
Again there is a mismatch. Again we move to next character. We continue this till me find
the pattern or reach end of the string
As you can see above, when there is a mismatch we jump character by character. Hence the
time complexity will be n*m, where “n” is the length of the string “s” and “m” is the length
if the pattern “p” at the worst case.
#include<iostream>
#include<string>
333
for (int i = 0; i <= n - m; i++)
{
int j;
for (j = 0; j < m; j++)
{
if (str[i+j] != pattern[j])
break;
}
if (j == m)
return true;
}
return false;
}
int main()
{
string str = "prodevelopertutrial";
string pattern = "rial";
if(search(str, pattern))
{
cout<<"The substring is present"<<endl;
}
else
{
cout<<"The substring is NOT present"<<endl;
}
return 0;
}
1.4 Output
Sequential search
Knapsack problem
334
We shall study the above problems in later chapter.
For Travelling sales man problem and Knapsack problem, there is no polynomial time
solution. Hence they are classified as NP hard problem. But they can solved by using
backtracking approach, that will increase the efficiency of the algorithm.
For the above sub string search problem, is there a way to increase the efficiency?
KMP algorithm
Rabir Karp Algorithm
Boyer Moore Algorithm.
335
Introduction to Recursion with stack frame and recursion tree
#include<iostream>
int fun(int n)
{
if (n == 1)
return 1; // base case
else
return 1 + fun(n-1);
}
int main()
{
int n = 5;
cout<< "The number of times the function are "<<fun(5)<<endl;
return 0;
}
In the above program, the function “fun()” is a recursive function. “main()” is calling
recursive function indirectly. Then the function “fun()” will call itself directly.
For writing any recursive function, there should be a base case. Base case is used to exit out
of the recursion loop. If base case is not there, it will result in stack overflow and will crash
the program.
336
2.3 Recursion and Stack Frame
From the above program we shall understand how stack frame gets effected when using
recursion function.
So we called the function with n = 3 value. We know that, in C, local c variables are stored in
stack. When you call a function, it’s activation record along with unction parameters are
also stored.
Stack Frame:
int fun(3 )
if (n == 1)
else
return 1 + fun(2);
As we are calling fun (2), we transfer the control from fun (3) to fun (2) as shown above.
Stack Frame:
337
Changes in the fun() function:
int fun( 2 )
if (n == 1)
else
return 1 + fun(1);
Now we call fun (1) from fun (2). Hence we transfer the control from fun (2) to fun (1).
Stack frame:
int fun( 1 )
338
{
if (n == 1)
Now in fun (1) now “n == 1” is true, hence we return 1. Which mean, we are returning 1 to
the calling function from the stack frame. We can see that the calling function is fun (2).
int fun( 2 )
else
return 1 + fun(1);
int fun( 2 )
else
return 1 + 1; // return 2
From the stack frame, we can see that fun (3) is calling fun (2). Hence the fun (3) will
become:
int fun( 3 )
else
return 1 + fun( 2 );
339
}
int fun( 3 )
else
return 1 + 2; // return 3
Now the value “3” will be returned to its calling function i.e main function.
As we saw in previous section, we saw what a recursion is and how the stack frame changes
when a recursive call is made.
Let’s understand the recursion tree by taking an example of printing n^th Fibonacci
number.
340
fib( n )
{
int n <= 1
return n;
else
return fib ( n -1 ) + fib ( n - 2 )
}
and when we call the fib function with n = 5. The stack framer and Fibonacci tree is as
shown below:
341
Right now the compiler is executing fib ( 4 ) all the other are in paused state.
Then fib ( 4 ) will make a call to fib ( 3 ), fib ( 3 ) will make a call to fib ( 2 ), fib (2) will call fib
( 1 )… it can be showed as below
Now fib ( 2 ) is in stack, it will call fib ( 0 ) and fib (0) will be put into stack.
342
Now fib ( 0 ) will return 0 and as fib ( 2 ) has called fib ( 0 ) and fib ( 1 ) the final value for fib
( 2 ) will be 1, and fib ( 2 ) will be popped out of stack. Now the execution will flow to fib ( 3
).
Now fib ( 3 ) already called fib ( 2 ) hence it will call fib ( 1 ) and fib ( 1 ) will be placed into
the stack.
343
Again fib ( 1 ) will call fib ( 0 ) and it can be showed as below:
Now for fib ( 4 ), it already called fib ( 3 ), hence it will call fib ( 2 ), again fib ( 2 )will call fib (
0 ) and fib ( 1 ).
344
Hence fib ( 4 ) value will be “ 2 + 1 = 3”. 3 will be returned to fib ( 5 )
Again fib ( 5 ) will call fib ( 3 ), fib ( 3 ) will call fib ( 2 ), then fib ( 2 ) will call fib ( 1 ). Fib ( 1 )
will return 0.
345
This is the basic of recursion and the changes in the stack frame when you call a recursion
function.
This is an important topic. Because in the next chapter i.e dynamic programming and
backtracking it uses recursion to get the results.
346
Introduction to Dynamic Programming with example
In this chapter we shall learn about below topics:
From the above, the time complexity will be 2^n and it you observe carefully we are
repeating the calculation for the values that are already been calculated.
We are calculating the values for “fib(2)” “fib(1)” “fib(0)” for more than one time.
Next time when we try to calculate the value for already calculated value, we check in our
array if the value is present or not. If present, then we take from the array and use it. Else
we calculate the value and store it in the array for further use.
As we are storing the result for already calculated value, for it ca be used in further in our
problem is called as dynamic programming.
347
There are 2 approaches of dong dynamic programming.
In this approach we take an array to store the values that are previously been calculated.
Step 1: Take an array and initialize with -1. As we are calculating for fib( 5 ), we take 5
element array.
First we calculate for “fib ( 5 )”. The value of fib ( 5 ) is -1, we calculate further, hence make a
recursive call to “fib ( 4 )”
Check the 4thindex of the array, it is -1, make a recursive call for “ fib ( 3 )”
348
As “fib ( 3 )” is also -1, make a recursive call again to “fib ( 2 )”.
As the index is “1” we return 1 and update the array with 1 for index 1.
349
Again “fib ( 2 )” will call “fib ( 0 )”. As “0” will return “0” update the array.
Now we can calculate the value for fib ( 2 ) = fib ( 1 ) + fib ( 0 ) = 1 + 0 = 1, update it the
array.
i.e “fib ( 2)”. But as we have already know the value of fib ( 2 ) form the array, we use that
value to calculate fib ( 3 ).
350
Now we need to make 2ndrecursive call to “fib ( 4 )”.
The 2ndrecursive call to “fib ( 4)” is “fib ( 2 )”. We know the value of fib ( 2), we can calculate
the value for “ fib ( 4)” and update the array.
Now make 2ndrecursive call for fib ( 5 ). The 2ndrecursive call for “fib ( 5)” is “fib ( 3)”. As we
already know the value for fib ( 3), use it and get the final result.
351
Hence as you can see, by using Memonization approach, we have reduced the time
complexity from 2 ^n to O ( n) by using dynamic programming;
And, here we have solved the problem from top to bottom to get the result. This is called as
top down approach. We have stored intermediate result in an array. This is called as
Memonization technique.
#include<iostream>
using namespace std;
int fib(int n)
{
if (array_memo[n] == -1)
{
if (n <= 1)
array_memo[n] = n;
else
array_memo[n] = fib(n - 1) + fib(n - 2);
}
return array_memo[n];
}
int main ()
{
int n = 5;
//initialize array to -1
for(int i = 0; i < 6 ; i++)
array_memo [i] = -1;
352
cout << "Fibonacci number is " << fib(n)<<endl;
return 0;
}
Output
Fibonacci number is 5
Tabular method can be achieved by iterative method instead of recursive method. Below is
the function that calculate Fibonacci in iterative method.
int fib ( n)
{
int arr[5]
arr[0] = 0
arr[1] = 1
if (n <= 1)
return n
return arr[n]
}
In the above program, we have to generate an array, and we shall start filling the array from
lower index to upper index. As first 2 index are prefilled we shall start with
Pass 3:
arr [0] = 0
arr[1] =1
arr [2] = arr [0] + arr [1]
=1+0
arr[2] =1
array:
0, 1, 1, 0, 0, 0
Pass 4:
353
arr [3] = arr [2] + arr [1]
=1+1
arr[2] =2
array:
0, 1, 1, 2, 0, 0
Pass 4:
arr [4] = arr [3] + arr [2]
=2+1
arr[4] =3
array:
0, 1, 1, 2, 3, 0
Pass 5:
arr [5] = arr [4] + arr [3]
=2+3
arr[4] =5
array:
0, 1, 1, 2, 3, 5
Here if you observe carefully, we are filling from lower index to higher index. Hence it is
bottom up approach using tabular method.
#include<iostream>
int fib(int n)
{
int fib_arr[n+1];
fib_arr[0] = 0;
fib_arr[1] = 1;
354
return fib_arr[n];
}
int main ()
{
int n = 5;
cout<<"Fibonacci number is = "<<fib(n)<<endl;
return 0;
}
Output:
Fibonacci number is = 5
355
Introduction to Backtracking Approach with example
Backtracking is a problem solving technique for the problems based on yes/no decision
based problems. Here you are making a decision and if you encounter a result that is not
acceptable because of a wrong decision you made, you will go back to the step where you
made wrong decision and try to make different decision.
A ball will be placed at the starting of the maze; your job is to move the ball such that it will
reach at the end of the maze.
From the above image, we can see that the ball can move left, right, down. By using these 3
operations you need to make the ball reach the end.
Here you will be making series of decision to make the ball reach the end. At some point
you might reach to a dead end, then you backtrack to the point where you can make a
different decision. Hence this is called as backtracking.
The ball will start at tile 1 and has to reach to tile 9 by making series of “yes” “no” based
decision.
1 -> 2 -> 3
356
Then it will go down to “6” and continue the path
As you can see, we made number of decision on how to traverse. Backtracking is based on
brute force approach. You continue till you reach a point where the result is not that you
have expected. Then you traverse back to a point where you have an accepted result and
then take other decision.
357
Introduction to Greedy Technique with example
Greedy method is a simple technique that is easy to understand.
Definition:
In greedy approach, we make decision on the current information available at the present
time without worrying about the effect on the future result.
Consider the graph below, you need to go from A to D with minimum cost.
With greedy method approach, we choose “a” to “b”. Because it is having less cost than “a”
to “c”.
Then we move from “b” to “d”. Hence the total cost for “a” to “d” is “a to b” + “b to d” i.e 2
+ 1 = 3.
But greedy approach will not always give the optimal solution.
358
Now we need to reach from node “a” to “d”. As always we become greedy and choose “a”
to “b” as the cost is “1”. Then we move from “b” to “d”. Hence the total cost will be 7.
Hence in the definition we can say that, we make a decision based on current data
available. Once the choice is made you cannot change it.
Ok, we stump upon an important question. When to choose greedy method to solve a
problem?
For a problem to be solved by greedy approach, the problem should satisfy below 2
Properties:
Let us understand above 2 properties with help of an example. Consider the graph below
and you need to reach from node “a” to “b” at less cost.
For the 1stproperty: We choose the locally optimal sub solution and choose to go from “a”
to “b”. Then we go to “b” to “d”. hence we have locally chosen the optimal solution and has
359
For the 2ndproperty: The sub problem which we choose should be optimal of all the sub
problem.
In this example, from “a” we can go to “b” or “c”. We have chosen to go “a to b”. And again
we have “c to d” or “b to d”. Again we chosen to go “b to d”, which is optimal of the sub
problem. Hence we can solve this problem with help of greedy approach.
Below are some of the examples/ problems that can be solved using greedy approach.
1. Finding shortest path
2. Finding Minimum Spanning Tree [MST]
3. Job sequencing problem
4. Fractional Knapsack problem
We shall see all the above problems in coming chapters.
360
Introduction to Two pointer approach with example code
In this context, two pointers simply mean there will be 2 variables that will be pointing to
two different index of an array.
Let us understand this approach with help of an example and understand how it will
increase the efficiency of the solution.
Problem statement:
You are given an array in ascending order and a key element. You need to find 2 elements
that add up to the key.
Key = 14
First we shall solve it with brute force approach, later we will see two pointer solution.
1+4=5
1+6=7
1+8=9
1 + 10 = 11
1 + 12 = 13
361
Here we did not find the required pair, we move to the next element from the outer loop.
Them we add to all the elements in the inner loop one by one.
4 + 6 = 10
4 + 8 = 12
4 + 10 = 14
Here by using brute force approach, at the worst case we will have O(n^2). Which takes lot
of time for large number of values.
Now we got 2 elements from the 2 pointers. Now we add them and check if the sum value
is equal to the key.
Pass 1:
Here the sum is 13. As the sum is less than key value, increase L index.
362
Pass 2:
Here the sum is 16. As the sum is greater than the key, decrease R index.
Pass 3:
As the sum value is 14, that is equal to the key element. We exit the loop.
As you can see, it can be done using only one loop, hence at worst case, it can be done in
O(n) time.
363
}
else if(arr[left] + arr[right] > key)
{
right--;
}
else
{
left++;
}
}
int main()
{
vector<int> arr;
arr.push_back(2);
arr.push_back(3);
arr.push_back(6);
arr.push_back(7);
arr.push_back(8);
arr.push_back(9);
brute_force_approach(arr, key);
two_pointers_approach(arr, key);
return 0;
}
Output:
Elements Found
Elements Found
364
Minimum Spanning Tree:
365
Minimum Spanning Tree tutorial 1. Introduction to minimum spanning tree
In this chapter we shall learn about below topics:
First thing to understand is that this topic will come under Graphs not trees.
Before solving questions related to Minimum Spanning Tree [MST], we shall take a look on
what are MST?
Given a connected undirected graph, a spanning tree of that graph is a sub graph that has all
the vertices and also a tree.
Means, a spanning tree should be connected [connected to all the vertices], acyclic [should
not have any cycle] and should have all the vertices.
Below are the different number of spanning tree for that graph.
366
Note:
If there are “n” vertices, then a spanning tree should have “n-1” edges. In the above image,
we have 4 vertices, hence our spanning tree has “4 -1 = 3” edges.
Now you are a sales person, and let us consider each vertices as cities, and you need to visit
all the places with minimum amount possible.
We use MST in
1. Network Design
367
2. Maps
3. Face Verification
In the next MST problems, we shall look at more complex problems with cycle and how to
solve them using Prims and Kruskal’s algorithm.
368
Minimum Spanning Tree tutorial 2: Introduction to Kruskal’s algorithm
In this chapter we shall learn about below topics:
Why do we call it as greedy? Because, as you will see further, we choose the shortest
distance first without considering the fact what there might be more optimized path. Hence,
we find another path with shortest value, we update the result with that value.
The working of Kruskal’s algorithm is very simple and can be understood by 3 simple steps
as given below:
Step 2: a. Start from the edge with smallest weight and connect them together.
1. Before connecting, check if it forms a cycle if it forms a cycle then reject the edge and
go for the net smallest weighted edge.
Step 3: Check if all the vertices are connected. If they are not connected, then repeat step 2
till all the vertices are connected.
Once all the tree vertices are connected to an edge, we get MST.
Note: As you see in Prims algorithm that starts by choosing a root vertex, in Kruskal’s
algorithm we start connecting 2 vertices by choosing least weighted edges.
369
2.4 Understanding Kruskal’s algorithm with the help of an example
370
Next connect nodes “D” and “E”, as they are next minimum
371
Next connect “B” and “A”
Next connect “A” and F”. Thus connecting all the nodes and forming a MST.
372
2.5 Implementation of Kruskal’s algorithm.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
struct edge
{
int u, v, w;
};
int parents[MAX+5];
vector <E> graph; // Store the inputted graph (u, v, w).
vector <E> selected_edges; // Store the edges which is selected for the MST from given
graph.
373
return l.w < r.w;
}
return;
}
make_set(nodes);
edgeCounter++;
if( edgeCounter == nodes-1 )
374
break;
}
return totalCost;
}
int main()
{
E getEdge;
int nodes, edges;
int u, v, w;
cout<<"Edge "<< i<<endl;
cin >> u >> v >> w;
getEdge.u = u;
getEdge.v = v;
getEdge.w = w;
graph.push_back(getEdge);
}
375
cout<<"\nTotal Costs: "<< totalCost<<endl;
getchar();
return 0;
}
Kruskal’s algorithm should be used in typical situations (sparse graphs) because it uses
simpler data structures.
376
Minimum Spanning Tree tutorial 3. Introduction to Prim’s algorithm
In this chapter we shall learn about below topics:
In this tutorial we shall learn about Prim’s algorithm is used to find MST. This is a greedy
based approach.
3.3 The working of Prim’s algorithm is very simple and can be understood by below steps:
377
Initially the graph will be empty with no edges connected
Now start from vertex ‘a’, connect ‘a’ and ‘c’ as it has less weight when compared to ‘a’ and
‘b’
378
Now go to node ‘c’, and connect node ‘c’ and ‘b’
Now connect ‘c’ and ‘e’ as they are having next lowest weight.
379
Now connect ‘f’ and ‘d’. Hence we got our minimum spanning tree.
#include <iostream>
#include<vector>
#include<queue>
380
void PrimsMST(vector<pair<int, int> > adj[],int src,int v)
{
priority_queue<pair<int,int> , vector<pair<int,int> > ,greater<pair<int,int> > >pq;
pq.push(make_pair(0,src));
while(!pq.empty())
{
int u = pq.top().second;
pq.pop();
inMST[u] = true;
for(int i=1;i<v;i++)
printf("%d - %d\n",parent[i],i);
}
vector<pair<int,int> >adj[v];
addEdge(adj,0, 1, 2);
381
addEdge(adj,0, 7, 4);
addEdge(adj,1, 2, 4);
addEdge(adj,1, 7, 9);
addEdge(adj,2, 3, 6);
addEdge(adj,2, 8, 2);
addEdge(adj,2, 5, 4);
addEdge(adj,3, 4, 5);
addEdge(adj,3, 5, 12);
addEdge(adj,4, 5, 8);
addEdge(adj,5, 6, 2);
addEdge(adj,6, 7, 1);
addEdge(adj,6, 8, 6);
addEdge(adj,7, 8, 5);
PrimsMST(adj,0,v);
return 0;
}
3.6 Output:
0-1
1-2
2-3
3-4
2-5
5-6
6-7
2-8
Prim’s algorithm should be used for a really dense graph with many more edges than
vertices.
In Kruskal algorithm, we first sort out all the edges according to their weights. Then we start
connecting the edges starting from lower weight to higher weight.
In prims algorithm, we start from any node, then we check the adjacent nodes weight. Then
we start connecting with the edges with least weight.
382
Find shortest path algorithm
383
Finding shortest path algorithm tutorial 1. Introduction to Bellman–Ford algorithm
In this chapter we shall learn about below topics:
Bellman Ford algorithm us used to find shortest path from source to destination. It can be
solved through Dynamic Programming approach.
A simple example can be thought as travelling from city A to city B. There are multiple
routs, you need to find the route that is cost effective.
With the help of Bellman Ford algorithm, we can find the shortest path from one
node/vertex to all other nodes/vertices.
1.2 Below are the conditions to be satisfied for Bellman Ford algorithm to work:
Dijkstra algorithm will not work for a graph for –ve weight. But Bellman ford algorithm will
work for –ve weight.
The basic working of the algorithm is that we relax each edge for [number of vertices -1]
times.
1.3 Below are the steps to be followed for bellman ford algorithm.
1. Choose the source vertex and make the weights of all the vertices as Infinity.
2. The cost of the source will be zero, because it won’t cost anything from source vertex
to itself.
3. For each edge try to relax the edge for |v -1| times
4. Repeat step 3 till al the edges are released.
384
1.4 What is relaxation in Bellman Ford algorithm?
Relaxation is a concept where we try to find the optimal distance by continuously shorting
the calculated distance between the vertices with the value that we already know.
then
1. Note: Once you relax all the edges for (n-1) times, then if you relax for the nth time,
the value should remain same. If it changes, then the solution is not possible, then
probably the graph has a cycle with negative total weight.
Consider “a” the initial nod, and make the distance from source “a” to all other vertices as
infinity as shown in below image.
385
Now write down all the edges in the graph in any order.
[a, b], [a, f], [b, c] , [f, e] , [c, d] , [e, d] , [e, g] , [g, c]
then
edge.cost = 2
distance(edge.to) = INF
386
[a, f]= distance_of(edge.from) = 0
edge.cost = 3
distance(edge.to) = INF
edge.cost = 4
distance(edge.to) = INF
387
[f, e]= distance_of(edge.from) = 3
edge.cost = -2
distance(edge.to) = INF
edge.cost = 6
distance(edge.to) = INF
388
[e, d]= distance_of(edge.from) = 1
edge.cost = 2
distance(edge.to) = 12
edge.cost = -1
distance(edge.to) = INF
389
[g, c]= distance_of(edge.from) = 0
edge.cost = 3
distance(edge.to) = 6
390
Iteration 2:
In the second iteration, there is no changes in the distance matrix. Hence we stop at second
iteration.
#include <iostream>
using namespace std;
struct Edge
{
int source, destination, weight;
};
struct Graph
{
int V, E;
struct Edge* edge;
};
391
struct Graph* createGraph(int V, int E)
{
struct Graph* graph =
(struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;
graph->edge =
(struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
return graph;
}
void printArr(int distance[], int n)
{
cout<<"Vertex distance from Source"<<endl;
for (int i = 0; i < n; ++i)
cout<<i<<" "<<distance[i]<<endl;
}
392
printArr(distance, V);
return;
}
int main()
{
int V,E;
cout<<"Enter no.of vertices and edges"<<endl;
cin>>V>>E;
struct Graph* graph = createGraph(V, E);
int a[E][3];
cout<<"enter source,destination and weight for each edge"<<endl;
for(int i=0;i<E;i++)
{
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
for(int i=0;i<E;i++)
{
graph->edge[i].source=a[i][0];
graph->edge[i].destination=a[i][1];
graph->edge[i].weight=a[i][2];
}
BellmanFord(graph, 0);
return 0;
}
393
Finding shortest path algorithm tutorial 2. Introduction to Dijkstra’s Algorithm
In this chapter we shall learn about below topics:
In this tutorial we shall learn about Dijkstra’s algorithm. It is used to get single source
shortest path algorithm.
You are given a weighted graph and you are given a source. You need to find shortest path
from source vertex to every other vertex in the graph.
Example:
So to find the shortest path between “A” and “C”, you can reach from “A” to “C” by:
A -> E -> C = 4 + 3 = 7
A -> B -> C = 2 + 4 = 6
394
Hence the shortest path is A -> B -> C.
So to solve this, we can generate all the possible paths from the source vertex to every
other vertex. Find the weight of all the paths, compare those weights and find min of all
those weights. This can be optimized using Dijkstra’s algorithm.
Step 3: From the starting vertex, visit all its adjacent/ neighbouring vertices and write their
cost/value.
Step 4: Now that we have finished visiting all the adjacent vertices, we make the source
vertex as visited.
Step 5: Choose another vertex, such that, the distance from source vertex is minimum.
Step 6: Now write down the cost for reaching its adjacent nodes form the starting node,
such that the distance should be minimum.
The process of choosing the length of the new path form source vertex to destination vertex
is lesser than the current value, then update with the shortest value. This process is called
as Relaxation.
395
Now, what is the cost from “a” to “b”? It is 5.
Hence we will use this path from “a” to “b” through “c”. Because the cost is less. This is
called as Relaxation.
2.6 Now let’s understand this algorithm with the help of an example.
We shall select node “a” as starting node, we shall make all the nodes from node “a” to all
other nodes as infinity and distance form “a” to “a” is zero.
396
From node “a” check the adjacent nodes, i.e “b” and “c”, write down the cost in place of
Infinity as they are less.
Now make node “a” as visited as all its adjacent nodes are visited.
397
Now we shall relax all the nodes adjacent to node “b”. Only node “d” is adjacent to node
“b”. Hence total cost from “a” to “d” is
▪ a -> b + b -> d
▪ 2+4=6
As 6 is less than INF, update the cost and make node “b” as visited.
Now we choose node “c” as the cost is less when compared to node “d”.
Now try to relax all the nodes that are adjacent to node “c”. Node “d” and node “e” are
adjacent.
▪ a -> c + c-> d
▪ 3+1
▪ 4
▪ a->c + c->e
▪ 3+8
▪ 11
Now make node “c” as visited.
398
Now we choose node “d” as the cost is less than other 2 nodes.
399
Now the cost is same for node “e” and node “f”. Choose any of the node.
From the above steps we can use the below formula to calculate the code of the node.
400
Then if (distance(u) + cost of path (u, v) < distance_at (v))
then
#include <iostream>
#include <climits>
return min_index;
}
distance[source] = 0;
401
int u = minDistance(distance, ShortestPathTree);
ShortestPathTree[u] = true;
int main()
{
int graph[numberVertex][numberVertex] = {{0, 14, 0, 7, 0, 0, 0, 8, 0, 10},
{14, 0, 8, 0, 0, 0, 0, 11, 0, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2, 0},
{7, 0, 7, 0, 9, 12, 0, 0, 0, 5},
{0, 0, 0, 9, 0, 0, 0, 0, 0, 0},
{0, 0, 4, 0, 0, 0, 2, 0, 0, 11},
{0, 0, 0, 12, 0, 2, 0, 1, 6, 15},
{8, 11, 0, 0, 0, 0, 1, 0, 7, 0},
{0, 0, 2, 0, 0, 0, 6, 7, 0, 0},
{10, 0, 0, 5, 0, 11, 15, 0, 0, 0}};
dijkstra(graph, 0);
return 0;
}
402
Finding shortest path algorithm tutorial 3: Introduction to Floyd Warshalls algorithm
In this chapter we shall learn about below topics:
In this tutorial we shall learn about Floyd warshalls algorithm. This algorithm is used to find
shortest path from all the vertices to every other vertex. This is the 3rdtype to find shortest
path between source node to destination node.
Before going to study Floyd warshalls algorithm, let’s review previous 2 algorithms.
1. Dijkstra’s algorithm: This algorithm is used when we need to find shortest path from
one node to all the other nodes/vertices.
2. Bellman Ford Algorithm: This algorithm is used to find shortest path from one node to
all the other nodes, -ve edges are allowed.
3. Floyd Warshalls algorithm: This algorithm is used to find all the shortest path from all
the vertex to every other vertex. Here also –ve valued edges are allowed.
3.2 Let us understand the working of Floyd Warshalls algorithm with help of an example.
As said earlier, the algorithm uses dynamic programming to arrive at the solution. So DP
approach as we saw in earlier chapter, uses memorization technique and divide the
problem into simple sub problems and solve those sub problems to arrive at the solution.
403
From the above graph, calculate the distance matrix.
While constructing a distance matrix, if there is a direct edge between 2 nodes then write
the value. If there is no direct path then make it as Infinity.
As you can see from the above matrix, the diagonal value is always zero. This is because the
cost of source to destination form the same node is zero.
As there are 4 vertices, we need to create 4 matric table. One for each node. Hence at the
end we get the shortest path from any vertex to any other vertex.
As we are using DP approach, we shall take help of previously generated matrix and
calculate the values based on that.
Now let’s write D1 matrix. For D1 matrix, we take 1strow and 1stcolumn from D0 matrix.
Initial D1 matrix is as below:
404
Now we dill the remaining empty cells. To fill that we use below 2 steps:
1. Check if there is a direct path from source to destination vertex. If there is, make a
note of it.
2. Check if there is a path via the node that we are currently in use. If there is a path,
make a note of the total distance via the current node.
Then take the min value of above 2 values and fill in the matrix.
For our current matrix D1, we must need to fill [b, c] and [b, d]. Here we shall take D0 matrix
as reference and fill D1 matrix.
1. [b, c] => Check if there is a direct path from D0 matrix. No there is not. Now check if
there is a path including “a” i.e “b -> a, a -> c”.
There is and the cost is “ 7 -1 = 6”. This is less than INF.
2. [b, d] = Check if there is a direct path from “b” to “d”. There is a path and the value is
2.
Check if there is a path via “a”. i.e “b -> a, a -> d”.
▪ 7 + INF = INF.
As INF is greater than 2. We choose the min element, i.e 2.
405
Similarly, we do it for [c, b] and [c, d].
1. [c to b]
Direct path value is = 3
▪ INF + 4 = Inf
Hence update 3.
2. [c to d]
Direct path value is INF.
▪ INF + INF
▪ INF
Hence INF. Below are the updated values:
406
1. [d, b]
Direct path value is INF
▪ INF + 4
▪ INF
Update INF
2. [d, c]
Direct path value = 1
▪ INF -1
▪ INF
Hence Min(1, INF). Update 1.
Now from the above steps we can derive the formula to find out the min cost.
407
Now with the help of D1 matrix we construct D2 matrix.
Now we shall take 2nd row and 2nd column from D1 matrix and copy into D2 matrix as below:
Similarly, like we did in D1 matrix, we take the min value of a direct path or the via path
from “b”, and choose the min value. Here we shall take help of D1 matrix for reference.
1. [a, c]
Direct path value = -1
▪ 4+6
▪ 10
As min is -1, choose -1.
2. [a, d]
Direct path value = INF
▪ 4+2
▪ 6
Min[INF, 6] = 6
3. [c, a]
Direct path = INF
408
Via “b” path => “c->b” + “b -> a”
▪ 3+7
▪ 10
min[INF, 10] = 10
4. [c, d]
Direct path = INF
▪ 3+2
▪ 5
min[INF, 5] = 5
5. [d, a]
Direct path = INF
▪ INF + 7
▪ INF
6. [d, c]
Direct path = 1
▪ INF + 6
▪ INF
min(INF, 1) = 1
409
Now we shall construct “D3” matrix. Making row 3 and column 3 as constant by taking value
from D2 matrix. The resultant matrix will be as below:
Again we calculate like above matrix. Now the via element will be “c”.
410
4. [b, d] => Direct path = 2,
▪ Via “c” path => “b->c” + “c->d”
▪ 6 + 5 = 11
min (11, 2) = 2
Similarly, we shall construct “D4” matrix. Initially we shall copy 4throw and 4thcolumn from
“D3” matrix, and will look as below:
411
We shall calculate like above, the via element will be “d”.
412
6. [c, b] => Direct path = 3,
▪ Via “d” path => “c->d” + “d->b”
▪ 5+4=9
min (3, 9) = 3
Finally we have completed calculating all the 4 matrices. The matrix “D4” will be the final
matrix as below:
The above matrix will give the shortest path from any node to any other vertices.
#include<stdio.h>
#define V 4
#define INF 99999
413
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
printSolution(dist);
}
int main()
{
int graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
floydWarshall(graph);
return 0;
}
414
String matching algorithms
String matching algorithms tutorial 1. Knuth Morris Pratt String matching algorithm
415
String matching algorithms tutorial 1. Knuth Morris Pratt String matching algorithm
Problem Statement: You are given a string “s” and a pattern ‘p’. You need to find if the
pattern is present in the string “s”.
Usually we can solve this by brute force approach. i.e comparing one letter after another, till
we find the sub pattern or we reach end of the string.
The above approach is not efficient. Hence we choose an efficient way to solve this
problem.
There are total of 3 pattern matching algorithms. KMP is the first algorithm in them.
416
By some mechanism [we shall look at it next] we create a partial match table. This table will
help us to skip the number of characters when there is a mismatch. Thus eliminating,
checking of all the characters one by one.
Proper Prefix:
It is combination of all the characters except the last character. Prefix will be taken from left
to right order.
For example:
AB
ABC
Proper Suffix:
It is the combination of all the characters except the first character. Suffix will be taken from
right to left order.
For example:
417
For the string “ABCD”
CD
BCD
Similarly, we cannot take “A” making it “ABCD”, essentially making it as original string.
Now that we have understood what is proper prefix and proper suffix, we shall build a
Partial Match Table [PMT].
PMT will be created for the “pattern” not for the “string”.
418
Now let’s fill a[1], for a[1] we concentrate on “ab”.
Here proper prefix = a, proper suffix = b. As there are no matching characters, a[1] = 0.
Here proper prefix = a, proper suffix = a. As there is 1 match, length is 1 characters, a[2] = 1
Here proper prefix = a, ab, aba, proper suffix = b, ab, bab. As there is 1 match, and the
length is 2 characters, a[3] = 2.
419
Now let’s fill a[4], for a[4] we concentrate on “ababa”.
Here proper prefix = a, ab, aba, abab proper suffix = b, ba, aba, baba. As there is 1 match,
and the length is 3 characters, a[4] = 3.
Here proper prefix = a, ab, aba, abab, ababa proper suffix = b, ab, bab, abab, babab. As
there is 1 match, and the length is 4 characters, a[5] = 4.
i = string [str[0]]
420
j = pattern[0]
String = ababcacabababacad
Here if you observe, we are starting the index of string from 1 and also pattern index is 1.
421
It is a match. Hence increment “i” and “j”.
422
Now we shall look at PMT[5], it is 4. Hence move j to 4th location again there is a mismatch.
Now again see PMT at index 4, at index 4, the value is 2. Hence move “j” to 2 index, again
there is a mismatch.
423
Again str[6] matches with pattern[1]
424
Now check again:
Str[8] == pattern[1]
Str[9] == pattern[2]
Str[10] == pattern[3]
Str[11] == pattern[4]
Str[12] == pattern[5]
Str[13] == pattern[6]
425
Implementation of KMP algorithm:
#include <iostream>
#include <string>
partialMatchTable(p, pi);
int i = 0;
int q = 0;
426
while (i < n)
{
if (q == -1)
{
++i;
q = 0;
}
else if (t[i] == p[q])
{
++i;
++q;
if (q == m)
return true;
}
else
q = pi[q];
}
return false;
}
int main()
{
string target = "abac";
string pattern = "abababajdcdjabac";
if ( KMP(pattern, target))
cout << "\n Target found in pattern";
else
427
String matching algorithms tutorial 2: Introduction to Rabin Karp algorithm
In this tutorial we shall understand how Rabin Karp algorithm will work. This is the 2ndkind
of algorithm we study in pattern matching algorithm set.
Rabin karp algorithm uses a hash function and brute force approach to check if a pattern is
present inside a string.
1. Get the hash of the pattern. Suppose the length of the pattern is ‘n’.
2. Get the hash of the whole string, by dividing the string in to “n” characters. And get
the hash of those individual sub strings.
3. Check if any hash value from substring matches our pattern hash.
1. If it matches, do a brute force check and check if all characters ae same as
pattern.
2. If it did not match, then calculate the hash for the next “n” pattern.
Now what we do is, we calculate the hash value of the string for the size that is equal to our
pattern.
As out pattern is “abc”, the length is 3. Hence for our string “abdcabcde” we calculate the
hash as:
hash(abd) => u
hash(bdc) => v
hash(dca) => w
hash(abc) => x
hash(bcd) => y
428
hash(cde) => x
Hash(abc) = x.
Now that we have calculated hash for the string and for pattern, we shall if there is any hash
matches our pattern hash.
Yes, there is a match. When there is a match, we shall do brute force search of the sub-
string and pattern. Then one of below 2 things can happen:
1. If all the characters in the string are same, then it is called as valid hit.
2. If the character are not same, it is called as spurious hit. Because the hash value
matches, but strings did not match.
In our example, the hash value for our pattern is ‘x’.In the hashes calculated, we have 2
substrings where the hash value is ‘x’.
hash(abc) = x
hash(cde) = x.
To avoid these kind of situations, it is recommended to have the hash key of larger value.
429
Now we shall see on how to actually solve by using a hash function and followed by rolling
hash function.
Pattern p = abc
Let our prime number be 3. Note that the prime number can be random. Larger the prime
number, less chances of getting same output from hash function.
a -> 1
b -> 2
c -> 3
d -> 4
z -> 26
430
So for our pattern abc, hash will be calculated as below:
▪
1 + 2*3 + 3*3*3
▪
1 + 6 + 27
▪
34
The output will be 34. New we shall calculate hash for our string and try to match with out
pattern.
▪
1 + 6 + 36
▪
43
Now for the string “bdc” => 2 + 4*3 +3*9
▪ 2 + 12 + 27
▪ 41
In the above 2 steps, we are actually rolling over character by character, at any point
we would have already calculated value for 2 characters.
i.e
abd=> bdc
As we would have calculated the hash value of “bd” already, there is no need to calculate
again. Here we need to calculate only for the new character i.e “c”.
= x/prime_number
431
i.e for “abd” we have 43.
▪ 43 – value of (a)
▪ 43 -1 = 42
▪ 42/3 = 14
▪ 14 + 3*9 = 41
The value is same as we calculated earlier individually. This method is called as rolling hash
method.
▪ 41 – value of (b)
▪ 41 -2 = 39
▪ 39/3 = 13
▪ 13 + 1*9 = 22
▪ 22 – value of (d)
▪ 22 – 4 = 18
▪ 18/3 = 6
▪ 6 + 2*9 = 24
▪ 24 – value of (c)
▪ 24 – 3 = 21
▪ 21/3 = 7
▪ 7 + 3*9 = 34
▪ 34 – value of (a)
▪ 34 – 1 = 33
▪ 33/3 = 11
▪ 11 + 4*9 = 47
432
Now we have calculated all the hash value for the string, we now shall compare with the
pattern hash.
When we find a match, we check if all the characters are same. If same we got out search
pattern.
If the hash value is same but strings are different, we conclude that it is a spurious hit and
check if there exist another hash value that is same as our pattern hash.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
433
printf("Rabin-Karp algorithm - Pattern matching\n");
printf("Text: ");
text = read_text(&n);
printf("Pattern: ");
pattern = read_text(&m);
return 0;
}
434
String matching algorithms tutorial 3: Introduction to Boyer Moore algorithm
Introduction:
Boyer Moore algorithm is used for pattern searching inside a string. This is the 3rdalgorithm
in this pattern search series.
This algorithm is very easy to understand. You need to remember below 3 points only.
1. Given a string ‘s’ and pattern ‘p’ we start searching from right most element.
2. When there is a mismatch occurred, one of below 2 rules to be followed:
3. If the mismatch character is not in the pattern p, then we skip the whole word in the
string s.
4. If the mismatched character is present in pattern ‘p’, then we skip till the character in
pattern ‘p’ matches a character in string ‘s’.
Don’t worry if you are not able to relate or visualize. We shall understand with help of an
example.
If there is mismatch and the character ‘d; from the string ‘s’ is not present in the pattern ‘p’,
we shall skip till ‘d’. Hence in the next pass will look as below
Again there is a mismatch. But the letter ‘l’ from the string is present in the pattern ‘p’.
Hence we skip till the letter ‘l’ from the string. Hence in the next pass will look like below:
435
Now again from right most, check ‘e’ from the pattern ‘p’ and string ‘s’. It is a match.
Similarly we do it for ‘p’ ‘o’ ‘l’ all are match, Hence we got our result, and the substring is
present in string s.
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
436
int j = m - 1;
if (j < 0)
{
cout << "pattern occurs at shift = " << s << endl;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
}
/* Driver code */
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
437
Knapsack Problem:
1. Fractional knapsack
2. Knapsack
438
Knapsack Problem tutorial 1: Fractional knapsack tutorial
In this chapter we shall learn about below topics:
1.1 Introduction:
There are 2 variants of Knapsack Problem
1. General Knapsack problem / Fractional Knapsack problem: Here the items can be
divided. This problem can be solved by greedy method.
2. 0/1 knapsack problem: Where the items cannot be divided. Either you take the whole
item[1] or dint take the item [0]. Hence 0/1. This can be solved by dynamic
programming approach.
In this tutorial we shall look at first type of knapsack problem with greedy approach.
This problem is also called as Fractional Knapsack problem. Because we are allowed to
divide the items to get maximum profit.
Problem Statement: You are given with ‘n’ objects with their weights and profit. You are
also given a bag or knapsack of certain size.
Your objective is to fill that knapsack with maximum profit.
According to the objective, you need to fill the knapsack with the weight of 15 or less with
maximum profit.
439
We shall solve this problem with help of greedy approach.
Note: This problem can also be solved with the help of Dynamic Programming. But in this
tutorial we shall learn about greedy approach only.
2.1 To solve this problem with the help of greedy approach, it can be solved in 3 different
ways.
1stMethod:
Select the item with maximum profit and fill the bag till weight is 15.
2ndMethod:
Select the items with minimum weight, so that we can choose more items there by
increasing the profit.
3rdMethod:
In this method we divide profit with weight, thereby giving us the profit for 1 unit.
For example, for the item ‘3’, the profit is 15 and weight is 5. Now we calculate the profit for
1kg. We can do it by 15/5 =3.
Like this we calculate the profit per unit for all the items. Then we select the items based on
it.
440
Now let’s select the items, where we get max profit for min weight.
Note: While choosing the max profit for min weight, you need to keep in mind about the
total weight present for a particular object. For example, for 5thobject, it has weight “1” and
profit “8”, it can be used only once because the weight is 1.
As the weight of object is 5 is 1, we have used it. Hence we are done with this object. Next
height profit is 5, we get:
Now we are done with object 1, as weight is 1. Next we have “3.3” with max profit. Hence
we get:
441
Next we have “3”. For profit “3” we have object 3 and object 6. We select object 3 we get:
#include <utility>
#include <iostream>
#include <algorithm>
442
//first is profit second is weight
typedef std::pair<double, double> item;
//return if first item has greater value by weight ratio than the
bool comp_item(item& a, item& b)
{
return a.first/a.second > b.first/b.second;
}
return profit;
}
int main(void)
{
using namespace std;
int n;
item items[100];
double capacity;
443
cin>>capacity;
return 0;
}
1.5 Output
444
Knapsack Problem tutorial 2: 0/1 knapsack problem tutorial with implementation
In this chapter we shall learn about below topics:
In the previous chapter we have solved fractional knapsack problem. In this chapter we shall
solve 0/1 knapsack problem.
Problem Statement:
You are given ‘n’ number of object with their weights and profits.
You are given a bag with max capacity it can hold. Objective here is to fill the bag/knapsack
so that you get max profit.
As this is 0/1 knapsack problem, you can either take the whole object or don’t take the
object at all.
We can solve this problem with help of Dynamic Programming. We cannot solve it with help
of greedy approach.
Before we solve using DP, we shall see how to solve it with help of brute force approach.
In brute force approach, we take an array of size ‘n’, then mark the objects as 1, if we select
it.
For example:
[0, 0, 0, 0]
445
If we user the object 1 and 4, we make them as 1 and calculate the profit.
Similarly, we do all the combinations and check the profit whose weight is less than or equal
to 8. Then select the max profit.
In the above table, we can see that, in the row we have taken individual weights. In the
column, we have taken the weights of item in increasing order [ascending].
In the DP table we fill with the profit value for the selected item.
So, when the total weight is 0, the profit will also be 0. So we shall fill our table as below:
Now, we have chosen an item with weight 2. So till weight 2, the profit will be 0. And after
weight 2, the profit will be ‘4’. Because ‘4’ is the profit for 2.
As we have only 1 item with weight 2, the profit for all the items will be 4.
446
Now we have weights [2, 3]. So till weight 2, we copy the values from above table.
Now when we arrive at weight 3, we have 2 choices. Either choose weight 2 with profit 4 or
weight 3 with profit 4. As both of the profits are same, we can either choose object with
weight 2 or object with weight 3.
But at weight 5, we can choose both objects with weight 2 and object with weight 3. So the
total profit will be 8. It will be continued till weight 7.
From the above table, can we make out a formula to fill the values in the table?
447
max [ [i-1, j], [value_at_i + [i-1, j-weight] ] ]
#include <iostream>
return DP[n][knapsack_size];
}
int main()
{
int object[] = {2, 6, 7, 3};
int weight[] = {4, 3, 2, 4};
int knapsack_size = 8;
int n = sizeof(weight) / sizeof(weight[0]);
cout << "The solution for knapsack 0/1 is = "<< knapSack(knapsack_size, weight, object,
n)<<endl;
return 0;
}
448
2.4 Output
449
Additional Problems:
2. Tower of Hanoi
3. Sieve of Eratosthenes
4. Kadane Algorithm
450
Introduction to P, NP, NP hard, NP Complete
In this tutorial we shall learn about what is P, NP, NP hard, NP Complete problems.
This is a complex topic. I have tried my best to make you understand in a easy way.
Any algorithm is said to take Constant time, if we are able to get the value by doing single
operation irrespective of input size. It is written as O(1).
For example:
1. Accessing element in an array will always take a constant time irrespective of input
size.
2. If the array is sorted in ascending order, getting the min element is always done in
constant time.
Linear time: Any algorithm is said to take linear time if the time complexity is O(n). It means,
the time consumed will be increased as input size increases.
Example;
1. Accessing min element in an unsorted array. If the min element is at the end of the
array, it will take O(n) time. And the time will increase as the input size is increased.
Ideally, linear time is a polynomial time where K = 1. Below are some of the algorithms that
can be solved in polynomial time.
451
Insertion Sort O(n^2)
Below are some of the algorithms that can be solved in exponential time:
The above problem cannot be solved in deterministic time. Hence we try to solve it through
non deterministic time.
The algorithms that shows different behaviour for same input, are called as non-
deterministic algorithms.
All deterministic algorithm can be solved in polynomial time, but non deterministic
algorithms cannot be solved in polynomial time.
Before going to our main topic, let’s understand one more concept.
452
So P is a class of decision based problems that can be solved efficiently.
NP Problem Class:
For NP class problems, we don’t know how to solve them efficiently. But we try to verify the
answer efficiently thus having a proof.
So NP is a class of decision based problems, that can be verified efficiently. It means that
there is an algorithm present that can verify the output of the problem.
So most of the time, we hear that P = NP, if and only if, the problem in class P are efficiently
verifiable.
If you have a problem “M”, it can be reduced to another problem “N” and that “N” problem
can be efficiently solved. These kind of problems are called as reduction based problems.
NP hard Problem:
A problem is called as NP hard, if all the problems in NP can be reduced to polynomial time.
It means if I have a set of problems in P and NP, and they can be reduced in polynomial
time, then those set of problems are called as NP based problems.
453
NP complete:
The group of problems what are both NP and NP hard is called as NP Complete Problems.
454
Tower of Hanoi
In this chapter we shall learn about below topics:
2.1 Introduction.
2.2 Problem Statement
2.3 Understanding using an example
2.4 Implementation
2.5 Output
2.1 Introduction
Tower of Hanoi is a classic problem that can be solved with the help of recursion.
There are different size of rings placed on top of each other in ascending order. There might
be “n” number of rings, but there will be only 3 towers.
Your goal is to move all the rings from one tower to another tower [final result should be in
ascending order] without breaking the below rules.
To illustrate the solution to the problem, consider the below diagram that has 3 rings.
We follow below steps to move all the 3 rings to the 2nd tower.
455
456
So from the above diagram, we can see that, to move only 3 rings we took 7 steps. i.e for n
rings it will take 2^n-1 steps.
Most of the steps are repetitive. Hence we use recursion to solve this problem.
So we need to take 3 towers, let us name them as Source, Destination, and temp.
And “n” be the number of rings.
The below image shows which tower refers to Source, Destination and temp.
2.4. Implementation
457
#include <iostream>
int main()
{
int n = 3;
2.5. Output
The time complexity of Tower of Hanoi using recursion is 2^n at worst case. I have written
as “recursion” because, there is a way that you can solve this by using Dynamic
Programming and Divide and Conquer Methods. As in this tutorial we have solved using
recursion, we have taken the time complexity of recursion.
458
Sieve Of Eratosthenes
In this chapter we shall learn about below topics:
3.1 Introduction.
3.2 Working of the algorithm
3.3 Understanding using an example
3.4 Implementation
3.5 Output
3.1 Introduction:
Sieve Of Eratosthenes is one of the most simple and efficient algorithm to find the prime
numbers for a given set of limit.
Step 2: From the number “2”, strike out all the multiple of 2. Here we have represented
strike out in red color.
459
Step 3: Then go to the next prime number, now strike out the numbers that are divisible by
the present prime number till the square of the present prime number. Here the next prime
is 3, it’s square is 9. Hence strike out all the numbers that are multiple of 3 till 9. As 6 is
already striked out earlier, we strike out 9 now.
Repeat step 3, till we reach the end. We shall try one more pass.
Now the next prime is “5”, it’s square is 25. Strike out all the numbers that are multiple of 5
till 25. i.e strikeout “10”, “15”, “20”, “25”. As “10” and “20” are already striked out, strike
out “15” and “25”
#include <iostream>
void sieve_of_eratosthenes(int n)
{
//take a boolean array to store which index is a prime number.
bool prime[n + 1];
460
for (int i = 2; i <= n; i++)
{
prime[i] = true;
}
int main()
{
// n is the max limit to find the list of prime numbers from
int n = 30;
sieve_of_eratosthenes(n);
return 0;
}
3.5 Output
2 3 5 7 11 13 17 19 23 29
461
Kadane Algorithm explanation with implementation in C++
Introduction:
Kadane Algorithm is an efficient way to solve the maximum sub array problem.
Explanation:
So before we know about Kadane algorithm, first we shall look at that is the maximum sub
array problem?
You will be given with an array, you need to find the continuous sub array whose sum is the
largest sum.
In the array above, you need to find a sub array with maximum sum.
By brute force we can see that sum of elements [2, 3] is 5. This is the maximum sum.
If you solve by brute force, it will take O(n) time at. This can be efficiently solved with help
of Kadane’s algorithm.
Before going to kadane’s algorithm, we shall see how to solve by brute force approach:
At any index, we check what is the maximum sub array at that index:
So for our example,
[-1, 0, 2, 3, -2]
462
[3]
)
Hence max = 5;
1. The local maximum sub array is either the element at the current index
or
2. The current element combined with previous local maximum sub array.
We continue to calculate the above for all the elements in the array. After that we are going
to pick the maximum sub array in the list of local_max_sub_array.
So how to do it programmatically?
Step 2: Start a loop from index 1 to end of the array and perform below operation:
local_max_sub_array = max(arr[i], local_max_sub_array + arr[i])
global_max_sub_array = max (local_max_sub_array, global_max_sub_array)
Initally
local_max_sub_array = a[0] = -1
global_max_sub_array = a[0] = -1
Pass 1:
local_max_sub_array = max[arr[1], (-1 + arr[1])]
= max [0, -1] = 0
Pass 2:
local_max_sub_array = max[arr[2], (0 + arr[2])]
= max [2, 2] = 2
global_max_sub_array = max(0, 2) = 2
463
Pass 3:
local_max_sub_array = max[arr[3], (2 + arr[3])]
= max [0, 5] = 5
global_max_sub_array = max(3, 5) = 5
Pass 4:
local_max_sub_array = max[arr[4], (5 + arr[4])]
= max [-2, (5 - 2)] = 3
global_max_sub_array = max(3, 5) = 5
Implementation in C++
#include<stdio.h>
for(i=0;i<size;i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
{
max_ending_here =0;
}
if(max_sum_so_far < max_ending_here)
{
max_sum_so_far = max_ending_here;
}
return max_sum_so_far;
}
464
int main(){
int i,size;
int a[size];
printf("\n Enter the elements of the array");
for(i=0; i<size; i++)
{
scanf("%d",&a[i]);
}
return 0;
}
Output:
The time complexity of Kadane is O(n) time [linear time] in all the cases.
There is a sliding window approach to solve this problem. We shall see one variant of that
algorithm in the next chapter.
465
Sliding Window technique
Introduction:
This technique can be applied in different ways. It can be applied on strings and also on
integers. Below are the 2 ways in which we can apply this technique.
1.Fixed size window [this technique we shall study in this chapter]: Here you will be
presented with an array and a fixed size window, you need to find the maximum continuous
sub array with largest value in that fixed window.
2. Variable size window: Here you will be given an array and a number, you need to find the
sub array of any length, to find the continuous elements that adds up that number.
Algorithm Explanation:
As discussed above, you are given an array, and window size. You need to find a continuous
sub array with in that window size.
For example:
array = [1, 2, 4, 3, 5, 7, 6]
window size = 2
So by looking at the array we can see that [7, 6] with the window size 2 is having the
maximum continuous sub array with largest value in that fixed window.
We can solve the above problem by using brute force method. i.e taking 2 for loops. First
loop will start from first index, then in the inner loop will go through all the elements from
that index till the window size. Here the time complexity will be O(n^2). This can be further
improved by Sliding Window technique.
Step 2: Move to the next element, then calculate their sum. If the present sum is greater
than the previous sum, update the max, else retain the previous value.
[1, 2, 4, 3, 5, 7, 6]
[1, 2]
[2, 4]
[4, 3]
[3, 5]
466
[5, 7]
[7, 6] = 13 is the max value.
As you can see from above, we slide the value from element to element. Hence we call it as
sliding window approach.
Implementation in C++
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 2, 4, 3, 5, 7, 6 };
int k = 2;
sliding_window(arr, 7, k);
return 0;
}
Output:
467
Travelling salesman problem with implementation
In this chapter we shall solve Travelling Salesman Problem with help of dynamic
programming.
Problem statement:
A salesman will start from a parent city and visit all the cities only once and return to parent
city. He has to do it with least cost possible.
Consider the below graph and let the parent city be “a”.
Now let’s write the valid cases where the salesman visits all the cities only once and return
to source city.
Here we have visited “b” 2 times. As you can see from the above valid case, we need to find
a Hamiltonian cycle.
As there can be many routes/cycles, we need to find a path with min cost.
468
So this problem can be solved by 3 different methods:
So we shall understand the DP approach with the help of the tree below:
Hence from “a” we can go to “b” “c” and “d”. It can be shown as below:
469
Again from node “c” he go to “c”
470
So above image shows all the possible paths. You need to reach to the source vertex again.
Hence we can further update the tree as below:
Starting from the last path, we go from bottom to top and update the cost taking from cost
table.
471
Again we shall go one level up and find the total distance:
472
Now again we go one level up, and check the value for “b -> c -> d -> a”, as we have
calculated value for “c -> d -> a”, we just need to add that value to the last path. Here with
help of DP table we shall be able to do it efficiently.
Now that we have calculated the value for all 6 paths, at the parent node of “b”, “c”, “d”.
We have 2 values, we need to find min of 2 values.
473
For node “b” we have:
Take 12.
474
Now we go one last level up and calculate the final path:
Hence if the salesman travels the path a -> d -> c -> b -> a, he can visit all the cities only once
and arrive at the initial city with min cost.
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;
int tsp(const vector<vector<int>>& cities, int pos, int visited, vector<vector<int>>& state)
{
if(visited == ((1 << cities.size()) - 1))
475
return cities[pos][0];
if(state[pos][visited] != INT_MAX)
return state[pos][visited];
int main()
{
vector<vector<int>> cities = { { 0, 15, 4, 5 },
{ 14, 0, 11, 4 },
{ 5, 21, 0, 8 },
{ 5, 4, 12, 0 }
};
vector<vector<int>> state(cities.size());
Output
minimum: 25
476
Minimum Coin Change Problem
In this tutorial we shall learn how to solve coin change problem with help of an example and
solve it by using Dynamic Programming.
Problem Statement:
You are given a certain coin denomination and a total amount. You need to find min number
of coins required to add up to that total amount. You can assume that you have unlimited
supply of coins.
Coin Denomination: 1, 2, 5, 7
Total = 7.
There can be also “2 + 2 + 2 + 1 = 7” 4 coins. But we need to calculate the min coins
required.
From the above image, we have written down the amount from 0 to 7. It is important to
include 0 also. We have also written the coin combination, so that we get to know the least
number of coins required that match the denomination.
So we you have only 1 coin/rupee the number of coins required will be equal to the amount.
Hence we can fil the array as below:
477
Now we shave coin options [1, 5] and now we shall check if we can reduce the number of
coins required. Till 4 rupees, the number of coins required will be same as the amount.
When you reach 5, as you have a 5 rupees’ coin, the number of coins required will be 1.
Similarly, when you reach 6, the min coin will be 2. i.e one rupee coin and one 5 rupee coin.
Similarly, when you reach 7, the min coin required will be 3. 2 one rupee coin and one 5
rupee coin.
Now that we have filled the amount by using logic, how can we formulate this logic?
When we reach 5 rupees, the number of coins required is 1. If you check carefully, we took
the minimum of the value above or value at 5 steps back + 1.
So min(5, 0 + 1) = 1.
478
Note that we take the number of steps back, according to the coin value. As of now we are
calculating (1, 5). Hence we take 5 steps back.
479
When we reach at 6 rupees, we can calculate using the previous formula, now we shall
move back 6 steps.
#include <iostream>
#include <vector>
480
int main (void)
{
vector <int> coins;
coins.push_back (1);
coins.push_back (3);
coins.push_back (6);
int amount_value = 6;
cout << min_coin << " is the minimum coin required for amount_value = " <<
amount_value << "." << endl;
return 0;
}
Output:
481
Total number of ways to get denomination of coins.
This is a variant of the previous problem. Like previous coin change problem, we shall solve
with help of Dynamic Programming.
Problem Statement:
You are given total amount and certain coin denomination. You need to get the total
number of ways you make the change.
Example:
Amount Value = 6
Coins = 1, 3, 6
Number of ways =
1+1+1+1+1+1
1 + 1 + 1+ 1 + 3
3+3
So if you have only 1 coin, the total number of ways you can arrange will be only 1. Hence
we write 1 in all the cells.
482
Now you have [1, 3] coin, the total number of ways till rupee 3 will be 1 only.
Now when you are at 3 rupees, the total number of ways will be 2. Because you can have 3
one rupees coin or one 3 rupees coins.
1+1+1+1=4
1+3=4
Similarly, for 6 rupees it will be 3. Because all 2’s or two 3’s or all 1’’s.
483
But how can we convert into a formula?
If you observe at 3 rupees, the value 2 can be got by adding the value from top and value for
3 steps before.
add(value_ar_top + value_at_3_steps_back)
484
Similarly, we can calculate when we have 3 choices. Till 5 rupees, we can copy the value
from above cell.
#include <iostream>
#include <vector>
485
table[j] += table[j-coins[i]];
}
}
return table[amount_value];
}
cout << num_of_ways << " Coin changes are possible for amount_value = " <<
amount_value << "." << endl;
return 0;
}
Output
486
Job Sequencing with deadline Problem
In this tutorial we shall learn about job sequencing with deadline problem. We shall solve
this problem with the help of Greedy Approach.
Problem statement:
You are given a set of jobs associated with deadline and profits attached to the jobs. Your
goal is to find the maximum profit within the given deadline.
You have to assume, only one job can run at a time. Profits will be counted only after the
execution of that task is completed. Every job needs one unit of time.
The deadline that is mentioned, is the amount of time a job is willing to wait.
Given below are number of jobs and deadline and profit associated with it.
Now, our focus is on the profits, hence we shall sort them accordingly to the profits
Now we have applied greedy method. Because we want to get more profits, hence we sort
according to decreasing profits.
0 _ 1 _ 2 _ 3 _ 4 _ 5 Profit = 0.
487
Here the slots are
0 _ 1,
1 _ 2,
2 _ 3,
3 _ 4,
4_5
So for job j2, it is willing to wait till 2 nd slot. Hence we take that slot and profit is 40.
0 _ 1,
1 _ 2 = taken by J2
2 _ 3,
3 _ 4,
4_5
Profit = 40
For job J1, it is willing to wait till 5. Hence take that slot.
0 _ 1,
1 _ 2 = taken by J2
2 _ 3,
3 _ 4,
4 _ 5 = taken by J1
Profit = 40 + 20 = 60
Now for job J4, it is willing to wait till 3. Hence we will put it in that slot and profit increases.
0 _ 1,
488
1 _ 2 = taken by J2
2 _ 3 = taken by J4
3 _ 4,
4 _ 5 = taken by J1
Profit = 40 + 20 + 15 = 75
Now for job J5. It is also willing to wait 3 time units. But the slot 2_3 is already taken.
Yes, there is a slot available at 0_1. Here, for any task, if there is a deadline, it means that
you cannot perform that task after that deadline, but you can perform before it. Hence for
the job J5, we take the slot 0_1 slot and get the profit.
0 _ 1 = taken by J5
1 _ 2 = taken by J2
2 _ 3 = taken by J4
3 _ 4,
4 _ 5 = taken by J1
Profit = 40 + 20 + 15 + 10 = 85
J6 can only wait for 1-time unit. But that slot 0_1 has been taken by J5. Hence discard job J6.
Now for the job J3. This job is willing to wait 5 time units. The slot 3_4 is available. Hence we
execute the job in that time slot.
0 _ 1 = taken by J5
1 _ 2 = taken by J2
2 _ 3 = taken by J4
3 _ 4 = taken by J3
489
4 _ 5 = taken by J1
Profit = 40 + 20 + 15 + 10 + 5 = 90
#include <iostream>
490
result[j] = i;
slot[j] = true;
break;
}
}
}
Output:
Result =
5 2 4 3 1
491
Activity Selection Problem
In this chapter we shall learn on how to solve activity selection problem with the help of
example and using greedy method.
Problem Statement:
You are given list of activity with starting and ending time. Your job is to find the maximum
number of activities can be performed by that machine. Note that the machine can only
perform 1 task at a time.
These activities should be non-conflicting. It means, a new activity start time should be
greater than or equal to the ending time of the previous activity.
For example:
Below is the list of activity with starting and ending time;
Now you can select activity a1, but you cannot choose a2 because the start time of a2 is less
than the ending time of a1. Hence you skip a2 and move to a3.
As a3 starting time is greater than the time of a1, you will choose it. But is the optimal
solution? No
Because, if you choose a2, a3. Then you will get more work done.
We can solve this by greedy method. We follow below 3 steps to arrive at the solution.
Step 1: Sort the activities according to the finishing time in ascending order.
492
Step 3: Check the new activity start time is greater than or equal to end time of previous
activity and select it. Repeat step 2 and 3 till all activities are checked.
Now a2 start time is less than a1 end time. Hence skip a2.
493
Now a6 start time is greater than a1 end time. Hence select that activity.
Similarly, a4 start time is less than a6 end time. Hence discard it.
494
Hence the final result.
#include <iostream>
struct Activity
{
char id[10];
int start;
int finish;
};
Activity temp;
cout<<"Final Result"<<endl;
cout<< "Activity Start Finish"<<endl;
495
cout<< activities[0].id<<" " << activities[0].start<<" " <<activities[0].finish<<endl;
//check and select the next activity whose start time is greater than or equal to the
finishing period of previous
//activity
i = 0;
for(j = 1; j < n; j++)
{
if(activities[j].start >= activities[i].finish)
{
cout<<activities[j].id<<" "<< activities[j].start<<" "<< activities[j].finish<<endl;
i = j;
}
}
}
int main(void) {
Activity activities[8] =
{
{"a1", 2, 3},
{"a2", 1, 4},
{"a3", 8, 10},
{"a4", 6, 9},
{"a5", 10, 15},
{"a6", 5, 8},
};
int total_activity = 6;
activitySelection(activities, total_activity);
return 0;
}
Output:
496
a6 5 8
a3 8 10
a5 10 15
497
House Robber Problem
In this tutorial we shall solve a very famous problem “House Robber” problem. This problem
can be solved by using DP method.
Problem Statement:
You are given an array of +ve numbers that represents amount present inside the house,
you need to rob the house such that you rob maximum amount. The only condition is that
you cannot rob 2 consecutive houses. Robbing 2 consecutive houses will result in alarm and
you will get caught.
Array
[2, 3, 4, 5, 7, 8]
= 16.
2, 4, 7 = 13
Suppose if you have 2 house, then you will rob the house that has more money.
Hence by solving in bottom up approach, we can arrive at the solution for getting maximum
profit by robbing n houses.
498
As usual for DP, we create a DP array with once extra size and initialize to 0.
[0, 0, 0, 0, 0, 0, 0]
We leave the 0thindex as 0, because if you don’t have a house, your profit will be ‘0’.
For index 1, we fill the value from index [0] of our given array.
[0, 4, 0, 0, 0, 0, 0]
We did this because, in our DP array, we have considered the possibility if there are no
house, then the profit is 0 in index [0] of DP array.
Now we reach index 2. WKT we cannot rob the house at index 2, because we have already
robbed 1. But the profit you gain when you rob the house 2 is greater than that of house 1 +
all the houses that are robbed before 1.
= max[4, 0 +5]
=5
dp [2] = 5
#include<iostream>
499
void houseRobber(int nums[], int length)
{
if(nums == NULL || length == 0)
{
cout<<"The profit is = 0"<<endl;
return ;
}
if(length == 1)
{
cout<<"The profit is = "<<nums[0]<<endl;
return ;
}
int dp[length];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
int main()
{
int arr[5] = { 3, 8, 4, 8, 9 };
houseRobber(arr, 5);
return 0;
}
500
HR Interview questions and tips to answer them
501
Expectations on oncoming topics:
Below are some of the expectations that I want to set before proceeding to the next topics:
1. Previous data structure and algorithms chapters I have given a detailed explanations
of the concept. But in the following HR interview questions I have provided the
points that might be useful for answering the questions.
3. The answers expected form the interviewer differs from person to person.
4. The points that I have expressed in following chapters are in my point of view. You
are free to take those points or ignore those points.
5. These oncoming topics were not included in initial book planning, but after
considering requests from the readers, I have included the topics.
502
Mistakes to avoid in an interview.
In this chapter we shall see what are the mistakes to avoid in an interview.
3. Body Language:
It’s common that while going for an interview you will be nervous. But you should not show
through your body. Avoid any such posture that will give that you are nervous.
It is usually good to look into the eye of the interviewer while giving a firm
handshake and a smile on your face during an interview.
503
Tell me about yourself
This is the most common question that will be asked in an interview. It is better that you
must be prepared for it. Below are some of the most common points that you can say:
1. All the points you say about yourself should be relevant to the interview. Don’t say
that you have a dog in your home. Say that you like technology and stay relevant to
the technology. It is always good to say some of the website names like:
www.engadget.com
www.prodevelopertutorial.com
www.ubergizmo.com
3. Say about your accomplishments. Like the most critical issue you have fixed and how
did you arrive at the solution.
4. Be confident on what you are saying, maintain good eye contact and show passion
that you are interested in the job position.
504
Why should we hire you?
For this question you answer should include points like why you are best suitable for this job
and how the project will improve if they hire you.
It is also good to mention what additional things you can contribute to the team apart from
day to day activities. It is good to include that you are good in giving presentation or good to
deal with clients, give some examples.
So for that to answer, research a bit about the company and the job position that you are
applying for.
So for a programming job, if they are looking for C, C++ with Linux experience. Then you
should include those skills in your answer.
You should also say that you are a team player and also good good in communication and
good in presentation skills.
Second thing is that you can tell a story on how there was a problem and you solved it by
using your skills.
For example, if the client was angry on a teammate and you stepped in and convinced the
client to give more time.
Another thing you can mention is what sets you apart from rest of the candidates.
Like you actively volunteer for work, great team player, your love things for quality or give
an example where you went beyond the work. You can also show your GitHub contribution
if you have any.
505
Why do you want to work for us?
This is very important question. You can answer by including below points:
1. Tell then in a technical way on what you like about that company.
2. Tell them how working for them in long term will help you to achieve carrier goals.
506
What are your greatest strengths and weakness?
To answer these type of question, you need to answer carefully. Saying too much or saying
too little will hurt your chances of getting the job. Below are few points that you can include
in your answer.
4. Straight forward while communicating about work and stay to the point without
diverting from the topic.
For example, you had stage fear while giving presentation, and how you overcame it.
507
What are your greatest achievements/ accomplishments?
To answer this question, you need to answer in such a way that they’re meaningful and
relevant to the to the job position you are applying to.
Don’t say that you have ran 25Kms. This is irrelevant in a programming interview.
1. Growing revenue.
For fresher you can write about internship, any certifications related to your job is a good
addition.
508
Any questions for us?
This question will be asked at the end of the interview. The answer to this question depends
on who is asking the question.
If the project manager is asking you the question, you need to ask question related to
company or the team he is handling. Tools that are used in the project.
If this question is asked by team lead, who is more accustomed with coding, below are the
questions you can ask:
1. What are the languages used?
If HR is asking you the question, below are the question you can ask:
2. Are there any additional benefits company is providing, like relocating changes,
health insurance?
2. Comp off
Because, all these are standard once you get selected, in company orientation they will
mention them.
509
Where do you want to see yourself in 5 years?
1. Be goal oriented.
3. Say that you are looking for long term with the company.
2. Don’t say that, you will set up a business, till then you will work.
510
How to you work under pressure?
1. Say that you have done your some of the best works under pressure.
2. Say that you prioritize the task and then complete highest priority task first and then
come to lowest priority task.
3. Say that if things get overloaded, you take small breaks then focus on the work.
4. Instead of getting distracted by the noise, I stay calm and complete the work.
5. Even though if there is panic in the team, I motivate everyone to work together, to
stay concentrated and complete the task.
511
How do you make important decisions?
1. I make sure that the decision I make will benefit the team and project.
2. I list down pros and cons of the decision and discuss with the team and arrive at the
solution.
3. Give any example of you have faced in real time scenarios, and the decision that you
have taken and how it has helped the team.
512
What motivates you to do the best on job?
1. I am self-motivated.
2. My dreams
6. Good team
1. Money is my motivation.
513
Do you prefer working alone or in a team?
Your answer should include both. Because missing out any one will hurt your chances of
getting selected in interview. Below are the points that you can include in your answer.
Sometimes, I prefer working alone. Because when you work in a team, your hard-work and
achievement will be considered as team achievements. But in reality I would have done
most of the contribution. If I work independently all of my work will be recognized.
514
What do you know about our company?
It is important to know about the company before you go for the interview. Don’t say too
much or too little about the company. It is recommended that you prepare for at-least to
speak for 2-3 minutes.
Below are the points that you can include:
1. It is recommended to talk about the flagship product and how it is helping it’s
customer.
2. Talk about the first product launched by the company and how it has helped to
reach the company to great heights.
4. Talk about the latest product that they are preparing to release.
5. Talk about the achievement and awards that the company has got.
7. Make a personal connection with any product of the company, and how it has
helped you.
515
Are you planning for further studies?
This is a common question asked for fresher’s. It is recommended that you say “no” and
give a justifiable reason.
You can say like: No, I don’t have any plans for higher studies. I am looking to start my
career with a good organization like yours.
Or
You can say like: I want to look for higher studies after some years for my career
improvement, but not as of now.
Or
516
What is your salary expectations?
This is a very important question and you need to be prepared to answer the question.
Because quoting too high or too low will not be feasible. Because, the company has a
budget allocated for that position and they will be ready to give your expected salary.
It is always good to ask their offering first, later you can say your expectation.
517
Tips for Developers to improve their skills
518
How to prepare for coding interview in 3 months.
I have created the answer for this question by taking my own experience and also asking it
to my friends and formulating the points.
I am not saying that if you follow this you will get a job, but this will provide you a way you
prepare better for interview.
1. Basics of programming.
2. Data structures and algorithm.
3. System Design concepts.
4. Commonly asked coding questions.
5. OS Concepts.
Below I have given the link from where you need to prepare for first 4 points. For OS
concepts you can refer YouTube videos.
3 months will have 12 weeks. I have structured in such a way that they will help you to
prepare better for interviews.
Week 1:
Choose a programming language and get your fundamentals right. Write basic programs
and execute them.
Note: During the interview, stick to one programming language. Don’t switch the language
during the interviews.
Week 2:
Start coding more complex problems.
For example:
1. Read from a file.
2. Working of pointers.
3. Function pointers.
4. String Operations.
5. Again lots of programs related to pointers.
519
Week 3 and Week 6:
Learn about data structure and algorithm. This book has exhaustive list of algorithms and
data structures that can be asked in interview.
Understand the program that I have given you. Try it on your own and then compile the
program that has been given to you.
Week 7:
In this week practice more complex coding problems related to:
1. Dynamic Programming
2. Backtracking
3. DFS
4. Strings
5. Matrix
6. Divide and conquer
7. Bit Manipulation
8. Linked List
9. Array
Try to solve at-least 50 to 60 questions from those links. All the questions that I have solved
has been frequently been asked in interview.
Week 11:
Learn about System design. Below I have written a book on system design concepts.
Go to YouTube or find a book on Linux System Programming and be prepared about below
topics:
So you have covered all the concepts in 3 months for your interview. All the best.
520
Tips to solve coding interview questions
In this chapter I shall give you some tips on how to solve coding interview questions.
2. Always think out loud so that interviewer will know your thought process.
3. Ask doubts/ questions related to the problem that they have given to you.
4. After you come up with brute force solutions, calculate and write down the
complexity of the solution.
6. While solving the problem, it is always rood to solve with simple and short input and
try noticing a pattern.
521
How to write a resume for coding interview?
In this chapter I shall give you some tips on how to write resume for software developer.
4. List of projects you were involved in and your roles in that project.
Don’t include:
1. FB profile.
2. Instagram Profile.
Keep your resume short, in about 2 pages. Google for good template and fill it.
522
Tips to become good at programming
2. Dedicate at-least 1 hour other than office hours to solve competitive programming.
10. Write your shell script and python script to do your daily tasks.
11. While coding, if you stuck anywhere, instead of asking your colleague, search in
google first. There is a good chance that they have the answer.
12. Read others code and understand the thought process that they have applied.
13. Explore other programming language, notice how they are better than other
programming language.
14. Create a small project and write documentation and upload in GitHub.
523
Proof of my work for this book:
I have spent day and night for writing this book for almost a year. Hope that you have
enjoyed learning as much as I enjoyed writing this book.
524
Additional Links:
If you have received this book for free from friends, please support me by buying the
original copy. This will help me to write additional books.
https://www.instamojo.com/aj_guides/
I have written additional books also. All are available in above link.
https://t.me/cpwithaj
Telegram Channel for daily Competitive Programming Question with Solution, join below:
https://t.me/competitive_programming_question
525