CareerCup

1. we can search at index 0,1,2,4,8,16....
2. at the point we get getItemAt(x) == 1, our required index at x/2 < ans_index <= x
3. from (x/2)+1 to x we can do binary search and can find the required index

/**
 * You are given a list of integers. 
 * You can call only one method on the list:getItemAt(x), 
 * which will return the integer at the index x from the list. 
 *
 * The list starts with value 0 and it goes on to have value 0 continuously until some index. 
 * After the index the list continues to have value 1 till the end. 
 *
 * You do not know the size of the list. 
 * Its huge. 
 * You need to find the index from where the value 1 begins in the list.
 * @author patrick_diloreto
 *
 */
public class FindPivot {

	public static void main(String[] args) {
		//pivot-index = 16
		int[] elements = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
		
		int index = findPivotIndex(elements, 0, 0);
		System.out.println("16 == " + index);
		assert(16 == index);
	}
	
	public static int findPivotIndex(int[] elements, int index, int previous) {
		int value = elements[valueFor(index)];
		if(value == 0)
			return findPivotIndex(elements, index+1, index);
		else {
			//value = 1
			return binarySearch(elements, valueFor(previous), valueFor(index));
		}
	}
	
	private static int binarySearch(int[] elements, int start, int end) {
		if(end == start)
			return start;
		else {
			int middle = (start + end)/2;
			if(start == middle)
				return end;
			return (elements[middle]==0) ? 
					binarySearch(elements, middle, end) :
					binarySearch(elements, start, middle);
		}
	}
	
	private static int valueFor(int index) {
		if(index == 0) {
			return 0;
		}
		else {
			return (int)Math.pow(2, index);
		}
	}
}

This problem can be solved by using binary search to get the first position of 1 in the list. Here is the logic:
a. First check for the middle position of the array. If the mid is not 1 then you do not have to check in the left subarray as it will contain only 0s. For it you just have to check the right subarray.

#include <stdio.h>
#include <stdlib.h>

int firstPosOfOne(int arr[],int low,int high)
{
    if(low==high)
    {
        if(arr[low]==1)
            return low;
    }
    if(low+1==high)
    {
        if(arr[high]==1)
            return high;
        else if(arr[low]==1)
            return low;
    }
    else
    {
        int mid=low+(high-low)/2;
        if(arr[mid]==1)
            return mid;
        firstPosOfOne(arr,mid+1,high);
    }
}
int main()
{
    int arr[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1};
    int n=sizeof(arr)/sizeof(arr[0]);
    printf(" First position of one occurs at %d location in the array ",firstPosOfOne(arr,0,n-1));
}

Used List.get in place of getItemAt in below answer

import java.util.LinkedList;
import java.util.List;


public class ZeroToOne {

	public static void main(String[] args) {
		int zero = 1000; //Zero count
		int one = 9; //One Count
		List<Integer> list = new LinkedList<>();
		ZeroToOne zto = new ZeroToOne();

		for (int i = 0; i < zero; i++)
			list.add(0);

		for (int i = 0; i < one; i++)
			list.add(1);

		System.out.println(zto.getZeroToOnePos(list));
	}

	public int getZeroToOnePos(List<Integer> list) {
		int start = 0;
		int end = 0;
		int factor = 2;

		/*
		 * Narrow down search area by exponential movements and
		 * adjust end point if gone beyond original list.
		 */
		while(true) {
			/*
			 * try-catch to check if gone beyond list.
			 * In case of c, we can check for value != 0 and 1
			 */
			try {
				if(list.get(end) == 1)
					break;				
				
				start = end + 1;
				end += factor;
				factor *= 2;
			} catch(Exception e) {
				//Assuming IndexOutOfBounds or similar
				
				/*
				 * Went beyond the list boundary. Re-align end position
				 */
				factor = (end - start) / 2;
				end = start + factor;

				if (start == end)
					return end + 1;
			}
		}

		/*
		 * Binary search for 0-1 in identified range.
		 */
		while (true) {
			if (start >= end)
				return end;
			
			int middle = (start + end) / 2;
			int val = list.get(middle);
			if (1 == val) {
				if (list.get(middle - 1) != 1) // can be a '== 0' check also
					return middle;
				else
					end = middle - 1;
			} else {
				start = middle + 1;
			}
		}
	}
}