CareerCup

Hold on.

I guess the above code fails if there are odd distinct elements.
Example consider: x = { 1,2,3}

cond1: sum( y.hours<=x.hours) >= (count(*)+1)/2
cond2: sum( y.hours>=x.hours) >= (count(*)+1)/2+1
for element 1:
1 >= 2 -- false -no need to consider the other condition

for 2:
cond1: 2>= 2 true
cond2: 2 >= 3 -- false

for 3:
cond1: 3 >=2 true
cond2: 1>= 3 false

so, the median function fails. Let me know if i misunderstood.

public class ExcelColumnGenerator {
	char[] alpha;
	int base;

	ExcelColumnGenerator(int base){
		this.base = base;
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i< base; i++){
             sb.append((char)('A'+i));
		}
		alpha = sb.toString().toCharArray();
	}
	public String column(int n){
        boolean flag = false;
        int r;
        StringBuffer sb = new StringBuffer();
		do{
			r = n%base;
			if(flag == false){
				sb.insert(0, alpha[r]);
				flag = true;
			}
			else{
				sb.insert(0, alpha[r-1]);
			}
			n = n/base;
		}while(n>0);
		
		return sb.toString();
	}
	public static void main(String[] args){
		ExcelColumnGenerator ecg = new ExcelColumnGenerator(26);
		for (int i=0;i<100;i++){
			System.out.println("n == " + i + " Column: "+ ecg.column(i));
		}
		System.out.println("n == " + 1000 + " Column: "+ ecg.column(1000));
	}
}

Output:
n == 0 Column: A
n == 1 Column: B
n == 2 Column: C
n == 3 Column: D
n == 4 Column: E
n == 5 Column: F
n == 6 Column: G
n == 7 Column: H
n == 8 Column: I
n == 9 Column: J
n == 10 Column: K
n == 11 Column: L
n == 12 Column: M
n == 13 Column: N
n == 14 Column: O
n == 15 Column: P
n == 16 Column: Q
n == 17 Column: R
n == 18 Column: S
n == 19 Column: T
n == 20 Column: U
n == 21 Column: V
n == 22 Column: W
n == 23 Column: X
n == 24 Column: Y
n == 25 Column: Z
n == 26 Column: AA
n == 27 Column: AB
n == 28 Column: AC
n == 29 Column: AD
n == 30 Column: AE
n == 31 Column: AF
n == 32 Column: AG
n == 33 Column: AH
n == 34 Column: AI
n == 35 Column: AJ
n == 36 Column: AK
n == 37 Column: AL
n == 38 Column: AM
n == 39 Column: AN
n == 40 Column: AO
n == 41 Column: AP
n == 42 Column: AQ
n == 43 Column: AR


n == 1000 Column: ALM

Binary Search based algo.
Java Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;


public class SearchMinIndexInRotatedSortedArray {

    public static int search(List<Integer> a,int lo, int hi){
        
        int mid = ( lo + hi) >>> 1;
        if( hi - lo == 1){
            if(a.get(lo) < a.get(hi))
                return lo;
            else 
                return hi;
        }
        else if( hi == lo){
            return hi;
        }
        
        if( a.get(lo) <= a.get(mid)){
                        if( a.get(mid) <= a.get(hi) ){
                            return lo;
                        }
                        else{
                return search(a, mid, hi);
                        }
        }
        else{
            return search(a, lo, mid);
        }
    }
    
    public static void main(String[] args){
        List<Integer> a = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
        List<Integer> b = null;
        b = new ArrayList<Integer>();

        for(int i=0;i< a.size(); i++){
            b.clear();
            b.addAll(a);
            Collections.rotate(b, i);
            System.out.println("Searching in: " + b + " index of min: " + search(b, 0, b.size()-1));
        }
    }
}

Output of above program:
Searching in: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] index of min: 0
Searching in: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] index of min: 1
Searching in: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] index of min: 2
Searching in: [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] index of min: 3
Searching in: [7, 8, 9, 10, 1, 2, 3, 4, 5, 6] index of min: 4
Searching in: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5] index of min: 5
Searching in: [5, 6, 7, 8, 9, 10, 1, 2, 3, 4] index of min: 6
Searching in: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] index of min: 7
Searching in: [3, 4, 5, 6, 7, 8, 9, 10, 1, 2] index of min: 8
Searching in: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] index of min: 9

In the even case: peep elements in both the heaps, let they be e1 and e2. In the solution I have given (e1+e2)/2 as my median, lets see how to attempt wikipedia cases.

Case 1: choose the smallest
simple return Math.min(e1,e2)
Case 2: always the largest one
simple return Math.max(e1,e2)
Case 3: randomly choose between the two
if random.randnextint(2) == 1 return e1 else e2
Hope this helps.

Its a modification of combinations algorithm, just that we need subsets of "r" elements. Just trace it down its pretty simple and straight forward.

Hope you know how to find mean ( sum of elements till now / number of elements ).

For finding median:

Have two heaps :
one min heap and one max heap and keep their sizes ( number of element in its heap)

To find median:

1. if both heaps are of equal size peep top element from both the heaps, sum them and divide the sum by 2 and return.

2. else return the top element of the heap having max elements.

Insertion of x:

1 if x is less than median insert it into max heap else insert into min heap.
2. if heap size differ by > 1 adjust them ( pop from largest heap and insert into small heap).

Python code:

uses extra O(r) space.

def combinations(a,n,used,start,depth,used_count):
    if used_count == depth:
        for i in range(depth):
            print a[used[i]],
        print
        return
    for i in range(start,n):
        used[depth]=i
        combinations(a,n,used,i+1,depth+1,used_count)
        used[depth]=-1
def main():
    a=[i for i in range(5)]
    for r in range(1,3):
        used = [-1]*r
        print "combinations of ",r, " elements of ",a, " are: "
        combinations(a,len(a),used,0,0,r)
main()

Output of above code:
combinations of  1  elements of  [0, 1, 2, 3, 4]  are: 
0
1
2
3
4
combinations of  2  elements of  [0, 1, 2, 3, 4]  are: 
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Java code.
Complexity: O(n) moves. Space O(1).

Assumptions: equal number of chars and digits and we should arrange (char||digit)*

Executions:

input: abcd1234ef56 modified string: a1b2c3d4e5f6
input: a1234bcdef56gh78 modified string: a1b2c3d4e5f6g7h8
input: a1 modified string: a1
input: a1234bcd modified string: a1b2c3d4
input: abcd1234 modified string: a1b2c3d4

public class OddEven {
  public static void main(String[] args){
    OddEven oe = new OddEven();
    oe.classify("abcd1234ef56");
    oe.classify("a1234bcdef56gh78");
    oe.classify("a1");
    oe.classify("a1234bcd");
    oe.classify("abcd1234");
  }
  private void classify(String string) {
    //Each position is touched at most once hence O(length of array)
    int nn=0,nc=0,mx=-1;
    char[] a = string.toCharArray();
    
    int state = 0 ; //expect char
    for(int i=0;i<string.length();i++){
      if(state == 0){
        if(ischar(a[i])){
          if( i> mx){
            nc++;
            mx = Math.max(i, mx);
          }
          state = 1;
        }
        else{//expected char but got a number
          boolean found = false;
          int j=i+1;
          while(!found){
            if(ischar(a[j])){
              found=true;
              break;
            }
            j++;
          }
          if(!found || j >= string.length()){
            //done with processing
            return;
          }
          char t=a[i];
          a[i]=a[j]; nc++; mx = Math.max(j, mx);
          a[j]='-';
          while(true){
            char tt;
            if(ischar(t)){
              tt = a[nc*2]; mx = Math.max(nc*2, mx);
              a[nc*2] = t; nc++;
              t=tt;
            }
            else{
              tt = a[nn*2+1]; mx = Math.max(nn*2+1, mx);
              a[nn*2+1] = t;
              nn++;
              t=tt;
            }
            if(t=='-'){
              break;
            }
          }
        }
        state=1;
      }
      else if(state == 1){
        if(isdigit(a[i])){
          if(i> mx){
            nn++;
            mx = Math.max(i, mx);
          }
          state = 0;
        }
        else{//expected number but got character
          boolean found = false;
          int j=i+1;
          while(!found){
            if(isdigit(a[j])){
              found=true;
              break;
            }
            j++;
          }
          if(!found || j >= string.length()){
            //done with processing
            return;
          }
          char t=a[i];
          a[i]=a[j]; nn++; mx = Math.max(j, mx);
          a[j]='-';
          while(true){
            char tt;
            if(ischar(t)){
              tt = a[nc*2]; mx = Math.max(nc*2, mx);
              a[nc*2] = t; nc++;
              t=tt;
            }
            else{
              tt = a[nn*2+1]; mx = Math.max(nn*2+1, mx);
              a[nn*2+1] = t;
              nn++;
              t=tt;
            }
            if(t=='-'){
              break;
            }
          }
        }
        state=0;
      }
    }
    System.out.print("input: " + string + " modified string: " ); System.out.println(a);
  }

  private static boolean isdigit(char c) {
    return ( c>='0' && c<='9');
  }
  private static boolean ischar(char c) {
    return ( c>='a' && c<='z');
  }
}