DEV Community

loading...

School problem from senior developer interview

rodiongork profile image Rodion Gorkovenko ・2 min read

I was asked this problem years ago at interview for Java developer. It was about using BigInt really, but that's not important. I later slightly extended it and started asking when I interview other people in my turn (usually big-data or data science developers). Curiously, it puzzles about 40% people pretending for several kilo-dollars salary :o

Code could be written in 3 minutes (e.g. in Python), but then people sometimes stuck for hour. I think most of you, Friends, will solve it easily - but you can check your colleagues for fun. So here it is:

Statement

Fibonacci numbers (we all know them) are defined as:

fib = [0, 1, 1, 2, 3, 5, 8, ...]

# or in other words
fib[0] = 0
fib[1] = 1
# ...
fib[n] = fib[n-1] + fib[n-2]

Write the program (usually in Python) which finds index, where Fibonacci value ends with specific digits. For example ending 12345 could be found at fib[155].

Then find the following:

For which index X fib[X] ends with five digits `55555` ?  
For which index Y fib[Y] ends with seven digits `7770777` ?  
For which index Z fib[Z] ends with eight digits `20200123` ?

This value 20200123 is just today's date, nothing special about it. :)

P.S. I think it's ok to drop X, Y, Z in the comments when you find them. Code - as you wish...

P.P.S. if can't solve at once, this problem may give inspiration, though of course you'd better try solving on your own first... If it is necessary I'll update the post with explanation in about three days, though I believe it is too simple for most of readers.

Discussion (8)

pic
Editor guide
Collapse
pinutz23 profile image
Jannik Wempe

That was a fun task and I could refresh some aspects of python doing it. Thanks!

Until now (programm is still executing) I just have the following solution:
X -> 92740
Y -> ???
Z -> ???

I am pretty sure that my solution is far from perfect, since it has a huge runtime and memory consumption. Therefore I'm really looking forward to a better approach.

Collapse
rodiongork profile image
Rodion Gorkovenko Author

Jannik, Hi!

Thanks for attempt!

Yep, it is just a matter of making it work without speed degradation due to number length increase :)

Collapse
arseniyk profile image
Arseniy Krasnov • Edited

There a trick you can use:

last 2 and 3 digits of fibonacci repeats each 1500 terms
last 4 digits repeats each 15,000
last 5 digits repeats each 150,000
last 6 digits repeats each 1,500,000
last 7 digits repeats each 15,000,000

x = 92.740
y = 4.562.603
z = 280.555.264

Collapse
rodiongork profile image
Rodion Gorkovenko Author

Nice idea about finding "the loop length" after which "endings" repeat :) Perhaps some other puzzle could be invented from it.

However my approach was simpler - just taking modulo by 10eX where X is amount of digits in the number we seek. Then numbers won't grow longer than this.

I suspect your and mine approaches are really two versions of the same fact, however

Collapse
brotschere profile image
Michael

Hi,

so far I have
x - 92.740
y - 4.562.603

Have a nice weekend
Michael

Collapse
rodiongork profile image
Rodion Gorkovenko Author

Michael, Hi!

Thanks for try! Judging by "so far" it seems you also use straightforward implementation which becomes a bit slower as the values grew :)

Good luck!

Collapse
brotschere profile image
Michael

Hi Rodion,

yes, I started with a default-Fibonacci, and that take a lot of time ;O)

With a little optimization (using only the necessary decimal places), the last value can be found within minutes.

b: 54212345 idx 155
b: 77255555 idx 92740
b: 67770777 idx 4562603
b: 20200123 idx 145555264

So I found z - 145.555.264

Is that correct?

Thread Thread
rodiongork profile image
Rodion Gorkovenko Author

Hi Michael!

At least my results are exactly the same! So I believe you are right and this is correct :)