4 ms·

The tools probably have changed but the fundamental language is the same. The same way that you need to wire your brain to see how a problem can be casted as a

The tools probably have changed but the fundamental language is the same. The same way that you need to wire your brain to see how a problem can be casted as a dynamic programming one, you also need to learn how to formulate problems as integer/linear programming ones. For example all of the "hard" leetcode problems can be casted as math programming ones. But the interviewers will not appreciate this solution approach lol. Once you conquer the logic/language then learning the tools is the easy part.

toolslive 2y ago
> But the interviewers will not appreciate this solution approach lol. I once witnessed a programmer with a PhD in Maths find closed form formulas for a lot of questions where it was expected to write some code with loops building/accumulating a result. As a simple example, to explain what was going on, if the question would be "calculate the 100th fibonacci number", she would just use Binet's formula to do so (as opposed to using a loop). I was rather impressed how often that happened.
- hyperthesis 2y ago
  TBF Binet's formula is astonishing
  - contravariant 2y ago
    If you think it is you should read up on linear algebra, specifically its use in finite difference equations and how that relates to linear differential equations. The astonishment doesn't get less, but it shifts from Binet's single formula to the exponential map, and maybe the fundamental theorem of algebra (or generalisations).
- LegionMammal978 2y ago
  Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression, but you'd still have to implement a bunch of fancy arbitrary-precision arithmetic to approximate the golden ratio through Newton's method. In other words, the formula gives much more information about the structure of the Fibonacci numbers than their actual values. For evaluating the Fibonacci numbers (as with any other integer linear recurrence), I'd generally prefer the matrix-exponentiation-by-squaring approach, or one of the simplified formulas based on it. Those don't need anything more complicated than bigint multiplication. [And from there, taking the ratio between two values gives you a quick way to approximate the golden ratio!]
  - fn-mote 2y ago
    Once you have postulated BigInt as available, the mathematician is going to make a rational approximation for phi using the continued fraction expansion that they know by heart (because of its “simplicity”).
    - LegionMammal978 2y ago
      Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.
- agumonkey 2y ago
  That's one thing that made me lost interest in computing. I felt we programmers are in fact centuries late to the party.
  - johnnyanmac 2y ago
    late to discovering proofs and thereoms, only a little bit late to apply them to real world problems.
travisjungroth 2y ago
Depending on the job, interviewer gripes may be legitimate, or at least they should give you the opportunity to write a different type of solution. If they’re writing a compartmentalized library specific to their domain, it’s fine. I’ve worked with a Stats PhD doing that. If you’re dropping them into a shared codebase, the comprehensibility of their code to the other people on their team is essential. Great code that depends on knowledge no one else on the team has is not great. You end up with “That’s going to take forever to change, Steve wrote it”.

toolslive 2y ago

> But the interviewers will not appreciate this solution approach lol. I once witnessed a programmer with a PhD in Maths find closed form formulas for a lot of questions where it was expected to write some code with loops building/accumulating a result. As a simple example, to explain what was going on, if the question would be "calculate the 100th fibonacci number", she would just use Binet's formula to do so (as opposed to using a loop). I was rather impressed how often that happened.

hyperthesis 2y ago
TBF Binet's formula is astonishing
- contravariant 2y ago
  If you think it is you should read up on linear algebra, specifically its use in finite difference equations and how that relates to linear differential equations. The astonishment doesn't get less, but it shifts from Binet's single formula to the exponential map, and maybe the fundamental theorem of algebra (or generalisations).
LegionMammal978 2y ago
Is Binet's formula really that practical a way to calculate the Fibonacci numbers (except asymptotically)? The problem is, you have this nice clean expression, but you'd still have to implement a bunch of fancy arbitrary-precision arithmetic to approximate the golden ratio through Newton's method. In other words, the formula gives much more information about the structure of the Fibonacci numbers than their actual values. For evaluating the Fibonacci numbers (as with any other integer linear recurrence), I'd generally prefer the matrix-exponentiation-by-squaring approach, or one of the simplified formulas based on it. Those don't need anything more complicated than bigint multiplication. [And from there, taking the ratio between two values gives you a quick way to approximate the golden ratio!]
- fn-mote 2y ago
  Once you have postulated BigInt as available, the mathematician is going to make a rational approximation for phi using the continued fraction expansion that they know by heart (because of its “simplicity”).
  - LegionMammal978 2y ago
    Calculating φ from its continued-fraction expansion is equivalent to just iterating the Fibonacci sequence normally, since its convergents are precisely the ratios between the Fibonacci numbers. At that point, it's totally redundant to use Binet's formula on the approximation, since you have the values already! If you want to beat the O(n^2) runtime of the trivial iteration, you pretty much have to use Newton's method for φ, exponentiation by squaring on the matrix form, or another method with faster-than-linear convergence.
agumonkey 2y ago
That's one thing that made me lost interest in computing. I felt we programmers are in fact centuries late to the party.
- johnnyanmac 2y ago
  late to discovering proofs and thereoms, only a little bit late to apply them to real world problems.

travisjungroth 2y ago

Depending on the job, interviewer gripes may be legitimate, or at least they should give you the opportunity to write a different type of solution. If they’re writing a compartmentalized library specific to their domain, it’s fine. I’ve worked with a Stats PhD doing that. If you’re dropping them into a shared codebase, the comprehensibility of their code to the other people on their team is essential. Great code that depends on knowledge no one else on the team has is not great. You end up with “That’s going to take forever to change, Steve wrote it”.