Bloomberg LP Interview Question
Financial Software Developerswhat kind of functionalities does the dataset have?
if you access element outside bounds, can it be handled properly?
are the elements ordered in the dataset?
what is the retrieval method? direct indexing or something else?
it didn't get that involved because I only know a little programming, so it was more of just the general idea of how it would work. I had said binary search but couldn't figure out how to do it with no bounds. His hint was selecting bounds, but I couldn't think of way to choose bounds that would contain the required datapoint. Dataset is considered to be ordered though.
Assumption: If index out of array the exception is caught are returns -1.
BSUnknown(A[],left,right,number)
{
while(A[right]<number && A[right]!=-1)
{
left=right;
right= right*2;
}
if(A[right]==-1)
{
while(A[right]!=-1)
right--;
}
if(A[right]>=number)
BinarySearch(A[],left,right,number)
}
I will go with sequential search because the dataset may not be sorted and we don't know the length of it.
- Karthik December 13, 2010- If length is known and sorted, then go for Binary search.
- If length is known and not sorted, use quick sort on the data set and binary search.