>job interview
>HR part goes very well, I'm relaxed
>developers come in
>they ask conceptual questions and programming language specific questions
>answer comfortably
>so confident that I will get hired
>suddenly pic related comes in
>"Write a fibonacci function in O(n) time"
>my hands shake profusely
>write a shitty recursive fibonacci
>"O..okay, so what is the complexity of what you've written?"
>start crying
>rejected
Why does it keep ruining professional carriers? How can I get past it?
Other urls found in this thread:
crackingthecodinginterview.com
en.wikipedia.org
twitter.com
>failing babbys first interview question
Should've paid more attention in your bootcamp
it's simple, you kill all your competitors that out-skill you, so those employer niggers won't have the luxury of choice
He will have more trouble killing all of india than actually finding a job user
>Fibonacci in O(n) complexity
>in recursive
You deserve what you got and you should've done it iteratively
public int fibonacci(int iterations){
int first, second;
first = 1;
second = first
for(int i=o;i,iterations;i++){
int sum = first+second;
second=first;
first=sum
}
return first;
}
>>"Write a fibonacci function in O(1) time"
>b-but..
>>"STOP! don't say anything else; do you actually have a CS degree?"
>of course I do, bu-
>>"We will not waste more of YOUR time, thank you... oh and please leave the door open..."
Just hard code the entire Fibonacci sequence from zero to sys.maxint() and you've now written a Fibonacci Sequence better than O(n)
>india
>knowing big O notation
this is how you weed out the Google babies from the 1337 haxx0rs
>writing a function to compute fibonacci
Is there anything more useless. There literally exist an exact formula.
Feel like converting your solution to a recursive one?
but it uses irrational numbers
Aight imma try a crack at this
let start = 0
let next = 1
let numbers = []
while(1 = true)
try{
for numbers in function() {
result += numbers.index() + next
printf("&result);
}
catch e {
logger.log("Gotta dump some bits in the harbor boss")
cat ${result} >> /dev/null
1 = false
}
println("And that's the end of the fibonacci sequnce")
>he can't reduce fibonacci set to O(1) function
don't call us, we will call you.
O(n^2) not O(n)
addition is not O(1)
>write recursive fibonacci
>tell the language has lazy evaluation
checkmate, atheists
absolute state of Jow Forums
Sadly it's not bait, it's fact. If you stay in int32_t world you're just coding an O(1) function that isn't Fibonacci.
lmaoing at your life OP
O(1) complexity bitch
>2018
>believing that round, pow * + - / are O(1) operations
lmao what else do you want me to use you cuck
>use in the corporate world
>"WHY IS MY DATA CORRUPTED IM SUING YOU"
explain
float computations are NEVER accurate. your formula depends on irrational numbers
True O(1)
#include
constexpr int fibonacci(int n)
{
if (n == 0)
return 0;
if (n
>absolute state od /g
>pow, round O(1)
To what indian university did u go?
>producing an approximation is the same as producing the expected value
kids these days think they can just skip a bunch of steps and still get to the same solution
>posts recursive solution
>o(1)
when rounded it produces the correct answer, and less compute time . For all practical intents and purposes it works better than both other solutions
Unless you use long arithmetics or programming for microcontrollers without those operations, they are.
Look at it again, poojeet
>they are.
In that case you're not coding Fibonacci. Fib implies long arithmetic.
>using c++
>prints with printf
literally the embodiment of Jow Forums memes
I'm doing Fibonacci modulo 2^64 :^)
>I'm doing Fibonacci modulo 2^64 :^)
That ain't fib, bro.
This is actually a top tier answer
>unironically uses cout
the absolute state of Jow Forums
>in O(n) time
explain
>these are the people on Jow Forums who complain about not being able to get programming jobs
Thank fucking god
OK explain how this is O(1)
constexpr
They did not specify runtime complexity though. Compile time complexity is not O(1)
Not that guy, just curious. cout is just printf without having to specify %d, %i, etc and simplifies some formatting...is that right?
No.
only true O(1) itt
>Interviewer then asks for series to n
We'll call YOU
Given arbitrary n. write fn that executes in a time of the order of n (eg double n = double time)
std::cout does a mutex lock and unlock for each operator
actual O(1) solution here folks
haslel
fibMoveSer n = take n . (1:) . map snd $ iterate (\(x, y) -> (y,x+y)) (1,1)
fibMoveN = last . fibMoveSer
Pray tell me oh great fp master O complexity of that?
sir, i did my stdies in iit khrsgpur. it is nmber 1 in th wrld...
>VGA
>homeless
lol no
it will never die thanks to businesses using old projectors
kinda bad, wanted to imitate the steppy solution
can make it faster (O(n)) by doing the usual trick
fbSer = 1 : 1 : zipWith (+) fbSer (tail fbSer)
A real tragedy for everyone who wants to move on.
#include
#define REP(i,n) for (int i = 1; i
>caring about big O notation
It's academic masturbation.
>not (int first, int second)
This. You won't use that shit on daily operations. Of course you should know how your code is optimized, but almost none of that shit is useful out there in the real world.
Ironically this was part of the curriculum for the exam I had today
This is the way to go if you regularly need to know the sequence at arbitrary index. This can also be applied across many other types of data that you can generate algorithmically.
Detecting O(n) is a fucking rule of thumb. I can understand if the mathematical proofs and notation don't fall into practical everyday use. However, if you can't understand or explain time complexity in layman's terms, but at the same time think you can "optimize" code, you're absolute cancer. Good code can benefit from compile-time optimizations, but that doesn't save you from bad code.
Whoops. Also, how did you manage to implement O(1) exponentiation?
>int i=o;
#include
char *fib[] = {
"0", "1","1","2","3",
"5","8","13","21","34",
"55","89","144","233",
"377","610","987","1597",
"2584","4181","6765","10946",
"17711","28657","46368","75025",
"121393","196418","317811","514229",
"832040","1346569","2178309","3524578","9227465"
};
int main(void){
for(int x=0;x
# Python 3: Fibonacci series up to n
>>> def fib(n):
>>> a, b = 0, 1
>>> while a < n:
>>> print(a, end=' ')
>>> a, b = b, a+b
>>> print()
>>> fib(1000)
this was on the front page of python.org.
You are fired
int fib(int iterations) {
int first, second = 1;
for(int i=0; i
Hey guys what O is this
(defun fibonacci (n) (loop as a = 0 then b and b = 1 then (+ a b) repeat n finally (return b)))
just werkz
def fib(n): ...
return int((math.pow((1+math.sqrt(5))/2.0, n)-math.pow((1-math.sqrt(5))/2.0, n))/math.sqrt(5))
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond [(= count 0) b]
[(even? count)
(fib-iter a
b
(+ (* q q) (* p p))
(+ (* q q) (* q p 2))
(/ count 2))]
[else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1))]))
>I'm a Computer SCIENTIST, not a silly mathematician: if I need to search for some stupid formula I can use Wikipedia. Good-bye asshole!
>*runs to the closest coffee shop and furiously writes a Medium article about how stupid code interviews are*
>*get tons of hackernews and leddit karma*
>*request tranny porn on /gif/, get banned for 3 days*
>*cries all night long*
>addition is not O(1)
Addition over fixed sized integers is, in fact, O(1). There was no expectation of arbitrary precision arithmetic.
>int first, second;
2
>second = first
1
>for(int i=o;i,iterations;i++)
n*(
> int sum = first+second;
2
> second=first;
1
> first=sum
1)
>return first;
1
Total Complexity:
2+1+n*(2+1+1)+1
=3+4n+1
=4n+4
=O(n)
it was indeed linear
i mean shit a tougher interview question would have been to ask you to code in in worse than linear time, this would be tough to code in O(n^2) without just adding useless shit
def fib_nonlinear(step):
f_n,f_m=1,1
for each in range(step):
for every in range(each):
print "Calculating, please wait... %s percent complete" % str((float(each)/float(step))*100)
add=f_n+f_m
f_m=f_n
f_n=add
return f_n
Here are a few O(n) or better solutions
int fibonacci(int n) {
if (n < 2) return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
why? Writing it recursively will be O(Log(n)), which is slower than O(n). You can optimize it with some dynamic programming and memo tables, but at that point...
???
fibonacci(5)
std::int64_t fibonacci(std::int64_t n) {
static const std::double_t sqrt_five = std::sqrt(5.0);
static const std::double_t golden_ratio = (1.0 + sqrt_five) / 2.0;
return static_cast((std::pow(golden_ratio, n) - std::pow(-golden_ratio, -n)) / sqrt_five);
}
O(1), what do i win
Thank you
isn't log(n) faster than n?
>the STATE of Jow Forums
Do other professions require you to pass a live timed test on knowledge from the occupation they're hiring for?
I legitimately dont know.
I feel like comp sci positions have more hoops to jump through to get a job than other occupations, but I have no idea.
Do people really not know fibonacci had a simple closed form solution?
99.999...% of numbers are irrational.
>he doesn't know the golden ratio
you deserved it my dude. study up on math as well as data structures.
Just use Binet's formula, iterative/recursive solutions for this aren't O(n).
Addition step is O(log(n)) though, so this is actually O(n*log(n))
Nothing because it doesn't give the correct answer.
kek
review your statement
if you graph time to execute vs size of input, you would see a linear function, such as y = x. (it could be y = 2x, or y = x/2, we don't care so long as it is linear). Such a program function would be considered to have a time complexity of O(n).
Brainlet discovered.
If the input is a fixed width integer then the complexity would be O(1). If the input is a dynamic width then it would be O(n^2) because addition is O(n).
Sorry, it would be O(fib(n) * n).
> not being prepared to showcase your (((dynamic programming))) skills on the huwhite board
>job interview
>things are going well
>able to bs my way through all the non-technical questions
>able to recite the shit i read on wikipedia for the language I'm applying for
>suddenly asked to actually demonstrate the skill I'm being hired for.
>this wasn't the in code examples on the wiki page
>i don't have stack overflow to answer it for me
>fail horribly
>get called out for it and don't get job
>go on Jow Forums and complain about it