## Labs247 Interview Question for Tech Leads

Team: Unknown
Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 4 vote

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

Comment hidden because of low score. Click to expand.
2

modification
1. search index exponentially 0,1,2,4,8,16,....
2. when you encounter 1 at any index, it means the transition 0->1 lies within x/2 and x

Till this step the above algorithm is correct.
But what if x is 100 million?? you do not want to operate a binary search on 50 million numbers. We already have a function which performs exponential search.
therefore 3rd step :

3. Recursive call to exponential search function which will now start at x/2, x/2 +1, x/2 + 2, x/2 + 4, x/2 +8, x/2 + 16....

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````/**
* 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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

it gives an ArrayIndexOutOfBoundsException with input
int [] elements = {0,0,0,0,0,0,1,1};

Comment hidden because of low score. Click to expand.
0

it fails because the list is very small and the distribution to get the next index is expo, so because the list has only 7 elements on the 3rd iteration I'm looking already at the index 8. The pre-condition of the problem says that is a huge list where I don't know the size as that is very large.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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
ZeroToOne zto = new ZeroToOne();

for (int i = 0; i < zero; i++)

for (int i = 0; i < one; i++)

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;
}
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.