2

I found in the Big Board (Spring 2018) that some people only used 7.4 KB memory (as highlighted), while the dictionary contains 140k words. I don't understand how that's possible.

Improve this question
2
2

It depends on the metrics used, I think those are heap and stack memory. Global variables don't show up in those statistics. Now if you can estimate an upper limit for the size of the dictionary...

Improve this answer
0
2

You don't have to use the heap (dynamic allocation) nor the stack (local variables) to store the dictionary. You can declare a static data structure as global and house the dictionary in it. For example, if you were to use a trie, you can check (empirically) what's the maximum number of nodes you'll need, and initialize a global 2D array with that number of entries. (Trie can be implemented using a 2D array). Similarly with a hash table whose size and chain length you fix to a specific value in code.

Improve this answer
1
  • does that mean implementing a "bloom filter" in a bit array? if so, did you manage to exclude false positives? my bloom filter has got false positives all over the place, and I cant figure how such an implementation could have successfully checked the dictionary - pray do tell? – amle Sep 21 '18 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .