No. 24 - Intersection of Sorted Arrays

Problem: Please implement a function which gets the intersection of two sorted arrays. Assuming numbers in each array are unique.

For example, if the two sorted arrays as input are {1, 4, 7, 10, 13} and {1, 3, 5, 7, 9}, it returns an intersection array with numbers {1, 7}.

Analysis: An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. We have two better solutions.

Solution 1: With O(m+n) Time

It is noticeable that the two input arrays are sorted. Supposing a number number1 in array1 equals to a number number2 in array2, the numbers after number1 in array1 should be greater than the numbers before number2 in array2. Therefore, it is not necessary to compare the numbers after number1 in array1 with numbers before number2 in array2. It improves efficiency since many comparisons are eliminated.

The sample code for this solution is shown below:

void GetIntersection_solution1(const vector<int>& array1,

                     const vector<int>& array2,

                     vector<int>& intersection)

{

    vector<int>::const_iterator iter1 = array1.begin();

    vector<int>::const_iterator iter2 = array2.begin();

    intersection.clear();

    while(iter1 != array1.end() && iter2 != array2.end())

    {

        if(*iter1 == *iter2)

        {

            intersection.push_back(*iter1);

            ++ iter1;

            ++ iter2;

        }

        else if(*iter1 < *iter2)

            ++ iter1;

        else

            ++ iter2;

    }

}

Since it only requires to scan two arrays once, its time complexity is O(m+n).

Solution 2: With O(nlogm) Time

As we know, a binary search algorithm requires O(logm) time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n). Therefore, we can implement a new and better solution based on binary search in such a situation. 

For instance, the following same code is suitable when array1 is much longer than array2.

/* === Supposing array1 is much longer than array2 === */

void GetIntersection_solution2(const vector<int>& array1,

                     const vector<int>& array2,

                     vector<int>& intersection)

{

    intersection.clear();

   

    vector<int>::const_iterator iter1 = array1.begin();

    while(iter1 != array1.end())

    {

        if(binary_search(array2.begin(), array2.end(), *iter1))

            intersection.push_back(*iter1);

    }

}

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. 23 - Palindrome Numbers

Problem: Please implement a function which checks whether a number is a palindrome or not. For example, 121 is a palindrome, while 123 is not.

Analysis: Many candidates can get a straight solution which converts the input number into a string first. However, it is not what interviewers expect usually.

Solution 1: Convert a Number into a String

It is easy to check whether a number is palindrome or not: We can check whether the first character and the last one are identical, and then check the second character and the second one from end, and so on. Therefore, we can firstly convert the input number into a string via the function sprintf, and then check whether the string is a palindrome.

This solution can be implemented as the following code:

bool IsPalindrome_solution1(unsigned int number)

{

    const int NUMBER_LENGTH = 20;

    char string[NUMBER_LENGTH];

    sprintf(string, "%d", number);

    return IsPalindrome(string);

}

bool IsPalindrome(const char* const string)

{

    bool palindrome = true;

    if(string != NULL)

    {

        int length = strlen(string);

        int half = length >> 1;

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

        {

            if(string[i] != string[length - 1 - i])

            {

                palindrome = false;

                break;

            }

        }

    }

    return palindrome;

}

Usually the solution above is not the one expected by interviewers. One reason is that it is intuitive while interviewers expect something innovative, and the other is that it requires auxiliary memory to store the converted string.

Solution 2: Compose a Reversed Number

As we know, it is easy to get digits from right to left via / and % operators. For example, digits in the number 123 are 3, 2 and 1. We can construct a reversed number 321 with these three digits. And then we check whether the reverse number is identical to the original one. If it is, the original number is a palindrome.

Its corresponding code is shown below:

bool IsPalindrome_solution2(unsigned int number)

{

    int reversed = 0;

    int copy = number;

    while(number != 0)

    {

        reversed = reversed * 10 + number % 10;

        number /= 10;

    }

    return (reversed == copy);

}

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. 22 - Turning Number in an Array

Problem: Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

Analysis: As we know, the binary search algorithm is suitable to search a number in a sorted array. Since the input array for this problem is partially sorted, we may also have a try with binary search.

Let us try to get the middle number in an array. The middle number of array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 5 (the fourth number). It is greater than its previous number 4, and less than its next number 10, so it is in the increasing sub-array. Therefore, numbers before 5 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9, 8, 7, 6}, and the number 9 is in the middle of them. Since 9 is less than is previous number 10 and greater than its next number 8, it is in the decreasing sub-array. Therefore, numbers after 9 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9}, and the number 10 is in the middle. It is noticeable that number 10 is greater than its previous number 5 and greater than its next number 9, so it is the maximum number. That is to say, the number 10 is the turning number in the input array.

We can see the process above is actually a classic binary search. Therefore, we can implement the required function based on binary search algorithm, as listed below:

int TurningNumberIndex(int* numbers, int length)

{

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

        return -1;

    int left = 0;

    int right = length - 1;

    while(right > left + 1)

    {

        int middle = (left + right) / 2;

        if(middle == 0 || middle == length - 1)

            return -1;

        if(numbers[middle] > numbers[middle - 1] &&

            numbers[middle] > numbers[middle + 1])

            return middle;

        else if(numbers[middle] > numbers[middle - 1] &&

            numbers[middle] < numbers[middle + 1])

            left = middle;

        else

            right = middle;

    }

    return -1;

}

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. 21 - Push and Pop Sequences of Stacks

Problem: Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not. 

For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not.

Analysis: An intuitive thought on this problem is to create an auxiliary stack. We push the numbers in the first sequence one by one, and try to pop them out according to the order in the second sequence.

Take the sequence 4, 5, 3, 2, 1 as an example to analyze the process to push and pop. The first number to be popped is 4, so we need to push it into a stack. The pushing order is defined in the first sequence, where there are numbers 1, 2 and 3 prior to 4. Therefore, numbers 1, 2, and 3 are pushed into a stack before 4 is pushed. At this time, there are 4 numbers in a stack, which are 1, 2, 3 and 4, with 4 on top. When 4 is popped, numbers 1, 2 and 3 are left. The next number to be popped is 5, which is not on top of stack, so we have to push numbers in the first sequence into stack until 5 is pushed. When number 5 is on top of a stack, we can pop it. The next three numbers to be popped are 3, 2 and 1. Since these numbers are on top of a stack before pop operations, they can be popped directly. The whole process to push and pop is summarized in Table 1.

Step	Operation	Stack Status	Popped	Step	Operation	Stack Status	Popped
1	Push 1	1		6	Push 5	1, 2, 3, 5
2	Push 2	1, 2		7	Pop	1, 2, 3	5
3	Push 3	1, 2, 3		8	Pop	1, 2	3
4	Push 4	1, 2, 3, 4		9	Pop	1	2
5	Pop	1, 2, 3	4	10	Pop		1

Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 5, 3, 2, 1

Let us continue to analyze another pop sequence 4, 3, 5, 1, 2. The process to pop the first number 4 is similar to the process above. After the number 4 is popped, 3 is on the top of stack and it can be popped. The next number to be popped is 5. Since it is not on top, we have to push numbers in the first sequence until the number 5 is pushed. The number 5 can be popped when it is pushed onto the top of a stack. After 5 is popped out, there are only two numbers 1 and 2 left in stack. The next number to be popped is 1, but it is not on the top of stack. We have to push numbers in the first sequence until 1 is pushed. However, all numbers in the first sequence have been pushed. Therefore, the sequence 4, 3, 5, 1, 2 is not a pop sequence of the stack with push sequence 1, 2, 3, 4, 5. The whole process to push and pop is summarized in Table 2.

Step	Operation	Stack Status	Popped	Step	Operation	Stack Status	Popped
1	Push 1	1		6	Pop	1, 2	3
2	Push 2	1, 2		7	Push 5	1, 2, 5
3	Push 3	1, 2, 3		8	Pop	1, 2	5
4	Push 4	1, 2, 3, 4		The next number to be popped is 1, which is neither on the top of stack, nor in the remaining numbers of push sequence.
5	Pop	1, 2, 3	4

Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 3, 5, 1, 2

According to the analysis above, we get a solution to check whether a sequence is a pop sequence of a stack or not. If the number to be popped is currently on top of stack, just pop it. If it is not on the top of stack, we have to push remaining numbers into the auxiliary stack until we meet the number to be popped. If the next number to be popped is not remaining in the push sequence, it is not a pop sequence of a stack. The following is some sample code based on this solution:

bool IsPopOrder(const int* pPush, const int* pPop, int nLength)

{

    bool bPossible = false;

    if(pPush != NULL && pPop != NULL && nLength > 0)

    {

        const int* pNextPush = pPush;

        const int* pNextPop = pPop;

        std::stack<int> stackData;

        while(pNextPop - pPop < nLength)

        {

            // When the number to be popped is not on top of stack,

            // push some numbers in the push sequence into stack

            while(stackData.empty() || stackData.top() != *pNextPop)

            {

                // If all numbers have been pushed, break

                if(pNextPush - pPush == nLength)

                    break;

                stackData.push(*pNextPush);

                pNextPush ++;

            }

            if(stackData.top() != *pNextPop)

                break;

            stackData.pop();

            pNextPop ++;

        }

        if(stackData.empty() && pNextPop - pPop == nLength)

            bPossible = true;

    }

    return bPossible;

}

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. 20 - Number of 1 in a Binary

Problem: Please implement a function to get the number of 1s in an integer. For example, the integer 9 is 1001 in binary, so it returns 2 since there are two bits of 1s.

Analysis: It looks like a simple question about binary numbers, and we have many solutions for it. Unfortunately, the most intuitive solution for many candidates is incorrect. We should be careful.

Solution 1: Check the most right bit, possibly with endless loop

When candidates are interviewed with this problem, many of them find a solution in short time: check whether the most right bit is 0 or 1, and then right shit the integer one bit and check the most right bit again. It continues in a loop until the integer becomes 0. How to check whether the most right bit of an integer is 0 or 1? It is simple since we have AND operation. There is only one bit of 1, which is the most right bit, in the binary format of integer 1. When we have AND operation on an integer and 1, we can check whether the most right bit is 0 or 1. When the result of AND operation is 1, it indicates the right most bit is 1; otherwise it is 0. We can implement a function base on this solution quickly:

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
            count ++;

        n = n >> 1;
    }

    return count;
}

Interviewers may ask a question when they are told this solution: What is the result when the input integer is a negative number such as 0x80000000? When we right shift the negative number 0x80000000 a bit, it become 0xC0000000 rather than 0x40000000, which is the result to move the first bit of 1 to the second bit. The integer 0x8000000 is negative before shift, so we should guarantee it is also negative after shift. Therefore, when a negative integer is right shifted, the first bit is set as 1 after the right shift operation. If we continue to shift to right side, a negative integer will be 0xFFFFFFFF eventually and it is trapped in an endless loop.

Solution 2: Check the most right bit, with left shift operation on 1

We should not right shift the input integer to avoid endless loop. Instead of shifting the input integer n to right, we may shift the number 1 to left. We may check firstly the least important bit of n, and then shift the number 1 to left, and continue to check the second least important bit of n. Now we can rewrite our code based on this solution:

int NumberOf1(int n)

{

    int count = 0;

    unsigned int flag = 1;

    while(flag)

    {

        if(n & flag)

            count ++;

        flag = flag << 1;

    }

    return count;

}

In the code above, it loops 32 times on 32-bit numbers.

Solution 3: Creative solution

Let us analyze that what happens when a number minus 1. There is at least one bit 1 in a non-zero number. We firstly assume the right most bit is 1. It becomes 0 if the number minus 1 and other bits keep unchanged. This result is identical to the not operation on the most right bit of a number, which also turns the right most bit from 1 into 0.

Secondly we assume the right most bit is 0. Since there is at least one bit 1 in a non-zero number, we suppose the m^th bit is the most right bit of 1. When it minus 1, the m^th bit becomes 0, and all 0 bits behind the m^th bit become 1. For instance, the second bit of binary number 1100 is the most right bit of 1. When it minus 1, the second bit becomes 0, and the third and fourth bits become 1, so the result is 1011.

In both situations above, the most right of bit 1 becomes 0 when it minus 1. When there are some 0 bits at right side, all of them become 1. The result of bit and operation on the original number and minus result is identical to result to modify the most right 1 into 0. Take the binary number 1100 as an example again. Its result is 1011 when it minus 1. The result of and operation on 1100 and 1011 is 1000. If we change the most right of 1 bit in number 1100, it also becomes 1000.

The analysis can be summarized as: If we first minus a number with 1, and have and operation on the original number and the minus result, the most right of 1 bit becomes 0. We continue these operations until the number becomes 0. We can develop the following code accordingly:

int NumberOf1(int n)

{

    int count = 0;

    while (n)

    {

        ++ count;

        n = (n - 1) & n;

    }

    return count;

}

The number of times in the while loops equals to the number of 1 in the binary format of input n.

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. 19 - Left Rotation of String

Problem: Left rotation of a string is to move some leading characters to its tail. Please implement a function to rotate a string. 

For example, if the input string is “abcdefg” and a number 2, the rotated result is “cdefgab”.

Analysis: It looks difficult to get rules of left rotation on a string. Fortunately, the 7^th problem in this series “Reverse Words in a Sentence” can give us some hints.

If we input a sentence with two words “hello world” for the problem “Reverse Words in a Sentence”, the reversed result should be “world hello”. It is noticeable that the result “world hello” can be viewed as a rotated result of “hello world”. It becomes “world hello” when we move some leading characters of string “hello world” to its ending. Therefore, this problem is quite similar to problem “Reverse Words in a Sentence”.

Let us take a string “abcdefg” as an example. We divide it into two parts: the first part contains the two leading characters “ab”, and the second part contains all other characters “cdefg”. We firstly reverse these two parts separately, and the whole string becomes “bagfedc”. It becomes “cdefgab” if we reverse the whole string, which is the expected result of left rotation with 2.

According to the analysis above, we can see that left rotation of a string can be implemented calling a Reverse function three times to reverse a segment or whole string. The sample code is shown below:

char* LeftRotateString(char* pStr, int n)

{

    if(pStr != NULL)

    {

        int nLength = static_cast<int>(strlen(pStr));

        if(nLength > 0 && n > 0 && n < nLength)

        {

            char* pFirstStart = pStr;

            char* pFirstEnd = pStr + n - 1;

            char* pSecondStart = pStr + n;

            char* pSecondEnd = pStr + nLength - 1;

            // Reverse the n leading characters

            Reverse(pFirstStart, pFirstEnd);

            // Reverse other characters

            Reverse(pSecondStart, pSecondEnd);

            // Reverse the whole string

            Reverse(pFirstStart, pSecondEnd);

        }

    }

    return pStr;

}

The function Reverse is shown in “Reverse Words in a Sentence”, so we are not going to repeat it here.

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.