## Student Interview Question

Country: United States

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

Before writing a program right away that counts the number of 0s and 1s printed, make a table with 3 columns:
1) "n"
2) "# of 0s printed"
3) "# of 1s printed"

Start filling in the first couple rows (i.e., for n=0, 1, 2, etc.):

n # of 0s printed # of 1s printed
0 1 0
1 0 1
2 1 1
3 1 2
4 2 3
5 3 5

Soon you'll realize that:
# of 0s printed = fib(n-1)
# of 1s printed = fib(n)

So the best solution is to just implement an efficient method for finding the (n-1)th and nth fibonacci numbers (e.g., iterative solution or recursive solution with memoization).

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

``````typedef std::pair<int, int> n10;

n10 numberOfOnesAndZeroes(int n)
{
if (n == 0) return n10(0, 1);
if (n == 1) return n10(1, 0);

n10 _2 = n10(0, 1);
n10 _1 = n10(1, 0);
n10 res;

int i;

for (i = 1; i < n; ++i) {
res.first = _1.first + _2.first;
res.second = _1.second + _2.second;
_2 = _1;
_1 = res;
}

return res;
}``````

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

pair <int, int> Count0sAnd1s(int n)
{
int oldNum = 1;
int newNum = 1;
for (int i = 3; i <= n; i++)
{
int tmp = oldNum + newNum;
oldNum = newNum;
newNum = tmp;
}
return pair <int, int>(oldNum, newNum);
}

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

public class FibCounter{

private ArrayList<ArrayList<Integer>> counts;

public FibCounter(){
counts = new ArrayList<ArrayList<Integer>();
ArrayList<Integer> currCounts = new ArrayList<Integer>();
currCounts.clear()
}

public static void countZerosAndOnes(n){
int zeros = 0;
int ones = 1;
if (counts.size() < n){
zeros = counts.get(n-1).get(0) + counts.get(n-2).get(0);
ones = counts.get(n-1).get(1) + counts.get(n-2).get(1);
System.out.println("Zeros: " + zeros + " Ones: " + ones);
return;
}

zeros = countZerosAndOnes(n-2).get(0) + countZerosAndOnes(n-1).get(0);
ones = countZerosAndOnes(n-2).get(1) + countZerosAndOnes(n-1).get(1);

ArrayList<Integer> currCounts = new ArrayList<Integer>();

System.out.println("Zeros: " + zeros + " Ones: " + ones);
}
}

Comment hidden because of low score. Click to expand.
0

Formatted:

``````public class FibCounter{

private ArrayList<ArrayList<Integer>> counts;

public FibCounter(){
counts = new ArrayList<ArrayList<Integer>();
ArrayList<Integer> currCounts = new ArrayList<Integer>();
currCounts.clear()
}

public static void countZerosAndOnes(n){
int zeros = 0;
int ones = 1;
if (counts.size() < n){
zeros = counts.get(n-1).get(0) + counts.get(n-2).get(0);
ones = counts.get(n-1).get(1) + counts.get(n-2).get(1);
System.out.println("Zeros: " + zeros + " Ones: " + ones);
return;
}

zeros = countZerosAndOnes(n-2).get(0) + countZerosAndOnes(n-1).get(0);
ones = countZerosAndOnes(n-2).get(1) + countZerosAndOnes(n-1).get(1);

ArrayList<Integer> currCounts = new ArrayList<Integer>();

System.out.println("Zeros: " + zeros + " Ones: " + ones);
}
}``````

Comment hidden because of low score. Click to expand.
0

Slight correction. Is there no edit button?

``````public class FibCounter{

private ArrayList<ArrayList<Integer>> counts;

public FibCounter(){
counts = new ArrayList<ArrayList<Integer>();
ArrayList<Integer> currCounts = new ArrayList<Integer>();
currCounts.clear()
}

public static void countZerosAndOnes(n){
int zeros = 0;
int ones = 1;
if (counts.size() < n){
zeros = counts.get(n-1).get(0) + counts.get(n-2).get(0);
ones = counts.get(n-1).get(1) + counts.get(n-2).get(1);
System.out.println("Zeros: " + zeros + " Ones: " + ones);
return;
}

zeros = countZerosAndOnes(n-2).get(0) + countZerosAndOnes(n-1).get(0);
ones = countZerosAndOnes(n-2).get(1) + countZerosAndOnes(n-1).get(1);

ArrayList<Integer> currCounts = new ArrayList<Integer>();

System.out.println("Zeros: " + zeros + " Ones: " + ones);
}
}``````

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

``````public class FiboCount {

public static void main(String[] args) {
Map<Integer, Output> cache = new HashMap<>();
System.out.println(getFib(14, cache));

}

public static Output getFib(int n, Map<Integer, Output> cache) {
if (cache.containsKey(n)) {
return cache.get(n);
}
if (n == 0) {
Output z = new Output(1, 0);
cache.put(0, z);
return z;
}
if (n == 1) {
Output o = new Output(0, 1);
cache.put(1, o);
return o;
}
Output first = getFib(n - 1, cache);
Output second = getFib(n - 2, cache);
Output result = new Output(first.z + second.z, first.o + second.o);
cache.put(n, result);
return result;
}

private static class Output {

int z;
int o;

public Output(int z, int o) {
this.z = z;
this.o = o;
}

@Override
public int hashCode() {
return o + z;
}

@Override
public boolean equals(Object o) {
if (this.getClass() != o.getClass()) {
throw new IllegalArgumentException();
}
Output comp = (Output) o;
return (this.z == comp.z && this.o == comp.o);
}

@Override
public String toString() {
return "Number of zeroes: " + z + '\t' + "Number of ones: " + o;
}
}

}``````

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

``````fib_Zero_And_One_Count(int n){

int *zero =  new int[n+1];
int *one =  new int[n+1];

zero[0] = 1;
zero[1] = 0;

one[0] = 0;
one[1] = 1;

for(int i = 2; i<=n; ++i){
zero[i] = zero[i-1] +zero[i-2];
one[i] = one[i-1] + one[i-2];
}

printf("zero: %d, one: %d\n", zero[n], one[n]);

delete [] zero;
delete [] one;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

package com.shashi.careercup;

public class FibonacciCount {

public static int op=0,op1=0;
public static void main(String args[])
{

System.out.println(fib(7));
System.out.print(op +" 0\'s and"+op1+" 1\'s"+" were printed ");
}
public static int fib(int n)
{

if(n==0)
{

op++;
return 0;
}
if(n==1)
{

op1++;
return 1;
}

return fib(n-1)+fib(n-2);
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>

int count0=0,count1=0;

int fib(int n){
if(n==0){
count0++;
return 0;
}
if(n==1){
count1++;
return 1;
}

return(fib(n-1)+fib(n-2));
}

int main(){
int ip,op;

printf("Enter the number:\t");
scanf("%d",&ip);

op=fib(ip);
printf("Output is %d",op);
printf("\nNumber of 0 is %d and Number of 1's are %d",count0,count1);
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>

using namespace std;

static int n0 = 0;
static int n1 = 0;

int fib(int n) {
if (n == 0) {
n0++;
return 0;
} else
if (n == 1) {
n1++;
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}

int main(int argc, const char * argv[]) {

std::cout << fib(14) << std::endl;

std::cout << "The number 0 is printed " << n0 << std::endl;

std::cout << "The number 1 is printed " << n1 << std::endl;

return 0;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

It can be solved using static variable

``````int fib (int n)
{
static int cntOne,cntZero;

if (n == 0)
{
cout<< "0";
cntZero++;
return 0;
}

if (n == 1)
{
cout << "1";
cntOne++;
return 1;
}

return fib(n-1) + fib(n-2);``````

}

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.

### 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.