Monday, October 27, 2014

Reversing a linked list in groups of given size

Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k.
For example consider the following diagram of input and output linked lists for k = 3.

There are no tricks involved in the solution for this problem. It is just an implementation challenge where we have to carefully manipulate pointers to achieve the desired result.

Here is the strategy. The first step is to subdivide the list into chunks of size k. The last chunk maybe less than size k (depends on whether the length of the linked list is a multiple of k).

Keep a reference to the beginning of the sub-list, and traverse through k nodes.
Reverse the sub-list and re-arrange the begin and end pointers for the reversed sub-list.

The following diagram might give an overview of the process.
Here is the C++ implementation including recursive as well as iterative implementation.
We can consider the following test cases to test the program.
  • An empty/NULL list
  • List with just one node
  • List with multiple of k size
  • List with non-multiple of k size
  • Arbitrary list with k = 0, k= 1, k= length(list)
  • Any combination of the above.

Thursday, October 16, 2014

How to check if a given number is Fibonacci number

How to check if the given number is a Fibonacci number?

A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers.

Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...

If a number is given, a straight forward way to check if it is a Fibonacci number is to generate the numbers one by one until we get the required number or greater than that.

Here is the python code do that.

One more approach is based on a property of Fibonacci numbers
If 5*x2+4 or 5*x2-4 (or both) is a perfect square, we can conclude that it is a Fibonacci number. 

The C++ code is given below.


Tuesday, October 14, 2014

Finding equal sum index

Given an array of numbers, find an index such that the sum of numbers to the left is equal to the sum of elements to it's right. If there are no elements to the left or right, the sum is considered to be zero.

This problem is from Hackerrank. Click here to solve this problem on your own.


A simple example will be {1,2,1}, at index 1, the left and right sum is 1.

One obvious approach to solve this problem can be as follows.

For each index, find the left sum and right sum and check if they are equal. This approach takes O(n2) time.

Let us look at some other method which uses some extra space to reduce the time complexity.

Build a prefix sum array which keeps track of the sum all the elements up to each index. 


For the above example, the prefix sum array is {1,3,4}
 

The last element of this array indicates the sum of all elements in the original array.

Now, for each index i, we can find the left sum in prefix_sum[i-1] and right sum in total_sum - prefix_sum[i] which can be found in O(1) time. So this algorithm takes O(n) time.

Below Python/C++ code is provided which implements above. 


The base cases are

  • If the array contains zero elements, we cannot find such an index
  • If the array has just one element, we can always find such an index.

Wednesday, October 8, 2014

Number of deletions needed to make anagrams

Given two strings, how do we find the number of characters to be deleted from both the strings in order to make them anagrams.

Two words are said to be anagrams if one word can be formed by re-arranging the letters of another word. For example the words "TAN" and "ANT" are anagrams.

Given two words "clean" and "lion", we need to delete 5 characters from both the strings, {c,e,a} from the first and {i,o} from the second.

Let us discuss the approach to solve this problem.

If two words are anagrams, they both have same set of characters along with their counts. So to make two random words as anagrams, we have to delete all the characters that are present in one word but not in the other word.

To do this 
  • We first create the frequency table of each character present in the first word.
  • Next we iterate through each character in the second word, and try to find it in the frequency table.
    • If there is a non zero count for that character, we decrement it.
    • Otherwise we need to delete the character.
  • After processing all the characters in the second word, we need to delete if there are any extra characters present in the table.

Here is the Python program which implements the same.