LeetCode Unique Tree Solution

Question:

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

First of all, please focus on the structure of the tree. We are figuring how many distinct structure could n nodes form. Values inside of these nodes are not important as long as I see.

Requirement:
Probability class.

Idea:
Level by level probability. We view each level as slots. Level one definitely only has one slot. We have to place only one ball(node). At level 2, we now have 2 slots! how many ways to place it? left, right, left&right.(only if we have 2 balls). And the next level number of slots is two times previous level number of slots.

class Solution {
   public:
   int factorial(int n){
      return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
   }

   int xChooseY(int x, int y){
      return factorial(x) / (factorial(x-y)* factorial(y)) ;
   }

   //@param
   // previous level num of nodes
   // reminding number of nodes we could place
   //@return the number of unique ways
   int explore(int nodeNum, int reminder){
      if(reminder == 0) return 1; //only previous possibility
      else {
      int ret = 0;
      int maxNumNode = nodeNum *2;// we gotta times 2 because of the tree structure
      int insertMax = min(reminder,maxNumNode);
      for(int i =1; i <= insertMax; i++){ //insert 1 ball, 2 ball...
        ret+= xChooseY(maxNumNode, i) *explore(i,reminder-i);//if insert i balls, what about next level?
      }
      return ret;
   }

   int numTrees(int n) {
     if(n == 0) return 0;
     else {
       return explore(1,n-1);// place one ball at level 1 and let's go!
     }
   }
}

char* and const char*

I think I should write a post about char* and const char*

string str = "goodDay";

char x = str[0];

char* X_what = str[0]; //c array

const char* = &str[0]; //still c array

Array as parameters

I used to think when pass in an array ,the receiver end will do

 someFunc(char* pass_in_arr); 

But it could done in this way as well, and is more clear:

#include <iostream>
using namespace std;

void printarray (int arg[], int length) {
  for (int n=0; n<length; n++)
    cout << arg[n] << " ";
  cout << "\n";
}

int main ()
{
  int firstarray[] = {5, 10, 15};
  int secondarray[] = {2, 4, 6, 8, 10};
  printarray (firstarray,3);
  printarray (secondarray,5);
  return 0;
}

Implementation of itoa

/* K&R Implememtation does not handle most negative number */
void reverse(char s[])
{
   int i, j;
   char c;

   for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
     c = s[i];
     s[i] = s[j];
     s[j] = c;
   }
}


void itoa(int n, char s[])
{
   int i, sign;

   if ((sign = n) < 0) /* record sign */
   n = -n; /* make n positive */
   i = 0;
   do { /* generate digits in reverse order */
     s[i++] = n % 10 + '0'; /* get next digit */
   } while ((n /= 10) > 0); /* delete it */
   if (sign < 0)
   s[i++] = '-';
   s[i] = '\0';
   reverse(s);
}

Char to Int, Int to Char

Char* to Int:

#include <stdlib.h>
int atoi ( const char * str );

Single Char to Int:

char x = '8';
int ret = x - '0';

Int to Char:

non-standard itoa is avaliable. But this function can be achieved by using sstream;

#include <sstream>
#include <string>

stringstream ss;
string str;
ss << 16;
ss >> str;
cout << str[i] << str[2] <<endl;

Delta Stepping result.

So, I think I should post some results for Delta Stepping using MPI. Generally, I think this project is pretty hard in the nature that MPI debugging is pretty hard. The result is not excellent but I was happy about it.

I did two implementation for it. But they share some similarities. First of all, the master node sends out partitions of the graph to each nodes. Then, inherited from distributed Dijkstra’s algorithm, each node will keep a local buckets. Now, the task boils down to relaxation which is where the two implementation comes from.

1. Master node will be maintaining distance vector. It listen to updates from nodes, also it sends out newest distance vector to each node as they requested. On the slave nodes side, in each iteration, it will request a copy of distance vector such that it is up to date. And then it will relax nodes if its local, send out request to actual owner to ask for delegated relaxation. Now it sounds pretty easy, but a lot of Asynchronous communication is involved and I even used pthread to test potential accelerations.

2. Very similar to above model. But the thing is there is a lot of re-insertion to the buckets which result a lot of iteration of the outer loop which lead to a lot of request for distance vector. If the number of nodes is large, there must be a lot lot of re-insertion… And network is congested. So, to reduce network overhead, I decided to use p2p model. That is, slave node will broadcast updates to all other nodes. By doing this, all nodes automatically gets updated and they do not even need to ask master node to send out newest copy! what a wonderful idea. But still, each slave node will be put some work on listening these updates such slow down speed. However, the speed up is still optimistic. It is 6…

Results:

 

1st implementation speedup 4, using 4 processors.

2nd speedup 6 using 4 processors.

both implementation suffered from network congestion if increase processor number to 8. Possible improvement could be made by constructing a customized Buckets structure. Re-utilizing bucket is an possible improvement as well. What I was optimizing is purely the model not in deeply in the data structure.

 

How To deactivate/remove ebay seller account

My girlfriend has recently opened an ebay account to sell staff. Things went pretty well, but after she sold all the items, we found ebay continued to charge her seller fee of $8/month. So I went on their website(web staff is always on me even I was not the one started!) to deactivate the seller account. On their help page, it says “removing payment information” = “deactivate seller account” = ” no more monthly fee once you stop listing items”. So it also tells me to go to “seller account” and find “remove all payment methods”. And I did not find it. Here is my way to remove payment:

Go to my account, then personal information

 

Click on remove

 

You are done with ebay. They could’ve made it easier by just adding one button at the most likely page that seller would think to deactivate it. Ebay is one of my favoriate, so I expected it to improve on not only buyer side but also seller side.

 

MPI Project on Shortest Path

I was working on Shortest Path problem most of the last week. It took me so long to understand a variant of Dijkstra’s algorithm called Delta Stepping. ‘Why does it work?’ That is the question I asked in the first 10 passes on that paper! The Author is not explaining in detail ! So i tried to find other sources. There are several, but not many. Eventually, I understood this algorithm and started to code what is stated in paper. I coded using C++ MPI. The sequential runs 126ms for 1k vertices&&10k edges which is okay speed.. But when I increase processor number, the problem just went wild, its running time GROWS linearly, not decreasing! I guess its communication overhead is too much!! Since I already used Asynchronized programming, it was already a pain to the ass to debug. I dont know what to do about it. HOW TO GET SPEEDUP? 

Netezza

For those of you know there is a thing called mySQL, it is time to know Netezza, Netezza is a database system, more precisely, it is a software and hardware system. Its functionality is to parallelize queries.

For example, using mySQL select * from table, say normal computer will run 16s for a large DB.

Netezza-> 1-2s probably.

Netezza is parallelizes this query using utilizing its many processors and many hard drives.

This kind of system is built for large data processing. It is one kind of superComputing I guess.

Install Chrome on ubuntu

Trying to install chrome on Ubuntu, and found out the package has dependency which I did not install, error saying I dont have libxss1.

So, go to terminal type in

sudo apt-get -f install libnss3 libnss3-1d libxss1

sudo dpkg –install #Path#to#Your#chrome#package#

Finally,

google-chrome &

I thought chrome & is the command.. Why dont they make it short?