Falling Lakers

Before the season started, I had the feeling that Lakers had no chance to win this year -- even go to the final. Actually their best chance in the next a few years was the playoff of last year when they screwed.  Now one month in the regular season, Lakers are at 12-9 and are fighting for a playoff seat in West.

There are a few sparkling moments when Kobe scored 40+ for 4 consecutive games, and hopefully that is not the last a few drops in his tank.

Why does Lakers fall so hard?

1. Lost two role players Odom and S Brown, but no new blood. Brown is a very good young player, a dependable substitute for Kobe. I am not sure why Lakers did not given him a contract. Bass is getting meaner because he is older.
2. The core of Lakers are older and older. Kobe has played 16 seasons and still plays 40+ minutes per game. Can he do this continuously in playoff? Fisher is way too old for a starting PG. Gasol is not as good as last year. Bynum is OK, but can we trust him for an entire season? The most disappointed is MWP. 
3. Lack of young talent. Phil was never a good coach that can find and grow young talents. 
4. Other teams are improving such as Clippers and Thunders etc. Some teams have been going through  reconstruct in the past a few years are now paid off such as Houston, Pacers and 76ers. 
5. Brown is a mediocre coach.  

What are Lakers' opportunities now?  They are way over the salary limit now, so the only thing they can do is to trade. But they do not have many players that have trade value except Gasol and Bynum. After this year, they will clear some salary room, but Kobe will be another year older. So I think they will suffer in the next a few years. 

Hope I am wrong because it is always my favorite team ...... 

Command line life in microsoft

Before I joined microsoft, I expected to use all the fancy tools from microsoft, but it turned out it is not the case, at least in my department. We used visual studio as a nice editing tool and sometimes used it for debugging. But we still spent a lot of time in command line working with source repository and building etc. We also need to work a lot on windows shell script too.

I am totally fine with that -- I am used to working in command line and 90% of my time was spent in putty in yahoo. But windows command line env (even cygwin) is much worse than linux shell session; windows shell scripting is even worse than linux shell scripting. For the shell one, I do not want to complain too much as I think this is probably because I am not familiar with windows shell. But the command line env, I guess everybody should agree with me. It also lacks a lot of handy linux shell utilities. My productivity is at least 50% worse than linux ;=(

be aware of the static variable in inline functions

I've learned a lesson Friday when debugging a test case -- the static variable in inline function is not always static.

Here is the use case. I have a singleton impl in a dll like below. In the DLL, I created a singleton instance and in my main program I also referred my singleton instance using Singleton::Instance(). Well it turned out that the instance referred in main program is different from the one created in the DLL!

// some .h file
class Singleton 
{
      T& Instance()  
      {
           static T  instance;
           return instance;
      }
};

// some cpp file

Singleton m_t = Singleton::Instance();

Why would it happen and how to resolve it?

• If the singleton is in a static library, this is OK. 
• DLL is same as exe that they are a standalone linker unit, which means they are complete -- all symbols have to be resolved, while static library is not. So when static variable is in the inline function and the function is invoked in a linker unit, a storage is allocated by the linker for that static variable. In my case, I have two linker units, so I have two copies of that instance.
• Solution 1: do not inline
• Solution 2: export the static variable in DLL and import it in the main program. A common way in visual c++ is like below

// in dll

// stdafx.h
#define MYAPI __declspec(dllexport)

// header file singleton.h
class MYAPI Singleton (};

# in other linker units

// stdafx.h
#ifndef MYAPI
#define MYAPI __declspec(dllimport)
#endif

// cpp of header file

#include "stdafx.h"
#include "singleton.h"

Puzzle: Find Sophie

A friend told me the facebook puzzles page, so I started to work on some puzzles for fun. I started to work on "Find Sophie" which is at buffet level (hardest). This one is pretty interesting and it is not as hard as I thought.

http://www.facebook.com/careers/puzzles.php?puzzle_id=11

As usual I started with a recursive solution. The algorithm is simple:

1. starts with a node (first node) and find all the neighbors. Also calculate the current distance traveled so far.
2. for each neighbor, if it has not been visited yet, compute the current cost and call the recursive method with that node

// pseudo code

double minCost, curCost;

void backtrack (int node, double distSoFar)
{
    if (currentPath.size() == numberOfNodes) 
    {
        // this is a solution
        if (minCost > curCost) minCost = curCost;
        return;
    }

    foreach n in node's neighbors
    {
        if n has not been accessed
        {
            double p; // possibility
            double dist; // the distance to this neighbor
            curCost = curCost + (distSoFar + dist) * p;
 

// set the access flag of node n 

// backtrack
            backtrack(n, distSoFar + dist);

// restore curCost, accessflag of n
        }
    }
} 

So what is  the complexity of this puzzle? Obviously it is O(n!). For a 17 node example, it took several hours running on my server and still not finished. So how to improve it? Simple. Prune the search path.  A few simple techniques were used and all of a sudden, it took less than 1 second to run all the examples posted in this blog. http://www.facebook.com/topic.php?uid=15325934266&topic=7058

1. At any time, a minimal cost is maintained. In the search process, if we find the cost of the search is larger than the minimal cost, the current search can be terminated earlier
2. Which neighbor to try first? Simple math could show that if the node has higher probability and lower distance, that node should go first. So we can sort the neighbors for each node by "dist * (1-p)", where "dist" is the distance to current node and "p" is the probability of the current node. This is very important. The earlier we find a relative lower cost, the more search paths can be pruned.

Another critical point about this puzzle is not all nodes are connected, so we need to calculate a path for each pair of nodes (preferably the shortest path between each pair). This is a O(n3) operation and should be OK comparing to the O(n!) nature of the problem.


Puzzles are fun!

what's wrong with lakers?

I was glad that Lakers won 2010 playoff and hoped they can get the triple. But  now I am so mad that they played so badly this season - they trailed a lot from spurs; they are also behind heats, dallas and boston etc; they lost to almost every winning team.....

so why did it happen?

• they have won in the last two years, so right now they (both coaches and players) do not have strong desire as before. Kobe wants to win again, but how about his teammates?
• Bynum Bynum's injury has some impact. Now he is back and lakers is still losing
• Phil depends on the star players too much. Paul is exhausted. Bench players do not get enough play time and do not play to their expectations. Brown was good in the first a few games and now got lost. 
• Phil is not good at unearthing young talents.
• Worst of all: Kobe is OLD. He is only 32, but he already played 14 seasons more than Jordan did when he first retired in 98.  He has to realize that he can't lift this team alone and has to trust his teammates; otherwise Lakers has no chance to win this year. He's been my favorite player but I have to admit he is not in par with Jordan at all......

Lakers is always my favorite, so hopefully they can improve in the new year ;=)