tag:blogger.com,1999:blog-72118647754839833952017-04-28T21:34:19.523+05:30Problem solving with programmingThis blog will be migrated to new domain www.letuscode.in. For latest updates check out this new URLRavi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.comBlogger211125tag:blogger.com,1999:blog-7211864775483983395.post-73192898309874117122015-09-16T13:01:00.002+05:302015-11-27T18:02:03.592+05:30Migrating to new domain
Dear Users,
Thanks for your patronage.
I am migrating this blog to my new domain www.letuscode.in .
So Problem solving with programming is now "Letuscode.in" .
I will post the latest updates on this new blog from now on.
I am also planning to migrate all the posts from my old blog to this new blog.
All the posts from this blog are migrated to the new blog.
Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-71531330918481534072015-08-24T11:46:00.001+05:302015-08-24T11:46:14.566+05:30How 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 Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-53784775431733458452015-08-20T11:57:00.001+05:302015-08-20T11:57:59.416+05:30Finding 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] Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-67731039642299469402015-08-12T10:56:00.001+05:302016-08-20T08:24:21.480+05:30Minimum number of squares formed from a rectangle
Given a rectangle of some length and width, How do you divide them into minimum number of equal sized squares? This is a problem from Codechef.
For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.
So what is the logic behind this?
The length and width should be Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-56125592738887775842015-08-10T10:56:00.001+05:302015-08-10T16:22:06.067+05:30Ambiguous permutations
Given a permutation of numbers from 1 to N, We can represent it in two ways.
For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.
Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index 'Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-50072315433536492402015-08-07T10:30:00.000+05:302015-08-07T10:30:54.383+05:30Duplicate 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 Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-21120428092585099332015-08-03T11:05:00.000+05:302015-08-03T11:05:46.093+05:30Mirror 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
If root is NULL, simply return
Invert the Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-60825067444467827842015-07-20T10:49:00.003+05:302015-07-20T10:49:53.341+05:30XOR of all sub arrays
Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?
For example let us consider the array [1, 2, 3], all possible sub-arrays are
XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3
And the result XOR[1, 3, 0, 2, 1, 3] = 2.
Brute force solution:
From the above example, you can see that an array Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-60377581396948909262015-07-16T07:35:00.000+05:302015-07-16T07:37:13.456+05:30Character to be removed to become a palindrome
Given a string, We have to find out by removing which character, it becomes a palindrome.
For example consider the string "racercar", the character 'r' at index 4 should be removed to become a palindrome.
The approach here is simple.
Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-72805788277524202262015-06-23T10:47:00.000+05:302015-06-23T10:47:44.534+05:30Generating 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. Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-41359831720469864572015-05-13T19:26:00.000+05:302015-05-13T19:26:21.205+05:30How does a radix sort work?
Radix sort is an integer sorting algorithm. As it's name indicates, it sorts a list of numbers based on the digits of the numbers.
It's a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.
Let us understand this algorithm using Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-7947340504167578022015-05-09T13:46:00.000+05:302015-05-11T08:46:25.377+05:30Check 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
Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-10515791437524336182015-05-01T13:38:00.000+05:302015-05-01T13:38:44.171+05:30Level 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 3An 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 Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-32472426188851128792015-04-30T10:53:00.000+05:302015-04-30T10:53:27.684+05:30Creating 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 5We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-10168771603875946642015-04-29T11:50:00.001+05:302015-04-29T11:50:42.934+05:30Checking 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
Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-77989102909510818192015-04-28T08:29:00.000+05:302015-04-28T08:29:54.680+05:30Finding the kth element in Binary search tree
Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on...
Solution:
We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-49050844061594175382015-04-27T13:15:00.000+05:302015-04-27T13:15:53.072+05:30Longest sub array with zero sum
Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements. The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.Can we do better than this?
Yes, by Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-87295289256316225602015-04-26T21:37:00.000+05:302015-04-26T21:37:12.901+05:30Programming puzzle - calculating product array
Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*...A[i-1]*A[i+1]...A[N]
That means each entry in the product array should contain product off all the elements except the one at that particular index.
For example let us consider the array [4, 2, 10, 5], the output should be {100, 200, 40, 80}.
The restriction here is that Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-57168512192881412062015-04-13T17:26:00.003+05:302015-04-13T21:09:06.254+05:30Infinite house of pancakes - Google Codejam 2015 Qualification round problem 2
Here is the link to the original problem. Let us try to simplify the problem statement a little bit.
There is a dinner house of infinite number of guests but finite number of pancakes. Each of them hold a plate which is either empty or has some pancakes in them. Every minute, one of the following actions can happen.
Each guest eats one pancake per minute.
The server will declare it as a Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-81300617594591021172015-04-13T05:44:00.000+05:302015-04-13T05:44:20.284+05:30Standing Ovation: Google codejam 2015 Qualification round problem
Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.
You can read the problem from this link. I will try to give the abridged problem statement below.
There are a group of N people in a stadium with their shyness Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-63302574115840262772015-04-03T10:27:00.000+05:302015-08-26T13:22:37.603+05:30Generating next bigger palindrome of a number
Given a number, how do we generate a smallest number which is greater than the given number and is a palindrome?
Consider the following examples
Input Output
3 4
9 11
13 22
767 777
594 595
898 909
999 1001
Here is the solution approach. This problem has multiple cases to be considered.
Case 1:
If all the digits in the number are '9', the Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-53293623028614001912015-03-31T12:54:00.000+05:302015-03-31T12:54:51.258+05:30Searching 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, Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-12505444360746960222015-03-30T13:24:00.000+05:302015-03-30T13:24:50.902+05:30Searching 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 Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-36154272068408925272015-03-20T17:03:00.001+05:302015-03-27T19:43:05.898+05:30Minimum 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
-----------------Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0tag:blogger.com,1999:blog-7211864775483983395.post-17634320359410238812015-03-19T18:12:00.001+05:302015-03-20T06:51:56.740+05:30Maximum 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 10 0 0 10 1 1 10 0 0 0The 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 Ravi Chandra Enagantihttps://plus.google.com/102378619467022544195noreply@blogger.com0