41 ms·

Interviewer: "Write a Θ(log(n)) approximation algorithm for converting n miles to kilometers that's accurate within plus or minus .01*n kilometers."

• garrettgarcia 2y ago
  def m2k(n): return n*1.609344 There, did it in O(1)
  • dirtdobber 2y ago
    I said θ ;) In other words, your algorithm is asymptotically too fast and you failed the interview! :D
    • cben 2y ago
      You could add "without using multiplication or division" as a less arbitrary constraint. Early microprocessors (and some really cheap microcontrollers still) didn't have the circuitry. That said a fixed-factor mutiplication can probably be done faster AND [more] precisely as a sum of some shifts. Or many other ways with a lookup table.