## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 6 vote

we can use binary search to find the most left and right positions of needle. Overall complexity O(logN)

Comment hidden because of low score. Click to expand.
0

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

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

You assume the number exists in the array. If the number does not exist then your upper and lowers bounds will not work

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

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

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

I think this solution is not O(logn) in case all the numbers are the same as the given number. it would be O(n) because of this line:
(1+numberOccurrence(sortedArray, number, a, pivot)+numberOccurrence(sortedArray, number, pivot+1, b));

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

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

Comment hidden because of low score. Click to expand.
0

This is O(n) average case

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

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;

Comment hidden because of low score. Click to expand.
0

You should update your hi and low variables in a separate branch when the pivot exactly equals the required number

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

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

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

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

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

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;

}

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

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

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

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

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

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

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

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

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

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)

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

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

}

}

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

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

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

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;

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

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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

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

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

Comment hidden because of low score. Click to expand.
0

*logn and not nlogn

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

int twoSum(vector<int> &nums, int target) {
int ans = 0;
for (int i=0; i<nums.size(); i++) {
int index = lower_bound(nums.begin()+i+1, nums.end(), target-nums[i])-nums.begin();
ans += nums.size()-index+1;
}
return ans;
}

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

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

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

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

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

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

}
}

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

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

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

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

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

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The algorithm is called "quick select".

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}
exit(1);
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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?

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

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.

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

Yes the point is you can do it in O(logN). As the question asks for better than O(N).
Binary search for an index such that A[j] == 3 and A[j-1] < 3 and then again for an index such that a[k] == 3 and a[k+1] > 3
return k-j+1;

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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

This is O(n) worst case (query number repeated n times)

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.