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