LinkedList - Split Linked List into Fibonacci and Non-Fibonacci Lists (Amazon Interview Question)

1. Problem Description

This is an Amazon interview question for software develop engineer from careercup. Here is the original thread,

"

Given a linkedlist, write an algorithm to divide the linkedlist into two linkedlists, the first contains the Fibonacci numbers in the list and the second contains the non-Fibonacci numbers. 

Test the algorithm after developing the code

- 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);

    }

}