Yahoo Interview Question for Software Engineer / Developers






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

I think for this question one has to know the range of elements in sorted array.
eg range of elements is ( m to n ). All elements exist in this range are there in array except one. now just do binary search as array is sorted.

- Anonymous September 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

binary search for what :)

Sum of numbers in a range can be calculated using n(n+1)/2 and thus find the missing number by summing the given numbers and calculating the difference.

- Mahesh September 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

adding all the numbers isnt that O(n)?. what is O(logn) solution?

- Rs September 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we can safely assume there is no logN solution for this problem in its current form.

- Mahesh September 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that too. All numbers between m and n except one must be inside the array. Otherwise, lots of numbers aren't in the array.

- S September 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wonder y we cant do a binary search.. :-?
its sorted, we know the range, so we know the middle element, we know what it shud sum up to.. if the calculatedVlaue > anticipatedValue then missing number is within the first half.. and continue ur search.. O(log n)..

now looking for criticism..

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

google Find Missing Term In Arithmetic Progression

- walnutown May 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is the binary search..
Lets assume range is [m,n] i.e. m and n is included in range
int diff = (n-m )/2
if (arr[diff] = m+diff ) then
//missing element is in lower half i.e. between [diff+1,n]
else
//missing element is in upper half i.e. between [m,diff-1]

- Patron September 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain for what number you are checking ..

10-70

and 54 is missing

diff is middle range = 30
arr[30] = 10 + 30 ?? whats the logic of checking this ??

Here it will go to lower half as arr[30] = 40 , and are u comparing i.e == or assigning by =

Please explain ..

According to what i think its really not possible to find a missing number in a list .. Binary search is to find the position and number is present or not when you know the exact number that is given. Also we should have a sorted list

- Raj September 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

** According to what i think its really not possible to find a missing number in a log N time in a list

- Raj September 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is possible. Please see my later comment. And avoid coming to hasty conclusions, the interviewer always look for you "can do" approach and your thinking abilities.

- Hinax September 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume that the range of the numbers are given (Otherwise we cannot differentiate the missing element when it is the first or last element)
We can still do a binary search by comparing the difference between positions and values.
Suppose the array is {0,1,2,4,5,6,7,8,9,10}, 3 is missing.
The first round of binary search will have left = 0, right = 9, mid = 0+(9-0)/2=4
And the element of left pointer is 0, mid pointer is 5
Since 5 - 0 > mid - left = 4, we can know that the missing element is on the left.

int binary_search(int *a, int left, int right) {
	if (left >= right - 1) { //Deal with the edge condition
		if ((left > 0) && (a[left] > a[left - 1] + 1))
			return (a[left] - 1);
		else
			return (a[left] + 1);
	}

	int mid = left + (right - left) / 2;
	if (mid - left < a[mid] - a[left])
		binary_search(a, left, mid);
	else
		binary_search(a, mid, right);
}

int main() {
	int a[10] = {0,1,2,4,5,6,7,8,9,10};
	cout << binary_search(a, 0, 9) << endl;

}

- jimmyzzxhlh September 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would work only if the numbers are consecutive

- praneethreddy.bokka March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution will return '0' all the time...

The problem with is as follows:
if (mid - left < a[mid] - a[left])
binary_search(a, left, mid); <<<< You are not returning the value from stack
else
binary_search(a, mid, right); <<<< You are not returning the value from stack

The solution is as follows:
if (mid - left < a[mid] - a[left])
return (binary_search(a, left, mid));
else
return (binary_search(a, mid, right));

- dronzer709 April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in o(logn) time. Simple binary search will do.
For each iteration, we can compare low,mid and high. if(mid-low) == (array[mid]-array[low]) it means all elements are present in first half(low to mid) and the missing element is present in the later half(mid to high). We can continue the binary search(recursive call) on the later half(mid to high).

This will take o(logn) as it is binary in approach.

- Hinax September 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cant you just check if current array[index] = index then its fine up to now...

because if array is sorted and continuous and starting from 0 then for every element array[index] = index.

if its not starting from 0 but x then array[index] = index+x. It will be sorted and continuous...always...

- Harit December 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can deduct from the total length
public static int Repeated_Arr(int[] arr)
{
int len = arr.Length - 1;
int sum = (len * (len + 1)) / 2;
for (int i = 0; i <= len; i++)
{
sum -= arr[i];
}
return -1 * sum;
}

- Biruk Solomon November 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it assumed that all elements in this sorted array are unique?

- Anonymous March 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To find the missing element in O(log n) you need to use binary search idea

Assumption : the array sorted in ascending order

public int findMissingElement ( int [] a ){


	if( a.lenght<2)
	return -1

	int start =0;
	int end =a.length;
	int mid =(start +end)>>1;
	
	while(start<end){

		if ( a[mid] - a[start] !=  mid -start ){
			if( mid - start == 1 && a[mid]-a[start]>1)
				return a[mid]-1;
			end =mid;
			mid =(start+end)>>1;
		}
		else if ( a[end] - a[mid] !=  end -mid ){
		if( end - mid == 1 &&  a[end] - a[mid] >1)
			return a[mid] +1;
			
			start =mid;
			mid =(start+end)>>1;
		}
		// Everything ok
		return -1;

- Maher Rezeq July 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int findMissingElement(int start , int end , int a []  )
{
	if (end < start)
		return -1; // not found means Ok
	else {
			int mid = (start + end)>>1;

			if( mid - start ==1 && a[mid] - a[start] >1)
				reutn a[mid]-1;
			if ( end - mid == 1 && a[end] - a[mid] >1)
				return a[mid]+1;

			if( a[mid] - a[start] != mid - start ){
				return findMissingElement (start ,mid,a);
			}
			else ( a[end] - a[mid] != end - mid ){
				return findMissingElement (mid ,end,a);
			}

		}
}

- Anonymous July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is a bit ambiguous:
1. Are the elements (val) continuously inc. by 1 meaning any element at index x is 1 less than element x + 1 ?
2. is the first element starting at 0 ?

So, I will try to provide my answer on the assumption that Yes for question (1) and (2) above.

Assume we have an array of 10 elements (or N elements of a general case). And, assume element 3 is missing (or any x where x >= 0 and x <= N-1;

Array index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array with missing: [0, 1, 2, 4, 5, 6, 7, 8, 9] // 3 is missing from the sorted array.

Algorithm:
1. If there are only 2 element, then the element which the index != Array[index] is the one missing.
2. else
a. find the mid point.
b. compare the index of array with the Array[index]
if (index < Array[index]) then the missing one is in the first (left) half of the array.
else the missing one is in the second (right) half of the array.



int missing(int A[], int begin, int end)
{
int mid = (begin + end)/2;

if (begin +1 == end)
return ((A[begin] != begin)? begin:end;

if (mid < A[mid])
return missing(A, begin, mid);
else
return missing(A, mid, end);
}

You can see that at each iteration, we are eliminating half of the array. Thus, it is an O(logn).

Any constructive comment ?

- Thanh Nguyen December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ok this is if the numbers are in the increasing format with one value. what if the numbers are sorted in arithmetic progression but not the index is not equal to the value of that index.
for ex, what if we have this array{1,4,7,10,16,19,22,...} the missing number is 13. Does the binary search is working with this? I think it will work just withe special sorted array but not to find general missing value in the sorted array. In this case can we use binary search in o(long) time to find the answer of it?
Thanx

- nawky June 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved in O(logn) using binary search .

int find_bs(int a[],int l,int n)
{
	if(l==n)
	{
		if(a[l]-a[l-1]>1)
			return a[l]-1;
		else
			return a[l]+1;
	}
	int mid=(n+l)/2;
	if(a[mid]-a[0]==mid)
	{
		find_bs(a,mid+1,n);
	}		
	else
	{
		find_bs(a,l,mid-1);
	}
}

int main()
{
	int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
	cout<<find_bs(arr,0,11);
	return 0;

}

- Mayank Gupta August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_bs(int a[],int l,int n)
{
if(l==n)
{
if(a[l]-a[l-1]>1)
return a[l]-1;
else
return a[l]+1;
}
int mid=(n+l)/2;
if(a[mid]-a[0]==mid)
{
find_bs(a,mid+1,n);
}
else
{
find_bs(a,l,mid-1);
}
}

int main()
{
int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
cout<<find_bs(arr,0,11);
return 0;
}

- Mayank Gupta August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_bs(int a[],int l,int n)
{
	if(l==n)
	{
		if(a[l]-a[l-1]>1)
			return a[l]-1;
		else
			return a[l]+1;
	}
	int mid=(n+l)/2;
	if(a[mid]-a[0]==mid)
	{
		find_bs(a,mid+1,n);
	}		
	else
	{
		find_bs(a,l,mid-1);
	}
}

int main()
{
	int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
	cout<<find_bs(arr,0,11);
	return 0;

}

- Mayank Gupta August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;


int find_bs(int a[],int l,int n)
{
	if(l==n)
	{
		if(a[l]-a[l-1]>1)
			return a[l]-1;
		else
			return a[l]+1;
	}
	int mid=(n+l)/2;
	if(a[mid]-a[0]==mid)
	{
		find_bs(a,mid+1,n);
	}		
	else
	{
		find_bs(a,l,mid-1);
	}
}

int main()
{
	int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
	cout<<find_bs(arr,0,11);
	return 0;
}

- Mayank Gupta August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static int MissingNumber(int [] a, int n)
{
int low = 0, mid = 0, high = n-1;
while (low <= high)
{
mid = (low+high)/2;
if( mid == 0 || a[mid] - a[mid - 1] > 1 ) // order of logic must be preserved as shown.
return a[mid] - 1;

if (a[mid] - mid > 1)
high = mid - 1;
else //(a[mid] - mid == 1)
low = mid + 1;
}

return 0;
}

- Taher Benisa June 13, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More