* Nobody:
[snip]
Yeah, post in [comp.programming], it's off-topic in clc++, and don't
post questions that have better than 50% chance of being HOMEWORK.

Hints: (1) you can't do it in less than linear time, (2) it's trivial to
do it in linear time with linear memory consumption, (3) with more
stringent conditions it becomes a challenge just to find out whether
it's doable.



Follow-ups to [comp.programming].

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

"Alf P. Steinbach" <alfps@start.no> wrote in message
news:4s9b9oFujthvU1@mid.individual.net...
Actually, I've been out of school for 12 years now. I got this question at
two recent job interviews. I mostly worked in the Windows GUI (MFC) area for
those 12 years which was not very heavy on algorithms.. this is a sort of
new career direction for me.

Anyways...

So you are saying its possible to do this in O(n)??? with one single pass?
WTH... I've been thinking about this for a week since the 2nd interview...
my AVL idea is still O(n + n log n) = O (n log n).

I'm assuming by hint 2, that you meant that if I had n numbers, it would
take 1 pass and 1 buffer of n size?

Any further hints on beating n log n?

Nobody wrote:
Like he says, it can be done in linear time with sufficient memory. A
hashtable is one approach. I don't think a single pass is sufficient
though.

Nobody wrote:
You can always find the maximum value in the list with a single
O(n) pass. Then you can create a bitarray covering the value
range, and do a second scan setting 'present' bits. The result is
still O(n), with auxiliary storage of MAXVALUE bits. This finds
ALL unique entries, but not necessarily the first.

You could alter the 'present' bit array to be an array of indices
into the original list, with an auxiliary value for 'multiple'.
Then the hunt for the first is a sort on that list.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

Mark P <usenet@fall2005REMOVE.fastmailCAPS.fm> writes:
O(n) doesn't mean a single pass. It means a finite number of pass.

O(10^1000000000000*n)=O(n)

--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.

"Mark P" <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote in message
news:wAL7h.4861$yE6.2631@newssvr14.news.prodigy.co m...
Hmmm... apperently I had a HUGE misunderstanding of big-O notation...
ARGH...

so you would consider this approach linear?

for (0..n)
{
if (hash.Find(element[n]) is NOT found)
hash[element[n]] = 1;
else
hash[element[n]] = hash[element[n]] + 1;
}

for (0..n)
{
if (hash.Find(element[n]) == 1)
FOUND IT
}

So this is a "trivial" solution to the problem and a lot easier then the AVL
thing to implement.

So with this hash table approach... I'm going through the worst case O(2n) =
O(n) for the two loops = linear algorithm.

But, it seems kind of iffy to call hash table insertions and lookups O(1)
though... thats kind of assuming you'll NEVER have a collision.

Looking through Microsoft's MFC hash tables, they use "key >> 4" as the hash
for a lot of the classes. Not saying thats optimal of course.

Jeez... now that I've cleared up that big O misconception, I probably could
have gotten that job... ARGH again...

CBFalconer wrote:

And thus, this approach has possibly much more than linear memory
consumption. It does not fit Alf's description.

[snip]


Best

Kai-Uwe Bux

"Kai-Uwe Bux" <jkherciueh@gmx.net> wrote in message
news:ejo578$d6d$1@murdoch.acc.Virginia.EDU...
The hash table solution that I posted ends up being O(n) in two passes of
the array. Much cleaner then both this and my AVL solution.

And the hash table solution actually also applied to a lot of the other
problems I got asked at this recent interview.

Thanks for the tips guys!

Pascal Bourguignon wrote:
I don't think I ever said O(n) means a single pass. If you'll read the
context that you clipped from my reply, you'll see that I was responding
to one of the OP's questions.

"Nobody" <nobody@cox.net> writes:
What were you doing and thinking twelve years ago? I bet you skipped
the lecture about algorithm complexity and went out drinking beer or
tickling girls. Well, you can see the result, one job missed! :-)


--
__Pascal Bourguignon__ http://www.informatimago.com/

HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.

CBFalconer <cbfalconer@yahoo.com> writes:
You need 1.5 bits per number: absent, present-once, present-more-than-once.

--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962O20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/

Pascal Bourguignon wrote:

Ah, but you don't know how many jobs he has landed /because/ of
improved beer-drinking and/or girl-tickling skills.

-- chris

Pascal Bourguignon wrote:

No need. Just scan the original list backwards, keeping track of the
last seen duplicate.

If you use a hash-based Set implementation using a pre-allocated table
with <some constant> * the size of the input list, then the problem can
be solved in a single pass in "morally" O(n) time.

-- chris