Pages in Java

Algorithm Question Substring Search KMP

Question LeetCode has this question Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Tags: Two Pointers, String. Let’s denote haystack length N, needle length M, character table size R (256 for extended ASCII). Java’s String class method indexOf() uses brute force algorithm O(MN). Examples: haystacsflksdjflkshhaystackneeneeneedle needle naslkfjskjlhhhh needle Method 1 2D DFA KMP Knuth Morris Pratt O(N) time complexity.

---

Sorting Algorithm Summary

The following table summarizes common characteristics of popular sorting algorithms, not including string sort algorithms (I may add those later here or write another separate post). algorithm In Place? Stable? parallel? worst average best remarks selection y n n N2/2 N2/2 N2/2 N exchanges insertion y y n N2/2 N2/4 N use for small N or partially ordered shell y n n ?

---

MongoDB Tutorial 5 - Aggregation Framework

The aggregation framework has its roots in SQL’s world of groupby clause. Introduction Example used: imagine a SQL table of products. name category manufacture price ipad tablet Apple 499 nexus s cellphone Samsung 350 To get number of products from each manufacture with SQL, select manufacture, count(*) from products group by manufacture; with mongodb, > use agg > db.

---

Using Java's Reflection for Testing

Writing Boilerplate Test Code is Boring Repeatedly writing boilerplate for loops for testing is not fun. We can use Java reflection API (java.lang.reflect package) to maximize code reuse and help testing. Frameworks like JUnit uses reflection for testing. I will introduce a single method today on how reflection can be used for testing. The code examples below are available at my github repository. Get an Instance of Class Being Tested First we will declare a message to print out if all tests passed.

---