- How would you calculate the square root of a number without any built in functions?
- To find the second max of an integer array.
- You have 3 integer Arrays , say array A, array B and array C. You have to compare whether these arrays are equal, keeping in mind the following things:
- All arrays are un-sorted
- You cant sort the arrays individually before comparing them
- Use optimized algo e.g. do not compare element by element
- You have an array A with 100 elements e.g. A[100]. It has got 60 elements in sorted order (Ascending) and 40 blank spaces.There is another array B, which has 40 elements e.g. B [40] and all of the are filled with values in sorted order (Ascending).Merge array B into array A, so that array A get its all elements filled and also gets sorted in ascending order, including new values from B. Restrictions are
- You can't use third datastrusture of any kind for temporary storage
- You can use some temporary variables
- You can use simple merger sort algo.
- Number of iterations and comparison have to be least possible.
- Given a large array of positive integers, we want to perform a large number of queries. Each query is as follow. For an arbitrary integer A, we want to know the first integer in the array which is greater than or equal A. A log(N) algorithm for each query is sufficient for this problem.
Hints: You need to consider boundary conditions. It should be able to find square root of all integers including 0.
Hints: It should be done in O(n) complexity.
9 comments:
1. To find square root
public static float SquareRoot(int num)
{
if (num < 0) { return -1; };
if (num ==0) { return 0; } // Avoid zero divide
float n = (num / 2) + 1; // Initial estimate, never low
float n1 = (n + (num / n)) / 2;
while (n1 < n)
{
n = n1;
n1 = (n + (num / n)) / 2;
} // end while
return n;
} // end SquareRoot
This uses the Newton Method to calculate roots.
2. Second max of an array
public static void FindSecondMax(int[] arr)
{
int len = arr.Length;
int pos = 0;
int max = arr[0];
//we just need to assign some value
//we will change it based on below for loop
int secondMax = arr[0];
//this loop will help to find 2 different value from array
//and assign then to max and secondMax
for (pos = 1; pos < len; pos++)
{
if (arr[pos] > max)
{
int temp = max;
max = arr[pos];
secondMax = temp;
break;
}
else if (arr[pos] < max)
{
secondMax = arr[pos];
break;
}
}
if (max == secondMax)
{
Console.WriteLine("All elemnets are equal");
}
else
{
//Note the posotion of j. It starts from (pos+1)
//because we have already traversed 0 to pos in above for loop
//this will make sure that we traverse array once and complexity remains O(n)
//u can run it from 0 to len also
for (int j = pos+1; j < len; j++)
{
if (arr[j] > max)
{
int temp = max;
max = arr[j];
secondMax = temp;
}
else if ((arr[j] < max) && (arr[j] > secondMax))
{
secondMax = arr[j];
}
}//end for
Console.WriteLine(secondMax);
}//end else
} // end FindSecondMax
Note:
1.There are couple of ways of doing it but we need way with O(n) complexity i.e. in single traversal. One of the way is to sort it by some efficient algo and get the last but one element.
2.You need to run test cases to test such scenario. Such as array with -ive number, combination of -ive and +ive number, all element equal, combination of +ive,-ive and zero etc.
3. To compare 3 arrays.
public static void compareArray(int[] a, int[] b, int[] c)
{
int temp = 0;
bool unequal = false;
if ((a.Length != b.Length) || ( a.Length != c.Length))
{
Console.WriteLine("array r not equal");
return;
}
for (int i = 0; i < a.Length; i++)
{
for (int j = i+1; j < a.Length; j++)
{
//this loop will fill i with max value
if (a[j] > a[i])
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
if (b[j] > b[i])
{
temp = b[j];
b[j] = b[i];
b[i] = temp;
}
if (c[j] > c[i])
{
temp = c[j];
c[j] = c[i];
c[i] = temp;
}
}
//compare the max value
if ((a[i] != b[i]) || (a[i] != c[i]))
{
unequal = true;
Console.WriteLine("array r unequal");
break;
}
}
if (!unequal)
{
Console.WriteLine("array r equal");
}
}
Note: The logic is based of
1. Compare length of each array ad if they are unequal then declare that atray r unequal.
2. Get the max value of each array in each inner loop and compare. When u find that max value in any iteration r unequal declare array as unequal.
The worst case complexity would be n^2 when the all the element of 3 arrays are equal except the smallest element in each array.
4.In place merging of two array.
public static void InPlaceMerge(int[] large, int[] small)
{
int l = large.Length;
int s = small.Length;
int diff = l - s;
for (int i = 0; i < s; i++)
{
large[diff + i] = small[i];
}
int j = 0, k = 0,temp= 0;
while (k < s)
{
while (j < diff + k)
{
if (large[j] > large[diff + k])
{
temp = large[j];
large[j] = large[diff + k];
large[diff + k] = temp;
j++;
}
else //(large[j] == large[large.Length - small.Length + k])
{
j++;
}
}
j = 0;
k++;
}
Console.WriteLine("Array is merged and sorted now");
foreach (int ii in large)
{
Console.WriteLine(ii.ToString());
}
}
Note:
1.The large array is array A in question and small array is B
2. The complexity in
[sizeof(A)]*[sizeof(B)]
For the Square root , your solution doesnot appear comprehensible . The square root of -8 is 2root2i.Your algo doesnt return that .
Also , more elgant way to find square root is to use modulus operator.// returns remainder.
From the initial estimate i.e float n
try this
for ( i=n;i>=1; i--)
(
if( mod(num/i)==0)
return i;
}
5. To find first max integer from array.
create a parallel array where each element A[i] = max(A[0..i]). Takes O(n) time to build the array, but then queries will be log(n) by binary search.
public static void FindFirstMax(int[] arr,int inputNum)
{
int[] parallelArr = new int[arr.Length];
int max = arr[0];
parallelArr[0] = arr[0];
//create parallel array in O(n)
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > max)
max = arr[i];
parallelArr[i] = max;
}
if(inputNum<=parallelArr[0])
{
Console.WriteLine("Number is " + parallelArr[0]);
return;
}
else if (inputNum > parallelArr[parallelArr.Length - 1])
{
Console.WriteLine("Number is greater than max in array");
return;
}
else
{
int numMax = SearchNum(parallelArr, inputNum);
if (numMax <= parallelArr[0])
Console.WriteLine("Number not found");
else
Console.WriteLine("Number is " + numMax.ToString());
}
}
public static int SearchNum(int[] parallelArr, int inputNum)
{
int length = parallelArr.Length;
int maxNum = parallelArr[0];
//it will find in O(log n)
BinarySearch(parallelArr, 0, length, inputNum,ref maxNum);
return maxNum;
}
public static void BinarySearch(int[] parallArr,int low, int high, int inputNum,ref int maxNum)
{
int mid = (low + high) / 2;
if (parallArr[mid] >= inputNum)
{
if ((parallArr[mid - 1] <= inputNum))
{
maxNum = parallArr[mid];
return;
}
high = mid - 1;
}
else
{
if ((parallArr[mid + 1] >= inputNum))
{
maxNum = parallArr[mid+1];
return;
}
low = mid + 1;
}
if (low < high)
BinarySearch(parallArr, low, high, inputNum, ref maxNum);
}
Note: It use parallel array concept.
I tested for array
int[] arr = {1,2,5,6,8,44,43,34,22,34,21,56,56,56,43,38,21};
Searched for -1,88,44,43,56,21,37,47. It works fine for all such test cases.
private static void SecondMaxArray()
{
int[] numbers = {-10, -20, 0, -30};
if (ValidInputArray(numbers))
{
int firstMax, secondMax;
firstMax = secondMax = numbers[0];
for (int iterator = 0; iterator < numbers.Length; iterator++)
{
if (numbers[iterator] > firstMax && secondMax <= firstMax) //there is new max.
{
secondMax = firstMax; //previous max.
firstMax = numbers[iterator];
}
else if (numbers[iterator] > secondMax) //Ok, the firstMax is still the max, but second max is someone else.
{
secondMax = numbers[iterator];
}
}
//let's print out what we got.
Console.WriteLine("Max is {0}, Second max is {1}", firstMax, secondMax);
}
else
{
Console.WriteLine("Invalid array"); //TODO : Add more information to the error.
}
}
private static bool ValidInputArray(int[] numbers)
{
return numbers.Length > 0 ;
}
and Blogspot acts funny.
The previous post is one of the solutions to the second max in an array problem, perhaps still o(n) but lesser lines of code.
Post a Comment