Tag Archive for 'java'

Java: Fix Unchecked Warnings In Java Collections

Published on May 4, 2012 in Tech. 0 Comments

If you use Collections.EMPTY_LIST, eclipse shows up an unchecked conversion warning. This can be easily avoided by using Collections.<FooBar> emptyList() instead.

Popularity: 1% [?]

Knuth-Morris-Pratt String Search Algorithm

Published on April 14, 2012 in Academic. 0 Comments

The KMP algorithm searches for the occurrence of a word W in a sentence S while employing the observation that when a mismatch occurs W contains sufficient information to determine the start position of the next search in S.

Say W = abcd and S = abcbabcd. Now we compare W[0] with S[0], W[1] with S[1], W[2] with S[2] and they all match. But W[3] does not match S[3]. The brute force algorithm would have started the next search by comparing W[0] with S[1]. But a simple observation tells us that it would be fruitless as there is no W[0] till S[3]. We would have done better by starting the next search from S[4]. And this is exactly what the KMP tries to achieve.

KMP requires a pre-processing of the word W. We create a Partial Match Table by iterating over all the letters of W in such a way that in case of a mismatch we can quickly figure out the next start position by looking at the table. The wiki article on KMP describes with an example how to create the table:

KMP – Partial Match Table

The partial match table can be created in O(n) time using O(n) space, where n is the length of the word W. Once we have the table we can iterate over each element of S consulting the table every time a mismatch occurs. You may want to read up the algorithm with examples from

KMP – Algorithm With Examples – Wikipedia

The search happens in O(k) where k is the length of the sentence S. Thus the algorithm runs in O(n + k).

Below is my java implementation of the same:

/**
 * Perform the Knuth-Morris-Pratt string search. The algorithm first pre-processes the word to create a Partial Match
 * Table. The table is creatd in O(n) where n is the length of the word. After the pre-processing, the actual search can
 * be performed in O(k) where k is the size of the sentence.
 */
public class KMPStringSearch {
	/**
	 * Searches for all occurances of the word in the sentence. Runs in O(n+k) where n is the word length and k is the
	 * sentence length.
	 * 
	 * @param word The word that is being searched
	 * @param sentence The collections of word over which the search happens.
	 * @return The list of starting indices of the matched word in the sentence. Empty list in case of no match.
	 */
	public List<Integer> searchString(final String word, final String sentence) {
		final List<Integer> matchedIndices = new ArrayList<>();

		final int sentenceLength = sentence.length();
		final int wordLength = word.length();
		int beginMatch = 0; // the starting position in sentence from which the match started
		int idxWord = 0; // the index of the character of the word that is being compared to a character in string
		final List<Integer> partialTable = createPartialMatchTable(word);
		while (beginMatch + idxWord < sentenceLength)
			if (word.charAt(idxWord) == sentence.charAt(beginMatch + idxWord)) {
				// the characters have matched
				if (idxWord == wordLength - 1) {
					// the word is complete. we have a match.
					matchedIndices.add(beginMatch);
					// restart the search
					beginMatch = beginMatch + idxWord - partialTable.get(idxWord);
					if (partialTable.get(idxWord) > -1) idxWord = partialTable.get(idxWord);
					else idxWord = 0;
				} else idxWord++;
			} else {
				// mismatch. restart the search.
				beginMatch = beginMatch + idxWord - partialTable.get(idxWord);
				if (partialTable.get(idxWord) > -1) idxWord = partialTable.get(idxWord);
				else idxWord = 0;
			}

		return Collections.unmodifiableList(matchedIndices);
	}

	/**
	 * Creates the Partial Match Table for the word. Runs in O(n) where n is the length of the word.
	 * 
	 * @param word The word whose Partial Match Table is required.
	 * @return The table as a list of integers.
	 */
	public List<Integer> createPartialMatchTable(final String word) {
		if (StringUtils.isBlank(word)) return Collections.EMPTY_LIST;

		final int length = word.length();
		final List<Integer> partialTable = new ArrayList<>(length + 1);
		partialTable.add(-1);
		partialTable.add(0);

		final char firstChar = word.charAt(0);
		for (int idx = 1; idx < word.length(); idx++) {
			final int prevVal = partialTable.get(idx);
			if (prevVal == 0) {
				if (word.charAt(idx) == firstChar) partialTable.add(1);
				else partialTable.add(0);
			} else if (word.charAt(idx) == word.charAt(prevVal)) partialTable.add(prevVal + 1);
			else partialTable.add(0);
		}

		return Collections.unmodifiableList(partialTable);
	}
}

view raw KMPStringSearch.java This Gist brought to you by GitHub.

Popularity: 3% [?]

Your ClassNotFound Error Is Probably Not Telling You Everything

Published on April 4, 2012 in Coding. 0 Comments

Quicktip
If a class fails to load due to an exception during class initialization, the actual problem is only logged the first time you attempt to load the class.  After the first time, the classloader recognizes that it’s already tried to load the class and just throws a ClassNotFoundException or NoClassDefFoundError.

Symptom
You will see logs for the ClassNotFoundException or NoClassDefFoundError (usually many such logs), but you see that the class is in the classpath.  You won’t see any root cause on any stack trace but the first (and that one is typically not a CNFE or NCDFE).

Finding the root cause
If you get a CNFE or NCDFE and you see the class in the classpath, search back your logs for ${missing classname}.<clinit> in a stack trace to figure out what prevented the class from being loaded.  Remember that the log may have rolled off.

Possible root causes for CNFE/NCDFE

  • Desired class is not in classpath (this is the boring case)
  • Initialization of desired class throws a RuntimeException or an Error
    • Static variable is initialized via a function which threw an uncaught Throwable
      • E.g. public static final String SOME_CONST = SomeClass.getString(“SOME_KEY”); where SomeClass.getString(String key) can throw an Exception.
    • Static block (loose code in {} in the class definition) threw an uncaught Throwable
      • E.g. public class Foo { { doSomeStaticInitialization(); } …
    • variable or method signature includes type which could not be initialized (see this same list of root causes)
      • E.g. public class Foo { SomeClassWithErrorInInitializer attr1; …

From The SDE Tip – Amazon

Popularity: 1% [?]

WTF Code: Hardcode URL When Cleaning

Published on March 4, 2012 in Coding. 0 Comments

At Amazon it’s a Service Oriented Architecture that everyone follows. We use the PAAPI (Product Advertising API) to create links to products in various marketplaces. Both PAAPI and us use the tag parameter to identify user who sent the request. So we always clean the urls returned by PAAPI to strip off tag. 

I looked around the code and found that we have a method which takes in a list of parameters to be removed and cleanses the url. Good. I had to integrate www.javari.jp into our widget server. When testing I found that all the urls were defaulting to www.amazon.co.jp instead of javari! Now this was baffling because clearly the url cleaner did not such thing as change the domain. I went deeper into the code and what I found surprised me!

For some reason, unknown to anyone in the team, someone had decided to comment out the piece of code calling that url cleaner method and instead chose to write his own cleaner. This is what he did:

As I understand from the above code, all that he wanted to do was strip out the get parameters. But that can very easily be done by using the URL class of java. Given a valid url, URL has all the logic to parse it and spit out various segments. My modified code was:

Simple and easy as it can get!

Popularity: 1% [?]

JVM : Out Of Memory PermGen

Published on January 24, 2012 in Tech. 0 Comments

Interesting thing I did not know about Java – PermGen. Apparently other than just the stack (local variables and methods) and the heap (everything else), java uses this extra storage which can also cause OOMs.

PermGen is where a few very long-lived types of objects are persisted in Java, such as class definitions and ‘intern’ed Strings.  It uses separate storage from the heap and the stack.  If you run out of PermGen you will get out of memory errors.  If you run very low you will get a JVM that spends all its time garbage collecting.

Few things I came about when I googled around:

Luckily I’ve never had to deal with PermGen OOM before. Apparently it’s hell-of-a-job debugging this issue.

From The SDE Tip – Amazon

Popularity: 1% [?]

Impossible Null Pointer Exceptions

Published on December 12, 2011 in Tech. 0 Comments

I must admit this had never occurred to me before but after reading, the explanation seems so obvious!

You can get NullPointerException from lines in Java which appear to have no possibility of throwing them, such as;

this.setCount(num)

The null pointer exception can come about when num is of type Integer and setCount takes an int parameter. Java’s auto-boxing will automatically call num.intValue(), and if num is null you get an exception.

Of course, the fix is to check for null-ness and treat it however the semantics of your operation requires.

From the SDE Tip – Amazon

Popularity: 1% [?]

Project Euler : Frequency Analysis For Message Decryption

Published on October 22, 2011 in Problems. 0 Comments

Problem 59 of Project Euler brought back memories of Sherlock Holme’s Dancing Men. Holmes had to decrypt a series of messages – the characters of which were stick men figures in varying dancing positions. He computed the frequencies of each dancing figure. Then since ‘e’ is the most used letter in English, he replaced the most frequent dancing figure with ‘e’.

I did the same thing with a difference. The given text in the problem did not have any spaces. This meant that even the spaces had been encrypted. And the most frequent number occurred almost twice as much as the next one. So I replaced that with space. That’s it. The problem was solved.

The password used to encrypt the text is – ‘god’ and the following code decrypts the text and finds the answer in the count variable.


    private List<Distribution<Integer>> parseInputFile(String fileName) throws FileNotFoundException {
        List<Distribution<Integer>> frequencies = Lists.newArrayList(new Distribution<Integer>(), new Distribution<Integer>(), new Distribution<Integer>());

        Scanner scanner = new Scanner(new File(fileName)).useDelimiter(",");
        int count = 0;
        for(int i = 0;  scanner.hasNext(); i++) {
            int num = scanner.nextInt();
            frequencies.get(i % 3).add(num);

            if(i % 3 ==0) num ^= 103;
            else if(i%3 == 1) num ^= 111;
            else if(i%3 == 2) num ^= 100;
            count += num;
            System.out.printf("%c", num);
        }

        System.out.println("Sum = " + count);

        return frequencies;
    }

Popularity: 5% [?]

Project Euler : Expansion Of Continued Fraction For Square Root Of Two

Published on October 4, 2011 in Problems. 0 Comments

Problem 57 of Project Euler is pretty simple forward. It is very easy to see the following relation:

Numerator = Numerator + 2 * Denominator

Denominator = Numerator + Denominator

Simple code and was done. Here’s that:

    public int getCount(int numberOfExpansions) {
        int count = 0;

        BigInteger numerator = BigInteger.valueOf(3);
        BigInteger denominator = BigInteger.valueOf(2);
        while(--numberOfExpansions > 0) {
            BigInteger a = denominator.multiply(NumberUtil.BIG_TWO).add(numerator);
            BigInteger b = numerator.add(denominator);
            numerator = a;
            denominator = b;
            if(NumberUtil.numberOfDigits(numerator) > NumberUtil.numberOfDigits(denominator)) count++;
        }

        return count;
    }

Popularity: 4% [?]

Project Euler : n Digit Integers That Are Also nth Power

Published on October 3, 2011 in Problems. 0 Comments

Problem number 63 of Project Euler gives the expression a = b^c and imposes the condition that the number of digits in a is equal to c. An example would be 16807 = 7^5. a, b and c are all positive integers. The problem asks one to find the number of such possibilities.

Solving this problem made me happy. So, I’ll go into the details.

Given the problem, the first thing that comes to mind is the special relationship between the log of a number and the number of digits. The hint is to use logarithms to simplify the problem.

a = b^c

\Rightarrow \log(a) = c \log(b)

But \log(a) = c - f, where f \in (0, 1]

\Rightarrow c - f = c \log(b)

\Rightarrow c \log(\frac{10}{b}) = f

\Rightarrow 0 < \log(\frac{10}{b}) \leq \frac{1}{c}, dividing by c \in Z^+

That’s it! Our problem has been solved. I hope you have already noted that b \in [1, 9]. This means that we can precompute the values of \log(\frac{10}{b}) and store the results in an array. Then for all c \geq 1, just count how many of the precomputed values are smaller than or equal to \frac{1}{c}. The iteration completes when the smallest precomputed value is greater than \frac{1}{c}.

Below is the piece of code I wrote in Java to solve the task.

    public int getCount() {
        m_precomputedValues = new double[9];
        for(int i = 1; i < 10; i++) {
            m_precomputedValues[i-1] = Math.log10(10.0 / i);
        }

        int count = 0;

        int numberOfDigits = 1;
        double val = 1.0 / numberOfDigits;
        while (val > m_precomputedValues[8]) {
            for(int idx = 8; idx >= 0 &amp;amp;&amp;amp; m_precomputedValues[idx] <= val; idx--) count++;
            val = 1.0 / ++numberOfDigits;
        }

        return count;
    }

Popularity: 4% [?]

Java ArrayList Is Actually Just An Array !

Published on August 27, 2011 in Coding. 0 Comments

I was reading The Art of Computer Programming Vol 1, the chapter about arrays and list. Knuth describes the differences and mentions how it’s very easy to add a new element to a list in a constant time if we have the node where the insertion needs to happen. Same for deletion. That is when I realized I did not know how the ArrayList implementation handles it. I did a code walk through of that class – something Prasun had advised me long ago but I always ignored.

I always knew that ArrayList used array for implementation, which is how it can guarantee the O(1) element access time. But I did not know how the other methods worked. For instance, one need not provide any initial size of the ArrayList. How does Java handle it? I remember Prasun telling me that the initial size in such cases is 10. But then what happens in the case of an overflow? What is the new space that gets assigned to the list?

But I was more interested in the add(index, element) and the remove(index) methods. And they are not constant time! They are O(n) operations. Say we want to remove(6). Java actually copies over all the elements from 7..n to indexes 6..n-1 and then sets the nth element as null. This is so not what we learn as deletion in list where it was just a matter of changing a couple of pointers (the next and prev ones).

Popularity: 2% [?]