Category: java

Q)What is difference between HashMap and HashTable?


Both collections implements Map. Both collections store value as key-value pairs. The key differences between the two are

1. Access to the Hashtable is synchronized on the table while access to the HashMap isn’t. You can add it, but it isn’t there by default.

2. Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn’t. If you change the map while iterating, you’ll know. • Fail-safe – “if the Hashtable is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException”

3. HashMap permits null values and only one null key, while Hashtable doesn’t allow key or value as null.

What is volatile keyword?


Ans) In general each thread has its own copy of variable, such that one thread is not concerned with the value of same variable in the other thread. But sometime this may not be the case. Consider a scenario in which the count variable is holding the number of times a method is called for a given class irrespective of any thread calling, in this case irrespective of thread access the count has to be increased. In this case the count variable is declared as volatile. The copy of volatile variable is stored in the main memory, so every time a thread access the variable even for reading purpose the local copy is updated each time from the main memory. The volatile variable also have performance issues.

Program to find height of a binary tree


The algorithm works as follows:

  • Each node starting from the parent node is push into an stack. Then the element is popped from the stack and a check is made to find whether the node has left and right child. If any one or both are present the elements are pushed into stack. At the same time a corresponding entry is made into a map with key as ‘node’ and value as the ‘height’ .The value of height is one more than the height of parent and intial height of parent is set to 1.

The code flow is explained below.

  • The program contains two classes : Node and BinaryTree class. The Node class is a datastructure used to build a tree and BinaryTree is a class to find the height.
  • The class Node is a data structure which can have left child (Node), a right child (Node) and can contain any value.

package com.src;

public class Node {

 

private Node left;

private Node right;

private Object value;

 

public Node getLeft() {

return left;

}

 

public Node getRight() {

return right;

}

 

public Object getValue() {

return value;

}

 

public Node(Node left, Node right, Object value) {

super();

this.left = left;

this.right = right;

this.value = value;

}

}

 

The BinaryTree class contains the logic of finding the height of the tree.

Consider the following example:

tree2

  • The createTree() method is used to create the node for each element in tree. Create node starting from the leaf node and moving upward. For above tree:

Node node21 = new Node(null,null,21);

Node node1 = new Node(null,node21,1);

  • For the given example the createTree() method will have code as:

private void createTree(){

Node node21 = new Node(null,null,21);

 

Node node23 = new Node(null,null,23);

Node node56 = new Node(null,null,56);

Node node11 = new Node(null,null,11);

Node node1 = new Node(null,node21,1);

Node node45 = new Node(node23,node1,45);

Node node73 = new Node(null,null,73);

Node node12 = new Node(node56,node11,12);

 

Node node34 = new Node(node45,node73,34);

Node node87 = new Node(node12,null,87);

 

Node node77 = new Node(node34,node87,77);

parent = node77;

}

 

The logic for finding height is put in getHeight() method:

private Node parent = null;

     private Stack<Node> stack = new Stack<Node>();

// the map will store the node and its current height

     private Map<Node,Integer> map = new

HashMap<Node,Integer>();    

 

private void getHeight(){

 

int highest_height =1;

int current_height = 1;

int parent_height=0;

Node temp_node = null;

stack.push(parent); // initially only the parent is present in stack

map.put(parent, current_height);

while(stack.size() != 0){

 temp_node = stack.pop();  // pop element at top from stack.

parent_height = map.get(temp_node);  // get the height

if(temp_node.getLeft() != null){  // if current node has left child

 current_height = parent_height+1; // increase the height by 1

stack.push(temp_node.getLeft()); // push the element to the stack

//put into map – put(current node, current height)

map.put(temp_node.getLeft(),current_height);   

 highest_height= (highest_height < current_height) ? current_height : highest_height;

}

 

if(temp_node.getRight() != null){  // same as left child

current_height =parent_height+1;

map.put(temp_node.getRight(),current_height);

stack.push(temp_node.getRight())     

 highest_height= (highest_height < current_height) ? current_height : highest_height;

    

}

    

System.out.println(“\n Elements currently in stack \n”);

         

for(int i =0; i<stack.size();i++){

System.out.print(” “ +((Node)stack.get(i)).getValue());  

     }

             

}

         

System.out.println(“The height is “ + highest_height);

   }

    

public static void main(String[] args) {

           BinaryTree bt = new BinaryTree();

          bt.createTree();

          bt.getHeight();

 

     }

 

}

 

The logs will show:

 

Elements currently in stack 34 87

Elements currently in stack 34 12

Elements currently in stack 34 56 11

Elements currently in stack 34 56

Elements currently in stack 34

Elements currently in stack 45 73

Elements currently in stack 45

Elements currently in stack 23 1

Elements currently in stack 23 21

Elements currently in stack 23

Elements currently in stack

The height is 5

 

 

 

  • When the parent is pop from the stack a check is made to find whether it has a left child or not, if a left child is present push the left child to stack, also put the same element in a map with key as the current node and value is height which is incremented by 1 of its parent height.
  • Now check if the current height is greater than the highest height or not. If it is set the highest_height to current_height.
  • Similarly it works for the right child.

For given example when a check is made for parent, then 34 and 87 are push into stack.

 

Elements currently in stack 34 87 

  • Now 87 is picked up and a check is made for it. Since it contains only left child as 12 , the current stack will look like

 Elements currently in stack 34 12

  • The while loop iterates till the stack becomes empty.
  • The main overhead in this program is to create a tree like structure by declaring the nodes explicitly.

What is difference between ClassNotFoundException and NoClassDefFoundError?


Many people get confused with these 2 errors. So here is a brief explanation.

 A ClassNotFoundException is thrown when the reported class is not found by the ClassLoader in the CLASSPATH. It could also mean that the class in question is trying to be loaded from another class which was loaded in a parent classloader and hence the class from the child classloader is not visible.

Consider if NoClassDefFoundError occurs which is something like

java.lang.NoClassDefFoundError

src/com/TestClass

does not mean that the TestClass class is not in the CLASSPATH. It means that the class TestClass was found by the ClassLoader however when trying to load the class, it ran into an error reading the class definition. This typically happens when the class in question has static blocks or members which use a Class that’s not found by the ClassLoader. So to find the culprit, view the source of the class in question (TestClass in this case) and look for code using static blocks or static members.