Java Data structure questions

Note : These are very useful Data Structure and algorithms questions and their java solutions.

1) Question : Reverse print the Single Linked List

      Call: ml.printReverse(ml.getHeader());
   
      public void printReverse(Node node)
{
if(node == null)
return;
else
printReverse(node.next);
System.out.println(" [ "+node.data+" ]");
}  

2) Question : Print alternative nodes in a linked list.

        call: ml.printAlternative(ml.getHeader());
        method:
        public void printAlternative(Node node)
        {
           if(node == null)
    return;
           System.out.println(" [ "+node.data+" ]");
           if(node.getNext() != null)
    printAlternative(node.next.getNext());
      }

3) Question : Reverse a Single Linked list

      Call : ml.setHeader(ml.reverseList(ml.getHeader()));
  
     private static Node reverseList(Node header)
     {
       
        Node currNode, prevNode,nextNode;
        prevNode = header;
        currNode = header.next;
        while(currNode != null)
       {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
           
        }
        header.next = null;
        header=prevNode;
       
        return header;
     }

4) Question : Kth element from last.

       Call: ml.kthElementFromLast(2);

        public void kthElementFromLast(int k)
        {
         Node n=this.getHeader();  // natural pointer
         Node p=this.getHeader(); // k pointer
    
         for(int i=1;n !=null;i++)
         {
     n=n.next;
     if(i>k)
     p=p.next;
         }
            System.out.println(" [ "+p.data+" ]");
        }

5) Question:  Swap alternative node in a linked list

          
        public void swapAlternate(Node head)
        {
          Node n=head;
             Node tmp,p;
             if(this.getListSize() > 1)
             {
         this.setHeader(n.next);
         while(n.next != null)
            {
        tmp=n;
        p=n.next;
        n.next=p.next;
                p.next=n;
                tmp=n.next;
                if(tmp ==null )
                     break;
                if(tmp.next !=null)
                        n.next=n.next.next;
                n=tmp;
                    }
            }
            else
          System.out.println("Does not qualify for alternate swap");
         }    

 6) Question : Adding Nodes to Single Linked list using Insertion Sort .

          public void addInsertSort(int dataValue)
          {
                Node temp=new Node(dataValue);
                if(this.getHead() != null)
               {
                    Node current = this.getHead();
                     while (current.getNext()!= null)
                    {    
                         if( current.next.getData() > dataValue)
                             break;
                         current=current.getNext();
                     }  
                     temp.next=current.next;
                     current.setNext(temp);
             }
             else
              {   head=temp;      }
             listSize++;
          }

  7) Question : get Median from a Single Linked list .

            public int getMedian()
            {
                     int n=getListSize();
                     int count=0;
                     Node current=this.head;
                     if(n==1)
                           return current.data;
                     if(n%2==0)
                    {
                             for(;count<(n/2-1);count++)
                                        current=current.next;
                              return((current.getData()+current.next.getData() )/2);
                     }
                     else
                     {
                                  for(;count<n/2;count++)
                                               current=current.next;
                                  return current.getData();
                   }
            }
    

        8) Question : Given an array of numbers, arrange them in a way that yields the largest value.

                 For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value.
                For  {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.
               Approach :
                      Given two numbers X and Y, how should myCompare() decide which number to put first – we compare
                           two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y).
                     If XY is larger, then X should come before Y in output, else Y should come before.
              --------
              private static boolean compare(int a, int b)
              {
                           int i =Integer.parseInt(Integer.toString(a)+Integer.toString(b));
                           int j =Integer.parseInt(Integer.toString(b)+Integer.toString(a));
                           if(i>=j)
                                   return true;
                           else
                                    return false;
            }
            ------------------- O(n2) complex solution ------
             private static String bigNumInSet(int a[])
             {
                    String result="";
                    for(int i=0;i<a.length;i++)
                   {
                      for(int j=i+1;j<a.length;j++)
                     {
                       if(!compare(a[i],a[j]))
                      {
                            int tmp=a[i];
                            a[i]=a[j];
                            a[j]=tmp;
                       }
                   }
                 }   
                 for(int k=0;k<a.length;k++)  // To know the progresss
                 {    result+=Integer.toString(a[k]);
                          System.out.println(a[k]+ " Result now:"+result);
                 }
                return result;
           }

9) Question : Can you implement Enqueue Dequeue operations of Queue with Stack ?

        Approach : We need at least 2 stacks to implement a Queue like functionality.

         1) S1, -- PUSH to S1 for all Enqueue operations.
         2) S2, -- Check empty stack of S2 , if so load S2 by popping all element from S1 to S2.
         3) S2 -- if not empty , POP S2 for every de-queue operation. 

10) Question: Finding a decimal equivalent for a ROMAN number.

      The difficulty here is to find 4 - IV , 9-IX like numbers. One way of to get it is ...
              1) Load numbers in a Hashmap for O(1) complexity for matching.
              2) Use a logic to find difficult patterns like 4, 9 , 90 etc.
       ----------------------
           // Test using the Hashmap
        HashMap guide = new HashMap();
       
        guide.put("I","1");
        guide.put("V","5");
        guide.put("X","10");
        guide.put("L","50");
        guide.put("C","100");
        guide.put("D","500");
        guide.put("M","1000");
       ---------------------------------------------
      private static int getDecimal(String roman,HashMap hm)
      {
        int result=0;
        int n=roman.length();
        for (int i=0;i<n;i++)
        {
            int currentDigit=Integer.parseInt((String)hm.get(roman.substring(i, i+1)));
            if(i < n-1)  // Decrease logic never go behind last but one digit
            {
                int nextDigit=Integer.parseInt((String)hm.get(roman.substring(i+1, i+2)));
                if(currentDigit >= nextDigit)
                            result += currentDigit;
                else if( ((currentDigit == 1)&& (nextDigit==5 || nextDigit == 10))
                        || ((currentDigit == 10) && (nextDigit==50 || nextDigit == 100)) 
                        || ((currentDigit == 100)&& (nextDigit==500 || nextDigit == 1000)) 
                        )
                        result -= currentDigit;   
                     else
                     {     return 0;
                     }
            }
            else
                result += currentDigit;   // At last just add what ever digit it is
        }
         return result;
      }
      -------------------------------------------------------