String tokenizer by hand

I was thinking of implementing my custom "StringTokenizer" and here it is. The complexity is O(n) which means it depends on the size of the string.

public static ArrayList tokenizer(String input){
  ArrayList tokenizedStr = new ArrayList();
  StringBuffer str = new StringBuffer();
  int strLength = input.length();
  int index = 0;
  while (index < strLength) {
    char curr = input.charAt(index);
    if (curr != ' '){
      str.append(curr);
    } else {
      tokenizedStr.add(str);
      str = new StringBuffer();
    } 
    if ((index == strLength-1 ) && (curr != ' ')) {
      tokenizedStr.add(str);
    }
    index++;
  }
  return tokenizedStr;
}

The most interesting part of this method if the condition to check if we have reached the last character of the string and to make sure if it is also not a whitespace character.

UPDATE:
On a second thought, the algorithm in this method is not perfect because it will still retain inline whitespace characters. This is a much better way to tokenize the strings

  while (index < strLength) {
    char curr = input.charAt(index);
    if (curr != ' '){
      str.append(curr);
    } else {
      if (str.length() != 0) {
        tokenizedStr.add(str);
      }
      str = new StringBuffer();
    } 
    if ((index == strLength-1 ) && (curr != ' ')) {
      tokenizedStr.add(str);
    }
    index++;
  }

An example of solving this in recursion is at "Tokenizing String Recursively".

Screencast of my iPhone App

Fibonacci Sequence

Here's an interesting usage of "memoization". According to Wikipedia, "In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.".

There is actually a drawback if we are using plain and simple recursion to compute the Fibonacci sequence using long datatype (because we are only limited to hold the first 48 Fibonacci numbers). Memoization helps to speed up the computation time by saving already computed values into memory (and we can use BigInteger datatype). An example implementation is as below:

import java.math.BigInteger;
import java.util.ArrayList;

public class Fibonacci {

  /** Variables for memoization **/
  private static ArrayList fibMemoized = new ArrayList();
  static {
    fibMemoized.add(BigInteger.ZERO);
    fibMemoized.add(BigInteger.ONE);
  }

  /** Memoized method to retrieve stored computed values **/
  public static BigInteger fibonacci(int n) {
    if (n >= fibMemoized.size()) {
      fibMemoized.add(n, fibonacci(n-1).add(fibonacci(n-2)));
    }
    return fibMemoized.get(n);
  }

  /** Old school recursion **/
  public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
  }

  /** Driver **/
  public static void main(String[] args) {
    int N = 45;
    System.out.println(fibonacci(N));
    System.out.println(fib(N));
  }

}

You may try copying the codes and run it locally to observe the difference in performance. The typical recursive method runs slower because it computes the Fibonnaci numbers from scratch many times. Unlike the memoized method, the ArrayList is used to store the previously computed values. While memoized method is more superior in terms of speed, we are actually sacrificing space in order to achieve greater speed.

Recursion vs iteration

Situations not to use recursion:
- recomputation of values (fibonacci, factorial, GCD)
- exhaust memory very quickly

Advisable to use iteration or memoization, instead, if you are so keen and persistent to implement recursion.

How to record the behavior of Internet users

I would like to discuss about this interesting topic which is sometimes wrongly perceived by many people as a menacing way practiced by some, if not many, Internet companies to invade one's privacy. I supposed there is a huge gap or the level of understanding that separates the consumers and the business people.

The technological perspective that I am illustrating in this article is about implementing "click-tracking". For software engineers that really know and understand whatever they are implementing, the server has no control over the dynamic HTML pages once the bits and bytes are presented to the end-users. For now, do we agree unanimously at this stage?

Great, thank you for agreeing to my thoughts! If so, I shall elaborate further about how "click-tracking" is implemented, especially at the anchor element <a> in the HTML document. There are at least three significant ways to track the links the users are clicking. I am taking an online video company as an example.

[1] Redirecting users to different servlets
This is the most common way to track user clicks. Imagine you are a registered user and while your session is still active:
1. You do a keyword search
2. You get a compiled list of result items in the result page
(eg: http://www.example.com/search/?q=keyword_string&pg=1)
3. You click at the link you think is most relevant to you
(eg: http://www.example.com/view/?videoID=12345678)
4. You enjoy watching the selected video
5. You demand for more videos and you reiterate step 1 again.
But WAIT ... what laymen do not know is that while they are busy with their viewing activities, the servers are busy harvesting the clicks of the links. Technically speaking, the servlet that is related to the URL request will update the user database with the unique video IDs, which I think is the most important element. Many interesting things can take place from here and one of them is to count the number of viewed videos.

[2] AJAX
Some of you might have this question popping in your mind "But what if the page is loaded dynamically using AJAX?". The implementation is actually quite similar to the one mentioned previously but with a slightly different flavor. By using AJAX, you can implement an asynchronous method to pass the video ID as an argument to the servlet using GET or POST method. The servlet will then take care of the rest without the user knowing whatever happens behind the scene (or their clicks are monitored).

[3] Javascript / AJAX
The other method to perform "click-track" is by using Javascript. This is used in the scenario where the search result page contains links that redirect users to the original sources and not within their domain. In other words, a totally different URL altogether. A GET or POST method is used to send the data back to the server.

While the 3 suggested implementations seem similar, they are actually not the same. I hope you find this article a good read and insightful about performing "click-track".

Binary Tree != B-tree

NOTE TO SELF: Binary tree is not B-tree
B-tree is commonly used in databases and filesystems.
Binary tree is used for binary search.

My pet project web-based music jukebox (part 2)

I have added a major feature in my web application to internationalize the page content. Hope you enjoy watching this video :)