agarwalanshul1987
BAN USERAs per my opinion , there could be multiple ways of solving the same. Assuming the precision request is upto 4 decimal places. Out of the all options, 3rd approach is fastest but could not work in case number is <1
1. Naive Approach -
a. Identify the integer part
b. Identidy the fractional part
Here is the code in c#
public static double findsqrt(double num)
{
if(num < 0)
throw new Exception("Invalid Input");
double i =1, precision = 0.0001;
//identify the integer part
for(i =1; i * i <=num; i++);
//identify the fractional part
for(--i; i*i <= num; i+=precision)
return i-precision;
}
2. Better Approach
a. Use Binary Search using low , mid , high
b. if number < 1 then low = number , high = 1 as 0.16 will have sqrt = 0.4
c. other wise low =1 and high = num and keep iterating till difference is of precision
public static double findsqrt(double num)
{
if(num <0 )
throw new Exception(" Invalid input");
double low =1, high = num, precision=0.0001;
double mid;
if(num <1)
{
low=num;
high=1;
}
while(low <=high)
{
mid = (low+high)/2;
if(mid * mid == num)
return mid;
else if ( mid* mid > num)
high = mid-precision;
else
low = mid+precision;
}
return mid;
}
3. Newton Raphson's Algorithm - It does not works for number less than 1
a. Take a guess which is less than sqrt of a number
b. Therefore, sqrt will be less than number/guess.
c. Keep averaging between these two numbers till difference is of precision.
public static double findsqrt(double num)
{
if(num <1)
throw new Exception(" Invalid input);
double guess = 1, precision =0.0001;
while((num- guess* guess > precision)
|| ( guess* guess - num > precision))
{
guess = (guess + num/guess)/2;
}
return guess;
}
There are two ways to approach the problem(code in C#) -
1.) One way BFS
a.) Create a class to store word and the level of the word from the root.
b.) Maintain a queue of the above class to do BFS.
c.) loop until queue is not empty
d.) For each char replace it with 26 possible chars and check if it exists in dictionary
e.) if found return the level.
2. Biderectional BFS -
a.) In previous solution as we go deeper , the number of words to loop will increase exponentially.
b.) if we consider end word as begin word , we could repeat the same step to find the soultion.
c.) Therefore , if we start from both end and eventually check if we found intermediate target list of words which can eventually form the end word in end list.
d.) Since we are using HashSet , We can save time for lopping through each word at deeper levels.
- agarwalanshul1987 May 22, 2016