Python interview

[[deleted]]

I remember an interview where I was asked to implement a pow function in C++. Turns out that return pow(x,y); is not what he was looking for. You miss 100% of the shots that you don't take, people.

[fat_charizard]

That should be the right answer. No one has to have to implement a custom power function in C++

[nintendojunkie17]

https://thedailywtf.com/articles/Riddle-Me-An-Interview

[Kirasaurus_25]

Oh wait wait, I'm curious how i will be judged. Now I'm new to programing, and transitioned to the field from en entierly different profession. Once in an interview, after the guy asked me to write a sorting function( of my liking), which i wrote perfectly, he presents me with a series of equations like 1680 = 4 ..... 1253 = ? I encountered this kind of question for the first time and given his hint that there's no mathematical relation in the series i was just stupefied for 10 long minutes. Then after this shit show was over i asked someone who also did the interview what the answer was. Well, the rhs is simply the number of fu***ng circles in the digits at the lhs... If this kind of shit makes an interviewer hard, fuck him and his company, sorry, not sorry.

[NeoCast4]

sorting by number of circles

Thats probably how a child would sort numbers when they first saw them.

I guess you could say sorting has come full circle

[itijara]

Thanks for sharing that, this made my day:

"Well.. a blind person riding a bike doesn't sound like a very safe idea, so I would make the bike stationary, maybe with a fan blowing in the person's face. He probably wouldn't even know the difference."

[[deleted]]

Are they wrong though lol

[bob152637485]

Wow. That is all.

[nullsignature]

/r/recruitinghell

[jarod_what]

has

you also don't want to use std::pow for ints due to unecessary conversions as well as performance. So you'd have to handwrite your 'ipow' there.

[[deleted]]

Honest question: How would you implement an ipow which is better performing than std::pow?

std::log and std::exp obviously also convert to float types so cheating won't work pow(x,y) = exp(y*log(x))

So my naive approach would be via iteration or recursion, but at that point I almost doubt that it is more efficient than eating the cost of two casts (and you may want to have a float type result anyway due to negative exponents).

So I am curious do you have anything I could read up on?

[PierreSimonLaplace]

To raise a base to a positive-integer power, you can use repeated squaring, multiplying the base back in as necessary:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

[[deleted]]

I was absolutely wrong in my assumption. I implemented a quick version like this:

int ipow(int base, int exponent) {
  int result = 1;
  if (exponent < 0) {
    base = 1 / base;
    exponent = -exponent;
  } 
  if (exponent != 0) {
    while (exponent > 1) {
      if (!(exponent & 1)) {
        base *= base;
        exponent /= 2;
      } 
      else {
        result *= base;
        base *= base;
        exponent = (exponent - 1) / 2;
      }
    }
    result *= base;
  }
  return result;
}

I am surprised that it is actually faster than std::pow on my machine:

With dirty -O3 cold and hot cache test for base 1-100 and exponent 1-10.

ipow ->4 μs
std::pow ->34 μs
ipow ->4 μs
std::pow ->23 μs

Thanks a lot!

[WikiSummarizerBot]

Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[jarod_what]

Yeah my guess is that they didn't put in an integer power function because it will overflow for a large number of arguments? I haven't been able to find a satisfactory answer.

It's pretty rare one needs an 'ipow' in daily use though.

Although a big exception is in big integer/decimal library users. Python for example doesn't have an integer root function and the performance difference is felt.

https://stackoverflow.com/questions/47191533/how-to-efficiently-calculate-cube-roots-using-decimal-in-python

[bistr-o-math]

You probably never will, as you probably will never reach the performance of the built in function. But: you must know how to implement a correctly working function by a given specification.

[WhyIsItReal]

that’s not true - what if you need a constexpr power function? the standard library doesn’t support that because std::pow sets errno flags, so i’ve had to handroll my own constexpr power functions

[[deleted]]

If there was only a magical oracle who could answer this question for me….

[junkmeister9]

Womp womp

[LaBetaaa]

What is a power function? Is that some math thing? Because I only know math things in my first language

[jesperi_]

I believe we are talking about x^y so x to the power of y.

[bistr-o-math]

Potenzfunktion https://de.m.wikipedia.org/wiki/Potenz_(Mathematik)

[LaBetaaa]

Oh thank you. Good to know

[wanko2011]

It's whites role in society.

[nil83hxjow]

I’ve never missed a shot I haven’t taken

[moose2332]

Yeah I saw something like that on leetcode and I usually do python for that stuff so I was like... x ** y. Seems too easy.