Tuesday, April 1, 2014

Given a element, find the strictly greater element in sorted array - 1st post for 2k14

E.g. if array is // [ a, c, d, h, k, l, l, l, o, u, x, z ]
//if given  m -> o
// if given k -> l


import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(search(new char[]{'b', 'c', 'd', 'h', 'k', 'l', 'l', 'l', 'o', 'u', 'x', 'z'},'b')) ;
}

static char search(char a[],char find)
{
   if(a==null || a.length==0)
   return ' ';// if nothing found
 
   int start=0;
   int end=a.length-1;
   if(start>end) return ' ' ; //|| find>=a[end]) return ' ';
   if(find <a[start]) return a[start];
   if(start==end && a[start]>find)
   return a[start];
   while(start<end)
   {
       int mid=start+(end-start+1)/2; //to minimize over flow
       if(mid+1<=end && find>=a[mid] && find <a[mid+1])
              return a[mid+1];
       else if(mid-1>=0 && find < a[mid] && find >= a[mid-1])
        return a[mid];
       else if(find >=a[mid])
           start=mid;
       else if( find <a[mid])
           end=mid;
       else
          return ' ';
      System.out.println("start= " + start + ":::" +  " End= " + end);
   }
   return ' ';//if nothing found , return special character
}
}

Time Complexity O(logn)
Space Complexity O(1)

Monday, December 9, 2013

Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.