## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 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 - 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.

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

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

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

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

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

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

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

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)
} else counter = counter + 1
counter = counter + n - 1
} else counter = counter + 1
}
}``````

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

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.

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;
int b[]=new int;
int j=0;
a=1;
a=1;
a=1;
a=1;
a=1;
a=1;
a=3;
a=7;
a=11;
a=12;
a=19;
a=101;
a=101;
a=101;
a=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]);
}
}
}
}

}``````

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

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

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]) {
startIndex = endIndex + 1;
}
while (intArr[startIndex] == startNum) {
startIndex++;
}
endIndex = startIndex + size - 1;
findOccurredNum(intArr, startIndex, size);
}

}``````

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]) {
startIndex = endIndex + 1;
}
while (intArr[startIndex] == startNum) {
startIndex++;
}
endIndex = startIndex + size - 1;
findOccurredNum(intArr, startIndex, size);
}

}``````

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

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

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

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

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.