511–520 of 547 posts
Earlier quoted context omitted.
Instead of recursing twice, recurse once, by carrying around not fib(n-1) but the pair (fib(n-2), fib(n-1)).
True, but then the "worker" fib() method should be called fib_calculate() and should be wrapped by fib() which then returns a single integer. I believe that breaks the spirit of the question.
This article is an excellent example of why most companies should never ask about algorithms in an interview. The author has worked for elite companies and yet even there he rarely had to reach something advanced. I've worked on some cool and really hard stuff in my career including cryptography and a popular Facebook app where my team used a graphdb, etc, etc, etc. And I would fail at most of today's interviews. For…
I call this distinction red flag versus green flag interviews. The typical hiring process is looking to quickly disqualify all but 1 person in the hundreds of resumes submitted to any open software engineering position. The hiring process you are proposing is looking to methodically search for all of the useful qualities in the candidate pool and determine how they can best be applied at the company. I think we can a…
> The hiring process you are proposing is looking to methodically search for all of the useful qualities in the candidate pool and determine how they can best be applied at the company.
That's not necessarily what I'm proposing. I often need find the first qualified candidate who can start contributing. Don't let perfect be the enemy of good.
One of the ways I accomplish cost effective hiring is to go through applications in the order they arrive and the first candidate who passes the interview gets the job. If I get 200 applications and I find a suitable candidate in the 1st interview, why would I waste my time and money doing the other 199 interviews?
I sometimes even use recruiters when my time is at a premium. And that raises another interesting question: how is it that so many recruiters who can't code have been able to send me top quality candidates so consistently? Which leads me right back to my first point in this thread: this article is an excellent example of why most companies should never ask about algorithms in an interview.
Earlier quoted context omitted.
I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically…
I had the opposite experience in a Google interview. I just said, that can be solved with a topological sort, and then we moved on. But I failed with another interviewer. He kept asking how to prevent hashing from producing collisions. The answer was universal hashing, but I had forgotten about that
Earlier quoted context omitted.
And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.
Your surprise comes from the fact that you're modeling an institution as a single person when it in reality consists of a hundred thousand people. It's obviously less mental effort to reason about large entities this way, but it's obviously much less accurate.
Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS ( https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... ) this is.…
Earlier quoted context omitted.
In Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!
> If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. The recursive Python version above didn't use tail calls. I don't think that a Haskell or Scheme compiler would compile the equivalent versions into a simple loop.
GHC is sometimes able to do some of those transformations.
> The recursive Python version above didn't use tail calls.
Just to be more pedantic: it did use tail calls, but the recursive calls weren't the tail calls.
Earlier quoted context omitted.
In Python, yes. If you have a decent language and a good compiler / interpreter, then the recursion with function calls will have no overhead over iteration. (Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) But, agreed with everything else you wrote!
>(Basically, in Haskell or Scheme your recursion will be compiled into the same machine language sequence of straight-line code plus conditional jump as the iterative loop.) This is not true. The recursive code will not compile with zero overhead even in haskell or lisp. fib :: int -> int fib 0 = 1 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) The code above will add layers to the call stack and has a speed complexity…
Though GHC is sometimes able to do some simple transformations on its own. But not in this case.
For anyone trying this at home: I suggest calculating your additions modulo some constant, so that the numbers involved stay within a fixed size. (Otherwise, you either hit the limits of Int and weird things can happen, or when calculating with the arbitrary precision type Integer, your numbers themselves will grow linearly in space.)
Earlier quoted context omitted.
Of course, recursion vs iteration is mostly an implementation detail. Here's a recursive version (expressed in Python) that works better than your loop: def fib(n): if n = (I say it works better, because it has the same asymptotic runtime, but fails better: When numbers get large, your C version will run into undefined behaviour that can cause arbitrary problems. The Python version will just crash with a well-defined…
> I say it works better, because it has the same asymptotic runtime [...] To be fair, while the asymptotic runtime may be the same, the C version is about 180 times faster.
Though if we allow programs like the C example that give wrong answers or have undefined behaviour, I can write an even faster version that takes no time at all.