3 Interview-like Algorithm Questions for Programmers

Th­ese are my fa­vorite in­ter­view-style al­gorithm ques­tions for pro­gram­mers. I like these ques­tions be­cause they test how well you un­der­stand in­for­ma­tion den­sity in­stead of your abil­ity to re­gur­gi­tate facts.

Com­ments to help clar­ify puz­zle de­tails such as how the Enigma ma­chine works are al­lowed. Other­wise, com­ments with hints, an­swers and spoilers will be deleted, even if they use spe­cial for­mat­ting to hide spoilers. PM me if you are un­sure. Edit: I can’t ac­tu­ally do this with less than 2000 karma. Please self-mod­er­ate re­spon­si­bly.

1. Sorting

What is the fastest you can sort a list of ints in Java?

An­swer: time where is the length of the list

2. Search

blue vials

You have 1000 sal­iva sam­ples. Ex­actly 1 of them is from some­one in­fected by COVID-19. You have un­limited test­ing strips. Each day the CDC has re­sources to pro­cess up to 10 test­ing strips for you. You must send all 10 test­ing strips to the CDC at the same time. The next day, the CDC will tell you which of the 10 strips has been ex­posed to in­fected sal­iva. What is the fewest num­ber of days re­quired to figure out which sam­ple is in­fected?

An­swer: 1 day

3. Cryptography

Enigma machine

It is the year 1932. You work for the Pol­ish gov­ern­ment. They have cap­tured a Ger­man Enigma ma­chine. The Enigma ma­chine has three ro­tat­ing rub­ber ro­tors (disks). Each ro­tor has 26 cop­per wires feed­ing from one side to the other. At the back of the ma­chine is a re­flec­tor, re­flect­ing 13 of the con­tact points on the back of ro­tor 3 to the 13 other con­tact points on the back of ro­tor 3. In this way, the cur­rent gets scram­bled for­ward through ro­tors 1, 2, and 3 and then scram­bled back­wards through ro­tors 3, 2 and 1. Each time some­one presses a key, the first ro­tor ro­tates for­ward one let­ter. Every full ro­ta­tion of the first ro­tor, the sec­ond ro­tor ro­tates one let­ter. Every full ro­ta­tion of the sec­ond ro­tor, the third ro­tor ro­tates one let­ter.

Each let­ter of the alpha­bet is thus mapped to an­other let­ter of the alpha­bet in a sym­met­ric ci­pher. This ci­pher changes each keystroke. You can con­figure the Enigma ma­chine by set­ting the di­als with a 3-let­ter code. The Ger­mans change this code once per day. To­day the daily code might be SEC. To­mor­row it could be UNK. The Ger­mans also cre­ate a unique 3-let­ter code sep­a­rately for each mes­sage. The daily code is used to trans­mit the mes­sage code twice.

For ex­am­ple, if the daily code is SEC and the mes­sage code is MES then the Ger­mans will use the daily code SEC to en­code MESMES. This might re­sult in the ci­pher­text XFYZQM. Only these first 6 let­ters are en­crypted with SEC. The rest of the mes­sage is en­crypted with MES. The next mes­sage (on the same day) might have a mes­sage code COD. In this case, the daily code SEC is used to en­code CODCOD which might re­sult in the ci­pher­text IWVUBB.

De­sign the cheap­est ma­chine you can to break the Ger­man cryp­tosys­tem. You have ac­cess to nei­ther vac­uum tubes nor tran­sis­tors. You may as­sume the Ger­mans always use the same three ro­tors and never use the plug­board.

Hint: Mar­ian Rejewski