Re: [algogeeks] MS Question:WAP to print last n lines of a log file
Both questions look related to me. If the log file is being updated as well simultaneously, you should be able to use Circular queue/buffer for that. On Mon, Mar 4, 2013 at 9:10 AM, Ashish Goel wrote: > Q1. Given a log file, pirnt last n lines. Note that the Log file is being > written into. > Q2. Implement Circular Buffer. > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] help with o/p why 0 comes???
Ya, its looking like the problem of 'i686-apple-darwin11-llvm-gcc-4.2'.
For me as well it shows different outputs.
On Mon, Mar 4, 2013 at 4:45 PM, rohit jangid wrote:
> yup , it is showing
> 0
> 0
>
> on ideone as well . so my gcc compiler
> is i686-apple-darwin11-llvm-gcc-4.2. that can be the reason . from here it
> appears 0 is just a coincidence and it depends on compiler implementation .
> C doesn't define any such behavior.
>
>
> On Mon, Mar 4, 2013 at 3:45 PM, Shubham Sandeep <
> s.shubhamsand...@gmail.com> wrote:
>
>> on my system every time o/p is 0
>> using ubuntu 10.04 ,gcc compiler
>>
>>
>> On Mon, Mar 4, 2013 at 7:34 AM, rohit jangid wrote:
>>
>>> output for me for the previous snippet
>>>
>>> localhost:slingshot rohitjangid$ ./a.out
>>> 1799476872
>>> 1799474584
>>> localhost:slingshot rohitjangid$ ./a.out
>>> 1710327432
>>> 1710325144
>>> localhost:slingshot rohitjangid$ ./a.out
>>> 1856128648
>>> 1856126360
>>> localhost:slingshot rohitjangid$ ./a.out
>>> 1724065416
>>> 1724063128
>>>
>>>
>>> On Mon, Mar 4, 2013 at 7:33 AM, rohit jangid wrote:
>>>
yeah true . one interesting thing I noticed is that if you run this code
#include
int main()
{
int i = 0;
do {
printf ("%d\n",(float)1);
}while(i++ < 1);
return 0;
}
one would expect same output in both the rows but surprisingly it came
different for me every time .
any clues .. why ?
On Fri, Mar 1, 2013 at 12:05 PM, Karthikeyan V.B
wrote:
> O/p will not be 0.
>
> 1.00 is the result which when read as %d takes the decimal value
> of stored in memory - it will not be 1.00 or 0.
>
> Since float is not stored as direct binary in memory as integer is
> stored, instead there's a separate procedure for storing float as binary
> in
> memory
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Rohit Jangid
Graduate
Deptt. of Computer Engineering
NSIT, Delhi University, India
>>>
>>>
>>> --
>>> Rohit Jangid
>>> Graduate
>>> Deptt. of Computer Engineering
>>> NSIT, Delhi University, India
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>>
>>>
>>>
>>
>>
>>
>> --
>> Regards,
>> SHUBHAM SANDEEP
>> IT 3rd yr.
>> NIT ALD.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> Rohit Jangid
> Graduate
> Deptt. of Computer Engineering
> NSIT, Delhi University, India
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks]
In context of C++ 1. Populate the digits of the given number in a vector V 2. call next_permutation() on V 3. print the vector [?] Thanks, Anurag Sharma +91-8712218874 On Tue, Dec 6, 2011 at 2:23 AM, sourabh wrote: > This problem is a direct implication of "next_permutation" defined in C > ++ STL algorithms. > > 1) From the end, keep decrementing till A[i] < A[i+1].. > 2) Now, find the closest element , greater than equal, to A[i] in A[i > +1 ... n]. Say, the index of the found element is "j". > 3) Swap (A[i], A[j]) > 4) Reverse array A[i+1 .. n] > > > > On Dec 6, 12:37 am, Anup Ghatage wrote: > > Hmm here is a thought. > > > > In the given number, check the second digit from the left. > > > > if it is the maximum, find the digit that is the next greater digit from > > the left most digit. > > append it to the start and append all the other numbers in sorted order. > > > > if the second from left isn't the largest, find the next digit that is > > greater than the last digit and swap places with it. > > > > On Mon, Dec 5, 2011 at 11:05 PM, raushan kumar < > raushan.vns2...@gmail.com>wrote: > > > > > Given a number,find the next higher number using the same digits in the > > > number. > > > eg: 15432 :: 21345 > > >14532 > > > > > -- > > > 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. > > > > -- > > Anup Ghatage > > -- > 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. <<330.gif>>
Re: [algogeeks] Amazon telephonic question
for second problem, you can create a stack of having each element as a node having the current value as well as pointer to the next smallest value present below it. This can solve all 3 operations in constant time. Thanks, Anurag On Tue, Jun 28, 2011 at 3:00 PM, vikas wrote: > 1.Given an array of integers and another integer X - create an algorithm to > determine if the sum of any two integers in the array would result in x > 2. design a ADT to implement push(), pop() method as stack, and also has a > getMinElement(). Require that getMinElement() is constant time but > push()/pop() do not have to be constant time at first. Then for improvement, > these three methods are all required to be constant time > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/_meOQF9Qu1AJ. > 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.
Re: [algogeeks] Re: sort in minimum cost
This seems longest increasing subsequence problem to me.. Thanks, Anurag On Mon, Apr 25, 2011 at 9:31 PM, snehal jain wrote: > few eg > input > 4 7 12 3 1 > output 4 7 12 > cost: 4 by removing 3 n 1 > > eg 2 > > 6 3 5 7 12 4 > o/p 3 3 5 7 12 > cost 7 by decrementing 6 by 3 and removing 4 > > eg 3 > > 4 9 8 7 8 > o/p 4 7 7 7 8 > cost 3 by decrementing 9 n 8 > > i hope its clear now.. > > > On Mon, Apr 25, 2011 at 9:16 PM, hary rathor wrote: > >> just tell me >> >> what is input and what will the output. atleast 3 example >> >> -- >> 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.
Re: [algogeeks] Ties The Rope With Minimum Cost ..Interesting For Geeks
I think the greedy method of taking the current minimum sized 2 ropes and
tying them will do. Consider this algo:-
int getMinCost(){
priority_queue pq;
insert all thread sizes to pq;
int sum=0;
while(!pq.empty()){
int a=pq.extractmin(); //O(logn)
int b=pq.extractmin();
sum+=a+b;
pq.push_back(a+b);
}
return sum;
}
Time: O(nlogn)
Let me know if this fails in some case.
Anurag
On Mon, Mar 28, 2011 at 12:11 PM, bittu wrote:
> you are given n ropes,maybe of different length. the cost of tying two
> ropes is the sum of their lengths.Find a way to tie these ropes
> together so that the cost is minimum.
>
>
>
> Thanks
> Shashank
>
> --
> 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.
Re: [algogeeks] pallindrome
Its a repeated question. Please check the archives for your answer. Anurag Sharma On Sat, Jul 24, 2010 at 11:34 PM, dreamer < igolalal...@gmail.com> wrote: > please tell me how to find longest pallindrome in a string in linear > time > > -- > 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] Java Random Method
int getNum(){
int arr[]={104,105,106,108};
return arr[(int)(Math.random()*4)];
}
Anurag Sharma
On Sat, Jun 26, 2010 at 8:43 PM, trdant wrote:
> I have the following sequence of integers: 104,105,106,108 and need to
> write a Java statement to randomly produce one of these numbers. I
> basically need a non-linear random number generator. Any ideas?
>
> Travis
>
> --
> 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] FIND DUPLICATE IN BINARY TREE
@jalaj Tree may have negative values. Anurag Sharma On Fri, Jun 25, 2010 at 7:38 PM, jalaj jaiswal wrote: > first do a traversal of the tree and find the maximum value > now take an auxilarry aray a[MAX].. initialize this array to zero > > now traverse the tree and each time update the value in array > a[valueintree]++; > and keep a check,if the value is 2.if at any time any value is 2 after > incrementing ...the index of array is the duplicate value in tree > > total time O(n)... > > but this method had space constraint... any one better ?? > > On Fri, Jun 25, 2010 at 5:34 PM, RIDER wrote: > >> you are given a binary tree (not a BST) .how to find is there is any >> element which occurs twice and if so what is value ? >> >> -- >> 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. >> >> > > > -- > 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. > -- 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] FIND DUPLICATE IN BINARY TREE
Make a Self Balancing BST like RB Tree or AVL Tree, lets call it T. ( O(n) ) Perform an inorder traversal of the Binary tree and for every element keep it inserting it to T only if its not found in T. If its found, then its repeated. ( O(logn) ) Total Time: O(nlogn) Total Space: O(n) Or use a hashmap instead of RB-Tree Total Time: O(n) Total Space: O(1) Anurag Sharma On Fri, Jun 25, 2010 at 5:34 PM, RIDER wrote: > you are given a binary tree (not a BST) .how to find is there is any > element which occurs twice and if so what is value ? > > -- > 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] FIND DUPLICATE IN BINARY TREE
PS: read 'hashmap' in my previous post as 'hashtable' Anurag Sharma On Fri, Jun 25, 2010 at 5:55 PM, Anurag Sharma wrote: > Make a Self Balancing BST like RB Tree or AVL Tree, lets call it T. ( O(n) > ) > Perform an inorder traversal of the Binary tree and for every element keep > it inserting it to T only if its not found in T. If its found, then its > repeated. ( O(logn) ) > > Total Time: O(nlogn) > Total Space: O(n) > > Or use a hashmap instead of RB-Tree > Total Time: O(n) > Total Space: O(1) > > Anurag Sharma > > > > On Fri, Jun 25, 2010 at 5:34 PM, RIDER wrote: > >> you are given a binary tree (not a BST) .how to find is there is any >> element which occurs twice and if so what is value ? >> >> -- >> 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] BST
I once posted it to my blog. Perhaps its the same you are asking : http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html Anurag Sharma On Mon, Jun 21, 2010 at 1:55 PM, jalaj jaiswal wrote: > CAN ANY 1 GIVE THE ALGORITHM.. HOW TO CONVERT BST TO dLL > > -- > 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. > -- 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] Array Problem
Sorry, this point is already pointed out by Sharad. Anurag Sharma On Thu, Jun 24, 2010 at 4:42 PM, Anurag Sharma wrote: > @jalaj > Your approach will not work, what I perceived from your solution, as in > question the maximum difference S is defined as:- > > S = a[i] - a[j] where* "i>j" > * > Perhaps you forgot that the 'order' of the max and min also matters :) > > > Anurag Sharma > > > > On Mon, Jun 21, 2010 at 10:34 PM, jalaj jaiswal > wrote: > >> traverse the array ...take two variables min and max ... and update them >> ...while traversing. >> finally min will contain the most negative value,,, and max will contain >> the most positive vale... do max-min.. that will be S >> >> On Mon, Jun 21, 2010 at 5:38 PM, amit wrote: >> >>> There is an integer array consisting positive and negative integers. >>> Find maximum positive difference S defined as: >>> >>> S = a[i] - a[j] where i>j >>> and >>> S > 0 >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> 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. >> > > -- 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] triplets summing to zero
Its a repeated question. Kindly search the archives for detailed discussion. Anurag Sharma On Wed, Jun 23, 2010 at 10:55 PM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > sort the array > for each element a[i] > find two elements that sum to -a[i] (this can be done in O(n) ) > > the overall time is O(n^2) > > On 6/23/10, Raj N wrote: > > Given a list of n integers?(negative and positive), not sorted and > > duplicates allowed, you have to output the triplets which sum upto 0. > > > > -- > > 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.
Re: [algogeeks] Array Problem
@jalaj Your approach will not work, what I perceived from your solution, as in question the maximum difference S is defined as:- S = a[i] - a[j] where* "i>j" *Perhaps you forgot that the 'order' of the max and min also matters :) Anurag Sharma On Mon, Jun 21, 2010 at 10:34 PM, jalaj jaiswal wrote: > traverse the array ...take two variables min and max ... and update them > ...while traversing. > finally min will contain the most negative value,,, and max will contain > the most positive vale... do max-min.. that will be S > > On Mon, Jun 21, 2010 at 5:38 PM, amit wrote: > >> There is an integer array consisting positive and negative integers. >> Find maximum positive difference S defined as: >> >> S = a[i] - a[j] where i>j >> and >> S > 0 >> >> -- >> 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. >> >> > > > -- > 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. > -- 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] balance tree
Will not any self balancing BST like RB Tree, AVL Tree etc. work for this case? Anurag Sharma On Sun, Jun 20, 2010 at 4:15 PM, sharad wrote: > Given an incoming stream of sorted numbers construct a binary search > tree. At each stage, you should have a nearly balanced tree. > > -- > 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] Count Structurally different binary tree possible ..
If it is to find out the number of different Full binary trees, then its Catalan number problem: http://en.wikipedia.org/wiki/Catalan_number Anurag Sharma On Sun, Jun 20, 2010 at 3:44 PM, sharad kumar wrote: > u mean to count the different subtrees? > > > On Sun, Jun 20, 2010 at 2:54 PM, RIDER wrote: > >> IF i have given N node binary Search Tree . How to count how many >> Structurally different binary tree are possible in that Tree. >> >> -- >> 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.
Re: [algogeeks] There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
Keep 2 pointers 'start' and 'end' and make them point to start and beginning of the array. Now keep decresing *end* pointer until an odd element is found Keep increasing the *start* pointer until an even element is found swap the elements at start and end Continue the above 3 steps till start wrote: > There is an array of odd and even numbers. Now, sort them in such a > way that the top portion of the array contains odd numbers, bottom > portion contains even numbers. The odd numbers are to be sorted in > descending order and the even numbers in ascending order. You are not > allowed to use any extra array and it has to use a conventional > sorting mechanism and should not do any pre or post processing > > -- > 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]Numbers search in an array
Its a repeated question. I would suggest you checking the archives of this groups for its solution. Anurag Sharma On Fri, Jun 18, 2010 at 8:05 AM, Arunkumar Sreenivasan < thegame.a...@gmail.com> wrote: > Hi, >You are given a set of numbers and another number 'x'. You have to find > if there exists any two numbers, whose sum is equal to 'x'. I have done this > is o(n)log n. Need a more optimized solution. > > regards, > Arun kumar S > > -- > 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] binary tree
Here is the link which fits your need. http://www.coders2020.com/construct-a-tree-given-its-inorder-and-preorder-traversal-strings-similarly-construct-a-tree-given-its-inorder-and-post-order Anurag Sharma On Thu, Jun 17, 2010 at 4:34 PM, divya wrote: > write a code to construct tree from inorder nd preorder traversal.. > > -- > 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] trees
Do a level order traversal, like in BFS, and make the child sibling tree accordingly Anurag Sharma On Wed, Jun 16, 2010 at 11:59 PM, divya wrote: > Given a Parent -Child binary tree ,build the child -sibling version of > it? Minimize the space requirements wherever possible. > > -- > 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] op
Every time the function f() is called, it allocates an entirely new set of
memory location, copies "goodbye" in it and returns its base address.
So even if you assign 'A' to its first location, the first character of the
array allocated by f() will still be 'g' if you call it the next time
Thats what is happening here and you will get output :
*g*
Anurag Sharma
On Wed, Jun 16, 2010 at 8:56 AM, sharad kumar wrote:
> ya i forgot that...considering that plz explain o/p
> i.e
> #include
> char *f()
> {char *s=malloc(8);
>strcpy(s,"goodbye");
>return s;
>
> }
>
> main()
> {
> *f()='A';
> printf("%c",*f());
> }
>
> --
> 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] Stack Space for Quick Sort vs Merge Sort.
Thats what he is referring to :) Anurag Sharma On Tue, Jun 15, 2010 at 4:49 PM, Amit Jaspal wrote: > But what about the Stack Space Used while doing Merge and Quick Sort? > > On Mon, Jun 14, 2010 at 9:30 AM, Anurag Sharma wrote: > >> Seems correct to me :) >> >> Anurag Sharma >> >> >> >> On Sun, Jun 13, 2010 at 11:23 PM, amit wrote: >> >>> Can anyone tell what is Stack Space required for Quick Sort and Merge >>> Sort.And how in each case it can be modified. >>> >>> Correct me if I am wrong on this. >>> Space Complexity of Merge Sort ( Not Inplace) - O(n) >>> Space Complexity of Quick Sort - O(1) >>> >>> -- >>> 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. > -- 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] copy
p may not always be > (n-1) as perceived from the initial question.
Like consider copying all the bits of x to y
Anurag Sharma
On Tue, Jun 15, 2010 at 7:02 PM, mohit ranjan wrote:
> @Sharad
>
> assuming p>(n-1)
>
> o/p=
> x & [ ~ { (~((~0)
>
>
> Mohit
>
>
> On Tue, Jun 15, 2010 at 2:10 PM, sharad wrote:
>
>> CopyBits(x,p,n,y)
>> write c code to copy n LSBs from y to x starting LSB at 'p'th
>> position using bitwi se.
>>
>> --
>> 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.
Re: [algogeeks] BST...doubt.......
@sharad height will be log2(n) only in case of balanced BST. what if its terribly unbalanced, you may get height as 'n' as well ! :) So you will have to go till the bottom of the tree to see the depth and find the height accordingly. Anurag Sharma On Wed, Jun 16, 2010 at 9:12 AM, Anurag Sharma wrote: > height of current node = max(height of left child, height of right child) > +1 > > Hope now you get that? :) > > Anurag Sharma > > > On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar wrote: > >> Write a pseudo code 4 that..using c/c++... >> >> how can we find the depth(height) of 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...@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] BST...doubt.......
height of current node = max(height of left child, height of right child) +1 Hope now you get that? :) Anurag Sharma On Tue, Jun 15, 2010 at 5:31 PM, ajay kumar wrote: > Write a pseudo code 4 that..using c/c++... > > how can we find the depth(height) of 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...@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] op
did you forget to return any value from function f() ?
Anurag Sharma
On Mon, Jun 14, 2010 at 7:19 PM, sharad wrote:
> #include
> char *f()
> {char *s=malloc(8);
>strcpy(s,"goodbye");
> }
>
> main()
> {
> *f()='A';
> printf("%c",*f()); }
>
>
> find o/p n explain it
>
> --
> 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] Best method to choose a quadrant
just check the signs of the i, j components of vector from the centre of
screen to (x,y)
pseudo code:-
getQuadrant(x,y){
string Q[]={"1st","4th","2nd", "3rd"};
vx=(x>=midx)?0:1
vy=(y>=midy)?0:1
return Q[(vx<<1)|vy]
}
Anurag Sharma
On Mon, Jun 14, 2010 at 5:55 PM, siddharth srivastava
wrote:
> I have this code snippet:
> This code snippet defines a boundary coordinates on the screen wrt to the
> center(of the screen).
>
> if( x < x_center )
> x_border = x_center - x_shift;
> else
> x_border = x_center + x_shift;
>
> if( y < y_center )
> y_border = y_center - y_shift;
> else
> y_border = y_center + y_shift;
>
> //x_shift and y_shift are constants.
>
> What is the best possible way to determine in which quadrant( wrt to the
> center) the point (x,y) lies ?
>
>
> Siddharth Srivastava
>
>
> --
> 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: unique number in an array
Guys, XOR operation you are suggesting wont work, as a number can be
repeated more than 2 times or may not be even number of times. Check the
example given by him:-
*a[]={1,3,4,1,4,5,6,1,5}*
Here 1 is repeated 3 times, and which certainly is not the unique element
but will leave its affect on XOR thing :)
Anurag Sharma
On Mon, Jun 14, 2010 at 5:14 PM, Modeling Expert <
cs.modelingexp...@gmail.com> wrote:
> use hash table , and if you find for a number , a entry already
> exists , mark it unwanted !
> in the end , hash table entries are unique numbers .
>
> @kunzmilan : could you explain a bit more, couldn't get full idea of
> what you wrote
>
> -Manish
>
> On Jun 14, 1:19 pm, kunzmilan wrote:
> > Write the array as a vector string S, eg
> > (1,0,0,0...)
> > (0,0,1,0...)
> > (0,0,0,1...)
> > etc.
> > Find the quadratic form S^T.S. On its diagonal, occurences of all
> > numbers are counted.
> > kunzmilan
> >
> > On 13 čvn, 20:44, jalaj jaiswal wrote:
> >
> > > give an algo to find a unique number in an array
> >
> > > for eg a[]={1,3,4,1,4,5,6,1,5}
> >
> > > here 3 is the unique number as it occur only once... moreover array
> contains
> > > only 1 unique number
> >
> > > --
> > > 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.
>
>
--
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] Stack Space for Quick Sort vs Merge Sort.
Seems correct to me :) Anurag Sharma On Sun, Jun 13, 2010 at 11:23 PM, amit wrote: > Can anyone tell what is Stack Space required for Quick Sort and Merge > Sort.And how in each case it can be modified. > > Correct me if I am wrong on this. > Space Complexity of Merge Sort ( Not Inplace) - O(n) > Space Complexity of Quick Sort - O(1) > > -- > 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: bits
@jalaj
endian specific.
Anurag Sharma
On Sun, Jun 13, 2010 at 11:54 PM, Modeling Expert <
cs.modelingexp...@gmail.com> wrote:
> @jalaj
>
> Yes , this is endian ness specific. On windows/x86 linux which are
> little endian, ch[0] would be lower 8 bits. On solaris/power pc which
> are big endian this would be upper 8 bits. e.g.
> union a temp;
> temp.i = 0x12345678 //! here big end is 0x12 and little end is 0x78
> then temp.ch[0] = 78 //! Little end first for little endian
>
> and temp.ch[0] = 0x12 for big endian
>
>
>
> On Jun 13, 9:18 pm, jalaj jaiswal wrote:
> > hey i too have a doubt... and its just 1 ... i'll not ask c/c++ again,,,
> >
> > we have a union a{
> >int i;
> >char ch[4];
> > }
> > int here is of 4 bytes.
> > i initialise i=512...
> > what value will ch[0] get the upper 8 bits or the lower 8 bits... is it
> big
> > endian or little endian dependent... please explain this ??
> >
> > On Sun, Jun 13, 2010 at 9:43 PM, Rohit Saraf <
> rohit.kumar.sa...@gmail.com>wrote:
> >
> >
> >
> > > I agree mass bombarding with such questions is not very good.. but one
> > > doesn't join groups and all for getting a few doubts cleared.
> > > Anyways, i have no problem with anything. :D
> >
> > > --
> > > 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>
> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >
> > > On Sun, Jun 13, 2010 at 9:26 PM, souravsain
> wrote:
> >
> > >> and @rohit you will get better insight into the topic by more expert
> > >> people by posting the question in right forum. I guess thats a win-win
> > >> situation for one who has the question as he is get to know more and
> > >> for people you are interested in going through C++ questions as they
> > >> will read views from many more experts :)
> >
> > >> On Jun 13, 7:31 pm, Rohit Saraf wrote:
> > >> > @Souravsain : Is there any serious problem in this. Anyone can just
> add
> > >> a
> > >> > [C++] in the subject and uninterested people can make filters in
> gmail
> > >> :)
> >
> > >> > --
> > >> > Rohit Saraf
> > >> > Second Year Undergraduate,
> > >> > Dept. of Computer Science and Engineering
> > >> > IIT
> > >> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
> <http://www.cse.iitb.ac.in/%7Erohitfeb14>
> >
> > >> > On Sun, Jun 13, 2010 at 6:35 PM, souravsain
> > >> wrote:
> > >> > > @divya
> >
> > >> > > Lets keep discussions in t his group limited to Algos and problems
> > >> > > neutral to any language.
> >
> > >> > > Request you to post these C++ / C language specific questions to
> those
> > >> > > language specific groups. This will not only help this group
> remain
> > >> > > confined to its core purpose but will help you get better insights
> to
> > >> > > ur problem by language specific geeks there. For C++ I would
> recommend
> > >> > > you to try the group
> > >> > >
> http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
> >
> > >> > > Regards,
> > >> > > Sourav
> >
> > >> > > On Jun 13, 2:29 pm, divya wrote:
> > >> > > > tell the o/p of following with explanations
> >
> > >> > > > 1. #include
> > >> > > > int main()
> > >> > > > {
> > >> > > > struct value
> > >> > > > {
> > >> > > > int bit1:1;
> > >> > > > int bit3:4;
> > >> > > > int bit4:4;
> >
> > >> > > > }bit;
> >
> > >> > > > printf("%d\n",sizeof(bit));
> > >> > > > return 0;
> >
> > >> > > > }
> >
> > >> > > > 2.
> > >> > > > #include
> > >> > > > int main()
> > >> > > > {
> > >> > >
Re: [algogeeks] tower of hanoi variation
I think there should be additional constraint added that atmost 1 disk can be placed in ground. Otherwise one can place all disks on ground and put them in order in the last peg :D Anurag Sharma On Mon, Jun 14, 2010 at 2:01 AM, jalaj jaiswal wrote: > give the algorithm for toi if... the a disk can be placed on top the disk > just larger then it and on the ground.. > > -- > 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. > -- 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] Towers of hanoi
Use iterative version :http://en.wikipedia.org/wiki/Tower_of_Hanoi Anurag Sharma On Mon, Jun 14, 2010 at 12:36 AM, ANUJ KUMAR wrote: > http://www.spoj.pl/problems/HAN01/ > i implemented it using stack but am getting tle someone please help > > -- > 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] unique number in an array
Are all the numbers within some given range?
If so then keep a count of all and later find out the non repeating one.
otherwise, make a balanced BST and insert every element in it and increment
the counter of the node if already present in the tree and then do inorder
traversal to find out the non repeating element.
Anurag Sharma
On Sun, Jun 13, 2010 at 11:44 PM, jalaj jaiswal
wrote:
> give an algo to find a unique number in an array
>
> for eg a[]={1,3,4,1,4,5,6,1,5}
>
> here 3 is the unique number as it occur only once... moreover array
> contains only 1 unique number
>
>
>
> --
> 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.
>
--
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] stack
Why not just pop all elements from stack ( O(n) ) and insert it in a self balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and inorder traversal ( O(n) )and push elements in stack again. Time = O(nlog(n) + n) Space=O(n) (for storing the tree) Anurag Sharma On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha wrote: > Stack can be sorted in O(n^2). > > @sankalp: > Stack can always be sorted. Why do you think it cant be in some cases ? > > One can think like insertion sort > algo : > 1. for i in (1,n) > 2. Pop up the top n-1 element and keep nth element in global variable say > "hold" > 3. while pushing get the position for "hold" and push it there > > for loop will take O(n) and step 2 will take take O(n) time. So overall > O(n^2) complexity > Program can be done with recursion using a variable (hence O(1) space). But > it will use system stack :) > > > Any comments OR better solution is welcomed?? > > -- > Regards > Jitendra Kushwaha > MNNIT, 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. > -- 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] union- c
Check the floating point representation(IEEE 754 format) in variables. There
are specific number of bits in a float variable to represent exponent,
mantissa etc.
Anurag Sharma
On Sun, Jun 13, 2010 at 1:19 PM, divya jain wrote:
> its an o/p questn..
> conversion wen ur variable is long..nd u r printing using %f...i dont know
> how to perform conversion from float to int long nd vice versa..
> pl help
>
>
> On 13 June 2010 12:12, Rohit Saraf wrote:
>
>> what is this for...
>> and which conversion are you talking abt?
>>
>> --
>> 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>
>>
>>
>> On Sat, Jun 12, 2010 at 11:20 PM, divya wrote:
>>
>>> #include
>>> main()
>>> {
>>> union {
>>> long l_e;
>>> float f_e;
>>> } u;
>>>
>>> long l_v;
>>> float f_v;
>>> l_v = u.l_e = 10;
>>> printf("%f ", (float)l_v);
>>> printf("%f ", u.f_e);
>>> f_v = u.f_e = 3.555;
>>> printf("%d ", (long)f_v);
>>> printf("%d ", u.l_e);
>>> }
>>> hw to do the conversion here..
>>>
>>> --
>>> 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.
>
--
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: identify the recurring part for a given decimal no
Since we are given numerator 'n' and denominator 'd' separately already. and
considering n and d as integers and d!=0 we can safely assume n/d as either
a terminating fraction or a non terminating but recurring fraction, in which
case we have to find the recurring digits of the fraction.
Now what I suggested was almost same as Ravi's approach.
take a Set 'S' keeping tuples (R,Q) where R is the current remainder and Q
is the factor such that d*Q is subtracted from the number to get R.
In other words. if at an intermediate step of division we have 'a' as the
divident left then Q=floor(a/d) and R=a%d
Keep dividing 'n' by 'd' like it is done manually. After every division
check-
1. If the current remainder is not present in 'S' then add current remainder
'R' and corresponding quotient 'Q' in the set
2. If R is found in the set S, then all the following entries in the set
until end will constitute the recurring digits.
taking Ravi's example:-
Example:
7) 9 (1.*285714*28S=[]
7
--
20 S=[(2,2)]
14
---
60S=[(2,2), (6,8)]
56
---
40 S=[(2,2), (6,8), (4,5)]
35
---
50 S=[(2,2), (6,8), (4,5),
(5,7)]
49
---
10 S=[(2,2), (6,8), (4,5),
(5,7), (1,1)]
7
30 S=[(2,2), (6,8), (4,5),
(5,7), (1,1), (3,4)]
28 ^
|
20 2 is found in S here,
so recurring digits are "285714"
14
60
56
repeats
hope its clear
Anurag Sharma
On Sat, Jun 12, 2010 at 4:02 PM, divya jain wrote:
> @anurag
>
> i dint get ur approach..which numerator n denominator u r talking
> about..plz explain.. thanks in advance
>
> On 11 June 2010 08:57, Anurag Sharma wrote:
>
>> Please note that the fractional repeating part is recurring. and so that
>> 4th temporary variable assignment will be this way->
>> temp=x*1 - x= 233456.34563456... - 23.34563456 = 233433.0 ( mark
>> the fractional part is 0 now since the infinitely repeating 3456... will get
>> cancelled)
>> In this case you can say that 4 places are repeating. But yes its
>> according to the maths and in any programming language whenever you divide
>> the numerator and denominator you wont get this infinitely recurring decimal
>> places.
>>
>> @divya, also your approach wont work if the recurring fractional digits
>> start after few places from the decimal like in the case of
>> 23.123345634563456 (note here after the decimal place 123 is not
>> repeating while 3456.. after this 123 is repeating.)
>>
>> What I suggest in this case is keep dividing the numerator by denominator
>> and at every step keep inserting the tupple (remainder, quotient) of that
>> division step in a set. and before inserting in the set check whether it
>> already exists. If yes then the all the quotients following from that point
>> (including the point) will be recurring.
>>
>> Regards,
>>
>> Anurag Sharma
>>
>>
>>
>> On Thu, Jun 10, 2010 at 8:25 AM, Veer Sharma
>> wrote:
>>
>>> Seems it wont work...
>>> x=23.34563456
>>>
>>> temp = x*100 -x = 233.4563456 - 23.34563456 = 210.11071104
>>> temp = x*100 -x = 2334.563456 - 23.34563456 = 2311.21782144
>>> temp = x*1000 -x = 23345.63456 - 23.34563456 = 23322.28892544
>>> temp = x*1 -x = 233456.3456 - 23.34563456 = 233432.6544
>>> temp = x*10 -x = 2334563.456 - 23.34563456 = 2334540.11036544
>>>
>>> ...
>>>
>>> On Jun 9, 11:24 pm, Anurag Sharma wrote:
>>> > multiply the original number x=23.34563456
>>> >
>>> > Anurag Sharma
>>> >
>>> > On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma <
>>> thisisv...@rediffmail.com>wrote:
>>> >
>>> >
>>> >
>>> > > One question:
>>> >
>>> > > No x = 23.34563456
>>> > > temp = x X 10 = 233.4563456
>>> > > temp = temp - x = 21
Re: [algogeeks] stack
Is it without having the need to shift elements at all? Anurag Sharma On Fri, Jun 11, 2010 at 3:41 PM, jalaj jaiswal wrote: > Give an algorithm to implement n stacks in an array... take care of the > empty space too i.e no overflow shld occur if there is eny empty space left > . > > > > > -- > 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. > -- 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] Common elements in 2 circular linked lists
Ya that will do.. Anurag Sharma On Fri, Jun 11, 2010 at 7:08 PM, Raj N wrote: > Given a circular linked list, what is the most efficient way of > constructing a new list which contains the common elements between the > 2 given lists. > > Is it sorting and then comparing ? > > -- > 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: identify the recurring part for a given decimal no
Please note that the fractional repeating part is recurring. and so that 4th temporary variable assignment will be this way-> temp=x*1 - x= 233456.34563456... - 23.34563456 = 233433.0 ( mark the fractional part is 0 now since the infinitely repeating 3456... will get cancelled) In this case you can say that 4 places are repeating. But yes its according to the maths and in any programming language whenever you divide the numerator and denominator you wont get this infinitely recurring decimal places. @divya, also your approach wont work if the recurring fractional digits start after few places from the decimal like in the case of 23.123345634563456 (note here after the decimal place 123 is not repeating while 3456.. after this 123 is repeating.) What I suggest in this case is keep dividing the numerator by denominator and at every step keep inserting the tupple (remainder, quotient) of that division step in a set. and before inserting in the set check whether it already exists. If yes then the all the quotients following from that point (including the point) will be recurring. Regards, Anurag Sharma On Thu, Jun 10, 2010 at 8:25 AM, Veer Sharma wrote: > Seems it wont work... > x=23.34563456 > > temp = x*100 -x = 233.4563456 - 23.34563456 = 210.11071104 > temp = x*100 -x = 2334.563456 - 23.34563456 = 2311.21782144 > temp = x*1000 -x = 23345.63456 - 23.34563456 = 23322.28892544 > temp = x*1 -x = 233456.3456 - 23.34563456 = 233432.6544 > temp = x*10 -x = 2334563.456 - 23.34563456 = 2334540.11036544 > > ... > > On Jun 9, 11:24 pm, Anurag Sharma wrote: > > multiply the original number x=23.34563456 > > > > Anurag Sharma > > > > On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma >wrote: > > > > > > > > > One question: > > > > > No x = 23.34563456 > > > temp = x X 10 = 233.4563456 > > > temp = temp - x = 210.11071104 > > > decimal part zero? No. > > > Now multiply the no. with 100. Which no? original x (= 23.34563456) or > > > new no. temp (=210.11071104)? > > > > > On Jun 9, 8:12 pm, divya jain wrote: > > > > multiply the no. with 10 nd store in temp. now subtract no from temp. > > > check > > > > if the decimal part is zero if yes. then 1st digit after decimal is > > > > recurring. if no. multiply the no with 100 and repeat . if this time > > > decimal > > > > part is zero then 2 digits after decimal r recurring nd so on.. > > > > > > On 8 June 2010 21:45, Veer Sharma wrote: > > > > > > > You have a Numerator and Denominator. After division you might get > a > > > > > recurring decimal points float as the answer. > > > > > > > Problem is: You need to identify the recurring part for a given > > > > > decimal no? > > > > > For example 23.34563456 ... > > > > > return 3456 > > > > > > > -- > > > > > 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.-Hide quoted text - > > > > > > - Show quoted text - > > > > > -- > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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] c output
printf returns number of successfully printed characters.
so printf("1\n") will return 6
and printf("c\n") will return 2
due to the extra '\n' character which is also being printed
I hope the output is now clear
Anurag Sharma
On Fri, Jun 11, 2010 at 12:26 AM, divya wrote:
> #include
> main()
> {
> int a = 1;
> char b='c';
> int i,j;
>
> printf("%d,%d",printf("%d\n",a),printf("%c\n",b));
>
> wat shd b the o/p of this..plzz explain y?
>
> --
> 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] level order traversal
If a doubly Linked List is made out of this, then there should be kept some mechanism to keep the parent pointer in it and update it while creating and then we can proceed in similar approach as my array solution above. Anurag Sharma On Thu, Jun 10, 2010 at 7:09 PM, sharad kumar wrote: > @ anurag we dont hve parent poiner > hey can we do this problem by converting this to doubly link list and > printing it > plzzz comment > > -- > 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] Derivation
well the solution is pretty straight forward. let the distance between stations be 'd' and speed of trains starting at A and B (lets call them X and Y) be 'u' and 'v' resp. A-B (X) u-> <-v(Y)at t=0 (X)|(Y) meet each other at t= d/(u+v) So distance left to cover for X = dv/(u+v) and distance left to cover for Y= du/(u+v) time X will take to cover this distance= dv/(u*(u+v)) = a time Y will take to cover this distance= du/(v*(u+v)) = b => a : b = v^2 : u^2 => u : v = b^1/2 : a^1/2 hope its clear Anurag Sharma On Thu, Jun 10, 2010 at 11:05 PM, Raj N wrote: > Can someone help me deriving this ? > If 2 trains start at the same time from points A and B towards each > other and after crossing they take a and b sec in reaching B and A > respectively, then A's speed:B's speed=b^1/2:a^1/2 > > -- > 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: ds
nice algo! Anurag Sharma On Wed, Jun 9, 2010 at 11:23 PM, souravsain wrote: > Guys > > We can solve this in O(n) time like this: > Let me say total elements in array is 2N such that 1 to N are a's and N > +1 to 2N (which I will again refer to as 1 to N) are b's > > Observation: > If an element is on first 1 to N (an 'a') and has index i then in the > final array its position index (in the final 2N array) will be i+(i-1) > [current index + no. of positions lying to the left]. > If an element is on the second 1 to N (the b's series) and has index j > then in the final array of 2N, its index will be 2j. > > With this observation we start with the last element of first series, > the a's and find its final position in result array. Place the element > in final position. Take the element which is lying there and find this > elements new position and go on. > Example: start with temp=a6 (the last element of furst series) > a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,b6 > temp=a6, final position of a6 = 6+(6-1) = 11. Put a6 in eleventh > position and take the element at 11th position into temp: So now > a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,a6,b6 and temp = b5. Final position of > b5 = 2*5 = 10. Put b5 at 10th position and take previous element in > temp. So now > a1,a2,a3,a4,a5,a6,b1,b2,b3,b5,a6,b6 and temp = b4. Final position of > b4 = 2*4 = 8. Put b4 at 8th position and take previous element at 8th > in temp. So now > a1,a2,a3,a4,a5,a6,b1,b4,b3,b5,a6,b6 and temp = b2, going this way we > will have next position of b2 = 2*2=4 > a1,a2,a3,b2,a5,a6,b1,b4,b3,b5,a6,b6 and temp = a4: next position of a4 > = 4 + (4-1) = 7 > a1,a2,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=b1: next position of b1 = > 1*2=2 > a1,b1,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a2:next position of a2 = > 2+(2-1)=3 > a1,b1,a2,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a3:next position of a3 = > 3+(3-1)=5 > a1,b1,a2,b2,a3,a6,b4,b4,b3,b5,a6,b6 and temp=a5:next position of a5 = > 5+(5-1)=9 > a1,b1,a2,b2,a3,a6,b4,b4,a5,b5,a6,b6 and temp=b3:next position of b3 = > 3*2=6 > a1,b1,a2,b2,a3,b3,b4,b4,a5,b5,a6,b6 and temp=a6:next position of a6 = > 6 + (6-1)=11 > But now we find a6 already present at 11. Hence arranged in O(n) time > and constant space of 1 temp variable > > Thanks, > Sourav Sain > > On Jun 9, 8:54 pm, Anurag Sharma wrote: > > Its not O(n) time. > > > > Anurag Sharma > > > > On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha > > wrote: > > > > > > > > > here is a sel explainatory algo > > > > > given: > > > > > abcd1234 > > > abc1d234 > > > ab1c2d34 > > > a1b2c3d4 > > > > > here is the link for the code :http://codepad.org/SZnufGc6 > > > > > -- > > > Regards > > > Jitendra Kushwaha > > > MNNIT, 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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] hashing
Even if you use bucket sort, you will have to store the numbers arriving, or atleast 1..1 numbers along with their count. If you reduce the size of the bucket further you will have to make a list associated with the buckets. So asymptotically you will again reach the same space complexity. Anurag Sharma On Thu, Jun 10, 2010 at 5:16 AM, sharad kumar wrote: > can u reduce the size by making use of bucket sort > > On Wed, Jun 9, 2010 at 5:01 PM, sharad wrote: > >> I have a stream of numbers coming one by one from a computer generated >> program. I know that these numbers will be between 0 and 1. In >> minimum time how can I sort them. Space is no constraint. >> Later we have to try and optimize the space to as minimum as possible >> >> -- >> 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.
Re: [algogeeks] hashing
but you have already given the range of numbers from 1 to 1 for which I think it should work pretty fine. We can just keep a count of every number arriving in an array since we know its in the range 1..1 and later get the sorted array accordingly repeating the elements that many times. Its almost trivial this way. I did not get your statement completely "if word size is more then its quite inefficient". Any algorithm you choose for this you may mostly need to work on such arithmetic(addition in this case). Do you want some algo with some bit level operations? Correct me if I am wrong. Anurag Sharma On Wed, Jun 9, 2010 at 9:29 PM, sharad kumar wrote: > @ anurag we can do operation only at bit level sowe will need o(32n) > although it is also O(n) bt if word size is more then its quite inefficient > so suggest 4 that > > -- > 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: identify the recurring part for a given decimal no
multiply the original number x=23.34563456 Anurag Sharma On Wed, Jun 9, 2010 at 10:36 PM, Veer Sharma wrote: > One question: > > No x = 23.34563456 > temp = x X 10 = 233.4563456 > temp = temp - x = 210.11071104 > decimal part zero? No. > Now multiply the no. with 100. Which no? original x (= 23.34563456) or > new no. temp (=210.11071104)? > > > On Jun 9, 8:12 pm, divya jain wrote: > > multiply the no. with 10 nd store in temp. now subtract no from temp. > check > > if the decimal part is zero if yes. then 1st digit after decimal is > > recurring. if no. multiply the no with 100 and repeat . if this time > decimal > > part is zero then 2 digits after decimal r recurring nd so on.. > > > > On 8 June 2010 21:45, Veer Sharma wrote: > > > > > > > > > You have a Numerator and Denominator. After division you might get a > > > recurring decimal points float as the answer. > > > > > Problem is: You need to identify the recurring part for a given > > > decimal no? > > > For example 23.34563456 ... > > > return 3456 > > > > > -- > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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] level order traversal
In case of array representation of this binary tree where we can traverse
through all the leaf nodes and move to their parents, this problem becomes
quite easy.
for the example stated consider its array representation
arr[]={1,2,3,4,5,6,7} and take another array marked[7]={false} indicating
whether the current node has been printed
Now for every non leaf node, index i in (n/2) to (n-1)
print the leaf node and mark its marked[i]=true
change j= floor(i-1)/2
while marked[j] = false:
print arr[j]
marked[j]=true
change j=floor(j-1)/2
a C++ implementation for the above:-
int main(int argc, char **argv) {
int arr[] = { 1, 2, 3, 4, 5, 6, 7 }, N = 7;
bool marked[7];
for (int i = 0; i < N; i++)
marked[i] = false;
for (int i = N / 2; i < N; i++) {
printf("[%d]", arr[i]);
marked[i] = true;
for (int j = (i - 1) / 2; j>=0 && !marked[j]; j = (j - 1) / 2) {
printf("[%d]", arr[j]);
marked[j] = true;
}
}
}
Anurag Sharma
On Wed, Jun 9, 2010 at 9:31 PM, sharad kumar wrote:
>
>>>
>>>
>>> 1
>>>/\
>>> 2 3
>>> / \/ \
>>>45 67
>>>
>>>
>>> print
>>>
>>> 4 2156 37
>>>
>>>
> a set of vertical line 4m left u draw then on each line whatever no comes
> write it
>
>>
>>
>>
>> --
>> Luv,
>> S.Antony Vincent Pandian
>>
>>
>> --
>> 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.
Re: [algogeeks] Re: constraints satisfied?
Proceed with the above logic of 2D array and only fill the matrix considering only the equality constraints ( xi=xj) Using the Floyd warshall All pair shortest path algorithm, we can know the all reachable places from every other place. Now fill the matrix as per the inequality constraints(xi!=xj) and whenever an overwrite occurs we will know that its not possible to satisfy all constraints. Although this will shoot up our time complexity to O(n^3) because of Floyd Warshal algorithm. Comments welcome. Anurag Sharma On Wed, Jun 9, 2010 at 3:42 PM, jaladhi dave wrote: > Using an n*n array, am afraid, will not solve the problem, since its not > capable to capture transitivity. > > Consider the case: > > v1=v2 > v3=v2 > v3!=v1 > > we will place 0 in arr(1,2) arr(2,1) for v1=v2 > we will place 0 in arr(2,3) arr(3,2) for v3=v2 > and place 1 in arr(1,3) and arr(3,1) for v3!=v1. > > no overwrite :( and still the constraints cannot be satisfied. > > -jkd > > > > > On Tue, Jun 8, 2010 at 10:07 PM, Minotauraus wrote: > >> Use a n x n array. >> initialize with -1 (don't care = no constraints). If there is an >> equality constraint, set to 1, if >> explicity non-equality constraint is expected, replace with 0. While >> doing either of these if >> you come across a situation where 0 has to be overwritten by 1 or 1 >> has to be overwritten by 0, >> the system constraints cannot be satisfied, else all is well. Space >> required = n^2 bytes. >> Time complexity = O(c) where c= number of constraints for the system. >> Therefore, independent of the number of variables. >> >> >> You can do this with hash tables too and probably save memory. Here >> you'll use not store = -1 = don't care. >> >> -Minotauraus. >> >> On Jun 7, 12:16 pm, divya wrote: >> > Here's a problem that occurs in automatic program analysis. For a set >> > of variables x1; .. ; xn, you are given some equality constraints, >> > of the form "xi = xj" and some dis equality constraints, of the form >> > "xi != xj" Is it possible to satisfy all of them? Give an efficient >> > algorithm that takes as input m constraints over n variables and >> > decides whether the constraints can be satisfied. >> >> -- >> 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.
Re: [algogeeks] level order traversal
Do you have 'parent pointers' stored at every node? Anurag Sharma On Wed, Jun 9, 2010 at 2:26 PM, sharad wrote: > can any one tell me how to code for vertical level traversal of a > binary tree? > > > 1 >/\ > 2 3 > / \/ \ >45 67 > > > print > > 4 2156 37 > > -- > 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: ds
Its not O(n) time. Anurag Sharma On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha wrote: > here is a sel explainatory algo > > given: > > abcd1234 > abc1d234 > ab1c2d34 > a1b2c3d4 > > here is the link for the code : http://codepad.org/SZnufGc6 > > -- > Regards > Jitendra Kushwaha > MNNIT, 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. > -- 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] hashing
Counting sort. Anurag Sharma On Wed, Jun 9, 2010 at 5:01 PM, sharad wrote: > I have a stream of numbers coming one by one from a computer generated > program. I know that these numbers will be between 0 and 1. In > minimum time how can I sort them. Space is no constraint. > Later we have to try and optimize the space to as minimum as possible > > -- > 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] min no of policemen
Can you expain "edge of the tree". I could not get that. Anurag Sharma On Tue, Jun 8, 2010 at 5:53 AM, sharad kumar wrote: > for placing police man we can use bellman ford bfs.or even make use of > topological sort. > > > On Mon, Jun 7, 2010 at 9:59 PM, divya wrote: > >> consider a tree. policemen is to be placed such that for each edge of >> tree, there is a policeman on atleast one side of each edge. tell the >> min no. of policemen and their locatn in time O(n) >> >> -- >> 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.
Re: [algogeeks] Veer: Kth element in binary tree
Inorder traversal will do. Can use morris inorder also. Anurag Sharma On Tue, Jun 8, 2010 at 12:40 AM, Veer Sharma wrote: > 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 > > -- > 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] ds
@anand. Perhaps, its not correct. Does not work for larger inputs. Anurag Sharma On Mon, Jun 7, 2010 at 3:35 AM, Anand wrote: > Here is my approach is o(n). > http://codepad.org/YAFfZpxO > > <http://codepad.org/YAFfZpxO> > > On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar wrote: > >> >> >> this is ques by adobe and they want inplace soln.. >> >> -- >> 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.
Re: [algogeeks] Re: Find Max Number of Elephants
I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus wrote: > I think you can do this in O(n) time. Feel free to correct me where > I'm wrong. > > Create a 2D array with years on one side and elephant's time alive on > the other. example: >2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 > E1 1 1 1 11 1 1 1 1 > E2 1 11 1 > 1 1 1 11 > E3 1 1 > 1 1 > > Now for every years add vertical indices example 2006 = 3, 2007 = 3, > 2008 = 3 and so on. This will give you the > year with max elephant population. The array can be init with 0 or a > static array can be used. > > @Anurag: How will you approach this problem by using LCA algorithm > that your link leads to? > > > > On Jun 5, 6:16 am, amit wrote: > > Maximum number of elephants alive > > Hello guyz, > > > > Every elephant has a birth_time and a death_time. Given N Elephants > > with birth times and death times.. How can we find > > 1) the maximum number of elephants that can be alive at any given > > point of time. > > 2) what is the year in which you can have maximum number of elephants > > alive. > > ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 > > So in 2006 you have 3 elephants alive (maximum) > > PS: ignore months and all stuff .. if a elephants live in a year > > consider it lives that complete year > > > > I have O(year_max-year_min) solution and O(n^2) solution , where > > n=number of elephants . > > Can we do better ?? > > > > thanks > > -- > 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] Find Max Number of Elephants
use interval trees. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, Jun 5, 2010 at 6:16 PM, amit wrote: > Maximum number of elephants alive > Hello guyz, > > Every elephant has a birth_time and a death_time. Given N Elephants > with birth times and death times.. How can we find > 1) the maximum number of elephants that can be alive at any given > point of time. > 2) what is the year in which you can have maximum number of elephants > alive. > ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 > So in 2006 you have 3 elephants alive (maximum) > PS: ignore months and all stuff .. if a elephants live in a year > consider it lives that complete year > > I have O(year_max-year_min) solution and O(n^2) solution , where > n=number of elephants . > Can we do better ?? > > thanks > > -- > 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] Check if 2 linked lists are identical
But perhaps the elements in lists may not be in order. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Thu, Jun 3, 2010 at 6:38 PM, Rohit Saraf wrote: > simple in place O(n lg n) solution. > Choose a pivot in first array and partition it like in quicksort. > Find the pivot in second array and partition. Now recurse on both > halves. At any point if no of elements in array are not equal... > Abort! > > > -- > -- > 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.
Re: [algogeeks] Re: Implementing 2 stacks within a single linear array
for 3 stacks we can start Stack 1 with index 0 and fill 0,3,6,... indices (3n) and for Stack 2 we can fill indices 1,4,7,... starting at index 1 (3n+1) and for Stack 3 we can fill indices 2,5,8... starting at index 2 (3n+2) Ofcourse in this case even if 2 of the stacks are empty the third one will get maximum size of N/3 where N is sizeof array. Or we can start 1st stack from starting, 2nd from end and 3rd from the middle. I cant think of any other implementation of 3 stacks where you can survive without shifting the elements and efficiently using the array space. Comments welcome. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Wed, Jun 2, 2010 at 10:49 AM, Raj N wrote: > @Gene: Hey can u explain it in more detail with an example taking 3 stacks > > > On Wed, Jun 2, 2010 at 7:38 AM, Gene wrote: > >> On Jun 1, 2:27 pm, Raj N wrote: >> > How to implement 3 stacks using the same? >> > >> > On Tue, Jun 1, 2010 at 8:59 PM, Sudarshan Reddy M < >> sudarsha...@gmail.com>wrote: >> > >> > >> > >> > > Hi, >> > > the stacks can implemented in the array one is starting at the begin >> and >> > > other is starting at the end growing in opposite directions. If the >> stack >> > > tops are colloid then there is no space left; means no room for extra >> > > elemnts. >> > > Thanks >> > > Sudarshan. >> > >> > > On Tue, Jun 1, 2010 at 2:11 PM, Raj N wrote: >> > >> > >> Hi all, >> > >> Can someone suggest me an efficient way to implement 2 stacks within >> a >> > >> single linear array assuming neither of the stack overflows and an >> > >> entire stack is never shifted to a different location within the >> array. >> > >> >> Interleave them. If you need N stacks, use A(i), A(i+N), A(i+2N) ... >> for the i'th stack. >> >> -- >> 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.
Re: [algogeeks] Check if 2 linked lists are identical
You can construct some kind of Search Tree like BST from the first list and search for every element in the second list in that search Tree. O(NlogN) time Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Wed, Jun 2, 2010 at 6:18 AM, sharad kumar wrote: > @Raj:sorting can be done in O(nlogn)..sort both and compare both.or use a > hash map to store all elements of one LL and then compare it with > otheror combine both the LL perform merge sort and start deleting > adjacent elements.if adjacent elements in equal count then LL are equal and > at end of process we get an empty list. > > > On Tue, Jun 1, 2010 at 11:55 PM, Raj N wrote: > >> Hi all, >> Can someone suggest an efficient algorithm to check if 2 linked lists >> are identical. If 2 lists have to be sorted then there'll be a lot of >> space consumption for 2 separate linked lists. Can the whole process >> be done < O(n2) >> >> -- >> 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.
Re: [algogeeks] Re: Can you solve this?
Well, in that case, then just forget the "balancing the number of elements in the 2 teams" portion of my solution above :) Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 31, 2010 at 10:38 AM, Nik_nitdgp wrote: > This problem is like 2 processor job scheduling problem ,We may get an > optimal solution for different instances using different algorithm > apart from brute force.Whereas Brute force covers all possible subsets > but may take years to complete if N is large. > > above algo fails in the following example. > > Eg. 2 2 2 3 3 > > above algo gives: > T1: 2 2 3 =7 > T2: 2 3 =5 > > But closest distribution is > T1=2 2 2=6 > T2 3 3=6 > > On May 31, 9:30 am, W Karas wrote: > > Is this the same problem as: > > > > http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc253... > > > > ? > > > > Or can the teams have different numbers of players? > > > > On May 30, 2:28 pm, Veer Sharma wrote: > > > > > Hi Friends, > > > > > This is my first post to this forum. A "Hi" to all of you and here is > > > my first problem... > > > > > Giiven int n, the total number of players and their skill-point. > > > Distribute the players on 2 evenly balanced teams. > > > > > Lets see who gives the best solution (least space complexity / least > > > time complexity or both...) > > -- > 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: Can you solve this?
ya I guess its the same problem.. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 31, 2010 at 10:00 AM, W Karas wrote: > Is this the same problem as: > > > http://groups.google.com/group/algogeeks/browse_frm/thread/26c31cc2530a88e1# > > ? > > Or can the teams have different numbers of players? > > On May 30, 2:28 pm, Veer Sharma wrote: > > Hi Friends, > > > > This is my first post to this forum. A "Hi" to all of you and here is > > my first problem... > > > > Giiven int n, the total number of players and their skill-point. > > Distribute the players on 2 evenly balanced teams. > > > > Lets see who gives the best solution (least space complexity / least > > time complexity or both...) > > -- > 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] Can you solve this?
@Abhishek,
I think your logic will not work. Although it can be done by greedy
approach, but your method needs some tweak.
Consider the case : 1,2,3,4,5,12
with your logic, we will get this answer
team 1: 1,3,5 (total=9)
team 2: 2,4,12(total=18)
difference is 9 and its huge.
what can be done is after sorting the array, keep track of the sum of all
elements in 2 variables for the 2 teams and keep assigning the next
element(in decreasing order) to the one with less sum, and update the sum.
Finally if the number of elements are not balanced for the 2 teams, transfer
the bottom diff/2 elements to the other team to make it balance ( where diff
is the difference in the number of elements in 2 teams)
Ex: for array: 1,2,3,4,5,12
sort in descending order in O(nlogn): 12,5,4,3,2,1
initially:
teamA={}, teamB={}
sumA=0, sumB=0
iteration 1:
teamA={12}, teamB={}
sumA=12,sumB=0
iteration 2:
teamA={12}, teamB={5}
sumA=12,sumB=5
iteration 3:
teamA={12}, teamB={5,4}
sumA=12,sumB=9
iteration 4:
teamA={12}, teamB={5,4,3}
sumA=12,sumB=12
iteration 5:
teamA={12,1}, teamB={5,4,3}
sumA=13,sumB=12
iteration 6:
teamA={12,1}, teamB={5,4,3,2}
sumA=13,sumB=14
now since the elements are not balanced in 2 arrays we need to transfer
lowest the (4-2)/2= 1 element from teamB to teamA i.e. transfer element 2 in
this case
final result:
teamA={12,1,2}, teamB={5,4,3}
sumA=15, sumB=12
difference is 3 unlike 9 in your case.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Mon, May 31, 2010 at 5:54 AM, sharad kumar wrote:
> @abhishek:i meant after sorting split the array into 2 part each with
> equal sum
>
> On Sun, May 30, 2010 at 11:45 PM, Abhishek Sharma
> wrote:
>
>> @sharad: if you find the subarrays of equal sum then the number of players
>> might differ in the team... also can you tell me how will you do
>> that..according to me time cmoplexity will be higher..
>>
>> According to me:
>> sort the palyers based on skill points (O(nlogn) --mergesort) then assign
>> the players one by one to each team (O(n))
>>
>> Ex: Consider 10 players to be assigned to two teams.
>>skill points: 12, 12, 7, 8, 15, 19, 11, 14, 5, 10.
>>
>> Ans:
>> after sorting: 5, 7, 8, 10, 11, 12, 12, 14, 15, 19.
>> Team1: 5, 8, 12, 14, 19
>> Team2: 7, 11,12,15.
>>
>> This is not exactly even but i think is the closest approach.
>> correct me if I am wrong..
>>
>> Regards,
>> Abhishek
>>
>> On Sun, May 30, 2010 at 8:21 PM, sharad kumar wrote:
>>
>>> sort the players based on skill point and get the subarray of equal
>>> sum..
>>>
>>>
>>> On Sun, May 30, 2010 at 6:58 PM, Veer Sharma
>>> wrote:
>>>
>>>> Hi Friends,
>>>>
>>>> This is my first post to this forum. A "Hi" to all of you and here is
>>>> my first problem...
>>>>
>>>> Giiven int n, the total number of players and their skill-point.
>>>> Distribute the players on 2 evenly balanced teams.
>>>>
>>>> Lets see who gives the best solution (least space complexity / least
>>>> time complexity or both...)
>>>>
>>>> --
>>>> 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.
&g
Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
@pawan Will it not take O(n^2) time then. What he is talking about is solving it in O(nlogn) time Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, May 29, 2010 at 7:04 PM, pawan sharma wrote: > @amit > for longest increasing subsequence , just sort the given array and find > longest subsequence of sorted array and unsorted array . It will give you > longest increasing subsequence (because of sorted array) . > > > On Sat, May 29, 2010 at 12:41 PM, Nikhil Agarwal < > nikhil.bhoja...@gmail.com> wrote: > >> Check: >> >> http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence >> >> >> >> >> >> On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari < >> amir.hossein.shahri...@gmail.com> wrote: >> >>> A hint from "Introduction to algorithms" on this problem: >>> Observe that the last element of a candidate subsequence of length *i* is >>> at least as large as the last element of a candidate subsequence of length >>> *i-1. *Maintain candidate subsequences by linking them through the input >>> sequence >>> >>> The attached file is a tutorial from train.usaco.org which includes 3 >>> approaches to the problem and explains them with some examples. >>> I hope it would help! >>> >>> >>> On Fri, May 28, 2010 at 7:44 PM, amit wrote: >>> >>>> Hi , Can anyone plz explain this algorithm taking some example. >>>> I read this on wiki but could'nt get how binary search was working. >>>> >>>> -- >>>> 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. >>> >> >> >> >> -- >> Thanks & Regards >> Nikhil Agarwal >> Senior Undergraduate >> Computer Science & Engineering, >> National Institute Of Technology, Durgapur,India >> http://tech-nikk.blogspot.com >> http://beta.freshersworld.com/communities/nitd >> >> >> -- >> 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.
Re: [algogeeks] Re: Google telephone interview question
Is it necessary that the sectors allocated to the file are strictly in increasing number? Can file2 have sectors like *"sec12->sec10->null"* ??? Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, May 29, 2010 at 12:37 AM, Atul Kumar wrote: > Sorry the example should be > > file1 = sec2 -> sec7->sec9 -> sec11 -> null > file2 = sec10 -> sec12-> null > > as first sector contains the file information. > > google don't hear DFS or linear parsing, give me the code ;) > > On May 27, 11:28 am, Atul Kumar wrote: > > There is a file system on the disc. the disc has many sectors. Always > > the first sector has the information about all the files. > > > > A file data is divided into sectors. Each sector can have data from a > > single file. > > > > Each sector has 2 parts, data and the pointer to the next sector of > > the file. Every last sector in the file has next pointer as null. > > > > say a disk has 18 sectors numbered 1 to 18. > > > > then the first sector would have this information about the file. > > > > file1 = sec1 -> sec7->sec9 -> sec11 -> null > > file2 = sec10 -> sec12-> null > > > > etc. > > > > Now the first sector has some error. write an algo to reconstruct the > > file information in the first sector. > > Write code in C. > > -- > 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: Yahoo coding round question
@W Karas Can you please give an example and explain your approach. Anurag Sharma On Tue, May 18, 2010 at 12:17 AM, W Karas wrote: > One (space-intensive) idea: > > Re-represent each string as a set of pairs (character, position of > character). Then sort each set of pairs by character. Then find > corresponding sequences in the sorted lists of pairs, where the > character and the difference between position is the same from pair to > pair in the sequence. Then narrow down the sequences to those that > actually are substrings of adjacent characters and choose the longest. > > On May 8, 5:00 am, Jitendra Kushwaha wrote: > > Find the longest common subsequence of given N strings each having > > length between 0 to M. > > Can anybody give a good approach to the solutions > > -- > 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] question
oops!
Anurag Sharma
On Mon, May 17, 2010 at 5:00 PM, Navin Naidu wrote:
> @anurag:
>
> -99 -2 -1 3 +99
>
> The min sum (=0) for value pair (-99, 99)
>
> Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1
>
> Actual result: -2, -1, 3 : 0
>
>
>
>
>
> On Mon, May 17, 2010 at 8:48 AM, Anurag Sharma wrote:
>
>> @Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
>>
>> 1. Sort the array in nlogn time: array={-99,-1,0,2,99}
>>
>> 2. consider all possible pairs of numbers and keep track of the sum
>> closest 2 zero:
>> -99+-1=-100, |-100|=100
>> -99+0=-99,|-99|=99
>> -99+2=-97,|-97|=97
>> -99+99=0,|0|=0 <--- this is the minimum sum(=0) for value pair (-99,
>> 99)
>> -1+0=-1,|-1|=1
>> -1+2=1,|1|=1
>> -1+99=98,|98|=98
>> 0+2=2,|2|=2
>> 0+99=99,|99|=99
>> 2+99=101,|101|=101
>>
>>
>> 3. Now traversing the array skipping the values -99, 99 and trying to get
>> minimum sum after including it in the existing sum :
>> array={-99,-1,0,2,99}
>> take -99: skip
>> take -1: 0+-1= -1 and |-1|=1
>> take 0: 0+0=0 and |0|=0 < this is the minimum so the third number is
>> 0
>> take 2: 0+2=2 and |2|=2
>> take 99: skip
>>
>> this way we got the three numbers as -99,99 and 0. Were you expecting some
>> other combo?
>> In step 3 we can skip checking the rest of the elements when we find the
>> sum increasing as the array is already sorted.
>>
>> Let me know if there is still some issue in it.
>>
>>
>> Regards,
>>
>> Anurag Sharma
>>
>>
>>
>> On Sun, May 16, 2010 at 9:26 PM, Navin Naidu wrote:
>>
>>>
>>> @anurag: wont work, consider the following case: -99 0 2 -1 99
>>>
>>>
>>>
>>>
>>>
>>> On Sun, May 16, 2010 at 9:12 PM, Rohit Saraf <
>>> rohit.kumar.sa...@gmail.com> wrote:
>>>
>>>> @anurag : won't work
>>>> --
>>>> 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.
>>>>
>>>
>>>
>>>
>>> --
>>> Thanks & Regards,
>>>
>>> - NMN
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Thanks & Regards,
>
> - NMN
>
> --
> 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] question
@Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
1. Sort the array in nlogn time: array={-99,-1,0,2,99}
2. consider all possible pairs of numbers and keep track of the sum closest
2 zero:
-99+-1=-100, |-100|=100
-99+0=-99,|-99|=99
-99+2=-97,|-97|=97
-99+99=0,|0|=0 <--- this is the minimum sum(=0) for value pair (-99,
99)
-1+0=-1,|-1|=1
-1+2=1,|1|=1
-1+99=98,|98|=98
0+2=2,|2|=2
0+99=99,|99|=99
2+99=101,|101|=101
3. Now traversing the array skipping the values -99, 99 and trying to get
minimum sum after including it in the existing sum :
array={-99,-1,0,2,99}
take -99: skip
take -1: 0+-1= -1 and |-1|=1
take 0: 0+0=0 and |0|=0 < this is the minimum so the third number is 0
take 2: 0+2=2 and |2|=2
take 99: skip
this way we got the three numbers as -99,99 and 0. Were you expecting some
other combo?
In step 3 we can skip checking the rest of the elements when we find the sum
increasing as the array is already sorted.
Let me know if there is still some issue in it.
Regards,
Anurag Sharma
On Sun, May 16, 2010 at 9:26 PM, Navin Naidu wrote:
>
> @anurag: wont work, consider the following case: -99 0 2 -1 99
>
>
>
>
>
> On Sun, May 16, 2010 at 9:12 PM, Rohit Saraf
> wrote:
>
>> @anurag : won't work
>> --
>> 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.
>>
>
>
>
> --
> Thanks & Regards,
>
> - NMN
>
> --
> 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] question
Cant it be done this way:- 1. Sort the array in O(n log(n)) time 2. select all pairs of numbers in array and keep track of minimum sum (closest to zero) and also their indices, in O(n^2) time 3. In another iteration skipping the indices which gave the minimum sum, check whether the current number yields the sum closest to zero. Thats what your third number is. It takes n log(n) + n^2 + n time which is O(n^2) and O(1) extra memory Correct me if I am wrong. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Mon, May 3, 2010 at 6:18 PM, jalaj jaiswal wrote: > > given an array(unsorted) may contain negative numbers too > find the index of three numbers whose sum is closest to zero in O(N2 log > N) time and O(N) space. > > P.S -3 is more close to zero then -6 (number line ...) > > -- > 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. > -- 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] partion of array
One more way to do this can be:
1. sorting the number in decreasing order
2. start with 2 empty sets A and B and assign first 2 elements to each of
them (see the following example)
3. maintain the sums of A and B in variables.
4. take the next number from list and add it to the set where the sum is
less than the other and update the sum
5. similarly add the rest of the numbers.
6. Now in case one set contains less number of elements than other, then
add the last |size(A)-size(B)|/2 elements from the set with more size to the
one with less size
Example:
list: {1,2,3,4,5,6,7,23}
set: A={}, B={}
sumA=0, sumB=0
sort list in descending order: list:{23,7,6,5,4,3,2,1}
add first 2 elements 2 each set
A={23}, sumA=23 and B={7}, sumB=7
take next element '6'
since sumBhttp://anuragsharma-sun.blogspot.com/
On Fri, May 14, 2010 at 1:51 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 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: Finding youngest common ancestor of two nodes in a binary tree
@Rahul,
The Tree is not Binary "Search" Tree.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 6:52 PM, Rahul Singh wrote:
> Perform inorder traverse for both the node. match element by element the 2
> strings and when first time the string deviates thats Lowest common
> ancestor.
> -rahul
>
> On Thu, Apr 8, 2010 at 6:21 PM, Anurag Sharma wrote:
>
>> @Dave,
>> Thanks for pointing out the limitation in my algorithm. I myself realized
>> the same mistake after I posted the algorithm. You are right, we should
>> additionally check the presence of A and B on the either side. It will add
>> few extra conditions to the algorithm. I will soon update the same on my
>> blog.
>>
>> Anurag Sharma
>>
>> http://anuragsharma-sun.blogspot.com/
>>
>>
>> On Thu, Apr 8, 2010 at 5:32 PM, Dave wrote:
>>
>>> @Anurag.
>>>
>>> I like your algorithm, but observe some deficiencies...
>>>
>>> A could be on the right subtree and B on the left, as well.
>>>
>>> And what if B is a descendent of A. Should we consider A to be the
>>> lowest common ancestor (i.e., is a node an ancestor of itself?), or is
>>> the LCA the first ancestor of A? In either case, something more must
>>> be done.
>>>
>>> Dave
>>>
>>> On Apr 8, 12:34 am, Anurag Sharma wrote:
>>> > Dear Himanshu,
>>> > Here is what I think. This problem can be solved easily by using
>>> recursion.
>>> > Here is the pseudo code for it:
>>> >
>>> > Logic: Let 'A' and 'B' be the given too node whose common ancestor we
>>> have
>>> > to find. Now perform an inorder traversal of the tree and at every node
>>> call
>>> > the 'search(A)' function on the left subtree and search(B) function on
>>> the
>>> > right subtree. When both the results are true, you can be assured that
>>> this
>>> > current node is only the first common ancestor of A, and B, since below
>>> the
>>> > current node, on either tree the other node (A or B) will not exist,
>>> and
>>> > above the current node, both A and B will exist on 1 side, so again
>>> they
>>> > will not exist on either side.
>>> > Heres d pseudo code:
>>> >
>>> > //this is a normal recursive function to search for a Key node in the
>>> tree
>>> > rooted at 'root'
>>> > bool search(node *root, node *key){
>>> >
>>> > if(root==NULL)
>>> > return false;
>>> >
>>> > if(root==key)
>>> > return true;
>>> >
>>> > return search(root->left, key) || search(root->right, key);
>>> >
>>> > }
>>> >
>>> > node* getCommonAncestor(node *root, node *A, node *B){
>>> >
>>> > if(root==NULL)
>>> > return NULL;
>>> >
>>> > //if A is present in the left subtree and B is present in the right
>>> subtree,
>>> > then we have found the common ancestor
>>> > if(search(root->left, A) && search(root->right, B))
>>> > return root;
>>> >
>>> > node* left = getCommonAncestor(root->left, A, B);
>>> > node* right= getCommonAncestor(root->right, A, B);
>>> >
>>> > if(left !=NULL)
>>> > return left;
>>> > if(right !=NULL)
>>> > return right;
>>> >
>>> > return NULL;
>>> >
>>> > }
>>> >
>>> > Hope this helps you.
>>> > Comments welcome
>>> >
>>> > --
>>> > Anurag Sharmahttp://anuragsharma-sun.blogspot.com/
>>> >
>>> > On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
>>> > wrote:
>>> >
>>> >
>>> >
>>> > > For a given binary tree, given the root and two node pointers, how
>>> can we
>>> > > find their youngest common ancestor.
>>> >
>>> > > Say the node is like:
>>> >
>>> > > struct node{
>>> > >int data;
>>> > >struct node*left, *right;
>>> > > };
>>> >
>>> > > i.e the father field is not there.
>>> >
>>> > > Please note that it is not a binary search tree, but just a binary
>>> tree.
>>> >
>&
Re: [algogeeks] Re: Finding youngest common ancestor of two nodes in a binary tree
@Dave,
Thanks for pointing out the limitation in my algorithm. I myself realized
the same mistake after I posted the algorithm. You are right, we should
additionally check the presence of A and B on the either side. It will add
few extra conditions to the algorithm. I will soon update the same on my
blog.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 5:32 PM, Dave wrote:
> @Anurag.
>
> I like your algorithm, but observe some deficiencies...
>
> A could be on the right subtree and B on the left, as well.
>
> And what if B is a descendent of A. Should we consider A to be the
> lowest common ancestor (i.e., is a node an ancestor of itself?), or is
> the LCA the first ancestor of A? In either case, something more must
> be done.
>
> Dave
>
> On Apr 8, 12:34 am, Anurag Sharma wrote:
> > Dear Himanshu,
> > Here is what I think. This problem can be solved easily by using
> recursion.
> > Here is the pseudo code for it:
> >
> > Logic: Let 'A' and 'B' be the given too node whose common ancestor we
> have
> > to find. Now perform an inorder traversal of the tree and at every node
> call
> > the 'search(A)' function on the left subtree and search(B) function on
> the
> > right subtree. When both the results are true, you can be assured that
> this
> > current node is only the first common ancestor of A, and B, since below
> the
> > current node, on either tree the other node (A or B) will not exist, and
> > above the current node, both A and B will exist on 1 side, so again they
> > will not exist on either side.
> > Heres d pseudo code:
> >
> > //this is a normal recursive function to search for a Key node in the
> tree
> > rooted at 'root'
> > bool search(node *root, node *key){
> >
> > if(root==NULL)
> > return false;
> >
> > if(root==key)
> > return true;
> >
> > return search(root->left, key) || search(root->right, key);
> >
> > }
> >
> > node* getCommonAncestor(node *root, node *A, node *B){
> >
> > if(root==NULL)
> > return NULL;
> >
> > //if A is present in the left subtree and B is present in the right
> subtree,
> > then we have found the common ancestor
> > if(search(root->left, A) && search(root->right, B))
> > return root;
> >
> > node* left = getCommonAncestor(root->left, A, B);
> > node* right= getCommonAncestor(root->right, A, B);
> >
> > if(left !=NULL)
> > return left;
> > if(right !=NULL)
> > return right;
> >
> > return NULL;
> >
> > }
> >
> > Hope this helps you.
> > Comments welcome
> >
> > --
> > Anurag Sharmahttp://anuragsharma-sun.blogspot.com/
> >
> > On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
> > wrote:
> >
> >
> >
> > > For a given binary tree, given the root and two node pointers, how can
> we
> > > find their youngest common ancestor.
> >
> > > Say the node is like:
> >
> > > struct node{
> > >int data;
> > >struct node*left, *right;
> > > };
> >
> > > i.e the father field is not there.
> >
> > > Please note that it is not a binary search tree, but just a binary
> tree.
> >
> > > Thanks,
> > > Himanshu
> >
> > > --
> > > 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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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] Finding youngest common ancestor of two nodes in a binary tree
Dear Himanshu,
Here is what I think. This problem can be solved easily by using recursion.
Here is the pseudo code for it:
Logic: Let 'A' and 'B' be the given too node whose common ancestor we have
to find. Now perform an inorder traversal of the tree and at every node call
the 'search(A)' function on the left subtree and search(B) function on the
right subtree. When both the results are true, you can be assured that this
current node is only the first common ancestor of A, and B, since below the
current node, on either tree the other node (A or B) will not exist, and
above the current node, both A and B will exist on 1 side, so again they
will not exist on either side.
Heres d pseudo code:
//this is a normal recursive function to search for a Key node in the tree
rooted at 'root'
bool search(node *root, node *key){
if(root==NULL)
return false;
if(root==key)
return true;
return search(root->left, key) || search(root->right, key);
}
node* getCommonAncestor(node *root, node *A, node *B){
if(root==NULL)
return NULL;
//if A is present in the left subtree and B is present in the right subtree,
then we have found the common ancestor
if(search(root->left, A) && search(root->right, B))
return root;
node* left = getCommonAncestor(root->left, A, B);
node* right= getCommonAncestor(root->right, A, B);
if(left !=NULL)
return left;
if(right !=NULL)
return right;
return NULL;
}
Hope this helps you.
Comments welcome
--
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Wed, Apr 7, 2010 at 10:04 PM, Himanshu Aggarwal
wrote:
> For a given binary tree, given the root and two node pointers, how can we
> find their youngest common ancestor.
>
> Say the node is like:
>
> struct node{
>int data;
>struct node*left, *right;
> };
>
> i.e the father field is not there.
>
> Please note that it is not a binary search tree, but just a binary tree.
>
> Thanks,
> Himanshu
>
> --
> 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] Finding youngest common ancestor of two nodes in a binary tree
Well Atul, Mind it, its not a Binary Search Tree, its just a Binary Tree. So
this concept of the elements in left sub tree all having the value less than
the current node and similar for the right subtree will not stand here.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 9:49 AM, atul verma wrote:
> Its very simple to solve this.
>
> Start from root.
>
> Compare the value of current node data value to both nodes.
>
> 1. if both are greater than current node then traverse node->right
> 2. if both are lesser than current node then traverse node->left
> 3. else return current node pointer.
>
> Any comments,
>
> Atul
>
>
> On Thu, Apr 8, 2010 at 10:15 AM, Pramod Negi wrote:
>
>> could you please elucidate more??
>>
>>
>> On Wed, Apr 7, 2010 at 10:34 PM, Himanshu Aggarwal <
>> lkml.himan...@gmail.com> wrote:
>>
>>> For a given binary tree, given the root and two node pointers, how can we
>>> find their youngest common ancestor.
>>>
>>> Say the node is like:
>>>
>>> struct node{
>>>int data;
>>>struct node*left, *right;
>>> };
>>>
>>> i.e the father field is not there.
>>>
>>> Please note that it is not a binary search tree, but just a binary tree.
>>>
>>> Thanks,
>>> Himanshu
>>>
>>> --
>>> 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.
>
--
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] Digest for algogeeks@googlegroups.com - 17 Messages in 3 Topics
Here is what you want exactly: http://anuragsharma-sun.blogspot.com/2010/03/converting-bst-to-circular-doubly.html Hope it helps -Anurag Sharma On Thu, Apr 1, 2010 at 4:54 PM, > wrote: > Today's Topic Summary > > Group: http://groups.google.com/group/algogeeks/topics > >- [No Subject] <#127b91d593367ca3_group_thread_0> [10 Updates] >- how to convert a BST into a sorted doubly linked > list.<#127b91d593367ca3_group_thread_1>[2 Updates] >- Implementation of Algorithms <#127b91d593367ca3_group_thread_2> [5 >Updates] > > Topic: [No > Subject]<http://groups.google.com/group/algogeeks/t/a93bb1feac751245> > >BlackdiamonD Mar 31 11:54AM +0530 > ^<#127b91d593367ca3_digest_top> > >is the list is sorted...or in some order... >i feel unless the point in the list in some order eg: sorted, >it will be difficult to get soluiton less than O(n) > > >-- >BL/\CK_D!AMOND > > > > >abhijith reddy Mar 31 01:23PM +0530 > ^<#127b91d593367ca3_digest_top> > >I guess she was asking that the per query complexity should be better >that >O(n). > >If that is the case then you can use any of these >Simple RMQ O(sqrt(n)) >Segment/Interval Trees O(lgn) >Binary Indexed Trees O(lgn) > >On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf > > > > >Ashim Kapoor Mar 31 01:07PM +0530 > ^<#127b91d593367ca3_digest_top> > >I think it can be done in logn time ( I assume the list is sorted, is >there >an order log n sorting algo, then i can even sort it in log n time ? ( >I am >new to algorithms ) ). > >1. binary search for low=x1. >2. binary search for high=x2. > >both will take log n time. Print all values between them then in >O(x2-x1) >time. > >Is this correct? >On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf > > > > >BlackdiamonD Mar 31 11:55AM +0530 > ^<#127b91d593367ca3_digest_top> > >ok...sorry u asked the data structure.. > > >-- >BL/\CK_D!AMOND > > > > >BlackdiamonD Mar 31 12:48PM +0530 > ^<#127b91d593367ca3_digest_top> > >what if your sort the element.first time.. >applying binary search on list for x1 (getting minimum index ) >applying binary search on list for x2(getting maximum index) >element between this index will be the answer. >complexity:O(log(N)) for getting the range. (not considering the >sorting) > > > > >-- >BL/\CK_D!AMOND > > > > >Anil Kishore Mar 31 12:48PM +0530 > ^<#127b91d593367ca3_digest_top> > >What do you mean by points ? .. Are you referring to the integer values >stored ? >. >1.) If the question is, given N integers.. and given x1 and x2, report >all >integers x (x1<=x<=x2), you can't do better than O(N), as going through >input itself takes O(N). >. >2.) if the question is, given N integers and Q queries, each query is >as >ques1, then you may sort it initially and answer each query. It will be >O( N >log N ) + Q . O ( logN + (x2-x1) ). > >- AK > > >-- >Anil Kishore > > > > >ANUJ KUMAR Mar 31 05:51PM +0530 > ^<#127b91d593367ca3_digest_top> > >We can make a query tree and then each query will take O(log n+k) time. > > > > > >Priyanka Chatterjee Mar 31 08:26PM +0530 > ^<#127b91d593367ca3_digest_top> > >The list of N integers is not sorted. >The solution is asked for a particular query. > >@Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or >*Segment >Interval trees*. May be you opted for the correct data structure. >Please >give the algorithm. > >@All: Doing a sorting for O(n logn) and then binary search for x1 and >x2 in >O(logn) will be less efficient than the simple solution of O(n). Think >on >the data structure that can optimize it. >Is it possible in time complexity < O(n)? > > >-- >Thanks & Regards, >Priyanka Chatterjee >Third Year Undergraduate Student, >Computer Science & Engineering, >National Institute Of Technology,Durgapur >India >http://priyanka-nit.blogspot.com/ > > > > >abhijith reddy Mar 31 09:58PM +0530 > ^<#127b91d593367ca3_digest_top> > >> O(logn) will be less efficient than the simple solution of O(n). >Think on >> the data structure that can op
