Given an int array which might contain duplicates, find if it is a sequence.

Given an int array which might contain duplicates, find if it is a sequence.
Eg. {45,50,47,46,49,48}
is a sequence 45, 46,47,48,49,50
Sorting is an obvious solution. Can this be done in O(n) time and O(1) space

                                            (Or)
Write a method that takes an int array of size m, and returns (True/False) if the array consists of the numbers n...n+m-1, all numbers in that range and only numbers in that range. The array is not guaranteed to be sorted. (For instance, {2,3,4} would return true. {1,3,1} would return false, {1,2,4} would return false.

By working with a[i] % a.length instead of a[i] you reduce the problem to needing to determine that you've got the numbers 0 to a.length - 1.

Approach:
Example array: A = {4, 1, 3, 3, 2}
1. get the min and max.
min=1 and max=4
2. if (max - min) > A.length then "its NOT a sequence".
3. else for each element in A[i] do the following:
a. calculate A[i] - min till A[i]-min=i;
i=0; 4 - 1 = 3, swap A[0] and A[3]
Now we have A = {3, 1, 3, 4, 2}
Again,
i=0; 3 - 1 = 2, now A[0] and A[2] are same so swap A[0] and A[length-1] and put A[length] = infinite.
A = {2, 1, 3, 4, INF}
Again,
i=0; 2 - 1 = 1, swap A[0] and A[1],
A = {1, 2, 3, 4, INF}
i=1; 2 - 1 = 1 (which is same as i)
similarlty for i=2, i=3
finally we have A as,
A = {1, 2, 3, 4, INF}

public static boolean isSequence(int A[])
{
    int min = Integer.MINIMUM;
    int max = Integer.MAXIMUM;
    int len = A.length;
    for(int i=0;i<len;i++)
    {
        if(A[i] < min)
        {
            min = A[i];
        }else if(A[i] > max)
        {
            max = A[i];
        } 
    }
    
    if(max-min > A.length)
        return false;
    
    int i=0;
    while(i<len)
    {
        while(i<len && i != (A[i] - min))
        {
              if(A[A[i] - min] == A[i])
              {
                   A[i] = A[len-1] ;
                   A[len-1] = Integer.MAXIMUM;
                   len = len-1;
              }else
              {
                  int k = A[i] - min;
                  int temp= A[i];
                  A[i] = A[k];
                  A[k] = temp;
              }
        
        }
        
        i++;
  
    }
    
    for(int i=1;i<len;i++)
    {
        if((A[i] - A[i-1]) != -1
        return false;
    }
    
    return true;
}

Longest Contiguous Subarray with Average Greater than or Equal to k

Consider an array of N integers. Find the longest contiguous sub array so that the average of its elements is greater (or equal) than a given number k.

We can reduce this problem to longest contiguous sub array with sum >= 0 by subtracting k from all values in O(n) time

public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

Implement rand7() using rand5()

public static int rand7() {
    int vals[][] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };
 
    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Another approach is

public static int rand7() {
    while (true) {
        int num = 5 * (rand5() - 1) + (rand5() - 1);
        if (num < 21)
            return (num % 7 + 1);
    }
}

Given a sorted, shifted array find the minimum element

Given a sorted, shifted array find the minimum element. For example in {3,4,5,1,2} the minimum is 1, in {4,5,1,2,3} the minimum is 1.

Concept of Binary search can be use with little modification.

// finds the smallest number and returns
// it , if not found it returns -1
public static int findSmallest(int a[], int N)
{
    if(length==0 || a==NULL)
        return -1;

    int start=0,end=N-1;

    while(start <= end)
    {
        int mid=(start end)/2;

        // this is the standard comparison condition
        if(a[mid] > a[mid+1])
            return a[mid+1];

        // an extra comparison that adds the optimization that 
        // if the mid element is the smallest one, there will not be 
        // extra iterations
        if(a[mid] < a[mid-1])
            return a[mid];

        // the left half is in strictly increasing order
        // so we search in the second half
        if(a[mid] > a[start])
        {
            start = mid+1;
        }
        // The array is not rrotated so we simply
        // return the first element of the array
        else if(a[mid] >= a[start] && a[mid] <= a[end])
             return a[0];

        // the right half is in strictly increasing order
        // and hence we will search in the left half
         else
           end= mid-1;

    }
    return -1;
}

Search in Rotated array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently

 

public static int rotatedBinarySearch(int a[], int N, int key)
{
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        int mid = (L+R)/2;
        
        if(a[mid] == key)
            return mid;
          
        //lower half is sorted 
        if(a[low] <= a[mid])
        {
            if(A[low]<= key && key < a[mid])
                high = mid -1;
            else
                low = mid +1;
        }     
        else   // upper half is sorted
        {
            if(a[mid] < key && key < a[high])
                low = mid + 1;
            else
                high = mid - 1;
        
        }       
    }
    
    return -1;
}

Stocks buy and sell, Max profit

Stock prices are stored in an array in the order of date. How do you get the most profit from a
sequence of stock prices? For example, the most profit to be gained from the sequence of ordered stock prices {9, 11, 5, 7, 16, 1, 4, 2} is 11, bought when the price was 5 and sold when the price was 16.

public static int maxStock(int stock[])
{
    if(stock == null || stock.length < 2)
    {
        return 0;
    }
    
    int minStock = stock[0];
    int maxDiff = stock[1]-stock[0];
    
    for(int i=2;i<stock.length;i++)
    {
        if(stock[i-1] < minStock)
            minStock = stock[i-1];
            
        int currDiff = stock[i] - minStock;
        if(currDiff > maxDiff)
            maxDiff = currDiff;  
    }
     
    return maxDiff;

}

Pattern matching.

How to find the phone numbers in 50,000 txt file and replace.

The phone numbers could be in several formats like below

"***-*******"
"**********"
"*** *******"
"***-***-****"

final String regex = "[\\s](\\({0,1}\\d{3}\\){0,1}" +
			"[- \\.]\\d{3}[- \\.]\\d{4})|" +
			"(\\+\\d{2}-\\d{2,4}-\\d{3,4}-\\d{3,4})";
	final Pattern phonePattern = Pattern.compile(regex);

	/* The result set */
	Set<File> files = new HashSet<File>();

	File dir = new File("/initDirPath");
	if (!dir.isDirectory()) return;

	for (File file : dir.listFiles()) {
		if (file.isDirectory()) continue;

		BufferedReader reader = new BufferedReader(new FileReader(file));

		String line;
		boolean found = false;
		while ((line = reader.readLine()) != null 
				&& !found) {
			
			Matcher matcher = phonePattern.matcher(line);
			if (found = matcher.find()) {
				matcher.replaceAll("xxxxxxxxxxx");
			}
		}
	}

	for (File file : files) {
		System.out.println(file.getAbsolutePath());
	}

Array of maximum value in sliding window

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and w is 3

Window position Max

---

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Input: A long array A[], and a window width w Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: Find a good optimal way to get B[i].

The double-ended queue is the perfect data structure for this problem. It supports insertion/deletion from the front and back. The trick is to find a way such that the largest element in the window would always appear in the front of the queue. How would you maintain this requirement as you push and pop elements in and out of the queue?

Besides, you might notice that there are some redundant elements in the queue that we shouldn't even consider about. For example, if the current queue has the elements: [10 5 3], and a new element in the window has the element 11. Now, we could have emptied the queue without considering elements 10, 5, and 3, and insert only element 11 into the queue.

Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.

Every time, we move to a new window, we will be getting a new element and leave an old element. We should take care of:

1. Popping elements outside the window from queue front.
2. Popping elements that are less than new element from the queue.
3. Push new element in the queue as per above discussion.

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindow {

	public static void maxSlidingWindow(int A[], int n, int w, int B[]) {
		Deque<Integer> Q = new ArrayDeque<Integer>();

		// Initialize deque Q for first window
		for (int i = 0; i < w; i++) {
			while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
				Q.pollLast();
			Q.offerLast(i);
		}

		for (int i = w; i < n; i++) {
			B[i - w] = A[Q.getFirst()];

			// update Q for new window
			while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
				Q.pollLast();

			// Pop older element outside window from Q
			while (!Q.isEmpty() && Q.getFirst() <= i - w)
				Q.pollFirst();

			// Insert current element in Q
			Q.offerLast(i);
		}
		B[n - w] = A[Q.getFirst()];
	}

	public static void main(String args[]) {
		int w = 3;
		int a[] = { 1, 3, -1, -3, 5, 3, 6, 7 };
		int b[] = new int[a.length - w + 1];

		maxSlidingWindow(a, a.length, w, b);
		
		System.out.println("Sliding Window Maximum is ");
		for (int i = 0; i < b.length; i++) {
			System.out.print(b[i] + ",");
		}

	}
}

Each element in the list is being inserted and then removed at most once. Therefore, the total number of insert and delete operations is 2n. Therefore it is an O(n) solution.

A queue with constant time operations

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

We know that push and pop are constant time operations But when we think of get_min()[i.e to find the current minimum number in the queue] generally the first thing that comes to mind is searching the whole queue every time the request for the minimum element is made. But this will never give the constant time operation, which is the main aim of the problem.

To do this we have to use two more queues which will keep the track of minimum element and we have to go on modifying these 2 queues as we do push and pop operations on the queue so that minimum element is obtained in O(1) time.

import java.util.LinkedList;
import java.util.Queue;

public class MinQueue {

	Queue<Integer> q = new LinkedList<Integer>();
	Queue<Integer> minq1 = new LinkedList<Integer>();
	Queue<Integer> minq2 = new LinkedList<Integer>();
	boolean isMinq1Current = true;

	public void push(int a) {
		q.offer(a);
		if (isMinq1Current) {
			if (minq1.isEmpty())
				minq1.offer(a);
			else {
				while (!minq1.isEmpty() && minq1.peek() <= a)
					minq2.offer(minq1.poll());
				minq2.offer(a);
				while (!minq1.isEmpty())
					minq1.poll();
				isMinq1Current = false;
			}
		} else {
			if (minq2.isEmpty())
				minq2.offer(a);
			else {
				while (!minq2.isEmpty() && minq2.peek() <= a)
					minq1.offer(minq2.poll());
				minq1.offer(a);
				while (!minq2.isEmpty())
					minq2.poll();
				isMinq1Current = true;
			}
		}
	}

	public int pop() {
		int a = q.poll();
		if (isMinq1Current) {
			if (a == minq1.peek())
				minq1.poll();
		} else {
			if (a == minq2.peek())
				minq2.poll();
		}
		return a;
	}

	public int min() {

		if (isMinq1Current) {
			return minq1.peek();
		} else {
			return minq2.peek();
		}
	}

}

Remove extra brackets from a paranthesized expression

How to remove extra bracket from expressions like ((((A+B))C)) to give (A+B)C in the most optimized way?

Remember the input expression will be valid expression and output expression generated must also be valid and should give the same result as the input expression.

This can be done in O(n) time complexity using stack data structure.

The algorithm

1. Start traversing the expression from left examining every bracket.
2. If you encounter "(" such that there is another "(" to the right of it, this might be one of the extra brackets to be removed. However we can't be sure right now. So put the minus times the index of this bracket in the integer stack.(we put minus times the index to distinguish brackets having similar brackets to their right from the ones not having )
3. If you encounter "(" such that there is a character other than "(" to its right , put its index in the stack.
4. If you encounter ")" such that there is another ")" to its left and we have a negative number on the top of the stack, pop the stack and replace current ")" and bracket at the index minus times top of the stack with "$"(so that these brackets can be removed later and are useless).
5. If you encounter ")" such that there is a character other than ")" to its left and top of the stack has the positive number than you need that bracket so just pop the stack.

At the end we will have useless brackets replaced with "$" sign, which can be removed in a single traversal. Thus giving us an O(n) complexity. Here is the running code using above explained algorithm.

import java.util.Stack;

public class ExpressionValidate {

	public static String validateExpression(String expr) {

		char r[] = expr.toCharArray();
		char s[] = expr.toCharArray();
		Stack<Integer> st = new Stack<Integer>();
		int i = 0;
		while (i < s.length) 
		{
			if (s[i] == '(') {
				if (s[i + 1] == '(') {
					st.push(-i);
				} else {
					st.push(i);
				}
				i++;
			} else if (s[i] != ')' && s[i] != '(') {
				i++;
			} else if (s[i] == ')') {
				int top = st.peek();
				if (s[i - 1] == ')' && top < 0) {
					r[-top] = '$';
					r[i] = '$';
					st.pop();
				}

				else if (s[i - 1] == ')' && top > 0) {
					System.out.println("Something is wrong!!");
				}

				else if (s[i - 1] != ')' && top > 0)
					st.pop();
				i++;
			}
		}

		StringBuffer result = new StringBuffer();

		for (i = 0; i<r.length; i++) {
			if (r[i] == '$') {
				continue;
			}
			result.append(r[i]);
		}

		return result.toString();

	}

	public static void main(String[] args) {
		String expr = "((((A+B))C))";
		System.out.println("Validate expression"+validateExpression(expr));

	}

}

Interval Tree

Question: Find the intervals from a set of intervals in which a given point lies

Given a set of intervals such as (10,20), (15,25), (28,40), (50,70), (0,9) (60,90) and build a data structure. Query the data structure for point x, and it find out all the intervals that contain this point x.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection.

In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in O(log n) time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naive approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in O(log n) time, but the results must be merged, requiring O(n) time. This gives us queries in O(n + log n) = O(n), which is no better than brute-force.

Interval trees solve this problem.

To construct an interval tree from the input given in the question, the following steps should be taken

1. Firstly we will arrange the end points of all the intervals in the increasing order. So for the above given input it will become 0 9 10 15 20 25 28 40 50 60 90. If there are N intervals, there will be 2N end-points and hence sorting will take O(NlogN) time. The entire range of all the intervals now becomes 0-90.

2. We start by taking the entire range of all the intervals and dividing it in half at x_center (in practice, x_center should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of x_center which we'll call S_left, those completely to the right of x_center which we'll call S_right, and those overlapping x_center which we'll call S_center.

3. The intervals in S_left and S_right are recursively divided in the same manner until there are no intervals left.

4. The intervals in S_center that overlap the center point are stored in a separate data structure linked to the node in the interval tree. This data structure consists of two lists, one containing all the intervals sorted by their beginning points, and another containing all the intervals sorted by their ending points.

The result is a binary tree with each node storing:

• A center point
• A pointer to another node containing all intervals completely to the left of the center point
• A pointer to another node containing all intervals completely to the right of the center point
• All intervals overlapping the center point sorted by their beginning point
• All intervals overlapping the center point sorted by their ending point

To find the intervals in which a given number 'x' lies we do the following:

1. For each tree node, x is compared to x_center, the midpoint used in node construction above. If x is less than x_center, the leftmost set of intervals, S_left, is considered. If x is greater than x_center, the rightmost set of intervals, S_right, is considered.

2. As each node is processed as we traverse the tree from the root to a leaf, the ranges in its S_center are processed. If x is less than x_center, we know that all intervals in S_center end after x, or they could not also overlap x_center. Therefore, we need only find those intervals in S_center that begin before x. Suppose we find the closest number no greater than x in this list. All ranges from the beginning of the list to that found point overlap x because they begin before x and end after x (as we know because they overlap x_center which is larger than x). Thus, we can simply start enumerating intervals in the list until the endpoint value exceeds x.

3. Likewise, if x is greater than x_center, we know that all intervals in S_center must begin before x, so we find those intervals that end after x using the list sorted by interval endings.

4. If x exactly matches x_center, all intervals in S_center can be added to the results without further processing and tree traversal can be stopped.

Intersection with Interval

First, we can reduce the case where an interval R is given as input to the simpler case where a single point is given as input. We first find all ranges with beginning or end points inside the input interval R using a separately constructed tree. In the one-dimensional case, we can use a simple tree containing all the beginning and ending points in the interval set, each with a pointer to its corresponding interval.

A binary search in O(log n) time for the beginning and end of R reveals the minimum and maximum points to consider. Each point within this range references an interval that overlaps our range and is added to the result list. Care must be taken to avoid duplicates, since an interval might both begin and end within R. This can be done using a binary flag on each interval to mark whether or not it has been added to the result set.

The only intervals not yet considered are those overlapping R that do not have an endpoint inside R, in other words, intervals that enclose it. To find these, we pick any point inside R and use the algorithm below to find all intervals intersecting that point (again, being careful to remove duplicates).

The complete java implementation can be found here.

http://thekevindolan.com/2010/02/interval-tree/

A pair with given sum in a Balanced BST

Find two elements in balanced BST which sums to a given a value. Constraints Time O(n) and space O(log n).

The Brute Force Solution is to consider each pair in BST and check whether the sum equals to X. The time complexity of this solution will be O(n^2).

A Better Solution is to create an auxiliary array and store Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted data. Once we have the Inorder traversal, we can pair in O(n) time. This solution works in O(n) time, but requires O(n) auxiliary space.

The idea is same as finding the pair in sorted array. We traverse BST in Normal Inorder and Reverse Inorder simultaneously. In reverse inorder, we start from the rightmost node which is the maximum value node. In normal inorder, we start from the left most node which is minimum value node. We add sum of current nodes in both traversals and compare this sum with given target sum. If the sum is same as target sum, we return true. If the sum is more than target sum, we move to next node in reverse inorder traversal, otherwise we move to next node in normal inorder traversal. If any of the traversals is finished without finding a pair, we return false. Following is C++ implementation of this approach.

 

public static int[] findSum(int toSearch, Node root){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        Node cur1 = root;
        Node cur2 = root;
        boolean done1 = false, done2 = false;

        int val1 = 0, val2 = 0;

        while (true) {
            while(!done1){
                if(cur1 != null){
                    s1.push(cur1);
                    cur1 = cur1.left;
                }
                else {
                    if(s1.isEmpty()) done1 = true;
                    else {
                        cur1 = s1.pop();
                        val1 = cur1.value;
                        cur1 = cur1.right;
                        done1 = true;
                    }
                }
            }
            while(!done2){
                if(cur2 != null){
                    s2.push(cur2);
                    cur2 = cur2.right;
                }
                else {
                    if(s2.isEmpty()) done2 = true;
                    else {
                        cur2 = s2.pop();
                        val2 = cur2.value;
                        cur2 = cur2.left;
                        done2 = true;
                    }
                }
            }
            if (val1 + val2 == toSearch){
                int[] res = {val1,val2};
                return res;
            }
            else if (val1 + val2 > toSearch){
                done2 = false;
            }
            else {
                done1 = false;
            }
        }
    }

Reverse adjacent nodes in a linked list

Reverse the adjacent nodes in a linked list If the nodes of a linked list are as follows 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 then after reverse they should be 2 -> 1 -> 4 -> 3 Here the number of entries are odd hence the last link is not reversed. If number of nodes are even then last node should also be reversed.

node * swapAdjacent(node * head){
    node *a,*b,*c,*d;
    a = head;
    if(a == null)
        return a;
    b = a->next;
    if(b == null)
        return a;
    c = b->next;
    if(c == null){
        b->next = a;
        a->next = c;
        return b;
    }
    d = c->next;

    //now all a,b,c are non null. size of list is  >=3
    node * newHead = b;
    while(b!= null){
        b->next = a;
        if(d != null)
            a->next = d;
        else
            a->next = c;
        a = c;
        b = d;
        c = (b!=null)?b->next : null;
        d = (c!=null)?c->next : null;
    }
    return newHead;
}

Subsets of size k

Question: Print All k size subset of given array of size n

Algorithm:
Suppose array size is of length 5 ie A = {1,2,3,4,5};
and we need all the subsets of size k=3.

If we were supposed to find all the subsets then we would have taken all the binary representations of numbers from 1 to (2^5 - 1) and then according to the bits set, we would have chosen the corresponding number from Array A.

Now the idea is get the minimum number where all "k" lower bits are set.
In our case that would be = "00111" => 7 in decimal
Now find the next decimal number > 7 where 3 bits are set.
Keep on finding the next numbers till you hit "11100" = 28 since that is the largest binary number with 3 bits set of length 5.

Given an integer, method to find the next smallest number that have the same numbers of bits set:
1. Traverse from right to left, Once we have passed a 1, turn on the next 0.
ex: 101110 becomes 111110
2. Turn off the one that's just to the right side of that (where you switched on '0' to '1').
now 111110 becomes 110110.
3. Make the number as small as possible by rearranging all the 1's to be as far as right as possible.
ex: 110110 becomes 110011.

public class KSubSet {

	public static void main(String[] args) {
		int[] A = { 1, 2, 3, 4, 5 };
		int k = 3;
		int len = A.length;
		int result = 0;

		StringBuffer sb = new StringBuffer();
		int diff = len - k;

		for (int i = 1; i <= diff; i++) {
			sb.append('0');
		}
		for (int i = 1; i <= k; i++) {
			sb.append('1');
		}

		String binStr = sb.toString();
		String finalBinStr = sb.reverse().toString();
		int last = Integer.parseInt(finalBinStr, 2);
		// System.out.println("LAST:" + last);
		System.out.println("Subsets of size " + k + " are: ");
		printSubSet(A, binStr);
		result = Integer.parseInt(binStr, 2);
		while (result < last) {
			binStr = findNext(result, len);
			printSubSet(A, binStr);
			result = Integer.parseInt(binStr, 2);
		}
	}

	public static void printSubSet(int[] A, String binaryString) {
		int len = binaryString.length();
		for (int i = 0; i < len; i++) {
			if (binaryString.charAt(i) == '1') {
				System.out.print(A[i] + " ");
			}
		}
		System.out.println();
	}

	// finds the next smallest number with same number of k bits set.
	public static String findNext(int n, int k) {
		StringBuffer sbuff = new StringBuffer();

		int l = Integer.toBinaryString(n).length();
		if (l < k) {
			for (int i = 1; i <= (k - l); i++) {
				sbuff.append('0');
			}
		}
		char[] ch = (sbuff.toString() + Integer.toBinaryString(n))
				.toCharArray();
		int len = ch.length;
		boolean switched = false;
		int index = 0;
		for (int i = len - 1; i >= 0; i--) {
			if (ch[i] == '1') {
				for (int j = i - 1; j >= 0; j--) {
					if (ch[j] == '0') {
						ch[j] = '1';
						ch[j + 1] = '0';
						index = j + 1;
						// System.out.println("J:" + j + " J+1:" + (j+1));
						switched = true;
						break;
					}
				}
				if (switched) {
					break;
				}
			}
		}
		int i = index + 1;
		int j = len - 1;

		while (i < j) {
			if (ch[i] == '1' && ch[j] == '0') {
				ch[i] = '0';
				ch[j] = '1';
				++i;
				--j;
			}
			++i;
		}
		StringBuffer sb = new StringBuffer();
		for (i = 0; i < len; i++) {
			sb.append(ch[i]);
		}

		return sb.toString();
	}

}

Inversions in an Array

For Array[0.....N-1], an inversion is an element pair that satisfes i<j and A[i]>A[j]. For instance, in array (1,3,5,2,4,6),  such pairs are (3,2) (5,2) (5,4), so number of inversions is 3.  The challenge is to implement an algorithm that computes the number of inversions with the array given to you.

Method1 (Brute Force Approach)

For each element, count number of elements which are on right side of it and are smaller than it.

public static int getInversionCount(int arr[])
	{
	  int invCount = 0;
	  int i, j;
	  int n = arr.length;
	 
	  for(i = 0; i < n - 1; i++)
	  {
	    for(j = i+1; j < n; j++)
	    {
	      if(arr[i] > arr[j])
	    	  invCount++;
	    }
	  }
	 
	  return invCount;
	}

Method2 ( Merge Sort Approach)

Suppose we know the number of inversions in the left half and right half of the array (let be inv1 and inv2), what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is – the inversions we have to count during the merge step. Therefore, to get number of inversions, we need to add number of inversions in left subarray, right subarray and merge().


How to get number of inversions in merge()?


In merge process, let i is used for indexing left sub-array and j for right sub-array. At any step in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j]

/* An auxiliary recursive function that sorts the input array and
	  returns the number of inversions in the array. */
	public static int mergeSort(int arr[], int temp[], int left, int right)
	{
	  int mid, invCount = 0;
	  if (right > left)
	  {
	    // Divide the array into two parts and call _mergeSortAndCountInv()
	    //   for each of the parts 
	    mid = (right + left)/2;
	  
	    // Inversion count will be sum of inversions in left-part, right-part
	    //  and number of inversions in merging 
	    invCount  = mergeSort(arr, temp, left, mid);
	    invCount += mergeSort(arr, temp, mid+1, right);
	  
	    //Merge the two parts
	    invCount += merge(arr, temp, left, mid+1, right);
	  }
	  return invCount;
	}
	  
	// This function merges two sorted arrays and returns inversion count in
	//  the arrays.
	public static int merge(int arr[], int temp[], int left, int mid, int right)
	{
	  int i, j, k;
	  int inv_count = 0;
	  
	  i = left; // i is index for left subarray
	  j = mid;  // i is index for right subarray
	  k = left; // i is index for resultant merged subarray
	  while ((i <= mid - 1) && (j <= right))
	  {
	    if (arr[i] <= arr[j])
	    {
	      temp[k++] = arr[i++];
	    }
	    else
	    {
	      temp[k++] = arr[j++];
	      inv_count = inv_count + (mid - i);
	    }
	  }
	  
	  // Copy the remaining elements of left subarray
	  // (if there are any) to temp
	  while (i <= mid - 1)
	    temp[k++] = arr[i++];
	  
	  // Copy the remaining elements of right subarray
	  // (if there are any) to temp
	  while (j <= right)
	    temp[k++] = arr[j++];
	  
	  // Copy back the merged elements to original array
	  for (i=left; i <= right; i++)
	    arr[i] = temp[i];
	  
	  return inv_count;
	}
	  

Subset Sum

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

The previous post talks about recursive approach which has exponential complexity

Lets see a dynamic programming approach which has polynomial complexity.

// Returns true if there is a subset of set[] with sun equal to given sum
	public static boolean isSubsetSumDynamic(int set[], int n, int sum)
	{
	    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
	    //  with sum equal to i
	    boolean subset[][] = new boolean[sum+1][n+1];
	 
	    // If sum is 0, then answer is true
	    for (int i = 0; i <= n; i++)
	      subset[0][i] = true;
	 
	    // If sum is not 0 and set is empty, then answer is false
	    for (int i = 1; i <= sum; i++)
	      subset[i][0] = false;
	 
	     // Fill the subset table in bottom up manner
	     for (int i = 1; i <= sum; i++)
	     {
	       for (int j = 1; j <= n; j++)
	       {
	         subset[i][j] = subset[i][j-1];
	         if (i >= set[j-1])
	           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
	       }
	     }
	     return subset[sum][n];
	}

Subset sum

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

 

public class SubsetSum {

	public static boolean isSubsetSum(int set[], int n, int sum)
	{
	   if (sum == 0)
	     return true;
	   if (n == 0 && sum != 0)
	     return false;
	 
	   if (set[n-1] > sum)
	     return isSubsetSum(set, n-1, sum);
	 
	   return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
	}
	 
	public static void main(String args[])
	{
	  int set[] = {3, 34, 4, 12, 5, 2};
	  int sum = 9;
	  
	  if (isSubsetSum(set, set.length, sum) == true)
	     System.out.println("Found a subset with given sum");
	  else
	     System.out.println("No subset with given sum");
	}
	
}

Continuous sub array adding to a number

Given an array having positive integers, find a continuous sub array which adds to a given number.?

Complexity:

Despite having two nested loops, this code runs in linear time because i and j never decrease, and can only be incremented O(N) times.

public class ContinousSum {

	public static void findContinousArray(int A[], int target) {
		for (int i = 0, j = 0, sum = 0; i < A.length; i++) {
			while(j < A.length && sum < target) {
				sum += A[j];
				if(sum >= target)break;
				j++;
			}
			if (sum == target) {
				System.out.println("sub array indices" + i + "," + j);
				return;
			}
			sum -= A[i];
		
		}

	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 4 };
		findContinousArray(a, 5);

	}
}

Postfix expression evaluation

Algorithm:

for each expression token:
  if the token is a number:
    push it
  else (the token is an operator, OP):
    second = pop();
    first = pop();
    compute: result = first OP second
    push the result on the stack

when there are no more tokens, pop the answer off the stack

4 2 3 - -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  3      [3, 2, 4]
  -      [-1, 4]
  -      [5]
 END     []    ⇒ answer = 5

public static Double evaluatePostfix(String rpn) {
		char[] exp = rpn.toCharArray();
		Stack<Double> stack = new Stack<Double>();

		int len = exp.length;
		for (int i = 0; i < len; i++) {
			if (!isOperator(exp[i])) {
				stack.push(Double.parseDouble("" + exp[i]));
			} else {
				double b = stack.pop();
				double a = stack.pop();
				stack.push(evaluate(a, b, exp[i]));
			}
		}
		double result = stack.pop();
		System.out.println("Result:" + result);
		return result;
	}

	private static Double evaluate(double a, double b, char operator) {
		double result = 0.0;
		switch (operator) {
		case '/':
			result = a / b;
			break;
		case '*':
			result = a * b;
			break;
		case '+':
			result = a + b;
			break;
		case '-':
			result = a - b;
			break;
		}
		return result;
	}

Infix to postfix Conversion

Algorithm:

for each expression token:
  if the token is a number:
    add it to output
  else if the token is a left paren:
    push it
  else if the token is a right paren:
    pop and add to output all tokens on stack up to left paren
    pop the left paren, but don't add to output
  else if the token is an operator:
    if stack is empty or the top is a left paren:
       push it
    else if the stack top is a lower precedence operator:
       push it
    else
       pop and add to output all operators of higher or equal precedence 
       push it

when there are no more tokens,
  pop and add to output all remaining operators on stack

Example:

7 - 3 + 5 - 2

token   stack     output
-----   -----     ------
        []
  7               7
  -     [-]
  3               7 3
  +     [+]       7 3 -
  5               7 3 - 5
  -     [-]       7 3 - 5 +
  2               7 3 - 5 + 2
 END    []        7 3 - 5 + 2 -

Code:

import java.util.*;

public class InfixToPostfix {
	
	// Translate's the expression to postfix
	public static String translate(String expression) {

		String output = "";
		char character = ' ';
		Stack<Character> stack = new Stack<Character>();

		for (int x = 0; x < expression.length(); x++) {
			character = expression.charAt(x);

			if (isOperator(character)) {
				while (!stack.empty()
						&& precedence(stack.peek()) >= precedence(character))
					output += stack.pop() + " ";
				stack.push(character);
			} else if (character == '(') {
				stack.push(character);
			} else if (character == ')') {
				while (!stack.peek().equals('('))
					output += stack.pop() + " ";
				stack.pop();
			} else {
					output += character;
			}
		}

		while (!stack.empty()) {
			output += stack.pop() + " ";
		}

		return output;
	}

	// Check priority on characters
	public static int precedence(char operator) {
		if (operator == '+' || operator == '-')
			return 1;
		else if (operator == '*' || operator == '/')
			return 2;
		else
			return 0;
	}

	public static boolean isOperator(char element) {
		if (element == '*' || element == '-' || element == '/'
				|| element == '+')
			return true;
		else
			return false;
	}
	
	public static void main(String args[])
	{
		System.out.println("Postfix conversion"+InfixToPostfix.translate("((2 * 3) - 5) / 4"));
		
	}
}