DEV Community: Sayani Mallick

Data structures and algorithms

Sayani Mallick — Wed, 10 Mar 2021 13:48:28 +0000

Data structures and algorithms are a must for any coding interview.
There is no well set road map for learning data structures and algorithms other than hard work, consistency and practice. Since this is a very vast field, therefore, only regular practice can help you become a good programmer.
While learning data structures and algorithms, I have solved various questions and decided to compile all the codes I come across into a git repository. Everyone and anyone enthusiastic in data structures and algorithms can contribute to the repository. All you have to do is: fork, clone, create a branch , write your code and send a pull request describing the code you have written.
Here is the link of the git repository:
DATA STRUCTURES AND ALGORITHMS
Hope this will help learners who want to learn DSA!
Follow me on Github
Happy coding!

Depth first search on Graphs

Sayani Mallick — Sat, 23 Jan 2021 18:07:39 +0000

Depth first search on Graphs is a very basic question on graphs and is necessary to solve any graph question of graphs.
A graph is a data structure which is defined in terms of vertices and edges,that is, G=f(V,E).

ALGORITHM
In depth first search, we first mark all the nodes as 'unvisited'. We start from the root of the graph and mark it as visited, and then move on to its connected nodes. If the present node has any unvisited node then we move on to that node. In the absence of any unvisited node, we backtrack and move to another node.

Let us implement the Explore function

Explore(i)
mark all nodes as unvisited

for all i node in graph
{
if node unvisited
mark node as visited
Explore(i)
}

Hope this helps you!

Longest common subsequence in C++

Sayani Mallick — Thu, 07 Jan 2021 17:22:11 +0000

The longest common subsequence is a standard dynamic programming problem. In the longest common subsequence problem, two strings are given. The aim is to find out the length of the longest common subsequence.
Example:
INPUT:
abcde
abxyzd

OUTPUT:3

The output of the above input will be 3 because the longest common subsequence is abd.

Other examples:
INPUT:
axyz
ghjk
OUTPUT:0
There is no common subsequence at all.

INPUT:
a
abcdefghijklmno
OUTPUT:1
The longest common subsequence is a

Using the dynamic programming concept, we form a two dimensional array
t[length_of_first_string+1][length_of_second_string+1].
We then initialize the two dimensional array as:If the length of the first string or second string is zero, then the common subsequence length will also be zero.

CODE:

Hope this helps you! Do follow me on Github!

Fractional knapsack using C++

Sayani Mallick — Wed, 06 Jan 2021 16:53:49 +0000

Fractional knapsack problem is a famous problem in greedy algorithms. The problem statement tells that a knapsack is given which has a weight W. You are given a list of weights and values of different items. The expected output is to output the maximum value of items that can be packed inside the knapsack.

ALGORITHM
1.We find the value per unit weight for each item
2.Next, we find the item with the maximum value per unit weight and check if the weight of that item is less or equal to the resultant weight of the knapsack then we include that item completely. Then we update the resultant weight of the knapsack.
3.If the weight of the item is less than that of the knapsack but the weight of the knapsack is not zero, then we include that amount of the item which fits into the knapsack.
4.If the sum of weights of all the items is less than the weight of the knapsack, then the output will be the sum of the values of each item.

CODE
The code snippet is:

Hope this helps you! If you liked the article do follow me on Github!

Converting a sorted array into a binary search tree in C++

Sayani Mallick — Wed, 06 Jan 2021 16:08:28 +0000

Let us see how to convert a sorted array into a binary search tree. Before that let us see what is a binary search tree.

What is a binary search tree?

A binary search tree is a node based data structure which has the following properties:

The left sub-tree of a node contains elements lesser than that of the node
The right sub-tree of a node contains elements greater than that of the node
There are no duplicated values in the binary search tree.
Each of the left sub-tree and right sub-tree follow the rules 1 and 2.

To create a binary search tree from a sorted array we first find the middle element and create the root. Then we use a recursive function to form the left and right sub-trees.

Code
The code snippet for creating a node:

The function for converting array to binary search tree:

The function for preorder traversal and printing of the binary search tree:

Hope this helps you!

Dynamic Programming Question: 0-1 Knapsack problem

Sayani Mallick — Sun, 03 Jan 2021 10:24:23 +0000

0-1 Knapsack problem is a very classic example of dynamic programming.
PROBLEM STATEMENT:Given an array of items with their quantity and their values, determine the maximum value of the items that can fit into the bag with a capacity of W.

SOLUTION:
An important thing to keep in mind about such question is that here we cannot take the fraction of any item, it is either whole or nothing at all.
This question can be solved with the help of dynamic programming. In fact, this question is a classic question of dynamic programming.
ALGORITHM:

We have been given a list of items with their value and weights.
Here we use the concept of dynamic programming, that is, we store the results of the previous calculations in an array and using those results for further calculations. 3.We start our calculations from the nth item. Here we check whether the weight of the nth item is less than the weight of the knapsack.If the weight of the knapsack is greater than the weight of the item , then we have two options, we can either include that item or we can exclude that item from our chosen ones. As we have been asked to store the maximum, therefore, we choose the maximum of the two.
If the weight of the knapsack is less than the weight of the item there is no way we can include that item.
We continue this process from the nth item to the 1st item.

CODE:

Hope this post helps you in becoming a better competitive programmer. Follow my Github for more competitive programming questions

Solving Balanced Parenthesis Problem

Sayani Mallick — Sun, 03 Jan 2021 09:56:50 +0000

A famous interview question on stacks is to solve the balanced parenthesis problem. In this question, the input consists of a series of parenthesis and other characters and the expected output is to print "Balanced" if the bracket sequence is balanced otherwise "Unbalanced".

Example:
INPUT: []{}{}{}[]
OUTPUT:Balanced

INPUT: [{}]{}
OUTPUT:Balanced

ALGORITHM
To solve this problem, we scan through the elements of the string one by one. If the character under consideration is an opening parenthesis "([{", then we push it to the stack.
If the character is a closing parenthesis, then we check whether the stack is empty or not. If the stack is empty, then it means the brackets are unbalanced. However if the stack is not empty, then we check whether the top element on the stack is the corresponding opening parenthesis or not, that is,( for ), { for }, [ for ]. If it is then we continue scanning, else the sequence is unbalanced.
But the algorithm does not end here.
After the entire string has been scanned, we check again whether the stack is empty. If the stack is empty and the previous scanning results(the algorithm followed above) also show that the string is balanced, then we print that the sequence is Balanced.
However if the stack is not empty, then it means that there is some parenthesis whose match has not been found yet, and the sequence is, hence , unbalanced.

Hope this helps you!