I was plotting a chart to visualize various development project in my area. The primary concern is in development density. But the project footprint itself is also a factor. We want to focus on big project that matters. We also want to identify outliers that has very high or very low density, but otherwise has small overall size and less relevance.

My solution is to use a variable with bar chart below. The height of each bar represents the density. The width represents the lot size. The area of each rectangle bar reflects the total number of units. The full article is posted in Potrero Boosters Neighborhood Association's website.

I thought everything that worth inventing has been invented. So I was frustrated that I cannot find a tool to generate this chart. Nothing in Excel (that I know) can generate a chart like this. I end up turning to matplotlib. But even matplotlib does not seem to have a function that support this directly. Fortunately a small twist to its histogram function does the job for me. See my (unpolished) source code here. In any case working with matplotlib is fun and the quality of the chart is excellent.

2010.02.26 [design, programming] - comments (0)

Refrigerator Madness is the second Facebook programming puzzle I have tried. The problem description is complicated. I won't try to repeat it here but to suggest you to refer to the original facebook page.

To solve this problem it is necessary to see through the smokescreen. Instead of thinking how much Red Bull a Facebook engineer likes to drink, it is easier to map it to a problem known as Two-Sided Matching. A model with intuitive meaning is a marriage matchup between a group of man and woman. Each man has his list of preferred woman and each woman has her list of preferred man. The marriage is considered stable if there are no two people of opposite sex who were not married to each other but would both prefer to be.

For the Refrigerator Madness problem just map the engineer from the upper 50th percentile to "man" and lower 50th percentile to "woman" (or vice versa). The matching condition is equivalent to the stable marriage criteria.

At this point the problem can be solved by applying the Gale-Shapley algorithm. Write the code and it's done!

2010.02.22 [programming] - comments (5)

Facebook has published a number of programming puzzles to challenge software developers. Their problems are not trivial at all. This is my attempt on "Snack" level problem It's A Small World. Even this one take me sometimes to solve.

The idea is that there are n points on a 2-dimensional plane. For every point, we have to find the 3 nearest neighbors. The naive solution simply match all possible pairs, resulting in O(n²) complexity. The problem requires us to find a better solution than O(n²).

My idea is to divide the plane into a regular grid like below. For example, to find the neighbor of point A, we can focus on cell 2 in the center top and pretty much ignore the points in cell 9 in the lower right. This works very well if the points are randomly distributed. But if many points are clustered together like cell 9, it will work less well. We can recursively partition it into smaller region. But the basic plan should be suffice for this puzzle. The subdivision is a very simple O(n) process.

To search for the nearest neighbor, we start from points from the same cell. If this doesn't find the three nearest neighbors we extend into the neighboring cells. The pseudo code is shown below:

  result = None

  for step in 0...n

    cells = find cells "step" away from the source
    min_distance = minimum distance from source to the boundary of the cells

    for all point in cells
        insert distance(source, point) into result

    result = 3 closest points in result

    if there exists 3 points in result those distance < min_distance
        return result

  end for

Of course I'm not the first one to consider these algorithm. Wikipedia has some information on the Nearest neighbor search problem. My solution code is available here. (2010-02-21 Facebook's puzzle server is down. So the solution has not been validated.)

I have decided to put the algorithm into good use. I used it to generate a map of all sizable cities in the world and their nearest neighbors. With 20,000 cities a naive algorithm will need 400 million pairing. Using this algorithm only 10 million pairing are need. It is far from optimal, but good enough to handle Facebook's problem. Also I am curious to use it to find the loneliest city in the world, that is, a city those nearest neighbor is the furthest away. Check the map to find out which city is the loneliest city in the world!

2010.02.21 [programming] - comments (3)

Last month the IT world is jolted by the news of a security breach of Google's system by Chinese hackers and the subsequence response by Google threatening to pull out their China operation altogether. Many in the west see this as a courageous resistance to China's Internet censorship and a righteous response to the assault on some human right activists. Other observers noted that Google's market share in China is trailing far behind the local competitor, that they may using this incident to give themselves a graceful excuse to exit.

All of them could have learned something from anthropologist Tricia Wang's insightful observation of Google's uses or non-use in China. Tricia is a research scholar working in China to study how youths and migrants are using ICT to manage their inter-personal communication networks. She come up with her observation from the angle of grassroot youngsters.

Among her observations are

• Google is mostly irrelevant to Chinese users. While elite, educated Chinese depend on Google as much as others do, young people has a very different usage pattern. They mostly use Internet with IM or mobile devices to connect to their friends. They have never found Google to be useful.
• Google has a huge branding issue in China. Most Chinese cannot spell the word 'Google'! I was amused to find that Google is known by its colloquial name GouGou (狗狗doggy) more than its official name Gu-Ge (谷歌). Here in the west, especially within the IT industry, Google's brand name stands for leadership in innovation and intelligent services. There in the back street of China, Google's name is associated with the lowly doggy. What a satire!

Tricia has an excellent piece of analysis that should be on most reader's radar screen.

2010.02.11 [tech] - comments (0)

Your walk in a cafe. You see everyone is working alone with their laptop. Nobody is talking to each other. Even the most ardent Internet junkie would admit they should have spent more time personally with other people rather than glue to the computer screen all day long. These cafe owner even try to setup rules asking patrons to log off and talk.

These moves are no doubt well intentioned. It will probably inspire many supporters. But why is so many people stick to their computer in the first place? It would be easy if we can determine that too much Internet is for sure a bad behavior, like watching too much TV. But what if it is true, that your second life is actually better than your first life?

2010.02.06 [philosophy] - comments (0)