List in Python is a Dynamic Array (Array list), string is a list of chars, and recursive (char is also str)
Bytes
Bytes, byte array - used to store values in range(0, 256), byte array is mutable array, bytes is immutable array
Tuple
‣
collections.namedtuple → immutable class
It solves 2 problems:
In tuple you can access element only by index, but in Namedtuple not only
Ensuring the structure over the data, two tuples will be exactly the same if they are namedtuples
from collections import namedtuple
Car = namedtuple('Car', ['color', 'millage'])
my_car = Car('red', 3453.5)
# You can even create the methods
class MyOwnClass(Car):
def test_method(self):
pass
c = MyOwnClass('red', 3453.5)
# We can use _fields to extend old namedtuple to new one
ElectroCar = namedtuple('ElectroCar', Car._fields + ('new_prop',))
_asdict() - to convert to dict
_replace() - to make a shallow copy and edit arguments
_make() - create namedtuple object from iterable (list for example)
‣
typing.NamedTuple – Improved namedtuples with type annotations
The main difference being an updated syntax for defining new record types and added support for type hints
type annotations are not enforced without a separate type-checking tool like mypy
collections.Counter – Multi-sets, counts how many time element occurred
# How to use defaultdict as Counter
counts = defaultdict(int)
result = []
for word in words:
counts[word] += 1
# And how defaultdict can be replaced
s1_counter = {}
for character in s1:
s1_counter[character] = s1_counter.get(character, 0) + 1
deque (queue, stack)
Stack - LIFO, Push / Pop (End of list)
list O(1)
collections.deque → append, pop → O(1)
queue.LifoQueue → put, get (for multiprocessing)
Queue - FIFO, on queue we add to end, delete from start
list is bad cuz it will take O(n) for pop(0)
collections.deque → append, popleft → O(1)
queue.Queue → put, get
multiprocessing.Queue– Shared Job Queues (cuz of GIL)
Complexity table
Index access of deque is O(N). WHY? Unlike Python's standard list (which uses a single contiguous block of memory and supports true O(1) random access), collections.deque is implemented as a doubly-linked list of blocks (fixed-size memory chunks, typically 64 elements each)
heapq (priority queue, min heap by default)
Keeps list sorted with O(logN), we can use list, BUT it will take O(N*logN) because of insertion and sorting
heapq.heapify(list) # O(n), in-place operation, min heap by default
heapq.heappush(heap, item) # O(logn), push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap) # O(logn)
heapq.nlargest(n, iterable, key=None) # O(K * log(K)) to find the kth largest element
heapq.nsmallest(n, iterable, key=None)
# Max heap
from heapq import *
h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg) # heapify
heappush(h_neg, -2) # push
print(-heappop(h_neg)) # pop
# 9
# How heapsort works with heapq module
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) # 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
# However, if you would like to convert an existing array / list to a heap, then use the heapify method
import heapq
heap = [i for i in range(1, 100)] # Imagine it is an existing array
heapq.heapify(heap)
print(heap[0])
class MaxHeap:
def __init__(self, data: List[int]):
self.data = [-num for num in data]
heapq.heapify(self.data)
def push(self, item: int):
heapq.heappush(self.data, -item)
def pop(self) -> int:
return -heapq.heappop(self.data)
def __len__(self) -> int:
return len(self.data)
def __bool__(self) -> bool:
return len(self) != 0
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
heap = MaxHeap(stones)
while len(heap) > 1:
first, second = heap.pop(), heap.pop()
if first != second:
heap.push(abs(first - second))
return heap.pop() if heap else 0
heap vs list
Operation
Standard list
heapq
Access Minimum (heap[0])
O(N) (un-sorted)
O(1) (sorted)
O(1)
Insert New Element
O(1) append()
O(log N)heappush()
Remove Minimum
O(N) pop(0)
O(log N)heappop()
Random Index Access (arr[i])
O(1)
O(1) (Returns arbitrary tree node, not i-th smallest)
Search by Value (x in arr)
O(N)
O(N)
Full Sort
O(N logN) sort()
O(N log N) [heappop() for _ in range(N)]
What is the advantage of heap?
The primary advantage of a heap over a sorted list is efficiency when handling dynamic data.
If you have a continuously changing collection of data where you constantly need to add new items and pull the smallest (or largest) item, a heap allows you to do both in O(log N) time—whereas keeping a list fully sorted costs O(N) time per insertion.
from typing import NamedTuple
class Car(NamedTuple):
color: str
mileage: float
automatic: bool
>>> car1 = Car('red', 3812.4, True)
# Instances have a nice repr:
>>> car1
Car(color='red', mileage=3812.4, automatic=True)
# Accessing fields:
>>> car1.mileage
3812.4
# Fields are immutable:
>>> car1.mileage = 12
AttributeError: "can't set attribute"
>>> car1.windshield = 'broken' AttributeError:
"'Car' object has no attribute 'windshield'"
# Type annotations are not enforced without
# a separate type checking tool like mypy:
>>> Car('red', 'NOT_A_FLOAT', 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)
portfolio = [
('GOOG', 100, 490.1),
('IBM', 50, 91.1),
('CAT', 150, 83.44),
('IBM', 100, 45.23),
('GOOG', 75, 572.45),
('AA', 50, 23.15)
]
from collections import defaultdict
holdings = defaultdict(list)
for name, shares, price in portfolio:
holdings[name].append((shares, price))
holdings['IBM'] # [ (50, 91.1)]
"""
s1_counter = {}
for character in s1:
s1_counter[character] = s1_counter.get(character, 0) + 1
"""
from collections import defaultdict
def example_with_list():
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = defaultdict(list)
for k, v in s:
d[k].append(v)
print(d.items())
def example_with_int():
"""Counter"""
s = 'mississippi'
d = defaultdict(int)
for k in s:
d[k] += 1
print(d.items())
def example_with_set():
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)
print(d.items())
# if you would like to keep the heap property of your data structure when adding new elements, then heappush is a way to go
import heapq
q = []
heapq.heappush(q, (2, 'code')) # no need to use heapfiy, because heappush maintains the structure of heap
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))
while q:
next_item = heapq.heappop(q)
print(next_item)
# Result:
# (1, 'eat')
# (2, 'code')
# (3, 'sleep')
