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.

Initialization:
D(i,0) = i, D(0,j) = j

For each i = 1…M
    For each j = 1…N
                     D(i-1,j) + 1
        D(i,j) = min D(i,j-1) + 1
                     D(i-1,j-1) + 2; if X(i) ≠ Y(j)
                                + 0; if X(i) = Y(j)

The complexity is O(MN).

Sample Code:

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];
}

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"

Best of Vim Tips

Common vim commands.
http://rayninfo.co.uk/vimtips.html

Learn Vim script the hard way.

http://learnvimscriptthehardway.stevelosh.com/

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;
}

Reference:
http://www.felix021.com/blog/read.php?2040

Ajax on Rails 3

http://net.tutsplus.com/tutorials/javascript-ajax/using-unobtrusive-javascript-and-ajax-with-rails-3/

Ruby object model

This gallery contains 1 photo.

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. 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 […]

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