Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
this is adapted from unbelievably mind-twisting STL lower/upper bound implemenetations:
void find_bounds(int *a, int n, int val) {
int beg = 0, end = n-1;
// searching upper bound
while(beg < end) {
int mid = (beg + end)/2;
if(!(val<a[mid])) {
beg = mid+1;
} else {
end = mid;
}
}
int upper_bnd = beg;
beg = 0, end = n-1;
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid] < val) {
beg = mid+1;
} else {
end = mid;
}
}
int lower_bnd = beg;
printf("[%d; %d]\n", lower_bnd, upper_bnd);
}
//Here is my solution
public static int numberOccurrence(int[]sortedArray,int number,int a,int b)
{
if(a<b)
{
int pivot=(a+b)/2;
int num=sortedArray[pivot];
if(num==number)
return (1+numberOccurrence(sortedArray, number, a, pivot)+numberOccurrence(sortedArray, number, pivot+1, b));
else if(num>number)
return numberOccurrence(sortedArray, number, a, pivot);
else
return numberOccurrence(sortedArray, number, pivot+1, b);
}
else
return 0;
}
1) Use binary search until mid points to the required number.
2) Then do left++ and right-- until both point at the required number.
3) Take difference between left and right pointer to find the number of repetition.
/*
Given a sorted array, find a way to find the # of occurrence of a number
for eg: [1, 1, 2, 3, 3, 3, 4, 5]
find # of occurrence of 3 in time better than O(n)
*/
public class NumOfOccurence {
public static void main (String args[]) {
int[] a = {1, 2, 3, 3, 3, 3, 3, 4, 5};
for (int i = 0; i < 6; i++) {
int r = func(a, i);
System.out.println("i = " + i + " Rep: " + r);
}
}
public static int func (int[] a, int n) {
if (a.length == 0)
return -1;
int low = 0;
int high= a.length - 1;
int mid = (low + high) / 2;
while (mid > low && mid < high) {
if (a[mid] == n) {
while (a[low] != a[mid] && low != mid)
low = low + 1;
while (a[high] != a[mid] && high != mid)
high = high - 1;
if (low == high)
return 1;
else
return (high - low + 1);
} else if (a[mid] < n) {
low = mid;
mid = (low + high) / 2;
} else if (a[mid] > n) {
high = mid;
mid = (low + high) / 2;
}
}
// Case when n is present only at edges
if (a[low] == n || a[high] == n)
return 1;
return -1;
}
}
To get O(lgn), we need to find the lower and upper bound of the given number in the array.
int findnum(int arr[], int n, int k)
{
int start=0;
int end = n-1;
int med=-1;
int low= 0;
int hi = 0;
while(start <= end)
{
med = (start+end)/2;
if( arr[med] < k)
{
low=med;
start = med+1;
}
else if(arr[med] >= k)
end=med-1;
}
start=0;
end = n-1;
while(start <= end)
{
med = (start+end)/2;
if(arr[med] > k)
{
hi = med;
end=med-1;
}
else if(arr[med] <= k)
start = med+1;
}
if(hi == 0 && low != 0)
{
return (n-low-1);
}
else if (low == 0 && hi !=0 )
return hi-low;
else if( hi == 0 && low == 0)
{
if(arr[low] == k)
return n;
return 0;
}
else
return hi-low-1;
In sorted array, we can locate any number in O(logn) time. By finding the first the target's first position and last position, we can count its occurrence in O(logn) time.
If we can use C++ standard library <algorithm>, then the answer is simple:
int count_in_sorted_array(int arr[], int n, int x)
{
return upper_bound(arr, arr + n, x) - lower_bound(arr, arr + n, x);
}
If we are not supposed to use library, the subfunctiones go like this:
def lower_bound(arr, x):
"""
return the first position in the sorted arr, on which the value is no smaller than x
return len(arr) if no such value exists
"""
if not arr:
return 0
# check front
l = 0
if arr[0] >= x:
return 0
# check back
r = len(arr)
if arr[r-1] < x:
return r
# binary search, keep arr[r] >= x and arr[l] < x
while l + 1 < r:
m = (l + r) // 2
if arr[m] >= x:
r = m
else:
l = m
return r
def upper_bound(arr, x):
"""
return the first position in the sorted arr, on which the value is larger than x
return len(arr) if no such value exists
"""
if not arr:
return 0
# check front
l = 0
if arr[0] > x:
return 0
# check back
r = len(arr)
if arr[r-1] <= x:
return r
# binary search, keep arr[r] > x and arr[l] <= x
while l + 1 < r:
m = (l + r) // 2
if arr[m] > x:
r = m
else:
l = m
return r
def count_in_sorted_array(arr, x):
return upper_bound(arr, x) - lower_bound(arr, x)
# test case
arr = [1, 1, 2, 3, 3, 3, 4, 5]
print(count_in_sorted_array(arr, 1))
print(count_in_sorted_array(arr, 2))
print(count_in_sorted_array(arr, 3))
print(count_in_sorted_array(arr, 4))
print(count_in_sorted_array(arr, 5))
If you are using C++,we can use upper_bound and lower_bound which is actually binary search in some ways.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[]={1,1,2,3,3,3,4,5,5,5,5}; //Let us take this for example
int l=sizeof(a)/sizeof(a[0]); //Size of our array
int x=upper_bound(a,a+(l),5)-lower_bound(a,a+l,5); //let us search for 5
cout<<x<<endl;
return 0;
// This will take logarithmic time,more precisely O(log2(N)) order.
}
int findCount(int[] sortedArray, int value){
//index range where for the first time value could occur in the array
int firstStart = 0, firstEnd = sortedArray.length - 1;
//index range where for the last time value could occur in the array
int lastStart = 0, lastEnd = sortedArray.length - 1;
int middle;
int middlevalue;
//finding first occurance of the element
//O(logn)
while(sortedArray[firstStart] != sortedArray[firstEnd]){
middle = ((firstEnd - firstStart)+ 1)/2 + firstStart;
middlevalue = sortedArray[middle];
if(value < middlevalue)
firstEnd = middle - 1;
if(value > middlevalue)
firstStart = middle + 1;
if(value == middlevalue)
firstEnd = middle;
}
//finding last occurance of the element
//O(logn)
while(sortedArray[lastStart] != sortedArray[lastEnd]){
middle = ((lastEnd - lastStart)+ 1)/2 + lastStart;
middlevalue = sortedArray[middle];
if(value < middlevalue)
lastEnd = middle - 1;
if(value > middlevalue)
lastStart = middle + 1;
if(value == middlevalue)
lastStart = middle;
}
//return the total count between first and last occurance
return lastEnd - firstStart + 1;
}
#python code
def find_element(mylist,find_ele):
length=len(mylist)
mid_pos=length/2
count=0
if mylist[0]==find_ele and mylist[length-1]==find_ele:
if not length==1:
return "All the elements are same,count is {0}".format(length)
else:
return "There is only 1 occurrence"
if mylist[mid_pos]>find_ele:
for i in range(mid_pos,-1,-1):
if mylist[i]!=find_ele:
break
else:
count+=1
elif mylist[mid_pos]>find_ele:
for i in range(mid_pos+1,length):
if mylist[i]!=find_ele:
break
else:
count+=1
else:
for i in range(mid_pos,-1,-1):
if mylist[i]!=find_ele:
break
else:
count+=1
for i in range(mid_pos+1,length):
if mylist[i]!=find_ele:
break
else:
count+=1
return count
print find_element([1, 1, 2, 3, 3, 3, 4, 5],3)
print find_element([3,3,3,3,3,3,3],3)
print find_element([3],3)
print find_element([3,3,3],3)
@Unroll
def "the #k th occurence of #number in #numbers is #result"() {
expect:
findKthOcurrence(numbers, number, k) == result
where:
numbers | number | k | result
[1, 2, 3] | 1 | 1 | 0
[1, 2, 3] | 2 | 1 | 1
[1, 2, 3] | 4 | 1 | -1
[1, 2, 3] | 1 | 2 | -1
[1, 1, 2, 2, 3] | 1 | 1 | 0
[1, 1, 2, 2, 3] | 1 | 2 | 1
[1, 1, 2, 2, 3] | 2 | 1 | 2
[1, 1, 2, 2, 3] | 2 | 2 | 3
[1, 1, 2, 2, 3] | 3 | 1 | 4
}
int findKthOcurrence(List<Integer> numbers, int number, int k) {
int firstOcurrence = findFirstOcurrence(numbers, number, 0, numbers.size() - 1);
if(firstOcurrence == -1) {
return -1;
}
int indexOfK = firstOcurrence + k - 1;
if(numbers.get(indexOfK) == number) {
return indexOfK;
} else {
return -1;
}
}
int findFirstOcurrence(List<Integer> numbers, int number, int left, int right) {
if(left > right) {
return -1;
}
int mid = left + (right - left)/2;
if(numbers.get(mid) == number) {
if(mid == 0 || numbers.get(mid-1) != number) {
return mid;
} else {
return findFirstOcurrence(numbers, number, left, mid-1);
}
} else if(number < numbers.get(mid)){
return findFirstOcurrence(numbers, number, left, mid-1);
} else {
return findFirstOcurrence(numbers, number, mid+1, right);
}
}
public class NumofOccurance {
public static void main(String[] args) {
int[] a = { 1, 1, 2, 3, 3, 3, 4, 5 };
Search(a,0,a.length,3);
}
static void Search(int[] arr,int left,int right, int value){
int pivot = left+right/2;
int val,check =0;
if(arr[pivot]==value){
val = pivot;
check=check+1;
while(arr[val-1] ==3 && val>=0 && check< arr.length){
val=val-1;
check++;
}
while(arr[pivot+1] ==3 && val>=0 && check< arr.length){
pivot=pivot+1;
check++;
}
}
else{
if(arr[pivot]<value){
Search(arr,0,pivot,value);
}
else if(arr[pivot]>value){
Search(arr,pivot,arr.length,value);
}
}
System.out.println(check);
}
public class NumofOccurance {
public static void main(String[] args) {
int[] a = { 1, 1, 2, 3, 3, 3, 4, 5 };
Search(a,0,a.length,3);
}
static void Search(int[] arr,int left,int right, int value){
int pivot = left+right/2;
int val,check =0;
if(arr[pivot]==value){
val = pivot;
check=check+1;
while(arr[val-1] ==3 && val>=0 && check< arr.length){
val=val-1;
check++;
}
while(arr[pivot+1] ==3 && val>=0 && check< arr.length){
pivot=pivot+1;
check++;
}
}
else{
if(arr[pivot]<value){
Search(arr,0,pivot,value);
}
else if(arr[pivot]>value){
Search(arr,pivot,arr.length,value);
}
}
System.out.println(check);
}
public class Occur {
public static void check(int[] a,int n,int val){
int beg=0,end=n-1;
while(beg<end){
int mid=(beg+end)/2;
if(val>a[mid])
beg=mid+1;
else
end=mid;
}
//System.out.println(beg);
int lower=beg;
beg=lower;
end=n-1;
while(beg<=end){
int mid=(beg+end)/2;
if(val<a[mid]){
end=mid-1;
}else{
beg=mid+1;
}
}
System.out.println("lower --- beg---end "+lower+" "+beg+" "+(beg-1));
System.out.println("occurances "+((beg-1)-lower+1));
}
public static void main(String[] args) {
int[] a={1,1,2,3,3,3,4,5};
check(a,8,3);
}
}
complexity: O(log n)
public class Occur {
public static void check(int[] a,int n,int val){
int beg=0,end=n-1;
while(beg<end){
int mid=(beg+end)/2;
if(val>a[mid])
beg=mid+1;
else
end=mid;
}
//System.out.println(beg);
int lower=beg;
beg=lower;
end=n-1;
while(beg<=end){
int mid=(beg+end)/2;
if(val<a[mid]){
end=mid-1;
}else{
beg=mid+1;
}
}
System.out.println("lower --- beg---end "+lower+" "+beg+" "+(beg-1));
System.out.println("occurances "+((beg-1)-lower+1));
}
public static void main(String[] args) {
int[] a={1,1,2,3,3,3,4,5};
check(a,8,3);
}
}
public class SortedArrayCountN {
public static void main(String[] args) {
int[] A = {1, 1, 2, 3, 3, 3, 4, 5};
System.out.println(count(A, 1, 0, A.length - 1));
}
static int count(int[] A, int n, int lo, int hi) {
if (A == null || A[lo] > n || A[hi] < n) {
return 0;
}
if (A[lo] == A[hi]) {
return hi - lo + 1;
}
int mid = lo + (hi - lo) / 2;
if (A[mid] < n) {
return count(A, n, mid + 1, hi);
} else if (A[mid] > n) {
return count(A, n, lo, mid - 1);
} else {
return 1 + count(A, n, mid + 1, hi)
+ count(A, n, lo, mid - 1);
}
}
}
This can be done with O(n) time and O(1) space using dynamic programming. The idea is Let N[I] be the number of pairs whose sum is greater than n.
N[I] = N[I-1] + PairsWithSumGreaterThanN {a[I] U { a[0... I-1]}}.
Observe that a[I] paired with a[I-1, I-2,....k] > n implies a[I+1] paired with a[I-1.....k] > n
now to the c# code:-
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
var arry =new int[] { 1, 2, 3, 4, 5 };
var res = SumGreaterThanN(arry, 3);
var res2 = SumGreaterThanN(arry, 10);
var res3 = SumGreaterThanN(arry, 7);
}
public static int SumGreaterThanN(int[] arr, int n)
{
if (arr == null || arr.Length <= 1)
{
return 0;
}
var m1 = arr[1] + arr[0] > n ? 1 : 0;
// unexplored elements [0..k1]
var u1 = m1 == 0 ? 1 : -1;
for (int i = 2; i < arr.Length; i++)
{
// -:) pairs will work if a[i] is replaced by a[i-1]
m1 += i - (u1 + 1);
while (u1 >= 0)
{
if (arr[i] + arr[u1] > n)
{
m1++;
u1--;
}
else
{
break;
}
}
if (arr[i] + arr[i - 1] < n)
{
u1 = i;
}
}
return m1;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
var arry =new int[] { 1, 2, 3, 4, 5 };
var res = SumGreaterThanN(arry, 3);
var res2 = SumGreaterThanN(arry, 10);
var res3 = SumGreaterThanN(arry, 7);
}
public static int SumGreaterThanN(int[] arr, int n)
{
if (arr == null || arr.Length <= 1)
{
return 0;
}
var m1 = arr[1] + arr[0] > n ? 1 : 0;
// unexplored elements [0..k1]
var u1 = m1 == 0 ? 1 : -1;
for (int i = 2; i < arr.Length; i++)
{
// -:) pairs will work if a[i] is replaced by a[i-1]
m1 += i - (u1 + 1);
while (u1 >= 0)
{
if (arr[i] + arr[u1] > n)
{
m1++;
u1--;
}
else
{
break;
}
}
if (arr[i] + arr[i - 1] < n)
{
u1 = i;
}
}
return m1;
}
}
}
Divide and conquer method:
1. Find the element in the array.
2. If found search for 1st and last replica in the previous interval
Worst case O(2*nlogn) = O(nlogn) -first iteration find the target-
Best case O(nlogn)
Python code
def findmax(a, i, j, x):
if a[j] == x:
return j
while i + 1 < j:
print (str(i) + " " + str(j) + " max")
m = (j + i)/2
if a[m] <= x :
i = m
else: #a[m] > x
j = m
if a[i] > x:
return i-1
else:
return i
def findmin(a, i, j, x):
if a[i] == x:
return i
while i + 1 < j:
print (str(i) + " " + str(j) + " min")
m = (j + i)/2
if a[m] < x :
i = m
else: #a[m] > x
j = m
if a[i] < x:
return i+1
else:
return i
def n_occ(a, x):
l = len(a)
i = 0
j = l - 1
while i + 1 < j:
print (str(i) + " " + str(j) + " nocc")
m = (j + i)/2
if a[m] < x :
i = m
elif a[m] > x:
j = m
else: ## a[m] == x
return (findmax(a,m,j, x) - findmin(a, i, m, x) + 1)
return 0
void int count(int[] a, int val) {
if(a == null || a.length == 0 || a[0] > val || a[a.length - 1] < val){
return 0;
}
if(a[0] == val && a[a.length - 1] == val){
return a.length;
}
int foundLowerBound = -1;
int foundUpperBound = -1;
int foundValue = -1;
if(a[0] == val){
foundLowerBound = 0;
foundValue = 0;
}
if(a[a.length - 1] == val){
foundUpperBound = a.length - 1;
foundValue = a.length - 1;
}
if(foundValue == -1){
int beg = 0;
int end = a.length-1;
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid] == val){
foundValue = mid;
break;
}
if(a[mid] < val)) {
beg = mid+1;
} else {
end = mid;
}
}
if(foundValue == -1){
return 0;
}
}
if(foundLowerBound == -1){
int beg = 0;
int end = foundValue - 1;
if(a[end] != val){
foundLowerBound = foundValue;
}
else{
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid + 1] == val && a[mid] != val){
foundLowerBound = mid + 1;
break;
}
if(a[mid] == val){
end = mid - 1;
if(a[end] != val){
foundLowerBound = mid;
break
}
} else {
beg = mid;
}
}
}
}
if(foundUpperBound == -1){
int beg = foundValue + 1;
int end = a.length - 1;
if(a[beg] != val){
foundUpperBound = foundValue;
}
else{
while(beg < end) {
int mid = (beg + end)/2;
if(a[mid - 1] == val && a[mid] != val){
foundUpperBound = mid - 1;
break;
}
if(a[mid] == val){
beg = mid + 1;
if(a[beg] != val){
foundUpperBound = mid;
break;
}
}
else {
end = mid;
}
}
}
}
return foundUpperBound - foundLowerBound + 1;
}
This one is logarithmic, even when the query is repeated n times.
def findNbrOcc (aSorted, nNumber, nLeft = False, nRight = False):
if len(aSorted) == 0:
return 0
elif len(aSorted) == 1:
if aSorted[0] != nNumber:
return 0
else:
return 1
nMiddle = len(aSorted)//2
if aSorted[nMiddle] > nNumber:
return findNbrOcc (aSorted[:nMiddle], nNumber, nLeft, nRight)
elif aSorted[nMiddle] < nNumber:
return findNbrOcc (aSorted[nMiddle:], nNumber, nLeft, nRight)
else:
if nLeft:
rightElems = len(aSorted[:nMiddle])
else:
rightElems = findNbrOcc (aSorted[:nMiddle], nNumber, False, True)
if nRight:
leftElems = len(aSorted[nMiddle + 1:])
else:
leftElems = findNbrOcc (aSorted[nMiddle + 1:], nNumber, True, False)
return 1 + leftElems + rightElems
1. Use binary search
2. if arr[mid] = val, chk for arr[mid/2] and arr[3*mid/2]
Here, key is to try to divide the search range always in half.
Tight bound will be O(logn)
public class HelloWorld{
public static void main(String []args){
int[] arr= {1,1,1,2,3,3,4,5,6};
System.out.println(f(arr, 3, 0, arr.length-1));
}
public static int f(int[] arr, int num, int start, int end){
if(start>end){
return 0;
}
int count=0;
int mid = start+(end-start)/2;
if(arr[mid] < num){
start=mid+1;
return f(arr, num, start, end);
} else if(arr[mid] >num){
end = mid-1;
return f(arr, num, start, end);
} else{ //(arr[mid]==num)
if(start==end){
return 1;
} // more than 1 element
count+=1;
int mid1= start+(mid-1-start)/2;
int mid2= (mid+1)+(end-(mid+1))/2;
if(arr[mid1]==num){
count+=mid-mid1;
count+= f(arr, num, start, mid1-1);
//check b/w start and mid1
} else{
count+= f(arr, num, mid1+1, mid-1);
//check b/w mid1 and mid
}
if(arr[mid2] ==num){
count+=mid2-mid;
count+= f(arr, num, mid2+1, end);
//check b/w end and mid2
} else{
count+= f(arr, num, mid+1, mid2-1);
//check b/w mid and mid2
}
return count;
}
}
}
O(n) worst case
public static int count(int[] a, int l, int r, int x){
int cnt = 0;
if(l>r) return cnt;
int mid = (l+r)/2;
if(a[mid] > x) return count(a, l, mid-1, x);
if(a[mid] < x) return count(a, mid+1, r, x);
if(a[mid] == x) {
cnt++;
int i = 1;
while(true) {
if(mid+i>r && mid-i<l) break;
if(mid+i<=r && a[mid+i] == x) cnt++;
if(mid-i>=l && a[mid-i] == x) cnt++;
i++;
}
}
return cnt;
}
public static int count(int[] a, int l, int r, int x){
int cnt = 0;
if(l>r) return cnt;
int mid = (l+r)/2;
if(a[mid] > x) return count(a, l, mid-1, x);
if(a[mid] < x) return count(a, mid+1, r, x);
if(a[mid] == x) {
cnt++;
int i = 1;
while(true) {
if(mid+i>r && mid-i<l) break;
if(mid+i<=r && a[mid+i] == x) cnt++;
if(mid-i>=l && a[mid-i] == x) cnt++;
i++;
}
}
return cnt;
}
O(n) worst case
#include <iostream>
using namespace std;
int search(int a[],int l,int h,int k)
{
if(l>h)
return 0;
int m=(l+h)/2;
if (a[m]==k)
return search(a,l,m-1,k)+search(a,m+1,h,k)+1;
else
return a[m]>k?search(a,l,m-1,k):search(a,m+1,h,k);
}
int main()
{
int a[]={1,1,2,3,4,5};
int n=sizeof(a)/sizeof(a[0]),k=-1;
cout<<search(a,0,n-1,k);
return 0;
}
#include <iostream>
using namespace std;
int search(int a[],int l,int h,int k)
{
if(l>h)
return 0;
int m=(l+h)/2;
if (a[m]==k)
return search(a,l,m-1,k)+search(a,m+1,h,k)+1;
else
return a[m]>k?search(a,l,m-1,k):search(a,m+1,h,k);
}
int main()
{
int a[]={1,1,2,3,4,5};
int n=sizeof(a)/sizeof(a[0]),k=-1;
cout<<search(a,0,n-1,k);
return 0;
}
We can use a sort of modified binary search. We get the middle element, if it equals the required val, then we search left and right again, but only by one element. If the middle element is not equal to val, then we do the normal binary search.
enum SearchDir {
LEFT = 0,
RIGHT,
BOTH
};
int num_count(int arr[], int left, int right, int val, enum SearchDir s) {
static int count;
if(left > right)
return 0;
int mid = (left + right) / 2;
if(arr[mid] == val){
count++;
if(s == SearchDir::LEFT || s == SearchDir::BOTH) {
num_count(arr, mid-1, mid-1, val, SearchDir::LEFT);
}
if(s == SearchDir::RIGHT|| s == SearchDir::BOTH) {
num_count(arr, mid+1, mid+1, val, SearchDir::RIGHT);
}
} else {
if(count == 0){
num_count(arr, left, mid-1, val, SearchDir::BOTH);
num_count(arr, mid + 1 , right, val, SearchDir::BOTH);
}
}
return count;
}
int main()
{
int arr[8] = {1, 1, 2, 3, 3, 3, 4, 5};
int count = num_count(arr, 0, 7, 1, SearchDir::BOTH);
cout << "number of times 1 found - " << count;
return 0;
}
Isn't this O(n) in the worst case when the entire array is 3s as it degenerates to a linear scan? You're not halving the array ever in that case.
Instead of "just moving by one element" why not do two binary searchs. One to find to find an index j such that A[j] = 3 and A[j+1] > 3 and another to find the other index k such that A[k] = 3 and a[k-1] < 3. Then return k-j+1.
int occur(int a[],int size,int t)
{
int count,lb=0,ub=size,mid,j;
count=0;
while(lb<=ub)
{
mid=(lb+ub)/2;
if(t==a[mid])
{
if(mid!=0)
{
j=mid-1;
while(t==a[j--])
count++;
}
while(t==a[mid++])
count++;
return count;
}
if(t>a[mid])
lb=mid+1;
if(t<a[mid])
ub=mid-1;
}
printf("Element Not Found\n");
exit(1);
}
My idea is to use binary search to locate the first occurrence of the target value, once we found it we just count the number of occurrences of the target value to the left and right.
public int NumberOccurrences(int[] values, int value)
{
int index = FindValue(values, value);
if (index == -1)
return 0;
int count = 1;
// Count the number of occurrences to the left
int i = index-1;
while (i >= 0 && values[i--] == value)
count++;
// Count the number of occurrences to the right
i = index + 1;
while (i < values.Length && values[i++] == value)
count++;
return count;
}
// Returns the index of the first occurrence found of value; using binary search.
private int FindValue(int[] values, int target)
{
return FindValue(values, target, 0, values.Length-1);
}
private int FindValue(int[] values, int target, int start, int end)
{
if (end < start)
return -1;
int middle = (start + end) / 2;
if (values[middle] == target)
return middle;
if (target < values[middle])
return FindValue(values, target, start, middle-1);
return FindValue(values, target, middle+1, end);
}
In this logic, the worst case complexity is still O(n) that is when the array is all 3's or the number you are trying to find.
Of course the worst case is O(n). The worst case will always be O(n). What is your point? Do you have a better solution?
Yes, do it in O(logN) time by binary searching for the index where A[j] ==3 and A[j-1] < 3. This is the lowerbound. Then do it again for the index where A[k] ==3 and A[k+1] > 3.
Return k-j+1.
Implement two recursive programs that utilize binary search but when they find the given instance they again perform search in a particular (left or right) direction. Your aim is to find the start and end of the continuous stream of the given number, check out the pseudocode below
int findStart(int [] array, int num)
{
int pos = binarySearch(array, num)
// If the number also exists left to the position, then binary search on left part of array
if (pos != 0 && array[pos-1] == num)
{
pos = findStart(array[0:pos], num)
}
return pos
}
int findEnd(int [] array, int num)
{
int pos = binarySearch(array, num)
// If the number exists right to the position then binary search on right part of array
if (pos != array.length-1 && array[pos+1] == num)
{
pos = findEnd(array[pos:array.length], num)
}
return pos
}
int count(int [] array, int num)
{
return findEnd(array, num) - findStart(array, num) + 1
}
1) Binary Search using Mid pointer until you find the value.
2) Once found, start moving left point to right by 1 and right pointer to left by 1 until the required number is found
3) To find the number of repetition, take difference between the left and right pointer indices.
/*
Given a sorted array, find a way to find the # of occurrence of a number
for eg: [1, 1, 2, 3, 3, 3, 4, 5]
find # of occurrence of 3 in time better than O(n)
*/
public class NumOfOccurence {
public static void main (String args[]) {
int[] a = {1, 2, 3, 3, 3, 3, 3, 4, 5};
for (int i = 0; i < 6; i++) {
int r = func(a, i);
System.out.println("i = " + i + " Rep: " + r);
}
}
public static int func (int[] a, int n) {
if (a.length == 0)
return -1;
int low = 0;
int high= a.length - 1;
int mid = (low + high) / 2;
while (mid > low && mid < high) {
if (a[mid] == n) {
while (a[low] != a[mid] && low != mid)
low = low + 1;
while (a[high] != a[mid] && high != mid)
high = high - 1;
if (low == high)
return 1;
else
return (high - low + 1);
} else if (a[mid] < n) {
low = mid;
mid = (low + high) / 2;
} else if (a[mid] > n) {
high = mid;
mid = (low + high) / 2;
}
}
// Case when n is present only at edges
if (a[low] == n || a[high] == n)
return 1;
return -1;
}
}
we can use binary search to find the most left and right positions of needle. Overall complexity O(logN)
- Darkhan.Imangaliev June 10, 2015