1. How to find median of a BST?

Find the no. of elements on the left side.
If it is n-1 the root is the median.
If it is more than n-1, then it has already been found in the left subtree.
Else it should be in the right subtree.

2. Define string in an algorithmic notation and an example to support it?

In the algorithmic notation, a string is expressed as any sequence of characters enclosed in single quote marks.
E.g. a single quote contained within a string is represented by two single quotes. Therefore, the string “It is John`s program.” is represented as ‘IT IS JOHN”S PROGRAM.'.

3. What are the two ways through which the Markov algorithm terminates?

A Markov algorithm terminates in one of the two ways.
1) The last production is not applicable
2) A terminal production is applicable
A terminal production is a statement of the form x map to y., where x and y represent the strings in V* and the symbol “.” Immediately follows the consequences.

4. What is the general strategy for Markov Algorithm?

The general strategy in a Markov Algorithm is to take as input a string x and, through a number of steps in the algorithm, transform x to an output string y. this transformation process is generally performed in computers for text editing or program compilation.

5. The most basic tool used to express generating functions in closed form is the closed form expression for the geometric series, which is an expression of the form a+ar+ar2+-------+arn. It can either be terminated or extended indefinitely. What are the restrictions for this geometric series?

If a and r represents numbers, r must not equal1 in the finite case.In the infinite case the absolute value of r must be less than 1.These restrictions don't come into play with Generating functions.

6. Name any three skills which are very important in order to work with generating functions.

The three most important skills which are used extensively while working with generating functions are
1)Manipulate summation expressions and their indices.
2)Solve algebraic equations and manipulate algebraic expressions, including partial function decompositions.
3)Identify sequences with their generating functions

7. Explain about the algorithm ORD_WORDS?

This algorithm constructs the vectors TITLE, KEYWORD and T_INDEX.

8. Explain the function of KWIC_Create?

This algorithm analyses the input phrases and creates the three arrays needed in procedure KWIC_GEN.

9. What is the general algorithm model for any recursive procedure?

Prologue: -Saves the parameters, local variables and returns addresses.
Body: -If the best criterion has been reached: then perform the final computation and go to step3, otherwise, perform the partial computation and go to step1.
Restore the most recently saved parameters, local variables and return address. Go to this return addresses.

10. Give the difference of format between an algorithm and a sub algorithm?

The format used is the same as for algorithms except that a return statement replaces an exit statement and a list of parameters follows the sub algorithms name. Although sub algorithms may invoke each other and that a sub algorithm may also invoke itself recursively

Download Interview PDF

11. Define and state the importance of sub algorithm in computation and its relation ship with main algorithm?

A sub algorithm is an independent component of an algorithm and for this reason is defined separately from the main algorithm. The purpose of a sub algorithm is to perform some computation when required, under control of the main algorithm. This computation may be performed on zero or more parameters passed by the calling routine.

12. Counting set bits in a number

First version:

int CoutSetBits(int Num)
{

for(int count=0; Num; Num >>= 1)
{
if (Num & 1)
count++;
}
return count;
}


Optimized version:

int CoutSetBits(int Num)
{

for(int count =0; Num; count++)
{
Num &= Num -1;
}
}

13. Return Nth the node from the end of the linked list in one pass.

Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;

for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}

14. Write a function that finds the last instance of a character in a string

char *lastchar(char *String, char ch)
{
char *pStr = NULL;

// traverse the entire string

while( * String ++ != NULL )
{
if( *String == ch )
pStr = String;
}

return pStr;
}

15. What is comp.ai.genetic all about?

The newsgroup comp.ai.genetic is intended as a forum for people who
want to use or explore the capabilities of Genetic Algorithms (GA),
Evolutionary Programming (EP), Evolution Strategies (ES), Classifier
Systems (CFS), Genetic Programming (GP), and some other, less well-
known problem solving algorithms that are more or less loosely
coupled to the field of Evolutionary Computation (EC).

16. What is ARCBALL?

Arcball is a general purpose 3-D rotation controller described by Ken Shoemake in the Graphics Interface '92 Proceedings. It features good behavior, easy implementation, cheap execution, and optional axis constraints. A Macintosh demo and electronic version of the original paper (Microsoft Word format)

17. How do I rotate a 3D point?

Assuming you want to rotate vectors around the origin of your coordinate system. (If you want to rotate around some other point, subtract its coordinates from the point you are rotating, do the rotation, and then add back what you subtracted.) In 3-D, you need not only an angle, but also an axis. (In higher dimensions it gets much worse, very quickly.) Actually, you need 3 independent numbers, and these come in a variety of flavors. The flavor I recommend is unit quaternions.

18. How do I find a t value at a specific point on a bezier?

In general, you'll need to find t closest to your search point. There are a number of ways you can do this, there's a chapter on finding the nearest point on the bezier curve. In my experience, digitizing the bezier curve is an acceptable method. You can also try recursively subdividing the curve, see if you point is in the convex hull of the control points, and checking is the control points are close enough to a linear line segment and find the nearest point on the line segment, using linear interpolation and keeping track of the subdivision level, you'll be able to find t.

19. How do I generate a bezier curve that is parallel to another bezier?

You can't. The only case where this is possible is when the bezier can be represented by a straight line. And then the parallel 'bezier' can also be represented by a straight line.

20. How do I rotate a 2D point?

In 2-D, the 2x2 matrix is very simple. If you want to rotate a column vector v by t degrees using matrix M, use

M = {{cos t, -sin t}, {sin t, cos t}} in M*v.

If you have a row vector, use the transpose of M (turn rows into columns and vice versa). If you want to combine rotations, in 2-D you can just add their angles, but in higher dimensions you must multiply their matrices.

21. State the problems which differentiate between recursive procedure and non-recursive procedure?

A recursive procedure can be called from within or outside itself, and to ensure its proper functioning, it has to save in same order the return address so that it return to the proper location will result when the return to a calling statement is made. The procedure must also save the formal parameters, local variables etc.

22. Explain the depth of recursion?

This is another recursion procedure which is the number of times the procedure is called recursively in the process of enlarging a given argument or arguments. Usually this quantity is not obvious except in the case of extremely simple recursive functions, such as FACTORIAL (N), for which the depth is N.

23. Explain about procedural body and computation boxes?

The procedural body contains two computation boxes namely, the partial and final computational boxes. The partial computation box is combined with the procedure call box. The test box determines whether the argument value is that for which explicit definition of the process is given.

24. How can an inductive definition be realized?

An inductive definition of a set can be realized by using a given finite set of elements A and the following three clauses.
1) Basis Clause
2) Inductive clause
3) External clause

25. State recursion and its different types?

Recursion is the name given to the technique of defining a set or a process in terms of itself. There are essentially two types of recursion. The first type concerns recursively defined function and the second type of recursion is the recursive use of a procedure.

Download Interview PDF

26. Define and describe an iterative process with general steps of flow chart?

There are four parts in the iterative process they are
Initialization: -The decision parameter is used to determine when to exit from the loop.
Decision: -The decision parameter is used to determine whether to remain in the loop or not.
Computation: - The required computation is performed in this part.
Update: - The decision parameter is updated and a transfer to the next iteration results.

27. Given a system of N equations whose coefficient matrix A is triangular and is stored in a vector R and the right hand side vector B, this algorithm obtains the solution vector X. Sum is a temporary variable. I am M are integer variables. How to follow the algorithm?

The algorithm is easy to follow. X1 is first computed from the first equation and then substituted in the second to obtain X2 and so on.
Another common application is one in which most of the elements of a large matrix are zeros. In such a case, only the non zero elements need to be stored along with their row and column sub scripts.

28. In Algorithmic context how would you define book keeping operations?

Usually when a user wants to estimate time he isolates the specific function and brands it as active operation. The other operations in the algorithm, the assignments, the manipulations of the index and the accessing of a value in the vector, occur no more often than the addition of vector values. These operations are collectively called as “book keeping operations”.

29. Explain the function SUB in algorithmic notation?

In the algorithmic notation rather than using special marker symbols, generally people use the cursor position plus a substring length to isolate a substring. The name of the function is SUB.
SUB returns a value the sub string of SUBJECT that is specified by the parameters i and j and an assumed value of j.

30. What are the arguments present in pattern matching algorithms?

These are the following arguments which are present in pattern matching
Algorithms.
1) Subject,
2) Pattern
3) Cursor
4) MATCH_STR
5) REPLACE_STR
6) REPLACE_FLAG