Category Archives: Interview

PutLong Version 3

Problem statement summary: this is a popular interview question in which you implement a void putlong(long n) function to write the long integer n to the console. To make the problem more challenging, interviewers often impose the following restrictions:

  1. Only use putchar() and no other functions (ltoa, sprintf, …)
  2. Do not create a buffer to store the digits
  3. Do not use a stack as a means to store and reverse the digits
  4. Do not use recursion

In my first attempt, I reversed the digits order, then extracted them from right to left and printed by means of putchar(). My solution did not work for numbers with trailing zeros such as 1900.

Instead of fixing my code, I approached the problem from a different angle. In my second attempt, I extracted the digits from left to right and that seems to take care of the trailing zeros problem. This solution worked for all of my test cases except when n is equal to long.MinValue(), or -9223372036854775808 (tested with Visual Studion 2005 in 32-bit Windows Vista).

After some debugging, I finally pin-pointed the problem. When n is long.MinValue, and extractor is -1, n / extractor == n because of overflow which prevented us from building the proper extractor, hence the bug (line 14 in the second solution).

To fix this problem, we can initialize the extractor to -10 instead of -1 for n == long.MinValue. Therefore, the expression in line 14 will become:

extractor = n == long.MinValue ? -10 : (n < 0 ? -1 : 1)

For portability, we do not want to rely on long.MinValue, so we can modify the above expression to:

extractor = n < -9 ? -10 : (n < 0 ? -1 : 1)

That should fixes the code. Here is the complete listing:

 

<div><pre>    1 /// <summary>
   2 /// Writes a long number to the console.
   3 /// Constraints:
   4 /// 1. Use only putchar() and no other means (itoa, sprintf, ...)
   5 /// 2. Do not use array to store the digits
   6 /// 3. No recursion
   7 /// </summary>
   8 /// <param name="n">The number to write to the console</param>
   9 public static void PutLong(long n)
  10 {
  11     long extractor;
  12
  13     // Build the extractor so that (n / extractor) is a single digit [0-9]
  14     for (extractor = n < -9 ? -10 : (n < 0 ? -1 : 1);
  15          n / extractor >= 10;
  16          extractor *= 10)
  17         ;
  18
  19     // Case: n is negative.
  20     if (n < 0)
  21         putchar('-');
  22
  23     // Now, we extract the digits starting with the most significant digit
  24     // (left-most) and work our way to the least significant digit (right-
  25     // most). The number now is always positive because of the previous
  26     // block.
  27     while (n != 0)
  28     {
  29         char digit = (char)(n / extractor + '0');
  30         putchar(digit);
  31         n %= extractor;
  32         extractor /= 10;
  33     }
  34
  35     // take care of trailing zeros: As long as the extractor is not zero,
  36     // we are not done. A non-zero extractor means we have trailing zeros.
  37     // For example, a 1000 means we need to write out 4 (yes, 4; not 3)
  38     // trailing zeros.
  39     for (; extractor != 0; extractor /= 10)
  40         putchar('0');
  41 }

As usual, if you have any comment or suggestion, please post them in the comment area or send me private email (see my email right below my picture).

Advertisements

Putlong() Revisited

In my previous post, I discussed and gave a solution to the putlong() problem. However, as Christy pointed out in her comment, my code did not work if a number has trailing zeros (e.g. 15700, 3000, 10, -10, …). Christy also suggested a fix, which I have not yet verified. As I tried to correct my code, I stepped back and thought, “what can I do differently?” and that is the topic of this post: a different way to solve the putlong() problem. In this post, I will discuss the problem, the strategy, caveats, and present the source itself.

The problem is a simple one: given a long integer, write it to the console (standard output) using only putchar(). The problem prohibits the candidate from using conversion or other output routines such as itoa, sprintf, … In addition, the problem prohibits the candidate from using array or any buffer. Finally, candidate should not use recursion.

Before I go on, it helps to review my other strategy in my previous post. This time around, my strategy is to extract each digit from left to right (i.e. most significant digit (MSD) to least significant digit (LSD)). As an example, let us examine the case where n=295 (n is the sole parameter to putlong). In this case, I will first extract and print the digit 2, then 9, and 5. To extract the first digit, 2, I divide n by 100, convert it to a character, and print it. Next, I remove the digit 2 from n using the modulus operator: 295 % 100 = 95. In similar fashion, I extract the next digit, 9, by dividing n by 10: 95 / 10 = 9. The logic then goes on until I extracted all the digits. Reader should notice that the same number 100 used to extract the MSD is also used to remove that MSD from n.

The question is, how do I come up with 100? For my solution, I will introduce a local variable called extractor (line 11), which is a long integer whose value is either a 1 or a multiple of 10 (1, 10, 100, 1000, and so on). The key is to build extractor so that it contains the same number of digits as n. To achieve this goal, I started out with extractor = 1, then keep multiply it by 10 until n / extractor produces a single-digit number (lines 14-15). After building the extractor, I will go through the cycles of extracting the MSD, convert to character type, write it out, and remove the MSD from the number. These cycle will end when I am running out of digits (lines 25-31).

At this point, I am not done yet becase I have to address two caveats: negative numbers and trailing zeros. So far, my discussion did not include negative numbers. For a background on how troublesome negative numbers are, please refer to my previous post. To deal with negative numbers, I modified my code to build the extractor as a negative multiple of 10: -1, -10, -100, and so on (lines 14-15). Next, I write the negative sign (line 18-19) and it should take care of the case.

At this point, the code passes most of my test cases, except for the cases that prompted me to rewrite putlong() in the first place: numbers with trailing zeros (e.g. 15700, 3000, 10, -10, and so on). Take the case where n=50; after extracting the digit 5 and print it (lines 27-28), removing the 5 will leave n=0 (line 29), and extractor=1 (line 30). With n=0, I exit the loop (lines 25-31) and did not write the last zero. Similarly, for the case of 3000, I only write out the digit 3 and exit the loop with extractor=100. Observe the value of extractor after exiting the loop (lines 25-31): when n=50, extractor=1 and when n=3000, extractor=100. That means the number of digits in extractor corresponds to the number trailing zeros I need to write and that is how I take care of trailing zeros (lines 37-38).

Here is the complete listing of my code for putlong() version 2. As usual, I would like to hear from the reader of any suggestion, comments, or bug report.

<div><pre>    1         /// <summary>
   2         /// Writes a long number to the console.
   3         /// Constraints:
   4         /// 1. Use only putchar() and no other means (itoa, sprintf, ...)
   5         /// 2. Do not use array to store the digits
   6         /// 3. No recursion
   7         /// </summary>
   8         /// <param name="n">The number to write to the console</param>
   9         public static void putlong(long n)
  10         {
  11             long extractor; // .., -100, -10, 1, 10, 100, .. to extract the digits
  12
  13             // Build the extractor so that (n / extractor) is a single digit [0-9]
  14             for (extractor = (n < 0 ? -1 : 1); n / extractor >= 10; extractor *= 10)
  15                 ;
  16
  17             // Case: n is negative.
  18             if (n < 0)
  19                 putchar('-');
  20
  21             // Now, we extract the digits starting with the most significant digit
  22             // (left-most) and work our way to the least significant digit (right-
  23             // most). The number now is always positive because of the previous
  24             // block.
  25             while (n != 0)
  26             {
  27                 char digit = (char)(n / extractor + '0');
  28                 putchar(digit);
  29                 n %= extractor;
  30                 extractor /= 10;
  31             }
  32
  33             // take care of trailing zeros: As long as the extractor is not zero,
  34             // we are not done. A non-zero extractor means we have trailing zeros.
  35             // For example, a 1000 means we need to write out 4 (yes, 4; not 3)
  36             // trailing zeros.
  37             for (; extractor != 0; extractor /= 10)
  38                 putchar('0');
  39         }

Finding If Two Rectangles Are Overlapped

Here is another popular interview questions: given two rectangles, each represented by two points: an upper left (UL) and a lower right (LR) corner. Write a function that takes in two rectangles and return true if they are overlapped, false if they are not.

Before we start coding, let’s take a look of the cases where rectangles are overlapped, and cases where they are not:


Based on my readings and experience, it is much simpler to determine if rectangles are not overlapped than if they are: we only have four cases to consider, and each case, we only need one comparison. In contrary, the four cases where the rectangles do overlapped are complex because we need to make several comparisons in each case. Therefore, our function will determine if the rectangles are not overlapped, then negate the result.

Before we go on, we need to take a step back and study the coordinate system used in most computer graphics frameworks. In most system, the origin (x = 0, y = 0) is located at the top left corner of the screen with he X axis extents from left to right and the Y axis from top to bottom.

So, how do we determine if the two rectangles are not overlapped? There are really four cases:

Case 1: A is to the left of B. In this case A’s right edge is either to the left of or touch B’s left edge. In the expression below, UL is short for upper left, and LR is for lower right. We can express this case in code as follow:

a.lr.x <= b.ul.x

Case 2: A is to the right of B:

a.ul.x >= b.lr.x

Case 3: A is above B:

a.lr.y <= b.ul.y

Case 4: A is below B:

a.ul.y >= b.lr.y

Putting these cases together and negate them, we got the conditions where the two rectangles overlap:

!(a.lr.x <= b.ul.x || 
a.ul.x >= b.lr.x || 
a.lr.y <= b.ul.y || 
a.ul.y >= b.lr.y)

As you can recall from your logic class: !(a || b) is the same as (!a && !b). Therefore, we can rewrite the above expression as:

a.lr.x > b.ul.x && 
a.ul.x < b.lr.x && 
a.lr.y > b.ul.y && 
a.ul.y < b.lr.y[/sourcecode]

And that will be the expression to test if two rectangles are overlapped.

Find Largest Sum of Contiguous Numbers in an Array

This is one popular interview question. The problem: given an array which could contain zero, negative, and positive numbers, find the largest sum of contiguous sub-array. For example, if the array contains:

    31, -41, 59, 26, -53, 58, 97, -93, -23, 84
		

then the largest sum is 187 taken from the [59 .. 97] block

My research points to Jon Bentley’s solution as the most efficient solution (see his book, “Programming Pearls”). In fact, Bentley was probably the person who started this thread. His solution has a complexity of O(n) which is very good, considering the brute force solution is of O(n3). Here is a Python implementation of Bentley’s solution:

def largest(array):
    maxSoFar = maxUpToHere = 0

    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)


    return maxSoFar

This solution is very efficient, short, and easy to remember. To understand it, I recommend reading his book, “Programming Pearls.”

After implementing this solution, I wrote some test cases to verify its correctness. Overall, the code works well, but it does not return the correct value for cases when the whole array contains only negative numbers. For example, consider this array:

    -3, -1, -2

I expect to see -1 as the largest sum, but instead, I got 0. After studying the algorithm, I noticed that the problem comes from the line:

    maxUpToHere= max(maxUpToHere + element, 0)

For negatives-only cases, maxUpToHere will be zero because it is the larger of the two. Instead of zero, the correct output in these cases should be the largest number in the array. I also noticed that negatives-only are the only cases which cause trouble, so we can add detection to the code and return the largest element instead of maxSoFar. Here is the patched code:

# This is based on Bentley’s Programming Pearls
# My (Hai Vu’s) modification: if the array is all negatives
# then max is the largest element
def largest(array):
    maxSoFar = maxUpToHere = 0
    largestElement = array[0]
    allNegatives = True
    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)
        largestElement = max(largestElement, element)
        if element >= 0:
            allNegatives = False
    if allNegatives:
        return largestElement
    return maxSoFar

The patched code works well for all cases. However, if you have a better solution, I would like to learn about it. My python program is available for download: largestsumpy.pdf

Remove Duplicates in a Java Array

As I go through interviews while looking for jobs, I often come home and revisit the questions as a learning experience. Here is an interview question that I often encounter: Given an array of integer where the elements (entries) are not sorted, write a function to return a new array with the duplicate entries removed. For example, if the original array is:

1,2,3,1,2,3

then the function should return:

1,2,3

The first time I tackled this problem, I did not make use of Java’s collections framework. As the result, the code are long, hard to read, and hard to maintain. When the interviewer asked me to improve the code, I finally thought of using the collections framework, but what kind of collection should I use? The interview was kind enough to provide me with a reference book for my research. To solve this problem, I need a collection that provides fast look-up, retains the original insertion order, and ignores the insertion of duplicate entries. As it turns out, Java collection framework does provide a collection that fit my demand and it is called LinkedHashSet. Using LinkedHashSet, I was able to simplify the code’s logic. For a complete listing of my code, follow the link here.

How to Reverse Words within a sentence in C++

This is yet another popular interview question: given a string, for example, “Ask, and you might get it.”, write a C/C++ function to reverse the words so that it becomes: “it. get might you and Ask,”. Since I have documented my source code fairly extensively, you can read the source code and see how to do it: ReverseWords.txt

Update: I have tested ReverseWords.txt (after renaming it to .cpp) under Mac OS X 10.4.11 and verified that it worked. However, some one has reported crashing when building and running under Visual Studio 2005. For that, I submitted my vs2005 project and hope that the same person can help me to verify the correctness of my code. I appreciate your help. Click here for the vs2005 project.

How to Print a Long Integer Using Only putchar()

How to Print a Long Integer Using Only putchar()

Here is a popular interview question: write a C/C++ function which outputs a long integer to the console:

void putlong(long number);

To make it harder, the interview often specifies the following restrictions:

  1. You can only use putchar(char c) as your only mean of outputing to the console
  2. Do not create a string buffer to store the digits (this is necessary to reverse the order of the digits)
  3. No stack to reverse the digits
  4. No recursion allowed

Before writing any code, let’s take a look at a simple example for number = 123. In the table below, we repeatedly extracting the last digit from the number using the modulus operator % and reduce the number by dividing it by 10.

Operation Result Note
123 % 10 3 This gives the third/last digit
123 / 10 12 The gives the remaining digits
12 % 10 2 This gives the second digit
12 / 10 1 This gives the remaining digits
1 % 10 1 This gives the first digit
1 / 10 0 This is when we stop

The problem with this approach is the extraction is in reverse order of what we should be printing out. There are several ways to address this issue. We can push the digits onto a stack and retrieve them in reverse order. However, restriction #3 prevents us from doing so. We can also use a char[] buffer to store the digits and later on output them in reverse order. As you guessed it, restriction #2 makes sure this will never happend. Restriction #4 also prevent us to use recursion as a way to print the digits in reverse order. So what’s left?

There are several solutions, but here is one that I devised: if we can reverse the digits in a number, then we can print them out in correct order. In the previous example where number == 123, if we can somehow reverse it so that number == 321 then we effectively solved the problem.

It turns out the reversing a number is not that hard, but we need to be aware of cases when overflow might occur. For example, on some machine, the range for long is -2147483648 to 2147483647. If we reverse the number near the limits, we get an overlow error. To remedy this problem, we can save off the last digit of the number, then reduce it by a factor of 10. This way, we can ensure that overflow will not happen. The code for saving the last digit and reducing the number looks like this:

char lastDigit = (char)((number % 10) + ‘0’); // Extract the last digit

number /= 10; // reduce the number

One last problem we need to address: the negative sign. At first, we might attempt to do something like:

if (number < 0)

{

putchar(‘-‘);

number *= -1;

}

However, it is not that simple. Recall that the range for long is -2147483648 to 2147483647. When number == -2147483648, changing sign the way we just did will produce an overflow. Thus, we will need to treat negative case with more care:

if (number < 0)
{

putchar(‘-‘);
lastDigit = (char)(‘0’ – (number % 10));
number /= -10;

}
else
{

lastDigit = (char)((number % 10) + ‘0’);
number /= 10;

}

Now that we save the last digit and reduce the number to prevent overflow, the fun begin. Our next task is to reverse the digits:

long reversed = 0;
while (number > 0)
{
reversed = reversed * 10 + (number % 10);
number /= 10;
}

Next, we will print out the digits of reverse:

while (reversed > 0)
{
char c = (char)((reversed % 10) + ‘0’);
putchar(c); // print it
reversed /= 10; // reduce the number
}

putchar(lastDigit); // don’t forget this

That’s all there to it. Below is the complete code in C, which also works in C++:


// putlong.c : Defines the entry point for the console application.// 
#include <stdio.h>
#include <limits.h>

void putlong(long number)
{
    char lastDigit;
    long reversed;

    // Extract the last digit and reduced the number by 10 to
    // avoid overflow. Also take care of the negative sign
    if (number < 0)
    {
        putchar('-');
        lastDigit = (char)('0' - (number % 10));
        number /= -10;
    }
    else
    {
        lastDigit = (char)((number % 10) + '0');
        number /= 10;
    }

    // Reverse the number
    reversed = 0;
    while (number > 0)
    {
        reversed = reversed * 10 + (number % 10);
        number /= 10;
    }

    // Now, output the number using only putchar()
    while (reversed > 0)
    {
        char c = (char)((reversed % 10) + '0');
        putchar(c);
        reversed /= 10;
    }
    putchar(lastDigit);
}

int main()
{
    putlong(0);
    putchar('\n');

    putlong(123456);
    putchar('\n');

    putlong(-123);
    putchar('\n');

    putlong(LONG_MAX);
    putchar('\n');

    putlong(LONG_MIN);
    putchar('\n');

    return 0;
}

If you have any comment or question, please post them at my blog.

Blogged with Flock