I tend to learn by example but also forget language syntax and semantics if I don’t program using in that language for some time. So I’ve made it a habit to capture notes (mostly concepts and examples). These notes were initially based on: https://bugs.python.org/file47781/Tutorial_EDIT.pdf. But I’ve been adding more stuff recently as I learn more about Python.
A variable (with name) is a reference to an object in memory. So every variable is just a memory address to some object.
The actual object is the “value” of the variable. A type is associated with the object at run-time.
The compiler can optimize e.g. multiple variables can point to the same object in memory.
Python is not strongly typed.
One way to classify types is that they’re either mutable or immutable e.g. List is mutable but a String is not. Since objects are associated with types, python has mutable objects or immutable objects.
When you pass variables around through functions, you are not doing the traditional pass by value or pass by reference. Rather, you’re really just passing the object.
If you pass a mutable object e.g. a List, you’re essentially binding a new variable (reference) inside that function to that object. That means you can mutate it. Having said that, if you do var = something, that something would be a new object and won’t mutate the original object. Instead for things like List, use append for example.
For immutable objects, you are also doing the same, except when you try to mutate it, Python would create a new immutable object in memory, and bind the variable to that object. That means that even though it may seem that you’re changing the variable’s value inside the function, what you’re really doing is creating a new value object whose life cycle is the same as that of the function. So the variable outside the function, even after the function’s execution, would have the same old value (since it is bound to the same old immutable object).
More details about this are well described here: http://stupidpythonideas.blogspot.com/2013/11/does-python-pass-by-value-or-by.html
Let’s use an example to illustrate this:
# id uniquely identifies variable, "like" a memory address; hex(id) can give address based on interpreter
def memAddr(var):
return hex(id(var))
a1, a2, a3 = 1, 1, 2
b1, b2, b3 = "abc", "abc", "Abc"
c1, c2, c3 = ['1', '2'], ['1', '2'], ['2', '1']
# Immutable objects are optimized and share the same object
print(memAddr(a1), memAddr(a2), memAddr(a3))
print(memAddr(b1), memAddr(b2), memAddr(b3))
# Mutable objects generally assigned new object from get go
print(memAddr(c1), memAddr(c2), memAddr(c3))
def foo_immutable_str(var):
var = "abcd"
print(memAddr(var))
def foo_mutable_list(var):
var.append('3')
print(memAddr(var))
print(b1)
foo_immutable_str(b1)
print(b1)
print(c1)
foo_mutable_list(c1)
print(c1)('0x7ff1e7d05718', '0x7ff1e7d05718', '0x7ff1e7d05700')
('0x106519dc8', '0x106519dc8', '0x106519e18')
('0x1064b2f38', '0x1064d8098', '0x1064e8170')
abc
0x1064e5ed0
abc
['1', '2']
0x1064b2f38
['1', '2', '3']
Quoting from Chapter 9.1 from the Python notes link at the top.
“Objects have individuality, and multiple names (in multiple scopes) can be bound to the same object. This is known as aliasing in other languages. This is usually not appreciated on a first glance at Python, and can be safely ignored when dealing with immutable basic types (numbers, strings, tuples). However, aliasing has a possibly surprising effect on the semantics of Python code involving mutable objects such as lists, dictionaries, and most other types. This is usually used to the benefit of the program, since aliases behave like pointers in some respects. For example, passing an object is cheap since only a pointer is passed by the implementation; and if a function modifies an object passed as an argument, the caller will see the change — this eliminates the need for two different argument passing mechanisms as in Pascal.”
To learn more about importing objects (classes, functions) from modules, read this.
As with any mainstream language, Python has a lot of types.
To categorize, they can be broken into primitive or built-in types and user-defined types (classes, enums).
There are also container types (made up of primitive types). Typically, these types have some specific properties that make them special. Containers types can be broken down into ordered sequence types (list, tuple, etc.) and key/association types (set, dict).
Details of Pyhon3 types can be found here: https://docs.python.org/3/library/stdtypes.html
High level list can be found here: https://docs.python.org/2/library/types.html
Let’s cover primitive types first:
a, b, c, d, e, f = 12, int(12), -12, 12.456, float(12.456), 1 * 10**9
print(a, b, c, d, e, f)
# Note that d (1 billion) is also an int
# Python 3 made every number int: https://stackoverflow.com/questions/2104884/how-does-python-manage-int-and-long
# Also see this: https://stackoverflow.com/a/52176129/10992281
print(type(a), type(b), type(c), type(d), type(e), type(f))
g, h, i = "abc", 'abc', str("abc")
print(g, h, i)
print(type(g), type(h), type(i))
j, k = True, bool(False)
print(j, k)
print(type(j), type(k))
l = bytes(123)
print(l)(12, 12, -12, 12.456, 12.456, 1000000000)
(<type 'int'>, <type 'int'>, <type 'int'>, <type 'float'>, <type 'float'>, <type 'int'>)
('abc', 'abc', 'abc')
(<type 'str'>, <type 'str'>, <type 'str'>)
(True, False)
(<type 'bool'>, <type 'bool'>)
123
There are also binary types such as bytes, bytearray, memoryview. Read about these here: https://www.w3resource.com/python/python-bytes.php
Now let’s see some container types:
a, b = [1, 2, 3], list([1, 2, 3])
print(a, b)
print(type(a),type(b))
c, d, d1 = (), (1, "2", 3.4), tuple((1, "2", 3.4))
print(c, d, d1)
print(type(c), type(d), type(d1))
e, f = set({1, 2, 3}), {1, 2, 3} # note {} is dict so empty set must be created using set()
print(e, f)
print(type(e), type(f))
g, h = {}, {"a": 2, "b": 6} # dict() usage was complicated for me
print(g, h)
print(type(g), type(h))
i = None # similar to nullptr in C++ and null in Java
print(i)
print(type(i))([1, 2, 3], [1, 2, 3])
(<type 'list'>, <type 'list'>)
((), (1, '2', 3.4), (1, '2', 3.4))
(<type 'tuple'>, <type 'tuple'>, <type 'tuple'>)
(set([1, 2, 3]), set([1, 2, 3]))
(<type 'set'>, <type 'set'>)
({}, {'a': 2, 'b': 6})
(<type 'dict'>, <type 'dict'>)
None
<type 'NoneType'>
If statements:
x = 12
if x < 0:
print("blah")
elif x > 0:
print("something")
else:
print("x is zero")something
For statements:
a = range(0, 10) # list in python2, iterator in python3
print(a)
print(list(a))
b = range(0, 10, 2)
print(list(b))
c = range(10, 0, -1)
print(list(c))
for i in range(0, 10):
print(i, end=" ") # end only supported in python3range(0, 10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 2, 4, 6, 8] [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 0 1 2 3 4 5 6 7 8 9
While statements:
i = 0
while i < 5:
print(i)
i += 10 1 2 3 4
Apart from range, things like list, sets, and dict (keys) are also iterables.
“break” and “continue” work similar to C/C++/Java.
There’s also “pass” which can be used to do nothing.
See this: https://www.w3schools.com/python/python_operators.asp
Function definition is simple:
def sum(a, b):
return a + b
print(sum(2, 3))
# functions are objects
f = sum
print(f(5, 7))5 12
Functions can have optional arguments:
def printer(a, b = "b", c = "c"):
print(a, b, c)
printer("a")
printer("a", "e")
printer("a", "f", "g")('a', 'b', 'c')
('a', 'e', 'c')
('a', 'f', 'g')
Note that optional arguments must come at the end, otherwise there’s no good syntax to call the function, so the compiler would complain.
Functions can also have named arguments (example taken from python notes link at the top):
def parrot(voltage, state='a stiff', action='voom', type='Norwegian Blue'):
print("-- This parrot wouldn't", action)
print("if you put", voltage, "volts through it.")
print("-- Lovely plumage, the", type)
print("-- It's", state, "!")
parrot(1000) # 1 positional argument
parrot(voltage=1000 ) # 1 keyword argument
parrot(voltage=1000000, action='VOOOOOM') # 2 keyword arguments
parrot(action='VOOOOOM', voltage=1000000) # 2 keyword arguments
parrot('a million', 'bereft of life', 'jump') # 3 positional arguments
parrot('a thousand', state='pushing up the daisies') # 1 positional, 1 keyword("-- This parrot wouldn't", 'voom')
('if you put', 1000, 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'a stiff', '!')
("-- This parrot wouldn't", 'voom')
('if you put', 1000, 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'a stiff', '!')
("-- This parrot wouldn't", 'VOOOOOM')
('if you put', 1000000, 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'a stiff', '!')
("-- This parrot wouldn't", 'VOOOOOM')
('if you put', 1000000, 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'a stiff', '!')
("-- This parrot wouldn't", 'jump')
('if you put', 'a million', 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'bereft of life', '!')
("-- This parrot wouldn't", 'voom')
('if you put', 'a thousand', 'volts through it.')
('-- Lovely plumage, the', 'Norwegian Blue')
("-- It's", 'pushing up the daisies', '!')
Using keyword arguments, you can have optional arguments out of order. (Self note: Have to confirm this and optional argument text above).
There are also lambda or anonymous functions, useful when functions are used for a one time use-case e.g. as a sort functor in the sort() function. Example:
def get_incrementor(n):
return lambda x : x + n
f = get_incrementor(42)
print(f(3))45
Sort example:
A = [10, 4, -12, 25, 19]
print(A)
# sorted returns a list; if you want a string, do: "".join(sorted(s)) where s is the string to be sorted
print(sorted(A, key = lambda listElement : listElement * -1)) # sorted is out of place
# A.sort will be in-place
A.sort(key = lambda listElement : listElement * -1)
print(A)[10, 4, -12, 25, 19] [25, 19, 10, 4, -12] [25, 19, 10, 4, -12]
Strings in Python can be enclosed in either double quotes (“”) or single quotes (”). \ is used to escape if needed.
Strings are immutable objects.
Here’s an example on how to create/read strings, and perform common operations on them.
s = "Hey there!"
print(s)
print(s[0:3]) # mathematically picks s[i:j). Python calls this slice. It's basically a substring.
print(s[0:3] + ", " + s[4:len(s)]) # concatenation
print(s[:3] + ", " + s[4:]) # 0 and len(s) indices can be skipped
print("abc" " def") # another way to concat is to just place the strings together
print(s[-1]) # negative indices wrap around the end
print(s[-6:]) # negative indices can be used as an offset from the end
print(len(s)) # length
print(s.lower(), s.upper(), s.islower(), s.isupper())
print(s[len(s):0:-1], s[len(s)::-1], s[::-1], s[ : : -1]) # attempt to reverse
print(s[0:len(s):2]) # slices can be made with any increment, positive or negative (see reverse above)
print("<>".join(s)) # join goes through the "iterable", and puts a string after every iterator element
# for string input, iterable element are characters, but we can also use join on things like tuples
# join's input is an iterable but output is always a string
print("".join(reversed(s)), ''.join(reversed(s))) # another way to reverseHey there!
Hey
Hey, there!
Hey, there!
abc def
!
there!
10
('hey there!', 'HEY THERE!', False, False)
('!ereht ye', '!ereht yeH', '!ereht yeH', '!ereht yeH')
Hytee
H<>e<>y<> <>t<>h<>e<>r<>e<>!
('!ereht yeH', '!ereht yeH')
Lists are like arrays in other lanaguges: a sequence of objects of a type. Except in Python, elements of a list can have different types, although I’ve seen that rare in practice.
List operations are similar to string operations. Lists are mutable though.
Let’s see some examples:
l = ["a", "b", "c", "d", "e", "f", "g"]
print(l, len(l))
print(l[0], l[-1]) # indices
print(l[0:2], l[:3], l[-3:]) # slices
print(l + ["h", "i"], ["h", "i"] + l) # concatentation
# Writing to list
l[0] = "A"
l[-3:] = ["E", "F", "G"]
print(l)
# Removing from list
l[1:3] = []
print(l)
# Append to list
l.append("NEW1")
print(l)
l[len(l):] = ["NEW2"] # Another way to append
print(l)
# Reverse a list
lR = reversed(l) # returned reversed obect; use list() to create list
# use l.reverse() to reverse in place
print(list(lR))
# Copying
l2 = l[:]
l2.append("NEW3")
print(l, l2)
# Removing last element in list using pop() method
# Only last element removal is O(1); others are O(n)
l2.pop(len(l2) - 1)
print(l2)(['a', 'b', 'c', 'd', 'e', 'f', 'g'], 7)
('a', 'g')
(['a', 'b'], ['a', 'b', 'c'], ['e', 'f', 'g'])
(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'], ['h', 'i', 'a', 'b', 'c', 'd', 'e', 'f', 'g'])
['A', 'b', 'c', 'd', 'E', 'F', 'G']
['A', 'd', 'E', 'F', 'G']
['A', 'd', 'E', 'F', 'G', 'NEW1']
['A', 'd', 'E', 'F', 'G', 'NEW1', 'NEW2']
['NEW2', 'NEW1', 'G', 'F', 'E', 'd', 'A']
(['A', 'd', 'E', 'F', 'G', 'NEW1', 'NEW2'], ['A', 'd', 'E', 'F', 'G', 'NEW1', 'NEW2', 'NEW3'])
['A', 'd', 'E', 'F', 'G', 'NEW1', 'NEW2']
Lists can be used as stack:
stack = [1, 2, 3]
print(stack)
stack.append(4)
print(stack)
stack.pop()
print(stack)[1, 2, 3] [1, 2, 3, 4] [1, 2, 3]
For queues, use deque:
from collections import deque
l = [1, 2, 3]
queue = deque(l)
print(queue)
queue.append(4) # push to right (end/back of queue). O(1).
print(queue)
queue.popleft() # pop from left (start/front of queue). O(1).
print(queue)
# There are also these operations that deque provides:
# queue.appendleft(x) # push to left (start/front of queue). O(1).
# queue.pop() # pop from right (end/back of queue). O(1)deque([1, 2, 3]) deque([1, 2, 3, 4]) deque([2, 3, 4])
List comprehensions provide an easy way to create new lists:
squares = [x**2 for x in range(10)]
print(squares)
l1 = [(x,y) for x in [1,2,3] for y in [3,1,4] if x != y] # with tuples and conditions!
print(l1)[0, 1, 4, 9, 16, 25, 36, 49, 64, 81] [(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]
Lists can be joined:
a = [1,2,3]
b = [4,5,6,7,8]
c = a + b
print(c)[1, 2, 3, 4, 5, 6, 7, 8]
A tuple consists of a number of values of different types. Pairs are a special case of tuples (size = 2).
Tuples are immutable.
Tuples can be used in all interesting ways:
p = ("foo", 99) # packing/creating a tuple
print(p[0], p[1])
p1, p2 = p # unpacking into separate variables
print(p1, p2)
print(len(p)) # length('foo', 99)
('foo', 99)
2
Comphrensions are sometimes useful to form new tuples:
s = "ABC"
t = tuple(c for c in s)
print(t)('A', 'B', 'C')
Sets are like hash sets in other languages. Items are guarenteed to be unique. They are not ordered when you iterate. You can add new items and remove existing items. Everything is “key” based. “key” for sets are just its elements. Insertion and deletion are O(1).
s = {"apple", "orange", "mango"}
print(s, len(s))
# existence
print("apple" in s)
# insert
s.add("grapes")
print(s)
# remove
s.remove("apple")
print(s)
# Get and remove random element from set
r = s.pop()
print(r)
# union, intersection, difference
s2 = {"berries", "mango"}
print(s, s2)
print(s | s2) # union
print(s & s2) # intersection
print(s - s2) # difference
print(s2 - s) # difference
# set comprehensions (similar to list comprehensions)
s3 = {x for x in "abracadabra" if x not in "abc"}
print(s3)(set(['orange', 'mango', 'apple']), 3) True set(['orange', 'mango', 'apple', 'grapes']) set(['orange', 'mango', 'grapes']) orange (set(['mango', 'grapes']), set(['berries', 'mango'])) set(['mango', 'grapes', 'berries']) set(['mango']) set(['grapes']) set(['berries']) set(['r', 'd'])
Dictionaries in Python are hash maps. Basically they are key-value pairs, where keys are unique.
Inserts are O(1) and so are deletes, both key based. Looping doesn’t guarantee order of k-v pairs.
M = {"harry": 3, "paymaan": 12, "rick": 99}
print(M)
# inserts/updates
M["morty"] = 13
print(M)
M["harry"] = 4
print(M)
# deletes
del M["rick"]
print(M)
# iterating
# keys
for k in M:
print(k)
# values
for v in M.values():
print(v)
# k,v tuples/pairs
for k, v in M.items():
print(k, v){'paymaan': 12, 'rick': 99, 'harry': 3}
{'paymaan': 12, 'rick': 99, 'morty': 13, 'harry': 3}
{'paymaan': 12, 'rick': 99, 'morty': 13, 'harry': 4}
{'paymaan': 12, 'morty': 13, 'harry': 4}
paymaan
morty
harry
12
13
4
('paymaan', 12)
('morty', 13)
('harry', 4)
tldr: heapq
This is one way to implement a priority queue.
See these links for details:
- https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate
- https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python
- https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/
Code example. Uses maxHeap. heapq defaults to min, for max just multiply key by -1.
# https://leetcode.com/problems/k-closest-points-to-origin/
import heapq
class Solution(object):
def kClosest(self, points, K):
"""
:type points: List[List[int]]
:type K: int
:rtype: List[List[int]]
"""
maxHeap = []
# heapq.heapify(maxHeap) # not needed since maxHeap already empty
for i in range(len(points)):
point = points[i]
d = point[1] ** 2 + point[0] ** 2
heapq.heappush(maxHeap, (-1 * d, i))
if len(maxHeap) > K:
heapq.heappop(maxHeap)
return [points[e[1]] for e in maxHeap]Note that if you just want the min/max value w/o pop, use heap[0]. For max heap though, you will have to multiply by -1 again to get the max value.
There’s a caveat here. Internally, heappush will use the comparison operator < on the first item in the provided tuple. But what if two tuples have the same first item? Since heappush uses < and not <=, this mean we’ll have to somehow define == or tie breaker behavior. In this case, heappush goes to the next items in the two tuples, and keeps on going until it finds items not equal to each other. If it can’t find one, it’ll error. Or in other cases, it may reach an item in the tuple for which < is not defined, in which case it’ll error as well.
So how do we fix this? One way is that for the first item in the tuple, implement < using __lt__(self, other). This can work for custom data types (or classes) that you have, but won’t work easily for primitive types such as ints.
Another option is that we always add a second item in the tuple which is guarenteed to be unique. An example is a counter. So in this case, if the tie breaker happens, heappop will return the item that was pushed first (since that’ll have a lower counter value).
For more details, read this: https://docs.python.org/3/library/heapq.html#priority-queue-implementation-notes
Here’s the code:
import heapq
import itertools
class Node:
def __init__(self, val=-1, next=None):
self.val = val
self.next = next
nodes = [Node(1), Node(1), Node(2), Node(3), Node(3)]
minHeap = []
counter = itertools.count()
for node in nodes:
heapq.heappush(minHeap, (node.val, next(counter), node))
while len(minHeap) > 0:
minNode = heapq.heappop(minHeap)[2]
print(minNode.val)1 1 2 3 3
There’s a limitation here though. next(counter) returns an int, so when we run out of ints, we may still see duplicates, and heappush will complain. :)
List, deque, set, dictionary: https://wiki.python.org/moin/TimeComplexity
String: https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python
Read chapter 9 on the Python notes (link at the top) for details.
Here, I’ll give examples to illustrate common class features.
The example below describes constructor, static methods and variables, inheritance, instance methods and variables, method overriding.
class Animal:
# num_animals = 0 # STATIC variable can not be immutable
animal_map = dict() # STATIC mutable variable
def __init__(self, name): # All instance methods have self arg
print("In Animal class constructor")
self.name = name # All variables (instance + static) are referred via self
if name in self.animal_map:
self.animal_map[name] += 1 # STATIC variables still referred by self
else:
self.animal_map[name] = 1
def print_info(self):
print("Name: " + self.name)
print(self.animal_map)
@staticmethod
def print_general(): # static method w/o self
print("This is an Animal class")
class Dog(Animal):
def __init__(self, name):
print("In Dog class constructor")
super().__init__(name)
x = Animal("dog")
x.print_info()
x.print_general()
y = Animal("cat")
y.print_info()
y.print_general()
z = Dog("dog")
z.print_info()
z.print_general()In Animal class constructor
Name: dog
{'dog': 1}
This is an Animal class
True
False
In Animal class constructor
Name: cat
{'dog': 1, 'cat': 1}
This is an Animal class
True
False
In Dog class constructor
In Animal class constructor
Name: dog
{'dog': 2, 'cat': 1}
This is an Animal class
True
True
A good read about Python’s collection module: https://victorzhou.com/posts/python-collections-module/
Some useful examples based on above:
from collections import namedtuple
myCustomTupleClass = namedtuple('FooCustomTuple', 'id f1 f2')
a = myCustomTupleClass(id=12, f1='Field1', f2=[1,2,3]) # tuples are immutable but have non homogeneous types
print(a)
print(a.id, a.f1, a.f2)
print(a[0], a[1], a[2])
# a.id = 99 # can't do since tuples are immutableFooCustomTuple(id=12, f1='Field1', f2=[1, 2, 3]) (12, 'Field1', [1, 2, 3]) (12, 'Field1', [1, 2, 3])
Curated list of tricks I’ve seen in Python.
Repeat list element N times e.g. create a list of 10 0’s. The * operator on list does exactly that.
a = [0] * 10
print(a)
b = [1,2,3] * 3
print(b)
# also works on strings (string ~ list of chars)
c = "a" * 3
print(c)[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 2, 3, 1, 2, 3, 1, 2, 3] aaa
Reverse a list:
a = [1,2,3,4,5]
revA = a[::-1] # equivalent to a[len(a) - 1::-1]
print(revA)[5, 4, 3, 2, 1]
Range based for loops:
fruits = {"apple", "mango", "pear", "banana"}
for fruit in fruits:
print(fruit)mango pear apple banana
Multiple assignments:
a = b = c = -99
print(a,b,c)
d, e, f = 5, 6, 7
print(d,e,f)
g,h,i = [0]*5, [-1]*5, "a" * 5
print(g,h,i)(-99, -99, -99) (5, 6, 7) ([0, 0, 0, 0, 0], [-1, -1, -1, -1, -1], 'aaaaa')
Quick swap:
a,b = 10, 20
print(a,b)
a,b = b,a
print(a,b)(10, 20) (20, 10)
If else one liner:
f = "mango"
print("fruit" if f is "mango" else "not a fruit")
g = "mango2"
print("fruit" if g is "mango" else "not a fruit")fruit not a fruit
Chaining operators:
a, b, c = 2, 2, 2
d, e, f = 10, 20, 30
print(a, b, c)
print(a == b == c)
print(a == b == d)
print(d < e < f)
print(e < d < f)(2, 2, 2) True False True False
Enumerate() function lets you iterate an iteratable/sequence (think lists, sets, dictionaries, etc.) while maintaining a counter.
l = ["apple", "banana", "mango", "berry"]
s = {"apple", "banana", "mango", "berry"}
print(l)
print(s)
for counter, value in enumerate(l):
print(counter, value)
print("\n")
for counter, value in enumerate(l, 1):
print(counter, value)
print("\n")
for counter, value in enumerate(s):
print(counter, value)
print("\n")
counter_list = list(enumerate(l, 1))
print(counter_list) ['apple', 'banana', 'mango', 'berry'] set(['berry', 'mango', 'apple', 'banana']) (0, 'apple') (1, 'banana') (2, 'mango') (3, 'berry') (1, 'apple') (2, 'banana') (3, 'mango') (4, 'berry') (0, 'berry') (1, 'mango') (2, 'apple') (3, 'banana') [(1, 'apple'), (2, 'banana'), (3, 'mango'), (4, 'berry')]
Enumerate also comes in handy when dealing with strings:
s = "abcdef"
for i,c in enumerate(s):
print(i,c)(0, 'a') (1, 'b') (2, 'c') (3, 'd') (4, 'e') (5, 'f')
Deep and shallow copies: For Immutable types (literal numeric types, string, etc.), it does not matter since you can’t change the value anyway. For mutable types (lists, sets, dictionaries), it does matter because just a = b will do a shallow copy.
s = {1, 2, 3}
c1 = s
c2 = s.copy() # deep copy
print(s, c1, c2)
c1.remove(1)
print(s, c1, c2)(set([1, 2, 3]), set([1, 2, 3]), set([1, 2, 3])) (set([2, 3]), set([2, 3]), set([1, 2, 3]))
Swap two indices in a string:
s = "ABCDEF"
def swapStrIndices(s, i, j):
sL = list(s)
sL[i], sL[j] = sL[j], sL[i]
return "".join(sL)
print(swapStrIndices(s, 1, 4))AECDBF
Counter:
Counter is part of the collections module.
from collections import Counter
list = ["A", "A", "B", "C", "B", "A"]
listCount = Counter(list)
print(listCount)
print(type(listCount.items()))
# you can loop through elements and their count
for e, count in listCount.items():
print(e, count)Counter({'A': 3, 'B': 2, 'C': 1})
<type 'list'>
('A', 3)
('C', 1)
('B', 2)
Zip:
a = [1, 2, 3]
b = [4, 5, 6]
c = zip(a, b)
print(a)
print(b)
print(c)
print(type(a), type(b), type(c))[1, 2, 3] [4, 5, 6] [(1, 4), (2, 5), (3, 6)] (<type 'list'>, <type 'list'>, <type 'list'>)
For loop with two index variables:
A = [1, 2, 3, 4, 5]
# i = start pointer moving right , j = end pointer moving left
for i, j in zip(range(len(A)), range(len(A) - 1, -1, -1)):
print(A[i], A[j])(1, 5) (2, 4) (3, 3) (4, 2) (5, 1)
Randomness:
See the “random” module: https://docs.python.org/3/library/random.html
Some examples:
import random
print(random.random()) # uniform floating number between [0.0, 1.0)
A = [1, 2, 3, 4, 5]
print(random.choice(A)) # uniformly choose a random element from any sequence e.g. list
randIdx = random.randint(0, len(A) - 1) # uniformly pick a number between [a,b] where a,b are randint args
print("randIdx: ", randIdx)
print(A[randIdx])0.356216386975
3
('randIdx: ', 4)
5
String utilities:
s1 = "AbCd7"
s2 = "A bCd7"
print(s1.lower())
print(s1.isalnum())
print(s2.isalnum())abcd7 True False
Type casts:
num = 123
numStr = str(num)
print(type(numStr), numStr)
for c in numStr:
print(c)
str = "789"
strNum = int(str)
print(type(strNum), strNum)(<type 'str'>, '123') 1 2 3 (<type 'int'>, 789)
Dictionary comprehensions:
In addition to list comprehensions and set comprehensions, Python also has dictionary comprehensions. So you can have one-liners for creating dictionaries. For example, to create a reverse index map from a string character to the index, one can do:
s = "ABCDE"
revIdx = {c:i for i, c in enumerate(s)}
print(revIdx){'A': 0, 'C': 2, 'B': 1, 'E': 4, 'D': 3}
Infinity:
A lot of times in problems, you need to set the initial value of a variable as inf or -inf, so that the variable gets set inside the loop later on. Typically, I can set the initial value as None and then have some special logic around that when trying to set the variable. That’s hacky though, so it’d be nice to have first class (or in-built) inf/-inf support.
Python’s math module has this “inf” concept:
import math
i = math.inf
j = -math.inf
print(i, j)
print(99999 < i)
print(-999999 > j)inf -inf True True
Custom comparators in sort:
Typically, in Python 3, you sort a list like so:
# In this example, we sort such that even numbers come first
A = [9, 8, 2, 5, 4, 12, 33, 45]
# The key we pass is a lambda. The value it return will determine the ordering.
# A lower value for an element means it will be first in the sorted array.
# So we output -1 for even numbers; that way they're adding first.
# even criteria: LSB is 0 (e & 1 == 0) or equivalently e % 2 == 0
A.sort(key = lambda e : -1 if e & 1 == 0 else 1)
print(A)[8, 2, 4, 12, 9, 5, 33, 45]
This is great. By default, we’ll sort in ascending order. For desecending order, one can write a lambda that flips that sign of the number.
However, one limitation is that we can’t have any complexity in our sort. Typically, when you sort, you are given two elements, and you decide which comes first. If you need that level of customization, you can write a custom comparator (similar to lambda) and use the cmp_to_key function. Here’s an example:
from functools import cmp_to_key
A = [3, 34, 32]
# Sort by string concat (+). If c1+c2 > c2+c1, pick c1 first. And vice versa.
B = sorted(A, key = cmp_to_key(cmp))
print(B)
# -1 -> x1 will come before x2
# +1 -> x2 will come before x1
# 0 -> does not matter
def cmp(x1, x2):
c1, c2 = str(x1) + str(x2), str(x2) + str(x1)
diff = int(c1) - int(c2)
if diff > 0: # c1 > c2
return -1
elif diff < 0: # c2 > c1
return 1
else: # c1 == c2
return 0
[34, 3, 32]
Bisect:
How to add an element in an array such that array is sorted, and also search in O(logN) time?
One way you can think is a heap, although the ordering there is not total because we can only get min/max, not the whole sorted sequence. That won’t work.
Another way would be to implement BST insert/search. That provides total ordering. That’s because an inorder traversal of the BST would give the sorted array. We can also use BST to do range searches efficently.
Implementing BST can be non-trivial, especially if there are balancing requirements (in which case you need something like AVL or red-black trees).
Python provides an easy way to do this using the bisect package.
Here’s how it works:
# The bisect module implements an algorithm for inserting elements into a list while maintaining
# the list in sorted order. This can be much more efficient than repeatedly sorting a list, or
# explicitly sorting a large list after it is constructed. (source: https://pymotw.com/2/bisect/.)
import bisect
itemsToInsert = [-34, -100, -100, -89, 23, -150, -54]
print("itemsToInsert: " + str(itemsToInsert))
sortedList = []
print("sortedList: " + str(sortedList))
# Insertion as we go. O(N) insertion time for every insert.
for item in itemsToInsert:
bisect.insort(sortedList, item) # insert into A s.t. A remains sorted overall. O(N) insertion time because insertion into list dominates search time.
print("sortedList: " + str(sortedList)) # print after insertion
# Let's search for insertion point AFTER -100. This would be O(logN) time.
insertionIdxAfter = bisect.bisect_right(sortedList, -100, 0, len(sortedList) - 1) # bisect.bisect(..) defaults to _right
print("insertionIdx for adding after -100: " + str(insertionIdxAfter))
# Now we can insert at that position. Or we could've called bisect.insort directly which does search + insert in one go.
# We can also search for insertion position BEFORE -100. This is again a O(logN) time operation.
insertionIdxBefore = bisect.bisect_left(sortedList, -100, 0, len(sortedList) - 1) # bisect.bisect(..) defaults to _right
print("insertionIdx for adding before -100: " + str(insertionIdxBefore))itemsToInsert: [-34, -100, -100, -89, 23, -150, -54] sortedList: [] sortedList: [-34] sortedList: [-100, -34] sortedList: [-100, -100, -34] sortedList: [-100, -100, -89, -34] sortedList: [-100, -100, -89, -34, 23] sortedList: [-150, -100, -100, -89, -34, 23] sortedList: [-150, -100, -100, -89, -54, -34, 23] insertionIdx for adding after -100: 3 insertionIdx for adding before -100: 1
Note that this is good for search but insertions O(N), not O(logN). Why? Because internally things are stored as a list, so adding in the middle requires reshuffling memory. This is where a BST implementation would be better. That would provide O(logN) insertion and at the same time, search will still be O(logN) as we have over here.