Stack with getMin operation in O(1) time

This is a famous interview problem where the candidate is asked to design a stack so as to get minimum of the current elements present in the stack in O(1) time. I think having an auxiliary stack is the most general solution.

Found the following link to do it without using extra space obviously with some constraint on the data present in the stack, nonetheless solution deserves an "aha"!
http://stackoverflow.com/a/687945

Longest matching pattern

Given two strings find the longest matching pattern such that the pattern in the first string and the second string are permutation of each other.

Eg. - 
S1 = “ABCDEFG”
S2 = “DBCAPFG”
Then the output should be DBCA (length 4)
Assume there are no repeating characters.

Solution -
The idea is to transform S1 into clusters of indices of S2. So, for the example above we will get
Cluster 1 - 3, 1, 2, 0
Cluster 2 - 5, 6

Now, for each cluster find the longest portion (window) that satisfies the following property - 

• Max - Min + 1 = No of Elements

The longest portion (window) of the cluster will represent the indices of S2 that are contiguous and since the cluster itself is a a contiguous portion of transformed S1, the final solution will be the characters in S2 at the indices represented by such longest portion.

To find the longest portion satisfying the above property, we can recursively implement it as shown below in method getMaxCommonWindow. The idea is to find the maximum window starting with the first element satisfying the above property and then recusively find the maximum window not starting with the first element. The greater of these two windows will be the desired longest portion.

Count the number of six digit numbers possible

The problem is to calculate the number of 6-digit numbers that you can create using the following scheme of things.

0-9 digits are arranged like a phone keypad.
1 2 3
4 5 6
7 8 9
   0

The 6-digit number cannot start with 0. A digit can follow any other digit in the 6-digit number only if both the numbers are in the same row or column.
For eg. in a 6-digit number:
2 can follow 0
0 can follow 8
9 can follow 7
5 can follow 4
4 can follow 1
1 can follow 7
...
...
9 cannot follow 5
1 cannot follow 6
0 cannot follow 1
...
...

The idea of the solution is to use dynamic programming. A possible implementation is given below. To further optimize we can do memoization.

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:

Sum of bits set

Q: Given a positive integer N calculate the sum of bits set for all the numbers from 0 to N.

I will be using divide and conquer for this. 

Fact: The sum of all set bits from 0 to (2 ^ n) - 1 is (2 ^ n-1) * n
This can be proved by induction or construction.

Approach:

1) Get the MSB location of the integer N, i.e. the left most bit which is set as 1, lets say it is X

2) Get the sum of all the bits till (2 ^ X) - 1 using the fact given above, lets say it is Sum

3) Now, add 1 for number (2 ^ X) to Sum

4) We are now left to calculate from (2 ^ X) + 1 to N. All these will have Xth bit set.
5) So add N - (2 ^ X) to Sum
6) Now we can solve for a smaller sub-problem using recursion. The numbers left are (2 ^ X) + 1 ..... N, with the Xth bit now turned off since we have already considered the Xth bit in step 5. This is equivalent to finding the sum of bits till N XOR (2 ^ X)

Code:
To get the MSB location we can again use divide and conquer to reduce the no. of steps.
http://graphics.stanford.edu/~seander/bithacks.html

Ideas taken from:
http://tech-queries.blogspot.in/2010/12/number-of-set-bits-till-n.html
http://code.rishibaldawa.com/count-all-set-bits-from-0-till-n-for-each-number

Duplicate & missing number

Q: In an unsorted array of first N natural numbers which has a duplicate number and a missing number, find the duplicate and missing numbers.

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Sum of N^2 numbers = n(n+1)(2n+1)/6

3. Since there are 2 unknowns we can create 2 equations using the above formulae to solve them

Soln approach: 

1. Sum of N numbers = n(n+1)/2

2. Multiplication of N numbers / n! = Duplicate/Missing

3. Again we can solve for the 2 unknowns using the above formulae

Both the above approach assumes that N^2 or N! can be held in an int/double etc without overflow. In Java we can make use of BigInteger but there is another approach to solve the problem using bit operators.

Soln approach:

Let Ai be the ith element of the array, 0 <= i < n

Let Bi be i+1

1. Find Duplicate XOR Missing = X

    - XOR all Ai and Bi

2. Find which rightmost bit is 1 in X = Y

    - X & ~(X - 1)

3. Partition A and B such that A1 and B1 has Y set and A2 and B2 does not have Y set

    - Iterate and use & operator over Y and elements of A and B

4. XOR elements of A1 and B1 = VALUE1

5. XOR elements of A2 and B2 = VALUE2

6. If A1.length > B1.length then VALUE1 = Duplicate and VALUE2 = Missing

    else VALUE2 = Duplicate and VALUE1 = Missing