Which recursive sorting technique always makes recursive calls to sort subarrays that are about half size of the original array?

Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array, resulting in O(n log n) time.

What is the difference between an external iterator and an internal iterator? Describe an advantage of an external iterator.

Ans

An internal iterator is implemented with member functions of the class that has items to step through. .An external iterator is implemented as a separate class that can be "attach" to the object that has items to step through. .An external iterator has the advantage that many difference iterators can be active simultaneously on the same object.

What are the advantages and disadvantages of B-star trees over Binary trees?

Ans
A1 B-star trees have better data structure and are faster in search than Binary trees, but it’s harder to write codes for B-start trees.

Google Puzzle

You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?

Ans
ou simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people.

Euclidean algorithm

Write an algorithm for finding the greatest common divisor of two integers.

Ans
function gcd( a,b : Integer ) returns Integer
{
if ( b != 0 )
return gcd( b, a mod b )
return abs(a)
}

Majority element

Given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible. A majority element in an array of size N is any element which is present more than N/2 times.

Ans
Naive approach:

Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!

One needn't ponder much on the complexity of this bruteforce approach.

This requires O(N) additional space and O(N) time.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

let AL , AR be the first and second halves of A

ML = majority(AL ) and MR = majority(AR )

if neither half has a majority:

return ‘‘no majority’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

Divide a = a1a2 · · · aN by d using long division

Solution

B1 <-- a1 {Bi is what we divide d into in step i}
i <-- 1
while i <= N do
qi <-- largest integer such that d × qi <= Bi; {qi is the ith digit of the quotient q}
if i <= N − 1 then
Bi+1 <-- 10 × (Bi − d × qi) + ai+1
end if
i <-- i + 1;
end while
r <-- BN − d × qN {r is the remainder}

Algorithm Sum N numbers in a list (or array) named values

Solution
sum <-- 0;
index <-- 1;
while index <= N do
sum <-- sum + values[index ];
index <-- index + 1;
end while
print sum;