Re: [algogeeks] Re: Ever growing sorted linked list
i want to ask one thing...the way some are saying first check with 2 then 4 and then 16to reach at that place we are suppose to traverse it and also hav eto put a condition say like countn or something...in this case also we are comparing so whats the usecorrect me if im wrong. On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com wrote: can be done in O(n) find tow nodes from starting position find two nodes p,q such that p k k q as linked list is sorted we have to keep going on in right direction complexity will no less then O(N) as its linked list there is no notion of binary search sorted linked list think out why ? only think we can apply some logic to reduce the comparisons that's i also think will be gr8 improvement but approach sounds good if start comparing the nodes value using multiple of 2 fact .e.g. take an integer i=2^j from j=0 to start comparing 2^0th node, 2^1th node, 2^2th node2^jth node might be we are able to reduce the number of comparisons do notify me via gmail if i am wrong if u find difficulty in TC ? else happy learning if this would have been sorted array then we could have been solved it O(logn) suing same approach. Thanks Shashank Mani Computer Science Birla Institute of Technology, Mesra -- 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: Ever growing sorted linked list
One a not so standard way of doing that is while creating the link list, keep an extra pointer in the node to point to the jump location. Just hold the previous node in a temp say address of 2 node and when i/p reaches 4, point the jumper pointer to 4 and make 4 the next jumper pointer. On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: @Popli : Bingo , that is what i was thinking and mentioned in my previous post.. On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli abeygau...@gmail.comwrote: i want to ask one thing...the way some are saying first check with 2 then 4 and then 16to reach at that place we are suppose to traverse it and also hav eto put a condition say like countn or something...in this case also we are comparing so whats the usecorrect me if im wrong. On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com wrote: can be done in O(n) find tow nodes from starting position find two nodes p,q such that p k k q as linked list is sorted we have to keep going on in right direction complexity will no less then O(N) as its linked list there is no notion of binary search sorted linked list think out why ? only think we can apply some logic to reduce the comparisons that's i also think will be gr8 improvement but approach sounds good if start comparing the nodes value using multiple of 2 fact .e.g. take an integer i=2^j from j=0 to start comparing 2^0th node, 2^1th node, 2^2th node2^jth node might be we are able to reduce the number of comparisons do notify me via gmail if i am wrong if u find difficulty in TC ? else happy learning if this would have been sorted array then we could have been solved it O(logn) suing same approach. Thanks Shashank Mani Computer Science Birla Institute of Technology, Mesra -- 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. -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- 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: Ever growing sorted linked list
I think the novelty of this is that we are avoiding the comparison of new element with all the members of data in LL On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: @Popli : Bingo , that is what i was thinking and mentioned in my previous post.. On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli abeygau...@gmail.comwrote: i want to ask one thing...the way some are saying first check with 2 then 4 and then 16to reach at that place we are suppose to traverse it and also hav eto put a condition say like countn or something...in this case also we are comparing so whats the usecorrect me if im wrong. On Wed, Jul 20, 2011 at 6:58 PM, bittu shashank7andr...@gmail.com wrote: can be done in O(n) find tow nodes from starting position find two nodes p,q such that p k k q as linked list is sorted we have to keep going on in right direction complexity will no less then O(N) as its linked list there is no notion of binary search sorted linked list think out why ? only think we can apply some logic to reduce the comparisons that's i also think will be gr8 improvement but approach sounds good if start comparing the nodes value using multiple of 2 fact .e.g. take an integer i=2^j from j=0 to start comparing 2^0th node, 2^1th node, 2^2th node2^jth node might be we are able to reduce the number of comparisons do notify me via gmail if i am wrong if u find difficulty in TC ? else happy learning if this would have been sorted array then we could have been solved it O(logn) suing same approach. Thanks Shashank Mani Computer Science Birla Institute of Technology, Mesra -- 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. -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- 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] Re: Ever growing sorted linked list
hey check my algo...i mentioned all the possible cases :) On Tue, Jul 19, 2011 at 11:31 AM, oppilas . jatka.oppimi...@gmail.comwrote: Yes we can avoid integer comparison. But for jumping we will need to check whether the next node is null or not. So, depending upon the jump size, the number of comparison in worst case can be very large if our jump size is increasing exponentially. So, why not just compare with the next node instead of jumping. On Tue, Jul 19, 2011 at 10:47 AM, sunny agrawal sunny816.i...@gmail.comwrote: yes Alok u r right that in any case we will traverse k times if k is the position if the element that need to searched but by jumping we can save the time of avoiding unnecessary comparisions On Tue, Jul 19, 2011 at 10:44 AM, Alok Prakash alok251...@gmail.comwrote: If i am not wrong, in a linked list to move to any number of position, say n, we have to traverse all intermediate nodes of the linked list. So, it does not matter if we are moving pointer by 2,4,8,... positions, we have to scan all intermediate nodes. Is it not a simple searching On Tue, Jul 19, 2011 at 9:17 AM, sumit sumitispar...@gmail.com wrote: Here is the idea I was thinking of: - start from the root: if(root-data k) move to position 2 in the list. - in this way every time move the pointer to the position double the current position and compare th eelement of node with k( moving here is form 1 - 2 , 2-4, 4-8 ,8-16 ..) - suppose you found a certain node at position n whose node-data k , then now u only have to search for k between index n/2 to n (i.e. if you found 16th element k then search for k between 8th and 16ht element).. correct me if any flaws. On Jul 19, 3:38 am, Dumanshu duman...@gmail.com wrote: @Gaurav: Ever Increasing means that you don't know the length of the list. So you have to assume some index n, traverse the list upto that point and check the results. If not found increment the n to some higher value. We are basically trying to improve the complexity by taking higher and higher jumps for n. On Jul 19, 2:03 am, Gaurav Popli abeygau...@gmail.com wrote: yeah...im saying to reach position n at which k is placed we have to trverse n positions from head or not...?? and i didnt understand the use of ever increasing...please elaborate on it.. On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu duman...@gmail.com wrote: @Swathi: plz give the TC of ur algo (exponential plus log) On Jul 18, 10:14 pm, Swathi chukka.swa...@gmail.com wrote: The solution to this problem will be a combination of exponential increase and the binary search.. start = 0; end = 0; index =0; middle = 0; while (1) { if(a[start] == data) return start; if(a[end] == data) return end; if(data end) { start = end; end = pow(start,2); // here we are consider exponential for faster search. // no need to check any boundary conditions as the array is infinite continue; } else { // do binary search between start index and end index because data is inbetween a[start] and a[end] } } Hope this helps... On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: i dont understand it..if k is at position an let supposeso to check at that position dont you have to traverse till that position ...is thr anything else than the head of list...??or i understood wrongly...?? On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek sagarpar...@gmail.com wrote: Update on 2nd line 2.if( ptr2=ptr1-next-next...(5 or 10 times) ) goto 3. else make linear search till NULL encounter and exit with the solution On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek sagarpar...@gmail.com wrote: i have one approach :- first compare root-data and k if k is very much greater than root-data then set next=5or10 ur choice else set next 2or3 ur choice take two pointers ptr1 and ptr2 now lets take k is much greater than root-data then 1. set ptr1=root //initially 2. if( ptr2=ptr1-next-next...(5 or 10 times) ) else make linear search till NULL encounter 3. if ptr2-data==k return its position 4. else if (ptr2-datak) set ptr1=ptr2 goto 2 5. else traverse the ptr1 upto ptr2, if found return its position else return fail if anyone has more efficient solution then pls tell :) On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu duman...@gmail.com wrote: You have a sorted linked list of integers of some length you don't know and it keeps on increasing. You are given a number k. Print the position of the number k. Basically, you have to search for number k in the ever growing sorted list
Re: [algogeeks] Re: Ever growing sorted linked list
yeah...im saying to reach position n at which k is placed we have to trverse n positions from head or not...?? and i didnt understand the use of ever increasing...please elaborate on it.. On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu duman...@gmail.com wrote: @Swathi: plz give the TC of ur algo (exponential plus log) On Jul 18, 10:14 pm, Swathi chukka.swa...@gmail.com wrote: The solution to this problem will be a combination of exponential increase and the binary search.. start = 0; end = 0; index =0; middle = 0; while (1) { if(a[start] == data) return start; if(a[end] == data) return end; if(data end) { start = end; end = pow(start,2); // here we are consider exponential for faster search. // no need to check any boundary conditions as the array is infinite continue; } else { // do binary search between start index and end index because data is inbetween a[start] and a[end] } } Hope this helps... On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: i dont understand it..if k is at position an let supposeso to check at that position dont you have to traverse till that position ...is thr anything else than the head of list...??or i understood wrongly...?? On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek sagarpar...@gmail.com wrote: Update on 2nd line 2. if( ptr2=ptr1-next-next...(5 or 10 times) ) goto 3. else make linear search till NULL encounter and exit with the solution On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek sagarpar...@gmail.com wrote: i have one approach :- first compare root-data and k if k is very much greater than root-data then set next=5or10 ur choice else set next 2or3 ur choice take two pointers ptr1 and ptr2 now lets take k is much greater than root-data then 1. set ptr1=root //initially 2. if( ptr2=ptr1-next-next...(5 or 10 times) ) else make linear search till NULL encounter 3. if ptr2-data==k return its position 4. else if (ptr2-datak) set ptr1=ptr2 goto 2 5. else traverse the ptr1 upto ptr2, if found return its position else return fail if anyone has more efficient solution then pls tell :) On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu duman...@gmail.com wrote: You have a sorted linked list of integers of some length you don't know and it keeps on increasing. You are given a number k. Print the position of the number k. Basically, you have to search for number k in the ever growing sorted list and print its position. Please write the complexity of whatever solution you propose. -- 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. -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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: Ever growing sorted linked list
If i am not wrong, in a linked list to move to any number of position, say n, we have to traverse all intermediate nodes of the linked list. So, it does not matter if we are moving pointer by 2,4,8,... positions, we have to scan all intermediate nodes. Is it not a simple searching On Tue, Jul 19, 2011 at 9:17 AM, sumit sumitispar...@gmail.com wrote: Here is the idea I was thinking of: - start from the root: if(root-data k) move to position 2 in the list. - in this way every time move the pointer to the position double the current position and compare th eelement of node with k( moving here is form 1 - 2 , 2-4, 4-8 ,8-16 ..) - suppose you found a certain node at position n whose node-data k , then now u only have to search for k between index n/2 to n (i.e. if you found 16th element k then search for k between 8th and 16ht element).. correct me if any flaws. On Jul 19, 3:38 am, Dumanshu duman...@gmail.com wrote: @Gaurav: Ever Increasing means that you don't know the length of the list. So you have to assume some index n, traverse the list upto that point and check the results. If not found increment the n to some higher value. We are basically trying to improve the complexity by taking higher and higher jumps for n. On Jul 19, 2:03 am, Gaurav Popli abeygau...@gmail.com wrote: yeah...im saying to reach position n at which k is placed we have to trverse n positions from head or not...?? and i didnt understand the use of ever increasing...please elaborate on it.. On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu duman...@gmail.com wrote: @Swathi: plz give the TC of ur algo (exponential plus log) On Jul 18, 10:14 pm, Swathi chukka.swa...@gmail.com wrote: The solution to this problem will be a combination of exponential increase and the binary search.. start = 0; end = 0; index =0; middle = 0; while (1) { if(a[start] == data) return start; if(a[end] == data) return end; if(data end) { start = end; end = pow(start,2); // here we are consider exponential for faster search. // no need to check any boundary conditions as the array is infinite continue; } else { // do binary search between start index and end index because data is inbetween a[start] and a[end] } } Hope this helps... On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: i dont understand it..if k is at position an let supposeso to check at that position dont you have to traverse till that position ...is thr anything else than the head of list...??or i understood wrongly...?? On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek sagarpar...@gmail.com wrote: Update on 2nd line 2.if( ptr2=ptr1-next-next...(5 or 10 times) ) goto 3. else make linear search till NULL encounter and exit with the solution On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek sagarpar...@gmail.com wrote: i have one approach :- first compare root-data and k if k is very much greater than root-data then set next=5or10 ur choice else set next 2or3 ur choice take two pointers ptr1 and ptr2 now lets take k is much greater than root-data then 1. set ptr1=root //initially 2. if( ptr2=ptr1-next-next...(5 or 10 times) ) else make linear search till NULL encounter 3. if ptr2-data==k return its position 4. else if (ptr2-datak) set ptr1=ptr2 goto 2 5. else traverse the ptr1 upto ptr2, if found return its position else return fail if anyone has more efficient solution then pls tell :) On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu duman...@gmail.com wrote: You have a sorted linked list of integers of some length you don't know and it keeps on increasing. You are given a number k. Print the position of the number k. Basically, you have to search for number k in the ever growing sorted list and print its position. Please write the complexity of whatever solution you propose. -- 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. -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to
Re: [algogeeks] Re: Ever growing sorted linked list
yes Alok u r right that in any case we will traverse k times if k is the position if the element that need to searched but by jumping we can save the time of avoiding unnecessary comparisions On Tue, Jul 19, 2011 at 10:44 AM, Alok Prakash alok251...@gmail.com wrote: If i am not wrong, in a linked list to move to any number of position, say n, we have to traverse all intermediate nodes of the linked list. So, it does not matter if we are moving pointer by 2,4,8,... positions, we have to scan all intermediate nodes. Is it not a simple searching On Tue, Jul 19, 2011 at 9:17 AM, sumit sumitispar...@gmail.com wrote: Here is the idea I was thinking of: - start from the root: if(root-data k) move to position 2 in the list. - in this way every time move the pointer to the position double the current position and compare th eelement of node with k( moving here is form 1 - 2 , 2-4, 4-8 ,8-16 ..) - suppose you found a certain node at position n whose node-data k , then now u only have to search for k between index n/2 to n (i.e. if you found 16th element k then search for k between 8th and 16ht element).. correct me if any flaws. On Jul 19, 3:38 am, Dumanshu duman...@gmail.com wrote: @Gaurav: Ever Increasing means that you don't know the length of the list. So you have to assume some index n, traverse the list upto that point and check the results. If not found increment the n to some higher value. We are basically trying to improve the complexity by taking higher and higher jumps for n. On Jul 19, 2:03 am, Gaurav Popli abeygau...@gmail.com wrote: yeah...im saying to reach position n at which k is placed we have to trverse n positions from head or not...?? and i didnt understand the use of ever increasing...please elaborate on it.. On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu duman...@gmail.com wrote: @Swathi: plz give the TC of ur algo (exponential plus log) On Jul 18, 10:14 pm, Swathi chukka.swa...@gmail.com wrote: The solution to this problem will be a combination of exponential increase and the binary search.. start = 0; end = 0; index =0; middle = 0; while (1) { if(a[start] == data) return start; if(a[end] == data) return end; if(data end) { start = end; end = pow(start,2); // here we are consider exponential for faster search. // no need to check any boundary conditions as the array is infinite continue; } else { // do binary search between start index and end index because data is inbetween a[start] and a[end] } } Hope this helps... On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote: i dont understand it..if k is at position an let supposeso to check at that position dont you have to traverse till that position ...is thr anything else than the head of list...??or i understood wrongly...?? On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek sagarpar...@gmail.com wrote: Update on 2nd line 2.if( ptr2=ptr1-next-next...(5 or 10 times) ) goto 3. else make linear search till NULL encounter and exit with the solution On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek sagarpar...@gmail.com wrote: i have one approach :- first compare root-data and k if k is very much greater than root-data then set next=5or10 ur choice else set next 2or3 ur choice take two pointers ptr1 and ptr2 now lets take k is much greater than root-data then 1. set ptr1=root //initially 2. if( ptr2=ptr1-next-next...(5 or 10 times) ) else make linear search till NULL encounter 3. if ptr2-data==k return its position 4. else if (ptr2-datak) set ptr1=ptr2 goto 2 5. else traverse the ptr1 upto ptr2, if found return its position else return fail if anyone has more efficient solution then pls tell :) On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu duman...@gmail.com wrote: You have a sorted linked list of integers of some length you don't know and it keeps on increasing. You are given a number k. Print the position of the number k. Basically, you have to search for number k in the ever growing sorted list and print its position. Please write the complexity of whatever solution you propose. -- 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. -- Regards SAGAR PAREEK COMPUTER SCIENCE