Monthly Archives: January 2008

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         }

Some Python One-Liners

Python is such a simple and get-the-job-done language that many script I wrote is very short. Here are a couple of one- and two-liners:

# oneliners.py by Hai Vu
# Here are some of my one- and two-liners
import os, sys

# To create Pascal naming from a regular phrase
print 'print in order traversal'.title().replace(' ', '') # --> PrintInOrderTraversal

# Print the contents of a file:
print file('oneliners.py').read()

# read the contents of a file and put in a list:
lines = [x[:-1] for x in file('oneliners.py')]

# Poor man's calculator: parse the command line and evaluate it.
# If you save this to a file call eval.py, then call it as follow:
#   python eval.py "28 * 1.15" 
# The output will be:
#   28 * 1.15  = 32.2
expression = ' '.join(sys.argv[1:])
print expression, ' =', eval(expression)

# Prints out the path with each component in a separate line
# also work for such environment variables as INCLUDE, LIB, and CDPATH
print '\n'.join(os.environ['PATH'].split(os.pathsep))

Please submit your favorite one-liners in the comments section.

Solution for Vista to Leopard Connection Problem

I had my Leopard set up for file sharing, which I can connect from my other Mac and XP computers. However, for the longest time, I could not connect to it from my Vista machine.After doing some research, I finally found the solution posted in Apple’s discussion forum. If your user name on the Leopard machine is haivu, then you should use DOMAIN\haivuinstead of plain old haivu to log in.

Reference: Sharing files with Vista (look for the post by StatMan). Thank you StatMan.
Keywords: login, log in, file sharing, networking, windows, os x, mac

How to Post Source Code in WordPress

If you are hosting your blog on wordpress.com and would like to post your source code, WordPress has a treat for you. Check out this Java code sniffet:


for (int i = 0; i < 10; i++)
    print("Line number %d\n", i);
[/sourcecode]

If you are interested, check out this WordPress FAQ page. WordPress claims to support Python, but I have tried and the syntax-highlighting feature does not work.

Another alternative is to use the Code Colorizer which I have described in my previous post. The Code Colorizer supports a number of languages, but Python is not one of them. If you know a solution for Python, please post a comment here.

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.

How To Set Up CxxTest

I have been writing unit tests using C#, Java, and Python using MbUnit, JUnit, and PyUnit, respectively. Since C++ does not fully support retrospection, unit testing on C++ can be tricky. Most C++ testing frameworks require the developer to 1) write a test case, then 2) register it — a two step process. This two-step approach carries a couple of problems. First, it is tedious to having write the test case, then register it. Second, the process is error-prone because of potential mismatch between the test case and the registration. In addition, the developer might forgot to register the test case, which exclude the test case from being run.

For those reasons, I like CxxTest for its simplicity: I only need to write the test case and be done with it. At first, I was putting off by CxxTest’s requirement: It relies on Perl or Python to generate registration code. However, I decided to press on and give it a try and the result was worth it.

The following are the steps I performed to get CxxTest working. While they seem a little long, they are not complicated. If you follow them one by one, you should have your system up and running in no time.

Step 1: Installing Perl or Python

I recommend installing ActiveState Python or Perl. Recently, I discovered IronPython, but I do not know if IronPython works with CxxTest or not. After installation, make sure that Python or Perl is in your path.

Step 2: Installing CxxTest

Download CxxTest from its home page. I recommend to unzip CxxTest to the root directory, C:\, but you can pick other locations. After unzipping, add your directory to the PATH and to the INCLUDE environment variables. Here is how to do it in Vista:

  1. Click Start menu, click “Control Panel” from the right column to start the control panel
  2. From the control panel’s search box, type ‘env’ and you will see the choice for “Edit environment variables for you account”, click it.
  3. If the environment PATH does not exist, create it and assign the value C:\CxxTest (or the location of your CxxTest directory). If the PATH evironment already exist, append ;C:\CxxTest to it (note the semicolon which acts as a separator).
  4. Similarly, add C:\CxxTest to the INCLUDE variable
  5. Click OK to submit your changes

Step 3: Create a Test Project

This step is for those who is using Visual Studio. From Visual Studio, create a new project for your test, in my case, I created an empty project and add to it a new file call ‘mytestsuite.h’. This file is where my test cases reside. Please follow the CxxTest’s User Guide for information on how to create your test cases.

I also create a new file call ‘prebuild.cmd’ and add it to the project. The prebuild.cmd file contains only one line:

cxxtestgen –error-print -o mytestsuite.cxx mytestsuite.h

Basically, this script creates the code for registering the test cases. Next, you will configure Visual Studio to run this script before every build:

  1. In Visual Studio, Click the Project menu, then click Properties
  2. In the properties dialog, navigate to the following branch: Configuration Properties > Build Events > Pre-Build Event
  3. Fill in the following information:
    • Command Line = prebuild.cmd
    • Description = Build mytestsuite.cxx
    • Excluded from build = No
  4. Click OK to submit your changes
  5. Run the build once to create the file mytestsuite.cxx
  6. Add this file to your project

Now you have everything setup, each time you build your test project, Visual Studio will launch prebuild.cmd and you will not have to think about it any more, just concentrate on writing your test cases. If you have any question, comment, or correction, please submit them via this blog’s comment.

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