[algogeeks] Re: absolute minimum difference
In O(n^2 ) we can do. But in O(n) i don't get any idea. If any one got the idea just explain. On Friday, 27 July 2012 15:35:24 UTC+5:30, Navin Kumar wrote: Given array of integers (0 or +ve or -ve value) find two elements having minimum difference in their absolute values. e.g. Input {10 , -2, 4, 9,-20,17,-8,14,12) output {9,-8} I have solved it in O(nlogn). can it be solved in O(n). -- 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/-/viXnfcSJGZgJ. 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] Fixing Up The Binary Search Tree
Suppose a Binary Search Tree which is unbalanced.is given. Write a routine to balance the Binary Search Tree. Send the Root of the BST as an argument to that routine. It has to Return the Root of the Balanced BST. 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/-/iYdbt5mI4BQJ. 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] 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.
[algogeeks] LEFT MOST set bit in an unsigned integer.
How to find the LEFT MOST set bit in an unsigned integer. Example: 00*1*0 0001 0100 0010 is a 16-bit unsigned integer. We have to find the left most set bit position (Starting with 0 from right side ) which is 13th position in our example. How to find this. Can any one pls give any suggestions. Thank You Very Much 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/-/HJnuFujMZ3wJ. 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] Microsoft Interview Question
Given a array of integers both positive and negative and you need to shift positive numbers to one side and negative numbers to other side with the order intact. ex. {-1,5,3,-8,4,-6,9} to {-1,-8,-6,5,3,4,9}. This should be done in O(n). -- 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/-/PebCCcpUXpIJ. 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: Longest Path in A Graph
Thank You very much friends. I ve read algorithm Topological Sorting. First we have to perform the topological sorting ( in Linear Time ) on the graph. Then we can find which is the Longest Path in that ordering. But it works for only DAG ( Directed Acyclic Graphs ). I ve done it. But after performing the topological ordering it is a little bit confusing for me. Could you please get me the better idea that performs in less time complexity. Thank You. -- 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.