## Google Interview Question for Interns

Country: United States
Interview Type: Phone Interview

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

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

``````def closest_to_K(seq, K, C):
lo, hi = 0, len(seq) - 1
value = 0
while lo < hi:
mid = (lo  + hi) / 2
if seq[mid] == K:
value = mid
break
elif seq[mid] > K:
hi = mid - 1
else:
lo = mid + 1

if lo >= hi: value = lo # In case K is not in the array
res = []
lo, hi = value, value + 1
if seq[value] == K:
res.append(K)
lo, hi = value - 1, value + 1
while len(res) != C:
if K - seq[lo] <= seq[hi] - K:
res.insert(0, seq[lo])
lo -= 1
else:
res.append(seq[hi])
hi += 1

return res[0]``````

``````In: closest_to_K([1,2,5,8,9,13], 8, 4)
Out: 5

In: closest_to_K([1,2,5,8,9,13], 7, 4)
Out: 2``````

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

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

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

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

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

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

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

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

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

Solution: O(logn) + O(C)

-> binary search over n to find closest element to K
-> L=closest, R=closest
-> while (R-L+1 < C):
-> if (| array[L-1] - K |<=| array[R+1]) - K |:
-> L=L-1
-> else:
-> R=R+1
->return L

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

the follow-up will be how to optimize the linear time for selecting C element (if C is big for example) ... you can get to O(lg(n)+lg(C))

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

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

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

``````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])``````

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 3 vote

- Linear search finding begin and end index for values who lies within [K-C, K+C]
- Since data is sorted we can use binary search to find begin/end index of values that lies within [K-C, K+C]

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.