Algorithm and puzzles

This space is for technical purpose. It would contain few questions and their solutions (in comments). The space is for my collection and if anyone wants to leverage this collection can use it. Any doubt and suggestions are most welcome.

1. How would you calculate the square root of a number without any built in functions?

Hints: You need to consider boundary conditions. It should be able to find square root of all integers including 0.


2. To find the second max of an integer array.

Hints: It should be done in O(n) complexity.


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




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




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