No. 12 - Mirror of Binary Trees

Problem: Please implement a function which returns mirror of a binary tree.

Binary tree nodes are defined as:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Analysis: Mirror of binary trees may be a new concept for many candidates, so they may not find a solution in short time during interviews. In order to get some visual ideas about mirrors, we may draw a binary tree and its mirror according to our daily experience. For example, the binary tree on the right of Figure 1 is the mirror of the left one.

Figure 1: Two binary trees which are mirrors of each other

Let us analyze these two trees in Figure 1 carefully to get the steps of mirrors. Their root nodes are identical, but their left and right children are swapped. Firstly we may swap two nodes under the root of the original binary tree, and it becomes the second tree in Figure 2.

Figure 2: Process to get mirror of a binary tree. (a) Swap children of the root node; (b) Swap children of the node 10; (c) Swap the children of node 6.

We can notice that the children nodes of not 10 and 6 keep unchanged. Therefore, we need to continue to swap their children nodes. The third and fourth trees in Figure 2 are the swapped binary trees accordingly. It is noticeable that the fourth tree is the mirror target.

Now we can summarize the process for mirror: We visit all nodes in a binary tree with pre-order traversal, and swap the children of current visited node if it has. We will get mirror of a binary tree after we visit all of its nodes.

Let us begin to write code after we get clear ideas about the process. The following is the sample code:

void Mirror(BinaryTreeNode *pNode)

{

    if((pNode == NULL) || (pNode->m_pLeft == NULL && pNode->m_pRight))

        return;

    BinaryTreeNode *pTemp = pNode->m_pLeft;

    pNode->m_pLeft = pNode->m_pRight;

    pNode->m_pRight = pTemp;

   

    if(pNode->m_pLeft)

        MirrorRecursively(pNode->m_pLeft); 

    if(pNode->m_pRight)

        MirrorRecursively(pNode->m_pRight);

}

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.

No. 11 - Print Binary Trees from Top to Bottom

Problem: Please print a binary tree from its top level to bottom level, and print nodes from left to right if they are in same level. 

For example, it prints the binary tree in Figure 1 in order of 8, 6, 10, 5, 7, 9, 11.

A binary tree node is defined as below:

struct BinaryTreeNode

{

    int                    m_nValue;

    BinaryTreeNode*        m_pLeft; 

    BinaryTreeNode*        m_pRight;

};

Figure 1: A binary tree sample. If it is printed from top to bottom, it prints 8, 6, 10, 5, 7, 9, 11 sequentially.

Analysis: It examines candidates’ understanding of tree traverse algorithms, but the traverse here is not the traditional pre-order, in-order or post-order traverses. If we are not familiar with it, we may analyze the printing process with some examples during interview. Let us take the binary tree in Figure 1 as an example.

Since we begin to print from the top level of the tree in Figure 1, we can start our analysis from its root node. Firstly we print the value in its root node, which is 8. We need to store the children nodes with value 6 and 10 in a data container in order to print them after we print the root. There are two nodes in our container at this time.

Secondly we retrieve the node 6 from the container, since nodes 6 and 10 are in same level and we need to print them from left to right. We also need to store the nodes 5 and 7 after we print the node 6. There are three nodes in the container now, which are node 10, 5 and 7.

Thirdly we retrieve the node 10 from the container. It is noticeable that node 10 is stored into the container before nodes 5 and 7 are stored, and it is also retrieved ahead of nodes 5 and 7. It is typically “First in first out”, so the container is essentially a queue. After print the node 10, we store its two children nodes 9 and 11 into the container too.

Since nodes 5, 7, 9, 11 do not have children, we print them in order.

The printing process can be summarized in the following Table 1:

Step	Operation	Nodes in queue
1	Print Node 8	Node 6, Node 10
2	Print Node 6	Node 10, Node 5, Node 7
3	Print Node 10	Node 5, Node 7, Node 9, Node 11
4	Print Node 5	Node 7, Node 9, Node 11
5	Print Node 7	Node 9, Node 11
6	Print Node 9	Node 11
7	Print Node 11

Table 1: The process to print the binary tree in Figure 1 from top to bottom

We can summarize the rules to print a binary tree from top level to bottom level: Once we print a node, we store its children nodes into a queue if it has. We continue to print the head of the queue, pop it from the queue and store its children until there are no nodes left in the queue.

The following sample code is based on the deque class of STL:

void PrintFromTopToBottom(BinaryTreeNode* pTreeRoot)

{

    if(!pTreeRoot)

        return;

    std::deque<BinaryTreeNode *> dequeTreeNode;

    dequeTreeNode.push_back(pTreeRoot);

    while(dequeTreeNode.size())

    {

        BinaryTreeNode *pNode = dequeTreeNode.front();

        dequeTreeNode.pop_front();

        printf("%d ", pNode->m_nValue);

        if(pNode->m_pLeft)

            dequeTreeNode.push_back(pNode->m_pLeft);

        if(pNode->m_pRight)

            dequeTreeNode.push_back(pNode->m_pRight);

    }

}

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. 10 - K-th Node from End

Problem: Get the K^th node from end of a linked list. It counts from 1 here, so the 1^st node from end is the tail of list. 

For instance, given a linked list with 6 nodes, whose value are 1, 2, 3, 4, 5, 6, its 3^rd node from end is the node with value 4.

A node in the list is defined as:

struct ListNode

{

    int       m_nValue;

    ListNode* m_pNext;

};

Analysis: In a list with n nodes, its k^th node from end should be the (n-k+1)^th node from its head. Therefore, if we know the number of nodes n in a list, we can get the required node with n-k+1 steps from its head. How to get the number n? It is easy if we scan the whole list from beginning to end.

The solution above needs to scan a list twice: We get the total number of nodes with the first scan, and reach the k^th node from end with the second scan. Unfortunately, interviewers usually expect a solution which only scans a list once.

We have a better solution to get the k^th node from end with two pointers. Firstly we move a pointer (denoted as P1) k-1 steps beginning from the head of a list. And then we move another pointer (denoted as P2) beginning from the head, and continue moving the P1 forward at same speed. Since the distance of these two pointers is always k-1, P2 reaches the k^th node from end when P1 reaches the tail of a list. It scans a list only once, and it is more efficient than the previous solution.

Figure 1: Get the 3^rd node from end of a list with 6 nodes

It simulates the process to get the 3^rd node from end of a list with 6 nodes in Figure 1. We firstly move P1 2 steps (2=3-1) to reach the 3^rd node (Figure 1-a). Then P2 points to the head of a list (Figure 1-b). We move two pointers at the same speed, when the P1 reaches the tail, what P2 points is the 3^rd node from end (Figure 1-c).

The sample code of the solutions with two pointers is shown below:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)

{

    if(pListHead == NULL || k == 0)

        return NULL;

    ListNode *pAhead = pListHead;

    ListNode *pBehind = NULL;

    for(unsigned int i = 0; i < k - 1; ++ i)

    {

        if(pAhead->m_pNext != NULL)

            pAhead = pAhead->m_pNext;

        else

        {

            return NULL;

        }

    }

    pBehind = pListHead;

    while(pAhead->m_pNext != NULL)

    {

        pAhead = pAhead->m_pNext;

        pBehind = pBehind->m_pNext;

    }

    return pBehind;

}

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. 09 - Numbers with a Given Sum

Problem 1: Given an increasingly sorted array and a number s, please find two numbers whose sum is s. If there are multiple pairs with sum s, just output any one of them.

For example, if the inputs are an array {1, 2, 4, 7, 11, 15} and a number 15, please out two numbers 4 and 11 since 4+11=15.

Analysis: Let us firstly have a try to select two numbers (denoted as num1 and num2) of the input array. If their sum equals to s, we are fortunate because the required numbers have been found. If the sum is less than s, we may replace num1 with its next number, because the array is increasingly sorted and its next number should be greater. If the sum is greater than s, num2 can be replaced with its previous number in the sorted array, which should be less than num2.

Take the array {1, 2, 4, 7, 11, 15} and number 15 as an example. We define two pointers. At the first step, they point to the first number (also the least one) 1 and the last number (also the greatest one) 15. We move the second pointer forward to number 11, since their sum 16 and it is greater than 15.

At the second step, the two numbers are 1 and 11, and their sum 12 is less than 15. Therefore, we can move the first pointer afterward and let it point to 2.

The two numbers are 2 and 11 accordingly at the third step. Since their sum 13 is less than 15, we move the first pointer afterward again.

Now the two numbers are 4 and 11, and their sum is 15 which is the expected sum. Therefore, we have found two numbers whose sum is 15.

The process is summarized as in Table 1:

Step	Num1	Num2	Sum	Comparing with s	Operation
1	1	15	16	Greater	Select the previous number of Num2
2	1	11	12	Less	Select the next number of Num1
3	2	11	13	Less	Select the next number of Num1
4	4	11	15	Equal

Table 1: Find a pair of numbers with sum 15 out of array {1、2、4、7、11、15}

After interviewers approve our solution, we can begin to write code. The following is a piece of sample code:

bool FindNumbersWithSum(int data[], int length, int sum,

                        int* num1, int* num2)

{

    bool found = false;

    if(length < 1 || num1 == NULL || num2 == NULL)

        return found;

    int ahead = length - 1;

    int behind = 0;

    while(ahead > behind)

    {

        long long curSum = data[ahead] + data[behind];

        if(curSum == sum)

        {

            *num1 = data[behind];

            *num2 = data[ahead];

            found = true;

            break;

        }

        else if(curSum > sum)

            ahead --;

        else

            behind ++;

    }

    return found;

}

In the code above, ahead is the index of the first number, and behind is the index of the second number. Since we only need to scan the input array once, its time complexity is O(n).

Problem 2: Given an array, please determine whether it contains three numbers whose sum equals to 0.

Analysis: This problem is also required to find some numbers with a given array and sum, it is similar to the first problem. We may get some hints from the solution above.

Since the input of the previous problem is an increasingly sorted array, we can also firstly sort the input array increasingly. Secondly we scan the array. When we reach the i-th number with value n, we try to find whether there are two numbers whose sum is –n in the array excluding the i-th number.

It is time for us to write some code. We modify the function FindNumbersWithSum above a little bit:

bool FindNumbersWithSum(int data[], int length, int sum, int excludeIndex)

{

    bool found = false;

    int ahead = length - 1;

    int behind = 0;

    while(ahead > behind)

    {

        if(ahead == excludeIndex)

            ahead --;

        if(behind == excludeIndex)

            behind ++;

        long long curSum = data[ahead] + data[behind];

        if(curSum == sum)

        {

            found = true;

            break;

        }

        else if(curSum > sum)

            ahead --;

        else

            behind ++;

    }

    return found;

}

It determines whether there are two numbers whose sum is sum in array data excluding the number with index excludeIndex. We can determine whether there are three numbers in an array with sum 0 based on this function:

bool HasThreeNumbersWithSum0(int data[], int length)

{

    bool found = false;

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

        return found;

    std::sort(data, data + length - 1);

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

    {

        int sum = -data[i];

        int num1, num2;

        found = FindNumbersWithSum(data, length, sum, i);

        if(found)

            break;

    }

    return found;

}

It contains two steps in function HasThreeNumbersWithSum0. It costs O(nlogn)time to sort n numbers at its first step. At its second step it costs O(n) time for each number to call FindNumberWithSum, so it costs O(n²) time in the for loop. Therefore, its overall time complexity is O(n²).

The discussion about these two problems 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. 08 - Calculate 1+2+…+n

Problem: Calculate 1+2+…+n without multiplication, division, key words for, while, if, else, switch, case, as well as conditional operator (A ? B : C).

Analysis: This problem is not meaningful during software development since usually we do not have such rigorous limitations. However, many interviewers believe that it is useful to test candidates’ ability of divergent thinking. Ability of divergent thinking reflects the depth and width of programming understanding.

Besides equation n(n+1)/2 to get 1+2+…+n, we only have two approaches: Iteration and recursion. Since key words for and while are forbidden, we cannot utilize iteration directly any more. In a recursive function, we need to use key word if or conditional operators to check whether we should continue or stop recursion. Unfortunately, both of them are also forbidden.

Solution 1: Based on Constructors

Let us firstly focus on iterations. An iteration is actually only to repeat n times, and we can achieve it without key words for and while. We can define a class, and then create n instances of it. Therefore, its constructor and destructor will be definitely called n times. If we implement calculation operations inside the constructor, it will iterate for n times. The following code is based on this solution:

class Temp

{

public:

    Temp() { ++ N; Sum += N; }

    static void Reset() { N = 0; Sum = 0; }

    static unsigned int GetSum() { return Sum; }

private:

    static unsigned int N;

    static unsigned int Sum;

};

unsigned int Temp::N = 0;

unsigned int Temp::Sum = 0;

unsigned int Sum_Solution1(unsigned int n)

{

    Temp::Reset();

    Temp *a = new Temp[n];

    delete []a;

    a = NULL;

    return Temp::GetSum();

}

Solution 2: Based on Virtual Functions

We secondly focus on recursion. We cannot determine to continue or stop recursion inside a single function. How about to define two functions, one for normal operations and the other as a terminator? We may use Boolean variables since we are going to select a function out of two. When the Boolean variable is true (1), the operational function will be selected. When it is false (0), the terminal function will be selected.

We have to convert integer variables into Boolean variables. It is an easy task since it can be achieved with two not operations (!!n). Non-zero numbers will be true with two not operations and zero will be false.

class A;

A* Array[2];

class A

{

public:

    virtual unsigned int Sum (unsigned int n)

    {

        return 0;

    }

};

class B: public A

{

public:

    virtual unsigned int Sum (unsigned int n)

    {

        return Array[!!n]->Sum(n-1) + n;

    }

};

int Sum_Solution2(int n)

{

    A a;

    B b;

    Array[0] = &a;

    Array[1] = &b;

    int value = Array[1]->Sum(n);

    return value;

}

This solution is based on virtual functions. The function B::Sum is called when variable n is not zero, while the function A::Sum, which acts as a terminator, is called when n equals to zero.

Solution 3: Based on Function Pointers

There are no virtual functions in native C programming environment, so we have to simulate them with function pointers. The code below may be more straightforward:

typedef unsigned int (*fun)(unsigned int);

unsigned int Solution3_Teminator(unsigned int n)

{

    return 0;

}

unsigned int Sum_Solution3(unsigned int n)

{

    static fun f[2] = {Solution3_Teminator, Sum_Solution3};

    return n + f[!!n](n - 1);

}

Solution 4: Based on Template Classes

We can also utilize compiler to simulate recursive calculate. Let us have a look at the following code:

template <unsigned int n> struct Sum_Solution4

{

    enum Value { N = Sum_Solution4<n - 1>::N + n};

};

template <> struct Sum_Solution4<1>

{

    enum Value { N = 1};

};

The value of Sum_Solution4<100>::N is the result of 1+2+…+100. When compilers see Sum_Solution4<100>, it will generate code for the template class Sum_Solution4 with parameter 100. A class Sum _Solution4 <99> is needed to generate the class Sum_Solution4<100> since Sum _Solution4<100>::N= Sum _Solution4 <99>::N+100. The recursive process stops when it reaches the Sum_Solution4<1> because it has been defined explicitly.

In the solution, the input n must be a constant value since calculations are all in compiling time. It is a big short coming for this solution. Additionally, n cannot be a large number since compilers have limitations on the depths of recursive compiling.

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.