Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

The best solution is logarithmic (the trivial one is linear).

My solution:
1. First I'd like to generalize the task a bit: Find all the numbers that occur more than n/k times (in the example, more than n/4 times)
2. Let's split the array on k*2 segments (in the example on 4*2 = 8 segments)
3. Compare every segment's start and end values. If they are equal, it means that we have a potential candidate (that occurs more than n/k times).
3.1 Now we need to find the beginning of the candidate. To do that take the previous segment and do a binary search in it.
3.2 Once we find a beginning of our candidate, time to check if its length is more than n/k. Just add a length (n/k) to the start position and check the value at the end. If the values are equal, then we have a solution and can add it to the result set.

Below is the sketch of my solution in Java. Its complexity is the following:
2k * log(n/2k) = k*log(n) - k*log(k), if we assume that k is relatively small or constant, the complexity becomes log(n).

public Set<Integer> findNumbers(int[] arr, double k) {
        Set<Integer> result = new HashSet<>();
        double size = arr.length / k;
        if (size <= 1) {
            return result;
        }
        int step = (int) size / 2;
        step = step < 1 ? 1 : step;
        for (int i = 0; i < arr.length - step; i += step) {
            if (arr[i] == arr[i + step]) {
                int start = binarySearch(i - step, i, arr);
                int end = start + (int) size;
                if (end < arr.length && arr[end] == arr[i]) {
                    result.add(arr[i]);
                }
            }
        }
        return result;
    }

    private int binarySearch(int start, int end, int[] arr) {
        if (start < 0) {
            return 0;
        }
        int target = arr[end];
        while (start < end) {
            int mid = (start + end) / 2;
            if (arr[mid] == target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

- passenger March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Trivial solution in linear time.
Optimal solution - since the array is sorted, find the numbers that occur at index n/4, 2n/4, 3n/4 and binary search for the left and right boundaries of the numbers. if rightBound - leftBound > n/4 then the number shows up more than n/4 times.

public void findNums(int[] array) {
        if(array.length == 0) return;
        int[] factors = new int[] {1, 2, 3}; //search for the left and right bound on the numbers that show up at index n/4, n/2 and 3n/4;
        int N = array.length;
        int number = array[0] - 1;

        for(int factor: factors) {
            int current = array[N * factor / 4];
            if(number == current) continue;
            int leftBound = binarySearch(array, N * (factor - 1) / 4, N * factor / 4, current, -1);
            int rightBound = binarySearch(array, N * factor / 4, N - 1, current, 1);
            if(rightBound - leftBound >= N / 4) {
                number = current;
                System.out.print(current + "  ");  
            }
        }


    }

    int binarySearch(int[] array, int start, int end, int num, int direction) {
        if(start > end) {
            return -1;
        }
        while(start <= end) {
            int mid = (start + end) / 2;
            if(array[mid] == num) {
                if(mid + direction < 0 || mid + direction > end) {
                    return mid;
                }
                if(direction < 0) {
                    if(array[mid - 1] != num) {
                        return mid;
                    }
                    end = mid - 1;
                } else {
                    if (array[mid + 1] != num) {
                        return mid;
                    }
                    start = mid + 1;
                }
            } else {
                if(direction < 0) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

- aonecoding March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

if linear is best conceivable run-time, why not keep it simple?

def findNums(array):
    if len(array) <= 1: return
    n = 0
    for i in range(1, len(array)):
        if array[i] == array[i-1]: n += 1
        else: n = 1
        if n == 1 + len(array) // 4: print(array[i])

- ChrisK March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#python

a=[1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,]

count = 1

for i in range(1, len(a)):
    if(a[i] == a[i-1]):
        count += 1
    elif(count > (len(a) // 4)):
        print(a[i-1])
        count = 1
    else:        
        count = 1

- Nagashree March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will go with Chris, any day.
Just minimising more in ZoomBA - not using the sorted property:

println( select ( mset( array ) ) ) :: { $.value > size(array)/4 } )

- NoOne March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 4, 4 };
var n = list.Count / 4;
var moreThanGivenOccurance = list.GroupBy(x => x).Where(x => x.Count() > n).Select(x => x.Key);

OUTPUT:
4

var list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9};
var n = list.Count / 4;
var moreThanGivenOccurance = list.GroupBy(x => x).Where(x => x.Count() > n).Select(x => x.Key);

OUTPUT:
None

- Gunjan March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9, 4, 4 };
var n = list.Count / 4;
var moreThanGivenOccurance = list.GroupBy(x => x).Where(x => x.Count() > n).Select(x => x.Key);

OUTPUT:
4

var list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9};
var n = list.Count / 4;
var moreThanGivenOccurance = list.GroupBy(x => x).Where(x => x.Count() > n).Select(x => x.Key);

OUTPUT:
None

- gunjan.prmr March 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

# Python
cache = dict()
for x in arr:
	if x not in cache:
		cache[x] = 1
	else:
		cache[x] += 1
		if cache[x] > n/4:
			return cache[x]
return -1

- Jimmy March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One one of the simple approach I could think of is

def main(args: Array[String]): Unit = {
    val length = intSeq.length
    val n = length / 4
    var counter = 0
    val memory = scala.collection.mutable.HashSet[Int]()

    while (counter < length - n + 1) {
      val current = intSeq(counter)
      if (current == intSeq(counter + n - 1)) {
        if (!memory.contains(current)) {
          println(current)
          memory.add(current)
        } else counter = counter + 1
        counter = counter + n - 1
      } else counter = counter + 1
    }
  }

- Antriksh March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main(){

int arr[] = {11,12,13,13,13,13,14,17,17,19,19};
int m=0, k=0, i=0;

int n = sizeof(arr)/sizeof(arr[0]);

int p = n;
while(n-1!=0){

if(m==(p/4)){
k++;
m=0;
}
if(arr[i] == arr[i+1]){
m++;
}
i++;
n--;
}

printf("Val is %d\n", k);
return 1;
}

Idea is to do it in single traverse. I take two indexs, m and k. K gives me the number of elements which has occurence of n/4 and m increments every time there is a repetition. For instance, 13, 13.. so when the repetition goes n/4 times I increment k.

- Anonymous March 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In an array of size n, the maximum number of elements that can be greater than n/4 is 4.
So it does not make sense to iterate through all elements of the array especially if n is large. The idea is to check if i and (i+n/4)th element are the same. If they are same increment by n/4, else by 1. Below is an implementation of the same

public class algorithm1 {
	
	public static void main(String args[]){
		int a[]=new int[15];
		int b[]=new int[4];
		int j=0;
		a[0]=1;
		a[1]=1;
		a[2]=1;
		a[3]=1;
		a[4]=1;
		a[5]=1;
		a[6]=3;
		a[7]=7;
		a[8]=11;
		a[9]=12;
		a[10]=19;
		a[11]=101;
		a[12]=101;
		a[13]=101;
		a[14]=101;
		
	    for (int i=0;i<=a.length;i++) {
	    	
	    	if (i+(a.length/4) >= a.length) {
	    		break;
	    	}
	    	
	    	if ( a[i] == a[i+(a.length/4)]) {
	    		i=i+(a.length/4);
	    		if (a[i] != b[j]) {
		    		b[j] = a[i];
		    		System.out.println(b[j]);
	    		}
	    	}
	    }
	}

}

- Joyan March 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <algorithm>

int SearchEnd(const std::vector<int>& arr, int start, int end, int val, bool bLow)
{
int edge = bLow ? 0 : (int)arr.size() -1;
int edgeStep = bLow ? - 1 : 1;
int& vLow = bLow ? start : end;
int& vHigh = bLow ? end : start;

while (start < end - 1 )
{
int mid = (start + end)/2;
if (arr[mid] == val)
{
if (!mid || arr[mid-1] != val)
return mid;
else
vHigh = mid;
}
else
vLow = mid;
}
return start;
}

std::vector<int> FindN4(const std::vector<int>& arr, int div)
{
std::vector<int> result;

int sz = arr.size()/div;
for (int i = sz-1; i < (int)arr.size(); i += sz)
{
int start = SearchEnd(arr, i - sz + 1, i + 1, arr[i], true);
int end = SearchEnd(arr, i, std::min(i + sz, (int)arr.size()), arr[i], false);
if ((end - start + 1 >= sz) && (!result.size() || (result.back() != arr[i])))
result.push_back(arr[i]);
}
return result;
}

- tjcbs2 March 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <vector>
#include <algorithm>

int SearchEnd(const std::vector<int>& arr, int start, int end, int val, bool bLow)
{
   int edge = bLow ? 0 : (int)arr.size() -1;
   int edgeStep = bLow ? - 1 : 1;
   int& vLow = bLow ? start : end;
   int& vHigh = bLow ? end : start;

   while (start < end - 1 )
   {
      int mid = (start + end)/2;
      if (arr[mid] == val)
      {
         if (!mid || arr[mid-1] != val)
            return mid;
         else 
            vHigh = mid;
      }
      else 
         vLow = mid;
   }
   return start;
}

std::vector<int> FindN4(const std::vector<int>& arr, int div)
{
   std::vector<int> result;

   int sz = arr.size()/div;
   for (int i = sz-1; i < (int)arr.size(); i += sz)
   {
      int start = SearchEnd(arr, i - sz + 1, i + 1, arr[i], true);
      int end = SearchEnd(arr, i, std::min(i + sz, (int)arr.size()), arr[i], false);
      if ((end - start + 1 >= sz) && (!result.size() || (result.back() != arr[i])))
          result.push_back(arr[i]);
   }
   return result;
}

- tjcbs2 March 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Best case: n/4
Worst case: n

public class OccurredNumFinder {
  
  // call this method by providing the sortedArr with desired size to consider occurred.
  public List<Integer> findOccurredNum(int[] intArr, int size) {
    List<Integer> numList = new ArrayList<Integer>();
    findOccurredNum(intArr, 0, (0 + size - 1), size, numList);
    return numList;
  }
  
  protected void findOccurredNum(int[] intArr, int startIndex, int endIndex, int size, List<Integer> numList) {
    if (startIndex > intArr.length - size) {
      return;
    }
    int startNum = intArr[startIndex];
    if (intArr[startIndex] == intArr[endIndex]) {
      numList.add(intArr[startIndex]);
      startIndex = endIndex + 1;
    }
    while (intArr[startIndex] == startNum) {
      startIndex++;
    }
    endIndex = startIndex + size - 1;
    findOccurredNum(intArr, startIndex, size);
  }
  
}

- donotask March 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

best case: n/4
worst case: n

public class OccurredNumFinder {
  
  public List<Integer> findOccurredNum(int[] intArr, int size) {
    List<Integer> numList = new ArrayList<Integer>();
    findOccurredNum(intArr, 0, (0 + size - 1), size, numList);
    return numList;
  }
  
  protected void findOccurredNum(int[] intArr, int startIndex, int endIndex, int size, List<Integer> numList) {
    if (startIndex > intArr.length - size) {
      return;
    }
    int startNum = intArr[startIndex];
    if (intArr[startIndex] == intArr[endIndex]) {
      numList.add(intArr[startIndex]);
      startIndex = endIndex + 1;
    }
    while (intArr[startIndex] == startNum) {
      startIndex++;
    }
    endIndex = startIndex + size - 1;
    findOccurredNum(intArr, startIndex, size);
  }
  
}

- donotask March 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a = [1,2,3,4,5,6,7,8,9,0,6,6,6].sorted()
let limit = a.count/4
var n4counter = 0
var lastNumber = Int.max
for i in 0..<a.count {
    if lastNumber != a[i] {
        if n4counter > limit {
            print("\(lastNumber), ", terminator: "")
        }
        lastNumber = a[i]
        n4counter = 0
    }
    n4counter += 1
}
print()

- seriyvolk83 April 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> numsRepeated(vector<int> &nums) {
	unordered_map<int, int> items;
	for (auto i : nums) {
		items[i]++;
	}
	vector<int> result;
	for (auto entry : items) {
		if (entry.second == n / 4) {
			result.push_back(entry.first);
		}
	}
	return result;
}

- Anon April 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity of finding frequency of one number: log(n)
complexity of finding frequency of all numbers: d*log(n) where d is distinct numbers in array.

find_right_most_index_of_number() is modified version of binary search which return the right most index of value.

public class Main
{
    static int find_right_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l + r) / 2;

            if(array[r] == num)
                return r;
            else if (array[mid] == num)
                return find_right_most_index_of_number(array, mid, r-1, num);

            if (num < array[mid])
                return find_right_most_index_of_number(array, l, mid - 1, num);
            else if (num > array[mid])
                return find_right_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    public static void main(String args[])
    {
        int[] array = {1, 2, 2, 3, 4, 5, 5, 5};

        int l = 0;
        int r;
        while(l < array.length)
        {
            r = find_right_most_index_of_number(array, l, array.length - 1, array[l]);
            System.out.println("frequency of " + array[l] + " " + (r-l+1));
            l = r + 1;
        }
    }
}

- ziabadar4991 May 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity of finding frequency of one number: log(n)
complexity of finding frequency of all numbers: d*log(n) where d is distinct numbers in array.

find_right_most_index_of_number() is modified version of binary search which return the right most index of value.

public class Main
{
    static int find_right_most_index_of_number(int[] array, int l, int r, int num)
    {
        if(l <= r)
        {
            int mid = (l + r) / 2;

            if(array[r] == num)
                return r;
            else if (array[mid] == num)
                return find_right_most_index_of_number(array, mid, r-1, num);

            if (num < array[mid])
                return find_right_most_index_of_number(array, l, mid - 1, num);
            else if (num > array[mid])
                return find_right_most_index_of_number(array, mid + 1, r, num);
        }

        return -1;
    }

    public static void main(String args[])
    {
        int[] array = {1, 2, 2, 3, 4, 5, 5, 5};

        int l = 0;
        int r;
        while(l < array.length)
        {
            r = find_right_most_index_of_number(array, l, array.length - 1, array[l]);
            if((r-l+1) > array.length/4)
                System.out.println(array[l]);
            l = r + 1;
        }
    }
}

- ziabadar4991 May 13, 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