Re: [algogeeks] Median of BST
@Dhilip
Is it tested ? I doubt your code won't work ?
@Rohit
Can we anyways modify Morris Inorder Traversal process? We can have two
pointers slow(increments once) and fast(increments twice), so that if fast
reaches end or fast->next is end, we can have the median @ slow ?
Correct me If I am wrong.
Thanks and Regards
Kaushik
On Tue, May 18, 2010 at 4:05 PM, dhilip wrote:
> 1)do inorder and reverse inorder traversal
> 2)They will meet at one point or they will cross each other
> 3)That point is the median
> 4)Code for the same.
>
> while(true)
> {
> //inorder traversal
> while(count1<=count2 && flag1)
> {
> if(root)
> {
> push(root);
> root=root->lptr;
> }
> else
> {
> if(!isEmpty(stack1))
> t=pop();
> else
> flag1=false;
> var1=t->data;
> count1++;
> root=t->rptr;
> }
> if(count1==count2)
> {
> if(var1>=var2)
> return var2;
>}
>
>
> }
> //reverse inorder
> while(count2<=count1 && flag2)
> {
> if(root1)
> {
> push(root1);
> root1=root1->rptr;
> }
> else
> {
> if(!isEmpty(stack2))
> t1=pop();
> else
> flag2=false;
> var2=t1->data;
> count2++;
> root1=t1->lptr;
> }
>if(count1==count2)
>{
> if(var1>=var2)
> return var2;
>
> }
> }
>
>
> }
>
> --
> 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...@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 algoge...@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: BST
Sharing link for Morris Inorder http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf Courtesy Rohit On Mon, May 17, 2010 at 3:42 PM, kaushik sur wrote: > @Manish > > Does not a recursive solution [inorder traversal] takes an implicit stack > space ? > Please correct me if I am wrong ? > > @Rahul > > Can you please send us the *morris inorder pdf* link that u have shared > once ? > > Best Regards > Kaushik > -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST
@Manish Does not a recursive solution [inorder traversal] takes an implicit stack space ? Please correct me if I am wrong ? @Rahul Can you please send us the *morris inorder pdf* link that u have shared once ? Best Regards Kaushik -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: frequency
Hi Friends
Hash Map takes 2byte [in Java] for holding a character
So in Amazon -
It takes A - 1
M - 1
Z - 1
O - 1
N - 1
But it's time effective!
Yes it takes additional space for intergers, for each key 4 byte for an
integer!!! :-(
***
public void checkTheFrequency() {
for (int i = 0; i < str.length(); i++) {
char key = str.charAt(i);
if (checkMap.containsKey(key)!=
false) {
int value = checkMap.get(key);
checkMap.put(key, ++value);
} else {
checkMap.put(key, 1);
}
}
*
Best Regards
Kaushik
--
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...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] k the smallest in BST without using static variable
Thanks Rohit! On Sat, May 15, 2010 at 7:13 PM, Rohit Saraf wrote: > there is something called morris inorder traversal. > credits to donald knuth > > > On 5/15/10, kaushik sur wrote: > > Hi Friends > > > > I have encountered the question in sites - "Given a Binary Search > > Tree, write a program to print the kth smallest element without using > > any static/global variable. You can't pass the value k to any function > > also." > > > > I have tried my hands using explicit stack for inorder and keeping a > > non-static count variable. > > > > I welcome any better solution, time and space efficient. > > > > Best Regards > > Kaushik Sur > > > > -- > > 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...@googlegroups.com > . > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > > > > -- > -- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > -- > 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...@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 algoge...@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] k the smallest in BST without using static variable
Hi Friends I have encountered the question in sites - "Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can't pass the value k to any function also." I have tried my hands using explicit stack for inorder and keeping a non-static count variable. I welcome any better solution, time and space efficient. Best Regards Kaushik Sur -- 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...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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;
import java.util.Iterator;
import java.util.Set;
import java.util.Map.Entry;
public class Amazon1 {
private String str;
private HashMap checkMap;
public Amazon1(String s) {
this.str = s;
checkMap = new HashMap();
}
public void checkTheFrequency() {
for (int i = 0; i < str.length(); i++) {
char key = str.charAt(i);
if (checkMap.containsKey(key)!=false) {
int value = checkMap.get(key);
checkMap.put(key, ++value);
} else {
checkMap.put(key, 1);
}
}
/*
* VVI
*/
Set> entry = checkMap.entrySet();
Iterator> iter = entry.iterator();
while(iter.hasNext())
{
Entry pair = iter.next();
System.out.print(" "+pair.getKey()+pair.getValue()+" ");
}
}
public static void main(String[] args) {
Amazon1 test = new Amazon1("amazon");
test.checkTheFrequency();
}
}
***
Correct me if I am wrong.
On Fri, May 14, 2010 at 3:30 PM, divya jain wrote:
> 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 08:50, sharad kumar wrote:
>
>> cant u use a hash map of O(K) where K is distinct elements in
>> string..
>>
>>
>> On Thu, May 13, 2010 at 8:13 PM, jalaj jaiswal > > wrote:
>>
>>> input a character array from the user and output in the following way.
>>> example string is amazon.. then output should be a2m1z1o1n1
>>>
>>> i did it taking a 26 size array... some better solution ??
>>>
>>>
>>> --
>>> With Regards,
>>> Jalaj Jaiswal
>>> +919026283397
>>> B.TECH IT
>>> IIIT ALLAHABAD
>>>
>>> --
>>> 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...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> yezhu malai vaasa venkataramana Govinda Govinda
>>
>> --
>> 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...@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 algoge...@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 algoge...@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: 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 java.util.Iterator;
import java.util.Set;
import java.util.Map.Entry;
public class Amazon1 {
private String str;
private HashMap checkMap;
public Amazon1(String s) {
this.str = s;
checkMap = new HashMap();
}
public void checkTheFrequency() {
for (int i = 0; i < str.length(); i++) {
char key = str.charAt(i);
if (checkMap.containsKey(key)!=false) {
int value = checkMap.get(key);
checkMap.put(key, ++value);
} else {
checkMap.put(key, 1);
}
}
/*
* VVI
*/
Set> entry = checkMap.entrySet();
Iterator> iter = entry.iterator();
while(iter.hasNext())
{
Entry pair = iter.next();
System.out.print(" "+pair.getKey()+pair.getValue()+" ");
}
}
public static void main(String[] args) {
Amazon1 test = new Amazon1("amazon");
test.checkTheFrequency();
}
}
**
Best Regards
Kaushik Sur
On May 14, 3:00 pm, divya jain wrote:
> 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 08:50, sharad kumar wrote:
>
>
>
> > cant u use a hash map of O(K) where K is distinct elements in
> > string..
>
> > On Thu, May 13, 2010 at 8:13 PM, jalaj jaiswal
> > wrote:
>
> >> input a character array from the user and output in the following way.
> >> example string is amazon.. then output should be a2m1z1o1n1
>
> >> i did it taking a 26 size array... some better solution ??
>
> >> --
> >> With Regards,
> >> Jalaj Jaiswal
> >> +919026283397
> >> B.TECH IT
> >> IIIT ALLAHABAD
>
> >> --
> >> 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...@googlegroups.com
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > yezhu malai vaasa venkataramana Govinda Govinda
>
> > --
> > 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...@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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group
> athttp://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 algoge...@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.
