Create a binary tree from an array of integers .


Write a function that given an array representation of a binary tree will convert it into a typical tree format.
The following is a visual representation of expected input and output:

Input: [7, 3, 9, 2, 4, 8, 10,11,12,13,14]
Output:
7
/ \
3 9
/\ /\
2 4 8 10

One way to build a tree is that we know that array is like a breadth first traversal . So the series it appears is the same order we need to create tree. Also other property of tree is for a node at index “index” , left child is [2*index+1] and right child is [2*index+2].

public Node createTree(Integer[] array){
        
        if(array == null || array.size == 0)
         return null;
     	Node n = array[0];
     	Queue queue =new Queue();
     	queue.add(n);
        int count = 1;
     	while(count < array.length || !queue.isEmpty()){
     		n.left = new Node(array[count++]);
     		queue.add(n);
                if(count < array.length){
                  n.right = new Node(array[count++])
     		  queue.add(n.right)
               }    	
     	}
     return n;
     }

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 had to be done:

- Start the Terminal app.
- Create/Edit ~/.bash_profile file.
Note: I first tried creating and using the ~/.bashrc file, but that didn’t work (Mac OS 10.6.2), while ~/.bash_profile worked as expected.

Therefore,

$ 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 but if you want to set it to java 1.7 , then install it by downloading dmg file . 

My Java 1.7 was pointed to /usr/bin/java

so if set 

export JAVA_HOME=/usr

echo $JAVA_HOME to check the java version 

Maven uses JAVA_HOME value for java . 

 

 

Create complex json response , with child relationship in rails


For mobile based app, sometimes you want to return json responses to the client.

Let say I have a class with Attraction which could be typically a name of city and the city could have multiples places of attractions.


class Attraction
 include MongoMapper::Document

key :city, String
many :places
end

A child class Place.rb


class Place
 include MongoMapper::Document

belongs_to :attraction
 key :type, String
key :description , String
 key :address, String
 key :website, String
 key :rating, Float
 belongs_to :attraction

end

 

Note it will not change for ActiveRecord class.

Now for call like /attractions.json i want all the attractions and also places mapped to attraction.


class AttractionsController < ApplicationController
 # GET /attractions
 # GET /attractions.json
 def index
 @attractions = Attraction.all
 render :json => @attractions.to_json(:include => [:places])

 end

end

:include  does the trick . Also if you want to include only selected fields from places class


render :json => @attractions.to_json(:include =>

[:places =>{ :only =>[:website,:address])

 

Program to find whether the binary tree is BST ?


A binary tree is binary search tree (BST) if :

  • If the left subtree nodes value is less than the given node.
  • If the right subtree nodes value is greater than the give node
  • Both the left and right subtrees are BST.

public class BinaryTreeIsBST {

	public boolean IsBST(TreeNode node, int max, int min){

		if(node == null)
			return true;
		if(min < node.value && node.value > max){
			return IsBST(node.left,min,node.value) &&
                         IsBST(node.right,node.value,max);
		}
		return false;
	}
}