# Validate Binary Search Tree

The problem states that we will be given a binary tree and we have to determine if it is a valid binary search tree(BST) or not. you can find this problem in Leetcode and in Hackerrank.

First of all, what is a binary tree?

A binary tree is a tree that has at most two child nodes.

Then what is a binary search tree?

A binary search tree(BST) is a kind of binary tree where each node is greater than its left node and smaller than its right node.

If you do not know how to implement a binary search…

# Recursion

Most of us know what recursion is and can write recursive code if we are asked to. But when we try to solve advance problems(i.e binary tree, binary search tree etc.) and see recursive solutions, we get confused about how that code is working, so in this post, I will try to explain how a recursive code works behind the scene with a simple factorial finding recursive code, and we will be able to trace more complex recursive code the same way.

Now let’s see the c++ code to return the factorial of a number :

How does this…

# Least Recently Used(LRU) Cache Problem Part1

The problem asks you to build a caching(cache is something that stores computation for lookups or it may also store redundant data for quick access to speed up future requests) system that has all the usual cashing features(i.e insert, delete, search) but it has the ability to get rid of least recently used data. For example: if we have a LRU cache of size 3

v[‘c’] = 2;

v[‘b’] = 4;

v[‘a’] = 1;

Here ‘c’, ‘b’, ‘a’ are the key and 2, 4, 1 are values. Initially, the least recently used pair is v[‘a’] = 1 and the most…

# How C++ works

The basic workflow of c++ code is: source file-> compiler -> executable binary file. But how do we get to the executable binary file from source code?

Let's see a c++ code first:

What is in the Source file?

The first thing we see in the above code is: “#include<iostream>” this is a preprocessor statement. Whatever starts with “#” is a preprocessor statement. When a compiler gets a source file, it preprocesses all the preprocessor statements. Then we have “include”, it finds the file “iostream” and takes all of its contents and pastes them into the current file. …

# Shifted Binary Search Problem

The problem asks you to find a number from a sorted array but all the numbers has been shifted by some amount either left or right.For Example:{9, 19, 21, 2, 8} the array is sorted from index 0 to 2 and then we have the value 2 which is less than 21 and then again from index 3 to 4 the array is sorted again. Notice that for the array to be sorted, all the values from index 0 to 2 are supposed to come after the value 8 which is at index 4. So, the problem give you this…

# C++ STL

In this post I’m not doing in depth discussion on how these standard libraries works behind the scene. I will just show what they do and how to use them.

## Sort

• sort: It orders the elements from beginning to end in O(nlogn) complexity. By default it the elements in ascending order for numeric values and lexicographical ascending for string values. (* P.S. print() is not a stl, I have written the method to print the vector. you can see that in the source code I have provided in the end of the post)

# Longest Common Subsequence (LCS) DP Problem

A subsequence is a group of characters that appears sequentially but it doesn’t have to be contiguous though it can be. For example s = “AFPKL” in this string valid sub-sequences can be “AFP”, “APK”, “AFKL” etc.

So, the problem is asking us to return the sequence of the longest common subsequence (LCS) between two strings. For instance:

Input: “abdez”, “bxide”

Output: [“b”, “d”, “e”]

Solution Approach

If we had 2 strings “abc” and “ac” the LCS will be “ac” . We get to this LCS by looking at the last letter of both strings. …

# Binary Search Tree Implementation in C++

Binary search tree(BST) is a kind of binary tree(tree where each node has at most 2 child nodes) where any node of the tree will be less than all its right children and greater than all its left children. For Instance

To implement BST will implement three things that we can do on a BST:

1. Insertion
2. Search
3. Deletion

Insertion

If we want to insert a value in our BST, let’s say we want to insert 17 . We will start from the root node, which in our case has the value 12. So, We will compare 12 and 17, as…

# Edit Distance DP Problem

Edit distance problems is: if we are given two string word1 and word2 what is the minimum number of operation needed to transform a into b. The operations are: substitution, insertion and deletion. You can find this problem in interviewbit and leetcode.

In order to solve this problem, we have to be familiar with sub-string operation. Substations are contiguous sequence of characters within a string( from Wikipedia).Let’s say we have a string “horse” which goes from index 0 to 4. …

# BFS Implementation in C++

BFS is a graph traversal method that traverses the graph iterative way level by level. That means it traverses the graph “breadth first”, starting from the source then the neighbor of the source then the next level and so on.

For example:

If we traverse the given graph above, the output will be: ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘K’, ‘I’, ‘J’

‘A’ will be visited first as it is the source node. Then ‘B’, ‘C’, and ‘D’ is in the next level, so they will be visited. … ## Shaila Nasrin

Software Engineer at LogMeIn