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

7

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

8

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

12

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

16

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

18

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

19

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);
}