Interview Question


Country: United States




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

Again binary search does the job
Code

public static int findIndex(int[] arr) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                return m;
            }
            if (arr[m] > m) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

- thelineofcode February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If we plot (i, arr[i]) on a graph and assuming that these points are collinear, then this solution works only if the slope of this line is >1. It does not consider the case when the slope of this line is positive but less than 1. The fact that the array is sorted in ascending order just says that the slope is positive .. it could be either >1 or < 1.

I think the code needs to be modified as follows:

public static int findIndex(int[] arr) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (arr[m] == m) {
                return m;
            }
            if  ( ((arr[r] > r) && (arr[m] > m)) || 
		((arr[r] < r) && (arr[m] < m)) )  {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

- whatevva' February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Didn't get how binary search will return the index?

- Ricky February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 votes

@Ricky consider three cases:
1) a[m] == m - this is what we want to get if this condition is met the index is returned.
2) arr[m] > m e.g. {0,1,5,6,7} - a[3] = 5. Since we know that array is sorted and contains distinct elements we can skip the right side of the array because all elements >=3 are incorrect.
3) arr[m] < m e.g. {-2,-1,0,1,2} - a[3] = 0. We can skip the left side of the array because all elements <= 3 are incorrect.
Just like in case of binary search.

- thelineofcode February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

github.com/techpanja/interviewproblems/blob/master/src/arrays/indexequaltonumbersortedarray/IndexEqualToNumberSortedArray.java

public class IndexEqualToNumberSortedArray {

    private IndexEqualToNumberSortedArray() {

    }

    /*
    * Binary search. O(log N) solution.
    * */
    public static int indexEqualToNumberSortedArray(int[] inputArray) {
        if (inputArray.length == 0) {
            return -1;
        }
        int low = 0;
        int high = inputArray.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (inputArray[mid] == mid) {
                return mid;
            } else if (inputArray[mid] > mid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(indexEqualToNumberSortedArray(new int[] {1, 2, 4, 5, 6, 7}));
        System.out.println(indexEqualToNumberSortedArray(new int[] {0, 3, 4, 5, 6, 7}));
        System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 2, 4, 7}));
        System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 2, 3, 5}));
        System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 3, 5, 6}));
    }
}

- techpanja February 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindIndex(const int const* input, int len)
{
if (input == NULL || len == NULL)
return -1;

int start = 0;
int end = len - 1;

while (start <= end)
{
int pos = (start + end) / 2;

if (input[pos] < 0 || input[pos] < pos)
{
start = pos + 1;
}
else if (input[pos] > pos)
{
end = pos - 1;
}
else
{
return pos;
}
}

return -1;
}

- Swati February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(1)the array is in ascending order
>>> arr[i] > arr[i-1]
<=> arr[i] - arr[i-1] > 0
(2)the elements are integers
>>> arr[i] - arr[i-1] >= 1
<=> arr[i] - arr[i-1] >= i - (i-1)
<=> arr[i] - i >= arr[i-1] - (i-1)
(3)the array of arr[k]-k is in non-decesending order, so binary search works

- uuuouou February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh. +1.

- Subbu. February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Notice that a[i+1] - 1 >= a[i] IMPLIES a[i+1] - (i+1) >= a[i] - i. (Elements are distinct sorted)

Thus the "vitrual array" a[i] - i, is sorted, and you are basically looking for a 0.

So, do a binary search and look for 0, with the compare function which compares a[i] - i instead of a[i].

- Subbu. February 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The requirement of distinct elements is absolutely need for binary search to work.

- Subbu. February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*needed.

- Anonymous February 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findIndex(int arr[SIZE])
{
	int i;
	
	for( i=0;i<SIZE;i++)
	{
		if(arr[i]==i)
		{
			cout << "\n INDEX is"<<i;
			return i;
		}
	}
	
	return -1;
}

- Anonymous February 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the array index starts from 0, initialize always arr[0] to 0 so that you dont have to bother about index incrementation.

#include <iostream>
# include <string>

using namespace std;
int ser(int* arr, int low, int high)
{

 if(low > high)
  return -1;

 int mid = (low + high )/2;

 if(arr[mid] == mid)
  return mid;

 return arr[mid] > mid ? ser(arr, low, mid -1) :  ser(arr, mid+1, high);
}
 
int main()
{

int arr[11]={0,1,2,3,6,8,10,12,14,15,20};

cout<<ser(arr,1,11)<<endl;
return 0;
}

- kirankumarcelestial February 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int funct1(int[] a) {
for(int i=0;i<a.length-1;i++){
if(a[i]>i) {
return -1;
}
else if(a[i]==i) {
return i;
}
}
return -1;
}

- Ritesh Jha February 05, 2014 | 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