# Edit distance 1

Given two strings, how do we check if their edit distance is 1?

Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string.

For example let us consider two strings “java”, “lava” they both differ by just one character. we can change the first character in either of them to make them equal.

Similarly, the words “at”, “bat” also have an edit distance of 1 because either we can add “b” to the first string, or delete “b” from the second string to make them euqal.

By looking at the problem statement, one can think of a dynamic programming solution which takes O(n^2) time. However, it would an over kill to solve this problem.

Let’s observe some thing. Two strings can not have an edit distance of 1 if their lengths differ by more than 1 characters.

So we can simplify our approach to work on the two use cases.
which are either of equal length, or
one string longer than the other by just one character.

Lets see some representative test cases we need to handle.

(“abc”, “bc”), (“abc”, “ab”), (“string”, “sxring”), (“algorithm”, “algoritm”) etc.

If the two strings are equal, we just count the number of mismatches at each index in the two strings.

Otherwise, we check if the shorter string is a sub-sequence of the longer string except one character. In this case we calculate the number matching characters which should be equal to the length of the shorter string.

Here is the Java implementation of the above approach. The time complexity would be linear O(n).

# How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple.
• Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
• Do the following until we reach the end of any sequence.
• If both the elements are same, increment both indices.
• Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

# Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
• One array stores the maximum element seen so far from the left.
• Second array stores minimum element seen so far from the right

For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4]

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above.

# Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements,

How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?

Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is “Yes” because 9 is present at index 0, and 3

2. A = [10, 0, 10, 20, 30], K = 1
The answer is “No” because there are no duplicate elements at a distance less than or equal to 1

A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.

Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it’s most recent index as it’s value. Here are the steps.

• For each element in the array
• Store the element and it’s index in the map if does not exist already.
• Check if the difference between the recent index and current index is less than K.
• If so return true.
• Otherwise update the map with recent index

This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.

# Mirror image of a binary tree

Given a binary tree, how to convert it to it’s mirror image?
For example consider the following binary tree and it’s mirror image.

Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps

1. If root is NULL, simply return
2. Invert the left sub tree
3. Invert the right sub tree
4. Swap left and right sub trees.

Here is the C++ code which implements the above algorithm. It runs in O(n) time.

# Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?

For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()

We have a simple solution to this problem by using recursion. We design this method as follows.

It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.

As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.

Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.

When we don’t have any left or right braces remaining, we can print the contents of the buffer.

Here is the Java implementation.

# Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree.
A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

 1   / Symmetric  2   2 1   / Asymmetric  2   3 1     /     2   2  Symmetric   /       3       3

We can design a recursive algorithm like the following.

1. An empty tree is a symmetric tree.
2. At each node we check the following
1. If the left value and right value are same
2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
3. If all the above conditions are satisfied then the tree is symmetric.

Here is the C++ implementation of this.

# Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

1
/
2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.

# Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

3
/
2    4
/
1        5

We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?

The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

# Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

1          1               1             1
/                       /
2   3          2           2                 2
/
3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it’s left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it.

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.