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.

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

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.

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 .