Monthly Archives: January 2015

string vs stringbuffer vs stringbuilder

by

0

http://javahungry.blogspot.com/2013/06/difference-between-string-stringbuilder.html

In summary here are list of difference between StringBuffer, String and StringBuilder in Java :

1) String is immutable while StringBuffer and StringBuilder is mutable object.
2) StringBuffer is synchronized while StringBuilder is not which makes StringBuilder faster than StringBuffer.
3) Concatenation operator “+” is internal implemented using either StringBuffer or StringBuilder.
4) Use String if you require immutability, use Stringbuffer in java if you need mutable + thread-safety and use StringBuilder in Java if you require mutable + without thread-safety.

String hashCode() method, equals method comparision

by

0

  • hashCode

    public int hashCode()
    Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

    using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in practice (usually some keys will hash to the same bucket.

hashCode() vs equals() Method

  1. If object1 and object2 are equal according to their equals() method, they must also have the same hash code.
  2. If object1 and object2 have the same hash code, they do NOT have to be equal too.

Algo’s 2c

by

0

http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/
http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/ – (see 2nd solution using hashmap, O(n) solution).

http://www.programcreek.com/2012/12/add-two-numbers/

Finding an element in infinite sorted array

by

0

I am not sure if I understand your problem well, but would not that be a bit easier:

1. Check if a[i] > x for i=1,2,4,8,16… Do not search until a[i]=+infinity, it’s IMO unneccessary
2. When found, do binary search between a[previous i] and a[i], not between a[1] and a[i]. However this saves only one step of binary search, so rather is not that much of optimalization

Check for balanced parentheses in an expression

by

0

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”

public static void main(String[] args) {
		String str = "[()]{}{[()()]()}";
		if(checkBalancedParanthesis(str))
			System.out.println("Balanced Paranthesis");
		else
			System.out.println("Not Balanced Paranthesis");
	}
	
	public static Boolean checkBalancedParanthesis(String str)
	{
		HashMap<Character, Character> hm = new HashMap<Character, Character>();
		hm.put('[', ']');
		hm.put('(', ')');
		hm.put('{', '}');
		
		Stack st = new Stack();
		
		//Odd no. of characters => not balanced
		if(str.length() % 2 != 0)
			return false;
		
		for(int i =0;i<str.length();i++)
		{
			//opening brace
			if(hm.containsKey(str.charAt(i)))
			{
				st.push(str.charAt(i));
			}
			//closing brace
			else
			{
				if(st.isEmpty())
					return false;
				
				if(hm.get(st.pop()) != str.charAt(i))
					return false;
			}
		}		
		if(st.isEmpty())
			return true;
		else
			return false;
	}