Resources.md

題目參照

• top interview
• top 100
• Grind 75 (No hard, by topic)
• Neetcode

Python 常見操作複雜度

參考 Python Complexity

• list.sort(): Tim sort, $O(n\cdot logn)$
• set(list): $O(n)$
• x in set/dict: $O(1)$
• x in list: $O(n)$
• set/dict operation: $O(1)$
• set difference: $O(n)$
• list.pop(): $O(1)$ for last element while $O(n)$ for the others

相關重要演算法

• Fucking Algorithms Github or Its Website
• Dijkstra
• DFS Big-O and BFS Big-O
• Difference between DFS & BFS
• Performance comparison between list & deque
• LRU Cache
• How to master DSA

Python Code Snippets

Basic Data Structure

• Initialize a 2d matrix

  # Correct
  mat = [[0 for _ in range(cols)] for _ in range(rows)]
  mat = [[0] * cols for _ in range(rows)]
  # Wrong
  # mat = [[0] * cols] * rows 
  # mat = [[0 for _ in range(cols)]] * rows
  

• Copy a dictionary

   d1 = {1 : 2}
   d2 = dict(d1)
   d3 = d1.copy()
  

• Copy a List

  a1 = [1, 2, 3]
  # Three different ways to copy a list (Shallow)
  a2 = list(a1)
  a3 = a1.copy()
  a4 = a1[:]
  

• Copy a Set

   s1 = {1,2,3}
   s2 = set(s1)
   s3 = s1.copy()
  

• List and More about list

  >>> a = [1,2,3,4,5,6,7]
  >>> a[:3]
  [1, 2, 3]
  >>> a[3:]
  [4, 5, 6, 7]
  >>> a[:-3]
  [1, 2, 3, 4]
  >>> a[-3:]
  [5, 6, 7]
  >>> a[-3]
  5
  

• Sort a tuple list by sub-element

   >>> a = [(1,3),(2,2),(4,5),(6,0),(0,-1)]
   >>> print(sorted(a, key = lambda x: x[0]))
   [(0, -1), (1, 3), (2, 2), (4, 5), (6, 0)]
   >>> print(sorted(a, key = lambda x: x[1]))
   [(0, -1), (6, 0), (2, 2), (1, 3), (4, 5)]

• Get one item from set: set.pop() (Random/First element)
• Nonlocal vs global
• Nonlocal vs global 2
• Typing

Collections

• collections.defaultdict

  >>> s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
  >>> d = defaultdict(set)
  >>> for k, v in s:
  ...    d[k].add(v)
  ...
  >>> sorted(d.items())
  [('blue', {2, 4}), ('red', {1, 3})]
  

• collections.OrderedDict
• collections.ChainMap
• collections.Counter

   >>> c = Counter('gallahad')                 # a new counter from an iterable
   >>> c
   Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
   >>> c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
   >>> c
   Counter({'red': 4, 'blue': 2})
   >>> c = Counter(cats=4, dogs=8)             # a new counter from keyword args
   >>> c
   Counter({'dogs': 8, 'cats': 4})
  

• collections.deque
  • Used for [[Stack]] and [[Queue]]

  from collections import deque
  D = deque()
  D.append(1)
  D.appendleft(2)
  _ = D.pop()
  _ = D.popleft()
  print(D[0])
  print(D[-1])