B+ Tree operations

References: http://www.cs.jhu.edu/~hager/Teaching/cs226/Notes/B+Tree.pdf

Linux Command Line Tips

Linux command line tips that every linux user should know:
http://www.linuxstall.com/linux-command-line-tips-that-every-linux-user-should-know/

Parallelism For Prefix Sum

Recently I am studying parallel algorithm. Many algorithms taught in class use prefix sum. Given an array of n elements { a1, a2, a3, ... , an }, we are to calculate n partial sum { s1, s2, ... , sn }, where si = a1 + a2 + ... + ai. It is pretty straight forward that prefix sum is solved by O(n). Can we do better using parallelism?

The answer is yes. We can solve it using classical divide and conquer. Following is the pseudo-code:

This picture better illustrates the idea of above algorithm:

Here is a simple implementation of this algorithm using cilk concurrency platform:

void prefix_sum(LL *a, LL *s, unsigned int len){
    if (len == 1){ 
        s[1] = a[1];
        return ;
    }   
    int itr;
    cilk_for(unsigned int i = 1; i <= len; i++){
        s[i] = a[i];
    }   
    for (itr = 1; (1 << itr) <= len; itr++){
        // cout << itr << endl;
        cilk_for(unsigned int i = (1 << itr); i <= len; i += (1 << itr)){
            s[i] = s[i] + s[i - (1 << (itr - 1))];
        }
    }   
    itr--;
    while (itr >= 0){ 
        cilk_for(unsigned int i = (1 << itr); i <= len; i += (1 << itr)){
            if ((i >> itr) == 1){ 
                s[i] = s[i];
            } else if ((i >> itr) % 2 == 1){ 
                s[i] = s[i] + s[i - (1 << itr)];
            }
        }
        itr--;
    }   
}

Linux Directory Structure

This article illustrates Linux filesystem structure and the meaning of higher-level directories.
See:
http://www.thegeekstuff.com/2010/09/linux-file-system-structure/

Random Selection

Today when I coded ads recommendation for my db project, it reminds me some classical problems about random selection.

Q1. How to randomly select an element from a linked list whose size is unknown.

Node *ret = NULL;
int cnt = 0;

for (Node *p = head; p != NULL; p = p->next){
    if (rand() % ++cnt == 0)
        ret = p;
}

Q2. How to randomly select K elements from a huge linked list whose size is unknown.

Since the linked list is huge, we can assign a random number in [0, 1] to each element as its weight, then we can pick first K maximum-weighted elements.

Another solutions is to select the ith element with probability 1/i. We can prove that each element is selected with probability 1/N.

Ruby methods

Ruby provides way to call and define methods dynamically.

When you invoke a method, you actually send a message to an object. To illustrate this idea, let’s look at the following example.

class MyClass
  def greeting
    "Hello"
  end
end
obj = MyClass.new obj.greeting # => "hello"
obj.send :greeting # => "hello"

We can see that when you call greeting(), it actually goes through send() by sending the name of the method. This technique is called Dynamic Dispatch which means you can decide which method to call at runtime.

In Ruby, you also can define method dynamically with Module#define_method(). All you need to do is to pass a method name and a block.

class MyClass
  define_method :hello do
    "hello"
  end
end

obj = MyClass.new
puts obj.send :hello

With define_method(), we can define general-purpose method template to avoid duplicated code.

Another powerful thing in Ruby is method_missing(). With Ruby, there’s no compiler to check the method calls. So when you call a method that doesn’t existed, Ruby will finally call method_missing which raises NoMethodError. We can override method_missing() to handle no corresponding method. This is called Ghost Method since actually there is no corresponding method that exists.

class MyClass
  def method_missing(name, *args)
    puts "You tried to call #{name}, but this method is undefined"
  end
end

obj = MyClass.new
obj.hello   # => "You tried to call hello, but this method is undefined"

Ruby object model

If you pick up Ruby, you will love it! Currently I am reading the book Metaprogramming Ruby to dive into the depth in Ruby world.

1. Open Classes

You can easily add new methods to classes that has already existed, like the following:

class String
 def to_alphanumeric
  gsub /[^\w\s]/, ''
 end
end 

Now the String class has a new method ‘to_alphanumeric’. In fact, when you define a class, if it is predefined(like String), Ruby will open the existing class and add your methods. Otherwise, Ruby will create a class for you. This technique is simply called Open Class. So, you can overwrite the existing methods.

2. Object and Class Relationship

In Ruby, unlike Java, there is no connection between an object’s class and its instance variables. When you assign values, they just spring into existence in object. Ruby objects hold instance variables and reference to their classes which carry a list of methods. Here is an example:

class A
 def hey
  @v = "hey"
 end
end

obj = A.new
obj.instance_variables # => []
obj.hey
obj.instance_variables # => ["@v"]

Here is the relationship between class and object:

You can see that MyClass is just an object. But what MyClass has is instance methods that objects can call. Be careful with this jargon ‘instance method‘. It actually took me some time to understand this. And you can verify by running following code:

Array.instance_methods == [].methods # => true
Array.methods == [].methods          #=> false

3. Method

When you call a method, Ruby actually does two things:

• Method lookup
• Execute the method

In method lookup, there are concepts receiver and ancestor chain. Receiver is simply the object you call a method on. The ancestor chain is the path from class to its superclass, superclass to superclass’ superclass and so on. Ruby will look at each class’ instance methods along the chain until find the right method. One thing to notice that when you include a module in your class, Ruby creates an anonymous class that wraps the module and add it in the chain. In fact, Object includes module Kernel, that’s why you can call methods like puts, print in your class.

Manacher's algorithm

Longest palindromic substring is the problem of finding a maximum-length substring of a given string that is also a palindrome. Usually this can be done by dynamic programming or suffix array. However, Manacher's algorithm is a more efficient algorithm that takes only O(n) time.

The main idea is to turn odd/even palindromic substring into odd palindromic string. We add special characters among original characters. For example, we convert 'abba' to '#a#b#b#a#', 'aba' to '#a#b#a#'. And add '$' at the front of the string for handling edge cases.

Let's assume S = '1221' as to illustrate our algorithm. S' = '$#1#2#2#1#'. And we let array P to store the extension to the left(or right) in S'. So here,

S  #  1  #  2  #  2  #  1  #

P  1  2  1  2  5  2  1  2  1

P.S. P[i] - 1 is the length of the original palindrome.

Next question is how to calculate array P. Let id be the max palindromic substring's center, and mx = id + P[id], i.e., the right end of the substring. Then we have the following property:

    If mx > i, the P[i] >= min(P[2 * id - i], mx - i)

int mancher(){
    int mx = 0, id, i, ans = 0;
    memset(p, 0, sizeof(p));

    for (i = 1; i < m; i++){
        if (mx > i){
            p[i] = min(p[2 * id - i], mx - i);
        } else {
            p[i] = 1;
        }
        for ( ; str2[i - p[i]] == str2[i + p[i]]; p[i]++);
        if (i + p[i] > mx){
            mx = i + p[i];
            id = i;
        }
    }
    for (i = 0; i < m; i++){
        ans = max(ans, p[i]);
    }
    ans--;
    return ans;
}

Minimum Editing Distance

Minimum editing distance is to compute the minimum number of operations that transform a string X to another string Y by inserting, deleting and changing characters. This problem is solved by dynamic programming.

int m, n, dp[2][N];
char str1[N], str2[N];

int min_edit_dist(){
    int i, j, pre, cur, u, v;

    pre = 0, cur = 1;
    m = strlen(str1+1);
    n = strlen(str2+1);

    for (i = 0; i <= n; i++) dp[0][i] = i;
    for (i = 1; i <= m; i++){
        dp[cur][0] = i;
        for (j = 1; j <= n; j++){
            u = dp[pre][j]+1;
            v = dp[cur][j-1]+1;
            if (str1[i] == str2[j])
               dp[cur][j] = MIN(dp[pre][j-1], MIN(u, v));
            else
               dp[cur][j] = MIN(dp[pre][j-1] + 2, MIN(u, v));
        }
        pre ^= 1; cur ^= 1;
    }
    return dp[pre][n];
}

RB-Tree Implementation

Red-Black tree has the following properties:

• Root color is black
• If a node is red, then both its children are black
• For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

#define RED 1
#define BLACK 0
struct Node {
 Node *lc, *rc, *pa;
 int color;
 int key;
 Node(){ }
 Node(int val){
  lc = rc = pa = NULL;
  key = val;
  color = RED;
 }
};

class RBTree {
 public:
 Node *root;

 RBTree(){
  root = NULL;
 }

 void print(){
  _print(root, 0);
  cout << endl <rc != NULL){
   u = u->rc;
  }
  return u;
 }

 void remove(Node *z){
  Node *y = z, *x;
  int color;
  if (z == NULL){
   return ;
  }
  color = y->color;
  if (z->lc == NULL && z->rc == NULL){
   if (z->pa == NULL){
    root = NULL;
   } else if (z == z->pa->lc){
    z->pa->lc = NULL;
   } else {
    z->pa->rc = NULL;
   }
   x = NULL;
  } else if (z->lc == NULL){
   x = z->rc;
   transplant(z, z->rc);
  } else if (z->rc == NULL){
   x = z->lc;
   transplant(z, z->lc);
  } else {
   y = minimum(z->rc);
   color = y->color;
   x = y->rc;
   if (y->pa == z){
    if (x){
     x->pa = y;
    }
   } else {
    transplant(y, y->rc);
    y->rc = z->rc;
    y->rc->pa = y;
   }
   transplant(z, y);
   y->lc = z->lc;
   y->lc->pa = y;
   y->color = z->color;
  }
  if (color == BLACK && root != NULL){
   puts("Fixup");
   remove_fixup(x);
  }
  delete z;
 }

 private:

 void left_rotate(Node *x){
  Node *y = x->rc;
  x->rc = y->lc;
  if (y->lc != NULL){
   y->lc->pa = x;
  }
  y->pa = x->pa;
  if (x->pa == NULL){
   root = y;
  } else if (x == x->pa->lc) {
   x->pa->lc = y;
  } else {
   x->pa->rc = y;
  }
  y->lc = x;
  x->pa = y;
 }

 void right_rotate(Node *x){
  Node *y = x->lc;
  x->lc = y->rc;
  if (y->rc != NULL){
   y->rc->pa = x;
  }
  y->pa = x->pa;
  if (x->pa == NULL){
   root = y;
  } else if (x == x->pa->lc){
   x->pa->lc = y;
  } else {
   x->pa->rc = y;
  }
  y->rc = x;
  x->pa = y;
 }

 void transplant(Node *u, Node *v){
  if (u->pa == NULL){
   root = v;
  } else if (u == u->pa->lc){
   u->pa->lc = v;
  } else {
   u->pa->rc = v;
  }
  v->pa = u->pa;
 }

 void _print(Node *node, int dep){
  if (node == NULL) return ;
  if (node->lc) _print(node->lc, dep + 1);
  printf("%d: col %d -- dep %d\n", node->key, node->color, dep);
  if (node->rc) _print(node->rc, dep + 1);
 }

 void _insert(Node *z){
  Node *y = NULL, *x = root;
  while (x != NULL){
   y = x;
   if (z->key key){
    x = x->lc;
   } else {
    x = x->rc;
   }
  }
  z->pa = y;
  if (y == NULL){
   root = z;
  } else if (z->key key){
   y->lc = z;
  } else {
   y->rc = z;
  }
  z->lc = z->rc = NULL;
  z->color = RED;
  insert_fixup(z);
  // puts("**** _insert done");
 }

 void insert_fixup(Node *z){
  Node *y;
  if (z == root){
   z->color = BLACK;
   return ;
  }
  // printf("insert_fixup %d\n", z->pa->color);
  while (z != root && z->pa->color == RED){
   if (z->pa == z->pa->pa->lc){
    y = z->pa->pa->rc;
    if (y != NULL && y->color == RED){
     z->pa->color = BLACK;
     y->color = BLACK;
     z->pa->pa->color = RED;
     z = z->pa->pa;
    } else if (z == z->pa->rc){
     z = z->pa;
     left_rotate(z);
    } else {
     z->pa->color = BLACK;
     z->pa->pa->color = RED;
     right_rotate(z->pa->pa);
    }
   } else {
    y = z->pa->pa->lc;
    if (y != NULL && y->color == RED){
     z->pa->color = BLACK;
     y->color = BLACK;
     z->pa->pa->color = RED;
     z = z->pa->pa;
    } else if (z == z->pa->lc){
     z = z->pa;
     right_rotate(z);
    } else {
     z->pa->color = BLACK;
     z->pa->pa->color = RED;
     left_rotate(z->pa->pa);
    }
   }
  }
  root->color = BLACK;
 }

 Node *_search(Node *rt, int key){
  if (rt == NULL || rt->key == key){
   return rt;
  }
  if (key key){
   return _search(rt->lc, key);
  } else {
   return _search(rt->rc, key);
  }
 }

 void remove_fixup(Node *x){
  Node *w;
  if (x == NULL) return ;
  printf("--- %d\n", x->key);
  while (x != root && x->color == BLACK){
   if (x == x->pa->lc){
    w = x->pa->rc;
    if (w->color == RED){
     w->color = BLACK;
     x->pa->color = RED;
     left_rotate(x->pa);
     w = x->pa->rc;
    }
    if (w->lc->color == BLACK && w->rc->color == BLACK){
     w->color = RED;
     x = x->pa;
    } else if (w->rc->color == BLACK){
     w->lc->color = BLACK;
     w->color = RED;
     right_rotate(w);
     w = x->pa->rc;
    } else {
     w->color = x->pa->color;
     x->pa->color = BLACK;
     w->rc->color = BLACK;
     left_rotate(x->pa);
     x = root;
    }
   } else {
    w = x->pa->lc;
    if (w->color == RED){
     w->color = BLACK;
     x->pa->color = RED;
     right_rotate(x->pa);
     w = x->pa->lc;
    }
    if (w->rc->color == BLACK && w->lc->color == BLACK){
     w->color = RED;
     x = x->pa;
    } else if (w->lc->color == BLACK){
     w->rc->color = BLACK;
     w->color = RED;
     left_rotate(w);
     w = x->pa->lc;
    } else {
     w->color = x->pa->color;
     x->pa->color = BLACK;
     w->lc->color = BLACK;
     right_rotate(x->pa);
     x = root;
    }
   }
  }
  x->color = BLACK;
 }
};

int main(){
 int cmd, v;
 RBTree rb;
 srand(time(NULL));
 for (int i = 0; i > cmd){
  if (cmd == 0){
   // insert
   cin >> v;
   rb.insert(v);
   puts("Insert done");
  } else if (cmd == 1){
   // search
   cin >> v;
   Node *p = rb.search(v);
   if (p) printf("Found %d\n", v);
   else printf("Not Found\n");
  } else if (cmd == 2){
   // remove
   cin >> v;
   Node *p = rb.search(v);
   puts("Removing");
   if (p) rb.remove(p);
   puts("Remove done");
  } else {
   rb.print();
   puts("");
  }
 }
}

Caching Tutorial

Caching Tutorial for Web Authors and Webmasters

http://www.mnot.net/cache_docs/

Unix as IDE

This article illustrates common tools for the unix/linux programming environment

http://blog.sanctum.geek.nz/series/unix-as-ide/

Technical Interview Questions - Data Structure

1. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time.

    min/max heap

2. There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.

    bitmap?

3. For an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.

    hash table

4. What is the complexity of an algorithm to check whether a binary tree is symetric or not. No need to check the data only the structure needs to be verified.

bool IsSymmetric(Node* r) {

    if ( r == NULL ) return true;

    return IsSymmetric(r->left, r->right);

}



bool IsSymmetric(Node* L, Node* R) {

    if ( !L && !R ) return true;

    if ( !L && R || L && !R ) return false;

    return IsSymmetric(L->left, R->right) && IsSymmetric(L->right, R->left);

}

5. Implement stack class, algorithm for returning minimum number

6. Implement Trie

Technical Interview Questions - Linked List

1. Implement enqueue and dequeue operations using stack(s).

2. Sort a link list using merge sort.

3. You are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.

4. Randomly select an element from a linked list. The length of linked list is unknown.

5. Reverse a linked list, recursion or non-recursion.

6. Given a circular linked list where the length of the stem can be arbitrary (the shape of the list can be like number 6). What is the size of the list? Or determine if a linked list has a loop.

7. How would you find the nth to last element in a linked list?

Use two pointers. Initalize both pointers to the front of the list then use a loop to traverse one pointer Nth times. Then moves both pointers until one reaches the end of the list. The second pointer is Nth to last element.