Yahoo Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I'm not sure that your solution is O(log n) in the worst case, and it is not guaranteed to return the right index. The example case would be {1, 99, $, $, $, $, $, $, .....}, where n = 2 and the first n cells contains integers in sorted order.
it's O(log n) only. what is not guaranteed in your example?
{1, 99, $, $, $, $, $, $, .....}
1. k = 1 then in first if condition it finds
2. k = 99 then in first if condition it finds
3. 1<k>99 then in first if condition it returns -1 as number not found
4. k > 99 here first if condition fails so in else start becomes 2, arr[2] = '$' so it returns -1 as number not found
Ah, I see where you're going, I misinterpreted the number ranges. Clever solution, you got my vote.
The following is a solution in Java. Assumes that sorted integers are unique. We start by looking at position k since we're guaranteed that the value won't be in a position greater than k. Once we've checked k, we can then do a binary search on the range 0..k-1. This solution is O(log k).
public static int findPosition(String[] input, int k) {
if (input == null || input.length == 0 || input[0] == "$")
return -1;
if (input[k] == Integer.toString(k))
return k;
return binarySearch(input, k, 0, k-1);
}
public static int binarySearch(String[] input, int k, int start, int end) {
if (end < start)
return -1;
int mid = (start + end) / 2;
// Convert string array value to int, if possible
int midValue = -1;
if (input[mid] != "$")
midValue = Integer.parseInt(input[mid]);
// Check mid point
if (midValue == k)
return mid;
// Search low if mid value is greater than k
// or if it is "$"
if (midValue > k || input[mid] == "$")
return binarySearch(input, k, start, mid - 1);
// If mid point isn't "$", then search the upper range
else if (input[mid] != "$")
return binarySearch(input, k, mid + 1, end);
return -1;
}
Since the target is an infinite array, we are guaranteed not to reach its end (presumably)! We can start by searching every 2^k, k=0,1,... (i.e., arr[(1<<k)-1]) location (hence, o(lg n)) until we
1.either hit the value we are looking for so return the (1<<K)-1 as its location
2. we hit a value greater than the value we are looking for OR a '$'
If the second case occurs, then we know our value should be somewhere between indices 0 and (1<<k)-1. Do a binary search within this limit until you either find the value or figure out no such value exists.
bool searchInfiniteArray(int[] a)
{
bool lastBlock = false;
for (int k=0; ; k++);
{
int lo(1 << k - 1), hi(1 << (k+1) - 1), x;
while (lo <= hi)
{
x = lo + (hi-lo)/2;
try {
if (a[x] == target) return x;
else if (a[x] > target) return hi = x-1;
else lo = x+1;
}
catch(Exception e) { hi = x-1; lastBlock = true; }
}
if (lastBlock) return false;
}
}
- algos July 27, 2013