Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
try this : similar problem http://www.spoj.pl/problems/NOCHANGE/ On Tue, Jun 19, 2012 at 1:32 PM, aditya gupta adityagupta...@gmail.com wrote: this can be solved in a manner similar to knapsack problem. u can take the weight of tha knapsack the be the the various amounts u need to make, 13 cents etc etc. we would need to find a first empty cell. instead of parameter value, use your own parameter specifying the number of stamps used. and u would have to make a smal intuitive change to the manner in which the cells are populated so as to ensure that it picks a combination which reaches an exact amount/weight that u need as opposed to a = amount/weight in regular knapsack. On Tue, Jun 19, 2012 at 10:41 PM, rammar getam...@gmail.com wrote: This can be done with DP. Take an array with values 1 to n. For every number i, try to make it using the stamps available and the 1 to i-1 array. Anytime u find that the upper bound is reached, u return. sudo code. stamps[K]; - Stamp denominations available. a[N] - Array of number of stamps required. a[0] = 0; For i= 1 to n { tempMin = 1000( some large number) For j = 0 to K - loop over the array storing the number of stamp denominations. { if(stamps[j] = i) if( tempMin 1 + a[i-j]) tempMin := 1 + a[i-j]; } if(tempMin maxStampAllowed) { return i; } else { a[i] =tempMin } } This will work with time complexity of O (n*k) . Use of vectors (in c++) can be helpfule for dynamic arrays. P.S. Can we do better? On Tuesday, June 19, 2012 9:25:42 PM UTC+5:30, suzi wrote: The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values. For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps. Is there an algorithm that given the maximum amount of stamps allowed and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/a1ykZ8HaDjEJ. 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. -- Aditya Gupta B.Tech III yr CSE IITR -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SPOJ question LITE
#includeiostream using namespace std; struct node { int num; int l,r; node * left; node * right; }; node * create(node * root,int start,int end); node * update(node * root, int i,int j); int query(node * root,int i,int j); main() { int n,q; cinnq; node * root=new node; root-num=0; root-left=NULL; root-right=NULL; root=create(root,0,n-1); while(q--) { int type,i,j; cintypeij; if(type==0) root=update(root,i,j); if(type==1) coutquery(root,i,j); } } node * create(node * root,int start,int end) { if(start==end) { node * temp=new node(); temp-num=0; temp-right=NULL; temp-left=NULL; temp-l=temp-r=start; return temp; } if(start!=end) { if(root==NULL) root=new node(); root-num=0; root-l=start; root-r=end; root-left=create(root-left,start,(start+end)/2); root-right=create(root-right,((start+end)/2)+1,end); return root; } } node * update(node * root,int i,int j) { if(root-l==root-r (root-l =iroot-r =j)) { root-num=1-(root-num); return root; } if(root-left) root-left=update(root-left,i,j); if(root-right) root-right=update(root-right,i,j); if(root-left root-right) root-num=root-left-num+root-right-num; return root; } int query(node * root,int i,int j) { if(root-l=i root-r=j) return root-num; int ans1,ans2; if(root-left) ans1=query(root-left,i,j); if(root-right) ans2=query(root-right,i,j); if(!root-left !root-right) return 0; return ans1+ans2; } this is my solution to http://www.spoj.pl/problems/LITE/ . But i am getting wrong answer. Can someone suggest a few test cases for which my solution might be failing ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/h6UQhCs1W_0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: POSTAGE STAMP PROBLEM
isnt it is similar to coin change problem , here we need minimum number of stamps to form a value. so we can check which number exceed the min stamp range i.e 1 to 3. On Jun 19, 11:55 am, sanjay pandey sanjaypandey...@gmail.com wrote: The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values. For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps. Is there an algorithm that given the maximum amount of stamps allowed and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope? -- 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]
Hmmm, true. That's what I expected in this solution. Similarly, we can get 3 by (3,3) (1,2) However, did you take a look at the other solution I proposed? I guess that solves the problem to some extent. On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh singhsourab...@gmail.comwrote: @Umer and Navin : 1 is generated by (1,3) only. 2 is generated by (1,1) and (2,3). so given solution is wrong On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ *ALL* please. post along with your method . proof than it make's equal distribution over the given range. On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.comwrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.com wrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Double Linked List Represented With Single Linked List
Explain how to implement doubly linked lists using only one pointer value*np[x *] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. 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: Directi question-centre of the tree
I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/* *msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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: Directi question-centre of the tree
As you traverse along and find the diameter of the tree, keep track of the number of nodes thereby traversed. Let that be equal to n. Now, centre is the node corresponding to floor((n+1)/2). On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: I am asking again .. can any one please suggest better method for getting the median on the longest path of the tree .. efficient method . On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/ **msg/algogeeks/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Hemesh singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BWplK7bCatMJ. 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Double Linked List Represented With Single Linked List
Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.comwrote: Explain how to implement doubly linked lists using only one pointer value*np[x *] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Reverse Queue
How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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] Reverse Queue
count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 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] Reverse Queue
@Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse Queue
For ex: let only two element are in queue: 1 2 (1 at front and rear is at 2). looping two times: first time: delete from front and adding to rear: queue will be: 2 1(front at 2 , rear at 1) second iteration: deleting 2 and adding to queue :result will be: 1 2 (front 1, rear 2) On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse Queue
I meant do it for n-1 times (my focus was on time complexity).Try with more examples and you will know :) On Wed, Jun 20, 2012 at 6:50 PM, Navin Kumar algorithm.i...@gmail.comwrote: For ex: let only two element are in queue: 1 2 (1 at front and rear is at 2). looping two times: first time: delete from front and adding to rear: queue will be: 2 1(front at 2 , rear at 1) second iteration: deleting 2 and adding to queue :result will be: 1 2 (front 1, rear 2) On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 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] Reverse Queue
can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- 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] Reverse Queue
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse Queue
You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ. 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. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. 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] Reverse Queue
@Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.comwrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/ **msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reverse Queue
Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 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] Reverse Queue
@saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the
Re: [algogeeks] Reverse Queue
How ?? I am asking to manipulate the same queue. Dequeue n-1 elements and enqueue them in order to you take out to the same queue..Where is extra space involved ? On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: @saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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
Re: [algogeeks] Reverse Queue
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will take O(1) time but you have to enqueue elements in reverse order.Not in the order you fetched. Think about it :). Then you have to take stack or some other data structure. On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote: How ?? I am asking to manipulate the same queue. Dequeue n-1 elements and enqueue them in order to you take out to the same queue..Where is extra space involved ? On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: @saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.com wrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.com wrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Reverse Queue
My bad...Sorry :(..Yes it certainly was not right On Wed, Jun 20, 2012 at 8:56 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Saurabh:i was wrong in deciding space complexity. Yes, your algo will take O(1) time but you have to enqueue elements in reverse order.Not in the order you fetched. Think about it :). Then you have to take stack or some other data structure. On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote: How ?? I am asking to manipulate the same queue. Dequeue n-1 elements and enqueue them in order to you take out to the same queue..Where is extra space involved ? On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: @saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.com wrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.com wrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/* *group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups
Re: [algogeeks] Reverse Queue
@Navin: as you say you have to take stack or some other data structure then it will definately not be donw in O(1) space complexity i think the recursive solution is best because we are not explicitly using any extra space its internal stack is using this space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oKM6PICuD6oJ. 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] Reverse Queue
@Rishabh: i know using stack or recursion it can be done easily with O(n) space. I want to know whether there exist more space efficient algo for this problem or not? On Wed, Jun 20, 2012 at 9:20 PM, Rishabh Agarwal rishabh...@gmail.comwrote: @Navin: as you say you have to take stack or some other data structure then it will definately not be donw in O(1) space complexity i think the recursive solution is best because we are not explicitly using any extra space its internal stack is using this space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oKM6PICuD6oJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Reverse Queue
Queues are basically linked lists with head and tail pointers. It is possible to reverse the list by change of pointers in O(n) time n O(1) space. PS: Not considering queue ADT with enqueue dequeue operations. On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/syRXPuMjBpkJ. 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: Reverse Queue
void Reverse(std::queueint pQ) { if(pQ.empty()) return; int item=pQ.front(); pQ.pop(); Reverse(pQ); pQ.push(item); } Regards On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.com wrote: Queues are basically linked lists with head and tail pointers. It is possible to reverse the list by change of pointers in O(n) time n O(1) space. PS: Not considering queue ADT with enqueue dequeue operations. On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/syRXPuMjBpkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse Queue
Just a query : If the queue is implemented as an array, then is it not possible to swap the elements from the last and first position onwards until you reach middle point. Wont this use O(1) space and O(n/2) time. On Wed, Jun 20, 2012 at 1:56 PM, Hassan Monfared hmonfa...@gmail.comwrote: void Reverse(std::queueint pQ) { if(pQ.empty()) return; int item=pQ.front(); pQ.pop(); Reverse(pQ); pQ.push(item); } Regards On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.comwrote: Queues are basically linked lists with head and tail pointers. It is possible to reverse the list by change of pointers in O(n) time n O(1) space. PS: Not considering queue ADT with enqueue dequeue operations. On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/syRXPuMjBpkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse Queue
using recursion, reverse(queue,front,rear) { if( front rear ) { swap( queue[front], queue[rear] ); reverse( queue, front+1, rear-1); } } On Wed, Jun 20, 2012 at 11:53 PM, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote: Just a query : If the queue is implemented as an array, then is it not possible to swap the elements from the last and first position onwards until you reach middle point. Wont this use O(1) space and O(n/2) time. On Wed, Jun 20, 2012 at 1:56 PM, Hassan Monfared hmonfa...@gmail.comwrote: void Reverse(std::queueint pQ) { if(pQ.empty()) return; int item=pQ.front(); pQ.pop(); Reverse(pQ); pQ.push(item); } Regards On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.comwrote: Queues are basically linked lists with head and tail pointers. It is possible to reverse the list by change of pointers in O(n) time n O(1) space. PS: Not considering queue ADT with enqueue dequeue operations. On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/syRXPuMjBpkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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 Interview Question
void make_group( int a[], int size) { int j = 0; for ( int i = 0; i size; i++ ) { if ( a[i] 0 ) { swap(a[i],a[j]); j++; } } } -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- 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: Reverse Queue
Abhishek Sharma : swap is not allowed because you can push at only one side of queue. it's not dequeue. On Wed, Jun 20, 2012 at 11:21 PM, Abhishek Sharma abhi120...@gmail.comwrote: using recursion, reverse(queue,front,rear) { if( front rear ) { swap( queue[front], queue[rear] ); reverse( queue, front+1, rear-1); } } On Wed, Jun 20, 2012 at 11:53 PM, Sreeprasad Govindankutty sreeprasad...@gmail.com wrote: Just a query : If the queue is implemented as an array, then is it not possible to swap the elements from the last and first position onwards until you reach middle point. Wont this use O(1) space and O(n/2) time. On Wed, Jun 20, 2012 at 1:56 PM, Hassan Monfared hmonfa...@gmail.comwrote: void Reverse(std::queueint pQ) { if(pQ.empty()) return; int item=pQ.front(); pQ.pop(); Reverse(pQ); pQ.push(item); } Regards On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.comwrote: Queues are basically linked lists with head and tail pointers. It is possible to reverse the list by change of pointers in O(n) time n O(1) space. PS: Not considering queue ADT with enqueue dequeue operations. On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/syRXPuMjBpkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
@atul if range is high den complexity wud be much larger... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] SPOJ problem : CANDY
i am using long long but still getting WA. here's my code #includestdio.h #includeconio.h int main() { long long cand,sum; int T,N,i,j,temp[10]; scanf(%d,T); sum = 0; for(i=0;iT;i++) { scanf(%d,N); for(j=0;jN;j++) { scanf(%lld,cand); sum = (sum+cand)%N; } if(sum == 0) temp[i]=1; else temp[i]=0; } for(i=0;iT;i++) { if(temp[i]==1) printf(YES\n); else printf(NO\n); } return 0; } plz help me.. what's wrong in my code -- 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] SPOJ problem : CANDY
long long not require in this que . try it again.. -- 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] SPOJ problem : CANDY
still getting the WA . is there any test case i am getting wrong? -- 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] SPOJ problem : CANDY
here is my code u can check that.. http://ideone.com/Gii1d -- 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: Microsoft question
Hi, It looks like, The interviewer is expecting MinHeap from you, If modification to array is permitted just build the heap in place (from end bubbleUp n-1 time) and extract K elements in sorted order Otherwise you need minimum O(K) memory Again if you want to use the quick-sort, I would prefer only using partition part of quick sort.. 1. Select any pivot 'P' 2. Partition the array.. 3. position of the pivot p 4. if p k ( kth min lies on left part) repeat again for k 5 if p k ( kth min lies on right part) repeat again for k-p 6 if p = k ( You are lucky) exit Again in worst case it is o(N2) -Ajeet Thanks -A On Wednesday, 20 June 2012 00:56:36 UTC+5:30, adarsh kumar wrote: This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote: @enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.comwrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FABBRabzVqMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/sBvT2ztJpoUJ. 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] Reverse Queue
i doesn't seem possible without using stack... On Wed, Jun 20, 2012 at 10:13 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Rishabh: i know using stack or recursion it can be done easily with O(n) space. I want to know whether there exist more space efficient algo for this problem or not? On Wed, Jun 20, 2012 at 9:20 PM, Rishabh Agarwal rishabh...@gmail.comwrote: @Navin: as you say you have to take stack or some other data structure then it will definately not be donw in O(1) space complexity i think the recursive solution is best because we are not explicitly using any extra space its internal stack is using this space. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oKM6PICuD6oJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Amritpal singh -- 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] Double Linked List Represented With Single Linked List
*np *is nothing but *next_pointer. np[x] *does mean *x-np *which is the next pointer to node. Actually I am thinking in this way about *np, *that it stores the *XOR* value of *next* and *prev* pointers.Or Since *np *is a k-bit integer, the first k/2 bits wil be used for *next*, and other k/2 bits wil be used for *prev *pointer. On Wednesday, 20 June 2012 18:28:07 UTC+5:30, adarsh kumar wrote: Simple! Just traverse the doubly linked list and keep track of next and previous of each node, and do XOR and save the result in a new pointer, what according to you is np. Be careful about boundary cases, i.e head and tail, though. On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore kknarenkris...@gmail.com wrote: Explain how to implement doubly linked lists using only one pointer value * np[x*] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],*the k-bit “exclusive-or” of next[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implement the SEARCH, INSERT, and DELETE operations on such a list. Also show how to reverse such a list in O(1) time. This is the Question in the Book *Introduction To Algorithms *By CORMEN ( MIT Press ) Page Number : 209 , Problem No: 10.2-8. Thanks in Advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Uj1E8KXljAQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JlNBCRsj9kUJ. 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] Reverse Queue
@saurabh : your solution require O(n) space. On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote: How ?? I am asking to manipulate the same queue. Dequeue n-1 elements and enqueue them in order to you take out to the same queue..Where is extra space involved ? On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: @saurabh : i want solution with space complexity of O(1) . your solution is right but it takes O(n) space. On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote: Why will my proposed solution not work for you ??? On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Kirubakaran : still space complexity is O(n) due to stack.Can it be solved in space complexity O(1). On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.com wrote: You could use recursion. def reverse_Q q if !q.isEmpty? el = q.dequeue nQ = reverse_Q(q) nQ.enqueue el return nQ end return q end On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote: Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue etc On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.com wrote: can we create other methods or we have to use only enqueue and dequeue...? if yes then simply for(i=0;i=n/2;i++) swap(i,n-i); On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.com wrote: @Saurabh: queue will be remain unchanged according to your algorithm. Because if you will delete an element from front and add at rear no change will be there. After n iteration front will be pointing to same element and rear will also point to same element. Correct me if i am wrong. :) On Wed, Jun 20, 2012 at 6:39 PM, saurabh singh saurabh.n...@gmail.com wrote: count the size of queue : O(n) loop for n and do remove and add in queue : O(n) Total : O(n) On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.com wrote: How to reverse a Queue . Constraints: Time complexity O(n). space complexity: O(1) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/kepls-8qRwgJhttps://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- Thanks Regards Amritpal singh -- 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+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/qmLUaTNJns8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message
Re: [algogeeks] SPOJ problem : CANDY
@mayank: For each testcase sum is not zero make sum=0 inside the for loop -- 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] SPOJ problem : CANDY
oh i am really sorry the problem is CANDY III can you help me regarding that once again sorry -- 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.