Re: [algogeeks] minimum no. of clicks
@bittu
consider 12112
does your solution say 2 clicks ?
@srikar i don't think we can.
On Tue, Feb 1, 2011 at 11:34 PM, Srikar srikar2...@gmail.com wrote:
Could I sort it? Oh you mentioned that the original array could be
destroyed.
In that case,
1) Sort the array - O(nlogn)
2) loop through the array. if contiguous elements are same remove all of
them in one click else remove only that element. - O(n)
Time - O(nlogn)
space - O(1)
On Tue, Feb 1, 2011 at 7:23 PM, snehal jain learner@gmail.com wrote:
You are given an array A of length N. You have to destroy it, given
that you have the power to remove any continuous chunk of same numbers
with 1 click. Thus the order in which you remove chunk matters. For
example given {1, 2, 3, 1} normally it will take you 4 clicks to
remove but if you first remove 2 making array {1, 3, 1} then 3 making
it {1, 1} and then you can remove this continuous chunk of similar
number in one click, thus completing the task in 3 clicks. How to find
minimum number of clicks required? Another example is {1, 2, 3, 2, 1}
which can be destroyed in 3 clicks
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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: Frequently one of the Top Question Asked in Amazon
@bittu: please write the subject which could summarize the problem statement or give a context instead of writing top question, amazon everywhere. you have multiple posts with the same problem. In the content you can write this co., that co., frequency of questions etc etc whatever you like after your problem statement. @Rohit: I agree with you partly here. As long as the question contains terms which are generally known it should be fine but if somebody mentions a term which is rare it is always better to give a few examples to clarify, in my opinion. If majority of readers are forced to google then examples are necessary. This again is subjective so it's always the problem writer's call. This post qualifies for examples in the problem statement. On Sun, Jan 30, 2011 at 8:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Frequently one of the Top Question Asked in Amazon
@bittu: you may also want to answer juver++'s off topic question in your future posts. On Mon, Jan 31, 2011 at 1:15 AM, saurabh gupta sgup...@gmail.com wrote: @bittu: please write the subject which could summarize the problem statement or give a context instead of writing top question, amazon everywhere. you have multiple posts with the same problem. In the content you can write this co., that co., frequency of questions etc etc whatever you like after your problem statement. @Rohit: I agree with you partly here. As long as the question contains terms which are generally known it should be fine but if somebody mentions a term which is rare it is always better to give a few examples to clarify, in my opinion. If majority of readers are forced to google then examples are necessary. This again is subjective so it's always the problem writer's call. This post qualifies for examples in the problem statement. On Sun, Jan 30, 2011 at 8:38 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Frequently one of the Top Question Asked in Amazon
what do you mean by spiral order ? On Sat, Jan 29, 2011 at 8:25 PM, bittu shashank7andr...@gmail.com wrote: Convert BT in to DLL such that DLL represents the Sprial order traversal of BT. Inplace its Written Test Question They wants Exact Working Code...Not Approach..Be Clear..Try to provide best solutions Thanks Regards Shashank The best way to escape from a problem is to solve it. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Suggestions required regarding my final year Project....
wrong forum. On Fri, Jan 28, 2011 at 6:29 PM, Venu sendmail2v...@gmail.com wrote: Thanks pawan...Actually, i wanted to do a project related to Data Mining...Do you have any ideas related to this area ??? On Jan 28, 10:43 am, pawan gangwani pawan.gangw...@gmail.com wrote: Hi Rajeev/venu, i suggest you to think of a domain of you interest first, then proceed in that direction thinking of some project. have you thought of any domain in which you want to go for a project. it may some web application, some thing in O/S like unix, may be implementing a protocol of networks, bulding your own shell in Unix/Linux. regards Pawan On Fri, Jan 28, 2011 at 11:06 AM, Rajeev Kumar rajeevprasa...@gmail.com wrote: Hi, Can any one please suggest any good site to find good projects to do in final year. Thanks, Rajeev. On Fri, Jan 28, 2011 at 9:10 AM, Venu sendmail2v...@gmail.com wrote: Hi friends- This is Venu, studying final year B.Tech in Computer Science at Jawaharlal Nehru University, Hyderabad. Can you please suggest me some ideas regarding my final year project (3 months duration). Thanking you in advance... Regards Venu. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2Bunsubscribe@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Puzzle
up vote to 9 + 1 + 1/9 On Thu, Jan 27, 2011 at 6:06 PM, sunny agrawal sunny816.i...@gmail.comwrote: another one 9*(1+ 1/9) On Thu, Jan 27, 2011 at 5:40 PM, nhkrishna2...@yahoo.com nhkrishna2...@gmail.com wrote: 9+1+1/9 On Jan 27, 4:43 pm, ankit agarwal ankitgeniu...@gmail.com wrote: (9*9-1)/(9-1) On Thu, Jan 27, 2011 at 4:55 PM, nishaanth nishaant...@gmail.com wrote: (91-1)/9 On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 9 + 1 - ( 1 / 9 ) On Wed, Jan 26, 2011 at 10:29 PM, satish satish@gmail.com wrote: 19-(9/1). -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ankit Agarwal B.Tech. 3rd Year Computer Science Engineering IIT Rajasthan -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Coding question.............
correct me if anything wrong it's a rectangle. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Doubt regarding Pointers in C......
@Nishaanth,
boiling down to how things work everything is pass by value in C (or you can
argue for hours as Jammy said)
when your function prototype contains a pointer it is simply passed (copied)
the address which was contained in the variable(pointer here) which was
passed during the function call.
use a double pointer as indicated in the above posts.
On Thu, Jan 27, 2011 at 9:28 PM, Jammy xujiayiy...@gmail.com wrote:
call it by reference.
bst *rec = Null;
insert(rec,5);
void insert(bst *rec,int data){rec-data = data;}
Or declare it as
void insert(bst **rec,int data){*rec-data = data;}
and invoke with insert(rec,5);
First one is just syntactic sugar to me although you can argue about
the whole pass-by-value/ref/pointer thing for hours. :)
On Jan 27, 8:03 am, nishaanth nishaant...@gmail.com wrote:
How can we pass pointers by value. Lets say even if it creates a copy of
the
pointer.
The address stored by the pointer is the same. So when we dereference it
shouldnt it get updated(as its just a memory address)?
On Thu, Jan 27, 2011 at 5:39 PM, ritu ritugarg.c...@gmail.com wrote:
Here you are passing record pointer by value.
as you call insert(record, 5),stack frame of insert contains a copy
of record.after this value is modified by calling program,it should
be either returned explicitly to caller program or needs to be passed
by reference,so that calling program refers to it always by address.
On Jan 27, 4:17 pm, nishaanth nishaant...@gmail.com wrote:
Hi guys,
I have a small doubt regarding pointers and functions.
Consider the following prototype
void insert(bst * head, int data);
This function creates a node and inserts the data in the node. Lets
say i
call this function iteratively from main.
main(){
bst* record=NULL;
insert(record, 5);
insert(record, 8);
}
I see that record is not getting modified. Now is this related to
call by
value. But since we are passing pointers shouldnt the change get
reflected
in main.
isnt is similar to passing an array?
Enlighten me in this regard. I am tired of segfaults :(
Regards,
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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] MICROSOFT IDC
sort in-place and check. O(nlogn) time and O(1) space. On Wed, Jan 12, 2011 at 2:53 AM, Aniket aniket...@gmail.com wrote: Find the intersection of two unsorted singly linked list in O(1) space and less than O(n^2) complexity. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Amazon Intrerview
Based on various comments I think folks do not consider B in the path from A to C which leads to the LCA solution. @SVIX, one can implement the tree with a parent pointer in each node but that doesn't matter in the general case. What you are essentially saying is: consider the tree to be a directed graph with parent - child link to be one way, if that were the case we cannot even reach from A to C so that is out of question that's why we consider it to be a both way link. Now given this one can always argue that B lies in the path from A to C! i.e. A-D-M-B-M-C so here we can, perhaps, define a shortest path from A to C and it has to go through LCA. @all guys, one request please use @XYZ in case you are referring to a particular post by the person XYZ unless it is a general comment. just to avoid confusion. On Tue, Jan 11, 2011 at 8:06 PM, juver++ avpostni...@gmail.com wrote: The tree can be unrooted. Although, in any tree there is unique path from one node to another. Not only from the parent to childs. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Amazon Intrerview
the question is: does B lie in the path from A to C below? D / \ / \ A M / \ /\ BC if yes, DFS suffices. if no, it doesn't. LCA method would work in this case. On Sun, Jan 9, 2011 at 10:44 PM, Algoose chase harishp...@gmail.com wrote: @Juver++ I am not sure if your input represents a path as asked in the problem. We typically think of a path within a binary tree as a downward path(from root to a leaf) thats not spread across different branches. Of course, if you consider that example as a valid case, then DFS wont work ! On Sun, Jan 9, 2011 at 9:57 PM, nishaanth nishaant...@gmail.com wrote: please describe the tree...give an elaborate explanation to your input On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote: x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] algo to count the items in a list
sort list.txt|uniq -c On Fri, Oct 15, 2010 at 7:00 AM, Kumar S kush...@gmail.com wrote: Q : A file has list of names. We need an algorithm to find the number each names repeats in that list. NOT case sensitive Example... namefile.txt has the content.. bob abi jack ram jim tim joey riya kris bob kris ram jack joe joe joey bob bob bob kris joe this has more than 32000 in the list.. not limited number . Output : must have the distinct names and the count against them.. Appreciate your inputs. Thanks n have a good one -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: 2 elements with sum = x
Better than O(n):
start = 0;
end = n-1;
Loop
{
take a[start] and search for a number equal to or just less than x -
a[start] in array between a[start] and a[end]
If x - a[start] is found, break;
else
Lets this number be at position p. Set end = p
Now, take a[end] and search for a number equal to or just larger than
x-a[end] in array between a[start] and a[end].
If x - a[end] is found, break;
else
Let this number be at position p. Set start = p;
}(until start=end)
For searching the number, use binary search.
Enjoy..
On Sun, Oct 10, 2010 at 6:59 PM, ashish agarwal
ashish.cooldude...@gmail.com wrote:
take two pointer p and q
p=a[0] and q=a[n-1];
sum=p+q;
if(sumx)
q--;
if (sumx)
p++;
On Sun, Oct 10, 2010 at 6:54 PM, Rohit email.rohit.n...@gmail.com wrote:
On Oct 10, 10:48 am, Shravan shravann1...@gmail.com wrote:
http://ideone.com/D5W2y
Good :).
What if array is unsorted. What will be the best solution in terms of
time complexity?
Better then (nlog(n)+n).
Regards
Rohit
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Gupta
--
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 push/pop/min or max in O(1)
On Tue, Oct 5, 2010 at 9:47 AM, saurabh singh saurabh.n...@gmail.comwrote:
elaborate plz
For every new element in stack, you need thrice of space to store the min
and max elements also. This has the effect that at state of stack, you can
get the min and max till that point. Instead of this, maintaining a new
stack for min elements would be much more efficient in terms of memory since
in that all the number of elements would be lesser than the main one.
so, basically in your solution, the size of object will be three times
bigger than the data type which can hold the number otherwise.
On Tue, Oct 5, 2010 at 9:42 AM, Saurabh Gupta
saurabhgupta1...@gmail.comwrote:
In this method, the extra memory is used. In fact, maintaining a separate
stack of min and max would consume lesser memory than this.
On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh
saurabh.n...@gmail.comwrote:
You will just need to see what is min and max available on the current
top before push. in case of pop u dnt need to do anything...
consider this array imp of stack
each array index is stored with this object : {data, min_till_here,
max_till_here}
-Top
[{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
So if u push say 20 then at top u see whats max and min till now. since
curr min (-6) is smaller than 20 so min remains unaffected and since curr
max (9) is smaller than 20 so curr max becomes 20. Hence the object at top
in stack looks like {20,-6,20}
On Wed, Sep 29, 2010 at 10:18 PM, albert theboss
alberttheb...@gmail.com wrote:
when we pop out something
we need to find the max min again if max or min is popped out...
this ll take again O(n) to find max and min
Correct me if am wrong
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Saurabh
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Saurabh
--
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.comalgogeeks%2bunsubscr...@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 push/pop/min or max in O(1)
In this method, the extra memory is used. In fact, maintaining a separate
stack of min and max would consume lesser memory than this.
On Thu, Sep 30, 2010 at 12:17 AM, saurabh singh saurabh.n...@gmail.comwrote:
You will just need to see what is min and max available on the current top
before push. in case of pop u dnt need to do anything...
consider this array imp of stack
each array index is stored with this object : {data, min_till_here,
max_till_here}
-Top
[{4,4,4} , {2,2,4}, {7,2,7} , {-6,-6,7}, {1,-6,7}, {9,-6,9}]
So if u push say 20 then at top u see whats max and min till now. since
curr min (-6) is smaller than 20 so min remains unaffected and since curr
max (9) is smaller than 20 so curr max becomes 20. Hence the object at top
in stack looks like {20,-6,20}
On Wed, Sep 29, 2010 at 10:18 PM, albert theboss
alberttheb...@gmail.comwrote:
when we pop out something
we need to find the max min again if max or min is popped out...
this ll take again O(n) to find max and min
Correct me if am wrong
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
Saurabh
--
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.comalgogeeks%2bunsubscr...@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: array
check for 1st element if it occurs n times if not check for last element if it occurs n times if not move a block of 3 On Sat, Jul 3, 2010 at 3:38 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: @dave akash said Can you please tell me why you chose a bst, simply traversing the array and incrementing the count would have also worked in this case and it would have been O(n). so .. if the range will be high suppose there r few numbers which are very large so taking an auxillary array and incrementing count will waste a lot of memory On Fri, Jul 2, 2010 at 11:13 PM, Dave dave_and_da...@juno.com wrote: @Jalaj. I don't understand how your comment contributes to the discussion. Please explain. Dave On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: for count suppose if there are very big numbers ..then space will nt be efficient On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] rotation
why not block reversal? On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.com wrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.comwrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Best Regards Akash Gangil -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 with duplicates?
Disagree a BST can have duplicate entries the 'equal to' term in the definition allows that I am surprised to see in the Wiki: From the above properties it naturally follows that: - Each node (item in the tree) has a distinct key. The example in the question is definitely wrong in the sense that it allows duplicates in both directions once the definition is fixed one can have duplicates in 1 direction i.e. left or right I believe. On Thu, Jul 1, 2010 at 10:01 PM, mohit ranjan shoonya.mo...@gmail.comwrote: @Amit as per wiki, BST definition is - The left subtree of a node contains only nodes with keys *less than the node's key*. - The right subtree of a node contains only nodes with *keys greater than or equal to the node's key*. so, this following example is not a BST... Mohit On Thu, Jul 1, 2010 at 8:04 PM, amit amitjaspal...@gmail.com wrote: Can a BST have duplicate entries ?? .8 .../...\ .7..9 /..\/..\ ...6...8..8...10 i.e is this a BST . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] microsoft
place the sensors on the same color portion well apart to distinguish which one indicated the change first the sensor number to indicate a change first indicates the direction. On Fri, Jul 2, 2010 at 3:37 PM, Abhirup Ghosh abhiru...@gmail.com wrote: I think those two sensors should not be exactly opposite to each other to make the decision meaningful. On Fri, Jul 2, 2010 at 11:58 AM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: I think two sensors beside one another is enough to find the direction of rotation. At some time both will be sensing the same color but when there will be change of color below one of the senser, after some time same change will be below other one, and from this we can say that the direction of the disk rotation is from first senser to second senser direction. hope i am clear... -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: array
@Dave: ah, yeah, you are right On Fri, Jul 2, 2010 at 11:13 PM, Dave dave_and_da...@juno.com wrote: @Jalaj. I don't understand how your comment contributes to the discussion. Please explain. Dave On Jul 2, 10:56 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: for count suppose if there are very big numbers ..then space will nt be efficient On Fri, Jul 2, 2010 at 7:05 PM, saurabh gupta sgup...@gmail.com wrote: @Dave, for 2n+1 you can have a configuration where repeated nos may not be adjacent you need a block of 3 instead of 2. On Fri, Jul 2, 2010 at 6:04 PM, Dave dave_and_da...@juno.com wrote: For problem 1, finding a number that is repeated just once is enough. Scan the array to see if there are two adjacent numbers that are equal. If so, that is your repeated number. Otherwise, look for the repeat in the first 5 numbers. O(n). Dave On Jul 1, 11:43 am, sharad sharad20073...@gmail.com wrote: 1.an array of 2n+1 elements is given .one element is repeated n times and rest all are different.find the no repeated. 2.same question as above but this time other no's are not different ..i.e they can repeat. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] isomorphic trees
@Harish, it does.
@Divya, r we not on the same page.
On Thu, Jun 10, 2010 at 10:20 AM, Harish U harishs...@gmail.com wrote:
@Saurabh
I believe for Isomorphic trees only the structure counts not the value at
each nodes.
So i think there is no need to compare the value at the corresponding node
positions of the two trees.
On Wed, Jun 9, 2010 at 11:15 PM, saurabh gupta sgup...@gmail.com wrote:
is-isomorphic(t1, t2) {
t1ld = t1-left-data
t2ld = t2-left-data
//.
//base case for null or replace by sentinels and check
if( t1ld == t2ld t1rd == t2rd)
return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd,
t2rd)
if (t1ld == t2rd t1rd == t2ld)
return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd,
t2ld)
return false;
}
On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.comwrote:
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may
not. if all right and left are interchanged then it is mirror tree. i think
ur code is for mirror tree and not isomorphic 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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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] isomorphic trees
is-isomorphic(t1, t2) {
t1ld = t1-left-data
t2ld = t2-left-data
//.
//base case for null or replace by sentinels and check
if( t1ld == t2ld t1rd == t2rd)
return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd, t2rd)
if (t1ld == t2rd t1rd == t2ld)
return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld)
return false;
}
On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote:
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may
not. if all right and left are interchanged then it is mirror tree. i think
ur code is for mirror tree and not isomorphic 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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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] Number of sequences of n binary digits that don't contain two 1's in a row
recursion. for length n if the count is T(n) then T(n) = 1st digit 0 + 1st digit 1 = T(n-1) + 1st digit 1 2nd digit 0 = T(n-1) + T(n-2) QED. On Tue, Jun 8, 2010 at 9:03 PM, Raj N rajn...@gmail.com wrote: I just checked out with so many possibilities and it is indeed matching. I may not be correct though. On Tue, Jun 8, 2010 at 7:50 PM, divya jain sweetdivya@gmail.comwrote: how do u come to this formula T(n)=fib(n+2).. plz explain On 7 June 2010 21:19, saurabh gupta sgup...@gmail.com wrote: it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Number of sequences of n binary digits that don't contain two 1's in a row
it might be referring to no of sequences (say T(n) ) with no consecutive 1's for n = 3, ans would be 5 viz. 000, 001, 010, 100, 101 T(n) = fib(n+2) where fib = Fibonacci series which is interesting. On Sat, Jun 5, 2010 at 11:40 AM, Raj N rajn...@gmail.com wrote: @sharad: What about 101 even it doesn't have two 1's in a row On Sat, Jun 5, 2010 at 8:59 AM, sharad kumar aryansmit3...@gmail.comwrote: @rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is required answer. On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote: Hi, I came across this question to find the number of sequences of n binary digits that don't contain 2 1's in a row. I wanted to know what exactly this means. Is it like if n=3 then compute all binary numbers having 3 digits which don't have consecutive 1's 110, 011, 111 ?? If not help me understanding it. 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Valid permutation of the brackets
@Rohit: you have to visit all valid solutions at least once, (as you are printing it) so the lower bound is Cn (nth catalan number) On Fri, Jun 4, 2010 at 1:40 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @jitendra: How can you say that no polynomial algo can be found. I think you are wrong. A simple memoized formulation will make this polynomial because of the optimal substructure.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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?
@Divya: nope, your Q requires equal count too whereas this doesn't. On Thu, Jun 3, 2010 at 1:06 PM, divya jain sweetdivya@gmail.com wrote: same question as wat i asked in partioning of array such that the diff is min. On 31 May 2010 22:07, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Same question with interesting answers in stackoverflow : http://stackoverflow.com/questions/890171/algorithm-to-divide-a-list-of-numbers-into-2-equal-sum-lists On Mon, May 31, 2010 at 5:54 PM, Anurag Sharma anuragvic...@gmail.comwrote: 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 nikhil.bhoja...@gmail.comwrote: 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 wka...@yahoo.com 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 thisisv...@rediffmail.com 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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?
yep, constraints are fewer here but in terms of problem statement 'same' and 'similar' can create diversions. On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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?
This should be solvable by dp as in knapsack problem where value = weights and W = S/2. where S = sum of all elements in the array. The claim here is diff in sum of two subsets will be minimum when one maximizes a sub-set sum (say s) where sum (s) is closest to S/2. Divya's problem is looking for balanced sets which may or may not be feasible using a modified form of this. On Thu, Jun 3, 2010 at 7:06 PM, saurabh gupta sgup...@gmail.com wrote: yep, constraints are fewer here but in terms of problem statement 'same' and 'similar' can create diversions. On Thu, Jun 3, 2010 at 6:01 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] infy color balls
C(n-1,k-1) if balls are similar On Fri, Apr 30, 2010 at 4:34 PM, Ashish Mishra amishra@gmail.comwrote: One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 the middle of a singly linked list which has a cycle in it
@Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: sorry, i forgot to see *singly* linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 the middle of a singly linked list which has a cycle in it
@Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Rohit -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
Perhaps, if n is the length (from the beginning to the point where the loop ends after a traversal of the loop) then n/2 is the middle, i.e. length of list / 2 in which case middle is easy to find. Is that the definition, Sanjana ? On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Largest span of Increasing Pair in an array
Hi Achala,
This fails for:
0 1 2000 3 4 5 6
prog's output:
arr[j]=2000,arr[k]=0,j=2,k=0
correct output should be:
arr[j]=6,arr[k]=0,j=6,k=0
you seem to be relying on the difference in the 'values' (contents) instead
of the index span.
On Mon, Mar 22, 2010 at 11:10 PM, achala sharma 3.ach...@gmail.com wrote:
One Solution for Largest span in array,I have checked it on many
inputs,according to me its working fine
void Large_Span(int * arr,int num_elem)
{
int j=1,k=0,i,prev_k=0;
for(i=1;inum_elem;i++)
{
if(arr[i]arr[i-1])
{
if((arr[j]-arr[k])(arr[i]-arr[i-1]))
{
if(jarr[i] k=arr[i-1])
{
j=i;
}
else if((jarr[i] karr[i-1])||(jarr[i] karr[i-1]))
{
j=i;
k=i-1;
}
}
else if(arr[k]arr[i-1])
{
if(kj)
{
prev_k=k;
k=i-1;
}
}
else if(arr[j]arr[i])
j=i;
}
else
{
if(arr[k]arr[i])
{
if(ij)
{
prev_k=k;
k=i;
}
else
k=i;
}
}
}
if(kj)
{
k=prev_k;
}
printf(arr[j]=%d,arr[k]=%d,j=%d,k=%d,arr[j],arr[k],j,k);
}
On Mon, Mar 22, 2010 at 8:28 AM, Manish mannishmaheshw...@gmail.comwrote:
This does not look like a solution for the posted problem.
This fails the test case {2, 7, 6, 0, 100}, where the answer should
have been 4, for k=0 and j=4.
Manish
On Mar 20, 1:49 pm, saurabh gupta sgup...@gmail.com wrote:
This may not be the optimal solution to
Given an array of integers A[N], find the maximum value of (j-k) such
that A[k] = A[j] jk.
I am looking for a solution with time complexity better than O(N^2).
this was in response to
how u can solve it in o(n)
and
how to solve this in the claimed O(N) time.
On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland rpbol...@gmail.com
wrote:
On Mar 15, 10:07 am, saurabh gupta sgup...@gmail.com wrote:
while you scan the array
maintain four indices plus two lengths
two indices and a length mark one sub-array - start,end, length
each such sub-array indicates a non-decreasing sequence,
call them S1 and S2.
while one scans, S2 keeps track of incoming elements (curr sequence)
S1 keeps track of the maximum length (along with indices) so far
(prev
sequence)
as one encounters an element which is less than the previous
element,
this marks the end of S2,
S1 replaces S2 if len S2 len S1 else S2 starts afresh from this
new
element.
In the end if len S2 len S1 answer = S2
else answer = S1.
PS: In the beginning and till one encounters a smaller element than
the
prev one for the first time, S1 = S2
I agree that this is a nice algorthithm that solves the
largest non decreasing sequence problem.
However, I don't agree that this solves the problem
originally posted.
Regards,
Ralph Boland
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and
cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
You received this message because you
Re: [algogeeks] Re: Largest span of Increasing Pair in an array
ah yes, this is not a solution to the posted problem. I solved what Vikrant stated, I guess I was mislead by 'increasing'. Thanks Ralph and Vikrant for pointing it out. My apologies. Hmmm. for the actual problem, right now I can think of only an O(nlogn) solution. On Sun, Mar 21, 2010 at 11:51 AM, vikrant singh vikrantsing...@gmail.comwrote: Is the problem like this, Given an array of integers A[N], find the maximum value of (j-k) such that A[k] = A[j] jk. *for all i j and i=k, A[i]=A[i-1] * On Sat, Mar 20, 2010 at 11:19 PM, saurabh gupta sgup...@gmail.com wrote: This may not be the optimal solution to Given an array of integers A[N], find the maximum value of (j-k) such that A[k] = A[j] jk. I am looking for a solution with time complexity better than O(N^2). this was in response to how u can solve it in o(n) and how to solve this in the claimed O(N) time. On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland rpbol...@gmail.comwrote: On Mar 15, 10:07 am, saurabh gupta sgup...@gmail.com wrote: while you scan the array maintain four indices plus two lengths two indices and a length mark one sub-array - start,end, length each such sub-array indicates a non-decreasing sequence, call them S1 and S2. while one scans, S2 keeps track of incoming elements (curr sequence) S1 keeps track of the maximum length (along with indices) so far (prev sequence) as one encounters an element which is less than the previous element, this marks the end of S2, S1 replaces S2 if len S2 len S1 else S2 starts afresh from this new element. In the end if len S2 len S1 answer = S2 else answer = S1. PS: In the beginning and till one encounters a smaller element than the prev one for the first time, S1 = S2 I agree that this is a nice algorthithm that solves the largest non decreasing sequence problem. However, I don't agree that this solves the problem originally posted. Regards, Ralph Boland -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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: Largest span of Increasing Pair in an array
while you scan the array
maintain four indices plus two lengths
two indices and a length mark one sub-array - start,end, length
each such sub-array indicates a non-decreasing sequence,
call them S1 and S2.
while one scans, S2 keeps track of incoming elements (curr sequence)
S1 keeps track of the maximum length (along with indices) so far (prev
sequence)
as one encounters an element which is less than the previous element,
this marks the end of S2,
S1 replaces S2 if len S2 len S1 else S2 starts afresh from this new
element.
In the end if len S2 len S1 answer = S2
else answer = S1.
PS: In the beginning and till one encounters a smaller element than the
prev one for the first time, S1 = S2
On Mon, Mar 15, 2010 at 6:56 PM, Pramod Negi negi.1...@gmail.com wrote:
Hello Saurabh,
can you explain the algo??
On Sun, Mar 14, 2010 at 9:55 PM, saurabh gupta sgup...@gmail.com wrote:
O(N)
my @a = @ARGV;
my ($m, $j, $k, $l) = (0, 0, 0, 0);
my $len = 0;
my $curr = 0;
for (my $i = 1; $i @a; $i++) {
if ($a[$i] = $a[$i-1]) {
if ($m == $k) {
$j++;
$l++;
$curr++;
$len++;
}
else {
$l++;
$curr++;
}
}
else {
if ($curr $len) {
$m = $k;
$j = $l;
$len = $curr;
}
$k = $l = $i;
$curr = 0;
}
}
if ($curr $len) {
print $k $l;
}
else {
print $m $j;
}
On Sun, Mar 14, 2010 at 8:49 PM, Ralph Boland rpbol...@gmail.com wrote:
On Mar 14, 7:46 am, ASHISH MISHRA meetcoolash...@gmail.com wrote:
@ankur how u can solve it in o(n)
i suppose u need atleast o(n lgn)
On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal
ankur.mast@gmail.comwrote:
o(n) is the best sol known to me..
On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi negi.1...@gmail.com
wrote:
i guess sorting will do the work.
any other constraint??
On Sun, Sep 6, 2009 at 9:52 AM, p0r$h 1987.shis...@gmail.com
wrote:
Given an array of integers A[N], find the maximum value of (j-k)
such
that A[k] = A[j] jk.
I am looking for a solution with time complexity better than
O(N^2).
I don't know how to solve this in the claimed O(N) time.
However, I have coded a data structure that,
given j, will find k in O(log(N)) time.
With it you can solve your problem in O(N log N) time.
The data structure is built in O(N) time and space.
It is part of a larger data structure that I will implement
and release as open source in a few months.
Regards,
Ralph Boland
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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: Largest span of Increasing Pair in an array
O(N)
my @a = @ARGV;
my ($m, $j, $k, $l) = (0, 0, 0, 0);
my $len = 0;
my $curr = 0;
for (my $i = 1; $i @a; $i++) {
if ($a[$i] = $a[$i-1]) {
if ($m == $k) {
$j++;
$l++;
$curr++;
$len++;
}
else {
$l++;
$curr++;
}
}
else {
if ($curr $len) {
$m = $k;
$j = $l;
$len = $curr;
}
$k = $l = $i;
$curr = 0;
}
}
if ($curr $len) {
print $k $l;
}
else {
print $m $j;
}
On Sun, Mar 14, 2010 at 8:49 PM, Ralph Boland rpbol...@gmail.com wrote:
On Mar 14, 7:46 am, ASHISH MISHRA meetcoolash...@gmail.com wrote:
@ankur how u can solve it in o(n)
i suppose u need atleast o(n lgn)
On Sun, Sep 6, 2009 at 2:52 PM, ankur aggarwal ankur.mast@gmail.com
wrote:
o(n) is the best sol known to me..
On Sun, Sep 6, 2009 at 1:54 PM, Pramod Negi negi.1...@gmail.com
wrote:
i guess sorting will do the work.
any other constraint??
On Sun, Sep 6, 2009 at 9:52 AM, p0r$h 1987.shis...@gmail.com wrote:
Given an array of integers A[N], find the maximum value of (j-k) such
that A[k] = A[j] jk.
I am looking for a solution with time complexity better than O(N^2).
I don't know how to solve this in the claimed O(N) time.
However, I have coded a data structure that,
given j, will find k in O(log(N)) time.
With it you can solve your problem in O(N log N) time.
The data structure is built in O(N) time and space.
It is part of a larger data structure that I will implement
and release as open source in a few months.
Regards,
Ralph Boland
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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] Cartesian Product in set theory
you can always eliminate them
On Tue, Feb 9, 2010 at 5:07 PM, Parisa paris...@gmail.com wrote:
Not indeed.
Cartesian product produces tuples as the result, but I am interested in the
set form of these tuples.
if there are two sets like X={A,B,C} Y={A,B}
then The Cartesian product will be:
X.Y={(A,A),(A,B),(B,A),(B,B),(C,A),(C,B)}
Whereas if insted of tuples sets were produced it would be like the
followings:
X.Y={{A}, {A,B}, {B}, {A,C}, {B,C}}
P.
On Feb 9, 2010, at 5:21 AM, vignesh radhakrishnan wrote:
The unordered pair will be a subset of cartesian product. What is the
significance of it?
On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote:
Hi all,
I have came across a problem and I am not aware if there is such a
thing in set theory and if so what is it called.
Mainly I have several sets that I am interested in their cartesian
product. But this cartesian product should not be a set of ordered
pairs but a set of sets. Basically unordered pairs.
I wonder if this concept is well defined and what is it called.
Thanks.
P.
--
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.comalgogeeks%2bunsubscr...@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.
Parisa
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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 parent/grandparent relationship of nodes in binary tree in O(1) time
@Manisha can u pls elaborate, ith node index lies in a range ? extending Bijlwan's solution, node numbering on each new level begins by multiplying the index of the leftmost node in previous level by 2^k and then in incrementing it by one. and while one checks one shifts by k. On Sat, Feb 6, 2010 at 5:31 PM, Manisha pgo...@gmail.com wrote: One possible soln is: Store the k ary- tree nodes in an array such that child of the ith node lies in index range from (k*i -1) to (k*i + k -2) range. This way child and grandchild index and corresponding items can be found in constant time. On Feb 5, 8:47 pm, Anurag Bhatia abhati...@gmail.com wrote: @Nirmal: Did you find a solution as yet? On Thu, Jan 28, 2010 at 6:40 PM, Nirmal nirm...@gmail.com wrote: I found this problem in one of the interview form, that it is interesting to discuss Problem : There are two nodes given in a tree(not binary tree). Find whether one node is parent/grand parent of other. order should be O(1). You are allowed to do any amount of preprocessing -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Add 2 long integers with digits represented by linked lists
this is how it works
list 1 : H1-5-5-5-5-5
list 2 : H2-4-4-4-4-4
now we need to return a list say list 3 as our answer which contains the sum
and length at most n+1 (in this case as m=n)
step 1 : we spent O(n) to simply conclude they are of same length
step 2:
list 3: 9-9-9-9-9-H3
(we haven't used any extra space simply utilized the space where we store
the answer)
(not the pointers in lis3 they are in the 'opposite' sense)
plus we haven't touched 1 or 2
step 3:
list 3: H3-9-9-9-9-9
this is the answer.
This is actually a special case.
On Tue, Feb 2, 2010 at 10:40 AM, Algoose Chase harishp...@gmail.com wrote:
@saurabh :
so you scanned to find out that both lists are same : O(n) (agreed)
prepare list 3 in time O(n) (agreed)
process list 3 in time O(n) (*HOW ??*)
can you run through your method and show how you process list 3 in O(n)
using the below lists as input:
5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you
cant use recursion. and you need to traverse the list LEFT TO RIGHT to
satisfy the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 =
2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must be
O(n) only but you certainly need multiple passes depending upon the input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.com wrote:
the key observation is that your requirement for no space is nullified by
using the space in the resultant list.
so you scanned to find out that both lists are same : O(n)
prepare list 3 in time O(n)
process list 3 in time O(n)
current list 3 is the answer as list 4 is empty
total time O(n) as k is small
On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta sgup...@gmail.com wrote:
nope,
if both lists are of same length list 4 is not required and you save time
to deal with list 4
so, you have list 3 only
time reqd is O(3n)
3 passes approximately
On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase harishp...@gmail.comwrote:
Thats true ! , The purpose is to add very long integers such that we
cant use premative data types to represent them.
The point I was trying to prove is : you would need to go through
multiple passes through the list(essentially to propagate carry) when you
have conditions like No Reversing the original lists and no recursion and
no
to any extra memory usage.
@ saurabh: Hope you have not considered the worst case before
generalizing the running time to 2n+m .
lets assume the 2 lists are of same size so n = m.This eliminates the
need to find out m or to create list 4
and lets assume the linked list are 5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
Only thing is you need to create list 3 (as u have mentioned) . Now its
not possible to add the 2 lists through a single pass from left to right .
This would need n passes on a linked list of size n making the running
time
n^2.
On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta sgup...@gmail.comwrote:
this defeats the purpose,
they are stored in linked list because they cannot be stored in a given
type.
On Thu, Jan 28, 2010 at 3:25 AM, Deva R r.deva...@gmail.com wrote:
i faced this qn in * interview.
best soln i could give was:
- traverse each list and derive both the numbers.. something like
below
node = list-head;
i=1; value =0;
while (node)
{ value = (node-data)*i +value;
i*=10;
node = node-next;
}
- add both the numbers. u can either return the number or form a new
list and return.
i gave the code.. and its o(m+n), for lists of size m,n.
-Deva
On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta sgup...@gmail.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
its not exponential
time to find out m = m
time to create list 3 = m
time to create list 4 = n-m
time to come up with proper added list (list 3 modification) = m
time to merge list 3 and list 4 = n-m
total time = 2n+m
except step 1 all are reversals with approximately same constant and
constant for step 1 is smaller
so one can say
O(2n+m)
On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia abhati...@gmail.com
wrote:
If that is the representation, then the lists have to be reversed.
Otherwise the time goes up exponentially.
On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase
harishp...@gmail.com wrote:
Condition:
Can we do it keeping the original lists intact ? ie without
reversing it.
I mean , No recursion no Reversing ... is it possible ?
@kumar :
15234 is represented as 1-5-2-3-4
On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta
sgup...@gmail.com wrote:
perhaps you mean,
reverse each link list O(n+m).
then sum each node with carryover maintained.
On Wed, Jan
Re: [algogeeks] recursive algorithm
@DMX, please clarify your question
you mean given d arrays/lists of variable lengths i.e. n1, n2, ..., nd one
needs to iterate over them
iteratively and recursively ?
On Tue, Feb 2, 2010 at 8:50 AM, Sieu Truc sieut...@gmail.com wrote:
initial assignmnet: g()={n1,..,nd)
inter(i)
{
if(i0) return;
for(int j=0;jg(i),j++)
{
do st
}
inter(i-1);
}
initial run: inter(d-1)
inter(i,j)
{
if(j==0)
{
if(i==0) return;
inter(i-1,g(i-1));
}
else
{
do st
inter(i,j-1);
}
}
initial run: inter(d-1,g(0))
inter()
{
for(int i=0 ; ig(0);i++)
{
do st
}
.//d times loop for
}
May it satisfy your think?
On Mon, Feb 1, 2010 at 11:56 AM, DMX deepudan...@gmail.com wrote:
Can you please help me with this one.
write two algorithms that iterate over every index from (0,0,..,0)
to (n1,n2,..,nd).Make one algorithm recursive and the other
iterative.
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Add 2 long integers with digits represented by linked lists
it doesn't matter
in that case
list 3 becomes: (step 2)
9-9-9-9-10-H3
after processing it becomes (step 3)
H3-1-0-0-0-0-0
On Tue, Feb 2, 2010 at 3:42 PM, Harish U harishs...@gmail.com wrote:
saurabh pleeease look at the list that i have mentioned carefully
.. second list must be H2-4-4-4-4-5 and not H2-4-4-4-4-4.
Its straight forward to do the job with the list you have done with so far.
On Tue, Feb 2, 2010 at 12:22 PM, saurabh gupta sgup...@gmail.com wrote:
this is how it works
list 1 : H1-5-5-5-5-5
list 2 : H2-4-4-4-4-4
now we need to return a list say list 3 as our answer which contains the
sum and length at most n+1 (in this case as m=n)
step 1 : we spent O(n) to simply conclude they are of same length
step 2:
list 3: 9-9-9-9-9-H3
(we haven't used any extra space simply utilized the space where we store
the answer)
(not the pointers in lis3 they are in the 'opposite' sense)
plus we haven't touched 1 or 2
step 3:
list 3: H3-9-9-9-9-9
this is the answer.
This is actually a special case.
On Tue, Feb 2, 2010 at 10:40 AM, Algoose Chase harishp...@gmail.comwrote:
@saurabh :
so you scanned to find out that both lists are same : O(n) (agreed)
prepare list 3 in time O(n) (agreed)
process list 3 in time O(n) (*HOW ??*)
can you run through your method and show how you process list 3 in O(n)
using the below lists as input:
5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you
cant use recursion. and you need to traverse the list LEFT TO RIGHT to
satisfy the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 =
2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must
be O(n) only but you certainly need multiple passes depending upon the
input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.comwrote:
the key observation is that your requirement for no space is nullified
by using the space in the resultant list.
so you scanned to find out that both lists are same : O(n)
prepare list 3 in time O(n)
process list 3 in time O(n)
current list 3 is the answer as list 4 is empty
total time O(n) as k is small
On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta sgup...@gmail.comwrote:
nope,
if both lists are of same length list 4 is not required and you save
time to deal with list 4
so, you have list 3 only
time reqd is O(3n)
3 passes approximately
On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase
harishp...@gmail.comwrote:
Thats true ! , The purpose is to add very long integers such that we
cant use premative data types to represent them.
The point I was trying to prove is : you would need to go through
multiple passes through the list(essentially to propagate carry) when you
have conditions like No Reversing the original lists and no recursion
and no
to any extra memory usage.
@ saurabh: Hope you have not considered the worst case before
generalizing the running time to 2n+m .
lets assume the 2 lists are of same size so n = m.This eliminates the
need to find out m or to create list 4
and lets assume the linked list are 5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
Only thing is you need to create list 3 (as u have mentioned) . Now
its not possible to add the 2 lists through a single pass from left to
right
. This would need n passes on a linked list of size n making the running
time n^2.
On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta sgup...@gmail.comwrote:
this defeats the purpose,
they are stored in linked list because they cannot be stored in a
given type.
On Thu, Jan 28, 2010 at 3:25 AM, Deva R r.deva...@gmail.com wrote:
i faced this qn in * interview.
best soln i could give was:
- traverse each list and derive both the numbers.. something like
below
node = list-head;
i=1; value =0;
while (node)
{ value = (node-data)*i +value;
i*=10;
node = node-next;
}
- add both the numbers. u can either return the number or form a new
list and return.
i gave the code.. and its o(m+n), for lists of size m,n.
-Deva
On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta
sgup...@gmail.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta
sgup...@gmail.comwrote:
its not exponential
time to find out m = m
time to create list 3 = m
time to create list 4 = n-m
time to come up with proper added list (list 3 modification) = m
time to merge list 3 and list 4 = n-m
total time = 2n+m
except step 1 all are reversals with approximately same constant
and constant for step 1 is smaller
so one can say
O(2n+m)
On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia
abhati...@gmail.com wrote:
If that is the representation, then the lists have to be
reversed.
Otherwise
Re: [algogeeks] Add 2 long integers with digits represented by linked lists
nope,
if both lists are of same length list 4 is not required and you save time to
deal with list 4
so, you have list 3 only
time reqd is O(3n)
3 passes approximately
On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase harishp...@gmail.com wrote:
Thats true ! , The purpose is to add very long integers such that we cant
use premative data types to represent them.
The point I was trying to prove is : you would need to go through multiple
passes through the list(essentially to propagate carry) when you have
conditions like No Reversing the original lists and no recursion and no to
any extra memory usage.
@ saurabh: Hope you have not considered the worst case before generalizing
the running time to 2n+m .
lets assume the 2 lists are of same size so n = m.This eliminates the need
to find out m or to create list 4
and lets assume the linked list are 5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
Only thing is you need to create list 3 (as u have mentioned) . Now its not
possible to add the 2 lists through a single pass from left to right . This
would need n passes on a linked list of size n making the running time n^2.
On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta sgup...@gmail.com wrote:
this defeats the purpose,
they are stored in linked list because they cannot be stored in a given
type.
On Thu, Jan 28, 2010 at 3:25 AM, Deva R r.deva...@gmail.com wrote:
i faced this qn in * interview.
best soln i could give was:
- traverse each list and derive both the numbers.. something like below
node = list-head;
i=1; value =0;
while (node)
{ value = (node-data)*i +value;
i*=10;
node = node-next;
}
- add both the numbers. u can either return the number or form a new list
and return.
i gave the code.. and its o(m+n), for lists of size m,n.
-Deva
On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta sgup...@gmail.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
its not exponential
time to find out m = m
time to create list 3 = m
time to create list 4 = n-m
time to come up with proper added list (list 3 modification) = m
time to merge list 3 and list 4 = n-m
total time = 2n+m
except step 1 all are reversals with approximately same constant and
constant for step 1 is smaller
so one can say
O(2n+m)
On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia abhati...@gmail.comwrote:
If that is the representation, then the lists have to be reversed.
Otherwise the time goes up exponentially.
On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase harishp...@gmail.com
wrote:
Condition:
Can we do it keeping the original lists intact ? ie without
reversing it.
I mean , No recursion no Reversing ... is it possible ?
@kumar :
15234 is represented as 1-5-2-3-4
On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta sgup...@gmail.com
wrote:
perhaps you mean,
reverse each link list O(n+m).
then sum each node with carryover maintained.
On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia
abhati...@gmail.com
wrote:
Let us take an example -
Num 1 = 123456
Num 2= 1234
Link-1-Link-2-Link-3-Link-4-Link5-Link6
Link-1-Link-2-Link-3-Link-4
Add nodes into linkedlist 1 till either one of the list is not
null.
Make sure you process the carry in each iteration.
--AB
On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase
harishp...@gmail.com
wrote:
conditions:
NO extra memory (@ stack or Heap) at all. No recursion.
Any body has got any hint about how to get this done ?
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] Re: Merge two BST in O(n) time with O(1)
or a balanced BST can be made in step 3, in linear time too, if one objects to the skew model. 2010/1/29 ShingRay masterrays...@gmail.com Oh, I have said something wrong. 1. Inorder traverse both trees. This gives two sorted list. Θ(m+n) 2. Merge the two sorted list A, B into a new one C. Θ(m+n) 3. Build a new tree using C. Each node of the tree has just one child. Θ(m+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.comalgogeeks%2bunsubscr...@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] Add 2 long integers with digits represented by linked lists
perhaps you mean, reverse each link list O(n+m). then sum each node with carryover maintained. On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia abhati...@gmail.com wrote: Let us take an example - Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 Link-1-Link-2-Link-3-Link-4 Add nodes into linkedlist 1 till either one of the list is not null. Make sure you process the carry in each iteration. --AB On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase harishp...@gmail.com wrote: conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Add 2 long integers with digits represented by linked lists
well, you may reverse them again :-) anyways, assume n m, since our result is again a new link list with size at most n+1. lets use this storage. We can use this storage to begin with. take 2 temp pointers and iterate till you reach the end of either one i.e. the smaller one. now say list 2 has length m, say temp pointer p1 is at position n-m in list 1. we have remaining space of n-m, create a new link list 4 which is list 1 reversed from position 1 to n-m. now sum of any 2 nodes is at most 18, start iterating from position n-m+1 (p1) in list 1 and position 1 in list 2. as you proceed start creating a reverse link list with the sums in each node i.e. list 1 = 4-7-8-1-6 list 2 = 2-3-4 list 3 = 10-4-10 list 4 = 7-4 now reverse list 3 with the following if no 9 save a carry over, sum carry over + number. list 3 becomes: 0-5-0 and carry 1. join 3 and 4 taking care of carry over to get (reversing 4 in the process) 4-8-0-5-0 This also assumes you can store integers 9 in a node which should be fine. On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase harishp...@gmail.com wrote: Condition: Can we do it keeping the original lists intact ? ie without reversing it. I mean , No recursion no Reversing ... is it possible ? @kumar : 15234 is represented as 1-5-2-3-4 On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta sgup...@gmail.com wrote: perhaps you mean, reverse each link list O(n+m). then sum each node with carryover maintained. On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia abhati...@gmail.comwrote: Let us take an example - Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 Link-1-Link-2-Link-3-Link-4 Add nodes into linkedlist 1 till either one of the list is not null. Make sure you process the carry in each iteration. --AB On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase harishp...@gmail.com wrote: conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Add 2 long integers with digits represented by linked lists
its not exponential time to find out m = m time to create list 3 = m time to create list 4 = n-m time to come up with proper added list (list 3 modification) = m time to merge list 3 and list 4 = n-m total time = 2n+m except step 1 all are reversals with approximately same constant and constant for step 1 is smaller so one can say O(2n+m) On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia abhati...@gmail.com wrote: If that is the representation, then the lists have to be reversed. Otherwise the time goes up exponentially. On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase harishp...@gmail.com wrote: Condition: Can we do it keeping the original lists intact ? ie without reversing it. I mean , No recursion no Reversing ... is it possible ? @kumar : 15234 is represented as 1-5-2-3-4 On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta sgup...@gmail.com wrote: perhaps you mean, reverse each link list O(n+m). then sum each node with carryover maintained. On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia abhati...@gmail.com wrote: Let us take an example - Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 Link-1-Link-2-Link-3-Link-4 Add nodes into linkedlist 1 till either one of the list is not null. Make sure you process the carry in each iteration. --AB On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase harishp...@gmail.com wrote: conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] Add 2 long integers with digits represented by linked lists
step 1 is n not m which makes it O(3n) On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.com wrote: its not exponential time to find out m = m time to create list 3 = m time to create list 4 = n-m time to come up with proper added list (list 3 modification) = m time to merge list 3 and list 4 = n-m total time = 2n+m except step 1 all are reversals with approximately same constant and constant for step 1 is smaller so one can say O(2n+m) On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia abhati...@gmail.comwrote: If that is the representation, then the lists have to be reversed. Otherwise the time goes up exponentially. On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase harishp...@gmail.com wrote: Condition: Can we do it keeping the original lists intact ? ie without reversing it. I mean , No recursion no Reversing ... is it possible ? @kumar : 15234 is represented as 1-5-2-3-4 On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta sgup...@gmail.com wrote: perhaps you mean, reverse each link list O(n+m). then sum each node with carryover maintained. On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia abhati...@gmail.com wrote: Let us take an example - Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 Link-1-Link-2-Link-3-Link-4 Add nodes into linkedlist 1 till either one of the list is not null. Make sure you process the carry in each iteration. --AB On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase harishp...@gmail.com wrote: conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
