Given an array of integers.....
Imagine it as a pyramid as below:

a[]={1,2,3,4,5,6,7,8,9,10}
1
2 3
4 5 6
7 8 9 10
find a path from level 1 to last level such that the sum is maximum.... The path is such that its children should be reachable.
Ex:
1,2,5,9 is a path
1,2,6,10 is not a path since 6 is not reachable from 2.
The array is not sorted and numbers are random.

int sumPath(int[] a, int i){
int length = a.length();
int n = child(i);
if(n+1 < length)
return a[i] + max(sumPath(n), sumPath(n+1));
else if(n < length)
return a[i] + sumPath(n);
else
return a[i];
}

int child(int i){
// function returns #out for a given #in
//example (in,out) pairs: //(0,1), (1,3) (2,4), (3,6), (4,7), (5,8), (6,10), (7,11) etc.
return (1 + sqrt((double)(8*i + 1))) / 2;
}

It works just like a tree, heap in particular, where nodes are stored in a, say a zero based array and its children are accessed by 2i+1 and 2i+2. in case of a pyramid, inner nodes have two parents. so the function to determine children is slightly different.

And sumpath is just like any recursion tree algo, say to find maxdepth at a node.

Q. No. :

2

Question :

A n-tree where each node contains any no of nodes. Print the nodes in level order and each level must contain a line with a gap

Take two queues Q1, Q2
//each time in any queues only the nodes belong to one level will be present
//hence print all the queue nodes and print new line
enque root into Q1

while Q1!=empty
print node->data and enque the childs of all nodes in Q2

print("\n");
now process Q2,
while Q2!=empty
print node->data;
enque childs of each node in Q1.

print("\n");

if(Q1.empty() and Q2.empty())
break;//we have processes whole tree.

Q. No. :

3

Question :

Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square

Solution must end or begin with 16 since there is only one number in the rest of the list that sums to a perfect square with 16 so it can't be between two of the other numbers.

So you can start with 16 in one list of numbers and the remaining numbers 1-15 in another list and solve it recursively. The following code works and comes up with the solution

class SolutionFinder
{
public static void find(final LinkedList remaining, final LinkedList found)
{
if (remaining.size() == 0) // We made it through the whole list, this is a solution
{
for (final Integer curr : found)
{
System.out.printf("%d ", curr);
}
}
else
{
for (int i = 0; i < remaining.size(); i++)
{
final Integer next = remaining.get(i);
if (Arrays.asList(4, 9, 16, 25).contains(found.get(found.size() - 1) + next))
{
found.add(remaining.remove(i));
find(remaining, found);
remaining.add(i, found.remove(found.size() - 1));
}
}
}
}

public static void main(final String[] args)
{
final LinkedList remaining = new LinkedList();
final LinkedList found = new LinkedList();
for (int i = 1; i <= 15; i++)
{
remaining.add(i);
}
found.add(16);
find(remaining, found);
}
}

Q. No. :

4

Question :

If you have a N steps staircase and you are standing at 1 step now you have options to step up to 2step or you can skip one step and go to 3rd step... so at ith step you have a option to go to i+1 step or i+2 step. So how many ways you can climb the stairs?

The algorithm outlined below solves the longest increasing subsequence problem efficiently, using only arrays and binary searching. For the first time this algorithm was developed by M. L. Fredman in 1975. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the position k of the smallest value X[k] such that k ≤ i (note we have k ≤ j ≤ i here) and there is an increasing subsequence of length j ending at X[k]
P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at P[M[i]]. Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)

The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form

..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].

Because the algorithm performs a single binary search per sequence element, its total time is O(n log n).

Q. No. :

6

Question :

Given a binary tree, find a path (from root to a leaf) which gives maximum value by adding values of nodes.

use hashtable where key is the unique link and its value is the count. so if you get a new in bound check if it already exits if does then increment the value by one else add it to the hashtable with count 1

Q. No. :

8

Question :

You have millions of documents numbered 1,2,3,4,5 ......
You also have a mapping from a word to the list of documents that contains it

Find all the 'pair of words' that occur together in one and only document

It can be done in O(m+n)/O(Max(m,n)) time complexity and O(m*n bits).
We can calculate a BitMap for the given work by setting all the bits corresponding to each file(number). This BitMap will take O(m) space. The BitMap of both words can be compared in o(1) time (any weird insane comparison). The space requirement can be further scaled down by using base + offset value for any BitMap(can be done based on the range of the file index)

Q. No. :

9

Question :

Given n number of points in space and a point P, find 3 nearest point to p.

On first look, this problem appears to be quite simple. Indeed, the solution is possible through a very simple approach: Find the largest of the set, eliminate it and again find the largest of the remainder of the elements.

#include

#define MAXELT 10001

void main()
{
int i=-1,n=0,largest,slargest;
char t[10];
void largest_and_second_largest(int[],int,int&,int&);
int list[MAXELT];

do { //read the list of numbers
if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers ");
gets(t);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);

printf("The largest of the list is %d and the second largest is %d.",largest,slargest);
}

//pre: there must be atleast two numbers in the list
void largest_and_second_largest(int list[],int n,int &largest,int &slargest)
{
int largeindex=0,i;
largest=list[0];
for (i=1;i
if (list[i]>largest) {
largest=list[i];
largeindex=i; //to eliminate the largest later
}
//we have found the largest, stored in largest and its
//index stored in largeindex. Now find the second largest
//ignoring the largest.
if (largeindex==0)
slargest=list[1];
else
slargest=list[0];
for (i=0;i
if (list[i]>slargest && i!=largeindex)
slargest=list[i];
//we have found the second largest
}

Q. No. :

11

Question :

For a given matrix NxN having 0 or 1’s only. You have to find the count of rows and columns where atleast one 1 occurs.

1) Initialize row_count = 0
2) For each row.
a) Do OR of all elements in the row.
b) If OR is 1 then increment the row_count

Similarly, we can count columns with at least one 1.

Time Complexity: O(n^2)
Extra Space: O(1)

Time complexity can be reduced for average case performance of O(n). Worst case will be O(n**2)

Hint: Check all the rows, but need not check all the columns.

Q. No. :

12

Question :

You are provided with a max heap of 'n' elements with a number 'x' and 'k'...You have to find whether 'k' elements in heap are greater than 'x' or not??
Time Complexity should be O(k)

Use a DFS kind of approach. Terminate the recursion at a node when the value is less than or equal to 'x'. Keep incrementing the counter during the procedure. As soon as you encounter the value of counter as 'k' return true, else, when the DFS is complete and still counter<'k' return false.

Answer 1.
Total ways of placing 3 squares on the 8 x 8 grid is 64c3
Total ways in which all 3 squares are diagonal to each other are:
1st and 2nd diagonal rejected becoz in this there are less than 3 squares.
In the remaining diagonals the possible ways are 3c3, 4c3, 5c3, 6c3, 7c3, 8c3
All the ways are repeated again except 8c3.
Similar set of ways are their when we start from lower left corner.
So total number of ways are 2*( 2*(3c3+4c3+5c3+6c3+7c3) + 8c3) = 392
Hence the probability = 392/64c3.

Answer 2.
Total ways of placing squares such that they are adjacent and diagonal to each other are:
From the diagonal with 3 places = 1
......................... with 4 places = 2
.............................. with 5 places = 3
Hence total ways are 2*( 2*( 1 + 2 + 3 + 4 +5) + 6 ) = 72
Hence the probability would be = 72/64c3

Q. No. :

15

Question :

Given a binary tree and a node, print all the ancestors of that node.

The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it

Q. No. :

17

Question :

ind the two nodes in Binary Tree which have longest distance between them.

/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:

int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;

if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right,&rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;

All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.

Q. No. :

19

Question :

Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of

Here k=1 million
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
a) If the element is greater than the root then make it root and call heapify for MH
b) Else ignore it.
O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)

Q. No. :

20

Question :

Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path?

Let s be the source and d be the destination node in the graph G.
1) Find the shortest path between s and d using the given shortest path algo.
Let the shortest path be s ->v1->v2->v3->...vn->d.
2) For each link in set (s->v1, v1->v2, v2-v3, ..... vn->d):
a) break the link in G and get the shortest path of the remaining graph.
b) Add the broken link back.
3) Return the minimum of all shortest paths calculated in step 2.

Q. No. :

21

Question :

Given any number say 12, find the next multiple of 8 eg 16 using bit-wise manipulations.?

Let S is given string, T is reverse of S. Build a generalized suffix tree GST (see Wikipedia) for S and T. Search for the longest common prefix in GST.
example: S = 1232, T = 2321
suffixes of S = {1232,232,32,2}, and of T = {2321,321,21,1}
"232" is the longest common prefix. Even though number of possible suffixes in GST can be O(n^2), it can be collapsed to represent in compact way. As compact GST can be be built in O(n) time with O(n) space,

Q. No. :

27

Question :

There are N nuts and N bolts, all unique pairs od Nut and Bolt
You cant compare Nut with Nut.
You cant compare Bolt with Bolt
You CAN compare Nut with Bolt
Now how would you figure out matching pairs of nut and bolt from the given N nut and Bolt.
The basic soln is O(N^2). Give O(NlogN soln)

Suppose that there are n nuts and bolts. A simple modification of Quicksort shows that there are randomized algorithms whose expected number of comparisons (and running time) are O(n log n): pick a random bolt, compare it to all the nuts, find its matching nut and compare it to all the bolts, thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort

Q. No. :

28

Question :

A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given.
The L length block can't be placed in between to cross it, as it will fall in water (just fitting).
How would you cross using these L length blocks.

-- Difference between malloc and calloc
-- Signatures are different
-- Malloc(s);
-- Allocates byte of memory
-- Returns a pointer for enough storage for an object of s bytes

-- Calloc(n,s);
-- Allocates block of memory
-- Returns a pointer for enough contiguous storage for n objects, each of s bytes
-- The storage is all initialized to zeros
-- Calloc(m, n) is essentially equivalent to
p = malloc(m * n);
memset(p, 0, m * n);

Q. No. :

32

Question :

How would you dynamically allocate 2D array? Use 2 malloc() and then do the same thing using only 1 malloc().

In first statement, we are declaring a function pointer p, which takes 2 arguments (an array 'a' of void pointers and an integer) and returns nothing.
In 2nd statement, we are declaring an array 'p' of function pointers, with 2 arguments ( a void pointer and an integer) and returns a void pointer.

Q. No. :

36

Question :

Write an algorithm to print a binary tree level wise and that too from leaves to root. Also only one queue and one stack can be used for the purpose.

1. Start from root and enqueue to the queue.
2. Dequeue an element and push it to the stack.
3. Enqueue the children from the dequeued node(from step 2).
4. Repeat step 2 and 3 until you reach the leaves.
5. Now print the stack by popping elements until it gets empty.

To find the the longest increasing sequence, we maintain a lookup table, where the ith location indicates the maximum increasing value, for that input.

extending this idea to the current problem. given input is :

{7,8,9},{5,6,8},{5,8,7},{4,4,4}.

the lookup table for this problem should hold at each ith location, the maximum number of boxes that can be filled for the ith input.

to ease the computation we sort (descending) input array with one of the dimensions ( in this case the input is already sorted by length.

formula

Sj= max(Sk)+1 where 0<=k
example:
A - {7,8,9}
B - {5,6,8}
C - {5,8,7}
D - {4,4,4}

0 A B C D
S 0 1 2 2 3

so 3 is the max. # of boxes that can be filled.

Q. No. :

38

Question :

Given a binary matrix, find out the maximum size rectangular sub-matrix with all 1

Algorithm:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
view source
print?
#include
#define bool int
#define R 6
#define C 5

void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Source:geeksforgeeks.com

Q. No. :

39

Question :

What is the difference between >> and >>> in java?

#include
#include
#include
/* The node type from which both the tree and list are built */
struct node {
int data;
struct node* small;
struct node* large;
};
typedef struct node* Node;
/*
helper function -- given two list nodes, join them
together so the second immediately follow the first.
Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b) {
a->large = b;
b->small = a;
}
/*
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
Node aLast, bLast;
if (a==NULL) return(b);
if (b==NULL) return(a);
aLast = a->small;
bLast = b->small;
join(aLast, b);
join(bLast, a);
return(a);
}
/*
--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
Node aList, bList;
if (root==NULL) return(NULL);
/* recursively solve subtrees -- leap of faith! */
aList = treeToList(root->small);
bList = treeToList(root->large);
/* Make a length-1 list ouf of the root */
root->small = root;
root->large = root;
/* Append everything together in sorted order */
aList = append(aList, root);
aList = append(aList, bList);
return(aList);
/* Create a new node */
static Node newNode(int data) {
Node node = (Node) malloc(sizeof(struct node));
node->data = data;
node->small = NULL;
node->large = NULL;
return(node);
}
/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data) {
Node root = *rootRef;
if (root == NULL) *rootRef = newNode(data);
else {
if (data <= root->data) treeInsert(&(root->small), data);
else treeInsert(&(root->large), data);
}
}
static void printList(Node head) {
Node current = head;
while(current != NULL) {
printf("%d ", current->data);
current = current->large;
if (current == head) break;
}
printf("\n");
}
/* Demo that the code works */
int main() {
Node root = NULL;
Node head;
treeInsert(&root, 4);
treeInsert(&root, 2);
treeInsert(&root, 1);
treeInsert(&root, 3);
treeInsert(&root, 5);
head = treeToList(root);
printList(head); /* prints: 1 2 3 4 5 */
return(0);
}

main()
{
int n;
scanf("%d",&n);
int b=n;
int c=0xFFFE,d=1;
while(b&1==1)
{
b=b>>1;
n=n&c;
c=c<<1;
d=d<<1;
}

n=n| d;
printf("\n%d",n);

return 0;
}

Q. No. :

47

Question :

Given a stack S, write a C program to sort the stack (in ascending order).
You are not allowed to make any assumptions about how the stack is implemented; the only
functions allowed to be used are: Push, Pop, Top, IsEmpty, IsFull.

There is a sequence of increasing numbers that have the same number of binary 1^{s} in them. Given n, the number of 1 bits set in each number, write an algorithm
or C program to find the n^{th} number in the series

Let n=3 ,then number series will be like:
0000111,0001011,0001101,0001110
the whole bunch of 1's will slowly shift towards right and every nth number will be having all 1s together.

Pusedo code:: to find kth no of series.(index from 0)
base=0
shift=k/n;
remain=k%n;// a 0 will be there between remain and (n-remain) no of 1s.

You are given have a datatype, say X in C. Determine the size of the datatype,
without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator

Create two hash,
- start hashing first set, put each element as output if collision doesn't occurs.
- start hashing each element of this set, if no collision occurs put that in hash as well as as output.

*Check out for better algorithms

Q. No. :

51

Question :

You have m nuts and n bolts, Every unique nut is fit in every unique bolt, Suggest an effective algorithm for placing each nut in each bolt in less no. of passes?

Suppose that there are n nuts and bolts. A simple modification of Quicksort shows that there are randomized algorithms whose expected number of comparisons (and running time) are O(n log n): pick a random bolt, compare it to all the nuts, find its matching nut and compare it to all the bolts, thus splitting the problem into two problems, one consisting of the nuts and bolts smaller than the matched pair and one consisting of the larger ones. Repeating in this manner yields an algorithm whose expected running time can be analyzed by imitating the known analysis for Quicksort

Q. No. :

52

Question :

Write a program in C to store details of 100 books of a library where
each record contains booknumber, book name, bookauthor, publisher,
number of copies,unit cost.
Read the data from an external file.
Implement insertion of new record
Deletion of existing record
modification of existing record
Find the total worth of the library.

There are four dogs, each at the counter of a large square. Each of the dogs begins chasing the dog clockwise from it. All of the dogs run at the same speed. All continuously adjust their direction so that they are always heading straight towards their clockwise neighbor. How long does it take for the dogs to catch each other? Where does this happen? (Hint: Dog’s are moving in a symmetrical fashion, not along the edges of the square).

This problem can be solved by sorting the array in non increasing order. so array A = { 4,2,1,3,6,9}
becomes = { 9,6,4,3,2,1}
Start processing this array from the beginning and keep the sum of the elements in each of the sets upto that point. now consider next two elements at each step. assign the larger of these to the set with the smaller sum. update the sum and continue this procedure.
so here
9 | 9 3 | 9 3 1
6 | 6 4 | 6 4 2

Q. No. :

55

Question :

How to call a C++ function which is compiled with C++ compiler in C code?

The C++ compiler must know that f(int,char,float) is to be called by a C compiler using the extern "C"construct:

The extern "C" line tells the compiler that the external information sent to the linker should use C calling conventions and name mangling (e.g., preceded by a single underscore). Since name overloading isn't supported by C, you can't make several overloaded functions simultaneously callable by a C program.

// This is C++ code
// Declare f(int,char,float) using extern "C":
extern "C" void f(int i, char c, float x);
...
// Define f(int,char,float) in some C++ module:
void f(int i, char c, float x)
{
.....
}

Q. No. :

56

Question :

How do you initialize a static member of a class with return value of some function?

Static data members are shared by all object instances of that class. Each class instance sees and has access to the same static data. The static data is not part of the class object but is made available by the compiler whenever an object of that class comes into scope. Static data members, therefore, behave as global variables for a class. One of the trickiest ramifications of using a static data member in a class is that it must be initialized, just once, outside the class definition, in the source file. This is due to the fact a header file is typically seen multiple times by the compiler. If the compiler encountered the initialization of a variable multiple times it would be very difficult to ensure that variables were properly initialized. Hence, exactly one initialization of a static is allowed in the entire program.

Consider the following class, A, with a static data member, _id:

//File: a.h
class A
{
public:
A();
int _id;
};

The initialization of a static member is done similarly to the way global variables are initialized at file scope, except that the class scope operator must be used. Typically, the definition is placed at the top of the class source file:

// File: a.cc
int A::_id;

Because no explicit initial value was specified, the compiler will implicitly initialize _id to zero. An explicit initialization can also be specified:

// File: a.cc
int A::_id = 999;

In fact, C++ even allows arbitrary expressions to be used in initializers:

// File: a.cc
int A::_id = GetId(

Q. No. :

57

Question :

If you are given the name of the function at run time how will you invoke the function?

* Compile your program with --export-dynamic on the gcc command line
* Link with -ldl (dynamic library handling, needed for dlopen and dlsym
* Call dlopen() with a null parameter, meaning you aren't loading symbols from a file but from the current executable
* Call dlsym() with the name of the function you'll be calling. Note that C++ modifies function names, so If you're trying this with C++, you'd have to either declare this function as extern "C", or figure out what name the function has after compiling. (On unix, you could run nm -s on the object file for this).
* If dlsym() returns non-null, use the returned value as a function pointer to invoke your function.

For example, a Web browser initiates a request to a server, typically by opening a TCP/IP connection. The request itself comprises o a request line, o a set of request headers, and o an entity. The server sends a response that comprises o a status line, o a set of response headers, and o an entity. The entity in the request or response can be thought of simply as the payload, which may be binary data. The other items are readable ASCII characters. When the response has been completed, either the browser or the server may terminate the TCP/IP connection, or the browser can send another request.

COM is linked to Microsoft and CORBA to UNIX,Moreover, COM objects require installation on the machine from where it is being used .CORBA is ORB (Object request broker) , and also its a specification owned by OMG, which is open. Not owned by a company. So we cannot say that it only belongs to Unix. Corba servers can run on windows NT, and CORBA clients can run on Unix.

Web Service is defined as "a software system designed to support interoperable Machine to Machine interaction over a network." Web services are frequently just Web APIs that can be accessed over a network, such as the Internet, and executed on a remote system hosting the requested services.

Q. No. :

61

Question :

Explain the Traveling Salesman problem? What is an NP-complete problem? What is the Hamiltonian cycle problem?

node_type *create_link_list(int n);
void print_link_list(node_type *root);
node_type *kReverse(node_type *head , int n);
node_type *reverse(node_type *head , int n);
node_type *get_k_th_node(node_type *head , int k);
main()
{
node_type *head;
int n , k;
printf("Give the number of element\n");
scanf("%d",&n);
head=create_link_list(n);
print_link_list(head);
printf("Give the value of k\n");
scanf("%d",&k);
head=kReverse(head , k);
print_link_list(head);
}

#include
int find_smallest_element_position(int *a, int first , int last);
main()
{
int a[10]={4,5,6,7,8,9,1,2,3};
int pos;
pos=find_smallest_element_position(a,0,8);
printf("The smallest element's position is %d\n",pos);
}

int find_smallest_element_position(int *a, int first , int last)
{
int mid;
while(first
{
mid=(first+last)/2;
if(a[mid]>a[last])
{
first=mid+1;
}
else
{
last=mid;
}
}
return first;
}

Q. No. :

66

Question :

You have been given a linked list of numbers.
The size is not know. You need to find out if the number stored
in the list is a palindrome in the best possible optimized manner.

main()
{
int n;
int ret_val=FALSE;
node_type *head;
printf("Give the number of node\n");
scanf("%d",&n);
head=create_link_list(n);;
print_link_list(head);
hroot=head;
ret_val=check_palindrome(head);
printf("ret_val=%d\n",ret_val);

How to find an element in rotated sorted array?
Input 1: array[]={4,5,6,7,8,9,1,2,3}; element=5
Output : position of the element(=5) is 1 (array starts from zero).

Input 2: array[]={1,2,3,4,5,6,7,8,9}; element=7
Output : position of the element(=7) is 6 (array starts from zero).

#include
int find_element_position(int *a, int first , int last , int element);
main()
{
int a[10]={3,4,5,6,7,8,9,1,2};
int pos;
int element;
printf("Give the element\n");
scanf("%d",&element);
pos=find_element_position(a,0,8 ,element);
printf("The smallest element=%d position is %d\n",element , pos);
}

int find_element_position(int *a, int first , int last , int element)
{
int mid;
int pos = -1;
while(first
{
mid=(first+last)/2;
if(a[mid]>element && a[first]<=element)
{
last=mid-1;
}
else
{
first=mid;
}
}
if(a[first]==element)
pos=first;
if(a[last]==element)
pos=last;
return pos;
}

GROUP BY is a way by which we tell the DBMS, to group the retrieved records based on one or more columns so that an aggregate function can be performed on every group of rows.

Q. No. :

69

Question :

Swap two numbers without using a temporarily variable.

use fork() or vfork() to create process on unix.
to terminate process send a kill signal , kill(pid, sigID)

Q. No. :

71

Question :

write a program that accepts two mandatory arguments without using any built in date or time functions . The first argument is a string "[HH:MM {AM|PM}" and the second argument is an integer Which denotes minutes. The minutes get added to the string. The return value or output of the program should be a string of the same format as the first argument. For example AddMinutes("10:23 AM", 13) would return "10:36 AM

Easy question But keep boundary condition in mind.
let from first argument we get hh, mm and meridian = {AM = 0, PM = 1}. from second argument we get x the minutes to be added.
1. mm = (mm+x)%60;
2. hh = ((mm+x)/60+hh)%24
3. if (hh > 12) { meridian = 1-meridian; hh %= 12;}

Write me a function that receives three integer inputs for the lengths of the sides of a triangle and returns one of four values to determine the triangle type (1=scalene, 2=isosceles, 3=equilateral, 4=error). Generate test cases for the function assuming another developer coded the function

Each number represents the first number found after the decimal point when one number is divided by another. The first number, 5 is for 1/2; 6 is for 2/3, 7 is for 3/4, 8 is for 4/5, & so on.

++a means increment & use. a++ means use & increment. i.e use the same value and then increment. This means a temporary is created to hold & use the same value. While a is incremented. So, ++a is faster & it is always better practice to use ++a

Q. No. :

76

Question :

What it wrong with this function:
F1(...){
x = new();
F2();
delete x;
}

F2() has to assume that x has been newed i.e F1() has been called. This results in dependency of F2() on F1(). The design is flawed. If F1 throws an exception, F2 may not be called & memory for x cannot be reclaimed as long as the program is running.

Q. No. :

77

Question :

Given 2 squares on a 2 dimensional plane, find a line that would cut these two squares in half.

Find the centers of the squares and draw a line joining them. Any Line passing the center of the square cuts it in half.

Q. No. :

78

Question :

Suppose you have a 100 files in a directory and you need to find out if a keyword occurs in these files. How would you do it in Unix? How would you do it in Windows?

on Unix:
grep /*
on windows (using a dos command):
find (keyword) (file location & pattern)

Q. No. :

79

Question :

Given a cube. A ant is placed in a corner and cannot move. A spider starts from the opposite corner, and can move along cube edges in any direction (x,y,z) with probablity 1/3. What is the expected number of steps for this spider to get to the ant?

Let x=number of turns to reach ant from starting point.
Let y=number of turns to reach ant from diagonal corner on same face as ant.
Let z=number of turns to reach ant from an adjacent corner to ant.

After one turn the spider will be on a diagonal corner of a common face as the ant. So the mean number of turns from the x position is one more than the mean number from the y position:

E(x)=1+E(y).

Once at a y position there is a 2/3 chance it will then move to a z position, and a 1/3 chance back to an x position:

E(y)=(2/3)*(1+E(z))+(1/3)*(1+E(x)).

If the spider arrives at a z position there is a 1/3 chance it will move to the ant, and a 2/3 chance it will move back to a y position:

E(z)=(1/3)*1+(2/3)*(1+E(y)).

With these three equations and three unknowns it is not difficult to solve for E(x), E(y), and E(z).

Q. No. :

80

Question :

What is: in-order traversal of tree, quick sort in an array

A duck is in circular pond. The duck wants to swim ashore, because it wants to fly off and this particular duck is not able to start flying from the water. There is also a fox, on the shore. The fox wants to eat the duck, but this particular fox cannot swim, so it can only hope to catch the duck when the duck reaches the shore. The fox can run 4 times faster than the duck can swim. Is there always a way for the duck to escape?

(You don't have to remember much linear algebra to understand this -- just the formula for multiplying two symmetric 2x2 matrices:

[ a b ] [ d e ] [ ad + be bd + ce ]
[ b c ] [ e f ] = [ bd + ce be + cf ]

You can then prove the result above by induction: Let

[ 1 1 ]
A = [ 1 0 ]

assume by induction that the equation above is is true for some n, multiply both sides by another power of A using the formula for matrix multiplication, and verify that the terms you get are the same as the formula defining the Fibonacci numbers.)

int M[2][2] = {{1,0}{0,1}}

int fib(int n)
{
matpow(n-1);
return M[0][0];
}

void matpow(int n)
{
if (n > 1) {
matpow(n/2);
M = M*M;
}
if (n is odd) M = M*{{1,1}{1,0}}
}

Q. No. :

83

Question :

A computer has three registers, A, B and R. It has only three instructions:

A->R : Load R with A

B->R : Load R with B

A-R->A : Subtract R from A and store the result in A

Using these instructions how can you do the follwoing?

SELECT *
FROM customer c JOIN orders o ON c.custId=o.custId
JOIN order_items oi ON oi.OrderId=o.OrderId
JOIN inventory i ON oi.invId=i.invId
WHERE c.LName=:lname;

**NB: Breaking Order_items into a separate table to prevent a many-to-many relationship. For interview, this is probably not necessary

Q. No. :

85

Question :

What is static method? What is a static initializer?

A staic method in a class's role is to use the static data members only.
and staic method can be accessed by a static/non-static class object.
But a static method cannot have non-static access to the data-members.
And static method cnnot be constant, volatile and virtual.

Now, static non-class method: A staic keyword in front of a non-class method is used to limit the method scope to the current compilation unit. It has internal linkage and one can use this principal in C for information hiding, while class's static method/data-member has external-linkage.
e.g.
In abc.cpp/c
static void print_some_data()
{
}
is limited in abc.cpp/c only, no other compilation unit in an application can use it.

Q. No. :

86

Question :

Write a method to calculate the acute angle between a clock hour hand and minute hand.

public class Clock{
public static void main(String args[]){
long hours = 3;
long minutes = 15;
// Angle made by the hour hand in hours and minutes
long angle_hour = 30* hours;
double angle_Min_hour = 0.5*minutes;
long mins = 6 * minutes;
System.out.println(angle_hour+":"+angle_Min_hour+":"+mins);
System.out.println("Diff:"+((angle_hour+angle_Min_hour)-mins));
}
}

Q. No. :

87

Question :

Template vs. Inheritance. Why use one over the other?

Templates are useful when a specific behavior is independent of data type on which it operates.
Whereas inheritance is useful when a)code reuse b)more specifically (as in case of polymorphism) you want to have different specific behavior with a generic name for the behavior.

Q. No. :

88

Question :

Given a IP address, Validate the IP address. The IP address lies between [000.000.000.000]-[255.255.255.255] .
IP address is in String, hence you can fetch the characters in the string and move ahead.

Virtual Functions are implemented usign the vtable, which is a table of function pointers for each of the virtual function present in the class.
The class creates a vtable upon call of its constructor. In case of derived class ,base class creates the initial vtable but constructor of derived class over-rides the entry in the vtable if the virtual function is defined in derived class.

Q. No. :

90

Question :

What’s the difference between these two declarations?
struct str1 { … } ;
typedef struct { … } str2 ;

The first form declares a structure tag whereas the second declares a typedef. The main difference is that the second declaration is of a slightly more abstract type — its users don’t necessarily know that it is a structure, and the keyword struct is not used when declaring instances of it.