3 Interview-like Algorithm Questions for Programmers
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
These questions are way too ‘Eureka!‘/trivia for my taste. The first question relies on language specifics and then is really much more of a ‘do you know the moderately weird sorting algs’ question than an actual algorithms question. The second involves an oddly diluting resistant test. The third, again seems to test moderately well known crypto triva.
I’ve conducted ~60 interviews for Google and Waymo. To be clear, when I or most other interviewers I’ve seen say that a question covers ‘algorithms’ it means that it covers algorithm design. Ex. how do you find all pairs in an array whose sum is a given value? Such a question can be answered in several different ways, and the ‘best’ way involves using some moderately interesting data structures.
I’m super curious what kind of rubric you use in grading these questions.
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.
Re: #1:
Which sorting algorithm shows O(n) time complexity given no assumptions but that the values are integers?
There is no such algorithm.
… then your answer is wrong. So… what gives?
This question isn’t about integers “given no assumptions”. It’s about the
intprimitive in Java.Nevermind.
I think the trick you’re going for (and I agree with others that these are mostly tricks—fun for conversation, interesting puzzles among friends, but fairly poor for interviews) requires a further restriction than an arbitrary array of Java primitive ints.
This is too close to an answer, so I’ll further obscure it. I used rot-221 for extra secrecy!
V guvax gurl arrq gb or pbagvthbhf, fhpu gung gur enatr vf gur fnzr nf gur neenl fvmr. Gurer vf ab fbeg orggre guna B(AybtA) gung arrqf gb pbzcner ryrzragf gb rnpu bgure.
I share the general sentiment that these are tricks and unsuitable for interviews, but lsusr’s answer is correct and does not require additional constraints.
3. Crypto.
create another
Let’s imagine the daily code the machine is set it with is AAA.
Would this turn the plaintext “X” into the ‘ciphertext’ “X”?
But not “XX” to “XX”, because typing changes the configuration?
Fixed typo.
No, for a couple reasons.
First of all, each of the rotors have a different wiring. For example, in the first rotor, A might be wired to B and B might be wired to M.
Secondly, the reflector makes it impossible for any letter to be mapped to itself.
You are correct that the plaintext AAA is unlikely to be encrypted into the same letter multiple times such as BBB, due to the rotating rotors.
The rotors move after each typed character, but the way they move is independent of which character it is?
Yes. They move independent of which character it is.
For Question #1, I think you mean “lowest big-O complexity” not “fastest”, since constant factors matter a lot for actual fastest.
I do indeed mean “lowest big-O complexity”.
I want to know why the answer to the first question is like that.
How many samples can be included on one test strip? This study of saliva based testing only looked at a 5x spread of copies/mL (200 − 1000) which implies that actual positive samples could be diluted beyond detection if too many negative samples are included.
No limit.