Marko Jerkić

Learner's Deep Learning Blog

Java Algorithm Problem

I recently bought a book called Elements of programming interviews in Java.

At first, I couldn’t solve evan the simplest problems in the book. I got stuck on really easy, trivial stuff, but through practice, I got pretty good at solving them.

This is a problems involving Strings. It is the final problems in the chapter about String related problems and it offers a strange solution. I think it is a bit too much and the solution shouldn’t be so complicated.

Don’t get me wrong. I do not think that the solution is that complicated. I just think that it could be solved a bit simpler.

The problem

The idea of the problem is really simple.

Given two strings, s (the text string) and t (the search term), find the first occurrence of t in s.

For example, if s = “” and t = “com“, the method should return 11, as 11 is the index of the letter c if the sequence com in the string s.

A brute force solution would involve use of two nested loops, the first iterating through s and the second tests if t occurs starting at the current index in s. That solution’s time complexity would be O(n^2).

We generally avoid solutions with time complexities O(n^2).

The books goes over the Rabin-Karp algorithm.

This algorithm uses the concept of a fingerprint. It computes the hash codes for each substring of length m (the length of the t string).

This algorithm results in a time complexity of O(n + m), where n is the length of  s and m is the length of t.

My solution

I think that computing the hash codes for each substring of length m  is redundant.

My solution is to go over string s only once. We create a lookup index for string t (tIndex), where tIndex is the index of the character in string t which should equal the character of string s at index i.

The time complexity of my algorithm is O(n), and space O(1).


I do not see why we should use the Rabin-Karp algorithm instead of something like my algorithm. I tested these two approaches, although I could’ve spent a little bit more time figuring out a better and more difficult test, I found that both approaches yield the same results.

And the test:

If you’ve got any feedback, please let me know in the comments. Any help is greatly appreciated.

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top