Google Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
5
of 5 vote

The series last digit repeats with a cycle length of 60.

- ac March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The easiest way

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)

- Tony April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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+"]");
}

- SK March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the code when we have more than 2 digits ...seems it failed

- Anuj sharma April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void CreatePairs(int n)
        {
            var firstValue = 0;
            var secondValue = 1;

            for (int i = 0; i < n; i++)
            {
                var temp = secondValue;
                secondValue = (firstValue + secondValue) % 10;
                firstValue = temp;

                Console.WriteLine("[" + firstValue + "," + secondValue + "],");
            }

}

- ClintDempsey March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Neeraj Goyal March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }

- Neeraj Goyal March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Neeraj Goyal March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printFibPair(int N) {

int pp = 0;
int p = 1;


for (int i=2; i <= N; i++){
System.out.println("[" + pp%10 + " " + p%10 + "]");
current = pp + p;
pp = p;
p = current;
}

}

- sellingatduke March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void solve(int n){

    int a = 0,b = 1,c;
    for(int i=1;i<=n;++i){

        c = (a + b)%10;
        cout<<b<<" "<<c<<"\n";
        a = b;
        b = c;
    }

}

- alexalghisi March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + ")";
        }
        
    }
    
}

- um01 March 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "]");
}
}

- Anonymous March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "]");
        }
    }

- alives March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "]");
        }
    }

- alives March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {

return n <= 1 ? n : fib(n-1) + fib(n-2);

}

- alives March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- alives March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- vertika.srivastava2011 March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Outputpairs(int n ){
		arr = new int[n+1];
		arr[0]= 1; 
		arr[1] = 1; 
		int i = 2; 
		
		while( i <= n  ){
			arr[i] = arr[i-1] + arr[i-2];
			i++;
		}

		
		for( int k = 0; k <= n-1 ; k ++){
			System.out.print("[" +arr[k] %10 + " , " + arr[k+1] % 10+ "]" );
			System.out.println("\n");
		}
		
	}

- Anonymous March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
      }
    }
  }
}

- Anonymous March 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- pgupta6 March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sub Outputpairs(my $n) {
	my $pre_value = 1;
	my $pro_value = 1;
	my $i = 0;
	while ($i<$n){
		$i += 1;
		print "[". $pre_value%10 .",". $pro_value%10 ."]\n";
		$pre_value_2  =$pre_value;
		$pre_value = $pro_value;
		$pro_value = $pre_value_2+$pro_value;
	}
}

- Leo March 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
  }
}

- lavankumar01 April 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]]

- Tony April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code

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)

- Tony April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code

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)

- Tony April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
         
         
     }
}

- sunny April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
         
         
     }
}

- sunny April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 << "] ";
    }

}

- hoonji April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- Jeremyp August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- code123 November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- ManuT April 05, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

static void CreatePairs(int n)
        {
            var firstValue = 0;
            var secondValue = 1;

            for (int i = 0; i < n; i++)
            {
                var temp = secondValue;
                secondValue = (firstValue + secondValue) % 10;
                firstValue = temp;

                Console.WriteLine("[" + firstValue + "," + secondValue + "],");
            }
        }

- ClintDempsey March 22, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More