4 ms·

This solution won't give the correct results because when you sort and count duplicates, the text you output could be in a different order. Edit: And to be cle

This solution won't give the correct results because when you sort and count duplicates, the text you output could be in a different order. Edit: And to be clear, you should use the hash solution anyway since it is O(n+m).

dclara 13y ago
Nice catch. I should eliminate the sorting on the input words anyways, but save the duplicates in the neighbors, i.e. cache the previous ones. It does not affect the Big O level I mentioned in sorting of the word list loaded from the file. Looks like it's the necessary step.
dclara 13y ago
Thank you for giving out the Big O. Now I did the search and found that hash map is O(n) or O(1) here: http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1 http://stackoverflow.com/questions/1055243/is-a-java-hashmap... But I couldn't agree with you about O(n+m) because we cannot hash on the input set as well since that way we will lost the sequence order. Then the caching may help or use LinkedHashmap.
- jaredsohn 13y ago
  The hash _solution_ is O(n + m) in that it requires iterating through the words read from the dictionary file (O(m)) to fill the hash and then iterating through the inputs (O(n)), each time doing an O(1) hash lookup. You can think of it as: you need to read each word from the dictionary file once and you need to check each input word once; kind of hard to go faster than that.
  - dclara 13y ago
    Yes, I thought about exactly the same way you explained. But my point is trying to save more time, which may or may not be necessary depending on the size of the input data set. If we use caching, we can save the trip to look up the hashmap for each duplicated word of the input. However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.
    - jaredsohn 13y ago
      >save the trip to look up the hashmap for each duplicated word of the input. The time required to do a hashmap lookup should be small and of constant time. If you did cache it somehow, you would need a way to do lookups of what was cached (which might require another hashmap lookup.) Edit: I'm saying that trying to cache hashmap lookups might not save you any time and is probably not worth thinking about. Another poster has indicated that the solution described above (without trying to do some kind of caching of duplicates) should be sufficient to pass the Stripe CTF stage, so I would recommend just implementing that.
      - dclara 13y ago
        Good point. It really depends on the size of the data set. If the size of the input data set m << dictionary data size n, it's a worth trying for caching. Otherwise, the input word list should be loaded into LinkedList instead of ArrayList which is the most expensive list to be used when we need to access by its index number. Using Set will lose its order. (I'm just brainstorming the steps for discussion instead of writing code. I'd like to know the best solution and steps to improve it from you guys.)

dclara 13y ago

Nice catch. I should eliminate the sorting on the input words anyways, but save the duplicates in the neighbors, i.e. cache the previous ones. It does not affect the Big O level I mentioned in sorting of the word list loaded from the file. Looks like it's the necessary step.

dclara 13y ago

Thank you for giving out the Big O. Now I did the search and found that hash map is O(n) or O(1) here: http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1 http://stackoverflow.com/questions/1055243/is-a-java-hashmap... But I couldn't agree with you about O(n+m) because we cannot hash on the input set as well since that way we will lost the sequence order. Then the caching may help or use LinkedHashmap.

jaredsohn 13y ago
The hash _solution_ is O(n + m) in that it requires iterating through the words read from the dictionary file (O(m)) to fill the hash and then iterating through the inputs (O(n)), each time doing an O(1) hash lookup. You can think of it as: you need to read each word from the dictionary file once and you need to check each input word once; kind of hard to go faster than that.
- dclara 13y ago
  Yes, I thought about exactly the same way you explained. But my point is trying to save more time, which may or may not be necessary depending on the size of the input data set. If we use caching, we can save the trip to look up the hashmap for each duplicated word of the input. However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.
  - jaredsohn 13y ago
    >save the trip to look up the hashmap for each duplicated word of the input. The time required to do a hashmap lookup should be small and of constant time. If you did cache it somehow, you would need a way to do lookups of what was cached (which might require another hashmap lookup.) Edit: I'm saying that trying to cache hashmap lookups might not save you any time and is probably not worth thinking about. Another poster has indicated that the solution described above (without trying to do some kind of caching of duplicates) should be sufficient to pass the Stripe CTF stage, so I would recommend just implementing that.
    - dclara 13y ago
      Good point. It really depends on the size of the data set. If the size of the input data set m << dictionary data size n, it's a worth trying for caching. Otherwise, the input word list should be loaded into LinkedList instead of ArrayList which is the most expensive list to be used when we need to access by its index number. Using Set will lose its order. (I'm just brainstorming the steps for discussion instead of writing code. I'd like to know the best solution and steps to improve it from you guys.)