News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests

Main Menu

A collection of programming problems

Started by jj2007, December 23, 2022, 12:55:38 AM

Previous topic - Next topic

jj2007

Just in case you have nothing better to do :cool:

Example:
QuoteGiven 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

Quote from: jj2007 on December 23, 2022, 12:55:38 AM
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.  :cool:
Quote, using less than 2MB of memory
Still easy...  :cool: :cool:


Quoteand that runs in linear time
Does that mean no loops, jumps or calls? Not so easy.  :sad:


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.  :tongue:


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

jj2007

Quote from: zedd151 on December 23, 2022, 02:06:59 AM
Quote from: jj2007 on December 23, 2022, 12:55:38 AM
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.  :cool:

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

The algo is almost 3 times as fast as QuickSort (but you can't keep the duplicates):
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.  :tongue:
I don't think I will try working with bits. But also ...
Quote735828 phone numbers
a little short from one million.   :undecided:  You cheated.  :badgrin:
My code would be more usual stuff. I'll post it later.  :cool: 

... maybe

jj2007

Quote from: zedd151 on December 23, 2022, 02:44:55 AMYou 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

Quote from: jj2007 on December 23, 2022, 03:41:56 AM
Not really. When you create one Million random 7-digit phone numbers, there are lots of duplicates.
Okay, I'll buy that.  :tongue:  But wheres the source code?  :biggrin:
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.  :tongue:  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,

Quote from: FORTRANS on December 23, 2022, 03:54:30 AM
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

Quote from: jj2007 on December 23, 2022, 04:01:57 AM
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.  :tongue:  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 :tongue: )

jj2007

The random generator is excellent. It's something else :rolleyes:

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

Quote from: FORTRANS on December 23, 2022, 03:54:30 AM
Now one should find an actual application for it.
A call center that generates spam robocalls.  :tongue:  Of course the phone numbers would have to be valid.

Hi Steve!

jj2007


zedd151

Quote from: jj2007 on December 23, 2022, 04:59:26 AM
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 :

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