No. 47 - Search in a Rotation of an Array

Question: When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.

For example, array {3, 4, 5, 1, 2} is a rotation of array {1, 2, 3, 4, 5}. If the target number to be searched is 4, the index of the number 4 in the rotation 1 should be returned. If the target number to be searched is 6, -1 should be returned because the number does not exist in the rotated array.

Analysis: Binary search is suitable for sorted arrays. Let us try to utilize it on a rotation of a sorted array. Notice that a rotation of a sorted array can be partitioned into two sorted sub-arrays, and numbers in the first sub-array are greater than numbers in the second one.

Two pointers P1 and P2 are utilized. P1 references to the first element in the array, and P2 references to the last element. According to the rotation rule, the first element should be greater than the last one.

The algorithm always compares the number in middle with numbers pointed by P1 and P2 during binary search. If the middle number is in the first increasingly sorted sub-array, it is greater than the number pointed by P1.

If the value of target number to be search is between the number pointed by P1 and the middle number, we then search the target number in the first half sub-array. In such a case the first half sub-array is in the first increasing sub-array, we could utilize the binary search algorithm. For example, if we search the number 4 in a rotation {3, 4, 5, 1, 2}, we could search the target number 4 in the sub-array {3, 4, 5} because 4 is between the first number 3 and the middle number 5.

If the value of target number is not between the number pointed by P1 and the middle number, we search the target in the second half sub-array. Notice that the second half sub-array also contains two increasing sub-array and itself is also a rotation, so we could search recursively with the same strategy. For example, if we search the number 1 in a rotation {3, 4, 5, 1, 2}, we could search the target number 1 in the sub-array {5, 1, 2} recursively.

The analysis above is for two cases when the middle number is in the first increasing sub-array. Please analyze the other two cases when the middle number is in the second increasing sub-array yourself, when the middle number is less than the number pointed by P2.

The code implementing this algorithm is listed below, in C/C++:

int searchInRotation(int numbers[], int length, int k)

{

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

        return -1;

   

    return searchInRotation(numbers, k, 0, length - 1);

}

int searchInRotation(int numbers[], int k, int start, int end)

{

    if(start > end)

        return -1;

       

    int middle = start + (end - start) / 2;

    if(numbers[middle] == k)

        return middle;

   

    // the middle number is in the first increasing sub-array

    if(numbers[middle] >= numbers[start])

    {

        if(k >= numbers[start] && k < numbers[middle])

            return binarySearch(numbers, k, start, middle - 1);

        return searchInRotation(numbers, k, middle + 1, end);

    }

    // the middle number is in the second increasing sub-array

    else if(numbers[middle] <= numbers[end])

    {

        if(k > numbers[middle] && k <= numbers[end])

            return binarySearch(numbers, k, middle + 1, end);

        return searchInRotation(numbers, k, start, middle - 1);

    }

   

    // It should never reach here if the input is valid

    assert(false);

}

Since the function binarySearch is for the classic binary search algorithm, it is not listed here. You might implement your own binary search code if you are interested.

In each round of search, half of the array is excluded for the next round, so the time complexity is O(logn).

You may wonder why we assume there are no duplications in the input array. We determine whether the middle number is in the first or second sub-array by comparing the middle number and the numbers pointed by P1 or P2. When the middle number, the number pointed by P1 and P2 are identical, we don’t know whether the middle number is in the first or second increasing sub-array.

Let’s look at some examples. Two arrays {1, 0, 1, 1, 1} and {1, 1, 1, 0, 1} are both rotations of an increasingly sorted array {0, 1, 1, 1, 1}, which are visualized in Figure 1.

Figure 1: Two rotations of an increasingly sorted array {0, 1, 1, 1, 1}: {1, 0, 1, 1, 1} and {1, 1, 1, 0, 1}. Elements with gray background are in the second increasing sub-array.

In Figure 1, the elements pointed by P1 and P2, as well as the middle element are all 1. The middle element with index 2 is in the second sub-array in Figure 1 (a), while the middle element is in the first sub-array in Figure 1 (b).

Since we can’t determine whether the middle number in the first or second increasing sub-array, we have to search sequentially for such cases, and our code listed above should be revised.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.

No. 46 - Nodes with Sum in a Binary Search Tree

Problem: Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.


Figure 1: A sample binary search tree

For example, if the given sum is 66, there are two nodes in Figure 1 with value 25 and 41 whose sum is 66. While the given sum is 58, there are not two nodes whose sum is same as the given value.

Analysis: In a previous blog, we discussed how to check whether there are two numbers in a sorted array whose sum equals a given value. In order to solve this problem, we initialize a number num1 as the smallest number in the array, and initialize num2 as the greatest one. If the sum of num1 and num2 is same as the given value, two required numbers have been found. If the sum is greater than the given value, we move num2 to the previous number in the array (with less value). Similarly, we move num1 to the next number in the array (with greater value) if the sum is less than the given value.

Inspired by the solution, we may find two nodes with a given sum in a binary search tree with similar strategy. Firstly we initialize a pointer P1 to the smallest node in the tree, and another pointer P2 to the greatest node. When the sum of two values in the nodes pointed by P1 and P2 is same as the given value, two required nodes have been found. If their sum is greater than the given value, we move P2 to the previous node (containing less value). Moreover, we move P1 to the next node (containing greater value) if their sum is less than the given value.

It is not difficult to get the least and greatest value of a binary search tree. If we move along the links to left children, and the leaf node we arrive at finally contains the least value. For instance, if we move along the links to left children in Figure 1, the nodes on the path contain value 32, 24, 21 and 14, and 14 is the least value in the binary search tree.

Similarly, if we move along links to right children, and the leaf node we arrive at finally contains the greatest value.

The key to solve this problem is how to get the next nodes (with greater values) and the previous nodes (with less values) in a binary search tree. Let’s utilize stacks.

In order to get next nodes, we scan the tree along the links to leaf children, and push the scanned nodes into a stack. That’s to say, there are four nodes in the stack (nodes 32, 24, 21 and 14), and node 14 is on the top.

When the top of the stack is popped, node 21 on the top of stack is the next node of 14. And when the node 21 is popped, the node 24 on the top is the next node of 21.

The steps to get the next node of node 24 are more complex, because the node 24 has a right child. We pop the node 24, and push its right child, node 28, into the stack. And then, we scan the nodes from the right child along the links to left children. Therefore, the node 31 will also be pushed into the stack. At this time, there are three nodes in the stack (nodes 32, 28 and 25), and the top on the stack (node 25) is the next node of node 24.

Let’s summarize the steps to get next nodes. If the node on the top does not have a right child, the node is popped off, and the next node is on the top again. If the node on the top has a right child, after the node is popped off and then the right child is pushed, and all nodes along the links to left children are pushed into the stack. The last pushed node on the top is the next node. We continue the steps to pop and push until the stack is empty.

If you are interested, please try to analyze the steps to the next nodes after the node 25 by yourself.

The steps to get previous nodes are quite similar. At first we push the root node, and nodes along the links to right children. The node with least is on the top of stack. In order to get the previous nodes with less values, the top is popped off. If the top does not have a left child, the previous node is the new top node in the stack. If the top has the left child, we push its left child, as well as nodes along links to right children. The last pushed node is the previous node of the node popped.

Our solution can be implemented with the following C++ code:

bool hasTwoNodes(BinaryTreeNode* pRoot, int sum)

{
    stack<BinaryTreeNode*> nextNodes, prevNodes;
    buildNextNodes(pRoot, nextNodes);
    buildPrevNodes(pRoot, prevNodes);

    BinaryTreeNode* pNext = getNext(nextNodes);

    BinaryTreeNode* pPrev = getPrev(prevNodes);
    while(pNext != NULL && pPrev != NULL && pNext != pPrev)
    {
        int currentSum = pNext->m_nValue + pPrev->m_nValue;
        if(currentSum == sum)
            return true;

        if(currentSum < sum)

            pNext = getNext(nextNodes);
        else
            pPrev = getPrev(prevNodes);
    }

    return false;

}

void buildNextNodes(BinaryTreeNode* pRoot, stack<BinaryTreeNode*>& nodes)

{
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pLeft;
    }
}

void buildPrevNodes(BinaryTreeNode* pRoot, stack<BinaryTreeNode*>& nodes)

{
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pRight;
    }
}

BinaryTreeNode* getNext(stack<BinaryTreeNode*>& nodes)

{
    BinaryTreeNode* pNext = NULL;
    if(!nodes.empty())
    {
        pNext = nodes.top();
        nodes.pop();

        BinaryTreeNode* pRight = pNext->m_pRight;

        while(pRight != NULL)
        {
            nodes.push(pRight);
            pRight = pRight->m_pLeft;
        }
    }

    return pNext;

}

BinaryTreeNode* getPrev(stack<BinaryTreeNode*>& nodes)

{
    BinaryTreeNode* pPrev = NULL;
    if(!nodes.empty())
    {
        pPrev = nodes.top();
        nodes.pop();

        BinaryTreeNode* pLeft = pPrev->m_pLeft;

        while(pLeft != NULL)
        {
            nodes.push(pLeft);
            pLeft = pLeft->m_pRight;
        }
    }

    return pPrev;

}

This solution costs O(n) time. The space complexity is O(height of tree), which is O(logn) on average, and O(n) in the worst cases.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.

No. 45 - Closest Node in a Binary Search Tree

Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

For instance, in the binary search tree in Figure 1, the node closest to 29 is the node with value 28.

Figure 1: A sample binary search tree, in which the closest node to 29 is the node with value 28

Analysis: Let’s analyze this problem step by step, taking the binary search in Figure 1 and 29 as an example.

We start from the root node with value 32, and the distance to 29 is 3. Since the value 32 is greater than 29, and all values in the right sub-tree are greater than 32, distances to 29 in the right sub-tree should be greater than 3. We move to the left sub-tree.

The next node to be visited contains value 24, and the distance to 29 is 5. Since 5 is greater than the previous closest distance 3, the closest node up to now remains the node with value 32. Additionally, the current value 24 is less than 29, and all values in the left sub-tree are less than 24, so distances to 29 in the left sub-tree will be greater than 5. We move on to visit the right sub-tree.

The next node to be visited contains value 28, and the distance to 29 is 1. Since 1 is less than the previous closest distance 3, the closest node is updated to the node with value 28. Additionally, the value 28 is less than 29, and all values in the left sub-tree areless than 28, so distances to 29 in the left sub-tree will be greater than 1. Let’s continue to visit the right sub-tree.

Finally we reach a left node with value 31. The distance to 29 is 2 and it is greater than the previous closest distance 1, so the closest node to 29 is still the node with value 28.

According to the step-by-step analysis above, we could implement the following code:

BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
    BinaryTreeNode* pClosest = NULL;
    int minDistance = 0x7FFFFFFF;
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        int distance = abs(pNode->m_nValue - value);
        if(distance < minDistance)
        {
            minDistance = distance;
            pClosest = pNode;
        }

        if(distance == 0)

            break;

        if(pNode->m_nValue > value)

            pNode = pNode->m_pLeft;
        else if(pNode->m_nValue < value)
            pNode = pNode->m_pRight;
    }

    return pClosest;

}
 

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.

No. 44 - Dynamic Programming on Stolen Values

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

Analysis: A function f(i) is defined to denote the maximal stolen value from the first house to the i^th house, and the value contained in the i^th house is denoted as v_i. When the thief reaches the i^th house, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:

It would be much more efficient to calculate in bottom-up order than to calculate recursively. It looks like a 1D array with size n is needed, but actually it is only necessary to cache two values for f(i-1) and f(i-2) to calculate f(i).

This algorithm can be implemented with the following C++ code:

int maxStolenValue(const vector<int>& values)

{

    int length = values.size();

    if(length == 0)

        return 0;

    int value1 = values[0];

    if(length == 1)

        return value1;

    int value2 = max<int>(values[0], values[1]);

    if(length == 2)

        return value2;

    int value;

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

    {

        value = max<int>(value2, value1 + values[i]);

        value1 = value2;

        value2 = value;

    }

    return value;

}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.

No. 43 - Minimal Number of Palindromes on a String

Problem: A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.

Given a string str, please get the minimal numbers of splits to partition it into palindromes. The minimal number of splits to partition the string “abbab” into a set of palindromes is 1.

Analysis: This is a typical problem which can be solved by dynamic programming. We have two strategies to analyze and solve this problem

Solution 1: Split at any space between two characters

Given a substring of str, starting from the index i and ending at the index j (denoted as str[i:j]), we define a function f(i, j) to denote the minimal number of splits to partition the substring str[i:j] into a set of palindromes. If the substring is a palindrome itself, we don’t have to split so f(i, j) is 0. If the substring is not a palindrome, the substring is split between two characters k and k+1. f(i, j)= f(i, k)+ f(k+1, j)+1 under such conditions. Therefore, f(i, j) can be defined with the following equation:

<!--[if !msEquation]--> <!--[if !vml]--><!--[endif]--><!--[endif]-->

The value of f(0, n-1) is the value of the minimal number of splits to partition str into palindromes, if n is the length of str.

If the equation is calculated recursively, its complexity grows exponentially with the length n. A better choice is to calculate in bottom-up order with a 2D matrix with size n×n. The following C++ code implements this solution:

int minSplit_1(const string& str)

{

    int length = str.size();

    int* split = new int[length * length];

   

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

        split[i * length + i] = 0;

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

    {

        for(int j = length - i; j > 0; --j)

        {

            int row = length - i - j;

            int col = row + i;

            if(isPalindrome(str, row, col))

            {

                split[row * length + col] = 0;

            }

            else

            {

                int min = 0x7FFFFFFF;

                for(int k = row; k < col; ++k)

                {

                    int temp1 = split[row * length + k];

                    int temp2 = split[(k + 1) * length + col];

                    if(min > temp1 + temp2 + 1)

                        min = temp1 + temp2 + 1;

                }

                split[row * length + col] = min;

            }

        }

    }

    int minSplit = split[length - 1];

    delete[] split;

    return minSplit;

}

Solution 2: Split only before a palindrome

We split the string str with another strategy. Given a substring ending at the index i, str[0, i], we do not have to split if the substring is a palindrome itself. Otherwise it is split between two characters at index j and j+1 only if the substring str[j+1,i] is a palindrome. Therefore, an equation f(i) can be defined as the following:

<!--[if !msEquation]--> <!--[if !vml]--><!--[endif]--><!--[endif]-->

The value of f(n-1) is the value of the minimal number of splits to partition str into palindromes, if n is the length of str.

We could utilize a 1D array to solve this equation in bottom-up order, as listed in the following code:

int minSplit_2(const string& str)

{

    int length = str.size();

    int* split = new int[length];

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

        split[i] = i;

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

    {

        if(isPalindrome(str, 0, i))

        {

            split[i] = 0;

            continue;

        }

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

        {

            if(isPalindrome(str, j + 1, i) && split[i] > split[j] + 1)

                split[i] = split[j] + 1;

        }

    }

    int minSplit = split[length - 1];

    delete[] split;

    return minSplit;

}

Optimization to verify palindromes:

Usually it costs O(n) time to check whether a string with length n is a palindrome, and the typical implementation looks like the following code:

bool isPalindrome(const string& str, int begin, int end)

{

    for(int i = begin; i < end - (i - begin); ++i)

    {

        if(str[i] != str[end - (i - begin)])

            return false;

    }

    return true;

}

Both solutions above cost O(n³) time. The first solution contains three nesting for-loops. The function isPalindrome is inside two nesting for-loops.

If we could reduce the cost of isPalindrome to O(1), the time complexity of the second solution would be O(n²).

Notice that the substring str[i,j] is a palindrome only if the characters at index i and j, and str[i+1,j-1] is also a palindrome. We could build a 2D table accordingly to store whether every substring of str is a palindrome or not during the preprocessing. With such a table, the function isPalindrome can verify the substring str[i,j] in O(1) time.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.

No. 42 - Three Increasing Elements in an Array

Problem: Given an array of integers A, please find three indexes i, j, k, such that i<j<k and A[i]<A[j]<A[k].

Analysis: Firstly let’s analyze this problem with the brute-force solution: All elements in the array are scanned one by one. When an element is scanned, we take is as A[j], and check whether there is a smaller element on its left side (A[i]), and a greater element on its right side (A[k]).

Since it takes O(n) time to scan numbers on two sides of each A[j], the overall time of this solution is O(n²) on an array with n elements.

Solution 1: O(n) time efficiency with O(n) space consumption

As our analysis above, for each element A[j], we need to know whether there is a smaller element on its left side. If there is not a smaller element on the left side, A[j] itself is the smallest of all elements from the leftmost element to A[j]. If there is a smaller element on the left side, the smallest of all elements from the leftmost element to A[j] is on the left side of A[j].

Therefore, we could construct an auxiliary array B. The element B[j] stores the index of the smallest element of elements from the leftmost element to A[j]. The array B can be constructed based on elements in A from left to right.

Similarly, we could also construct another auxiliary array C. The element C[j] stores the index of the greatest element of elements from the rightmost element to A[j]. The array C can be constructed based on elements in A from right to left.

When an element A[j] is scanned, the index j is compared with B[j] and C[j]. if B[j]<j (there is a smaller element on the left side) and j<C[j] (there is a greater element on the right side), three increasing elements have been found.

This solution can be implemented with the following C/C++ code:

void increasingIndex_1(int* nums, int length, int* i, int* j, int* k)

{

    if(nums == NULL || length <= 0 || i == NULL || j == NULL || k == NULL)

        return;

    int* minIndex = new int[length];

    int index = 0;

    minIndex[0] = 0;

    int t;

    for(t = 1; t < length; ++t)

    {

        if(nums[t] < nums[index])

            index = t;

        minIndex[t] = index;

    }

    int* maxIndex = new int[length];

    index = length - 1;

    for(t = length - 1; t >= 0; --t)

    {

        if(nums[t] > nums[index])

            index = t;

        maxIndex[t] = index;

    }

    for(t = 1; t < length - 1; ++t)

    {

        if(minIndex[t] < t && maxIndex[t] > t)

            break;

    }

    if(t < length - 1)

    {

        *i = minIndex[t];

        *j = t;

        *k = maxIndex[t];

    }

    else

    {

        *i = *j = *k = -1;

    }

    delete[] minIndex;

    delete[] maxIndex;

}

Solution 2: O(n) time efficiency with O(1) space consumption

In order to find an even more efficient solution, let’s scan all elements in an array and try to find three increasing elements. The array {3, 2, 5, 1, 4, 7, 9, 6, 8} is taken as an example to simulate the process.

At first, all elements A[i], A[j], and A[k] have not been found, so three indexes i, j, and k are initialized as -1.

The number 3 is the first number to be scanned, and A[i] is updated as 3.

The next number to be scanned is the number 2. Notice that 2 is less than 3, and it is a better candidate of A[i]. The less A[i] is, the larger range A[j] and A[k] will have. Therefore, A[i] is updated as 2.

Let’s continue to scan the next number 5. Since 5 is greater the current A[i], it is a candidate of A[j]. A[j] is updated as 5.

The number 1 is scanned in the next round. Because 1 is less than the current A[j], it cannot be A[k]. Additionally, the number 1 is a candidate to be A[i] or A[j] in the future since it is less than the current A[i] than A[j]. However, either A[i] or A[j] can be updated as 1 at this time. If A[i] is updated as 1, A[i]<A[j] but i>j. If A[j] is updated as 1, A[i]>A[j]. Therefore, we store the number 1 into another variable named t.

We move on to scan the next number 4. Notice that the number 4 is less than A[j] again. At this time we have two numbers 1 (the stored variable t) and 4, so we have a new pair of numbers to be A[i] and A[j]. A[i] and A[j] are updated as 1 and 4 respectively.

The next number, 7, is greater than the current A[j], so A[k] is updated as 7. The process terminates.

The following table summarizes the step-by-step analysis above:

Step	Scanned Number	A[i]	A[j]	A[k]	t	Operation
1	3	3	-1	-1	-1	Update A[i]
2	2	2	-1	-1	-1	Update A[i]
3	5	2	5	-1	-1	Update A[j]
4	1	2	5	-1	1	Update t
5	4	1	4	-1	-1	Update A[i], A[j] and t
6	7	1	4	7	-1	Update A[k]. Terminate.

The strategy of this solution is to store as less value to A[i] and A[j] as possible, in order to enlarge the value range for steps in the future.

With our step-by-step analysis, we could implement this solution with the following C++ code:

void increasingIndex_2(int* nums, int length, int* i, int* j, int* k)

{

    if(nums == NULL || length <= 0 || i == NULL || j == NULL || k == NULL)

        return;

    *i = *j = *k = -1;

    int backup = -1;

    int index;

    for(index = 0; index < length; ++index)

    {

        if(*i == -1)

        {

            *i = index;

        }

        else if(*j == -1)

        {

            if(nums[index] > nums[*i])

                *j = index;

            else

                *i = index;

        }

        else if(nums[index] > nums[*j])

        {

            *k = index;

            break;

        }

        else if(nums[index] < nums[*j])

        {

            if(backup != -1)

            {

                if(nums[index] > nums[backup])

                {

                    *i = backup;

                    *j = index;

                    backup = -1;

                }

                else if (nums[index] < nums[backup])

                {

                    backup = index;

                }

            }

            else if(nums[index] < nums[*j])

                backup = index;

        }

    }

    if(index == length)

        *i = *j = *k = -1;

}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. 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 him via zhedahht@gmail.com . Thanks.