Interview Question
Software Engineer / DevelopersA better solution. The complexity of best case is O(1); worst case is O(n).
boolean isArray(int[] A, int num)
{
int len = A.len;
int m = len - 1 - abs( A[0] - A[len-1]);
if (A[0]<=num && num<=A[len-1])
return true;
else if (num>A[0]+m || num<A[0]-m)
return false;
else
// go through each element
}
The number is in array'A' if:
1. 0 <= num-a[0] < n when a[0] < a[n-1]...consecutive ascending numbers
2. 0 <= -(num-a[0]) < n when a[0] > a[n-1]...consecutive descending numbers
sorry...ignore the above solution...didn't consider the fact that next element might be +/- 1...
import java.util.Random;
public class FindInteger {
public static int findInteger(int k, int[] a, int start, int end) {
if (start < end) {
if (a[start] <= a[end]) {
// v is the numbers of decreases
int minus = (end - start - (a[end] - a[start])) / 2;
int plus = minus + (a[end] - a[start]);
if (k >= Math.max(a[start] - minus, a[end] - plus)) {
if (k <= Math.min(a[end] + minus, a[start] + plus)) {
// integer could validated
if (k == a[start])
return start;
else if (k == a[end])
return end;
else {
int t = findInteger(k, a, start, (start + end) / 2);
return t == -1 ? findInteger(k, a,
(start + end) / 2 + 1, end) : t;
}
} else {
return -1;
}
} else {
return -1;
}
} else {
int plus = (end - start - (a[start] - a[end])) / 2;
int minus = plus + (a[start] - a[end]);
if (k >= Math.max(a[end] - plus, a[start] - minus)) {
if (k <= Math.min(a[start] + plus, a[end] + minus)) {
if (k == a[start]) {
return start;
} else if (k == a[end]) {
return end;
} else {
int t = findInteger(k, a, start, (start + end) / 2);
return t == -1 ? findInteger(k, a,
(start + end) / 2 + 1, end) : t;
}
} else {
return -1;
}
} else {
return -1;
}
}
} else {
return a[start] == k ? start : -1;
}
}
public static void main(String[] args) {
Random random = new Random();
int k = 50;
int[] a = new int[10000];
a[0] = 5;
for (int i = 1; i < a.length; i++) {
int t = Math.abs(random.nextInt()) % 3;
if (t == 2) {
a[i] = a[i - 1] - 1;
} else {
a[i] = a[i - 1] + 1;
}
if (a[i] == k) {
System.out.println("Insert at #" + i);
}
}
int i = findInteger(k, a, 0, a.length - 1);
System.out.println("Found at #" + i);
}
}
- supersonglj August 30, 2011