int check_palindrome(node_type *root)
{
int ret_val;
if(root)
{
ret_val=check_palindrome(root->next);
if(root->data != hroot->data)
return FALSE;
hroot=hroot->next;
return ret_val;
}
return TRUE;
}
Wednesday, December 8, 2010
LCA : lowest common ancestor
tree_node_type *LowestCommonAncestor( tree_node_type *root , tree_node_type *p , tree_node_type *q) { tree_node_type *l , *r , *temp; if(root==NULL) { return NULL; }
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);
if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
====================================================
Good and easy solution
Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.
Implementation:
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int );
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
====================================================
http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html
Find Lowest Common Ancestor in Binary Tree
Question:-You have a Binary Tree and Two node p , q.
You have to find the first common parent of p and q.
tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
tree_node_type *l , *r , *temp;
if(root==NULL)
{
return NULL;
}
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);
if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);
if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
====================================================
Good and easy solution
Algorithm:
The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.
Implementation:
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int );
/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;
/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;
if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
====================================================
http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html
Find Lowest Common Ancestor in Binary Tree
Question:-You have a Binary Tree and Two node p , q.
You have to find the first common parent of p and q.
tree_node_type *LowestCommonAncestor(
tree_node_type *root , tree_node_type *p , tree_node_type *q)
{
tree_node_type *l , *r , *temp;
if(root==NULL)
{
return NULL;
}
if(root->left==p || root->left==q || root->right ==p || root->right ==q)
{
return root;
}
else
{
l=LowestCommonAncestor(root->left , p , q);
r=LowestCommonAncestor(root->right , p, q);
if(l!=NULL && r!=NULL)
{
return root;
}
else
{
temp = (l!=NULL)?l:r;
return temp;
}
}
}
hight of binary tree
Height of a Binary Tree
For a tree with just one node, the root node, the height is defined to be 0, if there are 2
levels of nodes the height is 1 and so on. A null tree (no nodes except the null node)
is defined to have a height of –1.
The following height function in pseudocode is defined recursively as discussed in
class. It should be easily to add a C++ version to the program binTree1.cpp.
int height( BinaryTree Node t) {
if t is a null tree
return -1;
hl = height( left subtree of t);
hr = height( right subtree of t);
h = 1 + maximum of hl and hr;
return h;
{
For a tree with just one node, the root node, the height is defined to be 0, if there are 2
levels of nodes the height is 1 and so on. A null tree (no nodes except the null node)
is defined to have a height of –1.
The following height function in pseudocode is defined recursively as discussed in
class. It should be easily to add a C++ version to the program binTree1.cpp.
int height( BinaryTree Node t) {
if t is a null tree
return -1;
hl = height( left subtree of t);
hr = height( right subtree of t);
h = 1 + maximum of hl and hr;
return h;
{
Sunday, November 28, 2010
Thursday, November 25, 2010
linux must read
1. http://tldp.org/LDP/tlk/tlk.html
2. http://tldp.org/LDP/khg/HyperNews/get/khg.html
3. http://tldp.org/LDP/khg/HyperNews/get/memory/linuxmm.html
4. http://tldp.org/LDP/khg/HyperNews/get/tour/tour.html
2. http://tldp.org/LDP/khg/HyperNews/get/khg.html
3. http://tldp.org/LDP/khg/HyperNews/get/memory/linuxmm.html
4. http://tldp.org/LDP/khg/HyperNews/get/tour/tour.html
Wednesday, November 24, 2010
interview puzzel
Pirates
Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).
Solution
(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )
solution: most of the time i get people who give answers like “the most senior pirate takes half and divides the rest up among the least senior pirates.” um, you missed the whole point to begin with. sorry.
any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.
now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.
lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.
if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he’s obviously going to keep all the money for himself.
if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. PIRATE 3 REALIZES THAT IF HIS PLAN IS NOT ADOPTED HE WILL BE EXECUTED AND THEY WILL BE LEFT WITH 2 PIRATES. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don’t vote for pirate 3, i get nothing, i should vote for this plan.
now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.
a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn’t want to die and we just showed that 3 has a winning proposal.
so lets sum up at this point
Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100
once you see the pattern it becomes very clear. you have to realize that when a pirate’s plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.
Pirate 1 2 3 4 5
5. 1 0 1 0 98
what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.
hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves (as all fogcreek employees have done so far).
Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).
Solution
(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )
solution: most of the time i get people who give answers like “the most senior pirate takes half and divides the rest up among the least senior pirates.” um, you missed the whole point to begin with. sorry.
any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.
now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.
lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.
if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he’s obviously going to keep all the money for himself.
if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. PIRATE 3 REALIZES THAT IF HIS PLAN IS NOT ADOPTED HE WILL BE EXECUTED AND THEY WILL BE LEFT WITH 2 PIRATES. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don’t vote for pirate 3, i get nothing, i should vote for this plan.
now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.
a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn’t want to die and we just showed that 3 has a winning proposal.
so lets sum up at this point
Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100
once you see the pattern it becomes very clear. you have to realize that when a pirate’s plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.
Pirate 1 2 3 4 5
5. 1 0 1 0 98
what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.
hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves (as all fogcreek employees have done so far).
array and pointer
Q: Since array references decay into pointers, if arr is an array, what's the difference between arr and &arr?
A: The type.
In Standard C, &arr yields a pointer, of type pointer-to-array-of-T, to the entire array. (In pre-ANSI C, the & in &arr generally elicited a warning, and was generally ignored.) Under all C compilers, a simple reference (without an explicit &) to an array yields a pointer, of type pointer-to-T, to the array's first element.
For a simple array
int a[10];
a reference to a has type ``pointer to int,'' and &a is ``pointer to array of 10 ints.'' For a two-dimensional array like
int array[NROWS][NCOLUMNS];
a reference to array has type ``pointer to array of NCOLUMNS ints,'' while &array has type ``pointer to array of NROWS arrays of NCOLUMNS ints.''
See also questions 6.3, 6.13, and 6.18.
A: The type.
In Standard C, &arr yields a pointer, of type pointer-to-array-of-T, to the entire array. (In pre-ANSI C, the & in &arr generally elicited a warning, and was generally ignored.) Under all C compilers, a simple reference (without an explicit &) to an array yields a pointer, of type pointer-to-T, to the array's first element.
For a simple array
int a[10];
a reference to a has type ``pointer to int,'' and &a is ``pointer to array of 10 ints.'' For a two-dimensional array like
int array[NROWS][NCOLUMNS];
a reference to array has type ``pointer to array of NCOLUMNS ints,'' while &array has type ``pointer to array of NROWS arrays of NCOLUMNS ints.''
See also questions 6.3, 6.13, and 6.18.
Subscribe to:
Posts (Atom)