[dclara]

Unfortunately, I cannot agree with you completely.

If there is no language constraint and the system resource constraint, to the problem we have understand so far, using Java will be the fastest and easiest way without hashmap.

Load the complete file as a string (depending on how the size of the data set, up to 2^31 - 1), then using string.indexOf() function will get the best result.

The underlying algorithm for indexOf() is implemented by JVM in C code which is must fast than any other implementation.

My gut told me that it's weird to use hashmap to do string lookup. Everybody knows hashmap is used to lookup key-value pairs. The real reason for not using hashmap here are:

1. hashmap's lookup Big O is O(n), but not the build cost. if the data set size is huge, it takes long time to build the hashmap since every new element exceeded the initialCapacity being added needs a rehash

2. the underlying implementation of indexOf() will use a sort of algorithm called "automata" or something else to do a fast search within a string.

So there are lots of alternative solutions. Don't always think there is only one. I'm not in this field, and I'm not interesting to get into to it too much. But I don't think the best answer is that tiny change.

This is why I suggested to consider if you are doing application level optimization or changing system level algorithm. Building software is a lot more than code manipulation. Understanding requirement is the first step in the SDLC (Software Development Life Cycle).

[grey-area]

Sure, you're welcome to do try it in another language, they almost encourage you to. No one said there's only one way, but for many simple problems a hash is a good solution.

The best answer is one that passes the test, and using ruby it is pretty easy to do so, but you could do it any way you like.

[dclara]

I'm not sure what you mean about "many simple problem". Is this one of the example for that? I'm trying to compare the two alternative solutions for this problem:

1) Hashmap 2) string index

which is better? I think about it what I'm going to do if I'm using it in my web application.

First the answer is still relying on the size of the data set. If the dictionary is huge, say up to 4G, I'd use string index vs hashmap, because the memory space is expensive. And how to break into mutiple sub strings is another performance tuning issue.

If the problem is simple enough with not too large data set, hash will be working.

When I mentioned "one way", I mean the "best way". So now you are talking about "The best answer is one that passes the test". So do you mean that all the answers which can pass the test are the best answers, or there is only one best answer which can pass the test? I don't put my personal preference on the problem solving. I'm always looking for the best solution for a particular problem under certain condition and constraints. Once we figure out the answer, coding implementation using which language does not matter that much, unless Ruby does not support the same algorithm of string.indexOf() as Java does.

Hope this discussion helps.

[grey-area]

So do you mean that all the answers which can pass the test are the best answers

Yes, what I was trying to say was that the performance required is just that to pass the test, not more, and the dataset is a few MB here, not 4GB. This is actually really similar to a lot of problems in real life; you can spend ages trying to find a platonic solution when a simple solution works fine given the dataset and requirements (return an answer within 200ms for example). Sometimes simpler is better, and even if you can improve the solution, it won't really matter to whoever pays the bills.

There are lots of solutions though, I tried a few just out of curiosity and you can of course improve on a hashmap - the possible solutions to a problem this small are pretty similar whatever language you choose, and sometimes when a dataset is this small other more complex solutions are slower (unless you preindex).

[dclara]

I have no intent to choose complicated solutions over a simple issue. First, I'm always concerned about the size of the data set. The first sentence I said, if the data set is not big enough, you cannot tell too much difference. Second, I didn't insist on any solutions, so far, I proposed three of them and would like to discuss with you guys on the pros and cons under different conditions. Some people in other posts told me that the first solution using sorting + binary search actually is way faster than hashmap, which deserves more than 2000 points. I tried to verify whether it's true, but nobody answered. Some people helped to provide the Big O comparison on the hash lookup algorithm and linklist, which is also constructive. But did you learn from it that building hashmap cost more than O(1)? Lastly, I proposed the Java solution with string index, did you ever hear about that?

I don't need to spend too much time on finding the solutions, they are on top of my head. Depending on different conditions I'll use different solutions. 4GB is the upper bound of string indexing, if it's being used for web indexing, it's still not enough. If in this case it is used in document indexing for enterprise level with a few MG, it's fine for using any of them. But the difference is the score you get.

I guess eventually you will pick hashmap solution because you have the indexes built in the lookup, which makes more sense over other solutions, but you (or they) don't give the condition out in the first place. How can we discuss based on that? Looks like I pretty much wasted my time on this issue and was taught to learn that making things simple is better. Thank you.