Hey, I was applying for a position, and they asked me to complete a coding problem for them. I did so and submitted it, but I later found out I was rejected from the position. Anyways, I have an eclectic programming background so I'm not sure if my code is grossly wrong or if I just didn't have the best solution out there. I would like to post my code and get some feedback about it. Before I do, here's a description of a problem:
You are given a sorted array of integers, say, {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13 }. Now you are supposed to write a program (in C or C++, but I chose C) that prompts the user for an element to search for. The program will then search for the element. If it is found, then it should return the first index the entry was found at and the number of instances of that element. If the element is not found, then it should return "not found" or something similar. Here's a simple run of it (with the array I just put up):
Enter a number to search for: 4
4 was found at index 2.
There are 2 instances for 4 in the array.
Enter a number to search for: -4.
-4 is not in the array.
They made a comment that my code should scale well with large arrays (so I wrote up a binary search). Anyways, my code basically runs as follows: Prompts user for input. Then it checks if it is within bounds (bigger than a[0] in the array and smaller than the largest element of the array). If so, then I perform a binary search. If the element is found, then I wrote two while loops. One while loop will count to the left of the element found, and the second while loop will count to the right of the element found. The loops terminate when the adjacent elements do not match with the desired value.
EX: 4, 4, 4, 4, 4
The bold 4 is the value the binary search landed on. One loop will check to the left of it, and another loop will check to the right of it. Their sum will be the total number of instances of the the number four.
Anyways, I don't know if there are any advanced techniques that I am missing or if I just don't have the CS background and made a big error. Any constructive critiques would be appreciated!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
/* function prototype */
int get_num_of_ints( const int* arr, size_t r, int N, size_t* first, size_t* count );
int main()
{
int N; /* input variable */
int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* array of sorted integers */
size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
size_t first; /* first match index */
size_t count; /* total number of matches */
/* prompts the user to enter input */
printf( "\nPlease input the integer you would like to find.\n" );
scanf( "%d", &N );
int a = get_num_of_ints( arr, r, N, &first, &count );
/* If the function returns -1 then the value is not found. Else it is returned */
if( a == -1)
printf( "%d has not been found.\n", N );
else if(a >= 0){
printf( "The first matching index is %d.\n", first );
printf( "The total number of instances is %d.\n", count );
}
return 0;
}
/* function definition */
int get_num_of_ints( const int* arr, size_t r, int N, size_t* first, size_t* count )
{
int lo=0; /* lower bound for search */
int m=0; /* middle value obtained */
int hi=r-1; /* upper bound for search */
int w=r-1; /* used as a fixed upper bound to calculate the number of right instances of a particular value. */
/* binary search to find if a value exists */
/* first check if the element is out of bounds */
if( N < arr[0] || arr[hi] < N ){
m = -1;
}
else{ /* binary search to find a value, if it exists, within given parameters */
while(lo <= hi){
m = (hi + lo)/2;
if(arr[m] < N)
lo = m+1;
else if(arr[m] > N)
hi = m-1;
else if(arr[m]==N){
m=m;
break;
}
}
if (lo > hi) /* if it doesn't we assign it -1 */
m = -1;
}
/* If the value is found, then we compute the left and right instances of it */
if( m >= 0 ){
int j = m-1; /* starting with the first term to the left */
int L = 0; /* total number of left instances */
/* while loop computes total number of left instances */
while( j >= 0 && arr[j] == arr[m] ){
L++;
j--;
}
/* There are six possible outcomes of this. Depending on the outcome, we must assign the first index variable accordingly */
if( j > 0 && L > 0 )
*first=j+1;
else if( j==0 && L==0)
*first=m;
else if( j > 0 && L==0 )
*first=m;
else if(j < 0 && L==0 )
*first=m;
else if( j < 0 && L > 0 )
*first=0;
else if( j=0 && L > 0 )
*first=j+1;
int h = m + 1; /* starting with the first term to the right */
int R = 0; /* total number of right instances */
/* while loop computes total number of right instances */
/* we fixed w earlier so that it's value does not change */
while( arr[h]==arr[m] && h <= w ){
R++;
h++;
}
*count = (R + L + 1); /* total number of instances stored as value of count */
return *first; /* first instance index stored here */
}
/* if value does not exist, then we return a negative value */
else if( m==-1)
return -1;
}
