break algorithm---multi-interface

---

---

python Language implementation

---

341.flatten-nested-list-iterator
600.non-negative-integers-without-consecutive-ones
707.design-linked-list
1603.design-parking-system
1656.design-an-ordered-stream
1670.design-front-middle-back-queue
1797.design-authentication-manager
1845.seat-reservation-manager
1912.design-movie-rental-system

---

---

341.flatten-nested-list-iterator

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """


class NestedInteger:
   def isInteger(self) -> bool:
       """ @return True if this NestedInteger holds a single integer, rather than a nested list. """

   def getInteger(self) -> int:
       """ @return the single integer that this NestedInteger holds, if it holds a single integer Return None if this NestedInteger holds a nested list """

   # def getList(self) -> [NestedInteger]:
   def getList(self):
       """ @return the nested list that this NestedInteger holds, if it holds a nested list Return None if this NestedInteger holds a single integer """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):

        def gen(nl):
            for ni in nl:
                if ni.isInteger():
                    yield ni.getInteger()
                else:
                    yield from gen(ni.getList())

        self.it = gen(nestedList)
        try:
            self.store = next(self.it)
        except StopIteration:
            self.store = None

    def next(self) -> int:
        ret = self.store
        try:
            self.store = next(self.it)
        except StopIteration:
            self.store = None
        return ret

    def hasNext(self) -> bool:
        return self.store is not None


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

---

---

---

---

707.design-linked-list

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None


class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = ListNode(0)  # sentinel node as pseudo-head

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        curr = self.head
        for _ in range(index + 1):
            curr = curr.next
        return curr.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return

        if index < 0:
            index = 0

        self.size += 1
        # find predecessor of the node to be added
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # node to be added
        to_add = ListNode(val)
        # insertion itself
        to_add.next = pred.next
        pred.next = to_add

    def deleteAtIndex(self, index: int) -> None:
        """ Delete the index-th node in the linked list, if the index is valid. """
        # if the index is invalid, do nothing
        if index < 0 or index >= self.size:
            return

        self.size -= 1
        # find predecessor of the node to be deleted
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # delete pred.next
        pred.next = pred.next.next

    def print(self) -> None:
        p = self.head
        while p.next:
            p = p.next
            print(p.val)


# Your MyLinkedList object will be instantiated and called as such:
linkedList = MyLinkedList()

linkedList.addAtHead(1)
linkedList.print()
print('---')


linkedList.addAtTail(3)
linkedList.print()
print('---')


linkedList.addAtIndex(1, 2)  #  Linked list becomes 1-> 2-> 3
linkedList.print()
print('---')


linkedList.get(1)  #  return 2
linkedList.print()
print('---')

linkedList.deleteAtIndex(1)  #  Now the list is 1-> 3
linkedList.print()
print('---')

linkedList.get(1)  #  return 3
linkedList.print()
print('---')

---

---

1603.design-parking-system

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.big = big
        self.medium = medium
        self.small = small

    def addCar(self, carType: int) -> bool:
        if carType == 1 and self.big > 0:
            self.big -= 1
            return True
        if carType == 2 and self.medium > 0:
            self.medium -= 1
            return True
        if carType == 3 and self.small > 0:
            self.small -= 1
            return True
        return False


# Your ParkingSystem object will be instantiated and called as such:
obj = ParkingSystem(1, 1, 0)

#  return  true , Because there is  1  A big empty parking space 
print(obj.addCar(1))

#  return  true , Because there is  1  An empty middle parking space 
print(obj.addCar(2))

#  return  false , Because there are no empty parking spaces 
print(obj.addCar(3))

#  return  false , Because there are no big empty parking spaces , The only big parking space has been occupied 
print(obj.addCar(1))

---

---

1656.design-an-ordered-stream

from typing import List


class OrderedStream:

    def __init__(self, n: int):
        self.n = n
        self.ptr = 1
        self.stream = {
    }

    def insert(self, idKey: int, value: str) -> List[str]:
        if idKey < 0 or idKey > self.n:
            return []

        self.stream.setdefault(idKey, value)
        res = []
        if self.stream.get(self.ptr):
            while idKey < self.n + 1:
                if self.stream.get(idKey):
                    res.append(self.stream.get(idKey))
                    idKey += 1
                    self.ptr = idKey
                else:
                    break
        # print(res)
        return res


# Your OrderedStream object will be instantiated and called as such:
obj = OrderedStream(5)

#  Insert  (3, "ccccc"), return  []
obj.insert(3, "ccccc")

#  Insert  (1, "aaaaa"), return  ["aaaaa"]
obj.insert(1, "aaaaa")

#  Insert  (2, "bbbbb"), return  ["bbbbb", "ccccc"]
obj.insert(2, "bbbbb")

#  Insert  (5, "eeeee"), return  []
obj.insert(5, "eeeee")

#  Insert  (4, "ddddd"), return  ["ddddd", "eeeee"]
obj.insert(4, "ddddd")

---

---

1670.design-front-middle-back-queue

class FrontMiddleBackQueue:

    def __init__(self):
        self.list = []

    def pushFront(self, val: int) -> None:
        self.list.insert(0, val)

    def pushMiddle(self, val: int) -> None:
        self.list.insert(len(self.list) // 2, val)

    def pushBack(self, val: int) -> None:
        self.list.append(val)

    def popFront(self) -> int:
        # self.list.try_pop(0)
        return self.try_pop(0)

    def popMiddle(self) -> int:
        return self.try_pop((len(self.list) - 1) // 2)

    def popBack(self) -> int:
        return self.try_pop(-1)

    def try_pop(self, index):
        try:
            return self.list.pop(index)
        except:
            return -1

    def print(self):
        print(self.list)


# Your FrontMiddleBackQueue object will be instantiated and called as such:
q = FrontMiddleBackQueue()

# [1]
q.pushFront(1)
q.print()
print('---')

# [1, 2]
q.pushBack(2)
q.print()
print('---')

# [1, 3, 2]
q.pushMiddle(3)
q.print()
print('---')

# [1, 4, 3, 2]
q.pushMiddle(4)
q.print()
print('---')

# return 1 -> [4, 3, 2]
q.popFront()
q.print()
print('---')

# return 3 -> [4, 2]
q.popMiddle()
q.print()
print('---')

# return 4 -> [2]
q.popMiddle()
q.print()
print('---')

# return 2 -> []
q.popBack()
q.print()
print('---')

# return -1 -> [] (The queue is empty)
q.popFront()
q.print()
print('---')

---

---

1797.design-authentication-manager

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokenId = dict()

    def generate(self, tokenId: str, currentTime: int) -> None:
        self.tokenId.setdefault(tokenId, currentTime)

    def renew(self, tokenId: str, currentTime: int) -> None:
        if self.tokenId.get(tokenId) and currentTime < self.timeToLive + self.tokenId.get(tokenId):
            self.tokenId[tokenId] = currentTime
        else:
            return

    def countUnexpiredTokens(self, currentTime: int) -> int:
        res = 0
        times = self.tokenId.values()
        for time in times:
            if time + self.timeToLive > currentTime:
                res += 1
        return res


#  structure  AuthenticationManager , Set up  timeToLive = 5  second .
authenticationManager = AuthenticationManager(5)
#  moment  1  when , No captcha  tokenId  by  "aaa" , No captcha has been updated .
print(authenticationManager.renew("aaa", 1))
#  moment  2  when , Generate a  tokenId  by  "aaa"  New captcha for .
print(authenticationManager.generate("aaa", 2))
#  moment  6  when , Only  tokenId  by  "aaa"  Has not expired , So back  1 .
print(authenticationManager.countUnexpiredTokens(6))
#  moment  7  when , Generate a  tokenId  by  "bbb"  New captcha for .
print(authenticationManager.generate("bbb", 7))
# tokenId  by  "aaa"  The captcha is at the moment  7  Be overdue , And  8 >= 7 , So the moment  8  Of renew  Operation ignored , No captcha has been updated .
print(authenticationManager.renew("aaa", 8))
# tokenId  by  "bbb"  The captcha is at the moment  10  No expired , therefore  renew  The operation will perform , The  token  Will be at the moment  15  Be overdue .
print(authenticationManager.renew("bbb", 10))
# tokenId  by  "bbb"  The captcha is at the moment  15  Be overdue ,tokenId  by  "aaa"  The captcha is at the moment  7  Be overdue , All captions have expired , So back  0 .
print(authenticationManager.countUnexpiredTokens(15))

---

---

1845.seat-reservation-manager

---

---

1912.design-movie-rental-system

from collections import defaultdict
from typing import List
import sortedcontainers


class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.t_price = dict()
        self.t_valid = defaultdict(sortedcontainers.SortedList)
        self.t_rent = sortedcontainers.SortedList()

        for shop, movie, price in entries:
            self.t_price[(shop, movie)] = price
            self.t_valid[movie].add((price, shop))

    def search(self, movie: int) -> List[int]:
        t_valid_ = self.t_valid

        if movie not in t_valid_:
            return []

        return [shop for (price, shop) in t_valid_[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].discard((price, shop))
        self.t_rent.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].add((price, shop))
        self.t_rent.discard((price, shop, movie))

    def report(self) -> List[List[int]]:
        return [[shop, movie] for price, shop, movie in self.t_rent[:5]]


movieRentingSystem = MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]])
#  return  [1, 0, 2] , The store  1,0  and  2  There's something that hasn't been lent  ID  by  1  In the movie . The store  1  The cheapest , The store  0  and  2  The price is the same , So sort by store number .
movieRentingSystem.search(1)
#  From the store  0  Lending movies  1 . Now the store  0  The number of the unsold movie is  [2,3] .
movieRentingSystem.rent(0, 1)
print('---')
#  From the store  1  Lending movies  2 . Now the store  1  The number of the movie not lent is  [1] .
movieRentingSystem.rent(1, 2)
print('---')
#  return  [[0, 1], [1, 2]] . The store  0  Movies on loan  1  The cheapest , Then there's the shops  1  Movies on loan  2 .
movieRentingSystem.report()
#  In the shop  1  Return the movie  2 . Now the store  1  The number of the movie not lent is  [1,2] .
movieRentingSystem.drop(1, 2)
print('---')
# #  return  [0, 1] . The store  0  and  1  There's something that hasn't been lent  ID  by  2  In the movie . The store  0  The cheapest , Then there's the shops  1 .
# movieRentingSystem.search(2)