No. 18 - Reverse a Linked List

Problem: Implement a function to reverse a linked list, and return the head of the reversed list. A list node is defined as below:

struct ListNode

{

       int       m_nKey;

       ListNode* m_pNext;

};

Analysis: Lots of pointer operations are necessary to solve problems related to linked lists. Interviewers know that many candidates are prone to make mistakes on pointer operations, so they like problems of linked list to qualify candidates’ programming abilities. During interviews, we had better analyze and design carefully rather than begin to code hastily. It is much better to write robust code with comprehensive analysis than write code quickly with many errors.

Direction of pointers should be adjusted in order to reverse a linked list. We may utilize figures to analyze visually the complex steps to adjust pointers. As shown in the list in Figure 1-a, node h, i and j are three adjacent nodes. Let us assume pointers of all nodes prior to h have been reversed after some operations and all m_pNext point to their previous nodes. We are going to reverse the m_pNext pointer in node i. The status of list is shown in Figure 1-b.

Figure 1: A list is broken when we reverse m_pNext pointers. (a) A linked list. (b) A link between node i and j is broken when all m_pNext pointers of node prior to node i point to their previous nodes.

It is noticeable that m_pNext in node i points to its previous node h, the list is broken and we cannot visit the node j anymore. We should save the node j before the m_pNext pointer of node i is adjusted to prevent the list becoming broken.

When we adjust the pointer in node i, we need to access to node h since m_pNext of node i is adjusted to point to node h. Meanwhile, we also need to access to node j because it is necessary to save it otherwise the list will be broken. Therefore, three pointers should be declared in our code, which point to the current visited node, its previous node and its next node.

Lastly we should get the head node of the reversed list. Obviously head in the reversed list should be tail of the original list. Which pointer is tail? It should be a node whose m_pNext is NULL.

With comprehensive analysis above, we are ready to write code, which is shown below:

ListNode* ReverseList(ListNode* pHead)

{

    ListNode* pReversedHead = NULL;

    ListNode* pNode = pHead;

    ListNode* pPrev = NULL;

    while(pNode != NULL)

    {

        ListNode* pNext = pNode->m_pNext;

        if(pNext == NULL)

            pReversedHead = pNode;

        pNode->m_pNext = pPrev;

        pPrev = pNode;

        pNode = pNext;

    }

    return pReversedHead;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.

No. 17 - Queue Implemented with Two Stacks

Problem: Implement a queue with two stacks. The class for queues is declared in C++ as below. Please implement two functions: appendTail to append an element into tail of a queue, and deleteHead to delete an element from head of a queue.

template <typename T> class CQueue

{

public:

    CQueue(void);

    ~CQueue(void);

   

void appendTail(const T& node);

    T deleteHead();                 

private:

    stack<T> stack1;

    stack<T> stack2;

};

Analysis: According to declaration above, a queue contains two stacks stack1 and stack2. Therefore, it is required to implement a queue which follows the rule “First In First Out” with two stacks which follow the rule of “First In Last Out”.

We analyze the process to add and delete some elements via some examples. Firstly en element a is inserted. Let us push it into stack1. There is an element {a} in stack1and stack2 is empty. We continue to add two more elements b and c (push them into stack1 too). There are three elements {a, b, c} in stack1 now, where c is on its top, and stack2 is still empty (as shown in Figure 1-a).

We then have a try to delete an element from a queue. According to the rule “First in First out”, the first element to be deleted is a since it is added before b and c. The element a is stored in to stack1, and it is not on the top of stack. Therefore, we cannot pop it directly. We can notice that stack2 has not been used, so it is the time for us to utilize it. If we pop elements from stack1 and push them into stack2 one by one, the order of elements in stack2 is reverse to the order in stack1. After three popping and pushing operations, stack1 becomes empty and there are three elements {c, b, a} in stack2. The element a can be popped out now since it is on the top of stack2. Now there are two elements left {c, b} in stack2 and b is on its top (as shown in Figure 1-b).

How about to continue deleting more elements from the tail of queue? The element b is inserted into queue before c, so it should be deleted when there are two elements b and c left in queue. It can be popped out since it is on the top of stack2. After the popping operation, stack1 remains empty and there is only an element c in stack2 (as shown in Figure 1-c).

It is time to summarize the steps to delete an element from a queue: The top of stack2 can be popped out since it is the first element inserted into queue when stack2 is not empty. When stack2 is empty, we pop all elements from stack1 and push them into stack2 one by one. The first element in a queue is pushed into the bottom of stack1. It can be popped out directly after popping and pushing operations since it is on the top of stack2.

Let us insert another element d. How about to push it into stack1 (as shown in Figure1-d)? When we continue to delete the top of stack2, which is element c, can be popped because it is not empty (as shown in Figure 1-d). The element c is indeed inserted into queue before the element d, so it is a reasonable operation to delete c before d. The final status of the queue is shown as Figure 1-e.

Figure 1: The process to simulate a queue with two stacks.

We can write code after we get clear ideas about the process to insert and delete elements. Some sample code is shown below:

template<typename T> void CQueue<T>::appendTail(const T& element)

{

    stack1.push(element);

}

template<typename T> T CQueue<T>::deleteHead()

{

    if(stack2.size()<= 0)

    {

        while(stack1.size()>0)

        {

            T& data = stack1.top();

            stack1.pop();

            stack2.push(data);

        }

    }

    if(stack2.size() == 0)

        throw new exception("queue is empty");

    T head = stack2.top();

    stack2.pop();

    return head;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.    

No. 16 - Maximal Length of Incremental Subsequences

Problem: Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

Analysis: We try to get the maximum length of all increasing subsequences ending with each element in the array.

For instance, when we analyze the maximum length of all increasing subsequences ending with number 5, we compare it with each number before it. The first number 7 is greater than 5. If the subsequence comes from 7, 7 cannot be included into the subsequence. Therefore, its length is 1. The following three numbers 2, 3 and 1 in the input array before 5 are less than 5. If the previous number of 5 in the increasing subsequence is 2, the maximum incremental length is 2. If the previous number of 5 in the increasing subsequence is 3, the maximum incremental length is 3 (with number 2, 3, and 5) since the maximum length of all subsequences ending with number 3 is 2 (with number 2 and 3). Similarly, its maximum length is 2 if the previous number is number 1. The whole process can be summarized in Table 1.

	7	2	3	1	5	8	9	6
7	1	NA	NA	NA	NA	NA	NA	NA
2	1	1	NA	NA	NA	NA	NA	NA
3	1	2	1	NA	NA	NA	NA	NA
1	1	1	1	1	NA	NA	NA	NA
5	1	2	3	2	1	NA	NA	NA
8	2	2	3	2	4	1	NA	NA
9	2	2	3	2	4	5	1	NA
6	1	2	3	2	4	1	1	1

Table 1: Process to get the maximum length of increasing subsequences in array {7, 2, 3, 1, 5, 8, 9, 6}. Numbers in each row indicate length of subsequences ending with row title with previous number in the column title. Highlighted numbers with yellow background are the maximum lengths.  The highlighted number 5 with yellow background and red font is the maximum length of all incremental subsequences in the input array.

We are ready to write code with the detailed analysis above. The following is sample code:

int LengthOfIncreasing(int* data, int length)

{

    if(data == NULL || length < 0)

        return 0;

    int* longest = new int[length];

    longest[0] = 1;

    int max = 0;

    for(int i = 1; i < length; ++ i)

    {

        max = 0;

        for(int j = 0; j < i; ++ j)

        {

            if(data[j] < data[i] && longest[j] > max)

                max = longest[j];

        }

        longest[i] = max + 1;

    }

    max = 0;

    for(int i = 0; i < length; ++ i)

        if(longest[i] > max)

            max = longest[i];

                                                                  

    return max;   

}

Even though a 2-D matrix is needed to analyze the process, only a 1-D array is necessary in our code to store the maximum length of subsequences ending with each number in the input array.

If we are familiar with dynamic programming, we can get a direct solution quickly in a formal way. We can define a function f(i) indicating the maximum length of all subsequences ending with the i^th number in the input array (denoted as A[i]). We define another function g(i, j) which stands for the maximum length of incremental subsequences ending with A[i] coming from A[j]. The required output is max(f(i)) where 0<=i<n and n is the length of array. We can get f(i) with the following equation:

Actually, same code will be implemented based on this equation. The function f(i) is longest[i] in the code above. Therefore, it is identical to the previous solution.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.   

No. 15 - Fibonacci Sequences

Problem: Please implement a function which returns the n^th number in Fibonacci sequences with an input n. Fibonacci sequence is defined as:

Analysis: It is a classic interview questions to get numbers in Fibonacci sequences. We have different solutions for it, and their performance varies a lot.

Solution 1: Inefficient recursive solution

Fibonacci sequences are taken as examples to lecture recursive functions in many C/C++ textbooks, so most of candidates are familiar with the recursive solution. They feel confident and delighted when they meet this problem during interviews, because the can write the following code in short time:

long long Fibonacci(unsigned int n)

{

    if(n <= 0)

        return 0;

    if(n == 1)

        return 1;

    return Fibonacci(n - 1) + Fibonacci(n - 2);

}

Our textbooks take Fibonacci sequences as examples for recursive functions does not necessarily mean that recursion is a good solution for Fibonacci sequences. Interviewers may tell candidates that the performance of this recursive solution is quite bad, and ask them to analyze root causes.

Let us take f(10) as an example to analyze the recursive process. We have to get f(9) and f(8) before we get f(10). Meanwhile, f(8) and f(7) are needed before we get f(9). The dependency can be visualized in a tree as shown in Figure 1:

Figure 1: Recursive process to get the 10^th number in Fibonacci sequences

It is not difficult to notice that there are many duplicate nodes in the tree in Figure 1. The number of duplicated nodes increases dramatically when n increases.  Readers may have a try on the 100^th number if Fibonacci sequences to have intuitive ideas about how slow this recursive solution is.

Solution 2: Practical Solution with O(n) efficiency

It is easy to optimize performance fortunately if we calculate from bottom. That is to say, we get f(2) based on f(0) and f(1), and get f(3) based on f(1) and f(2). We follow this pattern till we get f(n). It is obvious that its time complexity is O(n). Its corresponding code is shown below:

long long Fibonacci(unsigned n)

{

    int result[2] = {0, 1};

    if(n < 2)

        return result[n];

    long long  fibNMinusOne = 1;

    long long  fibNMinusTwo = 0;

    long long  fibN = 0;

    for(unsigned int i = 2; i <= n; ++ i)

    {

        fibN = fibNMinusOne + fibNMinusTwo;

        fibNMinusTwo = fibNMinusOne;

        fibNMinusOne = fibN;

    }

     return fibN;

}

Solution 3: O(logn) solution

Usually interviewers expect the O(n) solution above. However, there is an O(logn) solution available, which is based on an uncommon equation as shown below:

It is not difficult to prove this equation vithmathematical induction. Interested readers may have try.

Now the only problem is how to calculate power of a matrix. We can calculate power with exponent n in O(logn) time with the following equation:

The source code to get power of a matrix looks complicated, which is listed below:

#include <cassert>

struct Matrix2By2

{

    Matrix2By2

    (

        long long m00 = 0,

        long long m01 = 0,

        long long m10 = 0,

        long long m11 = 0

    )

    :m_00(m00), m_01(m01), m_10(m10), m_11(m11)

    {

    }

    long long m_00;

    long long m_01;

    long long m_10;

    long long m_11;

};

Matrix2By2 MatrixMultiply

(

    const Matrix2By2& matrix1,

    const Matrix2By2& matrix2

)

{

    return Matrix2By2(

        matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,

        matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,

        matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,

        matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);

}

Matrix2By2 MatrixPower(unsigned int n)

{

    assert(n > 0);

    Matrix2By2 matrix;

    if(n == 1)

    {

        matrix = Matrix2By2(1, 1, 1, 0);

    }

    else if(n % 2 == 0)

    {

        matrix = MatrixPower(n / 2);

        matrix = MatrixMultiply(matrix, matrix);

    }

    else if(n % 2 == 1)

    {

        matrix = MatrixPower((n - 1) / 2);

        matrix = MatrixMultiply(matrix, matrix);

        matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));

    }

    return matrix;

}

long long Fibonacci(unsigned int n)

{

    int result[2] = {0, 1};

    if(n < 2)

        return result[n];

    Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);

    return PowerNMinus2.m_00;

}

Even though it cost only O(logn) time in theory, its hidden constant parameter is quite big, so it is not treated as a practical solution in real software development. Additionally, it is not a recommended solution during interviews since its implementation code is very complex.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog o webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.  

No. 14 - Last Number in a Circle

Problem: If we delete the m^th number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4 as shown in Figure 1. If we delete the 3^rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

Figure 1: A circle composed of 5 numbers 0, 1, 2, 3, 4.

Analysis: We are going to introduce two solutions for this problem here, one is classic and quite intuitive and the other is very creative.

Solution 1: Simulate a circle with a looped linked list

Because a circle is mentioned in the problem, an intuitive solution is to simulate a circle with some data structures. Looped linked can fulfill such a purpose. We may create a looped list with n nodes, and then delete the m^th node at every time from it.

We can implement the looped list based on the std::list in the C++ standard template library. It should be noticed that std::list itself is not looped. When an iterator reaches end of a list, we need to reset it to its head. It behaves like a circle with such a little trick. The sample source code of this solution is shown below:

int LastRemaining(unsigned int n, unsigned int m)

{

    if(n < 1 || m < 1)

        return -1;

    unsigned int i = 0;

    list<int> numbers;

    for(i = 0; i < n; ++ i)

        numbers.push_back(i);

    list<int>::iterator current = numbers.begin();

    while(numbers.size() > 1)

    {

        for(int i = 1; i < m; ++ i)

        {

            current ++;

            if(current == numbers.end())

                current = numbers.begin();

        }

        list<int>::iterator next = ++ current;

        if(next == numbers.end())

            next = numbers.begin();

        -- current;

        numbers.erase(current);

        current = next;

    }

    return *(current);

}

If we analyze the code above carefully, we can notice that a looped list is scanned for many times. Of cause, repeatedly scanning has negative impacts on time efficiency. In this solution, traversal with m steps are necessary to delete a node, so the time complexity is O(mn) for a looped list. Meanwhile, it requires a list with n nodes to simulate a circle, so the space complexity is O(n).

Solution 2: Analyze the pattern of deleted numbers

Firstly, let us define a function f(n, m), which stands for the last remaining number in a circle which has n numbers 0, 1, …, n-1 and the m^th number is deleted at each time.

The first deleted number in the circle is (m-1)%n, which is denoted as k for simplicity. The n-1 numbers after k is deleted are 0, 1, …, k-1, k+1, …, n-1. The last remaining number is also a function about n and m. The pattern of new sequence is different from the pattern of the original sequence, which begins with 0, so the function differs from the function f, which can be denoted as f’(n-1, m). The last remaining number of the original sequence should be the last remaining number of the sequence deleting k, so f(n, m)=f’(n-1, m).

Since we count the next m^th number from k+1, the sequence might be also viewed as k+1, …, n-1, 0, 1, …, k-1. We project this sequence of numbers into a new sequence in range of 0 and n-2:

k+1	→	0
k+2	→	1
…
n-1	→	n-k-2
0	→	n-k-1
1	→	n-k
…
k-1	→	n-2

If the projection is denoted as p, p(x)=(x-k-1%n, and the reversed projection is p^-1(x)=(x+k+1)%n.

The projected sequence has the same format as the original sequence because they both begin from 0. Therefore, its last remaining number is the projected sequence also follows rules of function f. We denoted as f(n-1, m).

The last remaining number of the sequence before projection is f’(n-1, m)= p^-1[f(n-1, m)]=[f(n-1, m)+k+1]%n. Since k=(m-1)%n, f(n, m)=f’(n-1,m)=[f(n-1, m)+m]%n.

A recursive equation is found after complex analysis. We can get last remaining number in a list with n numbers based on the last remaining number in a list with n-1 numbers. When n=1 (there is only one number 0 in the list), the last remaining number is obviously 0. The rules can be summarized as:

The equation can be implemented based on both recursion and iteration. The following code is based on iteration:

int LastRemaining(unsigned int n, unsigned int m)

{

    if(n < 1 || m < 1)

        return -1;

    int last = 0;

    for (int i = 2; i <= n; i ++)

        last = (last + m) % i;

    return last;

}

Even though the analysis is quite complex, its corresponding code is very simple. That is beauty of mathematics. More importantly, its time complexity is O(n) and space complexity is O(1), so it is much better than the first solution in both time and memory efficiency.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a referenced to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.