Replacing whitespace characters in a string

Here is an example of method overloading - same method name with different number of parameters. The complexity of this algorithm is O(n) because the input string is scanned character by character.

But what if there is a input with a massive size? I would want to partition out the string into several portion depending on the size threshold which can be set in the method and the hash the partitioned texts into a hashmap. Threading is possible in this context because the texts will be processed synchronously instead of sequentially.

public static StringBuffer removeSpace(String input){
  return removeSpace(input, "%20");
}

public static StringBuffer removeSpace(String input, String fillerString){
  StringBuffer sb = new StringBuffer();
  int strLength = input.length();
  int index = 0;
  while(index != (strLength)){
    if (input.charAt(index) != ' ') {
      sb.append(input.charAt(index));
    } else {
      sb.append(fillerString);
    }
    index++;
  }
  return sb;
}

You may test this code with this sample method calls:

System.out.println(removeSpace("Hello World, I am Nicholas Key"));
System.out.println(removeSpace("Hello World, I am Nicholas Key", "[SPACE]"));

Usefulness of BigInteger

It's way much better than Integer, the primitive type; simply because we won't be restricted with arithmetic overflow issue. An example is in this method to compute factorial.

public static BigInteger factorial(int n){
  BigInteger result = BigInteger.ONE;
  for (int count = 1; count <= n; count++) {
    result = result.multiply(BigInteger.valueOf(count));
  }
  return result;
}

The precision is still well maintained even if you iterate through the first 38 numbers. Give it a try if you are not convinced :)
UPDATE: there is a fundamental flaw in this loop. In the previous code, I demonstrated for (int count = 1; count < n; count++). It has changed to for (int count = 1; count <= n; count++)

Numbers with commas

Here's a simple method to include commas after every third digit from the right:

public class Utilities{
  private static int startingPivot;
  private static final int INDENT = 3;

  public static StringBuffer decimalize(int input){
    String conv = Integer.toString(input);
    StringBuffer sb = new StringBuffer();

    int commaIndex = conv.length() / INDENT ; 
    int strLength = conv.length();

    startingPivot = (strLength) - (commaIndex * INDENT );
    if (startingPivot == 0) {
      startingPivot = INDENT ;
    }

    for (int index = 0; index < strLength; index++) {
      if (index == startingPivot) {
        sb.append(",");
        startingPivot = startingPivot + INDENT;
      }
      sb.append(conv.charAt(index));
    }
    return sb;
  }
}

You may try this code by making this method call

System.out.println(Utilities.decimalize(1234567890));

and the output is 1,234,567,890
NEAT :D

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".

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.

Solving Palindrome Using Recursion

This is a follow-up article about solving palindrome using recursion. While we solved this problem previously using iteration (link to previous article), I am demonstrating the way of solving it in a recursive manner.

  public static void isPalindromeRecursive(String text){
    text = text.toLowerCase().replaceAll("[\\W\\_*]", "");
    if (helperFunction(text, 0, text.length()-1)) {
      System.out.println("Is a Palindrome");
    } else {
      System.out.println("Is not a Palindrome");
    }
  }

  private static boolean helperFunction(String input, int leftIndex, int rightIndex){
    if (leftIndex < rightIndex) {
      if (!(input.charAt(leftIndex) == input.charAt(rightIndex))) {
        return false;
      }
      leftIndex++;
      rightIndex--;
      helperFunction(input, leftIndex, rightIndex);
    }
    return true;
  }

The one missing number

This question sounds rather intimidating but when you analyze it deep enough, you will be amazed about the way this problem is solved - "Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element." Many of us might have quickly jumped into the solution in which many fancy data structures are being used. But actually there is a much easier way to solve this problem. The suggested code is as follow. I think the complexity of this suggested algorithm is O(n). It is a linear operation as you can see in the implementation.

public static int missingNumber(int input[]){
  int arrSize = input.length;
  int totalLength = arrSize + 1;
  int missingNumber = 0;
  for (int count=1; count <= totalLength; count++) {
    missingNumber = missingNumber + count;
    if ((count-1) < arrSize) {
      missingNumber = missingNumber - input[(count-1)];
    }
  }  
  return missingNumber;
} 

Nicholas is salohciN

I have been thinking a lot about solving a problem optimally and efficiently. Let us take a look at a seemingly easy computer science problem but might take some of us quite a bit of time to come up with an elegant solution. It is the problem about reversing a string - be it by letters or by words. Below is my solution to reverse a string by letters.

public static String reverseCharacters(String text){
  StringBuffer reversed = new StringBuffer();  
  int len = text.length()-1;
  for (int i=len; i>=0; i--) {
    reversed.append(text.charAt(i));
  }
  return reversed.toString();
}

It is observed that I am decrementing the counter in the for-loop. Why is that? It is simply because I want to start to look at the given string in a backward manner. A StringBuffer is used to append the letters because append() operation is not as costly as we would have used a string and concatenate the letters. Simple isn't it? Many of us might thought that we could have used the reverse() method instead, rather than coding this unnecessarily. I would say this suggested solution is very reliable if we are looking at solving this problem more discretely.

Next we will explore how to reverse a string by words. Once again I am suggesting the cheapest way to solve it. Some of us might thought that we have to first split the strings by a whitespace and then push the words into a stack, which we will then pop every single item out from the stack. Here is my approach in solving it using very little copying and no temporary variables.

public static String reverseWords(String text) {
  StringBuffer reverse = new StringBuffer();
  String[] textArray= text.split("[\\s*]");
  int len = textArray.length-1;
  for (int i=len; i>=0; i--) {
    reverse.append(textArray[i]).append(" ");
  }
  return reverse.toString();
}

I am looking backwards again. This time it is the array of split texts. I am splitting the text using the split() method and provide a regular expression statement [\s*]. The StringBuffer is used instead of String because it is less costly to append strings using the append() method. The method reverseWords() returns "sky blue clear very" if the given string is "very clear blue sky".

Deduplication

Here is a Java static method that removes recurring characters in a string. Given an input string "[Nicholas N I cho L[A]s!]", this method returns a string that reads "[Nicholas ILA]!"

public static String removeDuplicates(String text){
  StringBuffer uniq = new StringBuffer(); 
  int len = text.length();
  for (int i=0; i<len; i++) {  
    if (uniq.indexOf(Character.toString(text.charAt(i))) < 0) {
      uniq.append(text.charAt(i));
    }
  }  
  return uniq.toString();
}

Initially I thought of using a set to compile a group of unique characters but that would be adding extra code executions. I figured that I can solve this rather easily by going back to the basics. You may see that as I am constructing a new string "uniq", I am using the indexOf() method to look up for a particular character in that string. A value less than 0 means that the character that we are looking for does not exist at that moment. So we are appending it to "uniq". Another problem solved :)
Update: The code is also available in Python in this entry

Palindrome

A palindrome is a word or phrase that reads the same forward as it does backward. Some of the simple examples are "kayak", "Hannah" and "refer" if we would like to know how do palindromic words look like. There are also palindrome-like phrases such as "Dennis and Edna sinned" and "Draw pupil's lip upward".

It would not be too difficult to determine algorithmically if a word or sentence is a palindrome. There are many ways to solve it but we also need to consider if our solution is not computationally expensive.

I have thought of a simple and yet an efficient solution to our discussion. This is a static method that strips off the punctuations and also white character spacings. The method returns a boolean value true if the input string is a palindrome otherwise it returns false.

public static boolean isPalindrome(String text){
  //Sets an index at the far left of the word or phrase
  int leftIndex = 0;

  //Converts input text into lower case and remove
  //any single non-alphanumeric and underscore
  text = text.toLowerCase().replaceAll("[\\W\\_*]", "");

  //Sets an index at the far right of the word or phrase
  int rightIndex = text.length()-1;
  while (leftIndex < rightIndex) {
    if (!(text.charAt(leftIndex) == text.charAt(rightIndex))) {
      //returns a false and get out from the while loop
      return false;
    }

    //gets the indexes from both sides closer
    leftIndex++;
    rightIndex--; 
  }
  //returns a true if all the characters mirrors to each other
  return true;
}

Truncating a sentence

Here is something that we often ask ourselves how do we truncate a sentence and then append it with a trailing "...". We see this in articles, newspapers, texts in television advertisements. I am suggesting a method that might be useful for front-end developers to truncate the sentences pulled out from the database.

public static String truncate(String text, int length) {
  return (text.length() <= length) ? text : text.substring(0, length) + " ...";
}

Simple isn't it? The use of this static method allows you to set a maximum length of the sentence to be truncated and then append it with the trailing "...".
Update: The code is also available in Python in this entry

The hopping grasshopper

I came across this quiz from the Internet (credits go to whoever prepared this question) and thought of giving it a try. The question is as follow:

A grasshopper is hopping forth and back in the field. Each time it hops, the distance is equal to the number of the hop. So for the first hop the distance is one unit, the second hop the distance is two units etc. However, the grasshopper would not hop back if it will otherwise land beyond the origin where it has started.

Your task is to write a program to determine whether the grasshopper can be N units from where it begins if it makes N hops, and the number of hopping patterns.

The following diagram shows that for 4 hops, there is only one possible hopping pattern.

Input: An integer not more than 25.
Output: The number of hopping patterns or zero if no such hop pattern is possible for the given input number.

Sample Input: 4
Sample Output: 1
Here's my solution to the trivia. It may be perfect, it may be not. Please feel free to drop a comment if you feel there is a simpler way to solve this.

public static int hop(int numberOfHops){  
  int hopCount = 1;
  int unitCount = 0;
  int pattern = 0;
  int currentIndex = 0; 

  if (numberOfHops < 1 || numberOfHops > 25) {
    //returns a 0 if the supplied input is more than 25 
    //or less than 1
    return 0;
  }

  while (hopCount <= numberOfHops) {   
    unitCount = unitCount + 1;
    currentIndex = currentIndex + unitCount;
    if (currentIndex > numberOfHops) {
      //bounces back the grasshopper if it is about to
      //hop out of bound from the current spot
      currentIndex = currentIndex - (unitCount*2);
    }
    if (hopCount == numberOfHops) {
      if (currentIndex == numberOfHops) {
        pattern++;
      }
    }   
    hopCount++;
  }
  return pattern;
} 

The Whitespace Stripper

This is yet another method written in Java that deals with string manipulations. I have written a method that returns the same result of the regular expression [\s*]. The regular expression "[\s*]" translated into plain English is "Match 0 or more of the preceeding whitespace character (spaces, tabs, line breaks) in the set".

Below is the suggested solution in Java to strip off whitespace characters without using regular expressions. The code itself is quite straight forward. "NicholasKey" will be returned as the result of this method with the given input "Nicholas Key".

public static String stripWhiteSpace(String text){
  StringBuffer cleanText = new StringBuffer();
  int len = text.length();
  for (int i=0; i<len; i++) {
    if (text.charAt(i) != ' ') {
      cleanText.append(text.charAt(i));
    }
  } 
  return cleanText.toString();
}

Update: The code is also available in Python in this entry