CareerCup

Same as /questions/7134129/stack-with-find-min-find-max-more-efficient-than-on, just worded differently.

Maintain 2 doubly-linked lists, adding new entries at the tail. The head will always be the answer (i.e., the max temp is the head of the max list, the min temp is the head of the min list).
For the max temp list: whenever new entries are added, the head is checked for being older than 24 hours (expired), and that entry is removed. for the new entry: if it is <= the current tail, just append. while > than the current tail, remove the tail.

The min temp list is similar.

I will do the following:
-Take three variables namely current_temprature,max_temperature and min_temperature
-After 5 second interval we update the current_temperature with the current temperature....
-If current temperature > max_temperature
then
update max_temperature with current temperature
else If current temperature < min_temperature
then
update min_temperature with current temperature

Do this for every 5 second interval for 24 hours

If space efficiency is important:

Maintain a "seconds" circular queue that adds a node every 5 sec for a new request and recycles the head node if the head node is past 1 minute. Maintain max and min temp for the minute and update it whenever a new node is added.

Maintain another "minutes" circular queue that will be added with new node (for current minute), whenever head node from "seconds" circular queue is recycled. This circular queue will be recycled whenever the head node is past 1 hour. Maintain max and min temp for the hour and update it whenever a new node is added.

Maintain another "hours" circular queue that will be added with new node (for current hour), whenever the head node from "minutes" circular queue is recycled. This queue will be recycled whenever the head node is past 24 hours. Maintain max and min temp for the 24 hour period and update it whenever new node is added or when head node is recycled. Search and update for max and min happens only if the node added or removed impacts max and min values.

There will be 12 + 60 + 24 nodes in total combining all queues.

#include<stdio.h>
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;

/* If there is only on element */
if (low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}

/* If there are two elements */
if (high == low + 1)
{
if (arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);

/* compare minimums of two parts*/
if (mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;

/* compare maximums of two parts*/
if (mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Keep an index of temperatures, rather than times. It won't contain many values Here's some python:

import random
import pprint
from datetime import datetime, timedelta

class Temperatures:
	def __init__(self):
		self.temperature_index = {}

	# called by a cron at the chosen interval
	def poll_temperature(self):
		temperature = self.get_temp()
		time = datetime.utcnow()
		self.temperature_index[temperature] = time
		for degree in self.temperature_index:
			if self.temperature_index[degree] < time - timedelta(hours=24):
				self.temperature_index.pop(degree, None)

	def high(self):
		key = max(self.temperature_index)
		return (key, self.temperature_index[key])

	def low(self):
		key = min(self.temperature_index)
		return (key, self.temperature_index[key])

	def get_temp(self):
		# ...connect to device, etc...
		return random.randrange(60, 80)

temp = Temperatures()
temp.poll_temperature()
temp.poll_temperature()
temp.poll_temperature()
temp.poll_temperature()
temp.poll_temperature()
temp.poll_temperature()
temp.poll_temperature()

print("High: ", temp.high())
print("Low: ", temp.low())
pp = pprint.PrettyPrinter(indent=4)
pp.pprint(temp.temperature_index)