Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
void fibonacci(int n, int len);
{
if(len<=0 ||n<0)cout<<"wrong Input";
else
{
for(int i=1; i<=len;i++)
cout<<fibo(n-1,i);
}
}
int fibo(int n, int len)
{
if(len==1)return n;
if(len==2)return (n+1);
return fibo(n-2) +fibo(n-1);
}
//test case:
1.(0,0)
2.(0,1)
3.(0,2)
4.(5,0)
5.(5,5)
6.(-1,-1)
class Fibonacci
{
static Dictionary<int, int> fibMap = new Dictionary<int, int>();
public static int RunFibonacci(int startIndex, int len)
{
int fib = 0;
if (fibMap.ContainsKey(len))
{
return fibMap[len];
}
if (len == 1 || len == 2)
{
fib = 1;
}
else
{
fib = RunFibonacci(startIndex, len - 2) + RunFibonacci(startIndex, len - 1);
}
fibMap.Add(len, fib);
if (len >= startIndex)
{
Console.WriteLine(fib);
}
return fib;
}
public static void FibonacciTest()
{
RunFibonacci(1, 10);
Console.WriteLine("===");
fibMap.Clear();
RunFibonacci(2, 6);
Console.WriteLine("===");
fibMap.Clear();
RunFibonacci(3, 5);
Console.WriteLine("===");
}
}
#include <iostream>
#include <cstdlib>
int main()
{
int lower = 0; // fibo series: 0, 1, 1, 2, 3, 5 ...
int upper = 1;
int temp = 0;
// ------------------- user input goes here ----------------------------- //
int startPoint = 1; // from 1st element, assuming series starts from 0th element
int range = 4; // 5 elements including startPoint
// ---------------------------------------------------------------------- //
if(startPoint>=0 && range > 0)
{
int endPoint = startPoint + range - 1;
if(startPoint < 2)
{
while(startPoint != 2 && range != 0) // this loop executes at most 2 times
{
std::cout<< startPoint++ <<" ";
range--;
}
endPoint = startPoint + range - 1; //recalculate
}
while(endPoint>=2) // iterate
{
temp = lower;
lower = upper;
upper = lower + temp;
endPoint--;
if(endPoint <= range)
std::cout << upper << " ";
}
}
else
{
std::cout<<"invalid input!";
}
getchar();
return 0;
}
bool fibo(int start,int length)
{
if (start < 0)
{
cout << "Invalid start";
return false;
}
if (length < 0)
{
cout << "Invalid length";
return false;
}
if (length == 0)
{
cout << "Lenght = 0";
return true;
}
int a = 0;
int b = 1;
int nr = 1;
if (start == 0)
{
cout << a << " ";
length--;
}
if (start == 1)
{
cout << b << " ";
length--;
}
while (nr < start)
{
a += b;
b = a - b;
nr++;
}
while (length--)
{
a += b;
b = a - b;
cout << a <<' ';
}
return true;
}
/**
* Print out fibonacci numbers from a start point and for a specific length
* @param start start index
* @param length number of count to print out
*/
public static void printFib(int start,int length){
int last2=0,last=1;
int count=0;
int current=0;
if(start<0 || length==0)return;
while(count<start+length){
if(count==0){
current=last2;
}else if(count==1){
current=last;
}else{
current=last+last2;
last2=last;
last=current;
}
if(count>=start){
System.out.println(""+current);
}
count++;
}
}
int[] f = new int[100];
internal void fibo(int start, int length)
{
f[0] = 0; // initialize first position to zero
for (int i = 0; i < length; i++)
{
int num = fibo(start + i);
Console.WriteLine(num);
}
}
private int fibo(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
f[n - 1] = fibo(n - 1);
return f[n - 1] + f[n - 2];
}
- Rayden January 18, 2012