Monday, December 24, 2012

My Book "Coding Interview: Questions, Analysis & Solutions" Was Published

Thanks to the readers of the blogs, whose encouragement helped me make the decision to write a book on coding interviewers. Now the book "Coding Interviews: Questions, Analysis and Solutions" has been published by Apress, and the cover page is shown as below.
 
The detailed information about this book is available on the Apress website. Additionally, we may also find this book in Amazon.com.
 

Summary of Chapters


The first chapter focuses on the interview process. A typical interview process can be divided into two phases: phone interviews (including phone-screen interviews) and on-site interviews. Usually there are three steps in each round of interview, which are the behavioral interview, technical interview, and general Q/A. Tips are provided for each stage of interviews.

The next three chapters cover basic programming knowledge. Technical interview questions on four popular programming languages (C, C++, C#, and Java) are discussed in Chapter 2. The most common data structures (including arrays, strings, lists, trees, stacks, and queues) and algorithms (including search, sort, backtracking, dynamic programming, greedy algorithms, and bit operations) are discussed in Chapter 3 and Chapter 4 respectively.

Chapter 5 discusses three factors of high quality code. Interviewers usually expect candidates’ code to fulfill the functional requirements as well as cover corner cases and handle invalid inputs gracefully. After reading this chapter, you should get the idea so that you will write clear, complete, and robust code.

Three strategies to solve difficult coding interview problems are provided in Chapter 6. If hard problems are met during interviews, candidates should figure out solutions before they write code. After reading this chapter, you may get three strategies to solve problems: figures to visualize problems, step-by-step analysis on examples to simplify problems, and divide-and-conquer strategies to break complex problems into manageable pieces.

The topic of Chapter 7 is performance optimization. If there are multiple solutions to a problem, usually interviewers expect the most efficient one. The strategies to improve time efficiency and make trade-off decisions between time and space are discussed with several sample coding interview questions.

Chapter 8 summarizes various skills for interviews. Interviewers usually pay close attention to candidates’ communication and learning skills. Additionally, many interviewers like to examine candidates’ skills of reapplying knowledge, mathematical modeling, and divergent thinking.

Chapter 9 closes this book with two interview cases, which highlight good behavior expected by interviewers and the most common mistakes made by candidates.

 Distinguishing Features


This book analyzes coding problems from interviewers’ perspectives. There are many tips about the expected behaviors in this book, which are based on my own experiences as an interviewer at Autodesk, Microsoft, and Cisco. Moreover, many interview questions have different solutions. This book evaluates various solutions from an interviewer’s point of view. When you read the problem analyses, you will get the idea as to why some solutions are better than others, and you will grasp the capabilities required to the assure the quality of your code through completeness, robustness, and efficiency.

This book not only solves more than 100 interview problems, but also summarizes common strategies to conquer complex problems. When I analyzed and solved dozens of coding interview problems, I found that there are many general strategies that are quite helpful to solve other similar problems during interviews. For example, if an interview problem is quite complex, we may divide it into several small subproblems, and then solve the subproblems recursively. We can also utilize hash tables implemented with arrays to solve many interview problems about strings. Similar problems are grouped in sections in this book. Pay attention to the similarities among problems in a section and the general ideas to solve them. When you meet new but similar problems at your interviews, you may reapply the strategies illustrated in this book.

Sample questions in this book are real interview problems frequently met in the famous IT companies. The coding interview is the most important phase of the whole interview process in many companies, such as Facebook, Google, and Microsoft. The sample questions collected in this book are the most typical ones adopted by interviewers in these companies. Don’t be discouraged when you find that the problems in this book are not easy because interviews in big companies are not easy for most software engineers at first. You will find that there are relatively few problems that truly test the capabilities of programmers in meaningful ways. So, while you may not get a problem directly from this book, you should attain the skills required to handle whatever an interviewer can dish out. When you gradually master the strategies to solve problems summarized in this book, your capabilities to develop code and solve complex problems will be improved, and you will feel confident when interviewed by the Facebooks and Googles of the world.

Source code to solve sample interview problems along with a complete set of test cases to each problem is included. After candidates finish writing code, many interviewers will ask them to design some test cases to test their own code. Some candidates, especially fresh graduates, do not have clear ideas about how to design test cases. When you finish reading this book, you should know how to improve code quality with functional test cases, boundary test cases, performance test cases, and so on.
 

Sunday, February 19, 2012

No. 34 - String Path in Matrix


Question: How to implement a function to check whether there is a path for a string in a matrix of characters?  It moves to left, right, up and down in a matrix, and a cell for a movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.

For example, the matrix below with three rows and four columns has a path for the string “BCCED” (as highlighted in the matrix). It does not have a path for the string “ABCB”, because the first “B” in the string occupies the “B” cell in the matrix, and the second “B” in the string cannot enter into the same cell again.

A
B
C
E
S
F
C
S
A
D
E
E

Analysis: It is a typical problem about backtracking, which can be solved by storing a path into a stack.

Firstly, it is necessary to define a structure for 2-D positions, as below:

struct Position
{
    int x;
    int y;
};

The movements of four directions can be defined accordingly:

Position up = {0, -1};
Position right = {1, 0};
Position down = {0, 1};
Position left = {-1, 0};
Position dir[] ={up, right, down, left};

Since paths can start from any entry in a matrix, we have to scan every cell to check whether the character in it is identical to the first character of the string. If it is identical, we begin to explore a path from such a cell.

A path is defined as a stack. When a cell on path is found, we push its position into the stack. Additionally, we also define a matrix of Boolean masks to void entering a cell twice, which is denoted as visited. Based on these considerations, the skeleton of solution can be implemented as the following:

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
        return false;

    bool *visited = new bool[rows * cols];
    memset(visited, 0, rows * cols);

    for(int row = 0; row < rows; ++row)
    {
        for(int column = 0; column < cols; ++column)
        {
            if(matrix[row * cols + column] != str[0])
                continue;

            std::stack<Position> path;
            Position position = {column, row};
            path.push(position);
            visited[row * cols + column] = true;

            if(hasPathCore(matrix, rows, cols, str, path, visited))
                return true;
        }
    }

    return false;
}

Now let us analyze how to explore a path in details. Supposing we have already found k characters on a path, and we are going to explore the next step. We stand at the cell corresponding to the kth character of the path, and check whether the character in its neighboring cell at up, right, down, and left side is identical to the (k+1)th character of the string.

If there is a neighboring cell whose value is identical to the (k+1)th character of the string, we continue exploring the next step.

If there is no such a neighboring cell whose value is identical to the (k+1)th character of the string, it means the cell corresponding to the kth character should not on a path. Therefore, we pop it off a path, and start to explore other directions on the (k-1)th character.

Based on the analysis above, the function hasPathCore can be defined as:

bool hasPathCore(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
    if(str[path.size()] == '\0')
        return true;

    if(getNext(matrix, rows, cols, str, path, visited, 0))
        return hasPathCore(matrix, rows, cols, str, path, visited);

    bool hasNext = popAndGetNext(matrix, rows, cols, str, path, visited);
    while(!hasNext && !path.empty())
        hasNext = popAndGetNext(matrix, rows, cols, str, path, visited);

    if(!path.empty())
        return hasPathCore(matrix, rows, cols, str, path, visited);
   
    return false;
}
 
The function getNext is defined to explore the (k+1)th character on a path. When it returns true, it means the (k+1)th character on a path has been found. Otherwise, we have to pop the kth character off. The function getNext is implemented as below:

bool getNext(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited, int start)
{
    for(int i = start; i < sizeof(dir) / sizeof(Position); ++i)
    {
        Position next = {path.top().x + dir[i].x, path.top().y + dir[i].y};
        if(next.x >= 0 && next.x < cols
            && next.y >=0 && next.y < rows
            && matrix[next.y * cols + next.x] == str[path.size()]
            && !visited[next.y * cols + next.x])
        {
            path.push(next);
            visited[next.y * cols + next.x] = true;

            return true;
        }
    }

    return false;
}

When we found that the kth character should not be on a path, we call the function popAndGetNext to pop it off, and try on other directions from the (k-1)th character. This function is implemented as below:

bool popAndGetNext(char* matrix, int rows, int cols, char* str, std::stack<Position>& path, bool* visited)
{
    Position toBePoped = path.top();
    path.pop();
    visited[toBePoped.y * cols + toBePoped.x] = false;

    bool hasNext = false;
    if(path.size() >= 1)
    {
        Position previous = path.top();
        int deltaX = toBePoped.x - previous.x;
        int deltaY = toBePoped.y - previous.y;
        for(int i = 0; (i < sizeof(dir) / sizeof(Position) && !hasNext); ++i)
        {
            if(deltaX != dir[i].x || deltaY != dir[i].y)
                continue;

            hasNext = getNext(matrix, rows, cols, str, path, visited, i + 1);
        }
    }

    return hasNext;
}

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 him via zhedahht@gmail.com . Thanks. 

Thursday, February 16, 2012

No. 33 - Maximums in Sliding Windows


Question: Given an array of numbers and a sliding window size, how to get the maximal numbers in all sliding windows?

For example, if the input array is {2, 3, 4, 2, 6, 2, 5, 1} and the size of sliding windows is 3, the output of maximums are {4, 4, 6, 6, 6, 5}, as illustrated in Table1.

Sliding Windows in an Array
Maximums in Sliding Windows
[2, 3, 4], 2, 6, 2, 5, 1
4
2, [3, 4, 2], 6, 2, 5, 1
4
2, 3, [4, 2, 6], 2, 5, 1
6
2, 3, 4, [2, 6, 2], 5, 1
6
2, 3, 4, 2, [6, 2, 5], 1
6
2, 3, 4, 2, 6, [2, 5, 1]
5
Table 1: Maximums of all sliding windows with size 3 in an array {2, 3, 4, 2, 6, 2, 5, 1}. A pair of brackets indicates a sliding window.

Analysis: It is not difficult to get a solution with brute force: Scan numbers in every sliding window to get its maximal value. The overall time complexity is O(nk) if the length of array is n and the size of sliding windows is k.

The naïve solution is not the best solution. Let us explore better solutions.

Solution 1: Maximal value in a queue

A window can be viewed as a queue. When it slides, a number is pushed into its back, and its front is popped off. Therefore, the problem is solved if we can get the maximal value of a queue.

There are no straightforward approaches to getting the maximal value of a queue. However, there are solutions to get the maximal value of a stack, which is similar to the solution introduced in the blog “Stack with Function min()”. Additionally, a queue can also be implemented with two stacks (details are discussed in another blog “Queue implemented with Two Stacks”). 

If a new type of queue is implemented with two stacks, in which a function max() is defined to get the maximal value, the maximal value in a queue is the greater number of the two maximal numbers in two stacks.

This solution is workable. However, we may not have enough time to write all code to implement our own queue and stack data structures during interviews. Let us continue exploring a more concise solution.

Solution 2: Saving the maximal value into the front of a queue

Instead of pushing every numbers inside a sliding window into a queue, we try to push the candidates of maximum only into a queue. Let us take the array {2, 3, 4, 2, 6, 2, 5, 1} as an example to analyze the solution step by step.

The first number in the array is 2, we push it into a queue. The second number is 3, which is greater than the previous number 2. The number 2 should be popped off, because it is less than 3 and it has no chance to be the maximal value. There is only one number left in the queue when we pop 2 at the back and push 3 at the back. The operations are similar when we push the next number 4. There is only a number 4 remaining in the queue. Now the sliding window already has three elements, we can get the maximum value at the front of the queue.

We continue to push the fourth number.  It is pushed at the back of queue, because it is less than the previous number 4 and it might be a maximal number in the future when the previous numbers are popped off. There are two numbers, 4 and 2, in the queue, and 4 is the maximum.

The next number to be pushed is 6. Since it is greater than the existing numbers, 4 and 2, these two numbers can be popped off because they have no chance to be the maximum. Now there is only one number in the queue, which is 6, after the current number is pushed. Of course, the maximum is 6.

The next number is 2, which is pushed into the back of the queue because it is less than the previous number 6. There are two numbers in the queue, 6 and 2, and the number 6 at the front of the queue is the maximal value.

It is time to push the number 5. Because it is greater than the number 2 at the back of the queue, 2 is popped off and then 5 is pushed. There are two numbers in the queue, 6 and 5, and the number 6 at the front of the queue is the maximal value.

Now let us push the last number 1. It can be pushed into the queue. It is noticeable that the number at the front is beyond the scope the current sliding window, and it should be popped off.  How do we know whether the number at the front of the queue is out of sliding window? Rather than storing numbers in the queue directly, we can store indices instead. If the distance between the index at the front of queue and the index of the current number to be pushed is greater than or equal to the window size, the number corresponding to be the index at the font of queue is out of sliding window.

The analysis process above is summarized in Table 2.

Step
Number to Be Pushed
Numbers in Sliding Window
Indices in queue
Maximum in Window
1
2
2
0(2)

2
3
2, 3
1(3)

3
4
2, 3, 4
2(4)
4
4
2
3, 4, 2
2(4), 3(2)
4
5
6
4, 2, 6
4(6)
6
6
2
2, 6, 2
4(6), 5(2)
6
7
5
6, 2, 5
4(6), 6(5)
6
8
1
2, 5, 1
6(5), 7(1)
5
Table 2: The process to get the maximal number in all sliding windows with window size 3 in the array {2, 3, 4, 2, 6, 2, 5, 1}. In the column “Indices in queue”, the number inside a pair of parentheses is the number indexed by the number before it in the array.

We can implement a solution based on the analysis above. Some sample code in C++ is shown below, which utilizes the type deque of STL.

vector<int> maxInWindows(const vector<int>& numbers, int windowSize)
{
    vector<int> maxInSlidingWindows;
    if(numbers.size() >= windowSize && windowSize > 1)
    {
        deque<int> indices;

        for(int i = 0; i < windowSize; ++i)
        {
            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();

            indices.push_back(i);
        }

        for(int i = windowSize; i < numbers.size(); ++i)
        {
            maxInSlidingWindows.push_back(numbers[indices.front()]);

            while(!indices.empty() && numbers[i] >= numbers[indices.back()])
                indices.pop_back();
            if(!indices.empty() && indices.front() <= i - windowSize)
                indices.pop_front();

            indices.push_back(i);
        }
        maxInSlidingWindows.push_back(numbers[indices.front()]);
    }

    return maxInSlidingWindows;
}


Extension: Another solution to get the maximum of a queue

As we mentioned before, a sliding window can be viewed as a queue. Therefore, we can implement a new solution to get the maximal value of a queue based on the second solution to get the maximums of sliding windows.

The following is the sample code:

template<typename T> class QueueWithMax
{
public:
    QueueWithMax(): currentIndex(0)
    {
    }

    void push_back(T number)
    {
        while(!maximums.empty() && number >= maximums.back().number)
            maximums.pop_back();

        InternalData internalData = {number, currentIndex};
        data.push_back(internalData);
        maximums.push_back(internalData);

        ++currentIndex;
    }

    void pop_front()
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        if(maximums.front().index == data.front().index)
            maximums.pop_front();

        data.pop_front();
    }

    T max() const
    {
        if(maximums.empty())
            throw new exception("queue is empty");

        return maximums.front().number;
    }

private:
    struct InternalData
    {
        T number;
        int index;
    };

    deque<InternalData> data;
    deque<InternalData> maximums;
    int currentIndex;
};

Since this solution is similar to the second solution to get maximums of sliding windows, we won’t analyze the process step by step, and leave it as an exercise if you are interested.

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 him via zhedahht@gmail.com . Thanks.    

Tuesday, February 14, 2012

No. 32 - Remove Numbers in Array


Question: Given an array and a value, how to implement a function to remove all instances of that value in place and return the new length? The order of elements can be changed. It doesn't matter what you leave beyond the new length.

For example, if the input array is {4, 3, 2, 1, 2, 3, 6}, the result array after removing value 2 contains numbers {4, 3, 1, 3, 6}, and the new length of the remaining array is 5.

Analysis: The most straightforward solution for this problem is to scan the whole array from the beginning to end. When a target number is scanned, remove it and move all number behind it backward. The overall complexity is O(n2), since we have to move O(n) numbers when a target value is removed.

We can notice that it is not required to keep the order for the remaining numbers, and it does not care what numbers left beyond the new length. Therefore, we can move all target numbers to be removed to the end of the array.

Two pointers are defined to solve this problem: The first pointer (denoted as p1) moves forward until it reaches a number equal to the target value, which is initialized to the beginning of array. The other (denoted as p2) moves backward until it reaches a number not equal to the target value, which is initialized to the end of array. Two numbers pointed by p1 and p2 are swapped. We repeat the moving and swapping operations until all target numbers are scanned.

The sample code is shown as below:

unsigned int Remove(int* numbers, unsigned int length, int n)
{
    if(numbers == NULL || length < 1)
        return 0;

    int* p1 = numbers;
    int* p2 = numbers + length - 1;
    while(p1 < p2)
    {
        while(*p1 != n && (p1 - numbers) < length)
            ++p1;
        while(*p2 == n && (p2 - numbers) > 0)
            --p2;

        if(p1 < p2)
        {
            *p1 = *p2;
            *p2 = n;
        }
    }

    return p1 - numbers;
}

Because p1 points to the first target number in the array after scanning and swap, all elements at the left side of p2 are the remaining numbers. The new length can be calculated by the difference between the beginning of array and p1.

Since it is only required to scan the whole array once, and it costs O(1) time to swap a target value to the end of array, the overall time complexity is O(n) for an array with n numbers.

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 him via zhedahht@gmail.com . Thanks.   

Thursday, January 26, 2012

No. 31 - Binary Search Tree Verification


Question: How to verify whether a binary tree is a binary search tree?

For example, the tree in Figure 1 is a binary search tree.
Figure 1: A binary search tree

A node in binary tree is defined as:

struct BinaryTreeNode
{
    int                    nValue;
    BinaryTreeNode*        pLeft; 
    BinaryTreeNode*        pRight;
};

Analysis: Binary search tree is an important data structure. It has a specific character: Each node is greater than or equal to nodes in its left sub-tree, and less than or equal to nodes in its right sub-tree. 

Solution 1: Verify value range of each node

If a binary search tree is scanned with pre-order traversal algorithm, the value in a root node is accessed to at first. After the root node is visited, it begins to scan nodes in the left sub-tree. The value of left sub-tree nodes should be less than or equal to the value of the root node. If value of a left sub-tree node is greater than the value of the root node, it violates the definition of binary search tree. It is similar for the right sub-tree.

Therefore, when it visits a node in binary search tree, it narrows the value range of left sub-tree and right sub-tree under the current visited node. All nodes are visited with the pre-order traversal algorithm, and their value is verified. If value in any node violates its corresponding range, it is not a binary search tree.

The following sample code is implemented based on this pre-order traversal solution:

bool isBST_Solution1(BinaryTreeNode* pRoot)
{
    int min = numeric_limits<int>::min();
    int max = numeric_limits<int>::max();
    return isBSTCore_Solution1(pRoot, min, max);
}

bool isBSTCore_Solution1(BinaryTreeNode* pRoot, int min, int max)
{
    if(pRoot == NULL)
        return true;

    if(pRoot->nValue < min || pRoot->nValue > max)
        return false;

    return isBSTCore_Solution1(pRoot->pLeft, min, pRoot->nValue)
        && isBSTCore_Solution1(pRoot->pRight, pRoot->nValue, max);
}

In the code above, value of each node should be in the range between min and max. The value of the current visited node is the maximal value of its left sub-tree, and the minimal value of its right sub-tree, so it updates the min and max arguments and verifies sub-trees recursively.

Solution 2: Increasing in-order traversal sequence

The first solution is based on pre-order traversal algorithm. Let us have another try on in-order traversal. The in-order traversal sequence of the binary search tree in Figure 1 is: 4, 6, 8, 10, 12, 14 and 16. It is noticeable that the sequence is increasingly sorted.

Therefore, a new solution is available: Nodes in a binary tree is scanned with in-order traversal, and compare value of each node against the value of the previously visited node. If the value of the previously visited node is greater than the value of current node, it breaks the definition of binary tree.

This solution might be implemented in C++ as the following code:

 bool isBST_Solution2(BinaryTreeNode* pRoot)
{
    int prev = numeric_limits<int>::min();
    return isBSTCore_Solution2(pRoot, prev);
}

bool isBSTCore_Solution2(BinaryTreeNode* pRoot, int& prev)
{
    if(pRoot == NULL)
        return true;

    return isBSTCore_Solution2(pRoot->pLeft, prev) // previous node
        && (pRoot->nValue >= prev) // current node
        && isBSTCore_Solution2(pRoot->pRight, prev = pRoot->nValue); // next node
}

The argument prev of the function isBSTCore_Solution2 above is the value of the previously visited node in pre_order traversal.

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 him via zhedahht@gmail.com . Thanks.