A collection of programming problems

[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

[zedd151]

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

Okay, that's easy. 

, using less than 2MB of memory

Still easy... 

and that runs in linear time

Does that mean no loops, jumps or calls? Not so easy. 


I tried to visit that site (quora) but can not do that on my computer due to Opera certificate issues. Even my dated iPad won't go there. I'll look at that link later today. I need a break from another project that I'm working on. 


By 'printing' does that mean physical printing to sheets of paper, or to console window?   

[jj2007]

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

Okay, that's easy. 

Good to see that you find it easy - my solution is attached

The algo is almost 3 times as fast as QuickSort (but you can't keep the duplicates):

Code: [Select]

5465 µs for  creating an array of random phone numbers
4317 µs for  setting the bits
37 ms  for  sorting & storing 735828 phone numbers
1000024
1000030
1000038
1000045
1000048
1000081
1000093
1000094
1000099
1000105
96 ms for nrQsortA (there are duplicates)
1000024
1000030
1000030
1000038
1000045
1000048
1000081
1000093
1000094
1000099

[zedd151]

Okay, you win. 
I don't think I will try working with bits. But also ...

735828 phone numbers

a little short from one million.     You cheated. 
My code would be more usual stuff. I'll post it later.   

... maybe

[jj2007]

You cheated

Not really. When you create one Million random 7-digit phone numbers, there are lots of duplicates.

[FORTRANS]

Hi Jochen,

   Thanks for pointing that problem out.  I liked the solution,
but I would (probably) have never figured it out on my own.
Now one should find an actual application for it.

Cheers,

Steve

[zedd151]

Not really. When you create one Million random 7-digit phone numbers, there are lots of duplicates.

Okay, I'll buy that.    But wheres the source code? 
Also, are they valid phone numbers? The article didn't give enough data, also didn't mentioned if the phone numbers need to be formatted in any particular manner. Are invalid phone numbers acceptable? And just a dead listing of the numbers opposed to formatted phone numbers (i.e., in U.S. = "267-4950" vs. '2674950')? So many unanswered questions.    I gotta go to take the dogs for a walk...

Depending upon the answers to my query, it could just be one million decimal numbers as opposed to phone numbers per se.

[jj2007]

Hi Steve,

Now one should find an actual application for it.

The application is an extra fast integer sort: it beats QuickSort by a factor three for the 7-digit range, in spite of bts being a rather slow instruction.

@Z: There is something odd with the number of elements. Too many duplicates for my taste, but I can't see the error in my logic. Source attached, maybe your eyes are better ;-)

[zedd151]

Too many duplicates for my taste, but I can't see the bug. Source attached, maybe your eyes are better ;-)

You're a funny guy.    Of course it's coded in MB.
But I agree, ~26% duplicates indicates that the random generator used might not be very random. I would expect some duplicates, but not so many. Seems a very high number of duplicates. Some tests with different random generator algorithms may be in order to test how other PRNG's do. (But of course I'm busy at the moment )

[jj2007]

The random generator is excellent. It's something else

[zedd151]

Also, I noticed that your solution always has 735828 phone numbers generated (after dup removal) no matter how many times run. Obviously a pattern there, indicating issues with randomness? Your program does not print the list of numbers to see if definitely patterns are there. (i.e., same list of numbers generated)
If I had to guess, possibly the same initial seed used?

[zedd151]

Now one should find an actual application for it.

A call center that generates spam robocalls.    Of course the phone numbers would have to be valid.

Hi Steve!

[jj2007]

same initial seed used?

Yes indeed, makes spotting bugs easier.

[zedd151]

Yes indeed, makes spotting bugs easier.

Did you write a list to file and compare to the list from another run?  I will bet that the results are identical. If it is, then the results are predictable and thus non-random. I had similar issues in writing my sudoku game in generating random game boards. While your algo may be fine for some uses, there are likely instances where it is not. Just my two cents.
In fact some programs actually depend on this anomaly; i.e., the freecell game from windows xp. A user can select a numbered game to run (1-1000000). Guess what? The number the user enters is the seed for the PRNG in that program in that case (user selected game #). That is how that program numbers its games, by using a seed in the 1-1000000 range with predictable results.

[Vortex]

Powershell script to create the list of random numbers. No duplicate removal :

Code: [Select]

for ($num = 1 ; $num -le 1000000 ; $num++)
 { Get-Random -Minimum 1000000 -Maximum 9999999 }