a) Write a function that validates whether a tree is a BST or not.
b) Write a function to find the common ancestor of two given nodes of binary tree.
c) In a BST, value of two of the nodes got exchanged by mistake. Write a function to correct the BST.
d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no.s can be anything. find that majority element in a single pass without using extra space.
e) Find the no. of root nodes in a Binary tree.
f) write a function to create a mirror image of a given binary tree without using recursion.
1).merge two height balanced binary trees to get another height balanced
binary tree.
------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
------------------------------
3) slight modification.(use heap)
find the maximum sum giving combination of k integers.
------------------------------
4)sudoku solver
------------------------------
5)How do you find a loop in a linked list?
1) ptr method
2) Go on reversing the linked list.
Ifyou reach the head again, the list has a loop
------------------------------
6) construct a n element binary tree from its inorder and preorder traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can Partion the inorder array into left and right subtrees. Thus this problem can be solved recursively...}
------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate the blocks...that is the question is to be framed..what datastructure do u think should we use for this????(may be trie,linked list.??)
------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop" them out... the resulting string will be in reverse order !}
------------------------------ ------------------------------
9)def. of tree,graph,linked list.nd many more
------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag value z true,otherwise false.
suppose recursive function access the already traversed node,then we can conclude that this tree z havng loop.}
------------------------------
11) If 'n' is even donfiltered=n/2
Else if 'n' is odd donfiltered=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to find out which number converges to 1 the quickest.
------------------------------
12) sort an array having elements only 0 and 1 in O(n)time and sorting should terminate immediately after array gets sorted.(1. find the first occurence of
1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0. swap them.}
------------------------------
13)findout the median of two sorted arrays as if this is one sorted array with O(1) space constraint.
------------------------------
14)how will you find out that a given binary tree is binary search tree.
(inorder traversal nd check 4 sorted nos.)
{ isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
------------------------------
15) given two node pointers in a binary tree . find out the closest common ancestor of the nodes.
{
int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->
if(root->right!=NULL)
right=postOrderToFindLCA(root-
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
------------------------------
17). Given the root of a binary tree, write a routine to find the depth of the tree.
depth ( Tree T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>
}
------------------------------
18)Given the head pointer of a singly linked list, print the contents of the list in reverse order.
Constraints - O(1) space
print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);
print(head->next);
printf("%d",head->element);
}
------------------------------
19) Algorithm to find the number of ones in the binary form of a given number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d ",count);
}
------------------------------
20)Given a string of length N, find whether there exits an even length palindrome substring.
------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
------------------------------
22) Given N sets of integers( Assume suitable representation), Device an algorithm to print the cross product of N sets, N known at runtime. complexity?
------------------------------
23)Algo to compute determinant of an array[N][N]
------------------------------
24) Array of size N is given, N is even. In this array one entry is repeated n/2 times and the remaining n/2 entries are unique. Write algo to find the repeated value. Complexity?
------------------------------
25)Given an array which represents a tree. Find out the distance between two elements. Distance between tree-nodes is length of their path from one to other through root. Assume array is represented as heap.
------------------------------
26)Convert a tree into doubly linked list such that the elements in the list are in order same as inorder traversal of tree.
------------------------------
27)write a program for Intersection of two sets for general data structures in O(nlogn) complexity or if u can minimise the complexity lower than that it would be great..
------------------------------
28) Can any one come up with generic solution for structurally unique binary search trees if yu are give a set of numbers?
( http://www-math.cudenver.edu/~
------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without branching
int x; // we want to find the min,max of x and y
int y;
int r; // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
------------------------------
30)int v; // we want to find the absolute value of v
int r; // the result goes here
r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
(v >> (sizeof(int) * CHAR_BIT - 1));
------------------------------
30)Compute the sign of an integer
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = !(v & (v - 1)) && v;
------------------------------
32)Reverse bits the obvious way
unsigned int v; // reverse the bits in this
unsigned int t = v << 1; // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~
------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
unsigned int v; // 32 bit word to reverse bit order
int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);
The following variation is also O(lg(N)), however it requires more operations to reverse v. Its virtue is in taking less memory by computing the table entries on the fly.
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
------------------------------
34)Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
confiltered= 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
------------------------------
35)largest sum of contiguous integer
------------------------------
36) Given an array of numbers,How can we find the most frequently occuring element?Without using extra space...
------------------------------
37) If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?.learn general approach
------------------------------
38)absolute value code(2 lines)
------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
------------------------------
40) A version of the "There are three persons X Y Z, one of which always lies".. etc..
------------------------------
41)An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
------------------------------
43)http://www.blackboxjobs.
http://wiki.mattgoyer.com/
Plain Text Attachment [ Scan and Save to Computer | Save to Yahoo! Briefcase ]
1).merge two height balanced binary trees to get another height
balanced
binary tree.
------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
------------------------------
3) slight modification.(use heap)
find the maximum sum giving combination of k integers.
------------------------------
4)sudoku solver
------------------------------
5)How do you find a loop in a linked list?
1) ptr method
2) Go on reversing the linked list.
Ifyou reach the head again, the list has a loop
------------------------------
6) construct a n element binary tree from its inorder and preorder
traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can
Partion the inorder array into left and right subtrees. Thus this problem
can be solved recursively...}
------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate
the blocks...that is the question is to be framed..what datastructure
do u think should we use for this????(may be trie,linked list.??)
------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop"
them out... the resulting string will be in reverse order !}
------------------------------
9)def. of tree,graph,linked list.nd many more
------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag
value z true,otherwise false.
suppose recursive function access the already traversed node,then we
can conclude that this tree z havng loop.}
------------------------------
11) If 'n' is even do n=n/2
Else if 'n' is odd do n=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at
some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to
find out which number converges to 1 the quickest.
------------------------------
12) sort an array having elements only 0 and 1 in O(n)time and sorting
should terminate immediately after array gets sorted.(1. find the first
occurence of
1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0.
swap them.}
------------------------------
13)findout the median of two sorted arrays as if this is one sorted
array with O(1) space constraint.
------------------------------
14)how will you find out that a given binary tree is binary search
tree.
(inorder traversal nd check 4 sorted nos.)
{ isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
------------------------------
15) given two node pointers in a binary tree . find out the closest
common ancestor of the nodes.
{
int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->
if(root->right!=NULL)
right=postOrderToFindLCA(root-
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
------------------------------
17). Given the root of a binary tree, write a routine to find the depth
of the tree.
depth ( Tree T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>
}
------------------------------
18)Given the head pointer of a singly linked list, print the contents
of the list in reverse order.
Constraints - O(1) space
print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);
print(head->next);
printf("%d",head->element);
}
------------------------------
19) Algorithm to find the number of ones in the binary form of a given
number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d ",count);
}
------------------------------
20)Given a string of length N, find whether there exits an even length
palindrome substring.
------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
------------------------------
22) Given N sets of integers( Assume suitable representation), Device
an algorithm to print the cross product of N sets, N known at runtime.
complexity?
------------------------------
23)Algo to compute determinant of an array[N][N]
------------------------------
24) Array of size N is given, N is even. In this array one entry is
repeated n/2 times and the remaining n/2 entries are unique. Write algo to
find the repeated value. Complexity?
------------------------------
25)Given an array which represents a tree. Find out the distance
between two elements. Distance between tree-nodes is length of their path
from one to other through root. Assume array is represented as heap.
------------------------------
26)Convert a tree into doubly linked list such that the elements in the
list are in order same as inorder traversal of tree.
------------------------------
27)write a program for Intersection of two sets for general data
structures in O(nlogn) complexity or if u can minimise the complexity lower
than that it would be great..
------------------------------
28) Can any one come up with generic solution for structurally unique
binary search trees if yu are give a set of numbers?
(http://www-math.cudenver.edu/
------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without
branching
int x; // we want to find the min,max of x and y
int y;
int r; // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
------------------------------
30)int v; // we want to find the absolute value of v
int r; // the result goes here
r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
(v >> (sizeof(int) * CHAR_BIT - 1));
------------------------------
30)Compute the sign of an integer
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy
this, use:
f = !(v & (v - 1)) && v;
------------------------------
32)Reverse bits the obvious way
unsigned int v; // reverse the bits in this
unsigned int t = v << 1; // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~
------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
unsigned int v; // 32 bit word to reverse bit order
int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF,
0x0000FFFF};
v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even
bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive
pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);
The following variation is also O(lg(N)), however it requires more
operations to reverse v. Its virtue is in taking less memory by computing
the table entries on the fly.
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
------------------------------
34)Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1 << s; // So d will be one of: 1, 2, 4, 8, 16,
32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
------------------------------
35)largest sum of contiguous integer
------------------------------
36) Given an array of numbers,How can we find the most frequently
occuring element?Without using extra space...
------------------------------
37) If you had an infinite supply of water and a 5 quart and 3 quart
pail, how would you measure exactly 4 quarts?.learn general approach
------------------------------
38)absolute value code(2 lines)
------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
------------------------------
40) A version of the "There are three persons X Y Z, one of which
always lies".. etc..
------------------------------
41)An array of pointers to (very long) strings. Find pointers to the
(lexicographically) smallest and largest strings.
------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how
can you efficiently find out if there is any element in the second list
that is an element of the first list (fixed list).
b) Write a function to find the common ancestor of two given nodes of binary tree.
c) In a BST, value of two of the nodes got exchanged by mistake. Write a function to correct the BST.
d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no.s can be anything. find that majority element in a single pass without using extra space.
e) Find the no. of root nodes in a Binary tree.
f) write a function to create a mirror image of a given binary tree without using recursion.
1).merge two height balanced binary trees to get another height balanced
binary tree.
------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
------------------------------
3) slight modification.(use heap)
find the maximum sum giving combination of k integers.
------------------------------
4)sudoku solver
------------------------------
5)How do you find a loop in a linked list?
1) ptr method
2) Go on reversing the linked list.
Ifyou reach the head again, the list has a loop
------------------------------
6) construct a n element binary tree from its inorder and preorder traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can Partion the inorder array into left and right subtrees. Thus this problem can be solved recursively...}
------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate the blocks...that is the question is to be framed..what datastructure do u think should we use for this????(may be trie,linked list.??)
------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop" them out... the resulting string will be in reverse order !}
------------------------------ ------------------------------
9)def. of tree,graph,linked list.nd many more
------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag value z true,otherwise false.
suppose recursive function access the already traversed node,then we can conclude that this tree z havng loop.}
------------------------------
11) If 'n' is even donfiltered=n/2
Else if 'n' is odd donfiltered=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to find out which number converges to 1 the quickest.
------------------------------
12) sort an array having elements only 0 and 1 in O(n)time and sorting should terminate immediately after array gets sorted.(1. find the first occurence of
1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0. swap them.}
------------------------------
13)findout the median of two sorted arrays as if this is one sorted array with O(1) space constraint.
------------------------------
14)how will you find out that a given binary tree is binary search tree.
(inorder traversal nd check 4 sorted nos.)
{ isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
------------------------------
15) given two node pointers in a binary tree . find out the closest common ancestor of the nodes.
{
int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->
if(root->right!=NULL)
right=postOrderToFindLCA(root-
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
------------------------------
17). Given the root of a binary tree, write a routine to find the depth of the tree.
depth ( Tree T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>
}
------------------------------
18)Given the head pointer of a singly linked list, print the contents of the list in reverse order.
Constraints - O(1) space
print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);
print(head->next);
printf("%d",head->element);
}
------------------------------
19) Algorithm to find the number of ones in the binary form of a given number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d ",count);
}
------------------------------
20)Given a string of length N, find whether there exits an even length palindrome substring.
------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
------------------------------
22) Given N sets of integers( Assume suitable representation), Device an algorithm to print the cross product of N sets, N known at runtime. complexity?
------------------------------
23)Algo to compute determinant of an array[N][N]
------------------------------
24) Array of size N is given, N is even. In this array one entry is repeated n/2 times and the remaining n/2 entries are unique. Write algo to find the repeated value. Complexity?
------------------------------
25)Given an array which represents a tree. Find out the distance between two elements. Distance between tree-nodes is length of their path from one to other through root. Assume array is represented as heap.
------------------------------
26)Convert a tree into doubly linked list such that the elements in the list are in order same as inorder traversal of tree.
------------------------------
27)write a program for Intersection of two sets for general data structures in O(nlogn) complexity or if u can minimise the complexity lower than that it would be great..
------------------------------
28) Can any one come up with generic solution for structurally unique binary search trees if yu are give a set of numbers?
( http://www-math.cudenver.edu/~
------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without branching
int x; // we want to find the min,max of x and y
int y;
int r; // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
------------------------------
30)int v; // we want to find the absolute value of v
int r; // the result goes here
r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
(v >> (sizeof(int) * CHAR_BIT - 1));
------------------------------
30)Compute the sign of an integer
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = !(v & (v - 1)) && v;
------------------------------
32)Reverse bits the obvious way
unsigned int v; // reverse the bits in this
unsigned int t = v << 1; // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~
------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
unsigned int v; // 32 bit word to reverse bit order
int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);
The following variation is also O(lg(N)), however it requires more operations to reverse v. Its virtue is in taking less memory by computing the table entries on the fly.
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
------------------------------
34)Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
confiltered= 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
------------------------------
35)largest sum of contiguous integer
------------------------------
36) Given an array of numbers,How can we find the most frequently occuring element?Without using extra space...
------------------------------
37) If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?.learn general approach
------------------------------
38)absolute value code(2 lines)
------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
------------------------------
40) A version of the "There are three persons X Y Z, one of which always lies".. etc..
------------------------------
41)An array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
------------------------------
43)http://www.blackboxjobs.
http://wiki.mattgoyer.com/
Plain Text Attachment [ Scan and Save to Computer | Save to Yahoo! Briefcase ]
1).merge two height balanced binary trees to get another height
balanced
binary tree.
------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
------------------------------
3) slight modification.(use heap)
find the maximum sum giving combination of k integers.
------------------------------
4)sudoku solver
------------------------------
5)How do you find a loop in a linked list?
1) ptr method
2) Go on reversing the linked list.
Ifyou reach the head again, the list has a loop
------------------------------
6) construct a n element binary tree from its inorder and preorder
traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can
Partion the inorder array into left and right subtrees. Thus this problem
can be solved recursively...}
------------------------------
7)we are given the answers to a crossword puzzzle...we need to generate
the blocks...that is the question is to be framed..what datastructure
do u think should we use for this????(may be trie,linked list.??)
------------------------------
8)how can v reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop"
them out... the resulting string will be in reverse order !}
------------------------------
9)def. of tree,graph,linked list.nd many more
------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag
value z true,otherwise false.
suppose recursive function access the already traversed node,then we
can conclude that this tree z havng loop.}
------------------------------
11) If 'n' is even do n=n/2
Else if 'n' is odd do n=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at
some point.
You are given a set of numbers (say 65 to 125.Give an efficient soln to
find out which number converges to 1 the quickest.
------------------------------
12) sort an array having elements only 0 and 1 in O(n)time and sorting
should terminate immediately after array gets sorted.(1. find the first
occurence of
1. now find the first occurence of 0.
2. when u are having two marker one at first 1 and other at first 0.
swap them.}
------------------------------
13)findout the median of two sorted arrays as if this is one sorted
array with O(1) space constraint.
------------------------------
14)how will you find out that a given binary tree is binary search
tree.
(inorder traversal nd check 4 sorted nos.)
{ isBST(Node *node){
if(node == NULL)
return TRUE;
if (node->left->data > node->data )
return FALSE;
else
return isBST(node->left);
if(node->right->data < node->data)
return FALSE;
else
return isBST(node->right);
}
------------------------------
15) given two node pointers in a binary tree . find out the closest
common ancestor of the nodes.
{
int postOrderToFindLCA(elem *root,elem a,elem b)
{
if(root==NULL) return 0;
if(root->left!=NULL)
left=postOrderToFindLCA(root->
if(root->right!=NULL)
right=postOrderToFindLCA(root-
if(right+left == 2)
{
printf("I am the LCA%d\n",root->id) ;
return 0;
}
if(root->id == a->id || root->id == b->id)
{
return 1;
}
return (left+right);
}
------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
------------------------------
17). Given the root of a binary tree, write a routine to find the depth
of the tree.
depth ( Tree T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>
}
------------------------------
18)Given the head pointer of a singly linked list, print the contents
of the list in reverse order.
Constraints - O(1) space
print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);
print(head->next);
printf("%d",head->element);
}
------------------------------
19) Algorithm to find the number of ones in the binary form of a given
number "n". An efficient method.
#include
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d ",count);
}
------------------------------
20)Given a string of length N, find whether there exits an even length
palindrome substring.
------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
------------------------------
22) Given N sets of integers( Assume suitable representation), Device
an algorithm to print the cross product of N sets, N known at runtime.
complexity?
------------------------------
23)Algo to compute determinant of an array[N][N]
------------------------------
24) Array of size N is given, N is even. In this array one entry is
repeated n/2 times and the remaining n/2 entries are unique. Write algo to
find the repeated value. Complexity?
------------------------------
25)Given an array which represents a tree. Find out the distance
between two elements. Distance between tree-nodes is length of their path
from one to other through root. Assume array is represented as heap.
------------------------------
26)Convert a tree into doubly linked list such that the elements in the
list are in order same as inorder traversal of tree.
------------------------------
27)write a program for Intersection of two sets for general data
structures in O(nlogn) complexity or if u can minimise the complexity lower
than that it would be great..
------------------------------
28) Can any one come up with generic solution for structurally unique
binary search trees if yu are give a set of numbers?
(http://www-math.cudenver.edu/
------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without
branching
int x; // we want to find the min,max of x and y
int y;
int r; // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
------------------------------
30)int v; // we want to find the absolute value of v
int r; // the result goes here
r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
(v >> (sizeof(int) * CHAR_BIT - 1));
------------------------------
30)Compute the sign of an integer
int v; // we want to find the sign of v
int sign; // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here
f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy
this, use:
f = !(v & (v - 1)) && v;
------------------------------
32)Reverse bits the obvious way
unsigned int v; // reverse the bits in this
unsigned int t = v << 1; // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~
------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:
unsigned int v; // 32 bit word to reverse bit order
int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF,
0x0000FFFF};
v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even
bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive
pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);
The following variation is also O(lg(N)), however it requires more
operations to reverse v. Its virtue is in taking less memory by computing
the table entries on the fly.
unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
------------------------------
34)Compute modulus division by 1 << s without a division operator
const unsigned int n; // numerator
const unsigned int s;
const unsigned int d = 1 << s; // So d will be one of: 1, 2, 4, 8, 16,
32, ...
unsigned int m; // m will be n % d
m = n & (d - 1);
------------------------------
35)largest sum of contiguous integer
------------------------------
36) Given an array of numbers,How can we find the most frequently
occuring element?Without using extra space...
------------------------------
37) If you had an infinite supply of water and a 5 quart and 3 quart
pail, how would you measure exactly 4 quarts?.learn general approach
------------------------------
38)absolute value code(2 lines)
------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
------------------------------
40) A version of the "There are three persons X Y Z, one of which
always lies".. etc..
------------------------------
41)An array of pointers to (very long) strings. Find pointers to the
(lexicographically) smallest and largest strings.
------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how
can you efficiently find out if there is any element in the second list
that is an element of the first list (fixed list).
0 comments:
Post a Comment