OvermindDL1

OvermindDL1

Fun Programming Question 2022-04-18

An interesting and yet simple programming question making the rounds the past few days, how does everyone here answer:

Given an input file with precisely 4 billion randomly-sorted non-negative 32-bit integers, provide an algorithm to generate a non-negative 32-bit integer that is not contained in the file.

Now of course the canonical answer is to create a zeroed 2^32-bit sized bit field (which consumes 512 megs of memory), and set each bit to 1 as you encounter its index in the file, then search for a 0 bit after, but that is memory heavy and potentially requires up to a near full second pass, how would you do it in, say, 10 megs or memory or so? What different ways and pattern with what different tradeoffs can you come up with?

Most Liked

OvermindDL1

OvermindDL1

One of the more popular ways to solve this, spoiler in case you want to figure it out:

Probabilistic Method

Remember that there are 4 billion numbers, in a 32-bit address space, which is 4294967296 in size, meaning that 294967296 are available, just need to find one. So if you, as an example, just select 100 unique numbers, then parse through the input once weeding them out for what you find, then you have a greater than 99.9% chance of finding a valid number just in the first pass, and if it doesn’t work then you can repeat it again and again until it does, probabilistically it will work quickly, and even more quickly if you select even more numbers to test with, 10 megs worth of numbers (2500000 of them) means that even in the worst case you loop over the input again and again 1599 times, which is still not ‘too’ bad even if not great, and that would only happen if you didn’t select any of the 294967296 available numbers until the very end.

There are other ways still!

kokolegorille

kokolegorille

If the problem is funny for You, it might mean it is unsolvable for me :slight_smile:

ohm

ohm

Since the list is sorted you could subtract two consecutive entries. If the result is not 1, then you have a missing number. :person_shrugging:

Popular General Dev topics Top

AstonJ
I really like our #general-developer-forum:in-the-news section and am wondering whether we could automate some of the cross-posting of th...
New
New
foxtrottwist
Here’s our thread for the Keyboardio Atreus. It is a mechanical keyboard based on and a slight update of the original Atreus (Keyboardio ...
New
AstonJ
Perhaps we can add some vids on sound differences, those I’ve seen so far are giving the plastic cases a nice stock sound (you could do s...
New
AstonJ
Please share your favourite Vim tips here :nerd_face:
New
Margaret
Hello content creators! Happy new year. What tech topics do you think will be the focus of 2021? My vote for one topic is ethics in tech...
New
Margaret
Hello everyone! This thread is to tell you about what authors from The Pragmatic Bookshelf are writing on Medium.
1126 25250 746
New
foxtrottwist
A few weeks ago I started using Warp a terminal written in rust. Though in it’s current state of development there are a few caveats (tab...
New
First poster: bot
Raspberry Pi security alarm — the basics. In November last year — I started building a DIY security alarm system, using a Raspberry Pi a...
New
First poster: bot
Large Language Models like ChatGPT say The Darnedest Things. The Errors They MakeWhy We Need to Document Them, and What We Have Decided ...
New

Other popular topics Top

AstonJ
In case anyone else is wondering why Ruby 3 doesn’t show when you do asdf list-all ruby :man_facepalming: do this first: asdf plugin-upd...
New
DevotionGeo
The V Programming Language Simple language for building maintainable programs V is already mentioned couple of times in the forum, but I...
New
mafinar
Crystal recently reached version 1. I had been following it for awhile but never got to really learn it. Most languages I picked up out o...
New
OvermindDL1
Woooooooo! This is such a huge release for it, and 2 years incoming! In short, the library is now using an updated hyper backend (not j...
New
AstonJ
Saw this on TikTok of all places! :lol: Anyone heard of them before? Lite:
New
AstonJ
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
Help
I am trying to crate a game for the Nintendo switch, I wanted to use Java as I am comfortable with that programming language. Can you use...
New
New
PragmaticBookshelf
Author Spotlight: Bruce Tate @redrapids Programming languages always emerge out of need, and if that’s not always true, they’re defin...
New

Latest in General Dev

View all threads ❯