split tree(C++)

这个代码没测试过。 
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
    int data;
    list<Node *> nodes;
};
------------------------
思路：每个node记录左子树和右子树的node的个数。随便找种顺序遍历树，对每个node的子树，是偶数就砍掉，是奇数就留着。递归做被砍掉的树。

void findnumber(Node *root, map<Node *,int> &num){
  if(!root) {num[root] = 0; return;}
  num[root] = 1;
  list<Node *>::iterator it = root->nodes.begin();
 while( it++ != root->nodes.end() ){
   findnumber(it,num);
   num[root] += num[it];
 }
}

void dfscut(Node *root, map<Node *, int> num, vector<Node *> &res){
   list<Node *>::iterator it = root->nodes.begin();
   while( it != root->nodes.end() ){
      if(num[it] & 1 == 1) { it++;}
      else {
        dfscut(it, num, res);
        it = root->nodes.erase(it);
       num[root] -= num[it];
      }
  }

res.push_back(root);
}


vector<Node *> cutTree(Node *root){
  map<Node *, int> num;
  vector<Node *> res;
  findnumber(root, num);
  if(num[root] & 1 == 1) return NULL;
  dfscut(root, num, res);

return res;
}

find next node of a tree(C++)

写的啥啊看不懂。。重新写一个。。
------06/17/13 rewrite-----------
假设不是最大的节点 ，假设是BST
1, node has  a parent field.
node *nextNode(node *root,  int val){
    if(!root) return NULL;
   while(root && root->val != val){
       if(root->val > val) root = root->left;
       else root = root->right;
   }
   if(!root->right) return root->parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}

2, node doesn't have a parent field.

node *nextNode(node *root,  int val){
   if(!root) return NULL;
   node dummy(0);
   dummy.next = root;
   node *parent = &dummy;
   // find node with value = val
   while(root && root->val != val){
       parent = root;
       if(root->val > val) root = root->left;
       else root = root->right;
   } 
   // find next node
   if(!root->right) return parent;
   root = root->right;
   while(root->left){
       root = root->left;
   }
   return root;
}


------------------old post---------------------------
add a successor pointer for each node in a tree

findsuc(node *root){
  node *parent = NULL;
  node *first,last;
  inorder(root,  first, last);
}

void inorder(node *root,  node *first, node *last){
  if(!root->left) first = root;
  if(!root->right) last = root;
  if(root->left){
   inorder(root->left, first, last);
   last->successor = root;
  }
  if(root->right) {
   inorder(root->right,first,last);
   root->sucessor = first;
   last->successor = NULL;
  }
}
---------------
void solve(Node * r) {
    while (r && r->left) r=r->left;
    Helper(NULL, r);
}

// return the last node of inorder travsal
Node * Helper(Node * prev, Node * r) {
    if (!r) return NULL;
    Node * prev_in_left = Helper(prev, r->left);

    if (prev_in_left) prev = prev_in_left;
    if (prev) prev->successor = r;

    return r->right?Helper(r, r->right):r;
}

quadtree (C++)

问题1 : 为这个 quadtree里面的 node 设计 data structure

然后的问题是关于两个 quadtree 的 intersection, 有两个 quadtree, 它们描述的 
image 是两个相同的 area
比如 都是 [0 1] x [0 1] 这个相同的二维区域的image.

问题二: 写一个函数，返回两个 quadtree的intersection,

这个intersection的规则是: 如果一个区域在 第一个quadtree 里面是
白的，这个相同的区域在 第二个 quadtree里面是黑的，那么intersection
就是白的，简单的说白是 0, 黑是 1, intersection就是两个bit 的 AND
-------------------
//color: 0 means white, 1 means black, 2 means mixed.
struct Qnode{
private:
  int color; 
  Qnode *children;
public:
  Qnode(int c){color = c;};
} 



Qnode *intersection(Qnode *first, Qnode *second){
   if(first == NULL && second == NULL)
 // if both nodes are mixed
  if(first->color == 2 && second->color == 2){
    Qnode *root = new Qnode(2);
    Qnode *newchildren = new Qnode[4];
    int count = 0;
    for(i = 0; i < 4; i++){
    newchildren[i] = intersection(first->children[i], second->children[i]); 
    if(newchildren[i]->color == 0) count++;  
    }
   if(count == 4){
     root->color = 0;
     delete[] newchildren;
   }  
 } 

//if at least one is while
else if(first->color == 0 || second->color == 0)  
  Qnode *root = new Qnode(0);
  root->children = NULL;
} 

//if one black one mixed or two blacks
else if(first->color == 1) Qnode *root =clone(second);
else (second->color == 1) Qnode *root = clone(first);

return root;
 }

Qnode *clone(Qnode *quad){
  if(quad == NULL) return Null;
  Qnode *root = new Qnode(quad->color);
  if(!quad->children) root->children == NULL; 
  else 
for(int i = 0; i < 4; i++){
 root->children[i] = clone(quad->children[i]);
}

return root;
}

Python for data analysis(study notes): chapter 2

Assume dataframe has rows 1,2,3...,n, columns A,B,C,...Z (so it has n records with 26 fields)
Example1:
a,  find 10 most common values in A
   pandas: value_counts()
b, find 10 most common values in A with sub-info of B
   numpy: where(B.str.contains('keyword'), 'keyword', 'no keyword')
   pandas: groupby, size(), unstack()
               .sum(1), aggsort(),take
 other funcs: dropna(), fillna(0),notnull()

Example2:
a, find A, mean of B group by A,C
  pandas: pivot_table(B,rows = A, cols = C, aggfunc = 'mean')
--------------to be continue---------------
 

Python: override hash key

list, dict等object不能直接当hashkey用，但是python里的tuple是可以的，如果要override自己定义的类，添加两个函数

__hash__(self),

__eq__(self, other)

即可。

例如：

class myclass:

  def __init__(self, str1,int2,var3):

     self.var1 = str1

     self.var2 = int2

     self.var3 = var3

  def __hash__(self):

     return hash((self.var1,self.var2))

  def __eq__(self,other):

     return (self.var1,self.var2) == (other.var1,other.var2)  

还有一种方法是用现成module: colletions.namedtuple()，这里就不写了。

参考来源：

http://stackoverflow.com/questions/4901815/object-as-a-dictionary-key

singleton double-checked locking pattern

为什么要用double check呢？因为当已经有instance存在，每次想新建instance时，我们就不需要先启用lock machnism,直接通过判定条件拒绝就行了。

class Singleton{

static Singleton *pInstance;

public:

static Singleton *instance();

 ...

}

Singleton* Singleton::instance() {

if(pInstance == 0) {

// 1st test

  Lock lock;

  if(pInstance == 0) {

  // 2nd test

    pInstance = new Singleton;

  }

}

return pInstance;

}

大数相乘string multiplication C

面试题给的是C string,那就写C吧。基本上就是模拟实际的乘法，因为数值很大存不了int,很自然要用string来存了。考虑进位的需要，结果应该是最多m+n位，再加上末位的'\0'字符，应该给结果分配m+n+1 byte的空间。此外还要考虑负数，不过我char array不熟，折腾了很久，就懒得再加这个case了。。
从写这个code，学到了char[]和char *的区别，最大的不同就是如果char *指向的是string literal, 内容不可更改，所以这里传入参数应该是由char[]定义的。

0. //assume that no negative integers are involved.  
1. //reverse a c string  
2. void reverse(char *c, int start, int end){  
3.     
4.   while(start < end){  
5.   
6.      char tmp = c[start];  
7.   
8.      c[start++] = c[end];  
9.   
10.      c[end--] = tmp;      
11.   
12.  }   
13. }  
14.   
15. char* MultiplyString(char *a,char *b){  
16.   
17.    int m = strlen(a), n = strlen(b);  
18.    //one extra position for carry, another one extra position for '\0'  
19.    char *c = new char[m+n+1];  
20.    memset(c, '0', m+n);  
21.    reverse(a,0,m-1);  
22.    reverse(b,0,n-1);  
23.    int carry;  
24.    //for each position in b, do the multiplication of b[i]*a,update corresponding positions in result c.  
25.    for(int i = 0; i < n; i++){  
26.   
27.      carry = 0;  
28.       
29.      for(int j = 0; j < m; j++){  
30.   
31.        int prod = (b[i] - '0')*(a[j] - '0') + carry + (c[i+j] - '0');  
32.    
33.        carry = prod/10;  
34.   
35.        c[i+j] = prod%10 + '0';  
36.      }  
37.    }  
38.    //deal with the highest position's carry  
39.    if(carry != 0) {   
40.       c[m+n-1] = '0' + carry;   
41.       reverse(c,0,m+n-1);  
42.     }  
43.   
44.    else {  
45.       c[m+n-1] = '\0';  
46.       reverse(c,0,m+n-2);  
47.    }  
48.   
49.    return c;   
50. }  

此外无意间发现一个有趣的swap方法，利用a^a ^b=b，可以不用额外tmp存中间值的：

swap(a,b):
  a = a^b
  b = b^a
  a = a^b