Tuesday, March 31, 2015

Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it's neighbors, we need to find the given element.

For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5.

This is just an implementation problem with a trick. Here is the approach.
  • Start with first element, check if the current element matches, if so return it.
  • Otherwise increment the index by the absolute difference between current element and target element.
  • Repeat the above step until we find the element or reach the end of the array.
This algorithm runs in O(1) in best case. Example of the base cases
Searching for 10 in [1,2,3,4,5,6,7,8,9,10] or
Searching for 1 in [10,9,8,7,6,5,4,3,2,1]

Within One jump we reach the target element.

However this takes O(n) time in the worst case like the following
Searching for 2 in [1,1,1,1,1,1,1,1,2]

Here is the C++ implementation.

Monday, March 30, 2015

Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid.
The word can be formed in any of the 8 possible directions as shown below.

Here is how I solved this problem.

Write a function which takes the string to be searched, the starting coordinates, and the direction number (as shown above) as parameters.

bool search_grid(const char *word, int x, int y, int direction)

If the current letter matches, depends on the direction, we recursively invoke the same method for the next character in the string with modified coordinates.
If the current letter does not match, the word cannot be found in the given direction starting from the initial coordinates.

Here is the C++ program which implements the basic algorithm for the word match. This is not  a complete program. You may try writing a wrapper which finds the initial coordinates to start the word search (Find the the coordinates where the first letter of the word appears) and do some checks for base cases like empty string etc.

Friday, March 20, 2015

Minimum number after removing K digits

Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.

For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.

The solution is based on the following observation, consider the above case. 
Let us delete a digit from 234987
Deleted Digit - Result
2             - 34987
3             - 24987
4             - 23987
9             - 23487
8             - 23497
7             - 23498

If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.

What if all the digits are in ascending order? 

Let us walk through an example.
N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.

[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.]

Here is the C++ implementation of the above approach.

Thursday, March 19, 2015

Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it's row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row.

For example consider the following matrix.

0 0 1 1
0 0 0 1
0 1 1 1
0 0 0 0

The maximum number of 1s in any row is three which appear in the third row.

The general approach is to find the number of 1s in each row and update the maximum.

There are two ways to find the number of 1s.
  • One simple approach is to linearly search for first 1 and find the count of 1s. This will take O(n) time in worst case. So the overall time complexity would be O(n2).
  • Another faster method is to search for first 1 using binary search since each row is sorted. This will take only O(log n) time and the overall complexity would be O(n log n).
Even more efficient approach can be as follows.
  • Start with the right most element in the first row, keep counting the number of 1s until we reach zero. 
  • Move to the next row and start checking the elements from previous column
    • If the element is zero, just move on to the next row
    • Otherwise count the ones until we reach zero or the first column
  • Repeat the above step for all the rows. At the end, we get the maximum number 1s.
This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.
Here is the C++ implementation of the above. I have used the lower_bound() method from the standard library to find the left most occurrence of a 1. Look at my previous post to understand how this method works.

Tuesday, March 17, 2015

Type casting in C++ - Part 1

Type casting frequently arises in real life programming. This post concentrates on type conversion of fundamental data types. Type casting is the process of converting from one data type to another. In C++, type casting is automatic in some situations. These are called implicit conversions.

For example
char c = 'A';
int ch_code = c;

short s_val = 1024;
int i_val = s_val;
Here the value of "c" is automatically promoted to an int as we are assigning a smaller type into a bigger type. The second case is also similar. This is also called a promotion. There is no truncation in these cases. Other examples of this type include int to float/double, float to double, boolean to int etc...

Implicit type conversion also happen when a bigger type is assigned to smaller type. This might result in truncation/data loss if the source data which cannot fit in the destination type. Some compilers gives a warning when we are using such a conversion. This can be avoided by explicit conversion.
int ch_code = 97;
char ch = ch_code; // no data loss as 97 is within the range of char type; represents the character 'a'

float pi = 3.14159;
int i_pi = (int)pi; //decimal part is truncated; explicit type conversion
If the truncated integer value is bigger than the integer type, the behavior is undefined.

If a negative integer type is converted to a unsigned type, the resulting value would be 2's compliment bit representation interpreted as a positive integer.

For example the following code
short x = -32768;
unsigned short y = x;
Assigns a value of 32768 to y. The least value has become the greatest value in this case.

If you are converting an integer to boolean type, all non-zero value will be converted to 1 including negative and positive values which are considered true. 0 is considered false.
int x = -10;
bool b = x; // b is assigned 1, i.e true
x = 10;
b = x; //b is 1 here also
x = 0;
b = x; //b is 0,i.e false
In the later posts, we will look at type conversions between non fundamental data types like pointers and classes.

Friday, March 13, 2015

Right view of the binary tree

Given a binary tree, how do we print the right view of it?

For example, consider the simple binary tree below

 / \
2   3

The right view of this is 1, 3. Similarly consider one more example

          /  \
         2    5
        / \  
       3   4 

Right view for this tree contains 1, 5, 4.

This is similar to my last post which asks for the left view of the binary tree. We just need to make the following changes to the algorithms discussed in the earlier post.

In case of iterative solution, we need to add the right child first to the queue before adding the left child.

In the recursive approach, we need to first recurse on the right child. Below is the modified code.

Thursday, March 12, 2015

Alternate arrangement of two linked lists

Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging.

For example consider the two lists

1 -> 2 -> NULL
3 -> 4 -> NULL

The result should look like the following.

1 -> 3 -> 2 -> 4 -> NULL.

There is no logic required for this problem except arranging the links carefully. 

Just take two pointers to the two lists, keep adding the first node followed by the second node by advancing both the pointers at a time. 

Come out from the loop when we reach the end of any list.

Lastly copy the remaining nodes from the longer list to the result list.

Below is the C++ implementation of the same. The program can be run through the following test cases.
  1. Two empty lists
  2. One empty list and the other non-empty list
  3. Two lists are of equal length
  4. Two lists are of unequal length

Wednesday, March 11, 2015

Left view of a binary tree

Given a binary tree, how do we print the left view of it?

For example, consider the simple binary tree below

 / \
2   3

The left view of this is 1, 2. Similarly consider one more example

          /  \
         2    3
             / \
            4   5

Left view for this tree contains 1, 2, 4.

If the tree is completely left skewed or right skewed, the left view contains all the nodes like the following. For example

1                1
 \              /
  2            2
   \          /
    3        3

The left view for both of the above trees is 1, 2, 3.

We can solve this problem in two ways, one iterative and the other using recursion.

Recursive method:
In this approach to the traversal function, we send two additional parameters along with root node, one is the current level and another is maximum level. maximum level is a reference parameter which remembers it's value between the function calls. 
We compare the current and maximum level values, if the max level is less than current level we print the data at root node and update the maximum level. Recursively call the same function for the left and right sub-trees by incrementing the current level.

Iterative method:

We use the level order traversal method to print the first node in each level. While storing the nodes in the queue, we store a separator (NULL) node to distinguish between the levels.

Here is the C++ code which implements the above approaches.Both run in O(n) time complexity.

Tuesday, March 3, 2015

Maximum nesting depth of a paranthesis expression

Given a parenthesis expression, We have to find the maximum nesting depth.

For example: the expression ()((()))(()) has a maximum nesting depth of 3.
The expression ((()())) has a maximum nesting depth of 3.
Let us output -1 for an unbalanced expressions such as (())) or ()(

This is a simple problem that can be asked in different forms. One such example can be
Given a sequence of jobs executed by a machine. What is the maximum number of parallel jobs executed at any point of time. 
One more variation of this problem can be
Given a maximum capacity of a computer center, and a sequence of people arrived, how many people have to wait for their turn.
Check this question for details.  
Here is the simple O(n) solution for the original problem. 
  1. Take two variables depth and max_depth initialize them to zero.
  2. Increment depth if we see an open bracket and update the max_depth
  3. Decrement depth if we see a closed bracket and check if it is going negative.If it goes negative, the expression is unbalanced.
  4. Check if depth is zero. If it is not zero, then it is not a balanced expression.
  5. Return max_depth
With minor modifications to this algorithm, we can design an algorithm for the second variation also.

Here is the Python implementation.The time complexity for this O(n) and space complexity is O(1).

Monday, March 2, 2015

Longest path in a binary tree

Given a binary tree, how do we find the longest distance between any two nodes in it? Some times this is referred to as the diameter of the tree.
For example consider the below binary tree

The longest path in this tree is 1 - 2 - 3 - 5 - 8 - 6 - 7. In this example the longest path passes through the root node. Sometimes it may not pass through the root. Checkout the next example.
The longest path 27-28-24-36-42-59-55 does not include the root node.

Here is how we can find the longest path recursively. We know that the height of the binary tree is the longest path from the root node to any leaf node.(Read this post to know more). Diameter is the maximum of the following.

Height(left subtree) + Height(right subtree) + 1
Diameter(left subtree)
Diameter(right subtree)

Here is the C++ implementation of the above. This program calculates the number of nodes on the longest path. The time complexity for this solution is O(n2). For optimal implementation, you can checkout this post.