Create custom hashmap in Java


One of the common interview question, is to build own CustomHashMap. Following code sample demonstrate generic map with put(), get() and remove() operations.

/**
 * The CustomHashMap uses an array of KeyValuePair.
 * KeyValuePair class  where K is the key and V value and  next is the element appended to it. The KeyValuePair acts 
 * as a list
 * 
 *  MapList is used to store elements. the getHash() method is used to find the index of the array. 
 * 
 * @param <K>
 * @param <V>
 */
public class CustomHashMap<K, V> {

	KeyValuePair<K, V> mapList[] = new KeyValuePair[100];

	public V get(K key) {
		int index = getHash(key);
		KeyValuePair<K,V> list = mapList[index];
		return getMatchValue(list, key);
	}

	public void put(K key, V value) {
		int index = getHash(key);
		storeValue(index, key, value);
	}
	
	public void remove(K key) {
		int index = getHash(key);
		KeyValuePair<K,V> list = mapList[index];
		if (list == null)
			return;
		// if only one element is present in the list ,set the index to null
		if(list.getKey().equals(key)){
			if (list.next == null){
				mapList[index] = null;
				return;
			}
		}
		KeyValuePair<K,V> prev = null;
		do{
			if(list.key.equals(key)){
				if (prev == null){
					list = list.getNext();
				}else{
					prev.next = list.getNext();
				}
				break;
			}
			list = list.next;
		}while(list != null);
		
		mapList[index] = list;
	}

	/*
	 * find the match value and return , if not found either throw exception or return null.
	 */
	private V getMatchValue(KeyValuePair<K, V> list, K key) {
		while (list != null) {
			if (list.getKey().equals(key))
				return list.getValue();
			list = list.next;
		}
		return null;
	}

	private void storeValue(int index, K key, V value) {
		KeyValuePair<K, V> list = mapList[index];
		
		// if list is empty , enter as first element
		if (list == null) {
			mapList[index] = new KeyValuePair<K, V>(key, value);
		} else {
			boolean done = false;
			// traverse through list , if a key is found ,replace the value or add it at the end of the list
			while(list.next != null) {
				if (list.getKey().equals(key)) {
					list.setValue(value);
					done = true;
					break;
				} 
				list = list.next;
			}
			// add at the end of the list
			if (!done)
				list.next = new KeyValuePair<K, V>(key, value);
		}

	}
	
	private int getHash(K key) {
		int hash = key.hashCode();
		return hash % 100;
	}
	
	public static void main(String args[]) {
		CustomHashMap<Integer, Integer> map = new CustomHashMap<Integer, Integer>();
		map.put(1, 1);
		map.put(2, 2);
		map.put(201,201);
		System.out.println("get value is " + map.get(1));
		System.out.println("get value is " + map.get(201));
		System.out.println("get value is " + map.get(2));
		map.remove(1);
		System.out.println("After deletion " + map.get(1));
		System.out.println("get value is " + map.get(201));
	}

}

class KeyValuePair<K, V> {
	K key;
	V value;
	KeyValuePair<K, V> next = null;

	public KeyValuePair<K, V> getNext() {
		return next;
	}

	public void setNext(KeyValuePair<K, V> next) {
		this.next = next;
	}

	public KeyValuePair(K key, V value) {
		super();
		this.key = key;
		this.value = value;
	}

	public K getKey() {
		return key;
	}

	public void setKey(K key) {
		this.key = key;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}

}

Unsupported major.minor version 51.0; nested exception is java.lang.UnsupportedClassVersionError


While doing mvn compile i got the following error

Unsupported major.minor version 51.0; nested exception is java.lang.UnsupportedClassVersionError

After going through google links, the error seems to be the JDK version for compilation is different that JDK version executing it .

But when i do , java -version and javac -version , I got the same result .

java version “1.7.0_51”

Java(TM) SE Runtime Environment (build 1.7.0_51-b13)

Then I decided to check java version used by maven and Aha !

frobplant-lm:test hrsht$ mvn -version

Apache Maven 3.2.1 (ea8b2b07643dbb1b84b6d16e1f08391b666bc1e9; 2014-02-14T09:37:52-08:00)

Maven home: /usr/local/Cellar/maven/3.2.1/libexec

Java version: 1.6.0_65, vendor: Apple Inc.

Maven was using java  1.6 and I had java 1.7 in the path.

To fix this I changed the path of maven java version by setting JAVA_HOME to java 1.7 .

Cheers.

How to set the JAVA_HOME variable in Mac OS X – maverick


Here’s what needs to be done:

– Start the Terminal.

$ vi ~/.bash_profile

… and paste the following (make it a single line):

export JAVA_HOME=/System/Library/Frameworks/
JavaVM.framework/Versions/CurrentJDK/Home

this set to java 1.6 or default installed in your mac.

But if you download and install jdk 1.7  which is pointing to /usr/bin/java

Set

export JAVA_HOME=/usr

echo $JAVA_HOME to check the java version

Maven uses JAVA_HOME value for java .

Note: I also tried creating and using the ~/.bashrc file, but that didn’t work (Mac OS 10.6.2), while ~/.bash_profile worked as expected.

 

 

Write a program to find whether a binary tree is a balanced ?


As per wikipedia

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

A binary tree can be considered as balanced if

  • The Left subtree is balanced
  • The right subtree is balanced
  • For a node the difference between height of left subtree and right subtree is not more than 1.

One approach to check balance condition for a node is by calculating height of left and right subtree and satisy the 3rd condition,then traverse down the tree to check for each child and keep continuing till you reach the leaf node. If condition is not satisfied for a node return false;

public class IsTreeBalance {


public boolean isBalance(TreeNode root){


if(root == null)

return true;

if (Math.abs(height(root.left)-height(root.right)) >1)

return false;

return isBalance(root.left) && isBalance(root.right);



}

  public int height(TreeNode node){


    if (node == null)

       return 0;
 
    return 1 + Math.max(height(node.left), height(node.right));

  }
}

So far so good. But the problem with this approach is that we visit each node (except root) more than once and hence not the best approach doing top-down check.

Opposite of top-down is bottom-up which is more efficient in this case. We start with leaf node and traverse up the tree. This way a node is visited only once.

public int isBalance1(TreeNode root){

if(root == null)

return 0;

int leftHeight = isBalance1(root.left);

int rightHeight = isBalance1(root.right);

if(Math.abs(leftHeight- rightHeight) > 1)

return -1;

return 1+Math.max(leftHeight, rightHeight);

&nbsp;

}
<pre>