Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

One solution is to use two priority heaps: a max heap for the values below the median, and a min heap for the values above the median. The median will be largest value of the max heap.
When a new value arrives it is placed in the below heap if the value is less than or equal to the median, otherwise it is placed into the above heap. The heap sizes can be equal or the below heap has one extra. This constraint can easily be restored by shifting an element from one heap to the other. The median is available in constant time, so updates are O(lg n).

1       private Comparator<Integer> maxHeapComparator, minHeapComparator;
2       private PriorityQueue<Integer> maxHeap, minHeap;
3       public void addNewNumber(int randomNumber) {
4              if (maxHeap.size() == minHeap.size()) {
5                      if ((minHeap.peek() != null) &&
6                               randomNumber > minHeap.peek()) {
7                               maxHeap.offer(minHeap.poll());
8                               minHeap.offer(randomNumber);
9                      } else {
10                              maxHeap.offer(randomNumber);
11                     }
12             }
13             else {
14                     if(randomNumber < maxHeap.peek()){
15                              minHeap.offer(maxHeap.poll());
16                              maxHeap.offer(randomNumber);
17                     }
18                     else {
19                              minHeap.offer(randomNumber);
20                     }
21             }
22      }
23      public static double getMedian() {
24             if (maxHeap.isEmpty()) return minHeap.peek();
25             else if (minHeap.isEmpty()) return maxHeap.peek();
26             if (maxHeap.size() == minHeap.size()) {
27                     return (minHeap.peek() + maxHeap.peek()) / 2;
28             } else if (maxHeap.size() > minHeap.size()) {
29                     return maxHeap.peek();
30             } else {
31                     return minHeap.peek();
32             }
33      }

Maximum sum subarray

       public static int getMaxSum(int[] a) {
2             int maxsum = 0;
3             int sum = 0;
4             for (int i = 0; i < a.length; i++) {
5                    sum += a[i];
6                    if (maxsum < sum) {
7                           maxsum = sum;
8                    } else if (sum < 0) {
9                           sum = 0;
10                   }
11            }
12            return maxsum;
13     }

Write a program to find whether a machine is big endian or little endian.

1     #define BIG_ENDIAN 0
2     #define LITTLE_ENDIAN 1
3     int TestByteOrder() {
4             short int word = 0x0001;
5             char *byte = (char *) &word;
6             return (byte[0] ? LITTLE_ENDIAN : BIG_ENDIAN);
7     }

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

1. Initialize array magic and queues Q3, Q5 and Q7
2. Insert 1 into magic.
3. Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
4. Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
5. If x was found in:
            Q3 -> append x*3, x*5 and x*7 to Q3, Q5 and Q7. Remove x from Q3.
            Q5 -> append x*5 and x*7 to Q5 and Q7. Remove x from Q5.
            Q7 -> only append x*7 to Q7. Remove x from Q7.
            Note: we do not need to append x*3 and x*5 to all lists because
            they will already be found in another list.
6. Repeat steps 4 - 6 until we’ve found k elements.



1        public static int getKthMagicNumber(int k) {
2                 if (k <= 0) return 0;
3                 int val = 1;
4                 Queue<Integer> Q3 = new LinkedList<Integer>();
5                 Queue<Integer> Q5 = new LinkedList<Integer>();
6                 Queue<Integer> Q7 = new LinkedList<Integer>();
7                 Q3.add(3);
8                 Q5.add(5);
9                 Q7.add(7);
10                for (--k; k > 0; --k) { // We’ve done one iteration already.
11                        val = Math.min(Q3.peek().intValue(),
12                                  Math.min(Q5.peek().inValue(), Q7.peek().intValue()));
13                        if (val == Q7.peek()) {
14                                Q7.remove();
15                        } else {
16                                if (val == Q5.peek()) {
17                                        Q5.remove();
18                                } else { // must be from Q3
19                                        Q3.remove();
20                                        Q3.add(val * 3);
21                                }
22                                Q5.add(val * 5);
23                        }
24                        Q7.add(val * 7);
25                }
26                return val;
27       }

Implement an algorithm to print all valid (e.g., properly opened and closed) combi- nations of n-pairs of parentheses.

We can solve this problem recursively by recursing through the string. On each iteration, we
have the index for a particular character in the string. We need to select either a left or a right
paren. When can we use left, and when can we use a right paren?
»»    Left: As long as we haven’t used up all the left parentheses, we can always insert a left
      paren.
»»    Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we
      get a syntax error? We will get a syntax error if there are more right parentheses than
      left.
So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (eg, if there are more left parens used), then we’ll insert a right paren and recurse.

1        public static void printPar(int l, int r, char[] str, int count) {
2                 if (l < 0 || r < l) return; // invalid state
3                 if (l == 0 && r == 0) {
4                         System.out.println(str); // found one, so print it
5                 } else {
6                         if (l > 0) { // try a left paren, if there are some available
7                                str[count] = ‘(‘;
8                                printPar(l - 1, r, str, count + 1);
9                         }
10                        if (r > l) { // try a right paren, if there’s a matching left
11                               str[count] = ‘)’;
12                               printPar(l, r - 1, str, count + 1);
13                        }
14                }   
15       }
16          
17       public static void printPar(int count) {
18                char[] str = new char[count*2];
19                printPar(count, count, str, 0);
20       }

Sort a stack in Ascending order

Sorting can be performed with one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the newitem. Since the items we removed are on the original stack, we’re back where we started.

The algorithm is O(N^2) and appears below.

1       public static Stack<Integer> sort(Stack<Integer> s) {
2                Stack<Integer> r = new Stack<Integer>();
3                while(!s.isEmpty()) {
4                       int tmp = s.pop();
5                       while(!r.isEmpty() && r.peek() > tmp) {
6                               s.push(r.pop());
7                       }
8                       r.push(tmp);
9                }
10               return r;
11      }

Queue Using Stack

1      public class MyQueue<T> {
2             Stack<T> s1, s2;
3             public MyQueue() {
4                    s1 = new Stack<T>();
5                    s2 = new Stack<T>();
6             }
7         
8             public int size() {
9                    return s1.size() + s2.size();
10            }
11        
12            public void add(T value) {
13                   s1.push(value);
14            }
15        
16            public T peek() {
17                   if (!s2.empty()) return s2.peek();
18                   while (!s1.empty()) s2.push(s1.pop());
19                   return s2.peek();
20            }
21        
22            public T remove() {
23                   if (!s2.empty()) return s2.pop();
24                   while (!s1.empty()) s2.push(s1.pop());
25                   return s2.pop();
26            }
27     }

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Use an additional stack which keeps track of
the mins.

1      public class StackWithMin2 extends Stack<Integer> {
2               Stack<Integer> s2;
3               public StackWithMin2() {
4                      s2 = new Stack<Integer>();       
5           }
6           public void push(int value){
7                  if (value <= min()) {
8                         s2.push(value);
9                  }
10                 super.push(value);
11          }
12          public Integer pop() {
13                 int value = super.pop();
14                 if (value == min()) {
15                        s2.pop();           
16                 }
17                 return value;
18          }
19          public int min() {
20                 if (s2.isEmpty()) {
21                        return Integer.MAX_VALUE;
22                 } else {
23                        return s2.peek();
24                 }
25          }
26     }

Length of unique subString in the given string

package arrays;

public class UniqueSubString {

public static void main(String[] args){

String s = "geeksforgeeks";
char[] str = s.toCharArray();
   int[] visited = new int[256];
   int max_length=1;
   int prev;

    //System.out.println(visited.length);
   for(int i=0;i<visited.length;i++)
    visited[i]=-1;
 
   visited[str[0]] = 0;
   int cur_length=1;

   for(int i=1;i<str.length;i++) {
    prev = visited[str[i]];
   if(prev == -1 || i-cur_length > prev){
    cur_length++;
   
   }
   
   else {
    if(max_length < cur_length)
    max_length = cur_length;
    cur_length = i - prev;
   
   }
   visited[str[i]] = i;
 
   }
 
   if(cur_length > max_length)
    max_length = cur_length;
   System.out.println(max_length);

}
}

The input : ABDEFGABEF
The length 6

Time Complexity: O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.
Auxiliary Space: O(d)

Pairs in array sum upto K

package arrays;

import java.util.HashMap;
import java.util.Map;


public class ArrayPairs {
public static void main(String[]args){
  int a[]={3,4,5,4,1,2};
  int sum=9;
  boolean found=false;
  Map<Integer,Integer> map = new HashMap<Integer,Integer>();

 
  for(int b : a){
    if(map.containsKey(b)){
      System.out.println("Pairs are :" + b + "," + map.get(b));
      found = true;
    }
    else {
      int diff=sum-b;
      map.put(diff, b);
    }
  }
  if(!found)
    System.out.println("No such pairs are there");
}
}

Reverse Dutch Flag problem

Given an array a1 a2 a3 a4.. b1 b2 b3... convert it to a1 b1 a2 b2 a3 b3 ...

 public static void main(String[] args) {
  int a[]={0,0,0,0,1,1,1,1};
  reverseDutch(a,0,a.length-1);
  for(int b : a)
    System.out.print(b);;
  
 }
 
 public static void reverseDutch(int a[],int low,int high){
  
  if(low==high) return;
  
  int centre=(low+high)/2;
  int start= 1 + (low+centre)/2;
  //swap elements ard centre
  // 00001111 => 00110011 => 01010101
  for(int k=1,i=start;i<=centre;i++,k++){
   int temp=a[i];
   a[i]=a[centre+k];
   a[centre+k]=temp;
   
  }
  
  reverseDutch(a,low,centre);
  reverseDutch(a,centre+1,high);
  
 }

O(n lgn)

Majority element in an array ( Moores Voting algorithm)

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

// Find out the candidate occurs maximum no of times
int candPos = 0,count=1;
for(int i=0;i<a.length;i++){
if(a[candPos]==a[i])
count++;
else
count--;
if(count==0){
candPos=i;
   count=1;
}
}

// now the candidate element is in position candPos
int n=0;
for(int i=0;i<a.length;i++)
if(a[candPos] == a[i])
n++;

// found out no of times candidate has occured in array
if(n > a.length/2)
System.out.println("Majority Element is : " + a[candPos]);
else
System.out.println("No majority element");

}

Sort array of 0s,1s and 2s in single scan

public static void main(String[] args){
int a[]={1,2,0,2,1,2,1,0,0,0,1,0,2,1};
int low=0,high=a.length-1;
int mid;
while(a[low]==0 && low<high)
 low++;
while(a[high]==2 && high>=0)
 high--;
mid=low;
while(mid<high)
{
if(a[mid]==0){
a[low]=0;
a[mid]=1;
low++;
mid--;
      }
else if(a[mid]==1)
mid++;
else{
a[mid]=1;
a[high]=2;
high--;
mid++;
}

}
for(int b : a)
System.out.print(b);


}

Sort an array of 0s and 1s

Maintaining count : O(n) two traversals

Single scan : O(n)


public static void main(String[] args) {
int a[]={0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1};
int i=0,j=a.length-1;
while(i<j){
while(a[i]==0 && i<j)
i++;
        while(a[j]==1 && i<j)
j--;
if(i<j){
a[i]=0;
a[j]=1;
i++;
j--;
}
}

for(int b : a)
System.out.print(b);
}
}

Can use QuickSort partitioning algorithm also for doing the same !!!

Checking whether given array elements are consecutive

The idea is to check for following two conditions. If following two conditions are true, then return true.

1) max – min + 1 = n where max is the maximum element in array, min is minimum element in array 
                               and n is the number of elements in array.
2) All elements are distinct.

import java.util.ArrayList;
import java.util.HashMap;

public class ArrayConsecutive {

public static void main(String[] args){
int a[]={1,2,3,4,5,6,7,8,9,10,10};
ArrayList<Integer> b=new ArrayList<Integer>();
int max=findmax(a);
int min=findmin(a);
if(max-min+1 != a.length)
System.out.println("Not consecutive");
else {
if(!Distinct(a))
System.out.println("Not consecutive");
else
System.out.println("Given array elements are consecutive");
}
}


public static int findmax(int[] a){
int max=a[0];
for(int i=1;i<a.length;i++)
if(max < a[i])
max=a[i];
return max;
}

public static int findmin(int[] a){
int min=a[0];
for(int i=1;i<a.length;i++)
if(min > a[i])
min=a[i];
return min;
}

public static boolean Distinct(int a[])
{
HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
Integer count;
for(int i=0;i<a.length;i++){
count=map.get(a[i]);
if(count==null)
map.put(a[i], (count==null?1:count++));
else{
if(count==1)
return false;
}  


}
return true;
}
}

Search in 2D array rowwise and columnwise sorted

public static void search(int x,int a[][])
  {
    int i=0;
    int j=a[0].length-1;
    while(i<a.length && j>=0) {
      if(a[i][j]==x){
        System.out.println(x + " is found at position [" + i + "," + j + "]");
        return;
      }
      if(a[i][j]>x)
        j--;
      else
        i++;
    }
    System.out.println("Element not found in the given matrix");
  }

Two non-repeating elements in an array

package arrays;

import java.util.HashMap;
import java.util.Map;


/**
 * @author ssundara
 *
 */
public class Two_non_rep {
 
  /**
   * @param args
   */
  public static void main(String args[]){

  int a[] = {2, 4, 7, 9, 2, 4};
 
  // METHOD 1
  int xor = a[0];
  for(int i=1;i < a.length;i++)
    xor = xor ^ a[i];
  // output xor will have the bits set on places where the bits of two non rep_no are differing.
  System.out.println(xor);
 
 
  //find d rightmost set bit, since finding tat ll be easy
  int rightmost_set_bit;
  rightmost_set_bit = xor & ~(xor-1);
  System.out.println(rightmost_set_bit);
 
  // x n y will have non rep_nos
  int x = 0,y = 0;
  for(int j = 0;j < a.length; j++){
    if((a[j] & rightmost_set_bit)!=0)
      x ^= a[j];
    else
      y ^= a[j];
 
}
  System.out.println("Two non rep nos are : :" + x + "," + y);

 
  // METHOD 1
 
  Map<Integer,Integer> map= new HashMap<Integer,Integer>();
  Integer count;
  for(int i=0;i < a.length;i++){
     count = map.get(a[i]);
     map.put(a[i], count == null ? 1 :count + 1);
  }
  System.out.println("Using Hashmap");
  for(int i=0;i < a.length;i++)
    if(map.get(a[i])==1)
       System.out.println(a[i]);
}
}

Printing all combinations of given array of Strings

public static void comb(String[] a){
    int n=a.length;
    for(int i=1;i<Math.pow(2, n);i++){
      int pos=0;
      int j=i;
      while(j!=0){
        if((j & 1)==1){
          System.out.print(a[pos]);
        }
        pos++;  
        j=j>>1;  
     }
     System.out.println("");
     }
    }

Matrix set 1 in column and row if any element in tat row or column is 1

package arrays;

public class Matrix_0_1_set_space {

public static void main(String[] args){
int a[][] = {{1,0,0,1},{0,0,1,0},{0,0,0,0}};
int rowsize = a.length;
int colsize = a[0].length;
int rowflg=0,colflg=0;
System.out.println(rowsize + ":" + colsize);

//To find whether first row needs to be set
for(int i=0;i<rowsize;i++) {
if(a[i][0]==1)
rowflg=1;
break;
}

//To find whether firsst column needs to be set
for(int j=0;j<colsize;j++){
if(a[0][j]==1)
colflg = 1;
break;
}

// Use 1st row n 1st column to chk
for(int i=1;i<rowsize;i++)
for(int j=1;j<colsize;j++)
if(a[i][j] == 1)
{
a[0][j]=1;
a[i][0]=1;
}


for(int i=1;i<rowsize;i++)
for(int j=1;j<colsize;j++)
if(a[0][j]==1 || a[i][0]==1)
a[i][j]=1;

if(rowflg==1){
for(int j=0;j<colsize;j++)
a[0][j]=1;
}

if(colflg==1){
for(int i=0;i<rowsize;i++)
a[i][0]=1;
}

for(int i=0;i<rowsize;i++){
System.out.println();
for(int j=0;j<colsize;j++)
System.out.print(a[i][j]);

}
}
}

Searching an Element in a Rotated Sorted Array

Reducing the search space by half : O(lgn)


public static void search(int[] a,int element){
int i=0,j=a.length-1;
boolean found=false;;
while(i<=j){
int middle = (i+j)/2;
if(a[middle]==element){
found=true;
System.out.println("Element is found @ index :" +middle+ " of rotated array");
}


if(a[i] < a[middle]){ // first half is in increasing order
if(a[i] <= element && element < a[middle])
j=middle-1;
else
i=middle+1;
}

else {
if(element > a[middle] && element <= a[j])
i=middle+1;
else
j=middle-1;

}
}

if(!found)
  System.out.println("Given element not found");
}