Data Structures

Dict

List

Custom classes

Counter: TODO

collections.counter

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        m = collections.defaultdict(int)
        lists = [A, B, C, D]

        def nSumCount() -> int:
            addToHash(0, 0)
            return countComplements(len(lists) // 2, 0)

        def addToHash(i: int, total: int) -> None:
            if i == len(lists) // 2:
                m[total] += 1
            else:
                for a in lists[i]:
                    addToHash(i + 1, total + a)

        def countComplements(i: int, complement: int) -> int:
            if i == len(lists):
                return m[complement]
            cnt = 0
            for a in lists[i]:
                cnt += countComplements(i + 1, complement - a)
            return cnt

        return nSumCount()

Stacks

• list
  • amortized O(1) for inserts and deletes

collections.deque

• double-ended queue
  • linked list

Adding: stack is the same as queue

>>> from collections import deque
>>> s = deque()
>>> s.append('eat')

>>> s.pop()
'eat'
>>> s.pop()
IndexError: "pop from an empty deque"

queue.LifoQueue

• multi-producers & multi-consumers from different threads
  • same process

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.get()
'eat'
>>> s.get_nowait()
queue.Empty
>>> s.get()
# Blocks / waits forever...

Queues

collections.deque

Adding: stack is the same as queue

>>> from collections import deque
>>> q = deque()
>>> q.append('eat')

>>> q.popleft()
'eat'
>>> q.popleft()
IndexError: "pop from an empty deque"

queue.Queue

• multi-producers & multi-consumers from different threads
  • same process

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')

>>> q.get()
'eat'
>>> q.get_nowait()
queue.Empty
>>> q.get()
# Blocks / waits forever...

multiprocessing.Queue

• similar to queue.Queue
• also handles different processes vs threads

Priority Queue

heapq

• binary heap

from heapq import heapq

pq = []

heappush(pq.(2, 'code'))

queue.PriorityQueue

• wrapper around heapq
• supports concurrency (locks, threads, ...)
• API is class based

from queue import PriorityQueue

q = PriorityQueue()
q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

---

Last update: 2023-04-24