Thursday, February 23, 2012

The beauty of algorithm

Consider this problem. For every node of a given binary tree, add a new pointer "next" to it and let it point to the next node at the same level. In another words, create a linked list fo each level at the binary tree. I.e. for the below binary tree.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

You will end up with 4 lists:
  • 3 -> NULL
  • 5 -> 1-> NULL
  • 6 -> 2 -> 0->8 -> NULL
  • 7->4-> NULL
This looks like a variant of a BFS problem. We just do a BFS for this binary tree, but how do we differ the node at each level? A slightly change to the BFS algorithm will do. Basically we add a level information to the node in the queue.  Check code below
void SetTreeNext(Node * root) 
{ 
    typedef std::pair NodeData;
    std::list queue;
    int prevLevel = 0;
    Node * prevNode;
    queue.push_back (NodeData(root, 1));

    while (!queue.empty())
    {
        NodeData data = queue.front();
        Node * curNode = data.first;
        int curLevel = data.second;
        queue.pop_front();
        
        if (curLevel != prevLevel)
        {
            prevNode = curNode; 
        }
        else 
        {
            prevNode->next = curNode;
        }
        if (curNode->left) 
            queue.push_back (NodeData(curNode->left, curLevel +1) );
        if (curNode->right) 
            queue.push_back (NodeData(curNode->right, curLevel +1) );
    }
} 

Time complicity O(N). Space complicity O(N)

Method 2:

Could we do it without the level information? Yes of course. We could track the number of nodes at current level and previous level. But here we will present a different solution.

Consider we do a normal BFS, the result looks like this:
 3-> 5 -> 1 -> 6 -> 2 -> 0 -> 8 -> 7 ->4

If we have a NULL pointer at the end of each level, the BFS will look like this:

3 -> NULL -> 5 -> 1 -> NULL -> 6 ->2 ->0 ->8 -> NULL -> 7 -> 4 -> NULL

The question is can we convert the first BFS result to the next one? Let's do it level by level.

First we have root information stored in the list

3 -> NULL

We keep a current pointer (starts with the first pointer for every level), now it points to 3. We start from this current pointer and put all its children to the end of list; then the current pointer moves to the next pointer until it sees a NULL (end of the current level). At this moment we know we are done to put children of current level at the end of list; we can put a NULL at the end of this.

3 -> NULL -> 5 -> 1 -> NULL

Repeat this process we can get the final list. For every node in this list, we can start to chain them. For every NULL node, we start with a new level.
Time complicity O(N). Space complicity O(N)

Method 3:

We presented two methods with O(N) time and O(N) space. We could not do any better in terms of time complexity since we need to visit each node at least once. Could we do it better in terms of space?  Here is an interesting one with O(1) space. 

We have a new pointer 'next' in each node. Could this pointer help us in the tree search? Consider at first level we have:

     root (3) -> NULL
For next level, we started with one of the children of the first level, in this case it is 5 (left child of 3). What is 5's next node? It could have a few possibilities:
  • if 5's parent node has a right child, the next node should be parent node's right child
  • if the node itself is the right child or the parent does not have aright child (i.e. at third level, 6->2->0->8->NULL, node 2). In this case, we will go to next node of its parent node and find its first child. What if no child? Continue to search the next chain!
Repeat this process we can chain all the nodes at the same level without any additional space.
Check code below
void SetNextNode (node * root)
{
    if (!root || (!root->left && ! root->right)) return;

    // start node of current level
    node * startNode  = root->left ? root->left : root->right;
    node * parentNode = root;
    while (true)
    {
        // process current level
        Node * currentStartNode = startNode;
        while (parentNode)
        {
            // The next child is the right sibling of current node
            if (parentNode->left == startNode && parentNode->right) 
            {
                startNode->next = parentNode->right;
                startNode = parentNode->right;
            }
            else if (parentNode->right == startNode || 
                   (! parentNode->left && !parentNode->right) )
            {
                // go to next node in parent's chain
                parentNode = parentNode->next;
            }
            else 
            {
                Node * nextNode = parentNode->left ? parentNode->left : parentNode->right;
                startNode->node  = nextNode;
                startNode = nextNode;
            }
        }

        // find first available child in current level
        while (currentStartNode && !currentStartNode->left && !currentStartNode->right) 
            currentStartNode = currentStartNode->next;
 
        if (!currentStartNode) break;
        parentNode = currentStartNode;
        startNode = parentNode->left? parentNode->left: parentNode->right;
    }
}








Sunday, January 29, 2012

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 ...... 

Saturday, March 26, 2011

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"


Monday, January 24, 2011

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!