These are my favorite interview-style algorithm questions for programmers. I like these questions because they test how well you understand information density instead of your ability to regurgitate facts.
Comments to help clarify puzzle details such as how the Enigma machine works are allowed. Otherwise, comments with hints, answers and spoilers will be deleted, even if they use special formatting to hide spoilers. PM me if you are unsure. Edit: I can't actually do this with less than 2000 karma. Please self-moderate responsibly.
1. Sorting
What is the fastest you can sort a list of ints in Java?
Answer: time where is the length of the list
2. Search
You have 1000 saliva samples. Exactly 1 of them is from someone infected by COVID-19. You have unlimited testing strips. Each day the CDC has resources to process up to 10 testing strips for you. You must send all 10 testing strips to the CDC at the same time. The next day, the CDC will tell you which of the 10 strips has been exposed to infected saliva. What is the fewest number of days required to figure out which sample is infected?
Answer: 1 day
3. Cryptography
It is the year 1932. You work for the Polish government. They have captured a German Enigma machine. The Enigma machine has three rotating rubber rotors (disks). Each rotor has 26 copper wires feeding from one side to the other. At the back of the machine is a reflector, reflecting 13 of the contact points on the back of rotor 3 to the 13 other contact points on the back of rotor 3. In this way, the current gets scrambled forward through rotors 1, 2, and 3 and then scrambled backwards through rotors 3, 2 and 1. Each time someone presses a key, the first rotor rotates forward one letter. Every full rotation of the first rotor, the second rotor rotates one letter. Every full rotation of the second rotor, the third rotor rotates one letter.
Each letter of the alphabet is thus mapped to another letter of the alphabet in a symmetric cipher. This cipher changes each keystroke. You can configure the Enigma machine by setting the dials with a 3-letter code. The Germans change this code once per day. Today the daily code might be SEC. Tomorrow it could be UNK. The Germans also create a unique 3-letter code separately for each message. The daily code is used to transmit the message code twice.
For example, if the daily code is SEC and the message code is MES then the Germans will use the daily code SEC to encode MESMES. This might result in the ciphertext XFYZQM. Only these first 6 letters are encrypted with SEC. The rest of the message is encrypted with MES. The next message (on the same day) might have a message code COD. In this case, the daily code SEC is used to encode CODCOD which might result in the ciphertext IWVUBB.
Design the cheapest machine you can to break the German cryptosystem. You have access to neither vacuum tubes nor transistors. You may assume the Germans always use the same three rotors and never use the plugboard.
Hint: Marian Rejewski
If you happen to know the answer already then the question is ruined. In this way, every algorithm puzzle in the world can be ruined by trivia. For an algorithm question to be interesting, I hope the reader doesn't already know the answer and has to figure it out her/himself. So in questions #1 and #3, I'm hoping the reader doesn't know the relevant trivia and will instead independently derive the answers without looking them up.
I'm not trying to ask "Do you know how Poland cracked the Enigma?" I'm trying to ask "Can you figure out how Poland cracked the Enigma?"
I don't grade these questions. These questions are for fun and self-improvement. Though I could imagine a timed written test with dozens of questions like this where the testee gets one point for each correct answer and loses one point for each incorrect answer. A sufficiently large number of questions might help counteract the individual variance.