Google Interview Question
Principal Software EngineersCountry: United States
Interview Type: In-Person
Specifically, the occurrence count of each of those would be checked using binary search.
Checking occurrence can be done by equal_range() algorithm in C++. It's O(logn) time algorithm for sorted array.
This relevant problem may interest you:
What if the array is NOT sorted, and the "popularity" is defined as repeated more than n/2 times?
We can find that popular element in linear time and constant extra space. The idea is similar to "majority voting".
Code illustrates majority voting:
int candidate = A[0];
int vote = 1;
for(int k = 1; k<N; k++){
if (candidate == A[k]){
vote ++;
continue;
};
if (vote > 0){
vote --;
continue;
}else{
candidate = A[k];
vote = 1;
}
};
//double check for candidate:
vote = 0;
for(int k = 0; k<N; k++) vote += (candidate == A[k]);
if (vote > N/2) cout <<"Popular element is: "<<candidate<<endl;
This link gives details: capacode.com/?p=496
what if you have a case like N = 12
A[] = {1,2, 4, 4,4,7,7,8,9,9,10,10} checking only the elements of n/4 - n/2 - n/4*3 will not suffice, besides that it is necessary to expand the window starting from one of these positions n/4, n/2 3*n/4 until you fit a window of size n/4... Since you don't know exactly if that element is the popular one or not until you counted a n/4 window.
Note that the only numbers that can be the popular are 1, n/4, n/2, 3n/4, n
In this solution we are doing 8 binary search and we are using O(1) additional memory
def findPopular(items):
N = len(items)
inc = int(N/4)
i = [x*inc for x in [1, 2, 3, 4]]
n = [items[x] for x in i]
for k in range(0,len(i)):
a = i[k - 1] if k > 0 else 0
b = i[k + 1] if k + 1 < N else N -1
first = findFirst(items, a, i[k], n[k])
last = findLast(items, i[k], b, n[k])
if last - first + 1 >= inc:
return n[k]
def findFirst(items, i, j, n):
first = -1
while i <= j:
mid = int((i + j)/2)
if items[mid] < n:
i = mid + 1
else:
if items[mid] == n:
first = mid
j = mid - 1
return first
def findLast(items, i, j, n):
last = -1
while i <= j:
mid = int((i + j)/2)
if items[mid] > n:
j = mid - 1
else:
if items[mid] == n:
last = mid
i = mid + 1
return last
Look at 9 positions:
1, n/8, n/4, 3n/8, n/2, 5n/8, 3n/4, 7n/8, n
If a number is repeated n/4 or more, two consecutive elements (from above) will have its value.
Answer is the value common between any two consecutive elements.
That's O(1).
[1,2,3,3,3,4, 4, 5,6,7,8,9,10,11,12,13]
Arr[n/8] = 3
Arr[n/4] = 3
Arr[3n/8] = 4
It would see the 3, even though 3 doesn't happen n/4 times
If value is common between 2 consecutive elements, it means its repeated n/8 times not n/4 times. What if the reputation is exactly from n/8 to n/4?
[1,2,2,3,3,3, 3, 5,6,7,8,9,10,11,12,13]
Arr[n/8] = Arr[2] = 2
Arr[n/4] = Arr[4] = 3
Arr[3n/8] = Arr[6] = 3
In this pathological case, n/8 != n/4, but there is indeed a majority element at 3
Yes, I agree.
So, one way to go is to go ahead and verify the length by doing binary search for the number below and number above.
So, the solution is valid, but O(log n).
public static int GetPopularItem(int[] A)
{
int start = 0;
int end = S.Length;
int startItem = S[start];
while(true)
{
int mid = (start + end)/2;
int expected = S[end] + startItem;
if( S[mid] > mid + startItem)
{
end = mid;
}
else if(S[mid] == mid + startItem)
{
start = mid;
}
else
{
return mid;
}
}
}
private static SearchPopularItem(int[] A, int start, int end)
{}
public class Majority {
public static int findMajority(String s){
int[] arr = new int[s.length()];
for(int i=0;i<s.length();i++)
arr[i] =s.charAt(i)-'0';
return findMajority(arr, 0, s.length()-1);
}
public static int findMajority(int[] arr, int st, int end){
if(st>end)
return -1;
if(end-arr[end]<2)
return -1;
int mid= st+(end-st)/2;
if(arr[mid]==arr[mid+1]){
int temp = arr[mid];
int k =mid;
int j=mid+1;
int count=0;
while(k>=st && arr[k]==temp){
count++;
k--;
}
while(j<=end && arr[j]==temp ){
count++;
j++;
}
if(count>=4)
return temp;
}
int left = findMajority(arr, st, mid);
if(left==-1)
return findMajority(arr, mid+1, end);
return left;
}
/**
* Find popular item in sorted array of natural numbers.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
* @param args
*/
public static void main(String[] args) {
// String x = "123444445678";
// System.out.println(findMajority(x));
String x1 = "123456789999";
System.out.println(findMajority(x1));
}
}
public int findPopular(int [] numbers){
return findPopularRecurse(numbers,0,numbers.length);
}
public int findPopularRecurse(int [] numbers, int begin, int end){
if(end - begin < numbers.length/4)
return -1;
int mid = (begin+end)/2;
int tempBegin = mid;
int tempEnd = mid;
while(tempBegin > 0 && numbers[tempBegin] == numbers[mid])
tempBegin--;
while(tempEnd < numbers.length && numbers[tempEnd] == numbers[mid])
tempEnd++;
System.out.println("Checking for "+numbers[mid] + " from "+(tempBegin+1) + "to "+(tempEnd-1));
if((tempEnd -1) - (tempBegin+1) +1 >= numbers.length/4){
return numbers[mid];
}else{
return Math.max(findPopularRecurse(numbers,0,tempBegin),findPopularRecurse(numbers,tempEnd,end));
}
}
public int findPopular(int [] numbers){
return findPopularRecurse(numbers,0,numbers.length);
}
public int findPopularRecurse(int [] numbers, int begin, int end){
if(end - begin < numbers.length/4)
return -1;
int mid = (begin+end)/2;
int tempBegin = mid;
int tempEnd = mid;
while(tempBegin > 0 && numbers[tempBegin] == numbers[mid])
tempBegin--;
while(tempEnd < numbers.length && numbers[tempEnd] == numbers[mid])
tempEnd++;
System.out.println("Checking for "+numbers[mid] + " from "+(tempBegin+1) + "to "+(tempEnd-1));
if((tempEnd -1) - (tempBegin+1) +1 >= numbers.length/4){
return numbers[mid];
}else{
return Math.max(findPopularRecurse(numbers,0,tempBegin),findPopularRecurse(numbers,tempEnd,end));
}
}
Modified quick-sort without the merge partition on bit... then check range values.
For example partition on even odd or LSB 1 or 0
check if high - low >= n/4 && A[low] == A[high] add it to popular
and
high - low < n/4 drop it
public class PopularNumber {
private int popular;
private int popCount;
public int findPopular(int[] nums) {
int length = nums.length;
popular = 0;
popCount = 0;
if (length <= 0) {
return -1;
}
search(nums, 0, length-1);
return popular;
}
private void search(int[] nums, int start, int end) {
if ((end-start) < (nums.length/4)) {
return;
}
int center = (start + end) /2;
search(nums, start, center);
search(nums, center+1, end);
int count = 0;
if (nums[center] == nums[center-1]) {
count++;
}
if (nums[center] == nums[center+1]) {
count++;
}
if (count > popCount) {
popCount = count;
popular = nums[center];
}
}
public static void main(String[] args) {
PopularNumber p = new PopularNumber();
int[] nums = {1, 2, 3, 4, 4, 5, 6, 7, 8};
int popular = p.findPopular(nums);
System.out.println(popular);
}
}
#!/usr/bin/env python
def findPopularNumberOLogN(numstring):
numLen = len(numstring)
popularNumCondition = numLen/4
i = 0
while (2 ** i) < numLen:
pos = 2 ** i
prevPos = pos - 1
nextPos = pos + 1
count = 1
while (prevPos >= 0) and (numstring[pos] == numstring[prevPos]):
count += 1
prevPos -= 1
while (nextPos < numLen) and (numstring[pos] == numstring[nextPos]):
count += 1
nextPos += 1
if count > popularNumCondition:
print 'Popular # from OLogN is ', numstring[pos]
return
else:
i += 1
print 'Popular # not found'
return
if __name__ == "__main__":
findPopularNumberOLogN('123444445678')
#!/usr/bin/env python
def findPopularNumberOLogN(numstring):
numLen = len(numstring)
popularNumCondition = numLen/4
i = 0
while (2 ** i) < numLen:
pos = 2 ** i
prevPos = pos - 1
nextPos = pos + 1
count = 1
while (prevPos >= 0) and (numstring[pos] == numstring[prevPos]):
count += 1
prevPos -= 1
while (nextPos < numLen) and (numstring[pos] == numstring[nextPos]):
count += 1
nextPos += 1
if count > popularNumCondition:
print 'Popular # from OLogN is ', numstring[pos]
return
else:
i += 1
print 'Popular # not found'
return
if __name__ == "__main__":
findPopularNumberOLogN('123456789')
// Popular number in an array occurs n/4 times.
// Assuming rounding down division of n/4, perform counting of every
// element on the index k*(n/4)-1 in the range [ 0, ..., n-1 ]
// - where k ∈ [1, ... ]
// Complexity: number of searches performed will be 4 or 5 times 2
// (lower and upper bound), each with O(log(n)) time.
// Example 1:
// o 12 / 4 = 3
// o [ 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8 ]
// ^ ^ ^ ^ 4 * 2 * binary-search
// Example 2:
// o 11 / 4 = 2
// o [ 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7 ]
// ^ ^ ^ ^ ^ 5 * 2 * binary-searches
#include <iostream>
#include <algorithm>
void print_popular(int a[], int L) {
using std::lower_bound;
using std::upper_bound;
int step = L / 4;
for (int i = step-1; i < L;) {
int val = a[i];
int *ub = upper_bound(a, a+L, val);
int *lb = lower_bound(a, a+L, val);
if (ub-lb >= step) {
std::cout << val << " ";
}
// next i from ub (draw array to understand this one...)
i = ((ub-a)/step + 1) * step - 1;
}
std::cout << std::endl;
}
int main() {
const int La = 12;
std::cout << "First case: ";
int a[La] = { 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8 };
print_popular(a, La);
const int Lb = 11;
std::cout << "Second case: ";
int b[Lb] = { 1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7 };
print_popular(b, Lb);
}
import java.util.*;
public class find_popular_items
{
public static int find_freq(List<Integer> nums, int pos)
{
int freq1 = 0;
// binary search
if (pos < 0 || pos >= nums.size())
{
return 0;
}
int pivot = nums.get(pos);
int leftmost_pos = 0;
int rightmost_pos = nums.size()-1;
if (nums.get(leftmost_pos) != pivot)
{
int right1 = pos;
int left1 = leftmost_pos;
while(true)
{
int mid1 = (int) (right1 + left1)/2;
if (mid1 == left1 || mid1 == right1)
{
if (nums.get(left1) == pivot)
{
leftmost_pos = left1;
}
else
{
leftmost_pos = right1;
}
break;
}
else if(nums.get(mid1) == pivot && nums.get(mid1-1) != pivot)
{
leftmost_pos = mid1; break;
}
else if (nums.get(mid1) != pivot && nums.get(mid1+1) == pivot)
{
leftmost_pos = mid1 + 1; break;
}
else
{
if (nums.get(mid1) < pivot)
left1 = mid1;
else
right1 = mid1;
}
}
}
if (nums.get(rightmost_pos) != pivot)
{
int left1 = pos;
int right1 = rightmost_pos;
while(true)
{
int mid1 = (int) (right1 + left1)/2;
if (mid1 == left1 || mid1 == right1)
{
if (nums.get(right1) == pivot)
{
rightmost_pos = right1;
}
else
{
rightmost_pos = left1;
}
break;
}
else if(nums.get(mid1) == pivot && nums.get(mid1+1) != pivot)
{
rightmost_pos = mid1; break;
}
else if (nums.get(mid1) != pivot && nums.get(mid1-1) == pivot)
{
rightmost_pos = mid1 - 1; break;
}
else
{
if (nums.get(mid1) > pivot)
right1 = mid1;
else
left1 = mid1;
}
}
}
return (rightmost_pos - leftmost_pos + 1);
}
public static void find_func(List<Integer> nums, List<Integer> p_items)
{
// we only need to check freq of four items: n/4, n/2, 3n/4, n
// n/4
int list_size = nums.size();
int freq1 = find_freq(nums, (list_size/4));
int freq2 = find_freq(nums, (list_size/4*2));
int freq3 = find_freq(nums, (list_size/4*3));
int freq4 = find_freq(nums, (list_size));
if ((double)freq1 >= list_size/4.0)
p_items.add(nums.get(list_size/4));
if ((double)freq2 >= list_size/4.0)
p_items.add(nums.get(list_size/4*2));
if ((double)freq3 >= list_size/4.0)
p_items.add(nums.get(list_size/4*3));
if ((double)freq4 >= list_size/4.0)
p_items.add(nums.get(list_size-1));
}
public static void main(String[] args)
{
List<Integer> nums = new ArrayList<Integer>();
nums.add(1); nums.add(2); nums.add(3); nums.add(4);
nums.add(4); nums.add(4); nums.add(4); nums.add(4);
nums.add(5); nums.add(6); nums.add(7); nums.add(8);
List<Integer> p_items = new ArrayList<Integer>();
find_func(nums, p_items);
Hashtable<Integer,Integer> hs1 = new Hashtable<Integer,Integer>();
for (int i = 0; i < p_items.size(); i++)
{
if (hs1.containsKey(p_items.get(i)))
continue;
else
hs1.put(p_items.get(i), 0);
}
Enumeration<Integer> keys1 = hs1.keys();
List<Integer> new_p_items = new ArrayList<Integer>();
while( keys1.hasMoreElements())
new_p_items.add(keys1.nextElement());
System.out.println("size: "+new_p_items.size());
for (int i = 0; i < new_p_items.size(); i++)
{
System.out.println(new_p_items.get(i));
}
System.out.println("Program Ends.");
}
}
I believe this should work.
void print_popular(vector<int> v)
{
if(v.size() > 0)
{
int currentIndex = (v.size() / 4)-1;
int prevIndex = 0;
int num1 = 0;
int num2 = 0;
while(currentIndex < v.size())
{
num1 = v[prevIndex];
num2 = v[currentIndex];
if(num1 == num2)
{
printf("\nPOPULAR=%d",num1);
prevIndex = currentIndex+1;
currentIndex += (v.size()/4);
}else
{
prevIndex++;
currentIndex++;
}
}
}
}
Hi,
please correct me if I am wrong.
-The O(log N) time requirement and O(1) space indicates this MUST be solved with binary search.
-The only way binary search works is if given the current number I can tell if I overshoot or undershoot the target
follows: there can be only one number repeated in the array, the popular number. (The original in the description fits this).
Otherwise, If I can repeat another number which is not the popular one it is impossible to find out if I overshot the popular number. E.g.:
[1,1,2,2,3,3,5,6,6,6,6]
Binary search will first land on 3 knowing that it should be a 6, thus there are 3 repeated numbers on the left side. So the left side could be [1,1,1,1,2,3 .... or [1,1,2,2,3,3 ... you can see binary search won't work unless you constraint the number of numbers that can be repeated.
Hi,
please correct me if I am wrong.
-The O(log N) time requirement and O(1) space indicates this MUST be solved with binary search.
-The only way binary search works is if given the current number I can tell if I overshoot or undershoot the target
follows: there can be only one number repeated in the array, the popular number. (The original in the description fits this).
Otherwise, If I can repeat another number which is not the popular one it is impossible to find out if I overshot the popular number. E.g.:
[1,1,2,2,3,3,5,6,6,6,6]
Binary search will first land on 3 knowing that it should be a 6, thus there are 3 repeated numbers on the left side. So the left side could be [1,1,1,1,2,3 .... or [1,1,2,2,3,3 ... you can see binary search won't work unless you constraint the number of numbers that can be repeated.
This is O(logn) for time and O(1) for space.
int findMajorNumber(int[] array){
int n = array.length;
int subsetSize = n/4;
int left = 0;
int right = left + subsetSize;
int majorNumber = -1;
while(left < n && right < (n-1)){
if(array[left] == array[right] || array[right] == array[right+1]){
majorNumber = checkMajorNumber(array, right, subsetSize+1);
}
left = right+1;
right = left + subsetSize;
}
return majorNumber;
}
int checkMajorNumber(int[] array, int position, int majorCount){
int left = position;
int right = position;
while(left >= 0 && array[left] == array[position]){
left--;
}
while(right < array.length && array[right] == array[position]){
right++;
}
left++;
if((right-left) >= majorCount){
return array[position];
}
return -1;
}
public static void popularIteminSortedArray(int[] arr) {
int counterBeg = 0;
int counterEnd = 0;
boolean isThereAny = false;
for (int i = 1, j = arr.length - 1; i < arr.length && j > 0; i++, j--) {
if (i>j && (counterBeg < 3) && (counterEnd < 3))
break;
if(arr[i] == arr[i-1]) {
if(counterBeg >= 4){
System.out.println(" element is: " + arr[i]);
counterBeg = 0;
isThereAny = true;
continue;
}
counterBeg++;
}
if (arr[j] == arr[j - 2]) {
if(counterEnd > 4){
System.out.println(" element is: " + arr[j]);
counterEnd = 0;
isThereAny = true;
continue;
}
counterEnd++;
}
}
if (!isThereAny) System.out.println("None !!!");
}
Check a[n/4] and a[n/2] and a[3*n/4] occurrence
- dgbfs February 26, 2015Checking the occurrence takes O(lgn) time