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

A memory Q here..

In file1.c
we have static int i = 5;
and int *ptr = &i;

now value of ptr is written in some file say abc.txt

now file2.c (another program) opens abc.txt
read the value

and print the value loacted at dat adress say
what will be the o/p????


example i = 5;
ptr = &i; ptr has now 0xABFF

0xABFF is written in abc.txt

file2.c opens the abc.txt and read the value 0xABFF

now print the value present at this address
waht it will print????



ANSWER:

A program has nothing to do with RAM but an address space available to it. That is, total amount of memory it can index (on 32 bit systems 2^32). Program is written at the lower level to hold addresses (any of these 2^32 minus some reserved for kernel) within this range irrespective of the amount of RAM you have. Program assume it has and can have whole addresses only for itself. OS and CPU help to map this wide range of addresses to the amount of available RAM in your computer. Thus, the address your pointer holds is an address in this address space (called virtual address).

Even if the same program runs twice your pointer may not be the same (with same value) next time due to various environmental (and your program logic) reasons.

There are programs that store addresses of objects in virtual memory and the links between these objects to a file. But prior to writing they change these addresses to file offsets (thinking now this file to be memory.) Converting memory pointers (addresses) to file offsets and fro is termed 'pointer swizzling.' These programs are in general called 'object stores', and object-oriented databases are on genre of object stores.

The variable being static makes no difference, the code produced by your program may be relinkable and reloadable (relocatable code.)

Continue

Reverse a Singly Linked List.

Reverse a singly linked list :

public void reverse()
{
Node current = head;
head = null ; //set head to null
while(current != null)
{
Node save = current;
//Interchange the pointers
current = current.next;
save.next = head;
head = save;
}
}

Continue

Chasing Dogs.

There are four dogs, each at a corner of a large square.
Each of the dogs begins chasing the dog clockwise from it.
All of the dogs run at the same speed. All continuously
adjust their direction so that they are always heading
straight toward their clockwise neighbor. How long does it
take for the dogs to catch each other? Where does this
happen?

Solution :

To make things easy, let’s say the square is 1 mile on each
side, and the dogs are genetically enhanced greyhounds that
run exactly 1 mile per minute. Pretend you’re a flea riding on
the back of Dog 1. You’ve got a tiny radar gun that tells you how
fast things are moving, relative to your own frame of reference
(which is to say, Dog l’s frame of reference, since you’re holding
tight to Dog l’s back with five of your legs and pointing the
radar gun with the sixth). Dog 1 is chasing Dog 2, who is
chasing Dog 3, who is chasing Dog 4, who in turn is chasing
Dog 1. At the start of the chase, you aim the radar gun at Dog
4 (who’s chasing you). It informs you that Dog 4 is
approaching at a speed of 1 mile per minute.
A little while later, you try the radar gun again. What
does the gun read now? By this point, all the dogs have
moved a little, all are a bit closer to each other, and all have
shifted direction just slightly in order to be tracking their
respective target dogs. The four dogs still form a perfect
square. Each dog is still chasing its target dog at 1 mile per
minute, and each target dog is still moving at right angles to
the chaser. Because the target dog’s motion is still at right
angles, each chasing dog gains on its target dog at the full
running speed. That means your radar gun must say that Dog
4 is still gaining on you at 1 mile per minute.
Your radar gun will report that Dog 4 is approaching at
that speed throughout the chase. This talk of fleas and radar
guns is just a colorful way of illustrating what the puzzle
specifies, that the dogs perpetually gain on their targets at
constant speed.
It makes no difference that your frame of reference
(read: dog) is itself moving relative to the other dogs or the
ground. One frame of reference is as good as any other. (If
they give you a hard time about that, tell ‘em Einstein said
so.) The only thing that matters is that Dog 4 approaches you
at constant speed. Since Dog 4 is a mile away from you at the
outset and approaches at an unvarying 1 mile per minute,
Dog 4 will necessarily smack into you at the end of a minute.
Fleas riding on the other dogs’ backs will come to similar
conclusions. All the dogs will plow into each other one
minute after the start.
Where does this happen? The dogs’ motions are
entirely symmetrical. It would be strange if the dogs ended
up two counties to the west. Nothing is "pulling" them to
the west. Whatever happens must preserve the symmetry of
the original situation. Given that the dogs meet, the collision
has to be right in the middle of the square.

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

Remove Duplicates from a String.

Given a string of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed)

Idea for an O(n) solution :

Let’s start with ['a','b','a','c','a','a','d','b','c']
[i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)
1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
['a',i:j:'b','a','c','a','a','d','b','c'] – [1,0,0,0]
2nd character is ‘b’, same procedure as before
['a','b',i:j:'a','c','a','a','d','b','c'] – [1,1,0,0]
third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
['a','b',j:0,i:'c','a','a','d','b','c'] – [1,1,0,0]
fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
['a','b','c',j:0,i:'a','a','d','b','c'] – [1,1,1,0]
fifth and sixth character are handled like the third
['a','b','c',j:0,0,0,i:'d','b','c'] – [1,1,1,0]
seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
['a','b','c','d',j:0,0,0,i:'b','c'] – [1,1,1,1]
last two are like third case.
['a','b','c','d',j:0,0,0,0,0]:i – [1,1,1,1]
i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.
Code :

public static void main(String[] args) {
char[] a = {‘a’,'b’,'a’,'c’,'a’,'a’,'d’,'b’,'c’};
boolean[] ascii = new boolean[256];
int j=0;
for(int i=0;i<255;i++){
ascii[i] = false;
}
for(int i=0; i {
if(ascii[a[i]] == false)
{
ascii[a[i]] = true;
a[j] = a[i];
if (i != j)
{
a[i] = ‘0′;
}
j++;
i++;
}
else if (ascii[a[i]] == true)
{
a[j]=’0′;
a[i]=’0′;
i++;
}
}

Continue

Loop in Singly Linked List.

I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm”

Solution with – O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}

Continue

Lowest Common Ancestor in a Binary Search Tree.

Given the values of two nodes in a binary search tree, we need to find the lowest common ancestor. You may assume that both values already exist in the tree.

I/P : 4 and 14

O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 <>

    private static int LCA(Node root, int x, int y){

       /* If we have reached a leaf node then LCA doesn't exist

          If root->data is equal to any of the inputs then input is

          not valid. For example 20, 22 in the given figure */

       if(root==null || root.data==x || root.data==y){

           return -1;

       }

       /* If any of the input nodes is child of the current node

       we have reached the LCA. For example, in the above figure

       if we want to calculate LCA of 12 and 14, recursion should

       terminate when we reach 8*/

       if(root.right != null && (root.right.data==x || root.right.data ==y)){

           return root.data;

       }

       if(root.left != null && (root.left.data==x || root.left.data ==y)){

           return root.data;

       }



       if(root.data > x && root.data < y){

           return root.data;

       }

       if(root.data > x && root.data > y)

       {

           return LCA(root.left, x,y);

       }

       if(root.data < x && root.data < y){

           return LCA(root.right,x,y);

       }

       return -1;

   }

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

Merge Sorted Linked Lists.

Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n)

Solution :

   public Node mergeList(Node a, Node b){
       Node result = null;
       if(a==null)
           return b;
       if(b==null)
           return a;

       if(a.data <= b.data){
           result =a;
           result.next = mergeList(a.next,b);
       }
       else
       {
           result =b;
           result.next = mergeList(b.next,a);
       }
       return result;
   }

Continue

MaxHeap and MinHeap Implementations in Java

Sometimes a code-segment is worth a thousand words. Understanding the MaxHeap and MinHeaps using Java code is very easy. Here is an implementation of both.

MaxHeap :

package bst;

import java.util.ArrayList;

import java.util.List;

public class BinaryHeap {

   //ArrayList to hold the heap

    List h = new ArrayList();

   public BinaryHeap(){



   }

   //Constructs the heap - heapify

    public BinaryHeap(int[] e) {

       for(int i=0; i<e.length;i++)

       {

           add(e[i]);

       }

   }

   private int intGet(int key){

       return new Integer(h.get(key).toString()).intValue();

   }

   public void add(int key){

       h.add(null);

       int k = h.size()-1;

       while (k>0){

           int parent = (k-1)/2;

           int parentValue = new Integer(h.get(parent).toString()).intValue();

           //MaxHeap -

           //for minheap - if(key > parentValue)

            if(key <= parentValue){

               break;

           }

           h.set(k,parentValue);

           k=parent;

       }

       h.set(k,key);

   }

   public int getMax()

   {

       return new Integer(h.get(0).toString()).intValue();

   }

   public void percolateUp(int k, int key){

       if(h.isEmpty())

           return ;



       while(k < h.size() /2){

           int child = 2*k + 1; //left child

            if(child < h.size() -1 &&

              (new Integer(h.get(child).toString()).intValue() <

               new Integer(h.get(child+1).toString()).intValue()    )){

               child++;

           }

           if(key >= new Integer(h.get(child).toString()).intValue()){

               break;

           }

           h.set(k,new Integer(h.get(child).toString()).intValue());

           k=child;

       }

       h.set(k,key);

   }

   public int remove()

   {

       int removeNode = new Integer(h.get(0).toString()).intValue();

       int lastNode = new Integer(h.remove(h.size()-1).toString()).intValue();

       percolateUp(0,lastNode);

       return removeNode;

   }

   public boolean isEmpty()

   {

       return h.isEmpty();

   }



   public static void main(String[] args) {

       BinaryHeap heap = new BinaryHeap(new int[] {2,5,1});

       while(!heap.isEmpty()){

           System.out.println(heap.remove());

       }



   }

}

MinHeap :

package bst;

import java.util.*;



public class MinHeap<E extends Comparable<E>> {

 List<E> h = new ArrayList<E>();



 public MinHeap() {

 }



 public MinHeap(E[] keys) {

   for (E key : keys) {

     h.add(key);

   }

   for (int k = h.size() / 2 - 1; k >= 0; k--) {

     percolateDown(k, h.get(k));

   }

 }



 public void add(E node) {

   h.add(null);

   int k = h.size() - 1;

   while (k > 0) {

     int parent = (k - 1) / 2;

     E p = h.get(parent);

     if (node.compareTo(p) >= 0) {

       break;

     }

     h.set(k, p);

     k = parent;

   }

   h.set(k, node);

 }



 public E remove() {

   E removedNode = h.get(0);

   E lastNode = h.remove(h.size() - 1);

   percolateDown(0, lastNode);

   return removedNode;

 }



 public E min() {

   return h.get(0);

 }



 public boolean isEmpty() {

   return h.isEmpty();

 }



 void percolateDown(int k, E node) {

   if (h.isEmpty()) {

     return;

   }

   while (k < h.size() / 2) {

     int child = 2 * k + 1;

     if (child < h.size() - 1 && h.get(child).compareTo(h.get(child + 1)) > 0) {

       child++;

     }

     if (node.compareTo(h.get(child)) <= 0) {

       break;

     }

     h.set(k, h.get(child));

     k = child;

   }

   h.set(k, node);

 }



 // Usage example

  public static void main(String[] args) {

   MinHeap<Integer> heap = new MinHeap<Integer>(new Integer[] { 2, 5, 1, 3 });

   // print keys in sorted order

    while (!heap.isEmpty()) {

     System.out.println(heap.remove());

   }

 }

}

Continue

LCA of two nodes in a Binary Tree

Ah, this question has bugged me a lot. Finally I have found an answer to this. Actually there are two standard ways of doing this :

a. Do a Euler Walk on the tree and get the RMQ algorithm to calculate the LCA – cool, but for Ph,D. Students.

b. Create two array/linked list/queue and store DFS path to both the nodes and store them in these arrays. The last match in these arrays will be LCA. This solution is more practical than the first one. But the problem is how to get the DFS paths efficiently in a non BST binary tree ? If you know how to do that, please let me know in the comments.

After some research, I found a way which is smart and easier to understand.

Lets take the following tree.

We want to find the LCA for nodes – 4 and 7. LCA would be 6.

Algorithm :

We want to find the LCA of two nodes a and b.

1. Call the method LCA recursively on the left and right sub-tree. If both calls return ‘1’, it means that the current node has the parent of the left and right child and hence current node is the LCA.

2. The node that gets a ‘1’ from either left or right sub-tree returns back 1 to the parent. This node is not the parent yet but he is in the right path.

3. We need to take care of a special care where a is the parent of b or vice versa. In this case, we return 2 from one side and 0 from the other.

Code :

public static int findAncestor(Node node, int a, int b){
       if(node==null){
           return 0;
       }
       //Recursive calls to left and right sub-trees
        int l = findAncestor(node.left, a,b);
       int r = findAncestor(node.right, a,b);
       if(l==1 && r==1) //We found the LCA
        {
           System.out.println("LCA - " + node.data);
       }
       if((l==1 && r==0) || (l==0 && r==1)){
           //We found one of the element under this parent
            return 1;
       }
       if((l==2 && r==0) || (l==0 && r==2)){
           return 2;
       }
       else  //when l==0 and r==0
        {
           int matchRoot = (node.data ==a || node.data ==b) ? 1 : 0 ;
           return (l + r + matchRoot);
       }
   }

Continue

Zero-One Array Shuffle

You are given a number (either 32 or 64 bit)containing some bit pattern (or numeric value). You have to place all the 0s in even position and 1s in odd position and if suppose number of 0s exceed the number of 1s or vice versa then keep them untouched. Generalize your solution for an N bit number.
It has to be done in O(n) time, without several single loops (only one pass) and O(1)space.
For e.g.
Input Number: 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1
output number: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1

Logic : We need to maintain two pointers – oddPtr which moves along the odd positions in the array and evenPtr which moves along the even positions. When we find an incorrect position, we swap this pointers and move along.

One interesting case is when one of the pointer moves past the last element, in that case, we have no way to compare the other pointer with. In this case, we simply swap one pointer with the other position.

public class ZeroOneArray {

      public static void main(String args[]){

          int[] a = {0 ,1 ,1 ,0 ,1 ,0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1};

          int oddPtr = 1;

          int evenPtr= 0;

          while(true){

              if((oddPtr > 0 && oddPtr < a.length-1)

                  && (evenPtr>=0 && evenPtr<a.length-1)){

                  //Incorrect position found for both odd and even pointers

                   if(a[oddPtr]!=1 && a[evenPtr] !=0)

                  {

                      //Swap the incorrect positions 

                       swap(a, evenPtr, oddPtr);

                      //Move both the pointers to two places.

                       oddPtr+=2; evenPtr+=2;

                  }

                  else

                  {

                      //Correct values at correct positions

                      //Just increment pointers

                       if(a[oddPtr] ==1)

                          oddPtr+=2;

                      if(a[evenPtr] ==0)

                          evenPtr+=2;

                  }

              }

              //This is the case where one of the pointers has reached the end

              //so there is no way to find a mismatch pointer

              //In that case, we simply swap odd with even and vice versa

               else if ((evenPtr>a.length-1) && (oddPtr+2 < a.length-1)) {swap(a, oddPtr, oddPtr+2); oddPtr+=2;}

              else if ((oddPtr>a.length-1) && (evenPtr+2 < a.length-1)) {swap(a, evenPtr, evenPtr+2); evenPtr+=2;}

              else{break;}

          }



          for(int i=0;i<=a.length-1;i++){

              System.out.print(","+a[i]);

          }



      }

      private static void swap(int[] a, int even, int odd){

          int tmp = a[even];

          a[even] = a[odd];

          a[odd] = tmp;

      }

}

Continue

Intersection of Two Linked Lists.

We have two linked lists which are merged at some point. We need to find the intersection.

This shape is popularly known as Y-Shape intersection also.

Finding of intersection can be done by several methods. Some of them are listed in this excellent article.

We will discuss a simpler approach which works by getting the difference of the counts of elements in two lists and performs at O(m+n) with O(1) complexity.

Algorithm:

1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

It is simple to code this if this concept is understood. Give it a try.

Continue

Check If the Singly Linked List is a Palindrome.

The list shows above is a palindrome and we need to check if it is indeed a palindrome. Among several approaches, the following is a simple and easy to understand method.

Algorithm:
1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half

Time Complexity O(n)
Space Complexity O(1)

Continue

Check If the Singly Linked List has a Loop

The list shown above contains a loop – from 5 its connected to 2. There are several incorrect and inefficient methods of finding a loop. The most efficient method is discussed here.

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm". Further Reading on various approaches.
This algorithm has – O(n) time complexity

// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
 if (slowNode == fastNode1 || slowNode == fastNode2) return true;
 slowNode = slowNode.next();
}
return false;
}

Continue

Check If Strings are Rotations of Each Other

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 Algorithm:

1. Create a temp string and store concatenation of str1 to
str1 in temp.
temp = str1+str1
2. If str2 is a substring of temp then str1 and str2 are
rotations of each other.

Example:
str1 = "ABACD"
str2 = "CDABA"

temp = str1.str1 = "ABACDABACD"
Since str2 is a substring of temp, str1 and str2 are
rotations of each other.

Continue

Measure 45 Minutes Using 2 Candles

A very famous Microsoft Interview question : You have two candles. Each burn for 60 minutes. How can you measure 45 minutes using this ?

Solution :

lay both the candles together on a horizontal surface, next to each other, but both pointing in opposite direction as shown….
<=======
=======>
now light both the candles….
when both the flames on both candles meet , exactly half an hour would hav passed…
now the candles should look like…
…..…|<===
===>|………
now rearrange the candles…
===>
<===
now wait until the flames meet…..
so that the total time elapsed will be 30 + 15 = 45 mins…
the above solution is assuming that the rate at which the candles burn doesnt change
with respect to its orientation – horizontal or vertical

OR
1.Light the first candle from both the sides and 2nd candle from one side.
2.1st canlel will finish in 30 min. while 2nd candle will be burnt half way.
3.Now light 2nd candle from both the sides. It will finish in next 15 min.
So we have calculated 45 minutes in all.

Continue

Matching Braces.

Write a function to generate all possible n pairs of balanced parentheses.
For example, if n=1
{}
for n=2
{}{}
{{}}

Solution : Beautiful use of tail recursion.

public class Parentheses {

   public static void main(String[] args) {

       generate("",0,0,3);

   }

   public static void generate(String s, int open, int close, int n){

       if(open==n && close==n){

           System.out.println(""+s);

           return;

       }

       if(close>open)

           return;



       if(open>=close && open<n){

           generate(s+"{",open+1,close, n );

       }

       if(close < open){

           generate(s+"}", open, close+1,n);

       }

   }

}

Continue

Zero-One Array Shuffle – Revisited.

Problem : Given an array of 0’s and 1’s. Arrange the array such that
all 0’s are placed in the front and 1’s are placed in the back. Do this in o(n)

Algorithm : Just check where the correct position of the 0 and 1 should be using two pointers. leftPtr runs from 0 to n and rightPtr runs backward from n to 0. When there is a inconsistency of 0 and 1 placement, we swap them.

public class ZeroOneArrayArrange {

  public static void main(String[] args) {

      int[] a = {1,1,0,0,1,1,0,0,0,0,1};

      int leftPtr=0;

      int rightPtr = a.length-1;

      for(;leftPtr<rightPtr;){

          if(a[leftPtr] == 0)

              leftPtr++;

          if(a[rightPtr]==1)

              rightPtr--;

          if(a[leftPtr]==1 && a[rightPtr]==0 && leftPtr<rightPtr) {

              swap(a,leftPtr,rightPtr);

          }

     

      for(int i=0;i<=a.length-1;i++){

             System.out.print(","+a[i]);

         }

  }

  private static void swap(int[] a, int even, int odd){

         int tmp = a[even];

         a[even] = a[odd];

         a[odd] = tmp;

  }



}

Continue