面試用的 Python 標準函式庫

n = 15 (complete tree, 4 levels)

level        shape           #nodes   max sift-down   work
  0            o                1           3           3
  1          o   o              2           2           4
  2         o o o o             4           1           4
  3       o o o o o o o o       8           0           0   <- half the nodes, FREE
                                                      ----
                                              total =  11   (< 2n = 30)

import heapq

#-------------------------------
# Basic Heap Operations
#-------------------------------

# Create empty heap
heap = []

# heappush: Add element to heap
# Time: O(log n)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
print(heap)  # [1, 3, 7, 5] - min heap property maintained

# heappop: Remove and return smallest element
# Time: O(log n)
smallest = heapq.heappop(heap)
print(smallest)  # 1
print(heap)      # [3, 5, 7]

# heappushpop: Push then pop (more efficient than separate operations)
# Time: O(log n)
result = heapq.heappushpop(heap, 2)  # Push 2, then pop smallest
print(result)  # 2
print(heap)    # [3, 5, 7]

# heapreplace: Pop then push (more efficient than separate operations)
# Time: O(log n)
result = heapq.heapreplace(heap, 4)  # Pop smallest, then push 4
print(result)  # 3
print(heap)    # [4, 5, 7]

#-------------------------------
# PEEK : get TOP element WITHOUT popping  ***
#-------------------------------

# !!! heapq has NO peek() function
# -> the heap IS a plain python list, and the heap invariant guarantees
#    the SMALLEST element sits at index 0  =>  heap[0] IS the peek
# Time: O(1)

top = heap[0]
print(top)   # 4  -> heap NOT modified
print(heap)  # [4, 5, 7]

# safe peek (heap[0] raises IndexError when heap is empty)
top = heap[0] if heap else None

# max heap : push NEGATED values, negate back when peeking
max_heap = []
for v in [5, 3, 7]:
    heapq.heappush(max_heap, -v)
largest = -max_heap[0]   # 7   (peek, NOT pop)

# ── other ways to peek, and why they are WORSE ──
#   heap[0]                    -> O(1)   ✅ idiomatic
#   heapq.nsmallest(1, heap)[0]-> O(n)   ❌ scans whole list
#   min(heap)                  -> O(n)   ❌ ignores heap structure
#   pq.queue[0]                -> O(1)   only for queue.PriorityQueue (thread-safe wrapper)

# ── ⚠️ GOTCHA 1 : ONLY index 0 is meaningful ──
h = [1, 3, 9, 7, 5]   # a VALID min heap
h[0]    # 1  ✅ guaranteed smallest
h[1]    # 3  ❌ NOT necessarily the 2nd smallest
h[-1]   # 5  ❌ NOT the largest
# a heap is only PARTIALLY ordered! for the 2nd smallest -> sorted(h)[1] (O(n log n))

# ── ⚠️ GOTCHA 2 : IndexError on empty heap -> guard FIRST (short-circuit) ──
pq = []
while pq and pq[0] < 10:   # ✅ `pq and ...` must come first
    heapq.heappop(pq)
# while pq[0] < 10 and pq:  # ❌ IndexError

# ── classic use : LAZY DELETION (peek -> drop stale tops) ──
# LC 3092 Most Frequent IDs / LC 218 Skyline / LC 1834 Single-Threaded CPU
# heapq can NOT remove an element from the middle, so we mark entries stale
# and pop them only when they surface at the top.
#
#   while pq and -pq[0][0] != c_map[pq[0][1]]:   # peek, compare, discard
#       heapq.heappop(pq)
#   ans = -pq[0][0] if pq else 0                 # now the top is VALID

# ── avoid a separate peek when you REPLACE the top anyway ──
# heapq.heapreplace(h, x)   # pop then push -> 1 sift (heap must be non-empty)
# heapq.heappushpop(h, x)   # push then pop -> cheaper when x <= h[0]

# ── java comparison ──
#   python : heap[0]      -> IndexError if empty  (NO peek() exists)
#   java   : pq.peek()    -> null if empty
#            pq.element() -> throws NoSuchElementException if empty

#-------------------------------
# Convert List to Heap
#-------------------------------

# heapify: Transform list into heap in-place
# Time: O(n) - more efficient than n × heappush
nums = [5, 7, 9, 1, 3]
heapq.heapify(nums)
print(nums)  # [1, 3, 9, 7, 5] - min heap

#-------------------------------
# Top K Elements (Most Common Interview Pattern)
#-------------------------------

# nsmallest: Find k smallest elements
# Time: O(n log k)
nums = [5, 7, 9, 1, 3, 4, 6, 8, 2]
k_smallest = heapq.nsmallest(3, nums)
print(k_smallest)  # [1, 2, 3]

# nlargest: Find k largest elements
# Time: O(n log k)
k_largest = heapq.nlargest(3, nums)
print(k_largest)  # [9, 8, 7]

# With key function (common in LC problems)
people = [(1, 'Alice'), (3, 'Bob'), (2, 'Charlie')]
top_2_by_id = heapq.nsmallest(2, people, key=lambda x: x[0])
print(top_2_by_id)  # [(1, 'Alice'), (2, 'Charlie')]

#-------------------------------
# Max Heap Pattern (Negate Values)
#-------------------------------

# Python heapq is min heap, for max heap: negate values
max_heap = []
for val in [5, 7, 9, 1, 3]:
    heapq.heappush(max_heap, -val)  # Negate for max heap

# Get largest element
largest = -heapq.heappop(max_heap)
print(largest)  # 9

# Example: Top K Frequent Elements
from collections import Counter
def topKFrequent(nums, k):
    count = Counter(nums)
    # Use negative frequency for max heap
    return heapq.nlargest(k, count.keys(), key=count.get)

#-------------------------------
# Merge K Sorted Lists/Arrays
#-------------------------------

# merge: Merge multiple sorted iterables
# Time: O(n log k) where k = number of iterables
list1 = [1, 3, 5]
list2 = [2, 4, 6]
list3 = [0, 7, 8]
merged = list(heapq.merge(list1, list2, list3))
print(merged)  # [0, 1, 2, 3, 4, 5, 6, 7, 8]

# Custom comparison for merge
# Example: Merge by second element of tuple
data1 = [(1, 'a'), (3, 'c')]
data2 = [(2, 'b'), (4, 'd')]
merged = list(heapq.merge(data1, data2, key=lambda x: x[0]))
print(merged)  # [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd')]

#-------------------------------
# Common LeetCode Patterns
#-------------------------------

# Pattern 1: Kth Largest Element (LC 215)
def findKthLargest(nums, k):
    # Use min heap of size k
    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)

    return heap[0]

# Pattern 2: Top K Frequent Elements (LC 347)
def topKFrequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

# Pattern 3: Kth Smallest in Sorted Matrix (LC 378)
def kthSmallest(matrix, k):
    """
    Use heap to track smallest elements across rows
    """
    n = len(matrix)
    heap = []

    # Add first element from each row
    for r in range(min(k, n)):
        heapq.heappush(heap, (matrix[r][0], r, 0))

    result = 0
    for _ in range(k):
        result, r, c = heapq.heappop(heap)
        if c + 1 < len(matrix[0]):
            heapq.heappush(heap, (matrix[r][c+1], r, c+1))

    return result

# Pattern 4: Merge K Sorted Lists (LC 23)
def mergeKLists(lists):
    """
    Merge k sorted linked lists
    """
    heap = []
    # Initialize heap with first node from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    current = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next

        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

# Pattern 5: Sliding Window Maximum (LC 239)
# Note: Usually solved with deque, but can use heap
def maxSlidingWindow(nums, k):
    """
    Use max heap (negate values) with index tracking
    """
    heap = []
    result = []

    for i, num in enumerate(nums):
        # Add to max heap (negate for max heap)
        heapq.heappush(heap, (-num, i))

        # Remove elements outside window
        while heap[0][1] <= i - k:
            heapq.heappop(heap)

        # Window is full
        if i >= k - 1:
            result.append(-heap[0][0])

    return result

#-------------------------------
# Advanced: Custom Comparison with Classes
#-------------------------------

# For complex objects, use tuples or dataclass with functools.total_ordering
from dataclasses import dataclass
from functools import total_ordering

@total_ordering
@dataclass
class Task:
    priority: int
    name: str

    def __lt__(self, other):
        return self.priority < other.priority

# Use with heapq
task_heap = []
heapq.heappush(task_heap, Task(3, "Low priority"))
heapq.heappush(task_heap, Task(1, "High priority"))
heapq.heappush(task_heap, Task(2, "Medium priority"))

top_task = heapq.heappop(task_heap)
print(top_task)  # Task(priority=1, name='High priority')

#-------------------------------
# Performance Tips
#-------------------------------

# 1. Use heapify() instead of repeated heappush() - O(n) vs O(n log n)
# SLOW:
heap = []
for num in nums:
    heapq.heappush(heap, num)  # O(n log n)

# FAST:
heap = nums[:]
heapq.heapify(heap)  # O(n)

# 2. Use nsmallest/nlargest for small k
# When k << n: nsmallest/nlargest are optimized
# When k ≈ n: just sort the array

# 3. For Top K problems with streaming data: maintain heap of size k

# Instead of storing (dist, x, y), store (-dist, x, y)

from heapq import heapify, heappop

pq = [(-10, "A"), (-5, "B"), (-20, "C")]
heapify(pq)

print(heappop(pq))  # (-20, 'C')  ← largest original dist (20) comes out first
print(heappop(pq))  # (-10, 'A')
print(heappop(pq))  # (-5,  'B')

import heapq

max_heap = []
heapq.heappush(max_heap, (-priority, value))

# Pop: negate back to get original value
neg_pri, val = heapq.heappop(max_heap)
print(-neg_pri, val)

# Sort by dist descending; on tie, by name ascending
heapq.heappush(pq, (-dist, name))

from sortedcontainers import SortedDict, SortedList

# ---------------- SortedDict (TreeMap) ----------------
sd = SortedDict()

# O(log n) basic ops
sd[key] = value          # insert / update
v = sd.get(key)          # lookup (None if missing)
del sd[key]              # delete
key in sd                # membership

# Ordered access — keys() is an indexable sorted view
sd.keys()[0]             # min key
sd.keys()[-1]            # max key
sd.peekitem(0)           # (min_key, val)
sd.peekitem(-1)          # (max_key, val)

# Floor / Ceiling via bisect methods on the keys (THE TreeMap superpower)
keys = sd.keys()
i = sd.bisect_left(target)    # first index with key >= target
j = sd.bisect_right(target)   # first index with key >  target
#   ceiling(target) = keys[i]      if i < len(sd)      (smallest key >= target)
#   floor(target)   = keys[j - 1]  if j > 0            (largest  key <= target)

# Range query: iterate keys in [lo, hi)
lo_i = sd.bisect_left(lo)
hi_i = sd.bisect_left(hi)
for k in sd.keys()[lo_i:hi_i]:
    process(k, sd[k])

# Range query, cleaner: irange (inclusive both ends by default)
for k in sd.irange(lo, hi):
    process(k, sd[k])

sd.popitem(0)            # pollFirstEntry()
sd.popitem(-1)           # pollLastEntry()

# ---------------- SortedList (TreeSet / multiset) ----------------
sl = SortedList()
sl.add(x)                # O(log n) insert, stays sorted
sl.remove(x)             # O(log n) delete one occurrence
sl[0], sl[-1]            # min / max
i = sl.bisect_left(x)    # floor/ceiling index, same idea as above

# ✅ the safe floor / ceiling idiom — memorize this
i = d.bisect_left(x)
ceil_key = d.keys()[i] if i < len(d) else None       # ceilingKey(x)

j = d.bisect_right(x) - 1
floor_key = d.keys()[j] if j >= 0 else None          # floorKey(x)

// java
// LC 729 - My Calendar I
TreeMap<Integer, Integer> calendar = new TreeMap<>();

public boolean book(int start, int end) {
    Integer prev = calendar.floorKey(start);    // largest start <= start
    Integer next = calendar.ceilingKey(start);  // smallest start >= start

    if ((prev == null || calendar.get(prev) <= start) &&
        (next == null || end <= next)) {
        calendar.put(start, end);
        return true;
    }
    return false;
}

# python
# LC 729 - My Calendar I
# IDEA: mirror floorKey / ceilingKey with bisect_right / bisect_left, then guard the index
from sortedcontainers import SortedDict

class MyCalendar:
    # time = O(log N) per booking, space = O(N)
    def __init__(self):
        self.calendar = SortedDict()   # {start: end}

    def book(self, start: int, end: int) -> bool:
        keys = self.calendar.keys()

        # floorKey(start): largest key <= start
        i = self.calendar.bisect_right(start)
        prev = keys[i - 1] if i > 0 else None

        # ceilingKey(start): smallest key >= start
        j = self.calendar.bisect_left(start)
        nxt = keys[j] if j < len(keys) else None

        if (prev is None or self.calendar[prev] <= start) and \
           (nxt is None or end <= nxt):
            self.calendar[start] = end
            return True
        return False

# python
# LC 729 - My Calendar I
# IDEA: keep intervals sorted as tuples; only the neighbours at the insert
#       position can possibly overlap
from sortedcontainers import SortedList

class MyCalendar:
    # time = O(log N) per booking, space = O(N)
    def __init__(self):
        self.books = SortedList()      # sorted (start, end) tuples

    def book(self, start: int, end: int) -> bool:
        i = self.books.bisect_left((start, end))
        if i > 0 and self.books[i - 1][1] > start:            # prev spills into us
            return False
        if i < len(self.books) and end > self.books[i][0]:    # we spill into next
            return False
        self.books.add((start, end))
        return True

# python
# LC 729 - My Calendar I
import bisect

class MyCalendar:
    # time = O(N) per booking (list shifting), space = O(N)
    def __init__(self):
        self.books = []                # sorted (start, end) tuples

    def book(self, start: int, end: int) -> bool:
        i = bisect.bisect_left(self.books, (start, end))
        if i > 0 and self.books[i - 1][1] > start:
            return False
        if i < len(self.books) and end > self.books[i][0]:
            return False
        self.books.insert(i, (start, end))
        return True

from sortedcontainers import SortedList

def containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
    # keep a sliding window of the last `indexDiff` values, kept sorted
    window = SortedList()
    for i, num in enumerate(nums):
        # ceiling: smallest value >= num - valueDiff
        pos = window.bisect_left(num - valueDiff)
        if pos < len(window) and window[pos] <= num + valueDiff:
            return True
        window.add(num)
        if len(window) > indexDiff:        # evict the value that falls out of window
            window.remove(nums[i - indexDiff])
    return False

# https://docs.python.org/zh-tw/3/library/bisect.html
# src code : https://github.com/python/cpython/blob/3.10/Lib/bisect.py
# https://myapollo.com.tw/zh-tw/python-bisect/
# https://www.liujiangblog.com/course/python/57


"""
NOTE !!! before using bisect, we need SORT the array
"""

#-------------------------------
# bisect_left
#-------------------------------
# will return an idx for inserting new element a, and keep the new array sorted, if element a already existed in array, will insert to "original" a's left idx

# example 1
In [3]: import bisect
   ...: a = [2,4,6]
   ...: idx = bisect.bisect_left(a, 3)
   ...: print (idx)
   ...:
   ...: a.insert(idx, 3)
   ...: print (a)
   ...:
1
[2, 3, 4, 6]


# example 2
In [4]: import bisect
   ...: a = [2, 4, 6]
   ...: idx = bisect.bisect_left(a, 4)
   ...: print (idx)
   ...:
   ...: a.insert(idx, 4)
   ...: print (a)
1
[2, 4, 4, 6]

#-------------------------------
# bisect_right
#-------------------------------
# will return an idx for inserting new element a, and keep the new array sorted, if element a already existed in array, will insert to "original" a's right idx

In [5]:
   ...: import bisect
   ...: a = a = [2, 2, 4, 4, 6, 6, 8, 8]
   ...: idx = bisect.bisect_right(a, 4)
   ...: print (idx)
   ...:
   ...: a.insert(idx, 4)
   ...: print (a)
4
[2, 2, 4, 4, 4, 6, 6, 8, 8]

#-------------------------------
# bisect
#-------------------------------
# bisect.bisect : 
#   -> similar as bisect.bisect_right
#   -> similar as bisect.bisect_left, but will insert to element RIGHT instead
# https://docs.python.org/zh-tw/3/library/bisect.html
# https://blog.csdn.net/qq_34914551/article/details/100062973

# example 1
# In [3]: import bisect
#    ...: a = [2, 4, 6, 8]
#    ...: idx = bisect.bisect(a, 7)
#    ...: print (idx)
#    ...: a.insert(idx, 7)
#    ...: print (a)
# 3
# [2, 4, 6, 7, 8]

#-------------------------------
# insort, insort_right, insort_left
#-------------------------------
# insort, insort_right, insort_left : will get idx and insert to array  (with idx) directly

# example 1
In [8]: import bisect
   ...: a = [2, 4, 6, 8]
   ...: bisect.insort_left(a, 4)
   ...: print (a)
   ...:
[2, 4, 4, 6, 8]

# exmaple 2
In [7]: import bisect
   ...: a = [2, 4, 6, 8]
   ...: bisect.insort_right(a, 4)
   ...: print (a)
[2, 4, 4, 6, 8]

# defaultdict never raises KeyError — returns a default value for missing keys
from collections import defaultdict

#----------------------------
# example 1 : int (default 0)
#----------------------------
d = defaultdict(int)
for ch in "aabbbc":
    d[ch] += 1
print(dict(d))  # {'a': 2, 'b': 3, 'c': 1}

#----------------------------
# example 2 : list (default [])
#----------------------------
graph = defaultdict(list)
edges = [(0,1),(0,2),(1,3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
# graph[0] -> [1, 2],  graph[99] -> []  (no KeyError)

#----------------------------
# example 3 : set (default set())
#----------------------------
d = defaultdict(set)
d['key'].add(1)
d['key'].add(2)
print(d['key'])  # {1, 2}

#----------------------------
# example 4 : nested defaultdict (adjacency matrix with weights)
#----------------------------
dist = defaultdict(lambda: defaultdict(lambda: float('inf')))
dist[0][1] = 5
print(dist[0][1])   # 5
print(dist[0][99])  # inf

from collections import Counter

#----------------------------
# basic usage
#----------------------------
c = Counter("aabbbc")
print(c)            # Counter({'b': 3, 'a': 2, 'c': 1})
print(c['b'])       # 3
print(c['z'])       # 0  (no KeyError, returns 0)

# most_common(k) : top k frequent elements
print(c.most_common(2))   # [('b', 3), ('a', 2)]

# Counter arithmetic
c1 = Counter("aab")
c2 = Counter("abc")
print(c1 + c2)  # Counter({'a': 3, 'b': 2, 'c': 1})
print(c1 - c2)  # Counter({'a': 1})  (only positive counts)
print(c1 & c2)  # Counter({'a': 1, 'b': 1})  intersection (min)
print(c1 | c2)  # Counter({'a': 2, 'b': 1, 'c': 1})  union (max)

# update (add) vs subtract
c = Counter({'a': 3})
c.update({'a': 1, 'b': 2})
print(c)    # Counter({'a': 4, 'b': 2})
c.subtract({'a': 2})
print(c)    # Counter({'a': 2, 'b': 2})

# LC 347 Top K Frequent Elements
from collections import Counter
def topKFrequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

from collections import deque

# deque() vs deque([]) — both produce an empty deque, functionally identical
q = deque()    # preferred: no unnecessary empty list created
q = deque([])  # equivalent but verbose; the [] is an extra throwaway object

# O(1) append/pop from BOTH ends (list.pop(0) is O(n))
d = deque([1, 2, 3])

d.append(4)       # [1, 2, 3, 4]
d.appendleft(0)   # [0, 1, 2, 3, 4]
d.pop()           # removes 4  -> [0, 1, 2, 3]
d.popleft()       # removes 0  -> [1, 2, 3]

# maxlen: auto-evicts oldest element (sliding window)
d = deque(maxlen=3)
for i in range(5):
    d.append(i)
print(d)  # deque([2, 3, 4], maxlen=3)

#----------------------------
# BFS template with deque
#----------------------------
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

#----------------------------
# Monotonic deque (LC 239 Sliding Window Maximum)
#----------------------------
def maxSlidingWindow(nums, k):
    d = deque()   # stores indices, decreasing order of values
    result = []
    for i, num in enumerate(nums):
        while d and nums[d[-1]] <= num:
            d.pop()
        d.append(i)
        if d[0] == i - k:   # front out of window
            d.popleft()
        if i >= k - 1:
            result.append(nums[d[0]])
    return result

# https://docs.python.org/zh-cn/3/library/itertools.html
# https://docs.python.org/zh-tw/3/library/itertools.html

# itertools — Functions creating iterators for efficient looping

#-----------------------------------------------------------------------------------------------------
# example 1 : itertools.accumulate : Aggregated sum
#-----------------------------------------------------------------------------------------------------
In [10]: import itertools
    ...: x = itertools.accumulate(range(10))
    ...: print (list(x))
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

#-----------------------------------------------------------------------------------------------------
# example 2 : itertools.combinations : get NON-duplicated elements from collections (with given len)
#-----------------------------------------------------------------------------------------------------
In [15]:  x = itertools.combinations(range(4), 3)

In [16]: print (list(x))
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

In [17]: x = itertools.combinations(range(4), 4)

In [18]: print (list(x))
[(0, 1, 2, 3)]

#-----------------------------------------------------------------------------------------------------
# example 3 : itertools.combinations_with_replacement : get duplicated or non-duplicated elements from collections (with given len)
#-----------------------------------------------------------------------------------------------------
In [19]: x = itertools.combinations_with_replacement('ABC', 2)

In [20]: print(list(x))
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

In [21]: x = itertools.combinations_with_replacement('ABC', 1)

In [22]: print(list(x))
[('A',), ('B',), ('C',)]

In [24]: x = itertools.combinations_with_replacement([1,2,2,1], 2)

In [25]: print (list(x))
[(1, 1), (1, 2), (1, 2), (1, 1), (2, 2), (2, 2), (2, 1), (2, 2), (2, 1), (1, 1)]

#-----------------------------------------------------------------------------------------------------
# example 4 : itertools.compress : filter elements by True/False
#-----------------------------------------------------------------------------------------------------
In [26]: x = itertools.compress(range(5), (True, False, True, True, False))

In [27]: print (list(x))
[0, 2, 3]

#-----------------------------------------------------------------------------------------------------
# example 5 : itertools.count : a counter, can define start point and path len
#-----------------------------------------------------------------------------------------------------
# NOTE THIS !!!!
In [2]: x = itertools.count(start=20, step=-1)

In [3]: print(list(itertools.islice(x, 0, 10, 1)))
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11]

#-----------------------------------------------------------------------------------------------------
# example 6 : itertools.groupby : group by lists by value
#-----------------------------------------------------------------------------------------------------
In [4]: x = itertools.groupby(range(10), lambda x: x < 5 or x > 8)

In [5]: for condition, numbers in x:
   ...:     print(condition, list(numbers))
   ...:
True [0, 1, 2, 3, 4]
False [5, 6, 7, 8]
True [9]

#-----------------------------------------------------------------------------------------------------
# example 7 : itertools.islice : slice on iterator
#-----------------------------------------------------------------------------------------------------
# https://docs.python.org/3/library/itertools.html#itertools.islice
# syntax : itertools.islice(seq, [start,] stop [, step])

In [6]:  x = itertools.islice(range(10), 0, 9, 2)

In [7]: print (list(x))
[0, 2, 4, 6, 8]

#-----------------------------------------------------------------------------------------------------
# example 8 : itertools.permutations : generate all combinations (ordering mattered)
#-----------------------------------------------------------------------------------------------------

In [9]: x = itertools.permutations(range(4), 3)

In [10]: print(list(x))
[(0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 3), (0, 3, 1), (0, 3, 2), (1, 0, 2), (1, 0, 3), (1, 2, 0), (1, 2, 3), (1, 3, 0), (1, 3, 2), (2, 0, 1), (2, 0, 3), (2, 1, 0), (2, 1, 3), (2, 3, 0), (2, 3, 1), (3, 0, 1), (3, 0, 2), (3, 1, 0), (3, 1, 2), (3, 2, 0), (3, 2, 1)]

#-----------------------------------------------------------------------------------------------------
# example 9 : itertools.product : generate multiple lists, and iterators's product
#-----------------------------------------------------------------------------------------------------

In [11]:  x = itertools.product('ABC', range(3))

In [12]: print(list(x))
[('A', 0), ('A', 1), ('A', 2), ('B', 0), ('B', 1), ('B', 2), ('C', 0), ('C', 1), ('C', 2)]

# example 1
@lru_cache
def count_vowels(sentence):
    return sum(sentence.count(vowel) for vowel in 'AEIOUaeiou')

# example 2
@lru_cache(maxsize=32)
def get_pep(num):
    'Retrieve text of a Python Enhancement Proposal'
    resource = 'https://www.python.org/dev/peps/pep-%04d/' % num
    try:
        with urllib.request.urlopen(resource) as s:
            return s.read()
    except urllib.error.HTTPError:
        return 'Not Found'

# example 3
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

# example 4
@api.route("/user/info", methods=["GET"])
@functools.lru_cache()
@login_require
def get_userinfo_list():
    userinfos = UserInfo.query.all()
    userinfo_list = [user.to_dict() for user in userinfos]
    return jsonify(userinfo_list)

from functools import reduce

# reduce(func, iterable[, initializer])
# Applies func cumulatively: func(func(a, b), c) ...

product = reduce(lambda a, b: a * b, [1, 2, 3, 4])   # 24
total   = reduce(lambda a, b: a + b, [1, 2, 3, 4], 0) # 10

# XOR all elements (LC 136 Single Number)
from functools import reduce
import operator
result = reduce(operator.xor, [4, 1, 2, 1, 2])  # 4
# equivalent to:
result = reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2])

# LC 681.Next Closest Time
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/String/next-closest-time.py

from datetime import datetime, timedelta

x = "10:20"

#--------------------------------------
# strptime : string -> datetime 
# (Return a datetime corresponding to date_string, parsed according to format.)
#--------------------------------------
x_datetime =  datetime.strptime(x, "%H:%M")
print (x_datetime)
# 1900-01-01 10:20:00


#--------------------------------------
# strftime : datetime -> string 
# (Return a string representing the date)
#--------------------------------------
x_str = x_datetime.strftime("%H:%M")
print (x_str)
# 10:20

# eatra : timedelta
tmp = x_datetime + timedelta(minutes=10)
print (tmp)
# 1900-01-01 10:30:00