Design the most efficient algorithm to find the first k smallest elements
in an array ?
--
Thanks Regards,
Priyanka Chatterjee
Third Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received
When the fast pointer points to head again, the slow pointer would point to
the middle of the linked list.
On Sat, Mar 27, 2010 at 11:51 PM, vikrant singh vikrantsing...@gmail.comwrote:
Well gaurav, i think by this method you can only check for a cycle in the
list.
If u have any idea how can
@black diamond
i think u may b wrong.
check out this 1-2-3-4-5-6-7-8-9-3-. . . . . .
On Sat, Mar 27, 2010 at 11:04 AM, blackDiamond patidarc...@gmail.comwrote:
take Two pointers increase one by 1 and other by two node if they match
somewhere Firstone will become the middle..
On Sat, Mar 27,
@mukunda , looks like a v nice solution , but can u xplain the step 2 :line2
a bit more clearly? what do u mean by highest length pointer ?
Please give an example to your solution.
On Sun, Mar 28, 2010 at 9:23 AM, mukunda n s mukundn...@gmail.com wrote:
Simplification of the problem would be
vikrant you havent read properly the post by Gaurav when the second pointer
will come back to the head first will be pointing the middle.(Think it)!!
On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote:
Well gaurav, i think by this method you can only check for a cycle
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee
dona.1...@gmail.comwrote:
Design the most efficient algorithm to find the first k smallest elements
in an array ?
--
Thanks
sorry, i forgot to see *singly* linked list.
what about doing a topological sort and returning the middle element.
-Rohit
On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
@sanjana: but what in case of 1-2-3-1-4-5-6
-Rohit
On Sat, Mar 27, 2010 at 11:19
There are about 5-6 solutions mentioned at
http://geeksforgeeks.org/forum/topic/kth-largest-element
anyone having a different and more efficient algorithm please come up.
On Sun, Mar 28, 2010 at 11:44 AM, sharad kumar aryansmit3...@gmail.comwrote:
i feel heapify the array to get a min heap and
On 28 March 2010 11:44, sharad kumar aryansmit3...@gmail.com wrote:
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
This algorithm works in O(n+k logn) time. It is good .
Can this be done using randomized selection algorithm in linear
hi, refer cormen book *Medians and Order Statistics* chapter .
On Sat, Mar 27, 2010 at 11:14 PM, sharad kumar aryansmit3...@gmail.comwrote:
i feel heapify the array to get a min heap and keep extracting root k
times.any further optimisations???
On Sun, Mar 28, 2010 at 11:33 AM, Priyanka
select algorithm in order statistics given in cormen book. get kth smallest
element in O(n) and output all array elements from index 0 to the index of
that kth smallest element. So better than Heap approach which is O(n+klogn)
Thanks regards,
Laxmikant Agrawal
Journey is more important than
this is impossible case.. how can node1 point to node2 as well as node4?...
On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
@sanjana: but what in case of 1-2-3-1-4-5-6
-Rohit
On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote:
For
@diamond
sorry but how do we know the fast pointer is pointing to head again?
u see, in case u dont have O(n) space to record visited nodes
On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote:
vikrant you havent read properly the post by Gaurav when the second pointer
How can we convert a BST into a sorted doubly linked list?
i have the solution that i traverse BST in inorder traversal and
storing elements in doubly linked list.
anyone has any best solution.
--
Piyush Kumar Verma
NIT Allahabad
--
You received this message because you are subscribed to
@Rohit we have a cycle here
using hare/tortoise find a node in the cycle
find the length of the cycle.
find the 'end' of the list, call it E
Now equivalent to a singly linked list with the modified termination
condition (you need to skip E when you hit it for the first time though)
OR
find the
in starting we keep track of head pointer..
we are having three pointers
head,slower,faster,
know we start traversing the list
if(faster==head||faster-next==head)
return slower
else
faster=faster-next-next
slower=slower-next
On Sun, Mar 28, 2010 at 12:15 PM, vikrant singh
@Rohit we have a cycle here
On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
that is topologcall sort
On 3/28/10, saurabh gupta sgup...@gmail.com wrote:
@Rohit we have a cycle here
using hare/tortoise find a node in the cycle
find the length of the cycle.
sry... i got confused
-Rohit
On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote:
@Rohit we have a cycle here
On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
that is topologcall sort
On 3/28/10, saurabh gupta sgup...@gmail.com wrote:
anyways.. the solution becomes still more trivial...
as there can be only one cycle remove it easily and that helps to find
the centre.
-Rohit
On Sun, Mar 28, 2010 at 4:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
sry... i got confused
-Rohit
On Sun, Mar 28, 2010 at 3:14
This is the best description.
http://cslibrary.stanford.edu/109/TreeListRecursion.html
Thanks
Pramod Negi
On Sun, Mar 28, 2010 at 1:39 PM, Piyush Verma 114piy...@gmail.com wrote:
How can we convert a BST into a sorted doubly linked list?
i have the solution that i traverse BST in
Create a temp array temp[0..k-1] of size k.
2) Traverse the array arr[k..n-1]. While traversing, keep updating the
smallest element of temp[]
3) Return the smallest of temp[]
Time Complexity: O((n-k)*k).
try it ..for this problem[?]
--
You received this message because you are
if(faster==head||faster-next=
=head)
return slower
else
faster=faster-next-next
slower=slower-next
HERE we hv three poniter faster,headr,slower.
as u hv mentioned that linked list has cycle list so better is that we hv
to use for loop
as :-
if we take headr,link,temp;
if(temp==headr)
{
how to convert a BST into a sorted doubly linked list.
is there any solution of this question.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group,
Here it is a nice solution:
http://cslibrary.stanford.edu/109/TreeListRecursion.html
On Sun, Mar 28, 2010 at 11:09 AM, Piyush Verma 114piy...@gmail.com wrote:
How can we convert a BST into a sorted doubly linked list?
i have the solution that i traverse BST in inorder traversal and
you have to find the kth element of your list. which will take O(n)
and remaining element you can get in the other traversal
eg: 3,5,4,35,599,34
you have to find the 3 min element from the lsit
so finding 3rd element we will get 5
on next thing is traverse the list and take all the element less
1) Construct max heap by taking first k elements in an array
2) if k+1 element less than root of max heap
a) Delete root of max heap
b) Insert k+1 element in max heap and apply heapify method
3) else skip the element
4) apply above procedure for all n elements in an array
At last
insert the elements in the list, the elements of the tree visited by inorder
traversal
On Sun, Mar 28, 2010 at 11:13 AM, Piyush Verma 114piy...@gmail.com wrote:
how to convert a BST into a sorted doubly linked list.
is there any solution of this question.
--
You received this message
27 matches
Mail list logo
