A collection of programming problems

[NoCforMe]

OK, I read the post where David Maynard threw down his gauntlet (made quite a bang) and explained the bit-vector thing. Which is dead simple: 1 million bits, each representing an integer depending on its position. Even I can understand that.

So what a guy would need in order to access the i^th bit in this "vector" are two things: a pointer to a byte and a bit mask to isolate the bit. Here's my take on how to do that:

Code Select Expand


MOV EAX, i
MOV ECX, EAX ;Save original i
SHR EAX, 3 ;Divide by 8
MOV EDX, EAX ;Pointer to the right byte
SHL EAX, 3 ;Back to original modulo 8
SUB ECX, EAX ;Get the "remainder"
MOV AL, 1 ;Set bit 0
SHL AL, CL ;Set bit [remainder]
MOV theMask, AL

; Now you can access the ith bit with:
MOV AL, [EDX + BitField]
TEST AL, theMask ;0 or 1?


Amiright? Totally untested.

BTW, his use of the term "vector" kind of made me chuckle. It's a $5 word that mathematicians use, where us ordinary folks would say "table" or "bitfield" or some other term. Vector? That's the kind of language one uses with one's nose in the air.

[jj2007]

Just in case you have nothing better to do

Example:

Given a list of one million random 7-digit phone numbers write a program that prints a sorted list of the phone numbers with duplicates removed, using less than 2MB of memory and that runs in linear time

Interesting challenge, but can you explain what "runs in linear time" means? That's a term I'm not familiar with.

It means that if sorting 1000 items takes 1 millisecond, sorting 10000 will take ten milliseconds. Many sorting algos behave differently: they would take 100 milliseconds then. Try a bubble sort, for example.

It's irrelevant for small item counts below a few thousand, but once you have a Million to sort, you wish for "linear time" behaviour