Hacker News Reader

Comment by dominotw | Hacker News Reader

My phone screen interviewer asked me this week to implement exponentiation function without using multiplication or addition.

How do i prepare for that :\ ?

View on HN

That's a difficult format, because the phone interview does not allow you to assert dominance by pissing at the corner of the interviewer's office desk.

Seems pretty harsh to me, and had you successfully answered that question I'm not quite sure what they'd have learnt.

If I were put on the spot with those constraints I'd suggest a lookup table.

I'm currently looking for a new job, however I tend to ask about the process upfront, if it sounds like a wanky anal probe type of interview I simply withdraw from the process. Which is sad, as some of the jobs I'd really like.

You don't. You simply allow whatever perfectly natural reaction your spinal cord chooses to trigger - to bubble up through your system. Which you should in no way be ashamed of. You're the one coming to them on good faith, expecting to be treated as a professional, after all. And they're the one who, unfortunately, has chosen to revert to silly mind games, and demonstrate a complete and obvious lack of respect for your time.

The only way to "prepare" for situations like these is to go in with a willingness to trust one's own gut - and to simply break off the interview once you start to feel you're not being treated professionally, and that the questions you're being asked are, like the above, completely out of line.†

† Okay, maybe if you were applying for the job of chairing some IEEE committee on numerical standards or something, thiis particular question might be. But I somehow doubt that was the case with this particular role.

EDIT: "this particular question might be" => "... might be applicable."

You read up on using bitwise operations to perform the usual ones, "how about you do some multiplication without actual multiplication" is one of the main interview inventions you want to know how to handle.

There's no straightforward way of implementing a general exponentiation function using only bitwise operations. Of course it is straightforward to compute 2^x for x an integer >= 0, or x*2, but it's not clear that this is the question that was posed.

IMHO if it's for a senior engineer position, you should at least be able to explain how that would be implemented (bitwise operations) even if you wouldn't get it right in a whiteboard.

You're not talking about an engineering problem, first of all (assuming it's a software implementation being talked about, of course). Secondly, it's difficult for me to see how this particular problem is a good motivation for discussion about the use of bitwise operations in general. I've written code in low level game engines, real time computational systems, physics and for drivers. The first and last items are the only ones where bitwise operations of this sort were even necessary to consider.

Unless this problem is for a job working on calculations on hardware that only supplies bitwise ops, it's a math trivia problem disguised as a coding interview question.

Depends on the job.

Aside from having to port an algorithm, I'm pretty sure the last time I used a bitwise operator seriously in 10 years was back in uni.

Could you explain it to us? Thx.

I know how bitwise operators works and have a CS degree... But even with googling I couldn't find a straight forward way to implement a general exponential operator using only bit operations.

You need some cleverness to code an add(x, y) method with only bitwise operators.

Then, you need to code a multiply(x, y) method using some more bit shifting cleverness and your new add method.

Then, do repeated squaring using your new multiply method.

Sure, but that's not a very satisfying answer because it doesn't rely on any special insight about how exponention works. It would be better to just ask someone to code up addition and/or multiplication using bitwise operations if that's what you want to test. That's sort of a reasonable question in the case of addition. Asking someone to implement multiplication using bitwise operations in a phone interview would be pretty crazy, though.

exponentiation be repeated squaring, multiplication by shift and add, then addition by subtraction "x - (- y)" or concatenating strings of the appropriate lengths (use printf in c), or bitwise operations

Nested for loop. Count the cycles.

Subtract and negations :)

If you start by using subtraction, I'm sure the interviewer will say that is disallowed as well. They're fishing for something else.

Better yet: repeatedly divide and then take the inverse.

Reply on news.ycombinator.com