## Groupon Interview Question

Senior Software Development Engineers**Country:**United States

**Interview Type:**In-Person

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

This approach will not work.

Consider the following scenario

Temperature at 5:00 PM today - 30

Temperature at 5:30 PM today - 25

Temperature at 5:00 PM tomorrow- 24

In the above scenario the Max temperature in the last 24 hrs will be 25.

For Max_T (Min_T will be the same but reverse):

```
Max_T(T, time) = first_T(T, Time)
temp = [] of may_be_MaxT(T, time)
read Next_T(T, time):
if T.Next_T > OR = T.Max_T
Max_T = Next_T
temp = []
else temp[1] = Next_T
If time.Next_T > (time.Max_t + 24 hours):
Max_T = temp[1]
for i in range 2 to last
i = i-1
```

After this one should compare T.Next_T to T.Max_T, if the T is more or equal, then Max_T = Next_T, if T is less, then we compare it with the last value in the temp array.

```
If T.Next_T < T.temp[last] --> temp[last+1] = Next_T,
last = last+1
If T.Next_T = T.temp[last] --> temp[last] = Next_T,
If T.Next_T > T.temp[last] --> temp[last] = Next_T:
do compare T.temp[last] with T.temp[last-1]
until T.temp[last] < T.temp[last-1]
```

If we do not have to show the time, we can set time.Max_T as integer from 1 to 1728 (number of inputs per 24 hrs), increasing and decreasing the counter when needed. This will be anyway easier and more memory efficient.

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)
```

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

- Imithya May 10, 2014