## Linkedin Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

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

The binary search will work like like this:
a. First find the start index of the number
b. Then find its end index
c. Thus we have find the start and the end index

``````#include <stdio.h>
#include <conio.h>

int firstIndex(int arr[],int low,int high,int key,int n)
{

if(high>=low)
{
int mid=low+(high-low)/2;
if((mid==0||key>arr[mid-1])&&arr[mid]==key)
return mid;
else if(arr[mid]<key)
return firstIndex(arr,mid+1,high,key,n);
else
return firstIndex(arr,low,mid-1,key,n);
}
return -1;
}
int lastIndex(int arr[],int low,int high,int key,int n)
{
if(high>=low)
{
int mid=low+(high-low)/2;
if( ( mid == n-1 || key < arr[mid+1]) && arr[mid] == key )
return mid;
else if(key < arr[mid])
return lastIndex(arr, low, (mid -1), key, n);
else
return lastIndex(arr, (mid + 1), high, key, n);
}
return -1;
}
int main()
{
int arr[]={1,2,2,2,3};
int n=sizeof(arr)/sizeof(arr[0]);
int fi=firstIndex(arr,0,n-1,2,n);
int si=lastIndex(arr,fi,n-1,2,n);
printf(" The first and last indices are %d %d ",fi,si);
}``````

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

There is a lot of redundancy in the code, you can combine the logic and use it in one method.

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

``````class BinarySearch{

public static void main (String []args){

int []a = {0,0,2,3,3,3,3,4,7,7,9};
int result[] = binarySearchModified(a,3);
System.out.println("{" + result[0] +"," + result[1] +"}");
result = binarySearchModified(a,5);
System.out.println("{" + result[0] +"," + result[1] +"}");

}

// The idea is to return an array containing two elements with lowerIndex and higherIndex
public static int[] binarySearchModified(int []input, int target){

int low =0, high=input.length-1,mid, highIndex;
int result[] ={-1,-1};

while(low<=high){
mid = low + (high-low)/2;

if(target == input[mid]){  // Once the target is reached, just check for the range
highIndex = mid;
while( mid!=0 && target == input[mid-1]) //loop over until target repeats, thereby finding higher index
mid--;
result[0] = mid;
while( highIndex != input.length-1 && target == input[highIndex+1] )
highIndex++;
result[1] = highIndex;

return result; //Return the result

}

if(target > input[mid])
low = mid+1;
else if(target < input[mid])
high = mid-1;

}

}
}``````

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

@Sriram:
Your method has O(n) worst case time complexity. <All elements of array having the key element.>
Whereas the binary search method guarantees less than O(n) complexity even for this worst case.

Thank you

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

``````public static int[] findBinarySearch(int[] input, int target){
int start = -1;
int end = -1;
int[] result = {start, end};
int low = 0;
int high = input.length -1;
while(low <= high){
int mid =  (low + high)/2;
if(input[mid] == target){
while(input[mid] == target ){
mid --;
}
start = mid + 1;
mid++;
while(input[mid] == target){
mid ++;
}
end = mid - 1;
result[0] = start;
result[1] = end;
return result;
}

if(target > input[mid]){
low = mid + 1;
}else{
high = mid -1;
}
}
return result;
}``````

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

I'm new to this community. I see the answers were down voted but couldnt get the reason. When down voting, wouldn't they describe why it was down voted?

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

Yes never i could also not determine the reason for down voting despite the fact that they are right answers.

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

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

hey guys...what about if u want to search for 3.....u
Use binary search to find 3.5 and 2.5..(Since this is integer array)..
And u would end up at start(-1) and end(+1) of where '3' is !!! ??

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

CAN ANYONE THINK OF THIS ??????????????????

what about if u want to search for 3.....u
Use binary search to find 3.5 and 2.5..(Since this is integer array)..
And u would end up at start(-1) and end(+1) of where '3' is !!! ??

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

``````//If the element is not present in the array I printed that array is not present rather printing -1 -1 , it's an easy thing to change
/*Given a sorted integer array and a number, find the start and end indexes of the number in the array.

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

Complexity should be less than O(n)
Developed by : Suman Roy
Email: email.suman.roy@gmail.com

*/

#include<iostream>
#include<stdlib.h>
using namespace std;
int MAX,MIN;
bool flag1=false;
bool flag2=false;
void Search(int *array , int i_start , int i_end , int i_search){
if ( flag1 & flag2 )
exit( EXIT_SUCCESS);
//	std::cout<<"start ="<<i_start<<"end ="<<i_end<<std::endl;
int i_mid= ( i_start+i_end ) /2;
//	std::cout<<"Mid= "<<i_mid<<":"<<array[i_mid]<<std::endl;
if ( array[i_mid ] == i_search) {
if ( ( array [ i_mid - 1 ] !=i_search  || i_mid==0 ) & !flag1 ){
std::cout<<"left_index= "<< i_mid<<std::endl;
flag1=true;
Search( array , i_mid + 1 , MAX , i_search );
std::cout<<"Rightindex = "<<i_mid<<std::endl;
flag2=true;
exit(EXIT_SUCCESS);
return ;
} if( !flag1 ){ Search ( array , MIN ,i_mid -1 , i_search ); }
if ( (array [ i_mid +1 ] !=i_search || i_mid == MAX ) & !flag2){
std::cout<<"right_index= "<<i_mid<<std::endl;
flag2=true;
Search ( array , MIN , i_mid-1 , i_search ) ;
std::cout<<"Left index="<<i_mid<<std::endl;
flag1=true;
exit(EXIT_SUCCESS);
return ;
}
if( !flag2 ){ Search ( array , i_mid + 1 , MAX , i_search );}

}
if( ( * ( array + i_mid ) >i_search )){
if( i_mid-1 >= i_start ){
MAX=i_mid-1;

Search ( array , i_start , i_mid-1 , i_search ) ;
}
}

else{
if( * ( array + i_mid ) < i_search  ){
if( i_mid + 1 <=i_end ){
MIN=i_mid+1;
Search( array , i_mid + 1 ,i_end , i_search );
}
}
}
}

int main(){
int i_search;
MIN=0;
MAX=11;//no of elements in array
int array[]={0,0,2,3,3,3,3,3,4,7,7,9};
std::cout<<"enter the element\n";
std::cin>>i_search;
Search ( array , MIN ,MAX  , i_search );
std::cout<<"Element not present\n";
}``````

Out Put:

``````suman@suman-laptop:/media/D/coding/algo/search\$ ./a.out
enter the element
1
Element not present
suman@suman-laptop:/media/D/coding/algo/search\$ ./a.out
enter the element
0
left_index= 0
right_index= 1
suman@suman-laptop:/media/D/coding/algo/search\$ ./a.out
enter the element
2
left_index= 2
Rightindex = 2
suman@suman-laptop:/media/D/coding/algo/search\$ ./a.out
enter the element
3
left_index= 3
right_index= 7
suman@suman-laptop:/media/D/coding/algo/search\$``````

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

Use an ArrayList provided in the java.util library. Retrieval/Search in an ArrayList is an O(1) operation in terms of complexity.
You can then use the indexOf and lastIndexOf methods to find an element if present, else return -1, -1 combination.

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

You can simply use an ArrayList and it's associated methods.
Search/retreival is an O(1) complexity operation which is very efficient in this case.

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

public static void FindIndex(int[] arr, int findNumber)
{
int count = 0;
foreach (int i in arr)
{
if (i == findNumber)
{ count++; }
}
if (count == 0)
{
Console.WriteLine("Output = {-1,-1}");
}
else
{
for (int i = 0; i < arr.Length; i++)
{
while (findNumber == arr[i])
{
Console.WriteLine("Output = {"+i+","+(i+count-1)+"}");
return;
}
}
}

}

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

``````I see very big length of codes here... I always try to simplify the procedure as much as possible. This codes seems to be working fine.

#include <iostream>
using namespace std;

#define MAX 5
int index[2], i;

void functionIndexFind(int arr[MAX], int num) {
bool chk = false;
for (i=0; i<MAX; i++)
{
if((arr[i]==num) && (chk==false)) {
index[0] = i+1;
chk = true;
}
if((arr[i]==num) && (chk==true)) {
index[1] = i+1;
}
else
continue;
}
}

int main(){
int array[MAX] = {2,3,4,8,2};
functionIndexFind(array, 2);
cout << index[0] << index[1];
return 0;
}``````

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

The required complexity is less than O(n).

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

Algorithm:

1) Find occurrence of the key using binary search
2) As soon as you find this occurrence, mark the last array (indices) where you found this first occurrence > Let us call this a subarray. To make it clear, subarray is the array that we found the key, that means subarray[mid] = key.
3) No do again a binary search in the first half of this array to find the first occurrence of the key.
4) Do a binary search, similar to #3 to find the last index.

Here is the code in java:

``````public class FirstAndLastIndex {
private static int intr_f_index,intr_l_index,key;
public static void main(String args[]){
int[] inparray = {1,2,4,6,6,6,6,6,6,7,12,14,14,14,14,14,14,14,14,14,14,14,14,300};
int index,firstindex,lastindex,arrfindex,arrlindex,n;
key = 14;
n = inparray.length;
arrfindex = 0;
arrlindex = n-1;
index = binarySearchIndex(inparray,arrfindex,arrlindex);
if(index == -1){
firstindex =-1;
lastindex =-1;
System.out.println("{"+firstindex+","+lastindex+"}");
}
else{
firstindex = binarySearchFirstIndex(inparray,intr_f_index,index);
lastindex = binarySearchLastIndex(inparray,index,intr_l_index);
System.out.println("{"+firstindex+","+lastindex+"}");
}
}
private static int binarySearchIndex(int[] inparr, int findex, int lindex){
int mid = findex+(lindex-findex)/2;
if(findex == lindex && inparr[findex]!=key)
return -1;
if(inparr[mid] == key){
intr_f_index=findex;
intr_l_index=lindex;
return mid;
}
else if(inparr[mid] > key){
return binarySearchIndex(inparr,findex,mid-1);
}
else{
return binarySearchIndex(inparr,mid+1,lindex);
}
//return -1;
}
private static int binarySearchFirstIndex(int[] inparr,int findex,int lindex){
if(findex == lindex)
return findex;
int mid = findex+(lindex-findex)/2;
if(inparr[mid] == key){
return binarySearchFirstIndex(inparr,findex,mid);
}
else{
return binarySearchFirstIndex(inparr,mid+1,lindex);
}
}
private static int binarySearchLastIndex(int[] inparr, int findex, int lindex){
int mid;
if(findex == lindex)
return findex;
mid = findex+(lindex-findex)/2+1;
if(inparr[mid] == key){
return binarySearchLastIndex(inparr,mid,lindex);
}
else{
return binarySearchLastIndex(inparr,findex,mid-1);
}
}
}``````

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

``````int count(vector<int>&a, int key)
{
return std::distance( a.upper_bound(a.begin(), a.end(), key) - a.lower_bound(a.begin(), a.end(), key) )
}
/``````

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

1) First find the index of the element by using binarySearch
2) If index find by binary Search is not equal to -1 i.e. element is found then
a) Recursively find the first occurrence of element in array[start, binarySearchIndex]
b) Recursively find the last occurrence of element in array[binarySearchIndex, end]

``````public static int firstOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}

if (start == end & key == a[start])
{
return start;
}

int middle = (start + end) / 2;
if (key == a[middle])
{
return firstOccurance(a, start, middle, key);
}
else
{
return firstOccurance(a, middle + 1, end, key);
}
}

public static int lastOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}

if (start == end & key == a[start])
{
return start;
}

int middle = (start + end) / 2 + 1;
if (key == a[middle])
{
return lastOccurance(a, middle, end, key);
}
else
{
return lastOccurance(a, start, middle - 1, key);
}
}

public static int binarySearch(int[] a, int start, int end, int key)
{
if (end < start)
{
return -1;
}

int middle = (start + end) / 2;

if (key == a[middle])
{
return middle;
}
else if (key > a[middle])
{
return binarySearch(a, middle + 1, end, key);
}
else
{
return binarySearch(a, start, middle - 1, key);
}

}

public static int[] findRangeBinarySearch(int[] a, int key)
{
int[] result = { -1, -1 };

int binIndex = binarySearch(a, 0, a.length, key);
if (binIndex != -1)
{
result[0] = firstOccurance(a, 0, binIndex, key);
result[1] = lastOccurance(a, binIndex, a.length - 1, key);
}
return result;
}``````

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

What about if you’re just trying to count the number of occurrence of key in a, from start to end? It’s for a project, and it’s using the same thing.

static int count(int[] a, int key, int start, int end)

Any ideas?

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

``````private static void findFistAndLastIndex(int[] array, int key) {
int low = 0;
int high = array.length - 1;
int firstIndex = -1;
int lastIndex = -1;
while (low < high ) {
int mid =  low +  (high - low)/ 2;
if (array[mid] < key) {
low = mid + 1;
} else if (array[mid] > key) {
high = mid - 1;
} else {
firstIndex = findFirstIndex(array, low, mid);
lastIndex = findLastIndex(array, mid, high);
break;
}
}
System.out.println(firstIndex);
System.out.println(lastIndex);
}

private static int findFirstIndex(int[] array, int low, int high) {
int index = high;
int key = array[high];
while (low < high) {
int mid = low + (high - low )/2;
if (array[mid] == key) {
index = mid;
high = mid - 1;
} else if (array[mid] < key) {
low = mid + 1;
}
if (array[low] == key) {
index = low;
break;
}
}
return index;
}

private static int findLastIndex(int[] array, int low, int high) {
int index = low;
int key = array[low];
while (low < high) {
int mid = low + (high - low )/2;
if (array[mid] == key) {
index = mid;
low = mid + 1;
} else if (array[mid] > key) {
high = mid -1;
}
if (array[high] == key) {
index = high;
break;
}
}
return index;
}``````

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

two binary search
1) left edge : array[pos] == target && array[pos -1] < target
2) right edge:array[pos] == target && array[pos -1] > target

``````static void Main(string[] args)
{
int[] array = { 1, 2, 3, 3, 3, 3, 3, 4, 5, 6 };

int target = 3;

Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, true));
Console.WriteLine(FindEdge(array, 0, array.Length - 1, target, false));
}

static int FindEdge(int[] array, int from, int to, int target, bool isLowerEdge)
{
int pos = from + (to - from) / 2;

if (pos == from && array[pos] >= target)
{
return -1;
}

if (pos == to - 1 && array[to] <= target)
{
return -1;
}

if (array[pos] == target && ((isLowerEdge && array[pos - 1] < target) || (!isLowerEdge && array[pos + 1] > target)))
{
return isLowerEdge ? pos - 1 : pos + 1;
}
else
{
if (array[pos] < target)
{
return FindEdge(array, pos + 1, to, target, isLowerEdge);
}
else if (array[pos] == target)
{
return Math.Max(FindEdge(array, from, pos, target, isLowerEdge), FindEdge(array, pos + 1, to, target, isLowerEdge));
}
else
{
return FindEdge(array, from, pos, target, isLowerEdge);
}
}
}``````

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

``````<?php
function fbinarysearch(\$inparray,\$target,\$start,\$end,\$ctr) {

echo "F COUNT:".\$ctr." START:".\$start." END:".\$end;

if(\$end>=\$start) {
\$mid = floor((\$start+\$end)/2);

echo " MID:".\$mid."\n";
\$ctr++;
if(\$inparray[\$mid] == \$target){
\$midprobe = fbinarysearch(\$inparray,\$target,\$start,\$mid-1,\$ctr);
if(\$midprobe == -1)
return \$mid;
else
return \$midprobe;
}
else if(\$inparray[\$mid] > \$target)
return fbinarysearch(\$inparray,\$target,\$start,\$mid-1,\$ctr);
else if(\$inparray[\$mid] < \$target)
return fbinarysearch(\$inparray,\$target,\$mid+1,\$end,\$ctr);
} else {
return -1;
}
}

function lbinarysearch(\$inparray,\$target,\$start,\$end,\$ctr) {

echo "L COUNT:".\$ctr." START:".\$start." END:".\$end;

if(\$end>=\$start) {
\$mid = ceil((\$start+\$end)/2);

echo " MID:".\$mid."\n";
\$ctr++;
if(\$inparray[\$mid] == \$target){
\$midprobe = lbinarysearch(\$inparray,\$target,\$mid+1,\$end,\$ctr);
if(\$midprobe == -1)
return \$mid;
else
return \$midprobe;
}
else if(\$inparray[\$mid] > \$target)
return lbinarysearch(\$inparray,\$target,\$start,\$mid-1,\$ctr);
else if(\$inparray[\$mid] < \$target)
return lbinarysearch(\$inparray,\$target,\$mid+1,\$end,\$ctr);
} else {
return -1;
}
}

\$inparray = array(1,2,3,4,4,4,4,4,4,4,4,5,6,7);
\$target = 4;
//TEST CASES
//\$target = 1;
//\$target = 7;
//\$target = 0;
//\$target = 10;
//\$inparray = array(1,2,3,3,4,4,4,4,4,4,4,5,6,7);
//\$target = 4;
//\$inparray = array(1,2,3,4,4,4,4,4,4,4,5,5,6,7);
//\$target = 4;
//\$inparray = array(4,4,4,4,4,4,4,4,4,4,4,4,4,4);
//\$target = 4;

\$len = sizeof(\$inparray);
echo "BINARY SEARCH POSITION: ".binarysearch(\$inparray,\$target,0,\$len-1,0)."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
\$first = fbinarysearch(\$inparray,\$target,0,\$len-1,0);
echo "\n\nFIRST BINARY SEARCH POSITION: ".\$first."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
if(\$first != -1) {
\$last = lbinarysearch(\$inparray,\$target,\$first,\$len-1,0);
echo "\n\nLAST BINARY SEARCH POSITION: ".\$last."\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
} else {
echo "\n\nLAST BINARY SEARCH POSITION: -1\n";
echo "\n++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
}

print_r(\$inparray);
?>``````

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

``````void calc_range(int *sorted_array, int start, int end, int x, int *range_start, int *range_end)
{
int start_1;
int end_1;
int start_2;
int end_2;
int mid;

start_1 = end_1 = start_2 = end_2 = -1;
mid = 0;

if(start <= end)
{
mid = (start+end)/2;
if(sorted_array[mid] == x)
{
*range_start = *range_end = mid;
if(start <= mid-1)
calc_range(sorted_array, start, mid-1, x, &start_1, &end_1);
if(mid+1 <= end)
calc_range(sorted_array, mid+1, end, x, &start_2, &end_2);
if(start_1 != -1)
*range_start = start_1;
if(end_2 != -1)
*range_end = end_2;
}
else if(x < sorted_array[mid])
{
if(start <= mid-1)
calc_range(sorted_array, start, mid-1, x, &start_1, &end_1);

*range_start = start_1;
*range_end = end_1;
}
else
{
if(mid+1 <= end)
calc_range(sorted_array, mid+1, end, x, &start_2, &end_2);

*range_start = start_2;
*range_end = end_2;
}
}
}``````

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

How abut this in Java as it should be O(n) complexity.

``````public class FindStartEndNumberIndex {

public static void main(String[] args) {

int[] Array = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };

findIndex(Array, 3);
findIndex(Array, 5);
}

static void findIndex(int[] array, int number) {
int startIndex = -1, endIndex = -1;

for(int i = 0; i < array.length; i++) {

if(array[i] == number) {
if(startIndex < 0) {
startIndex = i;
}
endIndex = i;
}
}

System.out.printf("{%d,%d}\n", startIndex, endIndex);
}
}``````

Output:

{3,6}
{-1,-1}

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

{{

#include <stdio.h>
#include <string.h>

/*
Given a sorted integer array and a number, find the start and end indexes of the number in the array.

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

Complexity should be less than O(n)
*/

int binarySearchFirst(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] < key ) {
l = m + 1;
} else {
r = m - 1;
}
}
if( arr[l] == key )
return l;
else
return -1; // Not in array
}

int binarySearchLast(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] <= key ) {
l = m + 1;
} else {
r = m - 1;
}
}
if( arr[r] == key )
return r;
else
return -1; // Not in array
}

void findIndicies(int *arr, int size, int num, int *start, int *end) {
*start = binarySearchFirst(arr, size, num);
*end = binarySearchLast(arr, size, num);
}

main()
{
int start = -1, end = -1;
int arr[] = {0,0,2,3,3,3,3,4,7,7,9};
findIndicies(arr, sizeof(arr)/sizeof(arr[0]), 9, &start, &end);
printf("start: %d end: %d", start, end);
}

}}

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

This program is simple and efficient. It does not handle boundary case when the key is not in the array. l/r in binarySearchFirst()/binarySearchLast() respectively could be out of bound (for example arr = {1, 1, 1}). Here is a corrected program (also taking care of indentation for clarity):

The (minor) correction is commented out. The test program illustrates the problem by printing l/r before the final compare with key.

``````#include <stdio.h>
#include <string.h>

/*
Given a sorted integer array and a number, find the start and end indexes of the number in the array.

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}

Complexity should be less than O(n)
*/

int binarySearchFirst(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] < key ) {
l = m + 1;
} else {
r = m - 1;
}
}

printf("l = %d\n", l);
if( /*l < size &&*/ arr[l] == key )
return l;
else
return -1; // Not in array
}

int binarySearchLast(int *arr, int size, int key ) {
int r = size-1;
int l = 0;
while( l <= r ) {
int m = (l+r)/2;
if( arr[m] <= key ) {
l = m + 1;
} else {
r = m - 1;
}
}

printf("r = %d\n", r);
if( /*r >= 0 &&*/ arr[r] == key )
return r;
else
return -1; // Not in array
}

void findIndicies(int *arr, int size, int num, int *start, int *end) {
*start = binarySearchFirst(arr, size, num);
*end = binarySearchLast(arr, size, num);
}

main()
{
int start = -1, end = -1;
int arr[] = {1, 1, 1};
findIndicies(arr, sizeof(arr)/sizeof(arr[0]), 3, &start, &end);
printf("start: %d end: %d\n", start, end);
int arr1[] = {4, 4, 4};
findIndicies(arr1, sizeof(arr1)/sizeof(arr1[0]), 3, &start, &end);
printf("start: %d end: %d\n", start, end);
}``````

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

``````public static int StartIndex(int[] arr, int target){
return StartIndex(arr,target, 0, arr.length-1);
}

public static int StartIndex(int[] arr, int target, int start, int end){
if (start>end) return -1;
if (start==end){
if (arr[start]==target) return start;
else return -1;
}
if (end==start+1){
if (arr[end]==target && arr[start]!=target) return end;
else return -1;
}

int mid = (start+end)/2;

if (arr[mid]<target){
return StartIndex(arr,target,mid,end);
}
else{  //>=
return StartIndex(arr,target,start,mid);
}
}

public static int EndIndex(int[] arr, int target){
return EndIndex(arr,target, 0, arr.length-1);
}

public static int EndIndex(int[] arr, int target, int start, int end){
if (start>end) return -1;
if (start==end){
if (arr[start]==target) return start;
else return -1;
}
if (end==start+1){
if (arr[end]!=target && arr[start]==target) return start;
else if (arr[end]==target && end==arr.length-1) return end;
else return -1;
}

int mid = (start+end)/2;

if (target>=arr[mid]){
return EndIndex(arr,target,mid,end);
}
else{  //>=
return EndIndex(arr,target,start,mid);
}
}``````

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

``````public class Solution {

public static int[] searchRange(int[] A, int target) {
int[] ret = {Integer.MAX_VALUE, Integer.MIN_VALUE};
rec(A, target, ret, 0, A.length-1);
if(ret[0] == Integer.MAX_VALUE){
ret[0] = -1;
}
if(ret[1] == Integer.MIN_VALUE){
ret[1] = -1;
}
return ret;
}

public static void rec(int[] A, int target, int[] ret, int low, int high){
if(low > high){
return;
}

int mid = low + (high-low)/2;
if(target == A[mid]){
ret[0] = Math.min(ret[0], mid);
ret[1] = Math.max(ret[1], mid);
rec(A, target, ret, low, mid-1);
rec(A, target, ret, mid+1, high);
}else if(target < A[mid]){
rec(A, target, ret, low, mid-1);
}else{
rec(A, target, ret, mid+1, high);
}
}

}``````

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

//Time Complexity: O(n)

``````ArrayList<Integer> findStartEnd(ArrayList<Integer> a, k){

ArrayList<Integer> ret = new ArrayList<~>();
if(a.size() < 0) return ret;
if(a.size() == 1){
if(a[a.size()] == k){
return ret;
}
return ret;
}
boolean stop = false;
int itr = 0;
while(itr < a.size()){//check entire len
if(a[itr] == k){ //element found
if(!stop){//hitting first index
stop = true;
}
}
else {
if(stop){
stop = false;
}
}
itr++;
}
return ret;
}``````

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

``````public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{
System.out.println(mid);
int r=1;

findex=mid;

while(low<(mid-r))
{
int z =  fbinarySearch(a, key,low,mid-r);
if (z== -1)  {return findex ; }
else {r++;

}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}

public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{
System.out.println(mid);
int r=1;

lindex=mid;

while(high>(mid+r))
{
int z =  lbinarySearch(a, key,mid+r,high);
if (z== -1)  {return lindex ; }
else {r++;

}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;

for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}``````

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

this is a simple an easy to find solution :
2 different calls of binary search fr each index :

on locating key , check its left subarray for key again recursively to get findex
check right subarray for key recursively to get last index

``````public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{

int r=1;

findex=mid;

while(low<(mid-r))
{
int z =  fbinarySearch(a, key,low,mid-r);
if (z== -1)  {return findex ; }
else {r++;

}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}

public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{

int r=1;

lindex=mid;

while(high>(mid+r))
{
int z =  lbinarySearch(a, key,mid+r,high);
if (z== -1)  {return lindex ; }
else {r++;

}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;

for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}``````

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

better solution :

find mid of key
check left subarray for occurences of key , if present , repeat till not present :mid of the prev iteration (2nd last ) is startindex

same for righ subarray and lastindex

``````public class BinarySearch
{
public static final int NOT_FOUND = -1;
public static int findex;
public static int lindex;
public static int fbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{

findex=mid;

while(low<(mid-1))
{
int z =  fbinarySearch(a, key,low,mid-1);
if (z== -1)  {return findex ; }
else {

mid=z;
}
}
}
else if (a[mid] < key)
return fbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return fbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}

public static int lbinarySearch(double[] a, double key, int low, int high)
{
int n=a.length;
int mid;

if (low<=high)
{
mid = low+(high-low) /2;

if  ((a[mid]==key))
{

lindex=mid;

while(high>(mid+1))
{
int z =  lbinarySearch(a, key,mid+1,high);
if (z== -1)  {return lindex ; }
else {
mid=z;

}
}
}
else if (a[mid] < key)
return lbinarySearch(a, key,mid+1,high);
else if (a[mid] > key)
return lbinarySearch(a, key,low,mid-1);

}
return NOT_FOUND;
}
public static void main(String[] args)
{
double key = 10.5, index;
double a[] ={2,3,10.5,10.5,10.5,10.5,10.5,10.5, 30.5};
int i;
int l = a.length;
int j;
int low=0;
int high = a.length-1;

for (i=0;i < l;i++)
{
System.out.println(a[i]);
}
int fi=0,fl=0;
fi =fbinarySearch(a, key,low, high) ;
fl =lbinarySearch(a, key,low, high) ;
System.out.println("Found " + key + " at " + fi + " to " + fl );
}
}``````

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

import java.util.Scanner;

public class StartAndEndIndexOfNumberInArray
{
public static void main(String args[])
{
int[] a = {0,0,2,3,3,3,3,4,7,7,9};
Scanner in = new Scanner(System.in);
System.out.println("Enter the number to be found: ");
int num = in.nextInt();
int low =0, high=0;

for(int i=0;i<a.length;i++)
{
if(a[i] == num)
{
low = i;
break;
}
else
low = -1;
}

for(int i=a.length - 1;i>=0;i--)
{
if(a[i] == num)
{
high = i;
break;
}
else
high = -1;
}

System.out.println("Low and High position of the number "+num+" is "+low+","+high);
}
}

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

public class StartAndEndIndexOfNumberInArray
{
public static void main(String args[])
{
int[] a = {0,0,2,3,3,3,3,4,7,7,9};
Scanner in = new Scanner(System.in);
System.out.println("Enter the number to be found: ");
int num = in.nextInt();
int low =0, high=0;

for(int i=0;i<a.length;i++)
{
if(a[i] == num)
{
low = i;
break;
}
else
low = -1;
}

for(int i=a.length - 1;i>=0;i--)
{
if(a[i] == num)
{
high = i;
break;
}
else
high = -1;
}

System.out.println("Low and High position of the number "+num+" is "+low+","+high);
}
}

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

Here is my Ruby solution:

``````#!/usr/bin/env ruby

class Array
def find_range_of_int(v)
i1 = self.find_index(v) || -1
i2 = i1 < 0 ? -1 : self.length - 1 - self.reverse.find_index(v)
[i1,i2]
end
end

a =
{
3 => [0,0,2,3,3,3,3,4,7,7,9],
5 => [0,0,2,3,3,3,3,4,7,7,9]
}
a.each_pair do |v,a|
i1,i2 = a.find_range_of_int(v)
puts "{#{i1},#{i2}}"
end``````

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

Here is my modified Ruby solution which executes with complexity less than O(n), in contrast to my previous posting:

``````#!/usr/bin/env ruby

class Array
def find_first(v,depth = 0,sign = 1)
n = self.length
p = (n/2.0).ceil - 1
return -1 if depth > 8
return p if self[p] == v && (n == 1 || self[p-1] != v)
return -1 if n == 1
i = self[0..p].find_first(v,depth + 1,sign)
return i if i >= 0
i = self[p+1..-1].find_first(v,depth + 1,sign)
return -1 if i < 0
r = p + 1 + i
return r
end

def find_last(v,depth = 0)
p = self.reverse.find_first(v,depth,sign = -1)
p = p < 0 ? p : self.length - 1 - p
return p
end

def find_range_of_int(v)
i1 = self.find_first(v)
i2 = self[i1+1..-1].find_last(v)
i2 = i2 < 0 ? i2 : i2 + i1 + 1
[i1,i2]
end
end

a =
{
3 => [0,0,2,3,3,3,3,4,7,7,9],
5 => [0,0,2,3,3,3,3,4,7,7,9]
}
a.each_pair do |v,a|
i1,i2 = a.find_range_of_int(v)
puts "a: #{a}, v: #{v} --> {#{i1},#{i2}}"
end``````

The output is as follows:

``````a: [0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9], v: 3 --> {3,6}
a: [0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9], v: 5 --> {-1,-1}``````

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

Comment out {{return -1 if depth > 8}} for use in practice.

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

Python 3:

def find_range(a, b):
counter = [i for i in range(len(a)) if a[i] == b]
start_index = counter[0]
end_index = counter[-1]
total = len(counter)

print("start index of " + str(b) + " --> " + str(start_index) + "; end index --> " + str(end_index) + ".")
return "start index of " + str(b) + " is " + str(start_index) + " and appears " + str(total) + " times."

result = find_range([1, 2, 2, 1, 1, 1, 4], 1)
print(result)

------------------------------
Result: start index of 1 --> 0; end index --> 5.
start index of 1 is 0 and appears 4 times.

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

``````public static void main(String[] args) {
int[] numbers = {0,1,1,1,1,1,1,1,1,1,1,1,1,1,2};
System.out.println(findLeftOccurance(numbers, 0, numbers.length-1, 1, -1, -1, -1));
}
public static int findLeftOccurance(int[] numbers, int i, int j, int number, int index, int indexLeft, int indexRight) {
int mid = i + (j - i) / 2;
if(i>j) {
return index;
}
if(numbers[mid] == number) {
index = mid;
}
if(number <= numbers[mid]) {
indexLeft = findLeftOccurance(numbers, i, mid - 1, number, index, indexLeft, indexRight);
}
if(number > numbers[mid]) {
indexRight = findLeftOccurance(numbers, mid + 1, j, number, index, indexLeft, indexRight);
}
return (indexLeft != -1 && indexRight != -1)?Math.min(indexLeft, indexRight):((indexLeft == -1)?indexRight:indexLeft);
}``````

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

Here's solution in python:

def getIndexOf(arr, y):
i =0
arr.sort()
while(i <= len(arr)):
if(y in arr):
indices = [i for i, x in enumerate(arr) if x == y]
print("Start Index :", min (indices),"End Index :",max(indices))
break
else:
print("Not in list")
print("Start Index :", -1 ,"End Index :",-1 )
break
return

arr = [0,2,3,3,3,10,10]
y = 6

getIndexOf(arr,y)

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

Use binary search to locate a given number in that number sequence. From that location, proceed both to the right and to the left until you see different numbers and mark the boundaries.

If the binary search is unable to find the given number, return -1,-1

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

I don't have the specifics right off the top of my head, but you'll want to do a modified binary search again once you are in the range. Searching linearly in each direction as you state should, if I am not mistaken, result in O(n) overall runtime, not the Sub O(n) the answer sought.

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

not required,i guess...suppose you found any one position of required value x in array using bsearch say k
now use this modified binary search in left side
low=0;high=k-1;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==x)
high=mid-1;
else low=mid+1
}
after this loop,the index value low will contain the first occurrence of x in array.
similarly you can search in other part for last occurrence too

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

Python:
If i can use inbuilt functions, below one would help answer your question?

``````def getindices(tlist, n):
indices = [-1,-1]
if tlist.count(n):
indices = map(lambda i: tlist.index(i[1], i[0]), \
enumerate([n] * tlist.count(n), tlist.index(n)))
indices = [indices[0], indices[-1]]
return indices

Testing:

>>> getindices([1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5], 4)
[8, 11]
>>> getindices([1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5], 11)
[-1, -1]
>>>``````

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

``````void search(int k, int start, int end, int &left, int &right, int a[])
{
if (start <= end)
{
int mid = end - ((end-start)>>1);
if(a[mid] == k)
{
if (left > mid)  left = mid;
if (right < mid) right = mid;
search(k, start, mid-1, left, right, a);
search(k, mid+1, end, left, right, a);
}
else if (a[mid] < k)
search(k, mid+1, end, left, right, a);
else
search(k, start, mid-1, left, right, a);

}
return;
}``````

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

public class ReturnIdx {
public static void main(String[] args) {
int arr[] = {-1, 0, 0, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6};

startAndEnd(arr,2);

}

private static void startAndEnd(int[] arr, int num) {

int stidx =getPos(arr,num);
int start = stidx;
if(stidx != -1){
int end = arr.length;
int mid;
while(start<=end){
mid = (start+end)/2;
if(arr[mid] < num){
start = mid+1;

}else if(arr[mid] > num){
end = mid - 1;

}
else {
if(start == end)
break;
else{

start = mid;

}

}
}
System.out.println("start: "+stidx+" end: "+end);
}
else{
System.out.println("The element does not exist");
}

}

static int getPos(int[] arr, int num) {
int start = 0;
int end = arr.length-1;
int mid;
while(start<=end){
mid = (start+end)/2;
if(arr[mid] < num){
start = mid+1;

}else if(arr[mid] > num){
end = mid - 1;

}
else {
if(start == end)
return start;
else{

end = mid;

}

}

}
return -1;
}

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

//Here is the simple solution in java.
public static void getStartEndIndex(int[] arr, int number) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == number) {
startIndex = i;
int j = i;
do {
j++;
} while (arr[j] == number);
endIndex = j - 1;
System.out
.println("Start and End Index of the given number is :"
+ startIndex + " and " + endIndex);
break;

}
}
}

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

This is an O(n) solution and the problem explicitly requires "Complexity should be less than O(n)".

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

Guaranteeing an O(n) solution is not possible, since you would need to iterate over all elements at least once in the case where the target value has no corresponding element present in the array.

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

I meant to say "[Guaranteeing less than O(n) complexity in the] solution...", as opposed to "[Guaranteeing an O(n)] solution..."

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

I was incorrect. If you know the length of the array (as opposed to an array buffer whose end is marked with a terminator), then you can use the binary search method to achieve O(log2(n)) without having to touch every element.

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.