3 Interview-like Algorithm Questions for Programmers

post by lsusr · 2020-03-25T09:05:10.875Z · LW · GW · 18 comments

Contents

  1. Sorting
  2. Search
  3. Cryptography
None
18 comments

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?

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?

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.

18 comments

Comments sorted by top scores.