Pi Day

Quite interesting:

http://en.wikipedia.org/wiki/Pi_Day

探索π值大事记

China Digital Science and Technology Museum.

Programmer Competency Matrix

Programmer Competency Matrix

This can be useful for self-checking on programming skills.

Wildcard character pattern matching

The problem is how to do string matching on a pattern including '*' (0-any characters) and '?' (0-1 character) wildcard characters.

Obviously when come into '*', you can ignore it, or eat the current input char, then recursively repeat this process. When come into '?', you can ignore it or eat the current input char. Therefore comes this backtracking recursive solution:

int match(char * s, char * p) {
  printf("string:%s \t pattern:%s\n", s, p);

  if (*s == 0) return *p == 0;
  if (*p == 0) return 1; // or "return *s == 0;" if you don't want extra char in s.
  if ('?' == *p) return match(s+1, p+1) || match(s, p+1);
  if ('*' == *p) return match(s+1, p) || match(s, p+1);
  if (*s == *p) return match(s+1, p+1);
  return 0;
}

int DoMatch(char * s, char * p) {
  if (s == NULL) return NULL == p;
  if (p == NULL) return 1; // or NULL == s if don't want extra char in s.
  return match(s, p);
}

Call DoMatch(string, pattern) to start the process. Note in the implementation you must use a+1 instead of ++a since the latter would change the value of a and causes problem for the next invocation of match call. Use of a++ is even worse since a won't be incremented at all until the match call finishes. These are simple issues but easy to ignore until you stumble into problem.

Since backtracking is used, this solution can be exponential in nature. This solution can be used when the input size is small.

This problem obviously is a simplification of regular expression string matching, such as used in lex, in Perl, Python, Java, C# etc. In a general regular expression we start with several basic building blocks (single symbol, concatenation of symbols, kleene closure (*, extensions are + and ?), alternation (|)) to build up the NFA for a regular expression. The next key step is to convert a NFA (Non-deterministic Finite Automata) to a DFA (Deterministic Finite Automata). Using DFA, the complexity is O(n) or linear, and therefore is the ideal solution. Check any computation theory textbook for the algorithm.

Career-Cup Top 150 Questions

The book is pretty easy to read.

There are over 20 chapters, each covers one area of topic, includes a short discussion and a small number of relevant problems.

Solutions to all questions are provided at the later half of the book.
http://www.docin.com/p-41796787.html
http://www.careercup.com/book

Reservoir Sampling

Problem: Given a stream of n elements (n is unknown), sample an element with the same probability for each element in ONE pass. (e.g. given a text file with unknown number of lines, randomly print one line in the same probability for each line, using ONE pass only.)

If two passes are allowed, then it's easy since the first pass can get the number of lines, then just randomly pick one in second pass. For one pass, this does not work since total number of lines is unknown.

Solution: Reservoir Sampling.

References:
http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx
http://gregable.com/2007/10/reservoir-sampling.html

[Added 3/6/2010]
A straightforward way of thinking about this is:

At the n-th element, we already have a sampled element x for the first n-1 elements, now choose between x and n with the probability of (n-1)/n for x, and 1/n for the n-th element. This is is someway similar to the card shuffling algorithm.

The next extension is to sample m (instead of 1) elements out of n. Then just choose the n-th element with probability m/n, and if chosen, replace the n-th element with a random element in the previously chosen m elements.

The next extension is weighted sampling. There are discussion in the first link above.

ASP.NET's Membership, Roles, and Profile

Pretty good introduction to ASP.NET's Membership, Roles, and Profile:
http://www.4guysfromrolla.com/articles/121405-1.aspx

Get UserId:
MembershipUser myObject = Membership.GetUser();
string UserID = myObject.ProviderUserKey.ToString();

Code to update membership property:
MembershipUser u = Membership.GetUser("member");
u.IsApproved = false;
Membership.UpdateUser(u);
Note that must use UpdateUser() method otherwise it won't update.

Drupal - CCK and VIEW

Use CCK and VIEW modules of Drupal:
http://learn.awakenedvoice.com/2007/07/30/drupal-cck-and-views-tutorial/
http://www.apaddedcell.com/creating-a-custom-home-page-in-drupal-using-views

- Make view column header sortable.

In Basic settings, style "table" has this option: click on the "*" to its right, in the style options panel, check "Sortable" checkbox to the fields that you want to be sortable.

- Add more fields to profile.

Default profile contains only account name and email. You can add more by using the Profiles module in Administer -> User management -> profiles.

- Show two fields in one column (The following is copied from this link):

By default, each field is its own column. However, you can place multiple fields in the same column. To do this, pick which field you want to represent the column, then pick another field and set the 'column' value to that field. You can place as many fields as you like in a single column, but only the main field in a column can be click-sorted.

This way, you can allow the user to enter first name and last name separately at registration, then show full name in a view.