This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook¶

Constraints¶

• Can we assume the inputs are valid?
• No
• Is there a range of inputs?
• 0 <= item <= 100
• Should mean return a float?
• Yes
• Should the other results return an int?
• Yes
• If there are multiple modes, what do we return?
• Any of the modes
• Can we assume this fits memory?
• Yes

Test Cases¶

• None -> TypeError
• [] -> ValueError
• [5, 2, 7, 9, 9, 2, 9, 4, 3, 3, 2]
• max: 9
• min: 2
• mean: 55
• mode: 9 or 2

Algorithm¶

• We'll init our max and min to None. Alternatively, we can init them to -sys.maxsize and sys.maxsize, respectively.
• For mean, we'll keep track of the number of items we have inserted so far, as well as the running sum.
• For mode, we'll keep track of the current mode and an array with the size of the given upper limit
• Each element in the array will be init to 0
• Each time we insert, we'll increment the element corresponding to the inserted item's value
• On each insert:
• Update the max and min
• Update the mean by calculating running_sum / num_items
• Update the mode by comparing the mode array's value with the current mode

Complexity:

• Time: O(1)
• Space: O(1), we are treating the 101 element array as a constant O(1), we could also see this as O(k)

Code¶

In [1]:
from __future__ import division

class Solution(object):

def __init__(self, upper_limit=100):
self.max = None
self.min = None
# Mean
self.num_items = 0
self.running_sum = 0
self.mean = None
# Mode
self.array = [0] * (upper_limit + 1)
self.mode_occurrences = 0
self.mode = None

def insert(self, val):
if val is None:
raise TypeError('val cannot be None')
if self.max is None or val > self.max:
self.max = val
if self.min is None or val < self.min:
self.min = val
# Calculate the mean
self.num_items += 1
self.running_sum += val
self.mean = self.running_sum / self.num_items
# Calculate the mode
self.array[val] += 1
if self.array[val] > self.mode_occurrences:
self.mode_occurrences = self.array[val]
self.mode = val


Unit Test¶

In [2]:
%%writefile test_math_ops.py
import unittest

class TestMathOps(unittest.TestCase):

def test_math_ops(self):
solution = Solution()
self.assertRaises(TypeError, solution.insert, None)
solution.insert(5)
solution.insert(2)
solution.insert(7)
solution.insert(9)
solution.insert(9)
solution.insert(2)
solution.insert(9)
solution.insert(4)
solution.insert(3)
solution.insert(3)
solution.insert(2)
self.assertEqual(solution.max, 9)
self.assertEqual(solution.min, 2)
self.assertEqual(solution.mean, 5)
self.assertTrue(solution.mode in (2, 9))
print('Success: test_math_ops')

def main():
test = TestMathOps()
test.test_math_ops()

if __name__ == '__main__':
main()

Overwriting test_math_ops.py

In [3]:
%run -i test_math_ops.py

Success: test_math_ops