Card shuffle

Write a program to shuffle an pack of cards in the most efficient way. This question can be asked in several flavors.
Knuth Shuffle / Fisher-Yates Shuffle(Modified version by Durstenfeld) algorithm is the answer to all the trick questions. So how does this algorithm work ?
Fisher and Yates’ original method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness. Modern approach suggested by – Richard Durstenfeld is as follows:
To shuffle an array a of n elements:

for i from n - 1 downto 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Reduced time complexity to O(n), compared to O(n²) for the naive implementation. A sample java implementation :

01	import java.util.Random;

02

03	static Random rng = new Random();

04	public static void shuffle(int[] array) {

05	// i is the number of items remaining to be shuffled.

06	for (int i = array.length; i > 1; i--) {

07	// Pick a random element to swap with the i-th element.

08	int j = rng.nextInt(i); // 0 <= j <= i-1 (0-based array)

09	// Swap array elements.

10	int tmp = array[j];

11	array[j] = array[i-1];

12	array[i-1] = tmp;

13

}

14

}

Continue

25 Horses.

You have 25 horses. You have 5 tracks to race on. We need to find 3 fastest horses. How many minimum races required to find that ? We have no stop-watch. Horses run at same speed.

Now this puzzle is deceptive if you are not careful enough.

Solution :

Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each.
Have a race each for all the horses in eachset.
This makes it a total of 5 races, one for each set.

Now, have a race for the winners of each of the previous 5 races.
This makes it a total of 6 races.
But this step is tricky. We need to use the following logic
to identify horses for this race.

Observe the position of each horse in the 6th race and correspondingly
number the sets. i.e. the set of the winner of 6th race will be said to be set no. 1
while the set of the loser of the 6th race will be said to be set no. 5.

Now, possible candidates for the first three positions :
1. No horse from set 4 or set 5.
2. No horse from set 3, except for 1st Rank from this group.
3. No horse from set 2, except for 1st and 2nd Rank from this group
4. No horse from set 1, except for 1st, 2nd and 3rd Rank from this group

So now we have 6 candidates for top 3 positions. However, we know that the winner
of set 1 is the fastest horse in the whole group of 25 sets.

So now we have 5 candidates for the second and third position.
What better way to find out who’s who than to have a race of these 5 horses. Race them and this will solve our
problem in just 7 races.

Continue

Find two numbers in an array whose sum =X

Find if the sum of two elements in an array sum up to b (a number) with complexity of O(n)?

Input – Array : 1,2,3,4,5,6,7,8 and the sum is : 6

Output would be : {1,5} {2,4}

Solution : Here is the idea is to start from the first element of the array and keep a hashtable to store the potential pairs. We will check if sum – (a[i]) already exists in the Hashtable. If yes, we have a pair (a[i], value from hashtable) as the pair with the sum. If no, we store a[i] in the hashtable.

Here is a little dry run of array a= {1,2,3,4,5,6,7,8} and sum = 6.

6 – 1 = 5 — found in Hashtable H ? No – store it in H. H will contain (1)

6 –2 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2)

6 –3 = 4 – found in Hashtable H ? No – store it in H. H will contain (1, 2, 3)

6 –4 = 2 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (4,2)

6 –5 = 1 – found in Hashtable H ? Yes – now we have a pair (a[i] , found in H) – (5,1)

Why Hashtable ? because the lookup is always O(1) in a hashtable.

Continue

Find Duplicates from m + n elements in an array

Given an array of m+n elements in the range 1 to n ie(m elements are repeated). Find the duplicate elements.
Time Complexity: O(m+n)
Space Complexity: O(m)

Solution :

Since we know there are 1 to n elements, we can sort the array in O(n).
The first n elements will be the unique values and n to m will be the duplicates.
This is O(n+m) && no extra space required.

for (int i = 0; i < array.Length; i++)
{
if (array[i] != i + 1)
{
int t = array[array[i]-1];
array[array[i]-1] = array[i];
array[i] = t;
}
}

Continue

Small Algo

Write an algorithm to find whether a given number is a multiple of 3 or not without using modulo or division operation.

Ans: Convert the number to a string, thereby getting the decimal digits separately. Read those digits once by one and add all of them. If the sum is more than 10, repeat the procedure. Once the sum is less than 10, if it is 0, 3, 6 or 9, then the original number is divisible by 3.

Continue

Array Question

In an integer array all numbers occur exactly twice except for a single number which occurs exactly once..give an O(n) algorithm to find the number occurring only once.

Ans: Do bitwise XOR of all numbers. The result will be the number that occurs only once. The result in each position is the different number if the two bits are different, and 0 if they are the same.

public class Xor
{
public static void main(String args[])
{
int[] arr= {1,1,2,2,3,4,4,5,5};
int xOR = arr[0] ;
for(int i =1 ;i< arr.length; i++)
{
xOR = xOR ^ arr[i];
System.out.println( arr[i] + " —- " + xOR);
}
System.out.println(xOR);
}
}

Continue

Find an element in a sorted 2D Array.

You have a [n * n] array which is sorted both row wise and column wise. How do you find an element in this array in O(n) time ?

Solution: 1

1. Start from left bottom most cell.
2. If query is larger move right .
3. If query is smaller move up.
4. If you can’t move right or up and haven’t found the query yet, it means that the query does not exist.

Applying binary search for Rows and column may furthur reduce the complexity,,,

Continue

Maximum sub-sequence…

Question : Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.
Eg.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

The idea is to use Dynamic Programming and store the intermediate “good” sums in an auxiliary array. The right way is to define an array B[n] whose j-th element B[j] represents the best sum that has A[j] as the last element.

A simplistic java code looks like this :

public class maxSkip
{
public static void main(String args[])
{
.... int[] a = {3,2,5,10,7};
.... int j,mx=0;
.... int len = a.length;
.... int[] b = new int[len];

....b[0] = a[0]; if(len==1) mx = b[0];
....b[1] = a[1]; if(len==2) mx = max(b[0],b[1]);
....b[2] = a[2]+b[0]; if(len==3) mx = max(b[1],b[2]);

.... for(j = 3 ; j< len; j++)
.... {
........ b[j] = max(a[j]+b[j-2] , a[j] + b[j-3]);
.... }
.... mx= max(b[j-2], b[j-1]);
.... System.out.println("Max subsequence : " + mx);
}
public static int max(int a, int b)
{
......return(a>b?a:b);
}
}

Continue

Max contiguous sub-sequence.

This problem is called Maximum contiguous sub sequence sum problem.
Given an array which can contain both positive and negative numbers, find the maximum contiguous sub sequence sum.
For example in an array = {2, -3, 4, -5, 6, -3, 8}, it should return 11.

Algo :

Take the array, {2, -3, 4, -5, 6, -3, 8}
Compute the partial sums up to place i for all i, {2, -1, 3, -2, 4, 1, 9}
Subtract from each element the minimum that occurs earlier (or 0), {2, -1, 4, -1, 6, 3, 11}
Take the maximum, 11

Code:

public class maxSubSeq
{
public static void main(String args[])
{
....int[] a = {2,-3,4,-5,6,-3,8};
....int[] p = new int[a.length];
....//Compute partial sums
....for(int i = 0; i ....{
....if(i==0)
.......p[i] = a[i] ;
....else
.......p[i] = a[i] + p[i-1];
....}
....//Substract from each element in p, the minimum that occur
....//earlier (or 0)
....int min=0;
....for(int i=0; i< p.length; i++)
....{
....if(i==0)
....{
....if(p[i] > 0)
........min = 0;
....else
........min = p[i];

..... p[i] = p[i] - min;
...}
....else
... {
....if(p[i] < min)
.......min = p[i];
....... p[i] = p[i] - min;
}
}

//Maximum of the resulting p would be the maximum subsequence
java.util.Arrays.sort(p);
System.out.println("The maximum subsequence - " + p[p.length-1]);
}

}

Continue

N stack 1 Array

Implement N stacks using constant sized array(space). Until the array is completely filled, I should be able to push elements to any one of the N stacks.(i.e.)Do not reserve space for the stacks. And I should also be able to pop elements from any stack.

Sounds very tricky. The idea is :

Keep an array S of N pointer, where each S_i.top will point to the top of the corresponding stack. And one global pointer gptr, which points to the next free location in the array. Now follow the steps:

Now implement Push(stackToPush) and pop(StackToPop) as follows :

Push(x, Si) //pushing x in Stack Si.
{
if(gptr > sizeof(Arr))
{
// To Be Added -- explained below
}
Arr[gptr].data = x;
Arr[gprt].prev = Si.top;
Si.top = gptr;
gptr++;
}


Pop(Si)
{
T data = Arr[Si.top].data; //T is data type
Si.top = Arr[Si.top].prev;
return data;
}

I would suggest that you try a very detailed dry-run with a little visual aid for this.

Continue

Inorder successor ?

This is one of the nasty ones, if you don’t fully understand what “Inorder successor” is. The inorder successor is the next value in an inorder traversal of a binary search tree. So how do you find the inorder successor for the node U ?

Algorithm : If node U has a right sub-tree, then the successor is the left most descendent of the right sub-tree. Otherwise, find the first ancestor that has node U in the left sub-tree.

Pseudocode :

if(node->right)
if( ! node->right->left)
return node->right;
else
{
tmp = node->right->left;
while(tmp->left)
tmp = tmp->left;
return tmp;
}

Continue

Sorting Array of 0’s and 1’s

You are given an Array of N size. It contains 0 and 1 only. You have to arrange all 0s before all 1s (In the program you can’t travel more than once. Minimum complexity desired).

Idea : Move a pointer left, from the front, until it encounters a 1
Move a pointer right, from the end, until it encounters a 0
Swap the elements at the two pointers (if they haven’t crossed)
Repeat this for entire array – this is inplace and single pass.

Code :

public class swap01
{
public static void main(String arg[])
{
int[] a = {0,1,1,0,0,1,1,1,0};
int l =0;
int r= a.length-1;
while(l {
if(a[l] == 0)
{
l++;
}
else if(a[r] == 1)
{
r–;
}
else {
swap(a,l,r);
l++;
r–;
}
}
for(int i=0;i System.out.print(a[i] + ",");
}
private static void swap(int[] a, int l, int r)
{
int tmp = a[l];
a[l] = a[r];
a[r]=tmp;
}
}

Continue

Merge Two Sorted Arrays.

Problem : There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.

Code:

public class MergeSortedArrays {

   public static void main(String[] args) {

       int[] a = new int[] {3,6,10,12,56};

       int[] b = new int[8] ;

       b[0] = 9;

       b[1] =11;

       b[2] =36;

       //after this b looks like {9,11,36,0,0,0,0,0}

       // with enough space to accommodate 'a'

       //0 indicating a free space.

       int i = a.length-1; //a's length

       int k = b.length-1; //b's length

       //Starting point to the empty slots.

       int j = findCount(b) - 1;

       for(; k>0; k--) {

           if(j<0)

               break;



           if(a[i] > b[j])

           {

               b[k] = a[i];

               i--;

           }

           else

           {

               b[k] = b[j];

               j--;

           }

           print(b);

       }

       //Copy the leftovers which are already sorted.

       while(k>=0){

               b[k--] = a[i--];



       }

      print(b); //Final array is printed.

   }

   //Purely a debug method

   private static void print(int[] b){

       for(int x=0;x           System.out.print(b[x] + ", ");



       System.out.println("");

   }

   private static int findCount(int[] b)

   {   int i=0;

       while (b[i] != 0){

          i++;

       }

       return i;

   }

}

Continue