Re: [algogeeks] Amazon written test question
Hi,
Construct a BST with 2,1,3. If my understanding is right, now distance
between 2,3 will be 2. Will this algo return the correct answer?.
On Thu, Feb 2, 2012 at 1:43 PM, Manni mbd mbd2...@gmail.com wrote:
Forget my previous post. it useless i think
Firstly there will be only 1 node upwards which will be at a distance
K units from the specified node.
so we can take help of recursion
int kthDistance(node *root, int k ,node *start){
static node * kthUp = NULL;
int distance = -1;
if(node ==NULL) return -1;
else if(node==Start) return 0;
else{
if(node-left){
leftDepth = kthDistance(node-left);
if(leftDepth=0) distance = leftDepth+1;
}
if(node-right distance0){
rightDepth = kthDistance(node-right);
if(rightDepth =0) distance = rightDepth+1;
}
if(distance ==k) kthUp = node;
return distance;
}
.
hope this helps
On 2/1/12, atul anand atul.87fri...@gmail.com wrote:
@Manni : didnt get your algo for upward nodes.
On Wed, Feb 1, 2012 at 2:30 PM, Manni mbd mbd2...@gmail.com wrote:
^same as above..
for upward.. start again from the nodes now distance is distance is
(distance of start node -k) .. if you reach this from the root.. print
it..
also better is we use array rather than using linked list .. as
sorting can be a tedious task in case of link lists !
On 2/1/12, atul anand atul.87fri...@gmail.com wrote:
if it is binary tree then to print the downward node...
we can search for start node and then do level-order traversal or BFS
from
start node till distance K recursively.
no as we want nodes to be printed in sorted order..what we do is
crated
a
linked-list and insert nodes (found in above method) in sorted way.
then print the linked list.
for upward nodes. thinking...
On Wed, Feb 1, 2012 at 9:52 AM, atul anand atul.87fri...@gmail.com
wrote:
are you sure given tree is binary tree and not BST.
if it is BST then we can search start node and then do inorder
traversal
from there.
before thinking printing abt upward node...please confirm if it a
binary
tree or BST.
On Tue, Jan 31, 2012 at 9:27 PM, Dhirendra Singh dps...@gmail.com
wrote:
You are given a function printKDistanceNodes which takes in a root
node
of a binary tree, a start node and an integer K. Complete the
function
to
print the value of all the nodes (one-per-line) which are a K
distance
from
the given start node in sorted order. Distance can be upwards or
downwards.
anyone any idea ?? how to print nodes above the specified node,
Note : we do not have a reference to parent
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Maximize XOR
Given an array of N integers, Find two Numbers with max XOR value. Naive Algorithm is O(N^2), what can be a better approach ? -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Maximize XOR
http://discuss.joelonsoftware.com/default.asp?interview.11.614716 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: merge two sorted list
Why are you using tail recursion when an iterative approach would be
more efficient?
Don
On Feb 23, 3:41 am, rahul sharma rahul23111...@gmail.com wrote:
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a-data = b-data)
{
result = a;
result-next = SortedMerge(a-next, b);
}
else
{
result = b;
result-next = SortedMerge(a, b-next);
}
return(result);
}
a : 10 20 30
b : 10 25 35
wats the o/p??? 10 20 25 30 35
or 10 10 20 25 30
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: merge two sorted list
// Iterative merge
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* head, tail;
// Select first node
if (a-data b-data)
{
head = tail = a;
a = a-next;
}
else
{
head = tail = b;
b = b-next;
}
// Merge lists
while(a b)
{
if (a-data b-data)
{
tail-next = a;
a = a-next;
}
else
{
tail-next = b;
b = b-next;
}
}
// Attach remaining list
tail-next = a ? a : b;
return head;
}
On Feb 23, 3:41 am, rahul sharma rahul23111...@gmail.com wrote:
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a-data = b-data)
{
result = a;
result-next = SortedMerge(a-next, b);
}
else
{
result = b;
result-next = SortedMerge(a, b-next);
}
return(result);
}
a : 10 20 30
b : 10 25 35
wats the o/p??? 10 20 25 30 35
or 10 10 20 25 30
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] merge two sorted list
output is 10 10 20 25 30 On Thu, Feb 23, 2012 at 4:44 PM, Karthikeyan V.B kartmu...@gmail.comwrote: Hi, this logic generates 10 10 20 25 .. and so on it doesn delete the duplicates in the result list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: merge two sorted list
Is the desired behavior to remove duplicates? On Feb 23, 5:14 am, Karthikeyan V.B kartmu...@gmail.com wrote: Hi, this logic generates 10 10 20 25 .. and so on it doesn delete the duplicates in the result list -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: merge two sorted list
tails needs to be updated in while loop also
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, Feb 23, 2012 at 8:19 PM, Don dondod...@gmail.com wrote:
// Iterative merge
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* head, tail;
// Select first node
if (a-data b-data)
{
head = tail = a;
a = a-next;
}
else
{
head = tail = b;
b = b-next;
}
// Merge lists
while(a b)
{
if (a-data b-data)
{
tail-next = a;
a = a-next;
}
else
{
tail-next = b;
b = b-next;
}
}
// Attach remaining list
tail-next = a ? a : b;
return head;
}
On Feb 23, 3:41 am, rahul sharma rahul23111...@gmail.com wrote:
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;
/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);
/* Pick either a or b, and recur */
if (a-data = b-data)
{
result = a;
result-next = SortedMerge(a-next, b);
}
else
{
result = b;
result-next = SortedMerge(a, b-next);
}
return(result);
}
a : 10 20 30
b : 10 25 35
wats the o/p??? 10 20 25 30 35
or 10 10 20 25 30
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Longest Path in A Graph
Thank You very much friends. I ve read algorithm Topological Sorting. First we have to perform the topological sorting ( in Linear Time ) on the graph. Then we can find which is the Longest Path in that ordering. But it works for only DAG ( Directed Acyclic Graphs ). I ve done it. But after performing the topological ordering it is a little bit confusing for me. Could you please get me the better idea that performs in less time complexity. Thank You. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
