Wednesday, September 21, 2011

Amazon interview question: you have unsorted array[n] elements. the numbers in the array[n] occurs event times except one number occurs odd time. So, write an algorithm to find that number. Also explain its complexity too. (time and space) both. (On ALGORITHM)"


Logic: Do Xor on the elements.
public class MainClass {
public static void main(String [] args)
{
int []a = new int []{1,1,2,3,2,4,4,4,4,1,1,5,6,5,1,6,1};
int res =a[0];
for(int i =1 ; i<a.length; i++)
{
res = res^a[i];
}
System.out.println(res);

}
}

Java Class Loading


It’s good to know, how Java class loading works, when you have to develop in Java. Basic understanding of class loading process helps every Java developer to deal with several ClassLoader related Exceptions.

Class loader delegation

The loading of Java classes is performed by class loaders (CL), they are responsible for loading classes into the JVM. Simple applications can use the Java platform’s built-in class loading facility to load their classes, more complex applications tend to define their own custom class loaders.
The class loaders in Java are organized in a tree. By request a class loader determines if the class has already been loaded in the past, looking up in its own cache. If the class is present in the cache the CL returns the class, if not, it delegates the request to the parent. If the parent is not set (is Null) or can not load the class and throws a ClassNotFoundException the classloader tries to load the class itself and searches its own path for the class file. If the class can be loaded it is returned, otherwise a ClassNotFoundException is thrown. The cache lookup goes on recursively from child to parent, until the tree root is reached or a class is found in cache. If the root is reached the class loaders try to load the class and unfold the recursion from parent to child. Summarizing that we have following order:
  • Cache
  • Parent
  • Self
This mechanism ensures that classes tending to be loaded by class loaders nearest to the root. Remember, that parent class loader is always has the opportunity to load a class first. It is important to ensure that core Java classes are loaded by the bootstrap loader, whichguarantees that the correct versions of classes such as java.lang.Object are loaded. Furthermore it ensures, that one class loader sees only classes loaded by itself or its parent (or further ancestors) and it cannot see classes loaded by its children or siblings!
The picture illustrates the hierarchy of class loaders. Root loader is bootstrap class loader which has native implementation and cannot be instantiated by Java code.
The class loader delegation model

It is followed by extension class loader, which is primary responsibility to load classes from the extension directories and provides ability to simply drop in new JVM extensions, without requiring modification to the user’s classpath. The system or application class loader responsible for loading classes from the path specified by the CLASSPATH environment variable. This class loader will be returned by the ClassLoader.getSystemClassLoader() method.

Phases of class loading

The are three phases of concrete class loading: physical loadinglinking, and initializing.
The phases of class loading
  1. In in first phase of physical loading required class file will be searched in specified classpaths. If the file is found it is read and the bytecode is loaded. This process gives a basic memory structure to the class object, such concepts like methods, fields, and other referenced classes are not known at this stage.
  2. Linking can be broken down into three main stages, because it is complex phase:
    1. Bytecode verification through class loader, which executes a number of checks on the bytecodes.
    2. Class preparation. This stage prepares the necessary data structures that represent fields, methods and implemented interfaces that are defined within the class.
    3. Resolving of all the other classes referenced by a particular class. The classes can be referenced in a number of ways:
      • Superclasses
      • Interfaces
      • Field types
      • Types in method signatures
      • Types of local variables used in methods
  3. During the initializing phase any static initializers contained within a class are executed so that, static fields are initialized to their default values.
It is interesting, that class loading can be performed in a lazy manner and therefore some parts of the class loading process may be done on first use of the class rather than at load time.

Exceptions

The biggest challenge in dealing with class-loading problems is that problems rarely manifest themselves during the class-loading process but rather during the usage of a class later on. In following shown two class loading related exceptions, with potential causes
  • ClassNotFoundException
    • An archive, directory, or other source for the classes was not added to the class loader asked to load the class, or to its parent.
    • A class loader’s parent is not set correctly.
    • The wrong class loader is used to load the class in question.
  • NoClassDefFoundError
    • An archive, directory, or other source for the classes was not added to the class loader asked to load the class, or to its parent.
    • A class loader’s parent is not set correctly.
    • Symbolic links in a class are unaccessible by the containing class’s class loader, such as a child class loader.

Tuesday, September 20, 2011

LinkedList Implementation in java and basic operations like Insertion , deletion, modifying a node



package linkedlist;

public class Node<E> {
E data;
Node<E> next;

}




package linkedlist;

public class SinglyLinkedList<E> {
Node<E> start;
int size;

public SinglyLinkedList()
{
start = null;
size = 0;
}

public void add (E data)
{
insertAtLast(data);
}

public void insertAtLast(E data)
{
if(size == 0)
{
start = new Node<E>();
start.data = data;
start.next = null;
}
else
{
Node<E> currentNode = getNodeAt(size -1);
Node<E> tempNode = new Node<E>();
tempNode.data = data;
tempNode.next = null;
currentNode.next = tempNode;

}
size++;
}

public void insertAtFirst(E data)
{
if(size == 0)
{
start = new Node<E>();
start.data = data;
start.next = null;
}
else
{
Node<E> tempNode = new Node<E>();
tempNode.data = data;
tempNode.next = start;
start = tempNode;
}
size++;
}
public Node<E> getNodeAt(int pos) throws ArrayIndexOutOfBoundsException
{
Node <E>temp = start;
if((pos < 0 ) ||(pos > size))
{
throw new ArrayIndexOutOfBoundsException();
}

else
{
for(int count  = 0; count < pos; count++)
{
temp = temp.next;
}
}
return temp;

}
public void insertAt(int pos, E data)
{
if (pos == 0)
{
insertAtFirst(data);
}
else if(pos == size - 1)
{
insertAtLast(data);
}
else
{
Node<E> temp = getNodeAt(pos -1);
Node<E> newNode = new Node<E>();
newNode.data = data;
newNode.next = temp.next;
temp.next = newNode;
size++;
}
}

public Node<E> getFirst()
{
return getNodeAt(0);
}
public Node<E> getLast()
{
return getNodeAt(size -1);
}
public E removeAtFirst() throws ArrayIndexOutOfBoundsException
{
if(size <= 0)
{
throw new ArrayIndexOutOfBoundsException();
}

E data = start.data;
start = start.next;
size--;
return data;
}
public E removeAtLast() throws ArrayIndexOutOfBoundsException
{
if(size<=0)
{
throw new ArrayIndexOutOfBoundsException();
}
Node<E> temp =getNodeAt(size-2);
E data = temp.next.data;
temp.next = null;
size--;
return data;
}
public E removeAt(int pos) throws ArrayIndexOutOfBoundsException
{
if(( pos < 0 ) || (pos > size))
{
throw new ArrayIndexOutOfBoundsException();
}
Node <E> temp = getNodeAt(pos-1);
E data = temp.next.data;
temp.next=temp.next.next;
size--;
return data;
}
public int size()
{
return size;
}
public String toString()
{
StringBuilder string = new StringBuilder();
if(size == 0)
{
return "";
}
Node<E> temp = new Node<E>();
temp = start;
while(temp.next != null)
{
string.append(temp.data).append(",");
temp = temp.next;
}
string.append(temp.data);
return string.toString();
}
public static void main(String [] args)
{
SinglyLinkedList<Integer> list = new SinglyLinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
System.out.println(list.toString());
System.out.println(list.removeAtFirst());
System.out.println(list.removeAtLast());
System.out.println(list.toString());
}
}

Wednesday, September 14, 2011

Epic Interview Question: Remove all Duplicates from the array

Let the Array be [1,1,1,2,2,2,3,4,4,4,5]

Output should be [1,2,3,4,5]

Source Code:

package com.interview.epic;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateRemoval {
    public static void main(String [] args)
   
    {
        Integer [] a = {1,1,1,2,2,3,4,4,5};
        List<Integer> intList = Arrays.asList(a);
        Set<Integer> set = new HashSet<Integer>(intList);
        System.out.println("set data");       
        for (Object temp: set)
        {
            System.out.println(temp);
        }
       
    }

}





What is difference between thread and process?

 
Ans) Differences between threads and processes are:-
1. Threads share the address space of the process that  created it; processes have their own address.
2. Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process.
3. Threads can directly communicate with other threads of its process; processes must use inter process communication to communicate with sibling processes.
4. Threads have almost no overhead; processes have considerable overhead.
5. New threads are easily created; new processes require duplication of the parent process.
6. Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.
7. Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process; changes to the parent process do not affect child processes.

Tuesday, September 13, 2011

Epic Interview Question: Keypad Interview Question

Hi
Q: On a cellphone keypad, 0,1 has no characters, 2=ABC, 3=DEF and so on. So, the entered number  should be converted to text. If for example 22 gives out B, 2222 gives out A. '#'  sign denotes end of a character. Example: 222#22#222222 = 'CBB'. Also if another number is started  new series is started. Example 2222333456622 = '2FGJNB'. Write a program to print this.

SourceCode:

package com.interview.epic;

public class KeyPad {
   
    public static void main(String [] args)
    {
        String s1 ="77333777#77";
        char [] c =s1.toCharArray();
        String[] tokens = s1.split("#");
        int k = 0;
        while(k < tokens.length)
        {           
            String tkn = tokens[k];
            char [] c1 = tkn.toCharArray();
            int startIndex = 0;
            for(int h = 0; h < c1.length; h++)
            {
                if((h<c1.length-1) && (c[h] == c[h+1]))
                {
                    continue;
                }
                else
                {
                    int endIndex = h;
                    String s = tkn.substring(startIndex, endIndex+1);
                   
           
        int i = s.length();
        if((s.charAt(0) != '9') && (s.charAt(0) != '7'))
        {
            i=i%3;
        }
        else
        {
            i=i%4;
        }
        int key = Integer.parseInt((Character.toString(tkn.charAt(startIndex))));
        startIndex = h+1;
        switch(key)
        {
        case (2):
            print(i,"ABC");
            break;
        case (3):
            print(i,"DEF");
            break;
        case (4):
            print(i,"GHI");
            break;
        case (5):
            print(i,"JKL");
            break;   
        case (6):
            print(i,"MNO");
            break;
        case (7):
            print(i,"PQRS");
            break;
        case (8):
            print(i,"TUV");
            break;
        case (9):
            print(i,"WXYZ");
            break;
           
           
        }
       
                }
            }
            k++;
       
        }
    }
    public static void print(int i, String letters)
    {
        if(i!= 0)
        {
            System.out.println(letters.charAt(i-1));
        }
        else
        {
            System.out.println(letters.charAt(letters.length() -1));
        }
    }

}

Sunday, September 11, 2011

Java Clone, Shallow Copy and Deep Copy

In java, though clone is ‘intended’ to produce a copy of the same object it is not guaranteed. Clone comes with lots of its and buts. So my first advice is to not depend on clones. If you want to provide a handle / method to deliver a copy of the current instance write a kind of factory method and provide it with a good documentation. When you are in a situation to use a third party component and produce copies of it using the clone method, then investigate that implementation carefully and get to know what is underlying. Because when you ask for a rabbit, it may give monkeys!

Shallow Copy

Generally clone method of an object, creates a new instance of the same class and copies all the fields to the new instance and returns it. This is nothing but shallow copy. Object class provides a clone method and provides support for the shallow copy. It returns ‘Object’ as type and you need to explicitly cast back to your original object.
Since the Object class has the clone method (protected) you cannot use it in all your classes. The class which you want to be cloned should implement clone method and overwrite it. It should provide its own meaning for copy or to the least it should invoke the super.clone(). Also you have to implement Cloneable marker interface or else you will get CloneNotSupportedException. When you invoke the super.clone() then you are dependent on the Object class’s implementation and what you get is a shallow copy.

 

Deep Copy

When you need a deep copy then you need to implement it yourself. When the copied object contains some other object its references are copied recursively in deep copy. When you implement deep copy be careful as you might fall for cyclic dependencies. If you don’t want to implement deep copy yourselves then you can go for serialization. It does implements deep copy implicitly and gracefully handling cyclic dependencies.
One more disadvantage with this clone system is that, most of theinterface / abstract class writers in java forget to put a public clone method. For example you can take List. So when you want to clone their implementations you have to ignore the abstract type and use actual implementations like ArrayList by name. This completely removes the advantage and goodness of abstractness.
When implementing a singleton pattern, if its superclass implements a public clone() method, to prevent your subclass from using this class’s clone() method to obtain a copy overwrite it and throw an exception of type  CloneNotSupportedException.
Note that clone is not for instantiation and initialization. It should not be synonymously used as creating a new object. Because the constructor of the cloned objects may never get invoked in the process. It is about copying the object in discussion and not creating new. It completely depends on the clone implementation. One more disadvantage (what to do there are so many), clone prevents the use of final fields. We have to find roundabout ways to copy the final fields into the copied object.
Clone is an agreement between you, compiler and implementer. If you are confident that you all three have good knowledge of java, then go ahead and use clone. If you have a slightest of doubt better copy the object manually.

Example source code for java clone and shallow copy

class Employee implements Cloneable {
 
 private String name;
 private String designation;
 
 public Employee() {
 this.setDesignation("Programmer");
 }
 public String getDesignation() {
 return designation;
 }
 
 public void setDesignation(String designation) {
 this.designation = designation;
 }
 
 public String getName() {
 return name;
 }
 
 public void setName(String name) {
 this.name = name;
 }
 
 public Object clone() throwsCloneNotSupportedException {
 /*
 Employee copyObj = new Employee();
 copyObj.setDesignation(this.designation);
 copyObj.setName(this.name);
 return copyObj;
 */
 return super.clone();
 }
}
 
public class CloneExample {
 public static void main(String arg[]){
 Employee jwz = new Employee();
 jwz.setName("Jamie Zawinski");
 try {
 Employee joel = (Employee) jwz.clone();
 System.out.println(joel.getName());
 System.out.println(joel.getDesignation());
 } catch (CloneNotSupportedException cnse) {
 System.out.println("Cloneable should be implemented. " + cnse );
 }
 }
}
Output of the above program:
Jamie Zawinski
Programmer