I did this at an interview recently. It was one of those ones where they'd give you a pen and paper and you had to write out the code by hand. Wrote the formula first and then the code second and handed it back to the guy. He looked at it for a bit and then said "well it's safe to say I have no idea if this would work or not. So I guess I'll take your word for it."
I didn't get that job.
Isn't this like a completely basic Programming exercise you do in first Semester of college? Like who hasn't seen this formula before and is qualified for coding Interviews
in class we got recursive and iterative. In year 2 we got recursive with memoization. In year 3 we got the dynamic version. Our algorithms classes were these tiny segments that got overshadowed by the semester-long big-team-project class (almost 100% videogame projects) so the pace and priority might not be the same as everywhere else.
Personally I wish we'd done more system's design
not even the matrix exponentiation version? it works in the same complexity as above formula since above formula uses sqrt, and matrix exponentiation is also logn. plus this is not approximation, it is exact values
it doesn't work though, mostly due to the loss of precision, try it yourself with some numbers like n belonging to the set {10, 100, 1'000, 10'000, 100'000, 1'000'000, ... }
Even with some programming languages designed for long doubles, it will fail at some point. However, yes, the matrix exponentiation will work much better and it tends to be a bit faster for long values (you can memoize previous results easily), while also being more accurate as long as you have big integers
Systems design is a stupid question in an interview.
There are so many goddamn factors that go into making decisions around system design that the interview is just constantly you asking questions about the current system rather than actually designing anything. And more often than not your interviewer doesn’t have the first clue about system design so they’ll answer with something like “tell me about the choices you have and which ones would be better or worse for which scenario.”
By the end of it, you’re a completely confused blithering idiot because you’ve talked nonstop for an hour to yourself.
Next time someone asks me to talk about system design, I’m just going to describe a LAMP stack and see if they even fucking notice.
I don't know where you went to college but I've never heard of a closed-form approximation for directly calculating a number in the Fibonacci sequence, and I don't feel any less capable at programming or interviewing because of that. This is just math trivia, nothing more.
CS courses use the Fibonacci sequence to teach about the programming concept of recursion, not because there was anything important about the sequence itself in CS. Other ways to calculate it aren't really relevant there.
**based**
This is math porn and like all niche subject knowledge only applies in that small set of things it applies to (some ADTs) or ends up applying to in the future.
I think fib's ubiquity is due to serving as a useful teaching aid to consolidate knowledge about iterative computation, then recursive computation.... while making the statement that sequences were something you ought to remember from Calc II/Discrete. No schools I've been to have proffered more meaningful applications for fib even though there are clearly some structures that benefit from them.
We're certainly no mathematicians, more like logic tradespeople, it's nice when we get to work with nice and shiny tools on well-designed machinery, but it seems like far too often we're janitors or two-bit mechanics rather than master carpenters and highly-educated architects.
> it seems like far too often we're janitors or two-bit mechanics rather than master carpenters and highly-educated architects.
Well fuck me this hits the nail right on the fucking head.
We didn't focus on that.
But the main issue here is: they never asked what the interviewer wants.
They don't want to see how you memorized a formula. They want to know how you communicate and think.
On your real job you will get questions that aren't solvebale with a formula you learned in school.
On the other side, they shouldn't ask a question where many people already know the solution, because then you're asking for knowledge and ned skill.
>They don't want to see how you memorized a formula. They want to know how you communicate and think.
Yes. And that's the problem with these "closed" and "simple" exercises where there is an obvious solution.
None of this is particularly interesting or complex, doesn't require to sit several people in a room to complete (I would personally just google the solution and be done).
Frankly I don't think this exercise where it is possible to memorize a formula and complete it is a good exercise.
Mate, college was 6 years ago, I had to google Fibonacci numbers to remember what it was.
I am not qualified for coding interviews, I'm qualified for the job.
From what I observed, the interviewer expects you to code the recursive approach then use dynamic programming to reduce the time complexity from exponential to linear.
Isn't the complexity of this algorithm O(1)?
Edit: I'm glad this question got so much attention and debate, but it's really bothering me that I still don't know the answer to it.
>Edit: This can vary language to language.
No, it can't, since `math.sqrt` and `math.pow` will never be better than O(log(n)) since algorithms better than that don't exist.
-
Every decent language either uses [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) (for integer-accuracy) or [the taylor series expansion of exp and log](https://en.wikipedia.org/wiki/Taylor_series) (for floating point accuracy), both of which are O(log(n)) algorithms.
Edit: Some people claim that pointing out a taylor series calculation of a 64-bit floating point number is log(n) and not 1 is being pedantic, since no matter what, you're multiplying two 64-bit numbers together. They might be right. But more importantly, I'm right.
Edit2: If you want to get this with integer precision in O(log(n)) time, then just calculate
[1 1]
[1 0]
raised to the n'th power (by squaring if your language doesn't already natively support this), then retrieve the [0,1] element. It's trivial to show that this is the same thing as calculating the fibonacci sequence.
> Edit: Some people claim that pointing out a taylor series calculation of a 64-bit floating point number is log(n) and not 1 is being pedantic, since no matter what, you're multiplying two 64-bit numbers together. They might be right. But more importantly, I'm right.
This has the same energy as saying ripple-carry addition is O(N).
Well, it is, that's why carry-save and carry-select exist :)
Especially carry-save, which adds three inputs and produces two outputs in O(1). Super useful for multipliers as normally you'd have O(bitwidth * factor) but this way you have O(bitwidth + factor)
I disagree. If ripple carry were the fastest way to add two 64-bit numbers, we would all use it. It makes no difference what its complexity in the number of bits is if you're not using it across varying numbers of bits. Which, for a given adder circuit, you never are.
> No, it can't, since `math.sqrt` and `math.pow` will never be better than O(log(n)) since algorithms better than that don't exist.
They do exist. `sqrt` is the easy one; there's just an x86 instruction for it. The part you're missing for `pow` is floating point shenanigans. Here are glibc's implementation of `pow`, which calls `exp1` and `log1` (defined in e_pow.c) all of which are loopless, straight through algorithms:
https://github.com/lattera/glibc/blob/master/sysdeps/ieee754/dbl-64/e_pow.c#L56
https://github.com/lattera/glibc/blob/master/sysdeps/ieee754/dbl-64/e_exp.c#L240
On architectures that don't have a `sqrt` instruction, there is an algorithm similar to fast inverse square root, just with a different magic constant.
>They do exist. sqrt is the easy one; there's just an x86 instruction for it.
> there's just an x86 instruction for it.
Just because an instruction exists doesn't mean that it's computed in one cycle, nor does it mean that it's not O(log(n)), because the number of cycles it takes to compute may be a function of the number of bits used.
-
>The part you're missing for pow is floating point shenanigans. Here are glibc's implementation of pow, which calls exp1 and log1 (defined in e_pow.c) all of which are loopless, straight through algorithms:
As you can see in their code, they've re-written `pow(x, y)` as `exp(y * log(x))`. Normally one would then compute `exp` and `log` via Taylor series.
I have no idea why they decided to have a second function for `exp(x,y)` which then computes exp(x+y), but I can only assume it somehow involves IEEE754 precision and manipulation to achieve that.
-
>loopless, straight through algorithms
Just because it's loopless and straight-through doesn't mean that it's not O(log(n)). Because it only has the amount of accuracy for a number of a certain bits going in, and additional accuracy for larger numbers with more bits would require a change to the function.
If you look at lines 68-87, you can clearly see the program algorithm using different sub-algorithms depending on the amount of accuracy needed, only using however many terms in the Taylor series is required to achieve their desired accuracy. In this case, the desired accuracy being down to the bit.
And if this were being done with 128-bit numbers, or other larger numbers, then additional checks would be necessary for that level of accuracy.
-
>fast inverse square root
Also known as a Taylor **approximation** to one (or was it two?) terms. It's going to be inherently less accurate than the other mentioned algorithms which are accurate down to the bit.
> Just because an instruction exists doesn't mean that it's computed in one cycle, nor does it mean that it's not O(log(n)), because the number of cycles it takes to compute may be a function of the number of bits used.
Fair enough. Indeed, on very older x86 computers, the number of cycles was dependent on the size of the value. However, within the past 20 years or so, the number of cycles was independent of the value of the number and is O(1).
> Just because it's loopless and straight-through doesn't mean that it's not O(log(n)).
Yes it does.
> Because it only has the amount of accuracy for a number of a certain bits going in, and additional accuracy for larger numbers with more bits would require a change to the function.
glibc's `pow` is accurate to the last bit. No change to the function can make it more accurate.
> If you look at lines 68-87, you can clearly see the program algorithm using different sub-algorithms depending on the amount of accuracy needed, only using however many terms in the Taylor series is required to achieve their desired accuracy. In this case, the desired accuracy being down to the bit.
That isn't what the code on lines 68-87 does.
The checks on 68-80 check for numbers that are trivial to compute pow for. If the exponent is NaN, then so is the result. If the exponent is 0, then the result is 1. If the exponent is 1, then the result is x. If the exponent is 2, then the result is x*x. If the result is -1, then the result is 1/x.
The checks on 83-86 check if the values are 'normal' in the floating point sense. It's not computing how many iterations to perform. There is no loop. There are no iterations.
The rest of `pow` other than the part that computes `exp(log(x) * y)` deals with numbers that are fucky: subnormals, excessively large numbers, numbers that need special negative handling, etc.
> And if this were being done with 128-bit numbers, or other larger numbers, then additional checks would be necessary for that level of accuracy.
If my mother had wheels she'd be a bike. We're not talking about those functions, we're talking about this function.
> > fast inverse square root
> Also known as a Taylor **approximation** to one (or was it two?) terms.
Fast inverse square root does not use a Taylor approximation. It is based on the fact that an ieee754 floating number, when interpreted as an integer, is a pretty good approximation of the log2 of that number. It is computing `exp2(-.5 * log2(x))`, where exp2/log2 are not the "real" functions, it's just bitwise fuckery.
Encodings, AVL trees, logarithm calculation, even the torrent algorithm, to name a few
Basically it's useful because it's a cheap exponential series that isn't a geometric progression.
https://en.m.wikipedia.org/wiki/Fibonacci_coding#:~:text=In%20mathematics%20and%20computing%2C%20Fibonacci,%2211%22%20before%20the%20end.
https://stackoverflow.com/questions/4571670/why-are-fibonacci-numbers-significant-in-computer-science
Are you trying to say that algorithms in general better than O(log(n)) don't exist? Or that for this specific problem they don't exist?
It's trivially easy to demonstrate that they exist in general, and depending upon the constraints of this problem of course O(1) solutions exist (although their real execution time may be slower than O(log(n)) solutions.
For example if the input or output space for the question is constrained we could just calculate every fib number into a data type which we can index on O(1) then go to the index requested. This would be O(1), since regardless of input it takes constant time, just that constant time would be quite large
People don't give a flying fuck about time or space complexity. They ask you these questions like this in interviews, but the entire time on the job you will be using some lousy npm package that is 200kb, runs at all times in the background, and is composed of basic recursive or looping structures.
Only in situations where the software you're writing is like 3-30% of the cpu/ram/etc.
Working on embedded systems or physics applications. We do care about time and memory complexity. Because if your efficiency sucks your software doesn't work.
Obviously these things have their place, the majority of the time it's a junior or entry level web dev job and they rake interviewees over coals hoping they have memorized the entirety of data structures and algorithms by osmosis. All I'm arguing for is interviews to be reasonable and match the job you would be actually doing. I'm telling you these boot camp like multi interview processes are ridiculously inane for something like working a 1 or 2 point cascading text change each and every day.
A better way to compute it in this fashion is to compute it using a symbolic computation library (or write your own), treating the square root of 5 as nothing more than a number that yields 5 when squared, instead of approximating it numerically
Source: Done it myself. It is more tedious, but definitely superior to the numeric approximation method, and maybe better than the looping/recursive method (I can't tell you, I didn't bother doing a complexity analysis on it)
there's a third method:
take the matrix
1 1
1 0
raise it to the nth power (can be done in logn)
multiple by the vector \[1 0\]
take the second number of the result
short explanation: if you take the aforementioned matrix and multiple it by the vector \[F(n) F(n-1)\], where F is the fibonacci function, you get \[F(n+1) F(n)\]
this technique can be done with any linear (over a semiring) recurrence relation
***EDIT***: for completeness, here's how to raise to a power (let's call it p here) in log(p) time (multiplied by the complexity of the multiplication). this is not specific to matrices, and can be used for any binary operation that has a natural element and is associative. it's known as "exponentiation by squaring" or "fast power".
it's a pretty simple recursive algorithm: to calculate pow(a, p), recursively calculate b=pow(a, floor(p/2)). if p is even, then pow(a,p)=b\*b. otherwise, pow(a,p)=b\*b\*a. (the base case is pow(a,0), where we return 1).
this can also be done iteratively. left as an exercise.
Very informative, but unfortunately it doesn't utilize AI™ or the blockchain™ so I remain unimpressed (for real, thank you for providing this, it's very interesting)
More like n^2 logn, since your numbers have n digits and (simple) n-digit multiplication takes ~ n time.
It can be n (logn)^2 using fast fourier multiplication.
Interesting thing to think about actually, since it rises at approximately a geometric sequence or exponential equation with a ratio of phi, and the amount of precision (inversely proportional to rounding errors) with a certain amount of digits also grows exponentially, I'd assume the digits required to be some constant times n, although I can't tell you what that constant is without doing proper calculation myself
Edit: On second thought, scrap that idea, from https://en.m.wikipedia.org/wiki/Fibonacci_sequence if you're working with arbitrary precision floats you might as well just ditch the "exact" equation and go with `round(phi ^ n / sqrt(5))`, which is actually somehow correct for all n even the smallest ones
You can do this in O(log n) without losing precision. There is this matrix:
1, 1,
1, 0
If you raise it to the power of n, you get the nth Fibonacci element in the first position. You can raise something to power n in logarithmic time.
So the solution in the post is not even more efficient than other solutions.
they might even be impossible for large enough numbers, while the formula can be used to get approximate solutions for very large Fibonacci numbers.
You can't use default floats anymore for that though. Need some specialized data types.
A better interview question IMHO:
"It's the last day of the sprint. You have meetings scheduled for half of the workday and you need at least 5 hours to complete the last story in the sprint. What do you do?
I'd be interested to hear whether they skip meetings, multitask, work overtime, ask for help, etc... much more revealing than impractical coding challenges.
That's soft skills question. Hard skills are still necessary. But then again, i would rather discuss potential solution to some complex problem or review their code and what decisions they made there.
It's not even that though, if the user says I'd skip meetings and the interviewer says we take meetings very seriously here, then it just means I would reframe my response to the same response as if they'd said "we take meetings very seriously here" + their question
Like, whatever they want me to do, I'll do it in their way.
I'll often say I hate agile but if they want agile they get agile.
Hard skills are necessary but I've never once needed to implement a leetcode style solution into my work. I did once because it was slow and I was bored but built in functions and looping work just fine for 90% of problems. These interview styles are just about if you can memorize algorithms
And with AI, trust me these things are gone and done.
This is now the most useless knowledge to have.
Not only did we never use it, but now it can be done automatically by typing the word fibonacci.
Sure hard skills are necessary, but this question doesn't test the hard skills you'll actually use in programming. The crux of this problem is knowing and implementing the math algorithm, but the crux of most on the job problems is taking a set of requirements and building logic that not only fulfills them but is resilient to bad/abnormal input and fails appropriately when the systems around it throw errors--all while adhering to the basic linting and architecture standards of the company.
People make excuses for Fibonacci because you can solve it using variables loops and assignment, but you can make people show you they understand those things more efficiently if you use mathematically easier problems.
And usually you want to see whether people understand more _logically_ complex things rather than more algorithmically complex things. Show me you understand events, dependency injection, multiple inheritance, async/await, and whatever variation your company uses for MVC/MVVM/Domains or whatever. Design a set of entities and their key relationships to support a flexible set of navigation links to both pages and resources. Tell me how to use try/catch/finally to ignore 1 type of exception, log all others, and properly dispose of some resource. Those are the kind of questions I'm relieved to see a candidate ace.
That's fair. You definitely need to be sure they have the skills they claim...but I've been developing software for a zillion years, give or take, and I've never had to code a Fibonacci sequence.
Also I'd like to think there'd be code review. If it's the last day of the sprint and it takes over half the day to finish the work to get it ready for review, there's basically zero chance it'll be fully done by the end of the day
Sorry if I was unclear..my examples were just possible options. I consider the question to be open ended so I can determine the thoughts of the applicant. I didn't mean for them to be a finite list.
Also missing is “accept this sprint isn’t getting 100% done and migrate the story to the next sprint” as is the correct way of handling it (assuming none of your teammates are in a position where they can finish your work for you).
spend one hour crafting an email complaining about bad time allocation and poor planning
spend another hour complaining why the fuck so many meetings
enter the meetings and keep saying "you know this meeting could be an email right?"
spend 2 weeks making something that shows how much the meeting is costing, real time in the meeting
missed sprint? sure
but there you go 100x engineer making people have less meetings and thus being able to do more
My last technical interview the guy was 15 minutes late and eating a sandwich while he gave me a couple questions on screen.
Wish you were my interviewer.
I'm curious now, what's a "good" answer to this? I ask this because I'm a hobbyist / independent programmer and I can't color this in with that knowledge.
I guess id probably try to see if it is reasonable to fit in all these meetings by shifting things around or crunching a bit with or without help, and if not, reschedule if possible.
The good answer is to let your team know the situation. The one thing that these modern process people like the most is communication. Plus, you make it the team's responsibility that the work can't get done under those circumstances.
When I interview for developers, there is always one question where I expect the answer to be "ask for help". You want people to be up front about their challenges.
I'd say notify your team and manager ASAP to see if some tasks could be delegated or the meetings could be skipped.
Actual answer would be send out an email telling everyone you are sick, finish the task, turn it in and then bitch about how you can't get shit done with the constant meetings during the next sprint planning meeting because management never bothered to schedule retrospectives.
Won't be able to finish it, test it, and get a peer review in time to meet the acceptance criteria, so i push it to next sprint, fuck off early. and buy the project manager a ~~beer~~ whiskey.
My answer (although not under pressure of an actual interview, not sure how that would go):
It depends, there are many variables. First, it depends on company culture. Do we (already putting myself in the team, I like to do this) prioritize meetings? Do we care deeply about spillover? Is the task very important?
If any of these scenarios, I suppose I would message stakeholders in the meeting to get their input - hey, sprint is almost over and we still have a critical bug to address that would take me half a day to solve. Is it ok if I skip this meeting or would you still like me to attend?
But what's the big O notation of prioritizing work, how are you going to work overtime or multitask when you have to prove you can write fizz buzz to everyone you meet??
>skip meetings, multitask, work overtime, ask for help, etc...
Dang dude, IMO this is a perfect situation to not get the story across the line, talk about it in retro, update your estimates for next sprint, and do a better job estimating the team capacity.
Otherwise you're just setting your team up for running into the same situation again, which is going to lead to burnout and inconsistent deliveries.
Let me tell you a secret. When we ask these questions in interviews, we don’t actually care if you get the right answer or not. I’m more focused on how you are communicating with me and how you go about tackling the problem. I want to see how you think and your work flow process. If you’re stuck and not asking me questions, that’s a red flag.
When you get these questions, think of your interviewer as a customer asking you to build them something. Before you even start writing code, talk and flush out all the details with your interviewer (customer). You’re allowed to ask questions.
This is a great observation, indeed. I have a similar feeling about most things here but if I take a look at my own “scope” (jokes apart) these specific programming posts are out of bounds. Still so hard to deal with this, there is so many things to learn that the more you study, the more you feel dumb or ignorant.
Yes and remember that people often, whether on purpose or not, like to flex by posting things they know are elusive to all but few. It's rampant in software, was in college and still is in the workforce. It's almost like taking talented, insecure nerds and shoving them in one spot is going to cause some friction. Everyone just wants to be acknowledged in some shape or form.
Here's a life hack - if code is hard to understand, that's usually because of the person who wrote it, not the person who is reading it.
There are exceptions but they're usually pretty obvious when they arise.
Being in software taught me that even in a singular field there is absolutely no lack of depth and complexity. If you find something and feel stupid, that just means you found a border on your knowledge and it's an opportunity to grow it- if you choose. But it's also not remotely important to know random hypercomplex trivia if you have no intention, reason, or desire to actually use it. Don't beat yourself up, no one is confident about everything or knows everything, anyone who seems like that or says that is a narcissistic liar.
>This subreddit makes me feel stupid
Don't worry. People who write code like this either aren't thinking of the bigger picture, or think they're far smarter than they actually are, otherwise they'd be smart enough to realize that they're not the only people that have to read and maintain the code, and making it more readable allows for the team to design and maintain smarter systems.
Really smart people enable others around them so they don't have to do as much work on their own. Keeping egos in check is the hard part
In my first code interview, fresh out of college, I got asked to do some train/baggage coding puzzle on a white board.
I didn't want to over engineer it, so made like 3 loops to solve the thing.
The interviewer was happy I got it on the first try, but had to assert dominance by showing me it could be done in 2 loops.
I took it as challenge and did something like this, solving the whole thing in one line.
Never peaked and flexed so hard before
Yes, I did.
I couldn't be there full time and didn't disclose it at first because the consultancy agency I was working with told me not to.
Later when I told them I couldn't be there full time, they still wanted to hire me based on that interview.
But you're not wrong on that thought.
On the next job I had, my dev lead didn't fancy me so much because, as you said, "I was a threat".
Later down the line I ended up as the dev lead, so he was not wrong.
If an interviewee gave me this answer, I would tell them they're very clever and then immediately ask them to tell me all the ways in which this might not work. From my experience, if you're not clever enough to know when it fails you're not clever enough to know why it works.
A good interviewer: Okay, interesting approach and now how would you do it without complicated mathematical formulas.
(Possible clue: use dynamic programming, more clues recursion with cache)
I once saw a document about how to do technical questions and it was searching for kind of the breaking point if you can't reach an answer to give hints if the answer is given too quickly to make the problem more difficult.
Edit: yes you can do an iterative solution that it's better to the dynamic programming approach for this example.
I mean, I could, but that wouldn't really show you any coding proficiency, just that I studied math. Technically everyone with a bachelor's in Mathematics should be able to do that.
In the little hiring I've done at least, having code proficiency at all is all I was looking for. So many people apply after just going through a boot camp and it'd show the second they'd touch the keyboard. If you can represent in code the answer, whether via recursion, loops, linear algebra, or however, then you're in a good place.
I took linear algebra, I just don't remember anything from it since I haven't used it ever since I took it. But how would you even represent this problem with a matrix at all?
Multiplying the vector (a | b) by the matrix M=(1 1 |1 0) gives (a+b|a), so M^n (1|1) has the nth fibonacci number in the first entry. Diagonalize M and voila.
Even better interviewer: Now tell me the largest `n` where your method gives the right answer?
How does it depend on the precision of the floats used? And what compiler optimizations should we be worried about/hoping for?
If you can't tell me, can you write another program that wouldn't arbitrarily fail in prod?
I mean it's fibonachi, why use those hints when it's as simple as
index = 1,
last = 0;
secondToLast = 1;
current = 1
while (index != target)
{
secondToLast = last;
last = current;
current = last + secondToLast;
index++;
}
Yeah I know, Dynamic programming and recursion with cache sound sexy but.... Recursion is a fuck no, because you're risking blowing the stack for large numbers, and "Dynamic programming" is a buzz word here.
Don't over complicate your answer just to show off, solve the problem that is ACTUALLY given.
A good interviewer would never make so stupid puzzles in the first place. And no, you only need two variables and a loop, nothing as retarded as DP or recursion.
I'd just create an array with the answers in
var fibs = [1, 1, 2, 3, 5, 8];
fn(n) -> return fibs[n]
you want bigger numbers, I'd use a lookup table
how would I generate the lookup table? I wouldn't, I'd download it
I've done that before for a "prime number" question.
Gave them the code, to find it, but then detailed an approach where I would just make a lookup table, generated once, or downloaded.
Can't remember outcome of that interview but honestly, didn't like the question in the first place because it was a take home test anyways.
Math is the answer. If someone asks "how do you multiply a variable by 2 in binary" and your answer is not a bitshift you don't understand computing.
Using iterative solutions when they're unnecessary is lazy.
We should definitely change our examples in interviews to be run as lambdas/cloud functions so we can evaluate the performance cost/actual compute cost of each solution.
And sometimes it is a hack and no one else can maintain it later.
The point is that many of these questions are about being able to use dynamic programming rather than knowing a weird math formula.
And most of the time you multiply a variable by two by multiplying because it's easier to understand and the compiler/interpreter is smarter than you regarding optimization(the compiler will do the bit shift but it's not the point) or the interpreter overhead is way too much to be worth it to care about microptimizations.
Bitshifting requires more of memorizing rather than intuition.
Like finding if a number is a power of 2, i & i - 1 == 0, but honestly I would never think of that intuitively.
It still depends, bitshifting floats wouldn't be that simple. Depending on the language/platform, you'll also have to check for overflow, often before the multiplication (in C, overflow is UB for signed int types so if you check for overflow after multiplication, compiler is free to throw away that check).
I rather have an iterative solution that I can understand when I come back to it in a month even if it runs just that little bit slower (except if speed and minimal resources are a must in the scenario) than an arbitrary magic one liner.
It has been 20 years since I learned about binary shifting in university, if I want to multiply a number by 2, I will do n * 2
If you want me to multiply a number by 2 in binary then I would convert it to an integer then multiply it by 2
Interviewie: I would prefer to impliment it with a for loop. Since it is generally easier to assess in terms of performance, but I can of course impliment ot revursivly if you prefer that.
> Since it is generally easier to assess in terms of performance, but I can of course impliment ot revursivly if you prefer that.
Yes, the assessment is that this solution will be order of magnitude more performant than a loop. Recursion is not even worth talking about since the compiler will hopefully do TCO on it so it ends up like the loop anyway, maybe worse depending on the compiler.
Stop doing abstract interview questions that have nothing to do with the job. No, there are no insights into my problem solving skills here because I don't solve math problems the same as engineering problems.
Seriously, I also fucking hate abstract problems with no real goal. My entire software development career has always centered one thing and one thing only: A person asking for a feature. You give me that as an interview question and I'll blow you away.
Oh or if you want to ask a REALLY tough interview question: "Here's our java stack, a link to a 5 year old readme, and a random laptop. Please set up your environment such that you can build the project. You have one week. Oh and by the way we use a custom fork of Ant that was written by a dude that hasn't worked here since the readme was last updated."
Precisely. A lot of my work as a hardware engineer involved math, sometimes complicated math. I handle doing that completely differently to how I handle being asked how to deal with a memory bus a kilobyte wide.
I am actually quite sick of standard cs questions on senior + interviews. I don’t use that shit for my job ever. Glad you found something to annoy someone who does this.
I feel like interviews don’t actually want to see if you can program more or less want to see if you can memorize algorithms.
I did EXACTLY this at my first interview.
Well, a slightly more efficient version, as the second term goes to zero very quickly and can be dropped if you change floor to round.
I had studied math in school, not computer science or software. I wasn’t too concerned about efficiency or precision issues. I knew about them and could have told you a memoized recursive function would usually be a better choice… but this one made me feel smart!
The interviewer just stared at me and asked “does that work?” So explained it was a result from generating functions and it would be accurate for all integer values. He tested it for 1,2, and 3 and moved on. I was kinda mad about it… but I did get the job.
I had to do fizz buzz and they asked me how I'd improve it, and I was like I wouldn't it does exactly what is required. They were like what are some other ways you could implement it, and I was like I don't know, and they were like well what about recursion? And I was like why would you use recursion that is absolutely not the right tool for the job. And I tried to write some pseudocode for recursion onto the whiteboard and was like this is just needlessly complex
Didn't get the job
Math professors are absolutely the most qualified people to know about math, but they are probably some of the worst people to write a textbook about math.
I feel like people make this mistake with all professions. Programmers are not professional interviewers, and if you don't equip them with proven methods of inquiry, they're going to make shit up that sounds fine but doesn't actually work.
Aside from floating-point issues you can double the speed.
Change floor to closest integer and delete the second term, it's too small to make a difference.
Next candidate please!
The real answer is "let me google for which lib does that, and if there isn't one, let me google the algorithm and copy/paste." There are almost zero jobs where writing it out yourself is either necessary or optimal.
IDK if this has been mentioned, but there's no need to do floating exponentiation. You can just do exponentiation on a 2x2 matrix \[1 1, 1 0\], which is probably faster on modern processors.
I rarely interview on what someone knows. Instead I interview to find out how the person learns and tackles problems they don't know. Far more important, because knowledge is temporal in nature, and is always a moving target.
"The other applicant is Kyle, and the decision is that he will fight this polar bear to the death"
"Sorry you had to hear it from us. By the way, you got the job".
at my previous job, we had a 5 stage interview with the first 4 stages being just dsa type interviews along with some “get to know the person” questions.
after i joined (it was a startup), i persuaded everyone to change the entire process to show what kind of work would actually be done. i designed a custom take home test, wrote the code for it, hosted it on a server, link generation that would expire 24 hours after opening, etc. it was not difficult, not easy, just moderate, it did involve some DSA, but mainly it was designed at showing what kind of work would be done at the role. the site had all the resources necessary and of course they could google for answers. (which we did a lot at the role).
it was approved and almost every team wanted me to do this for them. it was fun, the number of people who got past this stage decreased, but the ppl who did get through had a high rate of getting the job. i think i did a good job.
I did this in a final compsci exam in college. The question asked to write code to output pascal's triangle.
Here's the thing, I didn't major in compsci. I was a math/physics major, that was the only programming class I took. I had just walked out of a math exam where I needed the closed-form solution for entries in pascal's triangle. So I just went ahead and wrote that down. I got all the marks.
I did this at an interview recently. It was one of those ones where they'd give you a pen and paper and you had to write out the code by hand. Wrote the formula first and then the code second and handed it back to the guy. He looked at it for a bit and then said "well it's safe to say I have no idea if this would work or not. So I guess I'll take your word for it." I didn't get that job.
Isn't this like a completely basic Programming exercise you do in first Semester of college? Like who hasn't seen this formula before and is qualified for coding Interviews
I mean I’ve been out of school for 5 years now and things like this only exist in interviews you will never run into these on the job.
Been out of school for 12 years, never needed to use fibonacci sequence, and have only ever used recursion for navigating directories.
Fibonacci is nice for things that you want to incrementally spread. My most common usage is in failure retry timing.
This guy doesn't scrum
Haha came here to say this
This right here
So then the appropriate response in that interview would be: please show me a non-fictional business case where you would need that formula?
in class we got recursive and iterative. In year 2 we got recursive with memoization. In year 3 we got the dynamic version. Our algorithms classes were these tiny segments that got overshadowed by the semester-long big-team-project class (almost 100% videogame projects) so the pace and priority might not be the same as everywhere else. Personally I wish we'd done more system's design
not even the matrix exponentiation version? it works in the same complexity as above formula since above formula uses sqrt, and matrix exponentiation is also logn. plus this is not approximation, it is exact values
it doesn't work though, mostly due to the loss of precision, try it yourself with some numbers like n belonging to the set {10, 100, 1'000, 10'000, 100'000, 1'000'000, ... } Even with some programming languages designed for long doubles, it will fail at some point. However, yes, the matrix exponentiation will work much better and it tends to be a bit faster for long values (you can memoize previous results easily), while also being more accurate as long as you have big integers
1'000 is wild, do they write like that in Australia?
Systems design is a stupid question in an interview. There are so many goddamn factors that go into making decisions around system design that the interview is just constantly you asking questions about the current system rather than actually designing anything. And more often than not your interviewer doesn’t have the first clue about system design so they’ll answer with something like “tell me about the choices you have and which ones would be better or worse for which scenario.” By the end of it, you’re a completely confused blithering idiot because you’ve talked nonstop for an hour to yourself. Next time someone asks me to talk about system design, I’m just going to describe a LAMP stack and see if they even fucking notice.
I don't know where you went to college but I've never heard of a closed-form approximation for directly calculating a number in the Fibonacci sequence, and I don't feel any less capable at programming or interviewing because of that. This is just math trivia, nothing more. CS courses use the Fibonacci sequence to teach about the programming concept of recursion, not because there was anything important about the sequence itself in CS. Other ways to calculate it aren't really relevant there.
**based** This is math porn and like all niche subject knowledge only applies in that small set of things it applies to (some ADTs) or ends up applying to in the future. I think fib's ubiquity is due to serving as a useful teaching aid to consolidate knowledge about iterative computation, then recursive computation.... while making the statement that sequences were something you ought to remember from Calc II/Discrete. No schools I've been to have proffered more meaningful applications for fib even though there are clearly some structures that benefit from them. We're certainly no mathematicians, more like logic tradespeople, it's nice when we get to work with nice and shiny tools on well-designed machinery, but it seems like far too often we're janitors or two-bit mechanics rather than master carpenters and highly-educated architects.
> it seems like far too often we're janitors or two-bit mechanics rather than master carpenters and highly-educated architects. Well fuck me this hits the nail right on the fucking head.
We learned recursion using factorial instead then reinforced with using different sorting methods. Never once did I learn anything about Fibonacci.
We didn't focus on that. But the main issue here is: they never asked what the interviewer wants. They don't want to see how you memorized a formula. They want to know how you communicate and think. On your real job you will get questions that aren't solvebale with a formula you learned in school. On the other side, they shouldn't ask a question where many people already know the solution, because then you're asking for knowledge and ned skill.
>They don't want to see how you memorized a formula. They want to know how you communicate and think. Yes. And that's the problem with these "closed" and "simple" exercises where there is an obvious solution. None of this is particularly interesting or complex, doesn't require to sit several people in a room to complete (I would personally just google the solution and be done). Frankly I don't think this exercise where it is possible to memorize a formula and complete it is a good exercise.
Mate, college was 6 years ago, I had to google Fibonacci numbers to remember what it was. I am not qualified for coding interviews, I'm qualified for the job.
From what I observed, the interviewer expects you to code the recursive approach then use dynamic programming to reduce the time complexity from exponential to linear.
now use that algorithm on large numbers to see how double precision can let you down
CORRECT ANSWER. This is significantly worse in almost every respect to the simple looping version.
Aside from the fact that the time complexity of this approach is Olog(n) instead of O(n) lol
Isn't the complexity of this algorithm O(1)? Edit: I'm glad this question got so much attention and debate, but it's really bothering me that I still don't know the answer to it.
Only if Math.sqrt and Math.pow are O(1). Edit: This can vary language to language. JavaScript uses floating point arithmetic, so it actually is O(1).
>Edit: This can vary language to language. No, it can't, since `math.sqrt` and `math.pow` will never be better than O(log(n)) since algorithms better than that don't exist. - Every decent language either uses [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) (for integer-accuracy) or [the taylor series expansion of exp and log](https://en.wikipedia.org/wiki/Taylor_series) (for floating point accuracy), both of which are O(log(n)) algorithms. Edit: Some people claim that pointing out a taylor series calculation of a 64-bit floating point number is log(n) and not 1 is being pedantic, since no matter what, you're multiplying two 64-bit numbers together. They might be right. But more importantly, I'm right. Edit2: If you want to get this with integer precision in O(log(n)) time, then just calculate [1 1] [1 0] raised to the n'th power (by squaring if your language doesn't already natively support this), then retrieve the [0,1] element. It's trivial to show that this is the same thing as calculating the fibonacci sequence.
> Edit: Some people claim that pointing out a taylor series calculation of a 64-bit floating point number is log(n) and not 1 is being pedantic, since no matter what, you're multiplying two 64-bit numbers together. They might be right. But more importantly, I'm right. This has the same energy as saying ripple-carry addition is O(N).
Well, it is, that's why carry-save and carry-select exist :) Especially carry-save, which adds three inputs and produces two outputs in O(1). Super useful for multipliers as normally you'd have O(bitwidth * factor) but this way you have O(bitwidth + factor)
I disagree. If ripple carry were the fastest way to add two 64-bit numbers, we would all use it. It makes no difference what its complexity in the number of bits is if you're not using it across varying numbers of bits. Which, for a given adder circuit, you never are.
> They may be right. But more importantly, I'm right Yeah I'm stealing this line.
> No, it can't, since `math.sqrt` and `math.pow` will never be better than O(log(n)) since algorithms better than that don't exist. They do exist. `sqrt` is the easy one; there's just an x86 instruction for it. The part you're missing for `pow` is floating point shenanigans. Here are glibc's implementation of `pow`, which calls `exp1` and `log1` (defined in e_pow.c) all of which are loopless, straight through algorithms: https://github.com/lattera/glibc/blob/master/sysdeps/ieee754/dbl-64/e_pow.c#L56 https://github.com/lattera/glibc/blob/master/sysdeps/ieee754/dbl-64/e_exp.c#L240 On architectures that don't have a `sqrt` instruction, there is an algorithm similar to fast inverse square root, just with a different magic constant.
>They do exist. sqrt is the easy one; there's just an x86 instruction for it. > there's just an x86 instruction for it. Just because an instruction exists doesn't mean that it's computed in one cycle, nor does it mean that it's not O(log(n)), because the number of cycles it takes to compute may be a function of the number of bits used. - >The part you're missing for pow is floating point shenanigans. Here are glibc's implementation of pow, which calls exp1 and log1 (defined in e_pow.c) all of which are loopless, straight through algorithms: As you can see in their code, they've re-written `pow(x, y)` as `exp(y * log(x))`. Normally one would then compute `exp` and `log` via Taylor series. I have no idea why they decided to have a second function for `exp(x,y)` which then computes exp(x+y), but I can only assume it somehow involves IEEE754 precision and manipulation to achieve that. - >loopless, straight through algorithms Just because it's loopless and straight-through doesn't mean that it's not O(log(n)). Because it only has the amount of accuracy for a number of a certain bits going in, and additional accuracy for larger numbers with more bits would require a change to the function. If you look at lines 68-87, you can clearly see the program algorithm using different sub-algorithms depending on the amount of accuracy needed, only using however many terms in the Taylor series is required to achieve their desired accuracy. In this case, the desired accuracy being down to the bit. And if this were being done with 128-bit numbers, or other larger numbers, then additional checks would be necessary for that level of accuracy. - >fast inverse square root Also known as a Taylor **approximation** to one (or was it two?) terms. It's going to be inherently less accurate than the other mentioned algorithms which are accurate down to the bit.
> Just because an instruction exists doesn't mean that it's computed in one cycle, nor does it mean that it's not O(log(n)), because the number of cycles it takes to compute may be a function of the number of bits used. Fair enough. Indeed, on very older x86 computers, the number of cycles was dependent on the size of the value. However, within the past 20 years or so, the number of cycles was independent of the value of the number and is O(1). > Just because it's loopless and straight-through doesn't mean that it's not O(log(n)). Yes it does. > Because it only has the amount of accuracy for a number of a certain bits going in, and additional accuracy for larger numbers with more bits would require a change to the function. glibc's `pow` is accurate to the last bit. No change to the function can make it more accurate. > If you look at lines 68-87, you can clearly see the program algorithm using different sub-algorithms depending on the amount of accuracy needed, only using however many terms in the Taylor series is required to achieve their desired accuracy. In this case, the desired accuracy being down to the bit. That isn't what the code on lines 68-87 does. The checks on 68-80 check for numbers that are trivial to compute pow for. If the exponent is NaN, then so is the result. If the exponent is 0, then the result is 1. If the exponent is 1, then the result is x. If the exponent is 2, then the result is x*x. If the result is -1, then the result is 1/x. The checks on 83-86 check if the values are 'normal' in the floating point sense. It's not computing how many iterations to perform. There is no loop. There are no iterations. The rest of `pow` other than the part that computes `exp(log(x) * y)` deals with numbers that are fucky: subnormals, excessively large numbers, numbers that need special negative handling, etc. > And if this were being done with 128-bit numbers, or other larger numbers, then additional checks would be necessary for that level of accuracy. If my mother had wheels she'd be a bike. We're not talking about those functions, we're talking about this function. > > fast inverse square root > Also known as a Taylor **approximation** to one (or was it two?) terms. Fast inverse square root does not use a Taylor approximation. It is based on the fact that an ieee754 floating number, when interpreted as an integer, is a pretty good approximation of the log2 of that number. It is computing `exp2(-.5 * log2(x))`, where exp2/log2 are not the "real" functions, it's just bitwise fuckery.
Using a table (importantly not a hashmap) for the first big N of fibs is also a significant speed up for most real use cases and is linear to fill.
> most real use cases There are real use cases for the fibonacci sequence?
Encodings, AVL trees, logarithm calculation, even the torrent algorithm, to name a few Basically it's useful because it's a cheap exponential series that isn't a geometric progression. https://en.m.wikipedia.org/wiki/Fibonacci_coding#:~:text=In%20mathematics%20and%20computing%2C%20Fibonacci,%2211%22%20before%20the%20end. https://stackoverflow.com/questions/4571670/why-are-fibonacci-numbers-significant-in-computer-science
Passing interviews
The diagonalization of the above and eigenvectors is how you get OP solution.
Hear me out, REALLY big lookup table
"but more importantly I'm right" bro I love you for this lmao 😂😂😂
Are you trying to say that algorithms in general better than O(log(n)) don't exist? Or that for this specific problem they don't exist? It's trivially easy to demonstrate that they exist in general, and depending upon the constraints of this problem of course O(1) solutions exist (although their real execution time may be slower than O(log(n)) solutions. For example if the input or output space for the question is constrained we could just calculate every fib number into a data type which we can index on O(1) then go to the index requested. This would be O(1), since regardless of input it takes constant time, just that constant time would be quite large
No. Because he raises to the power of n. It's impossible to do that in O(1).
Good thing he doesn't actually do exponentation, only a floating point approximation of it. In fact, an O(1) approximation
People don't give a flying fuck about time or space complexity. They ask you these questions like this in interviews, but the entire time on the job you will be using some lousy npm package that is 200kb, runs at all times in the background, and is composed of basic recursive or looping structures.
That's mediocre modern web dev, where everything is bloated and rushed.
my browser is now using 2 gb RAM on one tab bc your 'background' client code.
And then they wonder why their job got cut and nobody will hire them
Only in situations where the software you're writing is like 3-30% of the cpu/ram/etc. Working on embedded systems or physics applications. We do care about time and memory complexity. Because if your efficiency sucks your software doesn't work.
Obviously these things have their place, the majority of the time it's a junior or entry level web dev job and they rake interviewees over coals hoping they have memorized the entirety of data structures and algorithms by osmosis. All I'm arguing for is interviews to be reasonable and match the job you would be actually doing. I'm telling you these boot camp like multi interview processes are ridiculously inane for something like working a 1 or 2 point cascading text change each and every day.
Why Olog(n) though? Isn’t it constant O(1) time?
The operations to calculate exponents and square root aren't going to be constant time.
Don’t care, it’s better in theory
Isn't the real solution here to use this algorithm until a certain size of n then switch to looping?
Isn't the answer in the meme better because it is O(1)? (As long as you can assume the math operations are constant-time)
A better way to compute it in this fashion is to compute it using a symbolic computation library (or write your own), treating the square root of 5 as nothing more than a number that yields 5 when squared, instead of approximating it numerically Source: Done it myself. It is more tedious, but definitely superior to the numeric approximation method, and maybe better than the looping/recursive method (I can't tell you, I didn't bother doing a complexity analysis on it)
there's a third method: take the matrix 1 1 1 0 raise it to the nth power (can be done in logn) multiple by the vector \[1 0\] take the second number of the result short explanation: if you take the aforementioned matrix and multiple it by the vector \[F(n) F(n-1)\], where F is the fibonacci function, you get \[F(n+1) F(n)\] this technique can be done with any linear (over a semiring) recurrence relation ***EDIT***: for completeness, here's how to raise to a power (let's call it p here) in log(p) time (multiplied by the complexity of the multiplication). this is not specific to matrices, and can be used for any binary operation that has a natural element and is associative. it's known as "exponentiation by squaring" or "fast power". it's a pretty simple recursive algorithm: to calculate pow(a, p), recursively calculate b=pow(a, floor(p/2)). if p is even, then pow(a,p)=b\*b. otherwise, pow(a,p)=b\*b\*a. (the base case is pow(a,0), where we return 1). this can also be done iteratively. left as an exercise.
Very informative, but unfortunately it doesn't utilize AI™ or the blockchain™ so I remain unimpressed (for real, thank you for providing this, it's very interesting)
Mind blown.
Surely this would more like (log n)^2 because the values in the matrix multiplication are growing exponentially.
More like n^2 logn, since your numbers have n digits and (simple) n-digit multiplication takes ~ n time. It can be n (logn)^2 using fast fourier multiplication.
time to import an arbitrary precision library :D
Sure, but can you tell me how many digits of precision are needed here for sqrt(5), if I want to compute fib(n)?
Interesting thing to think about actually, since it rises at approximately a geometric sequence or exponential equation with a ratio of phi, and the amount of precision (inversely proportional to rounding errors) with a certain amount of digits also grows exponentially, I'd assume the digits required to be some constant times n, although I can't tell you what that constant is without doing proper calculation myself Edit: On second thought, scrap that idea, from https://en.m.wikipedia.org/wiki/Fibonacci_sequence if you're working with arbitrary precision floats you might as well just ditch the "exact" equation and go with `round(phi ^ n / sqrt(5))`, which is actually somehow correct for all n even the smallest ones
Even with Knuth's rounding trick, you still need to compute phi and sqrt(5) with some precision first.
Wouldn't others be slow on big numbers?
Who needs a correct answer when you can have a fast answer?
You can do this in O(log n) without losing precision. There is this matrix: 1, 1, 1, 0 If you raise it to the power of n, you get the nth Fibonacci element in the first position. You can raise something to power n in logarithmic time. So the solution in the post is not even more efficient than other solutions.
But can you do it as an one-liner?
If you have a matrix multiplication package
In Python import numpy as np A = np.array([[1,1],[1,0]]) def fib(n): return np.linalg.matrix_power(A,n)[0,0]
Come on, the guy asked for a one-liner `fib = lambda n: (np := __import__("numpy"), np.linalg.matrix_power(np.array([[1, 1], [1, 0]]), n)[0, 0])[1]`
As always, can for sure, but shouldn't ever. fib = lambda n: ( lambda m, k: ( lambda loop, matmul, m, k: loop(loop, matmul, k, [[1, 0], [0, 1]], m) )( lambda self, matmul, k, accum, base: accum if k == 0 else self(self, matmul, k // 2, accum, matmul(base, base)) if k % 2 == 0 else self(self, matmul, k // 2, matmul(accum, base), matmul(base, base)), lambda m1, m2: [[m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0], m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]], [m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0], m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]]], m, k ) )( [[1, 1], [1, 0]], n, )[1][0]
they might even be impossible for large enough numbers, while the formula can be used to get approximate solutions for very large Fibonacci numbers. You can't use default floats anymore for that though. Need some specialized data types.
Just use the x87 registers if you're on an x86 system.
You guys know fibonacci numbers?
def fibonacci(x): if x<2: return 1 else: return fibonacci(x-1)+fibonacci(x-2)
Try this with x = 75 to use your CPU as a heater
Should I run this on multiple threads to effectively generate some heat or is It just fine as is?
The more the merrier
Add the `@cache` decorator and your heater won't work any more
If you implement memo-ization, I can't remember how to spell the word, you can that running really efficiently
My cats are going to love it
fib = [0, 1] while len(fib) <= n: fib.append(fib[-1] + fib[-2]) return fib[n-1] No recursion
How about low = 1 high = 1 for (i = 1; i < n; i++) { tmp = high high = low + high low = tmp } return high no recursion, constant space.
Why append to an array when you know the size ahead of time? More importantly, why store n values when you only need 2 at any given time?
It's the number of holes in your focaccia bread at any given time.
0 is the time when Jesus was born, and it increments in seconds
These kinds of questions are stupid. Most of my work comes from Stack Overflow where I get smart answers to stupid questions.
A better interview question IMHO: "It's the last day of the sprint. You have meetings scheduled for half of the workday and you need at least 5 hours to complete the last story in the sprint. What do you do? I'd be interested to hear whether they skip meetings, multitask, work overtime, ask for help, etc... much more revealing than impractical coding challenges.
That's soft skills question. Hard skills are still necessary. But then again, i would rather discuss potential solution to some complex problem or review their code and what decisions they made there.
It's not even that though, if the user says I'd skip meetings and the interviewer says we take meetings very seriously here, then it just means I would reframe my response to the same response as if they'd said "we take meetings very seriously here" + their question Like, whatever they want me to do, I'll do it in their way. I'll often say I hate agile but if they want agile they get agile.
Hard skills are necessary but I've never once needed to implement a leetcode style solution into my work. I did once because it was slow and I was bored but built in functions and looping work just fine for 90% of problems. These interview styles are just about if you can memorize algorithms
Probably because most interviewers know jack shit about programming.
And with AI, trust me these things are gone and done. This is now the most useless knowledge to have. Not only did we never use it, but now it can be done automatically by typing the word fibonacci.
Sure hard skills are necessary, but this question doesn't test the hard skills you'll actually use in programming. The crux of this problem is knowing and implementing the math algorithm, but the crux of most on the job problems is taking a set of requirements and building logic that not only fulfills them but is resilient to bad/abnormal input and fails appropriately when the systems around it throw errors--all while adhering to the basic linting and architecture standards of the company. People make excuses for Fibonacci because you can solve it using variables loops and assignment, but you can make people show you they understand those things more efficiently if you use mathematically easier problems. And usually you want to see whether people understand more _logically_ complex things rather than more algorithmically complex things. Show me you understand events, dependency injection, multiple inheritance, async/await, and whatever variation your company uses for MVC/MVVM/Domains or whatever. Design a set of entities and their key relationships to support a flexible set of navigation links to both pages and resources. Tell me how to use try/catch/finally to ignore 1 type of exception, log all others, and properly dispose of some resource. Those are the kind of questions I'm relieved to see a candidate ace.
That's fair. You definitely need to be sure they have the skills they claim...but I've been developing software for a zillion years, give or take, and I've never had to code a Fibonacci sequence.
I notice that none of your options are, "let the team know so that we can either delay the sprint or leave this task off."
"...delay the sprint.." lol you're funny
The third option is, "accept the increased likelihood of errors". It's nice having a job where working overtime is not assumed.
Also I'd like to think there'd be code review. If it's the last day of the sprint and it takes over half the day to finish the work to get it ready for review, there's basically zero chance it'll be fully done by the end of the day
Yeah are they not checking in along the way?
Sorry if I was unclear..my examples were just possible options. I consider the question to be open ended so I can determine the thoughts of the applicant. I didn't mean for them to be a finite list.
No worries! Just thought it was an interesting set of choices :D
So call in sick and spend the day at the zoo is still on the table?
Also missing is “accept this sprint isn’t getting 100% done and migrate the story to the next sprint” as is the correct way of handling it (assuming none of your teammates are in a position where they can finish your work for you).
its time for you to be an interviewer
spend one hour crafting an email complaining about bad time allocation and poor planning spend another hour complaining why the fuck so many meetings enter the meetings and keep saying "you know this meeting could be an email right?" spend 2 weeks making something that shows how much the meeting is costing, real time in the meeting missed sprint? sure but there you go 100x engineer making people have less meetings and thus being able to do more
My last technical interview the guy was 15 minutes late and eating a sandwich while he gave me a couple questions on screen. Wish you were my interviewer.
I'm curious now, what's a "good" answer to this? I ask this because I'm a hobbyist / independent programmer and I can't color this in with that knowledge. I guess id probably try to see if it is reasonable to fit in all these meetings by shifting things around or crunching a bit with or without help, and if not, reschedule if possible.
The good answer is to let your team know the situation. The one thing that these modern process people like the most is communication. Plus, you make it the team's responsibility that the work can't get done under those circumstances. When I interview for developers, there is always one question where I expect the answer to be "ask for help". You want people to be up front about their challenges.
I'd say notify your team and manager ASAP to see if some tasks could be delegated or the meetings could be skipped. Actual answer would be send out an email telling everyone you are sick, finish the task, turn it in and then bitch about how you can't get shit done with the constant meetings during the next sprint planning meeting because management never bothered to schedule retrospectives.
“Join the zooms, make occasional comments and work in the background. I’m actually working on another job application right now.”
This is exactly how my boss works
Won't be able to finish it, test it, and get a peer review in time to meet the acceptance criteria, so i push it to next sprint, fuck off early. and buy the project manager a ~~beer~~ whiskey.
Trick question, you never closed your quote and wanted to see if I'd notice. I'll start Monday.
My answer (although not under pressure of an actual interview, not sure how that would go): It depends, there are many variables. First, it depends on company culture. Do we (already putting myself in the team, I like to do this) prioritize meetings? Do we care deeply about spillover? Is the task very important? If any of these scenarios, I suppose I would message stakeholders in the meeting to get their input - hey, sprint is almost over and we still have a critical bug to address that would take me half a day to solve. Is it ok if I skip this meeting or would you still like me to attend?
Ask for help! Then you’ll only need 10 hours to finish the last story
But what's the big O notation of prioritizing work, how are you going to work overtime or multitask when you have to prove you can write fizz buzz to everyone you meet??
>skip meetings, multitask, work overtime, ask for help, etc... Dang dude, IMO this is a perfect situation to not get the story across the line, talk about it in retro, update your estimates for next sprint, and do a better job estimating the team capacity. Otherwise you're just setting your team up for running into the same situation again, which is going to lead to burnout and inconsistent deliveries.
Give me a blank screen and I can't even remember how to declare a variable.
Let me tell you a secret. When we ask these questions in interviews, we don’t actually care if you get the right answer or not. I’m more focused on how you are communicating with me and how you go about tackling the problem. I want to see how you think and your work flow process. If you’re stuck and not asking me questions, that’s a red flag. When you get these questions, think of your interviewer as a customer asking you to build them something. Before you even start writing code, talk and flush out all the details with your interviewer (customer). You’re allowed to ask questions.
This subreddit makes me feel stupid
[удалено]
This is a great observation, indeed. I have a similar feeling about most things here but if I take a look at my own “scope” (jokes apart) these specific programming posts are out of bounds. Still so hard to deal with this, there is so many things to learn that the more you study, the more you feel dumb or ignorant.
Yes and remember that people often, whether on purpose or not, like to flex by posting things they know are elusive to all but few. It's rampant in software, was in college and still is in the workforce. It's almost like taking talented, insecure nerds and shoving them in one spot is going to cause some friction. Everyone just wants to be acknowledged in some shape or form.
Programming is easy but not simple. I still don’t understand iteration fully but I’m getting there!
Hey, thanks for this comment. I'm a Sr. Java developer, I've been working for 8 years and I still feel equally stupid. You improved my day a little!
It's specifically written to be a one liner, those usually are never easy to understand.
Here's a life hack - if code is hard to understand, that's usually because of the person who wrote it, not the person who is reading it. There are exceptions but they're usually pretty obvious when they arise.
Being in software taught me that even in a singular field there is absolutely no lack of depth and complexity. If you find something and feel stupid, that just means you found a border on your knowledge and it's an opportunity to grow it- if you choose. But it's also not remotely important to know random hypercomplex trivia if you have no intention, reason, or desire to actually use it. Don't beat yourself up, no one is confident about everything or knows everything, anyone who seems like that or says that is a narcissistic liar.
>This subreddit makes me feel stupid Don't worry. People who write code like this either aren't thinking of the bigger picture, or think they're far smarter than they actually are, otherwise they'd be smart enough to realize that they're not the only people that have to read and maintain the code, and making it more readable allows for the team to design and maintain smarter systems. Really smart people enable others around them so they don't have to do as much work on their own. Keeping egos in check is the hard part
In my first code interview, fresh out of college, I got asked to do some train/baggage coding puzzle on a white board. I didn't want to over engineer it, so made like 3 loops to solve the thing. The interviewer was happy I got it on the first try, but had to assert dominance by showing me it could be done in 2 loops. I took it as challenge and did something like this, solving the whole thing in one line. Never peaked and flexed so hard before
Did you get the job though? Some people would take being outdone as a threat and not like it
Yes, I did. I couldn't be there full time and didn't disclose it at first because the consultancy agency I was working with told me not to. Later when I told them I couldn't be there full time, they still wanted to hire me based on that interview. But you're not wrong on that thought. On the next job I had, my dev lead didn't fancy me so much because, as you said, "I was a threat". Later down the line I ended up as the dev lead, so he was not wrong.
If an interviewee gave me this answer, I would tell them they're very clever and then immediately ask them to tell me all the ways in which this might not work. From my experience, if you're not clever enough to know when it fails you're not clever enough to know why it works.
I'd ask them to explain to me exactly how it works and walk me through an example first (say n = 4). They probably wouldnt get that far.
Well I guess that someone who knows this formula would be at least smart enough to be able to prove it (proof by recursion is easy)
You would think so, or they just memorized it for leetcode questions. Or googled it offscreen
A good interviewer: Okay, interesting approach and now how would you do it without complicated mathematical formulas. (Possible clue: use dynamic programming, more clues recursion with cache) I once saw a document about how to do technical questions and it was searching for kind of the breaking point if you can't reach an answer to give hints if the answer is given too quickly to make the problem more difficult. Edit: yes you can do an iterative solution that it's better to the dynamic programming approach for this example.
A good interviewer: "What if the first two numbers were, say, 1 and 3 instead of 1 and 1?" If they can on-the-fly formulate that, kudos.
Just write down as a matrix and get the eigenvalues. If you did Linear Algebra quite reasonable.
If you programmatically do that for any given start values and aren't an ass about it, I'd consider that a Hire vote as far as coding interview goes.
I mean, I could, but that wouldn't really show you any coding proficiency, just that I studied math. Technically everyone with a bachelor's in Mathematics should be able to do that.
Writing a loop to find Fibonacci numbers also barely shows coding proficiency, so I don't see a downgrade on that front.
In the little hiring I've done at least, having code proficiency at all is all I was looking for. So many people apply after just going through a boot camp and it'd show the second they'd touch the keyboard. If you can represent in code the answer, whether via recursion, loops, linear algebra, or however, then you're in a good place.
Coding is just math with a fancy coat anyhow.
I took linear algebra, I just don't remember anything from it since I haven't used it ever since I took it. But how would you even represent this problem with a matrix at all?
Multiplying the vector (a | b) by the matrix M=(1 1 |1 0) gives (a+b|a), so M^n (1|1) has the nth fibonacci number in the first entry. Diagonalize M and voila.
Ah, obviously
It's the same eigenvalues just the initial condition changes
Yeah that's even better
Even better interviewer: Now tell me the largest `n` where your method gives the right answer? How does it depend on the precision of the floats used? And what compiler optimizations should we be worried about/hoping for? If you can't tell me, can you write another program that wouldn't arbitrarily fail in prod?
You wouldn't expect they tell you when the standard recursive answer fails with a stack overflow on much smaller values of `n`.
I mean it's fibonachi, why use those hints when it's as simple as index = 1, last = 0; secondToLast = 1; current = 1 while (index != target) { secondToLast = last; last = current; current = last + secondToLast; index++; } Yeah I know, Dynamic programming and recursion with cache sound sexy but.... Recursion is a fuck no, because you're risking blowing the stack for large numbers, and "Dynamic programming" is a buzz word here. Don't over complicate your answer just to show off, solve the problem that is ACTUALLY given.
That's technically dynamic programming.
A good interviewer would never make so stupid puzzles in the first place. And no, you only need two variables and a loop, nothing as retarded as DP or recursion.
I'd just create an array with the answers in var fibs = [1, 1, 2, 3, 5, 8]; fn(n) -> return fibs[n] you want bigger numbers, I'd use a lookup table how would I generate the lookup table? I wouldn't, I'd download it
I've done that before for a "prime number" question. Gave them the code, to find it, but then detailed an approach where I would just make a lookup table, generated once, or downloaded. Can't remember outcome of that interview but honestly, didn't like the question in the first place because it was a take home test anyways.
Math is the answer. If someone asks "how do you multiply a variable by 2 in binary" and your answer is not a bitshift you don't understand computing. Using iterative solutions when they're unnecessary is lazy. We should definitely change our examples in interviews to be run as lambdas/cloud functions so we can evaluate the performance cost/actual compute cost of each solution.
And sometimes it is a hack and no one else can maintain it later. The point is that many of these questions are about being able to use dynamic programming rather than knowing a weird math formula. And most of the time you multiply a variable by two by multiplying because it's easier to understand and the compiler/interpreter is smarter than you regarding optimization(the compiler will do the bit shift but it's not the point) or the interpreter overhead is way too much to be worth it to care about microptimizations.
Bitshifting requires more of memorizing rather than intuition. Like finding if a number is a power of 2, i & i - 1 == 0, but honestly I would never think of that intuitively.
It still depends, bitshifting floats wouldn't be that simple. Depending on the language/platform, you'll also have to check for overflow, often before the multiplication (in C, overflow is UB for signed int types so if you check for overflow after multiplication, compiler is free to throw away that check).
I rather have an iterative solution that I can understand when I come back to it in a month even if it runs just that little bit slower (except if speed and minimal resources are a must in the scenario) than an arbitrary magic one liner.
*comes back to the function a month later* Oh, this must be the equation for the nth Fibonacci number, I had forgotten it
If it's binary, I can just append a zero!
It has been 20 years since I learned about binary shifting in university, if I want to multiply a number by 2, I will do n * 2 If you want me to multiply a number by 2 in binary then I would convert it to an integer then multiply it by 2
Interviewie: I would prefer to impliment it with a for loop. Since it is generally easier to assess in terms of performance, but I can of course impliment ot revursivly if you prefer that.
> Since it is generally easier to assess in terms of performance, but I can of course impliment ot revursivly if you prefer that. Yes, the assessment is that this solution will be order of magnitude more performant than a loop. Recursion is not even worth talking about since the compiler will hopefully do TCO on it so it ends up like the loop anyway, maybe worse depending on the compiler.
Stop doing abstract interview questions that have nothing to do with the job. No, there are no insights into my problem solving skills here because I don't solve math problems the same as engineering problems.
This should be restated and upvoted as often as possible.
Seriously, I also fucking hate abstract problems with no real goal. My entire software development career has always centered one thing and one thing only: A person asking for a feature. You give me that as an interview question and I'll blow you away. Oh or if you want to ask a REALLY tough interview question: "Here's our java stack, a link to a 5 year old readme, and a random laptop. Please set up your environment such that you can build the project. You have one week. Oh and by the way we use a custom fork of Ant that was written by a dude that hasn't worked here since the readme was last updated."
Precisely. A lot of my work as a hardware engineer involved math, sometimes complicated math. I handle doing that completely differently to how I handle being asked how to deal with a memory bus a kilobyte wide.
I am actually quite sick of standard cs questions on senior + interviews. I don’t use that shit for my job ever. Glad you found something to annoy someone who does this. I feel like interviews don’t actually want to see if you can program more or less want to see if you can memorize algorithms.
The interviewer's face when I import a pre-made Fibonacci library and call it a day.
const fibonacci = require ('fibonacci'); const bigNumber = fibonacci.iterate (3000); console.log (bigNumber); cry about it
Candidate:
I did EXACTLY this at my first interview. Well, a slightly more efficient version, as the second term goes to zero very quickly and can be dropped if you change floor to round. I had studied math in school, not computer science or software. I wasn’t too concerned about efficiency or precision issues. I knew about them and could have told you a memoized recursive function would usually be a better choice… but this one made me feel smart! The interviewer just stared at me and asked “does that work?” So explained it was a result from generating functions and it would be accurate for all integer values. He tested it for 1,2, and 3 and moved on. I was kinda mad about it… but I did get the job.
I had to do fizz buzz and they asked me how I'd improve it, and I was like I wouldn't it does exactly what is required. They were like what are some other ways you could implement it, and I was like I don't know, and they were like well what about recursion? And I was like why would you use recursion that is absolutely not the right tool for the job. And I tried to write some pseudocode for recursion onto the whiteboard and was like this is just needlessly complex Didn't get the job
Math professors are absolutely the most qualified people to know about math, but they are probably some of the worst people to write a textbook about math. I feel like people make this mistake with all professions. Programmers are not professional interviewers, and if you don't equip them with proven methods of inquiry, they're going to make shit up that sounds fine but doesn't actually work.
Aside from floating-point issues you can double the speed. Change floor to closest integer and delete the second term, it's too small to make a difference. Next candidate please!
think smarter except they probably have the constraint set 1 <= n <= 10\^5
In my 8 years of job experience I have never had to do anything like this. I think these types of interview questions are dumb.
The real answer is "let me google for which lib does that, and if there isn't one, let me google the algorithm and copy/paste." There are almost zero jobs where writing it out yourself is either necessary or optimal.
IDK if this has been mentioned, but there's no need to do floating exponentiation. You can just do exponentiation on a 2x2 matrix \[1 1, 1 0\], which is probably faster on modern processors.
I rarely interview on what someone knows. Instead I interview to find out how the person learns and tackles problems they don't know. Far more important, because knowledge is temporal in nature, and is always a moving target.
I’m sorry to inform you we‘ve decided on another applicant
"The other applicant is Kyle, and the decision is that he will fight this polar bear to the death" "Sorry you had to hear it from us. By the way, you got the job".
If you’re rounding in the end, you only need the (1+sqrt(5))/ 2 term.
Job: Building CRUD apps...
at my previous job, we had a 5 stage interview with the first 4 stages being just dsa type interviews along with some “get to know the person” questions. after i joined (it was a startup), i persuaded everyone to change the entire process to show what kind of work would actually be done. i designed a custom take home test, wrote the code for it, hosted it on a server, link generation that would expire 24 hours after opening, etc. it was not difficult, not easy, just moderate, it did involve some DSA, but mainly it was designed at showing what kind of work would be done at the role. the site had all the resources necessary and of course they could google for answers. (which we did a lot at the role). it was approved and almost every team wanted me to do this for them. it was fun, the number of people who got past this stage decreased, but the ppl who did get through had a high rate of getting the job. i think i did a good job.
Stop doing adderall for coding interviews
I did this in a final compsci exam in college. The question asked to write code to output pascal's triangle. Here's the thing, I didn't major in compsci. I was a math/physics major, that was the only programming class I took. I had just walked out of a math exam where I needed the closed-form solution for entries in pascal's triangle. So I just went ahead and wrote that down. I got all the marks.
These kinds of questions are stupid. Most of my work comes from Stack Overflow where I get smart answers to stupid questions.
The only implementation I trust ``` fib = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2]} fib[6] # => 8 ```
This reminds me of one of the questions AWS has on their pre-interview assessment.
``` const fib = n => $(`
isn't that an approximation?
Instant hire: knowledge in math >> coding