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

Edit: Added some examples

- Fernando August 04, 2017 | Flag Reply
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 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);
}

- anonymous August 04, 2017 | Flag Reply
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;
}

- a.asudeh August 04, 2017 | Flag Reply
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;
	}

- tiandiao123 August 05, 2017 | Flag Reply
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;
            }
        }
    }
}

- learnsomething247 August 05, 2017 | Flag Reply
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

- gumanji August 08, 2017 | Flag Reply
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))

- Chris August 08, 2017 | Flag Reply
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;
}

- Alex September 01, 2017 | Flag Reply
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])

- sabihabarlaskar90 May 13, 2018 | Flag Reply
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));

- koustav.adorable August 04, 2017 | Flag Reply
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]

- tnutty2k8 August 04, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More