### Author Topic: A collection of programming problems  (Read 1769 times)

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### A collection of programming problems
« on: December 23, 2022, 12:55:38 AM »
Just in case you have nothing better to do

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

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #1 on: December 23, 2022, 02:06:59 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.
Quote
, using less than 2MB of memory
Still easy...

Quote
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?
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #2 on: December 23, 2022, 02:10:31 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.

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 numbers4317 µs for  setting the bits37 ms  for  sorting & storing 735828 phone numbers100002410000301000038100004510000481000081100009310000941000099100010596 ms for nrQsortA (there are duplicates)1000024100003010000301000038100004510000481000081100009310000941000099`

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #3 on: December 23, 2022, 02:44:55 AM »

Okay, you win.
I don't think I will try working with bits. But also ...
Quote
735828 phone numbers
a little short from one million.     You cheated.
My code would be more usual stuff. I'll post it later.

... maybe
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #4 on: December 23, 2022, 03:41:56 AM »
You cheated

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

#### FORTRANS

• Member
• Posts: 1235
##### Re: A collection of programming problems
« Reply #5 on: December 23, 2022, 03:54:30 AM »
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

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #6 on: December 23, 2022, 03:54:53 AM »

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.
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #7 on: December 23, 2022, 04:01:57 AM »
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

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #8 on: December 23, 2022, 04:12:48 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.    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 )
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #9 on: December 23, 2022, 04:14:39 AM »
The random generator is excellent. It's something else

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #10 on: December 23, 2022, 04:16:03 AM »
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?
Regards, zedd.

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #11 on: December 23, 2022, 04:38:23 AM »
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!
Regards, zedd.

#### jj2007

• Member
• Posts: 13932
• Assembly is fun ;-)
##### Re: A collection of programming problems
« Reply #12 on: December 23, 2022, 04:59:26 AM »
same initial seed used?

Yes indeed, makes spotting bugs easier.

#### zedd151

• Member
• Posts: 1942
##### Re: A collection of programming problems
« Reply #13 on: December 23, 2022, 05:08:50 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.
Regards, zedd.

#### Vortex

• Member
• Posts: 2787
##### Re: A collection of programming problems
« Reply #14 on: December 23, 2022, 05:51:41 AM »
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 }`