Re: [algogeeks] Appropriate data structure

[praveen raj]

steps:

1) make max heapify and min heapify for first k days
2)for the next day... remove first element from  max heapify and min
heapify  then add new element to existing  max heapify and min
heapify  .
3) Then return max and min in O(1)from max heapify and min heapify .

PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING

-- 
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] Appropriate data structure

[adarsh kumar]

For using a stack in order to achieve O(n) time, we can modify push and pop
as follows(assuming we want max):
While pushing, compare the top of the stack with the element to be
pushed(say x). If x>top, just push normally. Else, pop elements until
top>x. Keep an eye on the border cases as well. Thus top will always be
containing the maximum, which can be retrieved obviously in O(1) time.
Similar algo  for pop can be formulated.
regards.

On Tue, Jul 17, 2012 at 9:19 AM, Tushar  wrote:

> can you please elaborate on usage of stack to do it in 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/-/8jTvBVdzsmYJ.
>
> 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] Appropriate data structure

[Tushar]

can you please elaborate on usage of stack to do it in 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/-/8jTvBVdzsmYJ.
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] Appropriate data structure

[vaibhav shukla]

Stack will do it...
and min or max can be even retrieved in O(1) ...

On Sun, Jul 15, 2012 at 6:36 PM, adarsh kumar  wrote:

> Oh ya sorry. I thought we have to retrieve kth min and max, in which case
> heap can be used.
>
> Here, we can either use stack or map. Map can be from a date(which
> increases by 1 daily) to a value, as only one value is received per day.
> Keeping in mind memory constraints, stack is better. Map is an otherwise
> safe solution.
> regards.
>
> On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar wrote:
>
>> I think stack would solve the purpose. please comment.
>>
>>
>> On Sun, Jul 15, 2012 at 5:42 PM, enchantress wrote:
>>
>>> It says K days if you keep heap the order of values gets disturbed. How
>>> are last k values accessed then?
>>>
>>>
>>> On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:

 Min or max heap accordingly. This will do the job in O(log n) time.

 On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar 
 wrote:

> A set of integer values are being received (1 per day). Store these
> values and at any given time, retrieve the min and max value over the last
> k days. What data structures would you use for storing and retrieving ?
>
> --
> 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/-/2AhV1Xn3jD8J
> .
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
> 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/-/peWhqjKLIH8J.
>>>
>>> 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.
>



-- 
best wishes!!
 Vaibhav

-- 
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] Appropriate data structure

[SHOBHIT GUPTA]

agree with naveen

On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar wrote:

> I think stack would solve the purpose. please comment.
>
> On Sun, Jul 15, 2012 at 5:42 PM, enchantress wrote:
>
>> It says K days if you keep heap the order of values gets disturbed. How
>> are last k values accessed then?
>>
>>
>> On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>>>
>>> Min or max heap accordingly. This will do the job in O(log n) time.
>>>
>>> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar 
>>> wrote:
>>>
 A set of integer values are being received (1 per day). Store these
 values and at any given time, retrieve the min and max value over the last
 k days. What data structures would you use for storing and retrieving ?

 --
 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/-/2AhV1Xn3jD8J
 .
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 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/-/peWhqjKLIH8J.
>>
>> 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] Appropriate data structure

[rspr]

I think by using min/max heap we can fetch the kth largest/smallest data 
from the heap. But here there is one more point how to ensure that the data 
is smallest in last kth day. Here you can use interval/segment(augmented 
version of heap tree) tree, where u can store the interval/segment on the 
basis of date and retrieve the same information.

On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>
> Min or max heap accordingly. This will do the job in O(log n) time.
>
> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar wrote:
>
>> A set of integer values are being received (1 per day). Store these 
>> values and at any given time, retrieve the min and max value over the last 
>> k days. What data structures would you use for storing and retrieving ? 
>>
>> -- 
>> 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/-/2AhV1Xn3jD8J.
>> 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/-/ypiCXt9_1BQJ.
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] Appropriate data structure

[adarsh kumar]

Oh ya sorry. I thought we have to retrieve kth min and max, in which case
heap can be used.

Here, we can either use stack or map. Map can be from a date(which
increases by 1 daily) to a value, as only one value is received per day.
Keeping in mind memory constraints, stack is better. Map is an otherwise
safe solution.
regards.

On Sun, Jul 15, 2012 at 6:24 PM, Navin Kumar wrote:

> I think stack would solve the purpose. please comment.
>
>
> On Sun, Jul 15, 2012 at 5:42 PM, enchantress wrote:
>
>> It says K days if you keep heap the order of values gets disturbed. How
>> are last k values accessed then?
>>
>>
>> On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>>>
>>> Min or max heap accordingly. This will do the job in O(log n) time.
>>>
>>> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar 
>>> wrote:
>>>
 A set of integer values are being received (1 per day). Store these
 values and at any given time, retrieve the min and max value over the last
 k days. What data structures would you use for storing and retrieving ?

 --
 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/-/2AhV1Xn3jD8J
 .
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 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/-/peWhqjKLIH8J.
>>
>> 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] Appropriate data structure

[Navin Kumar]

I think stack would solve the purpose. please comment.

On Sun, Jul 15, 2012 at 5:42 PM, enchantress  wrote:

> It says K days if you keep heap the order of values gets disturbed. How
> are last k values accessed then?
>
>
> On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>>
>> Min or max heap accordingly. This will do the job in O(log n) time.
>>
>> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar wrote:
>>
>>> A set of integer values are being received (1 per day). Store these
>>> values and at any given time, retrieve the min and max value over the last
>>> k days. What data structures would you use for storing and retrieving ?
>>>
>>> --
>>> 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/-/2AhV1Xn3jD8J
>>> .
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>> 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/-/peWhqjKLIH8J.
>
> 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] Appropriate data structure

[enchantress]

It says K days if you keep heap the order of values gets disturbed. How are 
last k values accessed then?

On Sunday, 15 July 2012 12:46:02 UTC+5:30, adarsh kumar wrote:
>
> Min or max heap accordingly. This will do the job in O(log n) time.
>
> On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar wrote:
>
>> A set of integer values are being received (1 per day). Store these 
>> values and at any given time, retrieve the min and max value over the last 
>> k days. What data structures would you use for storing and retrieving ? 
>>
>> -- 
>> 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/-/2AhV1Xn3jD8J.
>> 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/-/peWhqjKLIH8J.
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] Appropriate data structure

[adarsh kumar]

Min or max heap accordingly. This will do the job in O(log n) time.

On Sun, Jul 15, 2012 at 1:25 AM, Navin Kumar wrote:

> A set of integer values are being received (1 per day). Store these values
> and at any given time, retrieve the min and max value over the last k days.
> What data structures would you use for storing and retrieving ?
>
> --
> 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/-/2AhV1Xn3jD8J.
> 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] Appropriate data structure

[Navin Kumar]

A set of integer values are being received (1 per day). Store these values 
and at any given time, retrieve the min and max value over the last k days. 
What data structures would you use for storing and retrieving ?

-- 
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/-/2AhV1Xn3jD8J.
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.