IMP Questions

*******************************************************************************************************************
2 SUM Problem
http://coderevisited.com/2-sum-problem/
http://www.careercup.com/question?id=15206700


The 2 sum problem is a classic variation of the subset sum problem. It is defined as the following: 
You have an unsorted array, and you are given a value S. Find all pairs of elements in the array that
add up to value S. 
2 solutions - one minimizes space complexity, and the other time. As stated in the "hint", 
one approach is to hash the entire array, and then for each element check if S-array[j] is in the 
hash table. This takes O(n) time and O(n) space to store the array. 
Alternatively, if one wishes to minimize space complexity, simply sort the array. Then, have two
pointers - one initialized to array[0] and the other array[length-1]. Then check the sums; if the
sum is > S, decrement the right pointer. If it is < S, increment the left pointer.

Sample Java code for the second method of finding 2sum:
public static void findTwoSum(int[] A, int x) {
    Arrays.sort(A);        
    int start = 0;
    int end = A.length - 1;
    boolean found = false;
    while (!found && start < end) {
        if (A[start] + A[end] == x)
            found = true;
        else if (A[start] + A[end] > x)
            end--;
        else if (A[start] + A[end] < x)
            start++;
    }
    if (found)
        System.out.println("Sum " + x
                + " is found, values the making sum are " + A[start] + " , "
                + A[end]);
    else
        System.out.println("No pair exists whose sum is " + x);
}

***********************************************************************************************************
To reverse a string in Java:

package BST_Demo;

public class ReverseArray {
public static void main(String[] args) {
	
	String givenString = "Am I bad ? ";
			StringBuilder reverse=new StringBuilder(givenString.length());
			for(int i=givenString.length()-1;i>=0;i--){
				reverse.append(givenString.charAt(i));
			}
			System.out.println(reverse.toString());
	
}
}


How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
Push and pop are standard stack operations.

http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/


Very IMP Q -> Disadvantages of HashMap or Hashtable OR Why is BALANCED TREES better than using Hashtable
or HashMap?
Ans ->
Very IMP Q -> Disadvantages of HashMap or Hashtable OR Why is BALANCED TREES better than using Hashtable
or HashMap?
Ans -> 
In short:
1) Requires more main memory
2) Hashing algorithm does not result in spatial locality. Because hash tables cause
access patterns that jump around, this can trigger microprocessor cache misses that cause long delays.
3) Similar key types will result in more collision and hence the hashtable would be more like a linkedlist.
Collisions also ruin memory utilization- if I have 70 elements in 100 buckets, but those 70 elements hash to 
only 4 buckets (and yes, Virginia, I’ve seen collision rates this bad), then 96 of my buckets aren’t doing
me any good at, I’m just wasting that space.
4) Occasionally HashMap/Hashtable requires resizing when the original size of HashMap/Hashtable buckets
are full. Resizing takes O(n) time as the elements from the previous hashtable/HashMap are transferred to
a new bigger Hashtable/HashMap. This is not good for implementation.
5) The concept that Hashtables/HashMap offers O(constant) (aka O(1) ) time complexity
for insertion, deletion and searchingis something to rethink on as the datastructure givies that
time complexity on a average scale, which is called as "AMORTIZED" time complexity. That means that there
would be atleast on instance out of n instances where the Time Complexity would be O(n) and not O(constant).
This is the time when the HashMap/Hashtable requires resizing.

http://stackoverflow.com/questions/6924852/what-are-the-disadvantages-to-hashmaps
http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
http://en.wikipedia.org/wiki/Hash_table#Drawbacks


/* Program to find the 2nd minimum element in the array */
#include <stdio.h>
#include <limits.h> /* For INT_MAX */
 
/* Function to print first smallest and second smallest elements

Algorithm:

1) Initialize both first and second smallest as INT_MAX
   first = second = INT_MAX
2) Loop through all the elements.
   a) If the current element is smaller than first, then update first 
       and second. 
   b) Else if the current element is smaller than second then update 
    secondAlgorithm:

*/

void print2Smallest(int arr[], int arr_size)
{
    int i, first, second;
 
    /* There should be atleast two elements */
    if (arr_size < 2)
    {
        printf(" Invalid Input ");
        return;
    }
 
    first = second = INT_MAX;
    for (i = 0; i < arr_size ; i ++)
    {
        /* If current element is smaller than first then update both
          first and second */
        if (arr[i] < first)
        {
            second = first;
            first = arr[i];
        }
 
        /* If arr[i] is in between first and second then update second  */
        else if (arr[i] < second && arr[i] != first)
            second = arr[i];
    }
    if (second == INT_MAX)
        printf("There is no second smallest element\n");
    else
        printf("The smallest element is %d and second Smallest element is %d\n",
               first, second);
}
 
 
/* Driver program to test above function */
int main()
{
    int arr[] = {12, 13, 1, 10, 34, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    print2Smallest(arr, n);
    return 0;
}

******************************************************************************************************
Longest Common SubSequence Problem:
/*
Question: Find the longest common subsequence between two strings

Question and Answer Source: http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Algortihm: 1. declare a matrix of s1.length()+1 and s2.length()+1.
              +1 is to store the results of the previous matches
           2. initialize row = 0 OR column = 0 to 0 which indicates that the previous matches was 0
           3. for i=1 to s1.length+1 
           		for j=1 to s2.length+1
           			if(s1.charAt(i-1)==s2.charAt(j-1))
           				dp[i][j]= dp[i-1][j-1]+1 // current match = previous match +1 
           			else
           				dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) 
           				
           		// if the characters don't then the current matches = max of(previous matches)
           				
*/

package SubstringAndSubsequenceProblems.Subsequence;

import java.util.Scanner;


public class LongestCommonSubsequence {
	
	
	private static int[][] dp;  // matrix to store the match results
	 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		try{
			System.out.println("LONGEST COMMON SUBSEQUENCE PROGRAM");
			System.out.println("Enter the two strings");
			String s1 = in.nextLine();
			String s2 = in.nextLine();
			System.out.println("The Longest common SUBSTRING using DP is: "+usingDP(s1,s2));

			// Printing the Logest Common Subsequence
			int lengthOfLCSubSequence = usingDP(s1,s2);
			// we will construct a String of LCS from right to left. Hence we will use char array
			// instead of using StringBuilder which is used to construct the string from left to right
			
			char[] LCSubSequence = new char[lengthOfLCSubSequence];
			
			// pass this char array along with the matrix and 2 strings to get the result of matches
			String longestCommonSubsequence = buildLCSubsequence(LCSubSequence,s1,s2);
			
			System.out.println("The Longext Common SubSequence is: "+longestCommonSubsequence);
		}
		finally{
			in.close();
		}
	}



	private static int usingDP(String s1, String s2) {
	        
	        dp = new int[s1.length()+1][s2.length()+1];  // additional +1 to store the previous match result which is 0
	        
	        // fill the row with s1
	        for(int i=0;i<(s1.length()+1);i++)
	            dp[i][0] = 0;
	            
	        // fill the column with s2
	        for(int j=0;j<(s2.length()+1);j++)
	            dp[0][j] = 0;
	        
	         
	        int result = 0; // to store the length of MAX COMMON SUBSEQUENCE MATCH
	        
	        // fill the remaining rows and columns based on matches
	        for(int i=1;i<(s1.length()+1);i++){
	            for(int j=1;j<(s2.length()+1);j++){
	                
	                // if current characters match then the length of the substring is previous matches + 1
	                if(s1.charAt(i-1)==s2.charAt(j-1))
	                    dp[i][j] = dp[i-1][j-1]+1;
	                
	                else  // if doesnt match then current match = Max of (previous matches)
	                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
	                    
	                result = Math.max(result,dp[i][j]);  // this is to check the maximum match found
	                
	            }
	        }
	        
	        return result;
	    }
	
	 private static String buildLCSubsequence(char[] LCSubSequence, String s1, String s2) {
			
		 
		 	int i = s1.length();
		 	int j = s2.length();
		 	
		 	int index = LCSubSequence.length-1;
		 	
		 	while(i>0 && j>0){ // greater than 0 because there is nothing at 0th row and 0th column in the match matrix
		 	
		 		if(s1.charAt(i-1)==s2.charAt(j-1)){ // -1 because i and j start from their respective lengths
		 			// append the character
		 			LCSubSequence[index]=s1.charAt(i-1);
		 			// decrement the index
		 			index--;
		 			// decrement the i and j pointers
		 			i--;
		 			j--;
		 		}
		 		
		 		// if the characters do not match then go in the max direction in the match matrix
		 		
		 		else if(dp[i-1][j]>dp[i][j-1])
		 			i--;
		 		
		 		else
		 			j--;
		 		
		 	}
		 	
		 	return String.valueOf(LCSubSequence);  // convert char array to string and return
		 
		 
		}
}