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

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

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

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

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

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

@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.

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

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

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

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

oh. +1.

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].

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

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

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

*needed.

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

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

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

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.