Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
An suboptimal/optimal solution in O((log(n))^2) is:
1. Find position of K by using binary search in log(n) time
2. Do a nested binary search inside binary search to find L.
Binary search for radius (low_radius, high_radius) around key K:
- Binary search for number of elements on the left of K
- Binary search for number of elements on the right of K
- Total = number elements from left + number of elements from right + 1
If total >= C we binary search on (low_radius, mid_radius), otherwise we binary search on (mid_radius+1, high_radius).
Full code:
int bs(int A[],int low,int high,int value){
if(low==high)
return low;
int mid = (low+high)/2;
if(A[mid]>=value)
return bs(A,low,mid,value);
return bs(A,mid+1,high,value);
}
int bsR(int A[],int lowR,int highR,int C,int K,int index){
if(lowR == highR){
if(index-1<0)
return index;
int left = C-lowR;
int leftIndex = bs(A,0,index-1,left);
if(A[leftIndex]>=left)
return leftIndex;
return index;
}
int midR = (lowR+highR)/2;
int right = C + midR;
int left = C - midR;
int nLeft = 0;
if(index-1>=0){
int leftIndex = bs(A,0,index-1,left);
if(A[leftIndex]>=left)
nLeft = index-leftIndex;
}
int nRight = 0;
if(index+1<=n-1){
int rightIndex = bs(A,index+1,n-1,right+1);
if(A[rightIndex]<=right){
nRight = rightIndex - index;
}
else{
if(rightIndex>index+1){
nRight = rightIndex - 1 - index;
}
}
}
int n = 1 + nLeft + nRight;
if(n>=K)
return bsR(A,lowR,midR,C,K,index);
return bsR(A,midR+1,highR,C,K,index);
}
int kClosest(int A[],int n,int C,int K){
int index = bs(A,0,n-1,C);
int r = max(A[n-1]-C,C-A[0]);
return bsR(A,0,r,C,K,index);
}
int Leftindex(vector<int> A, int K, int C)
{
// 1. apply the b-search to find the index of closest point to K
int b=0, e=A.size()-1, mid;
while(b<=e)
{
mid = (b+e)/2;
if(K==A[mid])
break;
if(K>A[mid]) b = mid+1;
else e = mid-1;
}
// 2. do the expansion
b = e = mid;
while(e-b<C-1)
{
if(K-A[b-1]>A[e+1]-K) e++;
else b--;
}
return b;
}
public static int SearchRange(int[] array,int key,int K){
//List<Integer> list = new ArrayList<>();
if(K>=array.length){
return 0;
}
int index = Arrays.binarySearch(array,key);
if(index<0){
index = -(index+1);
}
int left=index-1;
int right=index;
int count=0;
while(count<K){
Integer left_value=left>=0?array[left]:null;
Integer right_value=right<array.length?array[right]:null;
if(left_value==null){
right++;
}else if(right_value==null){
left--;
}else if(Math.abs(key-left_value)<Math.abs(key-right_value)){
left--;
}else{
right++;
}
count++;
}
return left+1;
}
public class Range {
public static void main(String... a) {
int[] arr = {1, 2, 5, 8, 9, 13};
// int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int ele = 8;
int rangeSize = 4;
findRange(arr, ele, rangeSize);
}
private static void findRange(int[] arr, int ele, int rangeSize) {
int mid = bsearch(arr, ele);
expand(arr, mid, rangeSize);
}
private static int bsearch(int[] arr, int ele) {
int low = 0;
int high = arr.length;
int mid = -1;
while (low <= high) {
mid = (high - low) / 2;
if (arr[mid] == ele) {
break;
} else if (arr[mid] < ele) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return mid;
}
private static void expand(int[] arr, int loc, int rangeSize) {
int end = loc + 1;
int start = loc - 1;
System.out.print(arr[loc] + " ");
for (int i = 0; i < rangeSize - 1; ++i) {
if (arr[loc] - arr[start] > arr[end] - arr[loc]) {
System.out.print(arr[end] + " ");
++end;
} else {
System.out.print(arr[start] + " ");
--start;
}
}
}
}
int FindBlock(vector<int> const &a, int n, int block_size)
{
int result = -1;
if (block_size > 0 &&
a.size() >= block_size)
{
int n_idx = -1;
int l = 0;
int r = a.size() - 1;
while (l <= r &&
n_idx == -1)
{
int mid = (l + r) / 2;
if (a[mid] == n) {
n_idx = mid;
} else if (a[mid] > n) {
r = (r == mid) ? r - 1 : mid;
} else {
l = (l == mid) ? l + 1 : mid;
}
}
if (n_idx != -1) {
int l = n_idx;
int r = n_idx;
while (r - l + 1 < block_size) {
if (l == 0) {
++r;
} else if (r == a.size() - 1) {
--l;
} else {
if (n - a[l - 1] < a[r + 1] - n) {
--l;
} else {
++r;
}
}
}
result = l;
}
}
return result;
}
import operator
def closest_to_k(A,k,c):
d = {}
for i in range(len(A)):
d[i] = abs(A[i]-k)
sorted_x = sorted(d.items(), key=operator.itemgetter(1))
count = 1
min_ind = sorted_x[1][0]
while (count < c):
if(sorted_x[count][0] < min_ind):
min_ind = sorted_x[count][0]
count+=1
return (min_ind,A[min_ind:min_ind+c])
If C (n in my code) is small (say, C <= 32), just do a linear search. Otherwise, do a binary search:
inline constexpr std::ptrdiff_t n_threshold = 32;
template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements1(
Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
if (first == last || n <= 0)
return {pos, pos};
auto left = pos;
auto right = pos + 1;
while (--n > 0 && left != first && right != last)
if (*right - *pos < *pos - *(left - 1))
++right;
else
--left;
if (left == first)
right += std::min(n, last - right);
if (right == last)
left -= std::min(n, left - first);
return {left, right};
}
template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements2(
Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
if (first == last || n <= 0)
return {pos, pos};
if (last - first <= n)
return {first, last};
auto left = first + std::max(std::ptrdiff_t{0}, (pos - first) - (n - 1));
auto right = pos - std::max(std::ptrdiff_t{0}, n - (last - pos));
while (left != right)
if (const auto mid = left + (right - left) / 2; *(mid + n) - *pos < *pos - *mid)
left = mid + 1;
else
right = mid;
return {left, left + n};
}
template<class Random_access_it, class T>
std::pair<Random_access_it, Random_access_it> closest_elements(
Random_access_it first, Random_access_it last, const T& value, std::ptrdiff_t n) {
if (n <= n_threshold) {
const auto pos = std::find(first, last, value);
return closest_elements1(first, last, pos, n);
} else {
const auto pos = std::lower_bound(first, last, value);
return closest_elements2(first, last, pos, n);
}
}
def nearestCElem2K(list, K, C):
pos = binarySearch(list, K);
op = []
opIndex=999999;
i = pos - 1;
j = pos;
count = 0;
while count < C and i >= 0 and j < len(list):
if abs(list[i] - K) < abs(list[j] - K):
op.append(list[i]);
opIndex=min(i,opIndex);
i = i - 1;
else:
op.append(list[j]);
j = j + 1;
count = count + 1;
while count < C and i >= 0:
op.append(list[i]);
opIndex=min(i,opIndex);
i = i - 1;
count = count + 1;
while count < C and j < len(list):
op.append(list[j]);
j = j + 1;
count = count + 1;
print(op);
return list[opIndex];
def binarySearch(list, K):
st = 0;
end = len(list) - 1;
while st < end:
mid = st + ((end - st) / 2);
if list[mid] == K:
return mid;
if list[mid] < K:
st = mid + 1;
else:
end = mid - 1;
return st;
print(nearestCElem2K([1,2,5,8,9,13],8,4));
Perform a binary search of K on the array and from that iterate over until we get the all the C closest elements. The cost is log(n) + C. By the way the solution for the example should be 5 isn't?
Solution in Python
Edit: Added some examples
- Fernando August 04, 2017