Another One For Interview … This Time Recursion

Recursion has been famous technique of eliminating loop and breaking the execution of code into regular call of methods.
Some times your interview is going good and there comes recursion which just shocks you….
It is simple but it’s simplicity makes you in trouble especially during strict time bound interview.
Basically recursion is a technique of calling a method from it’s own method.
It is similar to divide and break the complex logic into simple executable code.
Key to remember before starting to code any recursion solution is this equation

F(n)=F(x) + – F(n)

.
Where F(n) calls it self multiple times using the old value.

Let say we have to multiply two positive unknown values without using the multiplication sign.
So the function would
F(0) =b+F(1) —– F(1)=b+F(0) …. and so on ….

So lets write the code.

using System;

public class Test
{
public static void Main()
{
int d= multiply (10,2);
Console.WriteLine(d);
}
public static int multiply(int a,int b)
{
if(b==0)
{
return 0;
}
else
{
return a+multiply(a,b-1);
}
}
}

 

Here you can see the function is calling itself and reusing the old returned value until and unless value becomes 0. We can do factorial and division using the same technique with little bit enhancement.

 

Advertisements

1 million prime number generation in less then half of a second …

This is an optimized code of prime number generation.
This question was asked in an entry test of a software house that how can you generate 1 million prime numbers in less then a second.
I wrote the code that generates the prime number and add to a list in 0.39 seconds to be specific 390.8387 milliseconds.

Important key point here to understand is that except 2 no even number is prime so that is why i have started it from 3 and increment 2 so by this why we will not be checking any even number.
public static void prime()
{
List l = new List(1000000);

l.add(1);
l.add(2);
for (uint i = 3; i < 1000000; i += 2)
{
bool isprime = true;
for (uint j = 3; j*j <= i; j += 2)
{
if (i % j == 0)
{
isprime = false;
break;
}
}
if (isprime == true)
{
l.Add(i);
//Console.WriteLine(i);
}
}
}

And to execute code and also calculate the running time you will need the following code.

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
prime();//Prime Function
stopWatch.Stop();
TimeSpan ts = stopWatch.Elapsed;
string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
ts.Hours, ts.Minutes, ts.Seconds,
ts.Milliseconds / 10);
Console.WriteLine("RunTime " + elapsedTime);
Console.WriteLine("RunTime " + stopWatch.Elapsed.TotalMilliseconds);