3 ms·

If this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-using-multiplication-oper

by munin 9y ago

If this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-using-multiplication-operator-loops/ http://www.techiedelight.com/multiply-two-numbers-without-us... "Implement multiplication without using loops." "Uh, okay. What do you mean by loops?" "Don't use a conditional loop." "What do you mean by a conditional loop?" "Oh, you know, the standard definition." Time passes. "I'm stuck. What is the answer?" "Oh, you just have a loop on b dividing it by 2 using shift operators until it is zero." "Wait a minute, you said you couldn't use loops." "Did I? Ah, well." Hackerrank/leetcode exercises are written the same way. So many times that a problem asks "Output the indexes of two numbers in the array such that their sum is K" and you write your code and the website says "INCORRECT! You said [3,6] but the right answer was [6,3]". Addition is commutative! The two are equal! And both right!

userbinator 9y ago
The real way to multiply without loops is to use a lookup table, or unroll the (fixed iteration) shift-and-add loop. That page is both hilarious and sad at the same time. Hilarious because the second "solution" clearly has a loop, and sad because sites like those don't really help anyone. Some of the pages on that site are downright WTFs: http://www.techiedelight.com/generate-binary-numbers-1-n/ http://www.techiedelight.com/generate-binary-numbers-1-n/
- vikiomega9 9y ago
  "What I told you the question was either or" haha
- bogomipz 9y ago
  >"or unroll the (fixed iteration) shift-and-add loop" Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"
  - userbinator 9y ago
    The shift-and-add algorithm for multiplication is usually implemented as a loop that iterates for the number of bits of the operand, so e.g. for an 8-bit x 8-bit multiplication, the loop runs 8 times. (An "early out" algorithm when one of the operands becomes 0 is also common, but let's not complicate things here.) It's trivial to unroll this loop into the 8 individual shift-and-add steps.
0xfeba 9y ago
> Multiply two numbers without using multiplication operator or loops Uh, ok: a * b = b != 0 ? a/(1/b) : 0 Done. EDIT: handle division by zero.
bloaf 9y ago
Mult(A,B) = Exp(Log(A) + Log(B))
- mike_ivanov 9y ago
  You didn't pass (overqualified, will likely be bored by the job).
  - bloaf 9y ago
    More like: bad culture fit, expects a standard library that handles infinite quantities and complex numbers out of the box. Edit: how about (Math.Pow(a+b, 2) - Math.Pow(a,2) - Math.Pow(b,2))/2
alexee 9y ago
I was asked something like this in Amazon SE interview - find something without using loops, the answer was to use recursion. Sigh.
- SomeStupidPoint 9y ago
  Isn't there an actual distinction here -- induction versus co-induction? I would argue that a loop constructs an answer, while recursion deconstructs input. There's a duality, so you can port algorithms between the two models, but there is an actual distinction.
  - hedora 9y ago
    I don’t see what recursion/loops have to do with constructing output or dividing and conquering input. For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. Clearly these transforms have no bearing on the nature of the computation. If asked such a question, I’d probably just use goto. (Bonus points if candidates use a goto on one part of one question I ask, since it saves a minute or two of whiteboard cut and paste, BTW).
    - SomeStupidPoint 9y ago
      > For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. That there's a transform between them doesn't make them the same thing, it makes them possible to use for each other in programming. You even seem aware that there's still a distinction -- you're just not sure why it matters. > Clearly these transforms have no bearing on the nature of the computation. Depending on the nature of the job, not understanding why you can transform between loops and recursion is big points off. (You can go back and forth because while not the same thing, they're duals, which means you'll be able to find similar structures in both for certain classes of problems.) That's why you need to understand what induction vs co-induction is -- so you can prove things about the transforms between them, such as that it doesn't impact the result to change the algorithm in a particular manner. Similarly, you're only talking about really simple inductive or recursive behaviors -- what about complex cases? Are all inductive structures transformable to co-inductive (or the other direction)? What does it do to computational complexity when you make the transform? That there's an uninteresting kernel in the transform doesn't make the entire transform trivial -- it just means you're only used to working in the "well-behaved" portion of it. (And that there is such a kernel is itself an interesting fact about computation!) > Clearly these transforms have no bearing on the nature of the computation. Just to reiterate how off-base I find this comment: there's entire huge collaborations in mathematics and academic computer science exploring the nature of those transforms because understanding how they can be applied is essential for moving forward with things like mechanically/formally verified software. I get that not everyone is going to know that distinction and its impact -- but the distinction absolutely matters. As you astutely point out, it's used by compilers routinely -- and they certainly need to be sure the transform is well-behaved in the cases they apply it!

by munin 9y ago

userbinator 9y ago

The real way to multiply without loops is to use a lookup table, or unroll the (fixed iteration) shift-and-add loop. That page is both hilarious and sad at the same time. Hilarious because the second "solution" clearly has a loop, and sad because sites like those don't really help anyone. Some of the pages on that site are downright WTFs: http://www.techiedelight.com/generate-binary-numbers-1-n/ http://www.techiedelight.com/generate-binary-numbers-1-n/

vikiomega9 9y ago
"What I told you the question was either or" haha
bogomipz 9y ago
>"or unroll the (fixed iteration) shift-and-add loop" Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"
- userbinator 9y ago
  The shift-and-add algorithm for multiplication is usually implemented as a loop that iterates for the number of bits of the operand, so e.g. for an 8-bit x 8-bit multiplication, the loop runs 8 times. (An "early out" algorithm when one of the operands becomes 0 is also common, but let's not complicate things here.) It's trivial to unroll this loop into the 8 individual shift-and-add steps.

0xfeba 9y ago

> Multiply two numbers without using multiplication operator or loops Uh, ok: a * b = b != 0 ? a/(1/b) : 0 Done. EDIT: handle division by zero.

bloaf 9y ago

Mult(A,B) = Exp(Log(A) + Log(B))

mike_ivanov 9y ago
You didn't pass (overqualified, will likely be bored by the job).
- bloaf 9y ago
  More like: bad culture fit, expects a standard library that handles infinite quantities and complex numbers out of the box. Edit: how about (Math.Pow(a+b, 2) - Math.Pow(a,2) - Math.Pow(b,2))/2

alexee 9y ago

I was asked something like this in Amazon SE interview - find something without using loops, the answer was to use recursion. Sigh.

SomeStupidPoint 9y ago
Isn't there an actual distinction here -- induction versus co-induction? I would argue that a loop constructs an answer, while recursion deconstructs input. There's a duality, so you can port algorithms between the two models, but there is an actual distinction.
- hedora 9y ago
  I don’t see what recursion/loops have to do with constructing output or dividing and conquering input. For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. Clearly these transforms have no bearing on the nature of the computation. If asked such a question, I’d probably just use goto. (Bonus points if candidates use a goto on one part of one question I ask, since it saves a minute or two of whiteboard cut and paste, BTW).
  - SomeStupidPoint 9y ago
    > For one thing, all loops can be trivially unrolled into a tail-recursive function that most languages will trivially transform back into a loop. That there's a transform between them doesn't make them the same thing, it makes them possible to use for each other in programming. You even seem aware that there's still a distinction -- you're just not sure why it matters. > Clearly these transforms have no bearing on the nature of the computation. Depending on the nature of the job, not understanding why you can transform between loops and recursion is big points off. (You can go back and forth because while not the same thing, they're duals, which means you'll be able to find similar structures in both for certain classes of problems.) That's why you need to understand what induction vs co-induction is -- so you can prove things about the transforms between them, such as that it doesn't impact the result to change the algorithm in a particular manner. Similarly, you're only talking about really simple inductive or recursive behaviors -- what about complex cases? Are all inductive structures transformable to co-inductive (or the other direction)? What does it do to computational complexity when you make the transform? That there's an uninteresting kernel in the transform doesn't make the entire transform trivial -- it just means you're only used to working in the "well-behaved" portion of it. (And that there is such a kernel is itself an interesting fact about computation!) > Clearly these transforms have no bearing on the nature of the computation. Just to reiterate how off-base I find this comment: there's entire huge collaborations in mathematics and academic computer science exploring the nature of those transforms because understanding how they can be applied is essential for moving forward with things like mechanically/formally verified software. I get that not everyone is going to know that distinction and its impact -- but the distinction absolutely matters. As you astutely point out, it's used by compilers routinely -- and they certainly need to be sure the transform is well-behaved in the cases they apply it!