String rotation

Given a string of length N, rotate the string by K units. Eg. rotation of abcdef by 2 units will result in cdefab.

Solution approaches:-
1) Using a temp Array
2) 1 shift at a time 
3) Juggling algorithm - uses GCD(N,K) outer loop and inner loop till cycle is encountered
4) Gries algorithm - divide and conquer
5) Reversal algorithm - revert individual blocks and then revert the full string
 
Links:-
Source - http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf
Solution - http://www.geeksforgeeks.org/archives/2398
Solution - http://www.geeksforgeeks.org/archives/2878
Solution - http://www.geeksforgeeks.org/archives/2838
Solution and Performance - http://www.drdobbs.com/article/print?articleId=232900395&siteSectionName=parallel
 
Juggling algorithm explanation:-
Taken from http://eli.thegreenplace.net/2008/08/29/space-efficient-list-rotation/

Now, are you asking yourself "Just when will the process come back to x[0], and how many elements will have been moved by that stage ?". So did I, and the answer turns out to be an exciting application of the greatest common divisor (GCD) function.

In the first iteration, the "juggling pointer" jumps i elements at a time and stops when it reaches 0. How many steps will this take ? Ignoring the modulo for a moment, To reach 0, the pointer must be a multiple of n, so 0 will be reached at an index that is a multiple of both i and n. The first such multiple, in fact.

The first multiple (also known as LCM – least common multiple) is easy to compute from the GCD.

The amount of steps is lcm(n, i) / i. This is n / gcd(n, i). Therefore, in each iteration, n / gcd(n, i) elements will be rotated. The next iteration will pick up at x[1], an keep hopping in steps of i from there, moving another n / gcd(n, i) elements. In special cases, like when n and i are coprime, the first iteration will run over all the elements in the vector, without the need for a second one.

In any case, the whole process will always make n steps in total, moving all the elements to their correct positions.

Shuffling

Q: Given an array, print a random permutation of it such that each permutation is equally likely.

• The first approach is to use a random number generator to generate a value between 0 - 1 and associate each element of the array with a random value. Now sort the array based on these random values associated with the array elements.
• The second approach is to iterate over the array and swap the current element with another randomly selected element - Knuth-Fisher-Yates algorithm.
• Care should be taken so that we do not perform biased shuffle as explained in the following blog entry http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html by Jeff Atwood

Java code for the second approach is given below. The biasedShuffle and knuthShuffle methods are called 100000 times each to gather statistics and to further corroborate the explanation by Jeff.

 

Repeating substring

Q: Given a string S find the smallest sub-string X such that S = (X)+, i.e. S is a repetition of one or more X's.

Soln approach: 

• Iterate string from start to end keeping 2 pointers pointing to certain indexes in the string
• The first one indicating endIndex of the sub-sequence X found till now
• The second one indicating the index with which we must compare the character read in the next iteration
• Update both the indexes in each iteration based on whether the character read matches the sub-sequence 
• At the end X will be the sub-string from 0 to the first index mentioned in first point above

Java code:

Array Product

Q: Given an unsorted array of I of N integers, find an array O of N integers such that O[i] is the product of all integers in I except I[i]. Solve without using division.

Soln approach: 
1. Break the product into two parts as O[i] = (I[0] * I[1] * ... * I[i-1]) * (I[i+1] * ... * I[N-1])

2. Calculate first part by iterating over I from 0 to N-1
3. Multiply the values from step 2 with the second part by iterating over I from N-1 to 0

Java code to do this: