Sorted Linked List To Balanced BST

http://www.geeksforgeeks.org/archives/17063

Marker Interfaces

Marker interfaces are interfaces which do not define any functions. But by using the language capabilities (for e.g. reflection in java) you can have a certain capabilities if a class implements a marker interface.

for e.g. Suppose you have a marker interface 'MarkerInterface'

public interface MarkerInterface
{
    // Nothing here
}

Now you can check if any class implements the MarkerInterface and provide a functionality by doing something like this:

if(object instanceof MarkerInterface)
{
   // do something specific
}

These are a few interesting links that can tell more about Marker Interfaces:
http://en.wikipedia.org/wiki/Marker_Interface_pattern
http://geekexplains.blogspot.com/2009/10/marker-interface-in-java-what-why-uses.html
http://www.coderanch.com/t/409760/java/java/Marker-Interface
http://www.jguru.com/faq/view.jsp?EID=224126

And of course you can google to find out more..

Construct binary tree given its inorder and preorder traversal

Construction of Binary tree given its inorder and preorder traversal.

 public static Node construct(String preorder, String inorder, int start, int end, int [] preorderIndex)
 {
  if(start > end)
   return null;
  
  Node root = new Node(preorder.charAt(preorderIndex[0]));
  
  ++preorderIndex[0];
  
  int inorderIndex = inorder.indexOf(""+root.data);
  
  root.left  = construct(preorder, inorder, start, inorderIndex - 1, preorderIndex);
  root.right = construct(preorder, inorder, inorderIndex + 1, end, preorderIndex);
  
  return root;
 }
  
 public static void main(String[] args) {
  
  String preorder = "ABCDEFG";
  String inorder  = "GFEDCBA";
  
  // We use this as a reference object, so that we pick the correct value from preorder array during
  // recursion. This could be done by having a static variable as well.
  int [] preorderIndex = new int[1];
  
  Node root = CodeSamples.construct(preorder, inorder, 0, preorder.length() - 1, preorderIndex);
                // Verify if it build correctly
  BinaryTree.preorderTraversal(root);
  System.out.println();
  BinaryTree.inorderTraversal(root);
  
 }

For explanation of the approach and other ways of doing it, visit this link: http://www.geeksforgeeks.org/archives/6633

Adding two linked lists

Given 2 singly linked lists which have single digit data, add the two lists and return a new list.

For e.g.

list1: 4->5->5->9->8
list2:      2->3->1->1

Output should be: 4->7->9->0->9

Approach 1: One of the approach can be to reverse both the linked list and then add node by node. In that case you will need to reverse the output list as well.

Approach 2: The other approach is to put the linked lists in the stack. This avoids the need to reverse the lists.

 
public static Node addLinkedLists(Node head1, Node head2)
 {
  if(head1 == null)
   return head2 != null ? head2 : null;
  
  if(head2 == null)
   return head1 != null ? head1 : null;
  
  Stack<node> s1 = new Stack<node>();
  Stack<node> s2 = new Stack<node>();
  Stack<node> s3 = new Stack<node>();
  
  Node list1 = head1;
  Node list2 = head2;
  
  while(list1 != null)
  {
   s1.push(list1);
   list1 = list1.next;
  }
  
  while(list2 != null)
  {
   s2.push(list2);
   list2 = list2.next;
  }
  
  int carry = 0;
  
  while(!s1.empty() &amp;&amp; !s2.empty())
  {
   int total = carry + s1.pop().data + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s1.empty())
  {
   int total = carry + s1.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  while(!s2.empty())
  {
   int total = carry + s2.pop().data;
   Node n = new Node(total%10);
   s3.push(n);
   carry = total/10;
  }
  
  Node result = s3.pop();
  Node retHead = result;
  
  while(!s3.empty())
  {
   Node n = s3.pop();
   result.next = n;
   result = n;
  }
  
  return retHead;
 }

Both approaches have similar run time complexity but the stack based approach requires more space.

Initialization-on-demand holder idiom

Almost everyone knows how the singleton pattern works. It looks something as follows:

class Singleton
{
private static Singleton _instance;

private Singleton(){ }

public Singleton getInstance()
{
   if(_instance == null)
  {
     _instance = new Singleton();
  } 

  return _instance;
} 

} 

This code would won't correctly in case of an multi-threaded environment. For it to work in a multi-threaded environment you will add some synchronization code.

However I came across this new way to assure singleton instance in Java. It is called Initialization-on-demand holder idiom. You can read about it here: http://en.wikipedia.org/wiki/Initialization_on_demand_holder_idiom

It relies on the defined initialization phase of execution within the JVM.