Wednesday, February 6, 2013

No. 39 - Stacks Sharing an Array

Problem 1: How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space?

Analysis: An array has two ends, so each of the two stacks may grow from an end in the array. Figure 1 below shows the initial status of the array and two stacks (assuming the capacity of the array is 10).
Figure 1: Initial status of the array and two stacks
Since two stacks are empty at first, so indexes of top items are initialized as -1 and 10 at first.
When items are pushed into first stack, it grows from left to right. Similarly, the second stack grows from right to left when items are items are pushed into it. For example, Figure 2 shows the status when three items a, b and c are pushed into the first stack, and d, e are pushed into the second stack.

Figure 2: The status after three items are pushed into the first stack and two items are pushed into the second stack 

No more items can be pushed into stacks when two top items are adjacent to each other, because all space in the array has been occupied.

Our solution can be implemented with the following C++ class:
template <typename T, int capacity> class TwoStacks
{
public:
    TwoStacks()
    {
        topFirst = -1;
        topSecond = capacity;
    }
    T top(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");
        if(stackIndex == 0)
            return items[topFirst];
        return items[topSecond];
    }
    void push(int stackIndex, T item)
    {
        validateIndex(stackIndex);
        if(full())
            throw new exception("All space has been occupied.");
        if(stackIndex == 0)
            items[++topFirst] = item;
        else
            items[--topSecond] = item;
    }
    void pop(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");
        if(stackIndex == 0)
            --topFirst;
        else
            ++topSecond;
    }
    bool empty(int stackIndex)
    {
        if(stackIndex == 0 && topFirst == -1)
            return true;
        if(stackIndex == 1 && topSecond == capacity)
            return true;
        return false;
    }
private:
    bool full()
    {
        return (topFirst >= topSecond - 1);
    }
    void validateIndex(int stackIndex)
    {
        if(stackIndex < 0 || stackIndex > 1)
            throw new exception("Invalid Stack Index.");
    }
private:
    T items[capacity];
    int topFirst;
    int topSecond;
};

Problem 2: How can you implement n (n > 2) stacks in a single array, where no stack overflows until no space left in the entire array space?

Analysis: An array only has two ends, so we need new strategies to implement more than two stacks in a single array.

We may implement the array like a list, where each item in the array has a link to another item. When an item has not been occupied by any stacks and it is available, it is linked to the next available item. When an item is pushed into a stack, it is linked to the previous item in the stack. That’s to say, there are n + 1 list in total in the system if there are n stacks sharing an array, a list for the available space left in the array, and a list for each stack.

Let’s take three stacks sharing an array with capacity 10 as an example. Figure 3 shows the initial status for the array and stacks. Each item in the array has two blocks, one for item data and the other for the index of another block.
Figure 3: Initial status of three stacks sharing an array


As shown in Figure 3, each item is linked to the next item (the link block of the ith item is i+1). The head of list for available items in the array points to the item at position 0, which is the Ava pointer in the figure. Since three stacks are empty, their top (Top1, Top2 and Top3 in the figure) are initialized as -1.

Let’s try to push an item a into the first stack. Currently the first available item is at the position 0, so we set its data block as a. The link block of the item is 1, which means the next available item is at the position 1, so we update the Ava pointer to the position 1. Additionally, the link block of the item at the position 1 should be updated to -1, the previous top index of the first stack. Lastly, we update to top index of the first stack to 0. The status of the array and stacks are shown in Figure 4.
Figure 4: The status after pushing a into the first stack
Let’s push two more items b and c into the first stack. The operations are similar as before, and the status is shown in Figure 5.
Figure 5: The status after adding two more items, b and c, into the first stack
In the next step we are going to push another d into the second stack. Most operations are similar as before. The link block in the item at the position 3 is updated to -1, since the second stack is empty before and its top index is -1 previously. And then the top index of the second stack is updated to 3. The status after adding d into the second stack is shown in Figure 6.

Figure 6: The status after pushing d into the second stack
If we continue to push three more item e, f, and g into the second stack, the status is shown in Figure 7.
Figure 7: The status after pushing three more items, e, f, and g, into the second stack
At this time we are going to pop an item from the first stack. Since the top index of the first stack is 2, the item to be popped off is at the position 2. The link value in that item is 1, which means the previous top in the first stack is at the position 1 in the array, so we update the top index of the first stack as 1. Now the item at the position 2 becomes available, it should be linked to the list for available items. We move the Ava pointer to 2, and then update the link value of the item at the position 2 as 7, which is the previous head position of the list for available items. The status is shown in Figure 8.
Figure 8: The status after popping an item from the first stack
If we pop an item off the second stack, the item at the position 6 will be linked to the list for available items too. Figure 9 depicts the status after the related operations.
Figure 9: The status after popping an item off the second stack
If we push h into the third stack, it will be placed into the item at the position 6 because Ava points to that item. The next available item is at the position 2 (the link value in the item at the position 6). Therefore, the head of the list for available items points to location 2, as shown in Figure 10.
Figure 10: The status after pushing h into the third stack
Let’s continue to push four more items into the third stack, i, j, k, and l. The status after these four items are pushed is shown in Figure 11. At this time, there are two items in the first stack (a and b), three items in the second stack (d, e and f), and five items in the third stack (h, i, j, k, and l). Please note that items inside a stack are not necessarily adjacent. 
Figure 11: The status after pushing i, j, k, l into the third stack
After l is pushed into the item at the position 9, the Ava pointer is update to -1 (the previous link value in the item at the position 9), which means all items in the array have been occupied by stacks. We can’t push more items until some items are popped off.
The source code in C++ to implement stacks sharing an array is listed below:
template <typename T, int capacity, int count> class Stacks
{
public:
    Stacks()
    {
        int i;
        for(i = 0; i < capacity - 1; ++i)
            items[i].link = i + 1;
        items[i].link = -1;
        emptyHead = 0;

        for(i = 0; i < count; ++i)
            stackHead[i] = -1;
    }

    T top(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");

        return items[stackHead[stackIndex]].data;
    }

    void push(int stackIndex, const T& item)
    {
        validateIndex(stackIndex);
        if(full())
            throw new exception("All space has been occupied.");

        Item<T>& block = items[emptyHead];
        int nextEmpty = block.link;

        block.data = item;
        block.link = stackHead[stackIndex];
        stackHead[stackIndex] = emptyHead;

        emptyHead = nextEmpty;
    }

    void pop(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");

        Item<T>& block = items[stackHead[stackIndex]];
        int nextItem = block.link;

        block.link = emptyHead;
        emptyHead = stackHead[stackIndex];
        stackHead[stackIndex] = nextItem;
    }

    bool empty(int stackIndex)
    {
        return (stackHead[stackIndex] < 0);
    }

private:
    void validateIndex(int stackIndex)
    {
        if(stackIndex < 0 || stackIndex >= count)
            throw new exception("Invalid index of stack.");
    }

    bool full()
    {
        return (emptyHead < 0);
    }

private:
    template <typename T> struct Item
    {
        T data;
        int link;
    };

private:
    Item<T> items[capacity];
    int emptyHead;
    int stackHead[count];
};

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. 

Tuesday, February 5, 2013

No. 38 - Digits in a Sequence

Problem: Numbers are serialized increasingly into a sequence in the format of 0123456789101112131415..., which each digit occupies a position in the sequence. For instance, the digit in the position 5 is 5, in the position 13 is 1, in the position 19 is 4, and so on.

Please write a function/method to get the digit on any given position.

Analysis: Let's take a specific position as an example to analyze this problem. For example, what is the digit at the position 1001?

The first 10 digits are for 10 numbers with only one digit (0, 1, 2, ..., 9). Since the position 1001 is beyond of the range of the first 10 digits, we continue to look for the digit at the position at 991 (991 = 1001 - 10) in the following sequence.

The next 180 digits are for 90 numbers with two digits, from 10 to 99. Since 991 is greater than 180, the digit at position 991 is beyond the numbers with two digits. Let's continue to get the 811 (811 = 991-180) in the following sequence.

The next 2700 digits are for 900 numbers with three digits, from 100 to 999. Since 811 is less than 2700, the position 811 should be inside a number with three digits.

Every number has three digits, so the position 811 should be the second digit of the 270-th nubmer starting from 100 (811 = 270 * 3 + 1). Therefore, the digit at the position 811 is the second digit in the number 370, which is digit 7.

The overall solution can be implemented with the following code:

int digitAtIndex(int index)
{
    if(index < 0)
        return -1;

    int digits = 1;
    while(true)
    {
        int numbers = countOfIntegers(digits);
        if(index < numbers * digits)
            return digitAtIndex(index, digits);

        index -= digits * numbers;
        digits++;
    }
    return -1;
}

We can get the count of integers with n digits via the following function:

int countOfIntegers(int digits)
{
    if(digits == 1)
        return 10;

    int count = 1;
    for(int i = 1; i < digits; ++i)
        count *= 10;
    return 9 * count;
}

After we know the digit inside an integer with m digits, we could get the digit with the following function:

int digitAtIndex(int index, int digits)
{
    int number = beginNumber(digits) + index / digits;
    int indexFromRight = digits - index % digits;
    for(int i = 1; i < indexFromRight; ++i)
        number /= 10;
    return number % 10;
}

In the function above, we need to know the first number with m digits. The first number with two digits is 10, and the first number with three digits is 100. These numbers can be calculated with the function below:

int beginNumber(int digits)
{
    if(digits == 1)
        return 0;

    int begin = 1;
    for(int i = 1; i < digits; ++i)
        begin *= 10;
    return begin;
}

The source code with unit tests is available at http://ideone.com/yogYbu.

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.
 

Monday, February 4, 2013

No. 37 - Missing Number in an Array

Problem 1: An array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.

Analysis: If we scan all numbers in the array, we could get the sum of all numbers. The sum is denoted as sum1.

Additionally, we could also get the sum of all numbers in the range from 0 to n - 1, which is n*(n-1)/2. The sum is denoted as sum2.

The only number missing in the array is the difference between sum2 and sum1.

This solution can be implemented with the following code:

int getOnceNumber_unsorted(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        return -1;

    int sum1 = 0;
    for(int i = 0; i < length; ++i)
        sum1 += numbers[i];

    int sum2 = length * (length + 1) / 2;
    return sum2 - sum1;
}

Since we have to scan all numbers in the array, it costs O(n) time if the size of array is n.

Problem 2: An sorted array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.

Analysis: Of couse, we could use the solution above to solve this problem, which costs O(n) time. This solution does not utilize the properties of sorted arrays.

Since numbers from 0 to n - 1 are sorted in an array, the first numbers should be same as their indexes. That's to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.

The number m + 1 is located at a cell with index m, The number m + 2 is located at a cell with index m + 1, and so on. We can see that, the missing number m is the first cell whose value is not identical to its value.

Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(lgn) time based on the binary search algorithm as implemented below:

int getOnceNumber_sorted(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        return -1;

    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }
  
    if(left == length ) // corrected by Kyunghee Kim
        return length;

    return -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.

Sunday, February 3, 2013

No. 36 - Permutation

Questions: Please print all permutations of a given string. For example, print “abc”, “acb”, “bac”, “bca”, “cab”, and “cba” when given the input string “abc”.

Analysis: For many candidates, it is not a simple problem to get all permutations of a set of characters. In order to solve such a problem, candidates might try to divide it into simple subproblems. An input string is partitioned into two parts. The first part only contains the first characters, and the second part contains others. As shown in Figure 1, a string is divided into two parts with different background colors.

Figure 1: The process to get permutations of a string. (a) A string is divided into two parts of which the
first part only contains the first character, and the second part contains others (with gray background). (b)
All characters in the second part are swapped with the first character one by one.

This solution gets permutations of a given string with two steps. The first step is to swap the first
character with the following characters one by one. The second step is to get permutations of the string excluding the first character. Take the sample string “abc” as an example. It gets permutations of “bc” when the first character is ‘a’. It then swaps the first character with ‘b’, gets permutations of “ac”, and finally gets permutation of “ba” after swapping the first character with ‘c’.

The process to get permutations of a string excluding the first character is similar to the process to
get permutations of a whole string. Therefore, it can be solved recursively, as shown below:

 
void Permutation(char* pStr)
{
    if(pStr == NULL)
        return;
    PermutationCore(pStr, pStr);
}

void PermutationCore(char* pStr, char* pBegin)
{
    char *pCh = NULL;
    char temp;
    if(*pBegin == '\0')
    {
        printf("%s\n", pStr);
    }
    else
    {
        for(pCh = pBegin; *pCh != '\0'; ++ pCh)
        {
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;

            PermutationCore(pStr, pBegin + 1);

            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

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.

Monday, January 28, 2013

No. 35 - Depth of Binary Trees

Question 1: How do you get the depth of a binary tree? Nodes from the root to a leaf form a path. Depth of a binary tree is the maximum length of all paths. For example, the depth of the binary tree in Figure 1 is 4, with the longest path through nodes 1, 2, 5, and 7.
Figure 1: A binary Tree with depth 4
Analysis: We have discussed how to store nodes of a path in a stack while traversing a binary tree in the blog "Paths with Specified Sum in Binary Tree ". The depth of a binary tree is the length of the longest path. This solution works, but it is not the most concise one.
The depth of a binary tree can be gotten in another way. If a binary tree has only one node, its depth is 1. If the root node of a binary tree has only a left subtree, its depth is the depth of the left subtree plus 1. Similarly, its depth is the depth of the right subtree plus 1 if the root node has only a right subtree. What is the depth if the root node has both left subtree and right subtree? It is the greater value of the depth of the left and right subtrees plus 1.
 
For example, the root node of the binary tree in Figure 1 has both left and right subtrees. The depth of the left subtree rooted at node 2 is 3, and the depth of the right subtree rooted at node 3 is 2, so the depth of the whole binary tree is 4; 1 plus the greater value of 3 and 2.
 
It is easy to implement this solution recursively, with little modification on the post-order traversal
algorithm, as shown below:
 
int TreeDepth(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return 0;
    int nLeft = TreeDepth(pRoot->m_pLeft);
    int nRight = TreeDepth(pRoot->m_pRight);
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
 
Question 2: How do you verify whether a binary tree is balanced? If the depth difference between a left subtree and right subtree of any node in a binary tree is not greater than 1, it is balanced. For instance, the binary tree in Figure 1 is balanced.
 
Analysis:
 
Solution 1: Visiting Nodes for Multiple Times

According to the definition of balanced binary trees, this problem can be solved by getting the depth difference between the left and right subtrees of every node. When a node is visited, the function depth is invoked to get the depth of its left and right subtrees. If the depth different is 1 at most for all nodes in a binary tree, it is balanced. This solution can be implemented based on the TreeDepth discussed in the preceding problem, as shown below:
 
bool IsBalanced_Solution1(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return true;
    int left = TreeDepth(pRoot->m_pLeft);
    int right = TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if(diff > 1 || diff < -1)
        return false;
    return IsBalanced_Solution1(pRoot->m_pLeft)
        && IsBalanced_Solution1(pRoot->m_pRight);
} 


This solution looks concise, but it is inefficient because it visits some nodes for multiple times. Take the binary tree in Figure 1 as an example. When the function TreeDepth takes the node 2 as a parameter, it visits nodes 4, 5, and 7. When it verifies whether the binary tree rooted at node 2 is balanced, it visits nodes 4, 5, and 7 again. Obviously, we could improve performance if nodes are visited only once.
 
Solution 2: Visiting Every Node Only Once
 
If a binary tree is scanned with the post-order algorithm, its left and right subtrees are traversed before the root node. If we record the depth of the currently visited node (the depth of a node is the maximum length of paths from the node to its leaf nodes), we can verify whether the subtree rooted at the currently visited node is balanced. If any subtree is unbalanced, the whole tree is unbalanced.
This new solution can be implemented as shown in below:
 
bool IsBalanced_Solution2(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}
bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }
    int left, right;
    if(IsBalanced(pRoot->m_pLeft, &left) && IsBalanced(pRoot->m_pRight, &right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }
    return false;
}
 
 
After verifying left and right subtrees of a node, the solution verifies the subtree rooted at the current visited node and passes the depth to verify its parent node. When the recursive process returns to the root node finally, the whole binary tree is verified. 
 
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. 

 

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.