Admin/developer job

[Mel Wilson]

On 11-01-11 12:48 AM, ted leslie wrote:
> If you were on a tight memory system, wouldn't the O(logN) sort be best,
> but on assumed resources available the O(1) hash table is what they
> wanted in the answer?
> Of course a grossly small hash would end up doing mostly linear runs
> in the overflow buckets, making it worst then O(logN) sort.
> And if memory was really restricted, a exhaustive scan and mark would
> be the only way O(N^2) with only a bit needed for each (in additional
> storage).
> I am assuming the question had some "additional info" ?

I'm not so sure of this one myself.  Why is the array huge?

If it's a huge number of small elements then coercing each element to 
an integer and making a bit map of values present might work (a la 
Programming Pearls.)

If it's a small number of huge elements, then sorting a list of index 
values.

I'd like to work SHA-1 hashes into this, but I suspect that's how I 
blew this question myself a few years ago.

	Mel.
--
The Toronto Linux Users Group.      Meetings: http://gtalug.org/
TLUG requests: Linux topics, No HTML, wrap text below 80 columns
How to UNSUBSCRIBE: http://gtalug.org/wiki/Mailing_lists