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?

36 904 13

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:

Where Next?

Popular General Dev topics Top

brentjanderson
From wikipedia: The zettelkasten (German: “slip box”) is a knowledge management and note-taking method used in research and study. ...
12 934 4
New
PragmaticBookshelf
Craft your dream role at work by guiding your manager to take your priorities into account when making decisions. Ken Kousen @kenko...
30 2744 10
New
AstonJ
On my Mac I would just use Apple’s Preview which open’s PDF files, and on the Kindle their standard app. On the iOS devices I am preferr...
18 1257 8
New
OvermindDL1
An interesting and yet simple programming question making the rounds the past few days, how does everyone here answer: Given an input f...
36 904 13
New

Other popular topics Top

Exadra37
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it. Does your monitor have eye p...
227 8684 88
New
AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
243 5922 95
New
AstonJ
We have a thread about the keyboards we have, but what about nice keyboards we come across that we want? If you have seen any that look n...
49 5284 39
New
AstonJ
Just done a fresh install of macOS Big Sur and on installing Erlang I am getting: asdf install erlang 23.1.2 Configure failed. checking ...
10 5616 8
New
AstonJ
Do the test and post your score :nerd_face: :keyboard: If possible, please add info such as the keyboard you’re using, the layout (Qw...
82 6920 31
New
Exadra37
Oh just spent so much time on this to discover now that RancherOS is in end of life but Rancher is refusing to mark the Github repo as su...
10 5256 6
New
wmnnd
Here’s the story how one of the world’s first production deployments of LiveView came to be - and how trying to improve it almost caused ...
37 2727 14
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
21 5598 9
New
First poster: bot
zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig. General-purpose programming language and toolchain for maintaini...
0 2781 0
New
CommunityNews
A Brief Review of the Minisforum V3 AMD Tablet. Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
0 1782 0
New