Ziyuan Qin's blog

Python Notes

3/10/2020 tech

While studying for interview problems, I use Python3 as the PL and feel like concluding its commonly used features.

# Why Python

  • elegant and clear
  • high-readability

# Style Guide

Google Python Style Guide (opens new window)

# Pyenv

Intro to Pyenv (opens new window)

# Scopes

Python scopes (opens new window)

# Local, Global, Nonlocal

Python Local and Global Variables (opens new window)

# For, While Loops

# Do-While Loop

As Python does not have a do-while loop, here are some workarounds (opens new window).

# Int

The # bits of number n is log⁡n\log n.

# Modular Arithmatic

(n+m)kmodn=m(n+m)^k \mod n = m

# Bit Manipulation

n & (n-1) would eliminate the rightmost 1-bit.

# Overflow

Basically, Python doesn't need to worry about integer overflow.

Following are from EPI in Python (opens new window).

Integers:

Integers in Python3 are unbounded-the maximum integer representable is a function of the available memory. The constant sys.maxsize can be used to find the word-size; specifically, it's the maximum value integer that can be stored in the word, e.g., 2∗∗63−L2**63 - L on a 64-bit machine. Bounds on floats are specified in sys.float-info.

Float:

Unlike integers, floats are not infinite precision, and it's convenient to refer to infinity as float('inf ') and float('-inf '). These values are comparable to integers, and can be used to create pseudo max-int and pseudo min-int.

# bin

From https://docs.python.org/3/library/functions.html#bin:

bin

bin converts an integer number to a binary string prefixed with “0b”. [2:] takes away 0b and returns the binary int as a string.

If n is an integer, int(bin(n)[2:],2) would return the original n.

# Division

divmod

# Division Operators / and //

The division operators difference in Python 2 and 3 is described here (opens new window).

Python 2 uses / for floor division if both arguments(the dividend and divisor) are integers.

Python 2 uses // for floor division for both int and float arguments.

Python 3 uses / for floating point division for both int and float arguments.

Python 3 uses // for floor division for both int and float arguments.

So the behavior of “//” is same for Python 2 and 3.

Personally I like Python 3 for division behavior as it's clearer and causes less confusion.

# Data Structures

Sometimes it's not so obvious to see how to use a data structure in Python3.

# String (Immutable)

'' or ""

# f-string

From https://docs.python.org/3/reference/lexical_analysis.html#f-strings:

f-strings

For example: f'{6:08b}'.

Starting with f, represent int 6 in 8 binary digits with 0's padded at front. So the evaluated result is: '00000110'.

Equivalently, could do bin(6)[2:].zfill(8), where zfill added the 0's padded at front.

# HashSet

hashset = set()
hashset.add(1)
# OR
hashset = {1}
1
2
3
4

# HashMap

{} get(self, key, default=None) returns the value for key if key is in the dictionary, else default.

Dictionary associates values with immutable keys which means you cannot use lists as keys.

# Array

[]

# Matrix

[0]*2 [[0 for j in range(num_cols)] for i in range(num_rows)] Since i and j are not used, can simplify the above to: [[0 for _ in range(num_cols)] for _ in range(num_rows)]

# Stack

[] from collections import deque and initialize a stack as deque()

# Queue

More at Queue in Python (opens new window).

# Linked List

[]

# Reverse

def reverseList(self, head: ListNode) -> ListNode:
    last = None
    while head:
        # keep the next node
        tmp = head.next
        # reverse the link
        head.next = last
        # update the last node and the current node
        last = head
        head = tmp
1
2
3
4
5
6
7
8
9
10

# Shallow Flatten

We could have nested for loops

[val for sublist in list_of_lists for val in sublist]
1

Or use reduce from functools

from functools import reduce
reduce(lambda l1, l2: l1 + l2, list_of_lists)
# or
reduce(operator.concat, l)
1
2
3
4

Or use chain from itertools

from itertools import chain
list(chain(*list_of_lists))
1
2

There may be many other possible ways.

# Tuple (Immutable)

()

# List Cannot be Hashed

A list adding to a set would cause error "list objects are unhashable" b/c list is mutable but elements in set are not supposed to change after being added and hashed. Instead of list, I could add a tuple to the set, as described in this Stack Overflow answer (opens new window).

# defaultdict of defaultdict (opens new window)

defaultdict(lambda: defaultdict(int))
1

The argument of a defaultdict (in this case is lambda: defaultdict(int)) will be called when you try to access a key that doesn't exist. The return value of it will be set as the new value of this key, which means in our case the value of d[Key_doesnt_exist] will be defaultdict(int).

If you try to access a key from this last defaultdict i.e. d[Key_doesnt_exist][key_doesnt_exist] it will return 0, which is the return value of the argument of the last defaultdict i.e. int().

To iterate:

for _, courses in schedulesByPECourses.items():
    pe = []
    for _, sc in courses.items():
        pe.append(sc)
1
2
3
4

# Heap

Python implements heap in its internal library heapq. See more at doc (opens new window) and examples (opens new window).

# Algorithms

Prefix Sum can look for subarray sum O(1) every time 前缀和：多次查询区间和 O(1)/次

  • 前缀和是⼀种思想，可以⽤于许多的减少时间复杂度的地⽅
  • 我们不⼀定会使⽤前缀“和”，可能是其他⽐如积，最⼤值，最⼩值这样 的值。主要还是要根据题⽬来考虑使⽤什么。
  • 哈希表是⼀种⼯具，与前缀和配套使⽤可以达到“⽤空间换时间”的⽬ 的。

双指针：根据区间和调整区间 树状数组：单点修改，区间查询 线状树：区间修改

Two Pointers is used interchangbly w/ sliding window, as the way of thinking is more important than name and style.

95% of the time, summing over a window requires prefix sum. Exceptions: 线状树, 互动数组

Edge cases to watch for:

  1. 0, empty input of string/array/any ds
  2. TLE / infinite loop

csum means cumulative sum.

隐式图：没有明确的点和边的关系（不会定义 Node 等）

矩阵就是⼀种经典的隐式图问题

Graph Algorithms:

https://leetcode.com/discuss/general-discussion/971272/Python-Graph-Algorithms-One-Place-for-quick-revision