# 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 = “markojerkic.com” 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 .

We generally avoid solutions with time complexities .

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

https://gist.github.com/markojerkic/0485069c1ca84aa27e2ce580b8ff2ae2

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.

https://gist.github.com/markojerkic/59139763997cd3ff8a3dc90b3bd533ae

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

## Help!

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.

https://gist.github.com/markojerkic/8cce7864eb8b8fa4eb65a7047480c761

And the test:

https://gist.github.com/markojerkic/706fb52ebf81f96b6afbf58d13b4a3e8

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