Install software from source on a shared Linux server

It's a very common task that installing a software from source on a shared Linux server. If you have root privilege, it suffice to install the package by "sudo apt-get install package_name" on Ubuntu or Fedora, or "yum install package_name" on redhat or centOS. However, the common case is that we do not have root privilege and do not have write access to folders other than $HOME. To install a software or package in this situation, we have to build it from source as follows.

$ mkdir -p ~/tmp      # create a temp folder for installation process
$ export TEMP=~/tmp   # set it to be the sys tmp folder
$ wget url            # get the package source from URL, or you can upload it to the server by sftp
$ unzip file          # if the package is .zip
$ tar xf file         # if the package is a tar ball
$ cd source           # source should be replaced by the folder you just unpacked from .zip or .tar
$ ./configure --prefix=$HOME
$ make
$ make install
$ make clean

Fibonacci calculation algorithm

Iterative version:

int fibonacci(int n) {
    if (n < 2)
        return n;
    int prev = 0;
    int last = 1;
    for (int i=2; i<=n; ++i) {
        prev = last;
        last = prev + last;
    }
    return last;
}

The time complexity is O(n) while the space complexity is O(3) or constant.

Recursive version:

int fib(int n) {
    if (n < 2)
      return n;
    return fib(n - 1) + fib(n - 2);
}

However, this straightforward solution for Fibonacci is extremely inefficient. Since the computation complexity would be exponential as many text books indicated. An intelligent solution is given below, which is O(n). The origin of this solution is here.

int fib(int n, int p0=0, int p1=1) {
    if (n==0)
        return 0;
    else if (n==1)
        return p1;
    else
        return fib(n - 1, p1, p0 + p1);
}

There are recursive solutions are doing even better than O(n). See this link.

Find the ith smallest element of the array in O(n)

How to find the ith smallest element of the array in O(n) time is a frequently asked question. The straightforward solution is sorting the array and return the ith element. However, for general cases, it's proven that sorting algorithms like merge sorting, is lower bound to O(nlogn). Thus finding the ith smallest element is unfeasible by a merge sorting. Although for some special cases, such as, the possible values or data range of the array is relatively small, counting sorting can give a O(n) solution, it doesn't work for general cases. The solution below works generally and the expected running time is O(n).

int find_ith_smallest_elem(int* A, int left, int right, int i) {
    if (left==right)  //only one element left, then it's the answer
        return A[left];
    pivot = random_partition(A,left,right);
    left_partition_length = pivot - left + 1; //1 counts for the pivot itself
    if (i==left_partition_length)
        return A[pivot];  //pivot is the answer
    else if (i<left_partition_length)
        return find_ith_smallest_elem(A,left,pivot-1,i);
    else
        return find_ith_smallest_elem(A,pivot+1,right,i-left_partition_length);
}

//randomly choose a pivot and partition the array into two parts, where the left part only
//contains elements smaller than the pivot while the right part only contains larger ones
int random_partition(int* A, int left, int right) {
    int pivot = rand(left,right);
    swap(A,pivot,right); // swap the pivot and the right-most element
    int pivot_value = A[right];
    int i = left - 1;
    for(int j=left; j<right; ++j) {
        if (A[j]<=pivot_value) {
            i++;
            swap(A,i,j); 
        }
    }
    swap(A,i+1,right);
    return i+1;
}

JSON Parsing in java with Jackson

When it comes to API data and results (like google APIs), json is of great favor to java developers. There are more than 50 libraries for json processing in different languages. To get an overview of json structure and access the libraries, please refer to http://www.json.org/.

Jackson offers three alternative methods for processing JSON:

• Streaming API reads and writes JSON content as discrete events.
• Tree Model provides a mutable in-memory tree representation of a JSON document.
• Data Binding converts JSON to and from POJOs based either on property accessor conventions or annotations.

For a known structure of API return and the requirement to reconstruct similar data skeleton, it would be effortless if Tree Model is used for the recovery.

To download the latest version of Jackson, please refer to:http://wiki.fasterxml.com/JacksonDownload. Both jackson.core and jackson.mapper will be needed for Tree Model processing.

To add the dependencies from internal jars in Eclipse, refer to:How to Add JARs to Project Build Paths in Eclipse

Tree Model Processing Step by Step

Facebook JavaScript SDK Call after FB.init()

When developing Facebook Apps, the JavaScript SDK is usually loaded asynchronously to not block loading other elements of your page. However, it leaves us a problem: every JavaScript SDK call must be made after the SDK loading. Otherwise, a "FB not defined" error will be thrown. There are two common ways to handle this situation.

Put the codes inside the callback function of fbAsyncInit process

<div id="fb-root">
</div>
<script>
  window.fbAsyncInit = function() {
    FB.init({
      appId      : 'YOUR_APP_ID',
      channelUrl : '//WWW.YOUR_DOMAIN.COM/channel.html',
      status     : true,
      cookie     : true,
      oauth      : true,
      xfbml      : true
    });
    // Put Your Codes Here
  };

  (function(d){
     var js, id = 'facebook-jssdk'; if (d.getElementById(id)) {return;}
     js = d.createElement('script'); js.id = id; js.async = true;
     js.src = "//connect.facebook.net/en_US/all.js";
     d.getElementsByTagName('head')[0].appendChild(js);
   }(document));
</script>

Add delay to your SDK call

/**
 * do something when user leaves a new comment
 */
function fb_event_subscribe() {
    try {
        FB.Event.subscribe('comment.create', function(response) {
            // do something here
        });
    }
    catch(err) {
        setTimeout("fb_event_subscribe()",1000); // try again later
    }
};

/**
 * subscribe the Facebook event "comment.create" after a one second delay, which
 * makes sure FB JavaScript SDK asynchronous initialization FB.init() is finished.
 */
setTimeout("fb_event_subscribe()",1000);

Iterate over a Map(HashMap) in Java

Here are three methods of iterating through a Map(HashMap) in Java and their pros and cons. They all works for any map implementation in Java, e.g. HashMap, TreeMap, HashTable,LinkedHashMap.

Method #1
Iterating over Entries

Map<Integer, Integer>; map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

pros : You can get both keys and values via entrySet().
cons: NullPointerException will be thrown if you try to iterate over a null map. You should always check for null references before iterating.

Method #2
Iterating over either Key or Value Sets

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

//iterating over keys only
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}

//iterating over values only
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}

pros: If all you need is either key sets or value sets, this method is about 10% faster than iteration over entrySet(), and also cleaner.

cons: The same as above

Method #3
Iterating using Iterator

--With Generics

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

--Without Generics

Map map = new HashMap();
Iterator entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry entry = (Map.Entry) entries.next();
Integer key = (Integer)entry.getKey();
Integer value = (Integer)entry.getValue();
System.out.println("Key = " + key + ", Value = " + value);
}

The same method can be used for obtaining the key and value sets respectively. Its performance is equal to for-each loop.

pros: It is the only way if you want to remove entries during iteration by implementing iterator.remove(). If you do this in for-each loop, you will get unpredictable results.

cons: Look a little redundant than other methods.

Method #4
Iterating over key sets and search values (inefficient)

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = " + key + ", Value = " + value);
}

Getting values by keys is inefficient and time-consuming, in different Maps it can be 20% to 200% slower than Method #1.

Arrow keys not working in Vim on Cygwin

Installed Cygwin today on my machine (ThinkPad, XP SP3). The arrow keys in Vim always bring me out from insert mode. And there is no syntax highlight at all.

The quick fix is copy /usr/share/vim/vim73/vimrc_example.vim to ~/.vimrc. Then everything works perfectly now.