Given: an array x of N elements, sorted in ascending order and an integer a Try to find a in x. 1. if a is in x: return its position 2. if a is not in x: return the position, where to insert a in x, such that x remains sorted

Note: Question is pretty simple but there are lots of test cases to cover if you find any test case is not working , feel free to comment.

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
{
int x[]=new int[]{2, 6, 8, 10,13};
  int a=11;
        System.out.println(search(x,a));
}
public static int search(int x[], int a)
{
       if(x==null || x.length==0) return 0;
     
       int pos=-1;
       int l=0;
       int length=x.length;
       int r=length-1;
     
       if(a<x[0])
       return 0;
     
       if(a>x[length-1])
       return length;
       if(r<=0)
        return 0;
       if(1==length){
        if(a>x[0])
        return 1;
        else if(a<=x[0])
        return 0;
       }
     
       // [2, 6, 8, 10]   values 0 , 7 , 5 , 9 , 11
       if(l<=r)
       {
         while(l<=r)
         {
           int mid=l+((r-l)/2);
           System.out.println("l= " + l + " mid = " + mid + " r= " + r);
           if(x[mid]==a)
              return mid;
           else if(x[mid] > a && x[mid-1]<a)
                  return mid;
           else if(x[mid] < a && x[mid+1]> a)
                  return mid+1;
           else if(a<=x[mid-1])
                r=mid-1;
           else if(a>=x[mid+1])
                l=mid+1;
          }
      }
        return pos;
}
}

Run Here http://ideone.com/YuA70F

TC O(logn)

SC O(1)

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)

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.

Given an integer N, print numbers from 1 to N in lexicographic order , You are not allowed to use any library functions

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order.

Example if  nCards=9 and ICut=6 then for  N=123456789 , you need 3 shuffle to get the original positions , wondering how , try it now and  feel free to post comment here .

Find all 10 digit numbers which are perfect squares efficiently

Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins. The candidate should write a function that given N decides who wins (first or second player)?

Design a function f, such that: f(f(n)) == -n Where n is a 32 bit signed integer; you can't use complex numbers arithmetic. If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Two strings can be chained if the first one ends with the same character second one starts with. Given set of 'n' strings, how can we verify efficiently, whether they can be chained or not?

e.g. cat, dog, toad  answer is YES.
for    tape ate ass answer is NO.

A circular array A[1, . . . , n] is an array such that n ≥ 3 and A[1] and A[n] are considered to be adjacent elements just like A[1] and A[2], A[2] and A[3], etc., are adjacent. We are given a circular array A[1, . . . , n] of non-negative integers. For any i, j ∈ {1, 2, . . . , n} such that i != j, dist(i, j) = max {|i − j|, n − |i − j|}. Design a linear time algorithm that computes a maximum number t such that for some i, j ∈ {1, 2, . . . , n}, i != j, t = A[i] + A[j] + dist(i, j).