This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,
- a.ahmed.shalabey 6 days ago in United States for Software Development | Report Duplicate | Flag ".
2. Implementation
The idea is quite simple that check each element if it is a Fibonacci number. If yes, append the Fibonacci number into one list otherwise append the number into another list.
In this implementation the newly introduced feature "std::function" is used to pass a predicate (a function that take the template type as the argument and return bool) as the parameter. And implement a predicate to tell if an number is Fibonacci number, which is passed into the linked-list split function. Literally this implementation can take any predicate to split the linked list into two parts, not necessarily only Fibonacci and non-Fibonacci.
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <functional>
template <typename T>
void LL_SpiltLinkedList(LinkedListElement<T>** input,
LinkedListElement<T>** splitOnTrue,
LinkedListElement<T>** splitOnFalse,
std::function<bool (const T&)> func)
{
if (input == nullptr || *input == nullptr) {
return;
}
LinkedListElement<T>* curNode = *input;
LinkedListElement<T>* nodesOnTrue = nullptr;
LinkedListElement<T>* nodesOnFalse = nullptr;
while (curNode) {
if (func(curNode->data)) {
if (*splitOnTrue == nullptr) {
*splitOnTrue = curNode;
nodesOnTrue = *splitOnTrue;
}
else {
nodesOnTrue->next = curNode;
nodesOnTrue = nodesOnTrue->next;
}
}
else {
if (*splitOnFalse == nullptr) {
*splitOnFalse = curNode;
nodesOnFalse = *splitOnFalse;
}
else {
nodesOnFalse->next = curNode;
nodesOnFalse = nodesOnFalse->next;
}
}
curNode = curNode->next;
}
if (nodesOnTrue) {
nodesOnTrue->next = nullptr;
}
if (nodesOnFalse) {
nodesOnFalse->next = nullptr;
}
*input = nullptr;
}
bool IsFibonaciNumber(int val)
{
int temp = 5 * val*val;
int root = static_cast<int>(sqrt(temp - 4));
if (root*root == (temp - 4)) {
return true;
}
root = static_cast<int>(sqrt(temp + 4));
if (root*root == (temp + 4)) {
return true;
}
return false;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestSplitLLAgainstFibonaci()
{
{
LinkedListElement<int>* head = nullptr;
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes == nullptr);
}
{
std::vector<int> testArr = { 0, 1, 1, 2, 3, 5, 8 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes == nullptr);
assert(head == nullptr);
std::vector<int> result;
LL_CopyDataToStdVector(fibonaciNodes, result);
assert(testArr == result);
LL_Delete(&fibonaciNodes);
}
{
std::vector<int> testArr = { 4, 6, 7, 9, 10 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes == nullptr);
assert(nonFibonaciNodes != nullptr);
assert(head == nullptr);
std::vector<int> result;
LL_CopyDataToStdVector(nonFibonaciNodes, result);
assert(testArr == result);
LL_Delete(&nonFibonaciNodes);
}
{
std::vector<int> testArr = { 0, 4, 1, 6, 1, 7, 2, 9, 3, 10, 5, 8 };
std::vector<int> fibonaciArr = { 0, 1, 1, 2, 3, 5, 8 };
std::vector<int> nonFibonaciArr = { 4, 6, 7, 9, 10 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
LinkedListElement<int>* fibonaciNodes = nullptr;
LinkedListElement<int>* nonFibonaciNodes = nullptr;
LL_SpiltLinkedList<int>(&head, &fibonaciNodes, &nonFibonaciNodes, IsFibonaciNumber);
assert(fibonaciNodes != nullptr);
assert(nonFibonaciNodes != nullptr);
assert(head == nullptr);
std::vector<int> fibonaciResult;
LL_CopyDataToStdVector(fibonaciNodes, fibonaciResult);
assert(fibonaciArr == fibonaciResult);
std::vector<int> nonFibonaciResult;
LL_CopyDataToStdVector(nonFibonaciNodes, nonFibonaciResult);
assert(nonFibonaciArr == nonFibonaciResult);
LL_Delete(&fibonaciNodes);
LL_Delete(&nonFibonaciNodes);
}
}
No comments:
Post a Comment