Re: [algogeeks] BST

if the tree has parent pointer then we can apply similar approach,, increment and decrenent... and can also be done in O(1) have to poninters pointed to the min and max nodes and them move pointers by checking the sums.. On Fri, May 14, 2010 at 5:03 PM, anna thomas wrote: > @rohit: Divya's solt

Re: [algogeeks] Re: partion of array

Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores

Re: [algogeeks] BST

hmmm i already realised that and even mailed that before :) and if we want to use constant space do not make an array. the bst itself is good enough to do what we are doing. On 5/14/10, anna thomas wrote: > @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than > req sum, incr

Re: [algogeeks] tree question

Strategy: subtract the node value from the sum when recurring down, and check to see if the remaining sum is 0 when you run out of tree. let sum be subsum int * PathSum(struct node* node, int sum) { int i=0; if (subsum == 0) { return(array); } elseif(node==NULL){ return; }

[algogeeks] Re: partion of array

how about 1.sorting the elements 2.moving 2 pointers ; one from first and one from last 3.group the elements that the 2 pointers pointing to until the number of elements it has grouped is less than or equal to half of the arraysize. On May 14, 3:53 pm, Rohit Saraf wrote: > A simple DP should wor

Re: [algogeeks] partion of array

@rohit ... please elaborate On Fri, May 14, 2010 at 4:23 PM, Rohit Saraf wrote: > A simple DP should work. Should it not? > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.

Re: [algogeeks] BST

@rohit my approach for ur array. initially p1 points to 1 and p2 points to 123456 now on adding we get 123457, which is greater than 6 so p2 will now point to 4 now sum is 5 which is less than 6 so now p1 will point to 2. now we get sum=6 which is the sum. so i m able to solve by my technique. corr

Re: [algogeeks] Re: partion of array

@karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow

Re: [algogeeks] BST

@rohit: Divya's soltn works in this way, if the sum of 2 nos is less than req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum, then decrement the 2nd ptr(ptr at end of array) In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6) dec ptr2 1+4 = 5 (sum < 6) inc ptr2: 2+4 =

Re: [algogeeks] Re: BST

with order of n space , we can easily do.. just copy inorder traversal in array.. keep two pointers one at beg and 1 at end increment and decrement accordingly until two pointers meet... but how to do in constant space and O(n) ?? On Fri, May 14, 2010 at 11:17 PM, W Karas wrote: > If you nee

Re: [algogeeks] BST

use a hash table. Add the frst element in the hash table. >From second element, check if the diff (sum - element) is present in the hash table or not. On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf wrote: > @divya : i guess... it wont work. > consider Array {1,2,3,4,123456} > and you want sum 6.

Re: [algogeeks] partion of array

yes u can assume even no of elements.. @ rohit please explain ur ans in detail.. thanks in advance :) On 14 May 2010 16:23, Rohit Saraf wrote: > A simple DP should work. Should it not? > > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of C

[algogeeks] Re: tree from linked list

See the definition of: template bool build(fwd_iter p, size num_nodes) Within the iter subclass, within the base_avl_tree template in: http://wkaras.webs.com/gen_cpp/avl_tree_h.txt On May 2, 9:08 am, divya wrote: > u are given a sorted lnked list construct a balanced binary search > tr

[algogeeks] Re: another google telephone interview question

On May 13, 10:06 am, divya wrote: > This problem was asked in google phone interview. We have N element > array with k distinct keys(No relation between k & N given so assume > k What is the best method to sort this array without using any extra > memory? Please elaborate. If "extra memory" inclu

[algogeeks] Re: median of a bst

On May 14, 3:32 am, divya wrote: > please suggest an efficient algo to find the median of a bst A recursive solution: unsigned count(node_handle_t base) { return(base == null ? 0 : count(left(base)) + 1 + count(right(base))); } val_t max(node_handle_t base) { return(right(base) == null ? va

[algogeeks] Re: BST

Are the node values unsigned? When you say constant space, are you counting call stack space? On May 13, 10:41 am, jalaj jaiswal wrote: > given a bst... find two nodes whose sum is equal to a number k ... in O(n) > time and constant space... > > -- > With Regards, > Jalaj Jaiswal > +919026283397

[algogeeks] Re: BST

If you need an array large enough to hold all tree elements, that is not constant space, it is O(n) space. On May 14, 5:47 am, divya jain wrote: > form a sorted  array from inorder traversal of tree. now take to pointers > one to the beginning of array and other at the end. now check if the sum o

[algogeeks] Re: partion of array

On May 14, 4:51 am, divya wrote: > Algorithm to partition set of numbers into two s.t. diff bw their > sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a);

Re: [algogeeks] 2nd shortest path in a graph

I think... it will work :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 2:20 PM, divya wrote: > Given a graph's shortest path algorithm

Re: [algogeeks] partion of array

A simple DP should work. Should it not? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 4:15 PM, Sathaiah Dontula wrote: > Any assumption

Re: [algogeeks] partion of array

Any assumption like, it has even number of elements and two distinct sets ? Thanks, Sathaiah On Fri, May 14, 2010 at 2:21 PM, divya wrote: > Algorithm to partition set of numbers into two s.t. diff bw their > sum is min and they hav equal num of elements > > -- > You received this message beca

Re: [algogeeks] BST

@divya : i guess... it wont work. consider Array {1,2,3,4,123456} and you want sum 6. @prashant: Is it O(n)? I guess after converting to array and removing all entries > sum, we should start with the smallest element and scan the elements from last till we get some value x which together with the

Re: [algogeeks] compute kth smallest element from union of two lists

You have to take some i nodes from array A and the rest k-i-1 from array B. You do not know i. => Problem is to "Find i" So we do a binary search for that. The value i is acceptable if the (k-i) th element in B is greater than ith element in A. So, i guess you would have got it now. -

Re: [algogeeks] BST

i think it can done like this, assume we have to find 'x' and 'y' wer s='x'+'y' 1) select ith node from tree (from beginning to end) 2) y= s - " ith number (node)" 3) now search for 'y' in BST if we found then there is node such that s= x + y; otherwise no.. -- Prashant Kulkarni || Lokaha Samast

Re: [algogeeks] frequency

Hi Friend Using HashMap in Java *** /* * input a character array from the user and output in the following way. example string is amazon.. then output should be a2m1z1o1n1 */ package questionaire; import java.util.Collection; import java.util.HashMap; impo

[algogeeks] Re: frequency

Hi Friends Correct me If I am wrong. Used HashMap in Java *** /* * input a character array from the user and output in the following way. example string is amazon.. then output should be a2m1z1o1n1 */ package questionaire; import java.util.Collection; import java.util.HashMap; import

Re: [algogeeks] BST

form a sorted array from inorder traversal of tree. now take to pointers one to the beginning of array and other at the end. now check if the sum of element is greater than reqd sum then increment 1st ptr. if their sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd

[algogeeks] partion of array

Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe fr

Re: [algogeeks] compute kth smallest element from union of two lists

sorry bt i dint get the approach. can u please explain a bit more by taking examples...thanks a lot in advance On 14 May 2010 10:12, Rohit Saraf wrote: > This was also asked in my Yahoo! Interview this year. :) > > > -- > Rohit Saraf > Second Year

[algogeeks] MULTICONF-10 Call for papers

MULTICONF-10 Call for papers The 2010 Multi-conference in Computer Science (MULTICONF-10) ( http://www.PromoteResearch.org ) will be held during July 12-14, 2010 at the Imperial Swan Hotel & Suites, located at 7050 South Kirkman Road, Orlando, Florida, 32819-8284

[algogeeks] 2nd shortest path in a graph

Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path? my solution well just a thought... is it something like.assume this is the smallest distance path start->node1->node2->node3->node4->destination (now the graph will be represented by a mat

Re: [algogeeks] frequency

use binary tree and insert in it every character u come across. if the character is already present then increment its count. use this approach if u r nt sure that characters will be only 26 or no. if u r sure there r 26 char then u cn use hash.. plz correct me if i m wrong. thanks On 14 May 2010

Re: [algogeeks] median of a bst

If you maintain the size of the subtree rooted at the nodes, then it will become easier. I guess you can see how. Else, 1) Use any algo to count the number of nodes in the BST.Let it be n. 2) Use morris inorder(no recursion/no stacks-all constraint met ) to traverse the tree. For each node visited

[algogeeks] median of a bst

please suggest an efficient algo to find the median of a bst -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...

[algogeeks] tree question

write a c code to print the path in a tree sum of whose nodes equals a given number.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email