Interview Question
Country: United States
Interview Type: In-Person
@Up. First, take a deep breath :)
There are two bugs in your solution:
1. The program doesn't check the left of the array, when arr[mid] == mid. Run your program against [-1, 1, 2, 4]. The program finds arr[1] = 1, then checks arr[2] == 2, and then returns [-1, 1, 2].
2. The program will never check the right of the middle (part larger than arr[mid]). Run your program against [-4, -2, 0, 3, 10]. It will return None, but arr[3] = 3.
1. It does check to the right of the array when arr[mid] == mid when it sets start = mid+1. Yours doesn't.
2. I think the phrasing of the question needs to be better, but I don't think you can do it in log n time without the constraint that the numbers be increasing sorted AND >= 0. Checking the mid in a binary search without the constraint that the array is >= 0 doesn't reveal any information on where in the array all the elements that are equal to the index are.
My solution above finds "the" element that is A[i] =i. If you're trying to find all of the elements that satisfies for all A[i] = i, which I think what you're trying to do, then you can't do it in O(log n), . You might as well just write a single loop and check the elements sequentially, why bother with the middle point?!
By the way, for your 1. bug, I meant the left of the array. So for the array [-1. 1. 2. 4], your program returns [-1, 1, 2], but the solution is [1,2].
I think this can be done in O(log n) complexity. There could be three cases...
Check the first number ... arr[0] > 0 or ==0 or < 0
case 1: arr[0] > 0
answer: none
O(1)
case 2: arr[0] = 0
e.g. arr = [ 0, 1, 2, 3, 5, 6, 7, 8, 9];
Apply binary search to arr[0 to n].
if array[n/2] > n/2, reapply binary search to arr[0 to (n/2 - 1)] until we reach an equality.. and keep track of the n/2 at each step, let it be variable "tracker"..
we will reach the equality at arr[2], and tracker = 4
Now, reapply binary search to arr[n/2 to tracker] because we know that all the elements to its left suffice the condition and will be in the result set.
Continue doing this, till we reach size(arr) = 1
O(logn n)
case 3: arr[0] < 0
This is a bit complex than the above two cases.
Here we have to run binary search twice (on two sides of the array) to check what is the index where positive number starts (let it be 'm'). and then repeat the case 2 with the lower bound 'm' instead of 0.
Agreed, no such solution exists. Just because an algorithm uses binary search doesn't mean it cannot degenerate in the worst case. In the case of this problem, the sorted input sequence above will perform at O(n log(n)) using the binary search method.
I don't think this is a good argument that no O(log N) solution exists. Consider an algorithm that first checks the first & last element. In this case, it would have immediately determined that there are n elements and that since the array is strictly increasing, none of the elements can be equal to its index.
It takes more than coming up with a counter-example for a reasonable algorithm to prove no faster algorithm exists.
But the interviewer was not pleased with my O(n) solution. So I think there must be an O(logn) solution as he consistently emphasized on binary search.
@DashDash, you're actually right. Now I read the question carefully. The question says find the elements (all the elements!) that are equal to their index.
In the worst case, if you're given an array with all the element values already equals to their index position, {0, 1, 2, 3, 4, 5, 6, ...}, then the solution is O(n).
My solution was for finding "the" element, that is A[i] = i.
1. Take middle element and check a[i] = i
2. If First step passed, check a[i+1]==i+1
3. if step two passed check for middle element between i and a.length and do from step1
4. if step two failed, then a[0] to a[i] , then print 0...i
5. If first step failed, check a[i-1]=i-1
6. if step five passed, then print 0... i-1
7. if step five failed check for middle term element between 0 and i-1, repeat from step 1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace OneTake
{
class ValueEqualToIndex
{
public int[] find(int[] array) {
if (array == null || array.Length < 1) return null;
if (array.Length == 1) {
if (array[0] == 0) return array;
else return null;
}
int? found = null;
int low = 0;
int high = array.Length - 1;
int mid = (low + high) / 2;
// Found array[mid] = mid;
while (mid > low && mid < high) {
if (array[mid] >= mid)
{
if (array[mid] == mid) {
found = mid;
break;
}
high = mid;
mid = (low + high) / 2;
}
else {
low = mid;
mid = (low + high) / 2;
}
}
// Iterate from left to right, found the equal case, worst O(n)
Queue<int> stack = new Queue<int>();
if(found.HasValue) {
low = found.Value - 1;
high = found.Value;
bool canLeft = true;
bool canRight = true;
while(canLeft || canRight) {
if(canLeft && low >= 0 &&array[low] == low) {
stack.Enqueue(array[low--]);
}
else {
canLeft = false;
}
if(canRight && high < array.Length && array[high] == high) {
stack.Enqueue(array[high++]);
}
else {
canRight = false;
}
}
}
return stack.ToArray();
}
public void test() {
int[] array = { -1, 0, 1, 2, 4, 5 };
int[] res = find(array);
Console.WriteLine(String.Join(",", res));
}
}
}
My divide & conquer approach:
(1) The method takes the array, starting position, ending position, and a TreeMap
(2) Each entry in the TreeMap (startPos, endPos) represents the start & end positions of a subarray that satisfies the condition
(3) First check whether array[startPos] == startPos && array[endPos] == endPos
(4) If so, that means all elements in this subarray satisfy the condition, so insert entry into TreeMap
(5) Otherwise, check if array[startPos] > startPos or array[endPos] < endPos
(6) If so, that means none of the elements in the subarray[startPos..endPos] can satisfy the condition. For instance, if startPos=0 and endPos=4 and that arr=[2,3,4,5,6], you can see how even if the array elements increase in the slowest manner, it would have still exceeded the endPos before it reaches the endPos.
(7) Otherwise, recursively check the left & right subarrays.
static void findMatching(int[] arr, int startPos, int endPos, TreeMap<Integer, Integer> matching) {
int startValue = arr[startPos];
int endValue = arr[endPos];
if(startValue == startPos && endValue == endPos) {
matching.put(startPos, endPos);
} else if(startValue <= startPos && endValue >= endPos) {
int middlePos = (startPos + endPos)/2;
if(middlePos != endPos)
findMatching(arr, startPos, middlePos, matching);
if(middlePos+1 <= endPos)
findMatching(arr, middlePos+1, endPos, matching);
}
}
There is a O(log n) solution using binary search to eliminate half the candidates at each iteration. Let's say you're looking for A[i] = i, then for any i > 0 A[i] >= A[i-1]+1, because the array is increasingly sorted. Then imagine you've created an array A' such that each element is A[i]-i, then A' is also increasingly sorted. Therefore, you can do a binary search for 0 in A' to find the index such that A[i] = i. By the way, we'll not need to actually create A', just assume that A'[i] = A[i] -i.
Here is the code:
This is code runs in O(log n)
- oOZz June 23, 2013