Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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;
}
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
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
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
}
}
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.
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]);
}
}
}
}
}
#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;
}
#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;
}
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);
}
}
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);
}
}
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;
}
}
}
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;
}
}
}
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).
- aonecoding March 24, 2017We 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.