Question

When given an English dictionary consisting of some 10,00,000 words, what could be the useful and optimal data structure that could be used to store this...?

Answer 1

guys pls do me the answer for this :( :(

Answer 2

well i guess u would not be storing 10,00,000 words in memory so disk storage will be your option. so i guess u can use hashing to store the words as keys and then store explanations in other files.. if this is not what u need then pls explain ur requirement a bit..

Answer 3

a binary tree, search in it is O(logn) where n its the number of words

an hash table works faster its O(1) for searching and inserting

here u can find more info on the differences: http://www.informit.com/guides/content.aspx?g=java&seqNum=472

If u are using c++ u can us map wich its a binary tree i think, and a hash_map or unordered_map in c++ wich are a hashtable

in Java in the link i gave u they tell wich one are

Both are good, use the one that suits u.

Answer 4

I think a b-tree would be a better option. Also note that depending on the number of bits in the generated hash (2^n for n bits is the number of hash bins) there may be lots of collisions.

Answer 5

Also a tree structure will have better time complexity for searching by inequality.

Answer 6

if we could use the hash table, then what could be the hash function that could be used...?that could avoid many collisions...?? can anyone suggest specific to this example?

Answer 7

am not an expert google there is plenty of info about that. Search hash function strings somthing like that

Answer 8

@fedep3 will try dude.... thanks a lot :) :)

Answer 9

I would say a quicksort algorithm, but a binary tree may be faster?

Answer 10

We are talking about the correct data structure to use to store the data, not how to sort an unsorted set of data.

Answer 11

then the correct term is data storage device and not data structure!

Answer 12

no its data structure. a structure for storing data, a tree, a hash table, etc

Answer 13

http://en.wikipedia.org/wiki/Data_structure, no mention of a hard-drive etc.

Answer 14

*sigh* This is theoretical obviously.

Answer 15

No, this is fact!

Answer 16

From wikipeidia:
" a data structure is a particular way of storing and organizing data"

Answer 17

This is exactly what I said before.

You were confusing an algorithm and a data structure.

Answer 18

a particular way not device...

Answer 19

When did I mention a device anywhere here....

Answer 20

And you don't understand what theory means.

Answer 21

obviously I dont! lol

Answer 22

I recommend using a Trie. http://en.wikipedia.org/wiki/Trie