Codility – Fibonacci sorusu

Enes Pekkaya    Java, Program     Java

Merhabalar,

Uluslar arası bir firma için iş teklifi gelmişti. Ben de iyi güzel dedim hadi görüşelim. 🙂 Skype üzerinden insan kaynakları ile yaklaşık 1 saat ingilizce konuştuktan sonra ilgili firma benim için olumlu dönüş yapmışlar ve codility sitesinde kod yazmamı istemişler. Tabi bu işlere biraz yabancı olduğum için bu site nedir ne değildir diye araştırdım. Bir çok firmanın bu site aracılığı ile developerların kod yeteneğini ölçtüklerini gördüm. Bildiğiniz herhangi bir dilde kod yazabiliyorsunuz anında kodunuzu compile edip kodunuzu çalıştırabilmektesiniz.

Uzun lafın kısası 1 saat süre tanındığı sınava girdim. Sınavın bitimine 1 dakika kala da sonlandırdım :s İşin açıkcası bu kadar kafa patlatacağımı hiç düşünmemiştim. Zaten soruyu anlamak en az 5 dakikamı aldı.

Sorulan Soru :

A function GF is defined as follows

 	GF(A, B, 0) = A;
 	GF(A, B, 1) = B;
 	GF(A, B, N) = GF(A, B, N-1) + GF(A, B, N-2); Where N > 1.
Write a function

java class Solution { public int solution(int A, int B, int N); }
that given 3 non-negative integers A, B and N returns the remainder from the division of GF(A, B, N) by 1,000,000,007

For example

given A = 3, B = 4 and N = 5, the function should return 29 because

 	GF(3,4,0) = 3 mod 1,000,000,007 = 3;
 	GF(3,4,1) = 4 mod 1,000,000,007 = 4;
 	GF(3,4,2) = (GF(3,4,1) GF(3,4,0)) mod 1,000,000,007 = 7;
 	GF(3,4,3) = (GF(3,4,2) GF(3,4,1)) mod 1,000,000,007 = 11;
 	GF(3,4,4) = (GF(3,4,3) GF(3,4,2)) mod 1,000,000,007 = 18;
 	GF(3,4,5) = (GF(3,4,4) GF(3,4,3)) mod 1,000,000,007 = 29;
Assume that

A and B are integers within the range [0..2,147,483,647].
N is an integer within the range [0..1,000,000,000].

Complexity

expected worst-case time complexity is O(log(N)).
expected worst-case space complexity is O(1).

Yukarıdaki sorunun çözümü için ilk önce aşağıdaki kodu çalıştırdım. İşte dedim soruyu çözdüm derken şu örneği denediğimde (30, 40, 500), 5 saniyede cevap dönmediği için bu testte fail etti. 🙂

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
public int solution(int A, int B, int N) {
int mod = 1000000007;
int retval = 0;

if(N == 0)
return A;

if(N == 1)
return B;

for(int i = 0; i <= N; i ++) {
if(i == 0) {
retval = A;
}
else if(i == 1) {
retval = B;
}
else {
retval = (solution(A, B, N - 1) + solution(A, B, N - 2)) % mod;
}
}

// System.out.println(retval);
return retval;
}
}

Onun üzerine bir kaç dakika düşündükten sonra daha hızlı cevap verecek şu kodu yazdım.

import java.util.ArrayList;
// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
public int solution(int A, int B, int N) {
int mod = 1000000007;
int retval = 0;
ArrayList<Integer> integers = new ArrayList<Integer>();

if(N == 0) {
retval = A % mod;
}
else if(N == 1) {
retval = B % mod;
}
else {
integers.add(0, A % mod);
integers.add(1, B % mod);

for(int i = 2; i <= N; i ++) {
integers.add(i, (integers.get(i - 1) + integers.get(i - 2)) % mod);
}

retval = integers.get(N);
}

// System.out.println(retval);
return retval;
}
}

N sayısını baya büyük girmeme rağmen performans açısından sorun yaşamadım.

Büyük ihtimalle sonucunu benimle paylaşmayacaklar ama herhalde başarılı bir şekilde geçeceğimi ümit etmekteyim.
Belki sizi de codility sitesi üzerinden aynı soru ile karşılaşırsanız, en azından bir hayır duası alırım diye düşünmekteyim 🙂