Google Interview Question
Software Engineer / DevelopersCountry: United States
Seems pretty straightforward:
public void outputPairs(int n) {
int prev, curr, temp;
prev = curr = 1;
for (int i = 1; i < n + 1; i++) {
printPair(prev % 10, curr % 10);
temp = curr;
curr += prev;
prev = temp;
}
}
public void printPair(int a, int b) {
System.out.println("["+a+", "+b+"]");
}
static void Main(string[] args)
{
int n = 0;
Console.WriteLine("Enter an integer");
n = int.Parse(Console.ReadLine());
int firstNum = 0;
int secondNum = 1;
int sumOfNums = 0;
for (int i = 0; i < n; i++)
{
Console.WriteLine("[" + (firstNum %10).ToString () + ", " + (secondNum%10).ToString() + "]");
sumOfNums = firstNum + secondNum;
firstNum = secondNum;
secondNum = sumOfNums;
}
Console.ReadKey();
}
static void Main(string[] args)
{
int n = 0;
Console.WriteLine("Enter an integer");
n = int.Parse(Console.ReadLine());
int firstNum = 0;
int secondNum = 1;
int sumOfNums = 0;
for (int i = 0; i < n; i++)
{
Console.WriteLine("[" + (firstNum %10).ToString () + ", " + (secondNum%10).ToString() + "]");
sumOfNums = firstNum + secondNum;
firstNum = secondNum;
secondNum = sumOfNums;
}
Console.ReadKey();
}
static void Main(string[] args)
{
int n = 0;
Console.WriteLine("Enter an integer");
n = int.Parse(Console.ReadLine());
int firstNum = 0;
int secondNum = 1;
int sumOfNums = 0;
for (int i = 0; i < n; i++)
{
Console.WriteLine("[" + (firstNum %10).ToString () + ", " + (secondNum%10).ToString() + "]");
sumOfNums = firstNum + secondNum;
firstNum = secondNum;
secondNum = sumOfNums;
}
Console.ReadKey();
}
package numbers;
import java.util.ArrayList;
public class FibPairLSD {
public static void main(String[] args) {
System.out.println(dpGenFib(8));
}
public static int dpGenFib(int n){
int[] fibNums = new int[n];
fibNums[0] = 1;
fibNums[1] = 1;
if (n <= 2)
return fibNums[n - 1];
Pairs p = new Pairs(1, 1);
ArrayList<Pairs> list = new ArrayList<Pairs>();
list.add(p);
for(int i = 2; i < n; i++){
fibNums[i] = fibNums[i - 1] + fibNums[ i - 2];
int s = fibNums[i] % 10;
int f = fibNums[i - 1] % 10;
p = new Pairs(f, s);
list.add(p);
}
System.out.println(list.toString());
return fibNums[n - 1];
}
public static class Pairs{
int f;
int s;
public Pairs(int f, int s) {
this.f = f;
this.s = s;
}
public String toString(){
return "(f:" + this.f + " s:" + this.s + ")";
}
}
}
public static void outputPairs(int n) {
int lst = 1;
for (int i=1;i<n;i++) {
int fb = fib(i);
int b = lst;
lst = fb%10;
System.out.println("[" + b + ", " + lst + "]");
}
}
private static int fib(int n) {
if(n <= 1){
return n;
}
int fibo = 1;
int fiboPrev = 1;
for(int i = 2; i < n; ++i){
int temp = fibo;
fibo += fiboPrev;
fiboPrev = temp;
}
return fibo;
}
#include <stdio.h>
#include <stdlib.h>
void compute(int);
void display(int ,int);
int main()
{
int n;
printf("Enter no of pairs is to be printed\n");
scanf("%d",&n);
compute(n);
return 0;
}
void compute(int n)
{
int i,a,b,c;
if(n==0 || n==1)
{
display(-1, -1);
return;
}
//n pairs
a=1;
b=1;
for( i=1; i<=n ; i++)
{
display(a%10,b%10);
c=a+b;
a=b;
b=c;
}
}
void display(int a,int b)
{
if(a==-1)
printf("no of pairs is too small . Enter a larger value\n");
else
printf("[%d,%d] ",a,b);
}
public class Fib
{
private static final Pair FIRST_PAIR = new Pair(1, 1);
private static class Pair
{
private int first;
private int second;
public Pair(int f, int s)
{
first = f;
second = s;
}
public int getFirst()
{
return first;
}
public int getSecond()
{
return second;
}
public Pair next()
{
return new Pair(getSecond(), (first + second) % 10);
}
public String toString()
{
return "[" + first + ", " + second + "]";
}
}
public static void outputpairs(int n)
{
if (n > 0)
{
Pair p = FIRST_PAIR;
System.out.print(p);
for (int i = 1; i < n; i++)
{
p = p.next();
System.out.print(", ");
System.out.print(p);
}
}
}
}
class fibo_sequence:
def fibonacci(self,n):
if n == 0 and n == 1:
return n
fibo = 0
temp1 = 1
temp2 = 1
arr = []
finalarr = []
count = 0
while(count < n ):
fibo = temp1 + temp2
temp2 = temp1
temp1 = fibo
arr.append(temp2%10)
arr.append(temp1%10)
finalarr.append(arr)
arr = []
count = count + 1
return finalarr
f = fibo_sequence()
print f.fibonacci(10)
package com.lavan.one;
public class Fib {
public static void main(String args[]){
// Pass number of pairs inside the method
OutputPairs(8);
}
static void OutputPairs(int n){
for(int i = 1; i<=n; i++){
int x = getFib(i-1)%10;
int y = getFib(i)%10;
System.out.print("[" + x + "," + y +"]");
}
}
static int getFib(int n){
if(n<=1){
return 1;
}else{
return getFib(n-1) + getFib(n-2);
}
}
}
def fib(n):
a=[1,1]
b=[1,1]
fib=[a]
for i in range(n-1):
temp=[b[1],(a[1]+b[1])%10]
fib.append(temp)
a=b
b=temp
print fib
fib(20)
OUTPUT:
[[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1], [1, 4], [4, 5], [5, 9], [9, 4], [4, 3], [3, 7], [7, 0], [0, 7], [7, 7], [7, 4], [4, 1], [1, 5], [5, 6]]
import java.util.*;
public class HelloWorld{
int size=100;
Map<Integer, List<List<Integer>>> map =new HashMap<>();
int[] M= new int[size];
public static void main(String []args){
System.out.println(new HelloWorld().f(12));
}
public List<List<Integer>> f(int n)
{
if(map.containsKey(n)){
return map.get(n);
}
if(n==1){
List<Integer> list= new ArrayList<>();
list.add(1);
list.add(1);
List<List<Integer>> megaList=new ArrayList<>();
megaList.add(list);
map.put(1, megaList);
return megaList;
}
List<List<Integer>> megaList= f(n-1);
List<Integer> list= new ArrayList<>();
list.add(lsdL(megaList)); //null check
list.add(lsd(fib(n)));
megaList.add(list);
return megaList;
}
private int lsdL(List<List<Integer>> list){
if(list !=null){
List<Integer> temp = list.get(list.size()-1);
return temp.get(1);
}
return 0;
}
private int lsd(int n){
return n%10;
}
private int fib(int n){
if(M[n]!=0){
return M[n];
}
if(n<=2){
return 1;
}
M[n]=fib(n-1)+fib(n-2);
return M[n];
}
}
import java.util.*;
public class HelloWorld{
int size=100;
Map<Integer, List<List<Integer>>> map =new HashMap<>();
int[] M= new int[size];
public static void main(String []args){
System.out.println(new HelloWorld().f(12));
}
public List<List<Integer>> f(int n)
{
if(map.containsKey(n)){
return map.get(n);
}
if(n==1){
List<Integer> list= new ArrayList<>();
list.add(1);
list.add(1);
List<List<Integer>> megaList=new ArrayList<>();
megaList.add(list);
map.put(1, megaList);
return megaList;
}
List<List<Integer>> megaList= f(n-1);
List<Integer> list= new ArrayList<>();
list.add(lsdL(megaList)); //null check
list.add(lsd(fib(n)));
megaList.add(list);
return megaList;
}
private int lsdL(List<List<Integer>> list){
if(list !=null){
List<Integer> temp = list.get(list.size()-1);
return temp.get(1);
}
return 0;
}
private int lsd(int n){
return n%10;
}
private int fib(int n){
if(M[n]!=0){
return M[n];
}
if(n<=2){
return 1;
}
M[n]=fib(n-1)+fib(n-2);
return M[n];
}
}
int fibDigit(int order) {
if (order == 0) {
return 0;
} else if (order == 1) {
return 1;
} else {
return fibDigit(order - 1) + fibDigit(order - 2);
}
}
void Outputpairs(int nPairs) {
for(int i = 1; i <= nPairs; i++) {
cout << "[";
cout << fibDigit(i) % 10 << ",";
cout << fibDigit(i + 1) % 10;
cout << "] ";
}
}
My solution in python. Not the shortest but it feels pretty clear to me.
def fibGen():
curr = 0
next = 1
while True:
temp = curr
curr = next
next += temp
yield curr, next
def fibPairs(n):
fibs = fibGen()
output = []
while (len(output) < n):
curr, next = fibs.next()
pair1 = [firstDigit(curr), firstDigit(next)]
if (len(output) == 0):
curr, next = fibs.next()
pair2 = [firstDigit(curr), firstDigit(next)]
if (pair2[0] == pair1[1]):
output.append(pair1)
output.append(pair2)
else:
if (pair1[0] == output[-1][1]):
output.append(pair1)
return output
def firstDigit(x):
return int(str(x)[-1])
My solution in python. Not the shortest, but it seems pretty clear to me.
def fibGen():
curr = 0
next = 1
while True:
temp = curr
curr = next
next += temp
yield curr, next
def fibPairs(n):
fibs = fibGen()
output = []
while (len(output) < n):
curr, next = fibs.next()
pair1 = [firstDigit(curr), firstDigit(next)]
if (len(output) == 0):
curr, next = fibs.next()
pair2 = [firstDigit(curr), firstDigit(next)]
if (pair2[0] == pair1[1]):
output.append(pair1)
output.append(pair2)
else:
if (pair1[0] == output[-1][1]):
output.append(pair1)
return output
def firstDigit(x):
return int(str(x)[-1])
My solution is same as others, but I have cached the old results to save some computation in future.
def pp(n):
repeat = {}
a = []
first = 1
second = 1
while (n>0):
index,length = repeat.get((first,second), (None,None))
if index:
if length > n:
for k in a[index:index+n]:
print k
return
else:
for k in a[index:index+length]:
print k
n -= length
else:
next = (first+second)%10
print (first, second)
first = second
second = next
n-=1
tup = (first, second)
try:
ind = a.index(tup)
repeat[(first, second)] = ind,len(a)-ind
except:
pass
a.append(tup)
#include <iostream>
/* the n-th and (n+1)-th terms of the fibonacci sequence are given by:
* [ 1 1 ]
* [ f_{n+1} f_n ] = [ f_1 f_0] * M^n, where M is [ 1 0 ]
*
* The eigenvalues are solutions of x^2 - x - 1 = 0
*
* Mod 2, eigenvalues generate GF(4), and have multiplicative order 3.
*
* Mod 5, we have a single eigenvalue (3), and the matrix is not
* diagonalizable. M^5 = (3 + (M-3))^5 = 3I is diagonal, though (since
* M-3 is nilpotent and its 5-th multiple is zero).
*
* Thus M^15 is diagonal, with diagonal elements congruent to 1 mod 2 and
* to 3^3=2 mod 5.
*
* 2 has multiplicative order 4 mod 5, so that M has period 60
*/
const int cache[] = {
1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0,
7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0,
9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0,
3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0};
void Outputpairs(int n)
{
int prev = cache[0];
bool first = true;
for(int i = 1 ; i <= n ; i++, first = false) {
int x = cache[i % 60];
if (!first) std::cout << ", ";
std::cout << "[" << prev << "," << x << "]";
prev = x;
}
std::cout << "\n";
}
int main(int argc, char * argv[])
{
int n = 10;
if (argc > 1)
n = atoi(argv[1]);
Outputpairs(n);
return 0;
}
The series last digit repeats with a cycle length of 60.
- ac March 22, 2015