Object-Oriented_Design

Posted on | In , |

Multiple Inheritance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Father():
   def skills(self):
       print("gardening,programming")
class Mother():
   def skills(self):
       print("cooking,art")
class Child(Father,Mother):
    def skills(self):
        Father.skills(self)
        Mother.skills(self)
        print("sports")
c = Child()
c.skills()

Examples

Hash Table

  • For simplicity, are the keys integers only? (Yes)
  • For collision resolution, can we use chaining? (Yes)
  • Do we have to worry about load factors? (No)
  • Can we assume inputs are valid or do we have to validate them? (Assume they’re valid)
  • Can we assume this fits memory? (Yes)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Item(object):
        def __init__(self, key, value):
            self.key = key
            self.value = value
    class HashTable(object):
        def __init__(self, size):
            self.size = size
            self.table = [[] for _ in range(self.size)]
        def _hash_function(self, key):
            return key % self.size
        def set(self, key, value):
            hash_index = self._hash_function(key)
            for item in self.table[hash_index]:
                if item.key == key:
                    item.value = value
                    return
            self.table[hash_index].append(Item(key, value))
        def get(self, key):
            hash_index = self._hash_function(key)
            for item in self.table[hash_index]:
                if item.key == key:
                    return item.value
            raise KeyError('Key not found')
        def remove(self, key):
            hash_index = self._hash_function(key)
            for index, item in enumerate(self.table[hash_index]):
                if item.key == key:
                    del self.table[hash_index][index]
                    return
            raise KeyError('Key not found')

Parking Lot

  • What types of vehicles should we support? (Motorcycle, Car, Bus)
  • Does each vehicle type take up a different amount of parking spots?
    Yes
    • Motorcycle spot -> Motorcycle
    • Compact spot -> Motorcycle, Car
    • Large spot -> Motorcycle, Car
    • Bus can park if we have 5 consecutive “large” spots
  • Does the parking lot have multiple levels? (Yes)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
from abc import ABCMeta, abstractmethod
class VehicleSize(Enum):
    MOTORCYCLE = 0
    COMPACT = 1
    LARGE = 2
class Vehicle(metaclass=ABCMeta):
    def __init__(self, vehicle_size, license_plate, spot_size):
        self.vehicle_size = vehicle_size
        self.license_plate = license_plate
        self.spot_size = spot_size
        self.spots_taken = []
    def clear_spots(self):
        for spot in self.spots_taken:
            spot.remove_vehicle(self)
        self.spots_taken = []
    def take_spot(self, spot):
        self.spots_taken.append(spot)
    @abstractmethod
    def can_fit_in_spot(self, spot):
        pass
class Motorcycle(Vehicle):
    def __init__(self, license_plate):
        super(Motorcycle, self).__init__(VehicleSize.MOTORCYCLE, license_plate, spot_size=1)
    def can_fit_in_spot(self, spot):
        return True
class Car(Vehicle):
    def __init__(self, license_plate):
        super(Car, self).__init__(VehicleSize.COMPACT, license_plate, spot_size=1)
    def can_fit_in_spot(self, spot):
        return True if (spot.size == LARGE or spot.size == COMPACT) else False
class Bus(Vehicle):
    def __init__(self, license_plate):
        super(Bus, self).__init__(VehicleSize.LARGE, license_plate, spot_size=5)
    def can_fit_in_spot(self, spot):
        return True if spot.size == LARGE else False
class ParkingLot(object):
    def __init__(self, num_levels):
        self.num_levels = num_levels
        self.levels = []
    def park_vehicle(self, vehicle):
        for level in levels:
            if level.park_vehicle(vehicle):
                return True
        return False
class Level(object):
    SPOTS_PER_ROW = 10
    def __init__(self, floor, total_spots):
        self.floor = floor
        self.num_spots = total_spots
        self.available_spots = 0
        self.parking_spots = []
    def spot_freed(self):
        self.available_spots += 1
    def park_vehicle(self, vehicle):
        spot = self._find_available_spot(vehicle)
        if spot is None:
            return None
        else:
            spot.park_vehicle(vehicle)
            return spot
    def _find_available_spot(self, vehicle):
        """Find an available spot where vehicle can fit, or return None"""
        # ...
    def _park_starting_at_spot(self, spot, vehicle):
        """Occupy starting at spot.spot_number to vehicle.spot_size."""
        # ...
class ParkingSpot(object):
    def __init__(self, level, row, spot_number, spot_size, vehicle_size):
        self.level = level
        self.row = row
        self.spot_number = spot_number
        self.spot_size = spot_size
        self.vehicle_size = vehicle_size
        self.vehicle = None
    def is_available(self):
        return True if self.vehicle is None else False
    def can_fit_vehicle(self, vehicle):
        if self.vehicle is not None:
            return False
        return vehicle.can_fit_in_spot(self)
    def park_vehicle(self, vehicle):  # ...
    def remove_vehicle(self):  # ...

Call Center

  • What levels of employees are in the call center? (Operator, supervisor, director)
  • Can we assume operators always get the initial calls? (Yes)
  • If there is no free operators or the operator can’t handle the call, does the call go to the supervisors? (Yes)
  • If there is no free supervisors or the supervisor can’t handle the call, does the call go to the directors? (Yes)
  • Can we assume the directors can handle all calls? (Yes)
  • What happens if nobody can answer the call? (It gets queued)
  • Do we need to handle ‘VIP’ calls where we put someone to the front of the line? (No)
  • Can we assume inputs are valid or do we have to validate them? (Assume they’re valid)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from abc import ABCMeta, abstractmethod
from collections import deque
from enum import Enum
class Rank(Enum):
    OPERATOR = 0
    SUPERVISOR = 1
    DIRECTOR = 2
class Employee(metaclass=ABCMeta):
    def __init__(self, employee_id, name, rank, call_center):
        self.employee_id = employee_id
        self.name = name
        self.rank = rank
        self.call = None
        self.call_center = call_center
    def take_call(self, call):
        """Assume the employee will always successfully take the call."""
        self.call = call
        self.call.employee = self
        self.call.state = CallState.IN_PROGRESS
    def complete_call(self):
        self.call.state = CallState.COMPLETE
        self.call_center.notify_call_completed(self.call)
    @abstractmethod
    def escalate_call(self):
        pass
    def _escalate_call(self):
        self.call.state = CallState.READY
        call = self.call
        self.call = None
        self.call_center.notify_call_escalated(call)
class Operator(Employee):
    def __init__(self, employee_id, name):
        super(Operator, self).__init__(employee_id, name, Rank.OPERATOR)
    def escalate_call(self):
        self.call.level = Rank.SUPERVISOR
        self._escalate_call()
class Supervisor(Employee):
    def __init__(self, employee_id, name):
        super(Operator, self).__init__(employee_id, name, Rank.SUPERVISOR)
    def escalate_call(self):
        self.call.level = Rank.DIRECTOR
        self._escalate_call()
class Director(Employee):
    def __init__(self, employee_id, name):
        super(Operator, self).__init__(employee_id, name, Rank.DIRECTOR)
    def escalate_call(self):
        raise NotImplemented('Directors must be able to handle any call')
class CallState(Enum):
    READY = 0
    IN_PROGRESS = 1
    COMPLETE = 2
class Call(object):
    def __init__(self, rank):
        self.state = CallState.READY
        self.rank = rank
        self.employee = None
class CallCenter(object):
    def __init__(self, operators, supervisors, directors):
        self.operators = operators
        self.supervisors = supervisors
        self.directors = directors
        self.queued_calls = deque()
    def dispatch_call(self, call):
        if call.rank not in (Rank.OPERATOR, Rank.SUPERVISOR, Rank.DIRECTOR):
            raise ValueError('Invalid call rank: {}'.format(call.rank))
        employee = None
        if call.rank == Rank.OPERATOR:
            employee = self._dispatch_call(call, self.operators)
        if call.rank == Rank.SUPERVISOR or employee is None:
            employee = self._dispatch_call(call, self.supervisors)
        if call.rank == Rank.DIRECTOR or employee is None:
            employee = self._dispatch_call(call, self.directors)
        if employee is None:
            self.queued_calls.append(call)
    def _dispatch_call(self, call, employees):
        for employee in employees:
            if employee.call is None:
                employee.take_call(call)
                return employee
        return None
    def notify_call_escalated(self, call):  # ...
    def notify_call_completed(self, call):  # ...
    def dispatch_queued_call_to_newly_freed_employee(self, call, employee):  # ...

Deck of Cards

  • Is this a generic deck of cards for games like poker and black jack? (Yes, design a generic deck then extend it to black jack)
  • Can we assume the deck has 52 cards (2-10, Jack, Queen, King, Ace) and 4 suits? (Yes)
  • Can we assume inputs are valid or do we have to validate them? (Assume they’re valid)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
from abc import ABCMeta, abstractmethod
from enum import Enum
import sys
class Suit(Enum):
    HEART = 0
    DIAMOND = 1
    CLUBS = 2
    SPADE = 3
class Card(metaclass=ABCMeta):
    def __init__(self, value, suit):
        self.value = value
        self.suit = suit
        self.is_available = True
    @property
    @abstractmethod
    def value(self):
        pass
    @value.setter
    @abstractmethod
    def value(self, other):
        pass
class BlackJackCard(Card):
    def __init__(self, value, suit):
        super(BlackJackCard, self).__init__(value, suit)
    def is_ace(self):
        return self._value == 1
    def is_face_card(self):
        """Jack = 11, Queen = 12, King = 13"""
        return 10 < self._value <= 13
    @property
    def value(self):
        if self.is_ace() == 1:
            return 1
        elif self.is_face_card():
            return 10
        else:
            return self._value
    @value.setter
    def value(self, new_value):
        if 1 <= new_value <= 13:
            self._value = new_value
        else:
            raise ValueError('Invalid card value: {}'.format(new_value))
class Hand(object):
    def __init__(self, cards):
        self.cards = cards
    def add_card(self, card):
        self.cards.append(card)
    def score(self):
        total_value = 0
        for card in card:
            total_value += card.value
        return total_value
class BlackJackHand(Hand):
    BLACKJACK = 21
    def __init__(self, cards):
        super(BlackJackHand, self).__init__(cards)
    def score(self):
        min_over = sys.MAXSIZE
        max_under = -sys.MAXSIZE
        for score in self.possible_scores():
            if self.BLACKJACK < score < min_over:
                min_over = score
            elif max_under < score <= self.BLACKJACK:
                max_under = score
        return max_under if max_under != -sys.MAXSIZE else min_over
    def possible_scores(self):
        """Return a list of possible scores, taking Aces into account."""
        # ...
class Deck(object):
    def __init__(self, cards):
        self.cards = cards
        self.deal_index = 0
    def remaining_cards(self):
        return len(self.cards) - deal_index
    def deal_card():
        try:
            card = self.cards[self.deal_index]
            card.is_available = False
            self.deal_index += 1
        except IndexError:
            return None
        return card
    def shuffle(self):  # ...

Design an LRU cache¶

  • What are we caching? (cahing the results of web queries)
  • Can we assume inputs are valid or do we have to validate them? (Assume they’re valid)
  • Can we assume this fits memory? (Yes)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Node(object):
    def __init__(self, results):
        self.results = results
        self.prev = None
        self.next = None
class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
    def move_to_front(self, node):  # ...
    def append_to_front(self, node):  # ...
    def remove_from_tail(self):  # ...
class Cache(object):
    def __init__(self, MAX_SIZE):
        self.MAX_SIZE = MAX_SIZE
        self.size = 0
        self.lookup = {}  # key: query, value: node
        self.linked_list = LinkedList()
    def get(self, query)
        """Get the stored query result from the cache.
        
        Accessing a node updates its position to the front of the LRU list.
        """
        node = self.lookup.get(query)
        if node is None:
            return None
        self.linked_list.move_to_front(node)
        return node.results
    def set(self, results, query):
        """Set the result for the given query key in the cache.
        
        When updating an entry, updates its position to the front of the LRU list.
        If the entry is new and the cache is at capacity, removes the oldest entry
        before the new entry is added.
        """
        node = self.lookup.get(query)
        if node is not None:
            # Key exists in cache, update the value
            node.results = results
            self.linked_list.move_to_front(node)
        else:
            # Key does not exist in cache
            if self.size == self.MAX_SIZE:
                # Remove the oldest entry from the linked list and lookup
                self.lookup.pop(self.linked_list.tail.query, None)
                self.linked_list.remove_from_tail()
            else:
                self.size += 1
            # Add the new key and value
            new_node = Node(results)
            self.linked_list.append_to_front(new_node)
            self.lookup[query] = new_node