This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,
2. Implementation
Sorted array - a significant reminder to use binary search. This is O(logN) solution and use recursive implementation. Does this question remind you of something? Think about equal_range in STL.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <vector>
template <typename T>
void FindTheFirstOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,
const T& val,
const long start,
const long end,
size_t& first)
{
if (start > end) {
return;
}
const size_t mid = (start + end) >> 1;
auto iter = sortedArray.begin();
if (*(iter + mid) == val) {
// special case: hit the beginning of the array
// normal case: the left hand side has a smaller value
// otherwise continue binary search
if (mid == 0 || *(iter + mid - 1) < val) {
first = mid;
}
else {
FindTheFirstOfGivenNumberInSortedArray(sortedArray,
val,
start,
mid - 1,
first);
}
}
else {
FindTheFirstOfGivenNumberInSortedArray(sortedArray,
val,
mid + 1,
end,
first);
}
}
template <typename T>
void FindTheLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,
const T& val,
const size_t arr_len,
const long start,
const long end,
size_t& last)
{
if (start > end) {
return;
}
const size_t mid = (start + end) >> 1;
auto iter = sortedArray.begin();
if (*(iter + mid) == val) {
// special case: hit the end of array
// normal case: the right hand side has a larger value
// otherwise continue with binary search
if (mid == (arr_len - 1) || *(iter + mid + 1) > val) {
last = mid;
}
else {
FindTheLastOfGivenNumberInSortedArray(sortedArray,
val,
arr_len,
mid + 1,
end,
last);
}
}
else {
FindTheLastOfGivenNumberInSortedArray(sortedArray,
val,
arr_len,
start,
mid - 1,
last);
}
}
template <typename T>
bool FindTheFirstAndLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,
const T& val,
const size_t arr_len,
const long start,
const long end,
size_t& first,
size_t& last)
{
if (start > end) {
// does not find the given value
return false;
}
const size_t mid = (start + end) >> 1;
auto iter = sortedArray.begin();
if (*(iter + mid) == val)
{
// find the given value
if (mid == 0 || *(iter + mid - 1) < val) {
// hit the first occurrence
first = mid;
}
else {
// find the first occurrence in the left part of array
FindTheFirstOfGivenNumberInSortedArray(sortedArray,
val,
start,
mid - 1,
first);
}
if (mid == (arr_len - 1) || *(iter + mid + 1) > val) {
// hit the last occurrence
last = mid;
}
else {
// find the last occurrence in the right part of array
FindTheLastOfGivenNumberInSortedArray(sortedArray,
val,
arr_len,
mid + 1,
end,
last);
}
return true;
}
else if (*(iter + mid) > val) {
return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
val,
arr_len,
start,
mid - 1,
first,
last);
}
else
{
return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
val,
arr_len,
mid + 1,
end,
first,
last);
}
}
template <typename T>
bool FindTheFirstAndLastOfGivenNumberInSortedArray(const std::vector<T>& sortedArray,
const T& val,
size_t& first,
size_t& last)
{
if (sortedArray.empty()) {
return false;
}
const size_t len = sortedArray.size();
return FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
val,
len,
0,
len - 1,
first,
last);
}
// ********************************************************************************
// Test
// ********************************************************************************
#include <cassert>
void TestFindTheFistAndLastOfGivenNumberInSortedArray()
{
std::vector<int> sortedArray;
size_t first, last;
{
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
1,
first,
last) == false);
}
{
sortedArray = { 5 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
1,
first,
last) == false);
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 0);
}
{
sortedArray = { 5, 6 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 0);
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
6,
first,
last) == true);
assert(first == 1 && last == 1);
}
{
sortedArray = { 5, 5, 5, 5, 5 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 0 && last == 4);
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
6,
first,
last) == false);
}
{
sortedArray = { 1, 2, 3, 5, 5, 5, 5, 5, 6, 7, 8 };
assert(FindTheFirstAndLastOfGivenNumberInSortedArray(sortedArray,
5,
first,
last) == true);
assert(first == 3 && last == 7);
}
}
No comments:
Post a Comment