Sunday, 1 November 2015

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

1. Problem Description

- 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