4 ms·
You might get have done better if you remembered the criterion correctly. Almost every data type used in computing is represented by non-fixed-length strings ov
by tamana 10y ago
You might get have done better if you remembered the criterion correctly. Almost every data type used in computing is represented by non-fixed-length strings over a fixed alphabet (usually {0,1}).
Radix sort is O(n) in log(dictionary size) which is only a useful bound when the data set is larger than the dictionary (this is a severe but not fatal requirement. Some datasets have many duplicate values, and anyway in practice log(n) factors in real world systems are practically constant factors: an 1log(n) algorithm will be slower than a 100(1) algorithm.)
You can misstate a theorem, or forget the proof, OK, but doing both is poor form.
- bhntr3 10y agoYou're right. I misstated it here and was clearly lying when I said I understood it. Another good tip for interviewees: If you don't really understand something well enough to explain it, sometimes it's better not to bring it up than to introduce it and look silly. Sucks. But you're more likely to lose points than gain them for just kind of knowing something exists. Also applies to hacker news comments ;)