c*****t
发帖数: 1879 | 1 I was interviewing for a principle software engineer / architect
position. The manager also gave me an offline interview question.
I did not give it much thought and sent the solution back. Then
I googled the problem afterward. It was the same as this one.
https://github.com/deepsolo9/interview/tree/master/amazon
The solution there was very bad. Obvious problems you can spot:
1. macros should not be defined in the header file. These macros are
strickly for the implementation, and not for the outsider to see.
2. too many comparisons inside the loop.
You could easily fail the interview using that solution.
If you look beyond just coding for interview, this is actually a
great problem, since it is a little challenging to write code very
efficiently and elegantly.
Here is my solution. There are a bit formatting issues (i.e. tab),
but you can fix it yourself.
If you think yours is better, then post yours :)
/**
* Search a sorted int array from the beginning of the array.
*
* @param nItems(IN)
* # of items in items
* @param items(IN)
* a sorted integer array
* @param op
* comparison operator
* @param value(IN)
* the search value
* @param foundIndex(OUT)
* the index of the found value
*/
#define SearchFromStart(nItems,items,op,value,foundIndex) do { \
int i; \
for (i = 0; i < (nItems) && (items)[i] op (value); ++i) \
{ \
(foundIndex) = i; \
} \
} while (0)
/**
* Same as SearchFromStart, just from the end of the array. Same parameters.
*/
#define SearchFromEnd(nItems,items,op,value,foundIndex) do { \
int i; \
for (i = (nItems) - 1; i >= 0 && (items)[i] op (value); --i) \
{ \
(foundIndex) = i; \
} \
} while (0)
/**
* A macro based linear search
*
* @param start(IN)
* a non-zero value indicates that we should search from
* the start of the array. 0 means from the back of the array.
* @param nItems(IN)
* # of items in items
* @param items(IN)
* a sorted integer array
* @param op
* comparison operator
* @param value(IN)
* the search value
* @param foundIndex(OUT)
* the index of the found value
*/
#define FastSearch(start,nItems,items,op,value,foundIndex) do { \
if (start) \
SearchFromStart(nItems,items,op,value,foundIndex); \
else \
SearchFromEnd(nItems,items,op,value,foundIndex); \
} while (0)
SearchResult Search(
const int * const items,
const int n_items,
const int ascending,
const int key,
const SearchType type,
int* const index)
{
int quickIndex = -1; /* a negative value means not found */
SearchResult result;
switch (type)
{
case LessThan:
{
FastSearch(ascending, n_items, items, <, key, quickIndex);
result = (quickIndex < 0 ? NotFound : FoundLess);
break;
}
case LessThanEquals:
{
FastSearch (ascending, n_items, items, <=, key, quickIndex);
result = (quickIndex < 0 ? NotFound : (items[quickIndex] < key ?
FoundLess : FoundExact));
break;
}
case Equals:
{
/* we use LessThanEquals comparison to do the search, and verify
* the result needs to be equals.
*/
FastSearch (ascending, n_items, items, <=, key, quickIndex);
result = (quickIndex < 0 ? NotFound : (items[quickIndex] == key
? FoundExact : NotFound));
break;
}
case GreaterThanEquals:
{
/* the search direction is reversed of ascending value */
FastSearch (!ascending, n_items, items, >=, key, quickIndex);
result = (quickIndex < 0 ? NotFound : (items[quickIndex] > key ?
FoundGreater : FoundExact));
break;
}
case GreaterThan:
{
/* the search direction is reversed of ascending value */
FastSearch(!ascending, n_items, items, >, key, quickIndex);
result = (quickIndex < 0 ? NotFound : FoundGreater);
break;
}
default:
{
result = NotFound;
break;
}
}
if (result != NotFound)
{
*index = quickIndex;
}
return result;
} |
|
