Python Flashcards
Example O(log n)
Binary search
Example O(n)
- Simple search
Example O(n * log n)
quicksort (fast)
Example O(n2)
- selection sort (slow)
actually O(n × 1/2 × n) list get's smaller each time you find an element
O(n!)
traveling salesperson
Explain O(n)
Big O and n = number of operations
time factor would be c*O(n)
Average cost for execution
binary search algo
- sorted list (!)
- calc mid point
- == return pos
- list[mid]> item -> high=mid-1
- list[mid]< item -> low=mid+1
def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
delta=(high-low)//2
mid = low+delta
if list[mid] == item:
return mid
if list[mid] > item:
high = mid - 1
else:
low = mid + 1
return low
log 8
3: 23
log 1,024
10: 210
log 256
- 8: 28
Big O of reading array
O(1)
a[5]
Big O of reading linked list
O(n)
Big O of inserting array
O(n)
array with 4 elements and you add another requires new array and moving elements over
Big O of inserting linked list
O(1)
Minimal implementation of linked list
class Node: def \_\_init\_\_(self, **val=None**): self.val = val # the value self.next = None # reference to next node
find smallest element in array
def findSmallestIndex(arr): smallest\_index = 0 for i in range(1, len(arr)): if arr[i] \< arr[smallest\_index]: smallest\_index = i return smallest\_index
Selection sort
def selectionSort(arr): n=len(arr) for i in range(n): nmin=arr[i] npos=i for j in range(i+1,n): if arr[j]: **nmin=arr[j]** **npos=j** arr[npos]=arr[i] arr[i]=nmin
in-place sorting
Remove element from array\list
and return the value
- val=array.pop(index)
- from end arr.pop()
- from start arr.pop(0)
Count down using recursion
def countdown(i): print(i)
base case
if i <= 0:
return
else:
# recursion
countdown(i-1)
Runtime O(n)
Explain call stack
stack:
push new item on top
pop from the top most item
When you call a function from another function, the calling function is paused in a partially completed state.
Applies to recusrsion.
Library to import type List?
from typing import List
others:
from typing import Mapping, Optional, Sequence, Union
Library to import Optional?
- from typing import Optional
Get Maximum, Minimum
max() and min() no import required
Mutable vs immutable
mutable = liable to change
Everything in Python is an Object, every variable holds an object instance.
Objects of built-in types like (int, float, bool, str, tuple, unicode) are immutable.
Array slicing: from start index to end index?
arr[2:4]
Array slicing: from start index to end?
arr[3:]
a=[0,1,2,3,4,5,6]
a[3:]
Array slicing: from start to end index?
arr[:4]
ans = [0, 1, 2, 3]
Array slicing: negative index?
Counting from the end.
Array slicing: index with step?
print(list(range(0,13,3)))
[0, 3, 6, 9, 12]
Last index-1!
Array slicing: stepping entire array?
arr=list(range(0,13))
print(arr[::3])
Array slicing: reversing the array?
arr=list(range(0,13))
print(arr[::-1])
[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Array slicing: 2d array?
arr=[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]]
arr[1][2:4]
ans = [8, 9]
Deque translation
Double Ended Queue
Main methods in deque
from collections import deque
d=deque([0,1,2,3,4,5])
append(item) and pop()
but also
appendleft()
popleft()
deque vs list
list: append and pop is O(n)
FIFO queue
first In, first Out
from queue import Queue
q=Queue(maxsize=10)
Methods:
qsize()
empty()
full()
put()
get()
LIFO
Last In, First Out - same as Stack
Python list:
arr. append(item)
arr. pop()
from queue import LifoQueue
from queue import LifoQueue
d=LifoQueue()
d.put(0)
d.put(1)
d.put(2)
d.put(3)
d.get() -> 3
Quick sort
- recursiv
- pivot
- generator for left and right
def quicksort(array):
if len(array) <=1: #empty or 1 element
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
Hash Function
“maps strings to numbers.”
What does a hash function do?
- The hash function consistently maps a name to the same index. Every time you put in “avocado”, you’ll get the same number back. So you can use it the first time to find where to store the price of an avocado, and then you can use it to find where you stored that price.
- The hash function maps different strings to different indexes. “Avocado” maps to index 4. “Milk” maps to index 0. Everything maps to a different slot in the array where you can store its price.
- The hash function knows how big your array is and only returns valid indexes. So if your array is 5 items, the hash function doesn’t return 100 … that wouldn’t be a valid index in the array
Creating a dictionary?
x={}
or
x=dict()
What is a a Palindrome?
- Number or word that spells the same forward and backwards.
- Can be odd and even
Anna
level
Binary Tree Traversals
Depth First Search (DFS):
Left always before right!
(a) Inorder (Left, Root, Right)
(b) Preorder (Root, Left, Right)
(c) Postorder (Left, Right, Root)
Breadth-First (BFS) or Level Order Traversal
Stack vs Heap
- Stack linear data structure
- Heap hierarchical data structure
- Stack never fragments
- Stack local variables
- Heap global variables
- Stack variables can’t be resized
- Heap variables can be resized
- Stack deallocation by compiler
- Heap done by programmer
- Stack is a linear data structure whereas Heap is a hierarchical data structure.
- Stack memory will never become fragmented whereas Heap memory can become fragmented as blocks of memory are first allocated and then freed.
- Stack accesses local variables only while Heap allows you to access variables globally.
- Stack variables can’t be resized whereas Heap variables can be resized.
- Stack memory is allocated in a contiguous block whereas Heap memory is allocated in any random order.
- Stack doesn’t require to de-allocate variables whereas in Heap de-allocation is needed.
- Stack allocation and deallocation are done by compiler instructions whereas Heap allocation and deallocation is done by the programmer.
BUD Principle
Bottlenecks
Unnecesssary Work
Duplicated work
Sort string
sorted(string)
Remove white spaces from string?
- strip(): returns a new string after removing any leading and trailing whitespaces including tabs (\t).
- rstrip(): returns a new string with trailing whitespace removed. It’s easier to remember as removing white spaces from “right” side of the string.
- lstrip(): returns a new string with leading whitespace removed, or removing whitespaces from the “left” side of the string.
Class stub
A Sample class with init method
class Person: def \_\_init\_\_(self, name): self.name = name
Create print() method in Class
def \_\_repr\_\_(self): return "Test()" def \_\_str\_\_(self): return "member of Test"
Linked list, delete middle node:
def delete_middle_node(node):
node. val=node.next.val
node. next = node.next.next
Base Methods for stack?
A stack is a last in - first out (LIFO) queue!
list methods: append, pop
LifoQueue methods: put, get, qsize, empty
Base methods for Queue?
- put
- get
- empty
- qsize
- full
Initialize:
from queue import Queue
q=Queue(5)
Inherit class, show constructor?
class Student(Person): def \_\_init\_\_(self, fname, lname): **super().\_\_init\_\_**(fname, lname)
How to override class methods?
- Use the same name for the method
class Parent(object): def \_\_init\_\_(self): self.value = 4 def **get\_value**(self): return self.value
class Child(Parent): def **get\_value**(self): return self.value + 1
Manually raise error
- raise Exception(‘I know Python!’)
- SyntaxError
- ValueError
- Warning
Tree definitions
Binary tree: each node has at most 2 children
A node is called a “leaf” node if it has no children.
Binary Tree vs. Binary Search Tree
- Binary Tree: Node, max 2 children
- Binary Search Tree (BST) = sorted binary tree
- BST: for each node left subtree < node < right subtree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.
Complete Binary Trees
A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level.
To the extent that the last level is filled, it is filled left to right.
If there are not gpas then it would be Perfect Binary Tree.
Full Binary Tree?
- Each node has 0 = leaf or 2 children
A full binary tree is a binary tree in which every node has either zero or two children.
That is, no nodes have only one child.
Perfect Binary Trees
A perfect binary tree is one that is both full and complete.
All leaf nodes will be at the same level, and this level has the maximum number of nodes.
In-Order Traversal
def in_order_traversal(node:BinaryTree,level=0):
if node:
level+=1
in_order_traversal(node.left,level
print(‘ ‘*level+str(node.val))
in_order_traversal(node.right,level)
return
Pre-Order Traversal
def pre_order_traversal(node:BinaryTree,level=0):
if node:
level+=1
visit(node,level)
in_order_traversal(node.left,level)
in_order_traversal(node.right,level)
return
Post-Order Traversal
def post_order_traversal(node:BinaryTree,level=0):
if node:
level+=1
in_order_traversal(node.left,level)
in_order_traversal(node.right,level)
visit(node,level)
return
Binary Heaps
(Min-Heaps and Max-Heaps)
A min-heap is a complete binary tree (that is, totally filled other than the rightmost elements on the last level) where each node is smaller than its children.
Tries
(Prefix Trees)
- characters are stored in nodes
- use dictionary in python
- each level is a new dictionary
- ends with ‘*’
A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.
The * nodes (sometimes called “null nodes”) are often used to indicate complete words. For example, the
fact that there is a * node under MANY indicates that MANY is a complete word. The existence of the MA path
indicates there are words that start with MA.
O(k) with k = length of the word
same as hash
Graph
Graphs can be expressed as dictionaries = Adjacency List
d={}
d[nodex]=[nodey,nodez]
class **Graph()**: def \_\_init\_\_(self,val): self.val=val **self.children=[]**
Adjacency Matrices
An adjacency matrix is an NxN boolean matrix (where N is the number of nodes), where a true value at matrix[i][j] indicates an edge from node i to node j. (You can also use an integer matrix with Os and 1s.)
Bit operations in Python
print bin(123)
OperatorExampleMeaning
& a & b Bitwise AND
| a | b Bitwise OR
^ a^b Bitwise XOR (exclusive OR)
Only true if either is True- not both
~ ~a Bitwise NOT
« n Bitwise left shift - multiply by 2
» n Bitwise right shift - divide by 2^n-1
What does the following mean:
(( n & (n-1)) == 0)
Example: n is 15
then (n-1) = 14
n & (n-1) is only 0 if the two numbers dont share a bit.
-> this can only happen if n is 2^x
For example 2, 4, 8, 16, …
Singleton Class in Python
- __instance as class variable (no self)
- getInstance() as static method
- __init__ to allow setting __instance 1 time
class Singleton:
__instance = None
@staticmethod
def getInstance():
if Singleton.__instance == None:
Singleton()
return Singleton.__instance
def __init__(self):
if Singleton.__instance != None:
raise Exception(“This class is a singleton!”)
else:
Singleton.__instance = self
Memoization vs Recursion
A note on terminology: Some people call top-down dynamic programming “memoization” and
only use “dynamic programming“to refer to bottom-up work. We do not make such a distinction here. We call both dynamic programming.
Fibonacci number
- sum of previous 2 numbers
- starts with 0 and 1
In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Horizontal vs. Vertical Scaling
- Vertical scaling means increasing the resources of a specific node. For example, you might add additional memory to a server to improve its ability to handle load changes.
- Horizontal scaling means increasing the number of nodes. For example, you might add additional servers, thus decreasing the load on any one server.
Load Balancer
- distribute the load evenly
Typically, some frontend parts of a scalable website will be thrown behind a load balancer. This allows a system to distribute the load evenly so that one server doesn’t crash and take down the whole system. To do so, of course, you have to build out a network of cloned servers that all have essentially the same code and access to the same data.
Database Denormalization and NoSQL
- Table with redundant information.
Denormalization is one part of this. Denormalization means adding redundant information into a database to speed up reads.
Chr and Ord
Ord(‘A’)
and
Chr(2)
Modulo operator
%
Example: n % 26
Database Partitioning (Sharding)
- Vertical = by feature
- Key-or Hash-Based = split up by index
- Directory-Based = directories based on lookup
- Vertical Partitioning: This is basically partitioning by feature. For example, if you were building a social network, you might have one partition for tables relating to profiles, another one for messages, and so on. One drawback of this is that if one of these tables gets very large, you might need to repartition that database (possibly using a different partitioning scheme).
-
Key-Based (or Hash-Based) Partitioning: This uses some part of the data (for example an ID) to parti
tion it. A very simple way to do this is to allocate N servers and put the data on mod (key, n). One issue
with this is that the number of servers you have is effectively fixed. Adding additional servers means
reallocating all the data-a very expensive task. -
Directory-Based Partitioning: In this scheme, you maintain a lookup table for where the data can be
found. This makes it relatively easy to add additional servers, but it comes with two major drawbacks.
First, the lookup table can be a single point of failure. Second, constantly accessing this table impacts
performance.
Networking Metrics
- Bandwidth = maximum
- Throughput = actual
- Latency = delay
- Bandwidth: This is the maximum amount of data that can be transferred in a unit of time. It is typically expressed in bits per second (or some similar ways, such as gigabytes per second).
-
Throughput: Whereas bandwidth is the maximum data that can be transferred in a unit of time,
throughput is the actual amount of data that is transferred. -
Latency: This is how long it takes data to go from one end to the other. That is, it is the delay between the
sender sending information (even a very small chunk of data) and the receiver receiving it.
Bubble Sort
- Runtime: O(n2), Memory O(1)
- Two loops
- Shifts last elements to the right
def bubbleSort(arr): n = len(arr) for i in range(n-1): for j in range(0, n-i-1): if arr[j] \> arr[j + 1] : arr[j], arr[j + 1] = arr[j + 1], arr[j]
Selection Sort
- O(n2)
- Two loops
- Inner loop to find the local minimum
def selectionSort(arr):
n=len(arr)
result=[]
for i in range(n):
nmin=float(‘inf’)
npos=-1
for j in range(n-i):
if arr[j] nmin=arr[j]
npos=j
result.append(nmin)
arr.pop(npos)
return result
Merge Sort
- Runtime: O(n*log(n))
- len(arr)>1, mid, left, right recursion
- i=j=k=0, sort the array with while i,j
- use array extend()
merge sort
def merge\_sort(list): list\_length = len(list) if list\_length == 1: return list mid\_point = list\_length // 2 left\_partition = merge\_sort(list[:mid\_point]) right\_partition = merge\_sort(list[mid\_point:])
return merge(left_partition, right_partition)
def merge(left, right):
output = []
i = j = 0
while i if left[i] output.append(left[i])
i += 1
else:
output.append(right[j])
j += 1
output. extend(left[i:])
output. extend(right[j:])
return output
Quick Sort
def quicksort(array):
if len(array) <=1: #empty or 1 element
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
Arithmetic operators
*
/
% modulo
// Integer division
** Exponent
Comparison operators
>
<
=
!= not equal
>=
<=
Logical operators
and
or
not
Bitwise operators
& and
| or
~ not
^ xor: or with false for (true,true)
» shift right -> //2
« shift left -> *2
Identity operators
is
is not
Membership operators
- in
- not in
What is the Fibonacci number?
n=prev(n-1)+perv(n-1)
Slow recursiv:
def fib(n:int): if (n \<= 0): return 0 elif (n == 1): return 1 return fib(n - 1) + fib(n - 2)
fast non recursive:
Time function execution time?
import timeit
print(timeit.timeit(lambda: fib(8),number=1000))
What is __repr__ ?
Called by the repr() built-in function and by string conversions (reverse quotes) to compute the “official” string representation of an object. If at all possible, this should look like a valid Python expression that could be used to recreate an object with the same value (given an appropriate environment).
What is __str__ ?
Called by the str() built-in function and by the print statement to compute the “informal” string representation of an object.
What is a Tries (Prefix Trees)?
A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.
Runtime: O(k), with k the legth of the string
Adjacency List
A graph representation as simple list or dictionary. Each node shows it’s value and then a list of connected nodes.
0: 1
1: 2
2: 0, 3
3: 2
4: 6
5: 4
6: 5
Convert Adjascent List to Node:
def adjascentListToNode(d):
if not d:
return None
created={}
root=None
# first create all single nodes
for k in d.keys():
temp=Tree(k)
created[k]=temp
if not root:
root=created[k]
# wire up the children
for k in d.keys():
item=created[k]
for child in d[k]:
item.children.append(created[child])
return root
Depth First Search
def dfs(visited,parent,node):
if node not in visited:
print(str(parent.val)+’ -> ‘+str(node.val))
visited.add(node)
if len(node.children)>0:
for child in node.children:
dfs(visited,node,child)
else:
print(str(node.val)+’ -> null’)
Breadth First Search
def bfs(visited, node):
q=Queue()
q.put(node)
while not q.empty():
item=q.get()
visited.add(item)
print(str(item.val))
for child in item.children:
if child not in visited:
q.put(child)
enumerate
Gives both the value and index!
def function(s:str):
for i, c in enumerate(s):
Sparse Vector
A vector where the 0’s are compressed away.
Maybe dictionary class.
Enumerate dictionary?
for k, v in d.items():
print(k, v)
sorted with key
sorted(“This is a test string from Andrew”.split(),key=str.lower)
[‘a’, ‘Andrew’, ‘from’, ‘is’, ‘string’, ‘test’, ‘This’]
Binary Tree traversals
Breadth-First Search (a.k.a BFS)
and Depth-First Search (a.k.a. DFS).
DFS:
preorder DFS
inorder DFS
and postorder DFS
random
import random
- randome.choice([1,2,3,4])
- r=random.random()
- rint=random.randint(1,3)
Modulo Distributive
- (a + b) mod n = [(a mod n) + (b mod n)] mod n.
- ab mod n = [(a mod n)(b mod n)] mod n.
Which of the following are equivalent to O(N)? Why?
O(N + P), where P < N/2
O(2N)
O(N + log N)
O(N + M)
- If P < N/2, then we know that N is the dominant term so we can drop the O(P).
- O(2N) is O(N) since we drop constants.
- O(N) dominatesO(log N),so we can drop the O(log N).
- There is no established relationship between N and M, so we have to keep both variables in there.
Min Heap
Algorithm Average Worst case
Space O(n) O(n)
Search O(n) O(n)
Insert O(1) O(log n)
Find-min O(1) O(1)
Delete-min O(log n) O(log n)
Max Heap
Algorithm Average Worst case
Space O(n) O(n)
Search O(n) O(n)
Insert O(1) O(log n)
Find-min O(1) O(1)
Delete-min O(log n) O(log n)
Python List/Array Methods
- append() Adds an element at the end of the list
- clear() Removes all the elements from the list
- copy() Returns a copy of the list
- count() Number of elements (of value)
- extend() Add the elements of a list at end
- index() Index of the first element with value
- insert() Adds an element at the specified position
- pop() Removes the element at position
- remove() Removes the first item with value
- reverse() Reverses the order of the list
- sort() Sorts the list
Split string
s=’abcd efgh’
temp=s.split()
Join String
Can only join string arrays!
text = ['Python', 'is', 'a', 'fun', 'programming', 'language']
# join elements of text with space
print(' '.join(text))The “Runner” Technique
Linked List
Working with two pointer - maybe one runing ahead of the other
Recursive Problems in Linked Lists
You should remember that recursive algorithms take at least O(n) space, where n is the depth of the recursive call. All recursive algorithms can be implemented iteratively, although they may be much more complex.
Remove Duplicates from Linked List
- Get 2 pointers: previous and current node
- Compare values
def removeDups(node:Node):
s=set()
head=node
prev=node
while node:
if node.val in s:
prev.next=node.next
else:
s.add(node.val)
prev=node
node=node.next
return head
Graph Search
In breadth-first search (BFS), we start at the root (or another arbitrarily selected node) and explore each neighbor before going on to any of their children. That is, we go wide (hence breadth-first search) before we go deep.
breadth-first search (BFS)
- using queue
- from level 0 - n
In depth-first search (DFS), we start at the root (or another arbitrarily selected node) and explore each branch completely before moving on to the next branch. That is, we go deep first (hence the name depth first search) before we go wide.
depth first search best by recursion!
depth-first search (DFS), if binary:
- in-order
- pre-order
- post-order
Find collision in Single Search
Find collision in Bidirectional Search
Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
- arr, start, end
- calculate mid
- set root val to mid
- set left, right recursivly
- retun root
def minimalTree(arr:List,start, end): if start \> end: return None mid = (start+end) // 2 root = Node(arr[mid]) root.left = minimalTree(arr, start, mid - 1) root.right = minimalTree(arr, mid + 1, end) return root
What is a tuple?
a=(1,2)
x ^ 0s = x
x ^ ls = ~x
x ^ x = 0
XOR
exclusive Or
0 0 = 0
1 0 = 1
0 1 = 1
1 1 = 0
x | 0s = x
x | 1s = 1s
x | x = x
Or
0 | 0 = 0
1 | 0 = 1
0 | 1 = 1
1 | 1 = 1
x & 0s = 0
x & 1s = x
x & x = x
0 0 = 0
1 0 = 0
0 1 = 0
1 1 = 1
Two’s Complement and Negative Numbers
The binary representation of-K (negative K) as a N-bit number is concat (1, 2n-1 - K)
Example: -7
n = 4 n-1 = 3 =\> 2<sup>n-1</sup> = 8 - K = 1
binary representation: 1001
Example 7:
the usual: 0111
Logical vs Arithmetic Right Shift
- Logical left==0
- Arithmetic left==1
In a logical right shift, we shift the bits and put a 0 in the most significant bit. It is indicated with a >>> operator:
10011001
01001100
In an arithmetic right shift, we shift values to the right but fill in the new bits with the value of the sign bit. This has the effect of (roughly) dividing by two. It is indicated by a >> operator:
10011001
11001100
Get bit = check if bit is set
- shift 1 by k
- apply and
def getBit(val,k): mask=**1«k return (val & mask)!=0**
alternatively:
def getBit(val,k): mask=**1«k return (val ^ mask)!=val**
Set bit and return value
or
def setBit(val,k): mask=1«k return (val **|** mask)
Clear bit
def clearBit(val,k): mask= 1«k mask = ~mask # **set all other bits and clear the on**
return val & mask
Clear all bits from the most significant bit through i (inclusive).
- mask=1<
- mask=mask-1
- example 00000111
- num & mask
Clear all bits from i through 0 (inclusive).
mask=1«k
mask=mask-1
example: 00000111
mask=~mask
example: 11111000
num & mask
Convert binary string to decimal?
int(‘0010’,2)
nonlocal vs global variable
- global: access of global variable in method
- nonlocal: access to global method in nested method
Longest distance between two nodes?
path=[0]
def longest_path(node,path):
if not node:
return 0
left\_path = longest\_path(node.left,path) right\_path = longest\_path(node.right,path) **path[0] = max(path[0], left\_path + right\_path)** return max(left\_path, right\_path) + 1
longest_path(root,path)
Check if char is number?
‘A’.isdigit() False
‘A’.isalpha() True
‘1’.isdigit() True
‘1’.isalpha() False
What is the __call__ method?
- same as __init__ just for instance
- e=E() -> __init__
- e() -> __call__
The __call__ method enables Python programmers to write classes where the instances behave like functions and can be called like a function. When the instance is called as a function; if this method is defined, x(arg1, arg2, …) is a shorthand for x.__call__(arg1, arg2, …)
yield vs return
- return = single value
- yield = sequence of values
- yiel is used as a generator
print(list(range(10))) vs
print(list(range(10,0,-1)))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Sort list of tuples by second item?
tup.sort(key = lambda x: x[1])
Lamda function?
- lambda arguments : expression
- f = lambda x : x + 10
- print(f(5))
Abs value?
- abs(-3.1) =3.1
- no import reuqired!
Short Circuiting in Boolean Operators
- x or y -> y only eval if x is False
- x and y -> y only eval if x is True
*
Evaluate string expression?
- eval(‘2+3’)
- ans=5
Get only the bits from an integer?
- bin(1234235)[2:]
- ans = ‘100101101010100111011’
What is the base case in recursion?
The base case (or base condition) is the state where the program’s solution has been reached. An achievable base case is essential to avoid an infinite loop. Recursive methods are built with two paths: the method first checks if the base state has been reached, if yes, the method ends and returns the current data, if not the method instead goes the other path and executes the recursive case, altering the input and calling the method again.
Tail Recursion
Tail recursion is when the recursive call for the next cycle is the final statement in a method.
Tail end recursion is considered good practice whenever possible because it is easier to follow from a reader’s perspective and it can be optimized by modern compilers.
Thread vs. Process
- Process means a program is in execution, whereas thread means a segment of a process.
- A Process is not Lightweight, whereas Threads are Lightweight.
- A Process takes more time to terminate, and the thread takes less time to terminate.
- Process takes more time for creation, whereas Thread takes less time for creation.
- Process likely takes more time for context switching whereas as Threads takes less time for context switching.
- A Process is mostly isolated, whereas Threads share memory.
- Process does not share data, and Threads share data with each other.
How would you measure the time spent in a context switch?
Record the timestamps of the first and last instructions of the swapping processes. The context switch time is the difference between the two processes.
Lock vs Mutex vs Semaphore
- A lock allows only one thread to enter the part that’s locked and the lock is not shared with any other processes.
- A mutex is the same as a lock but it can be system wide (shared by multiple processes).
- The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal or wait—not both.
Python default threading.
- Single threaded due to
GIL = Global Interpreter Lock - GIL is a mutex
How to do string interpolation?
- variable in brackets {}
- needs the f’ aprt
name = ‘World’
program = ‘Python’
print(f’Hello {name}! This is {program}’)
How to create a thread?
- import threading
- x = threading.Thread(target=thread_function,
* *args=(1,), daemon=False**) - x.start()
- x.join() -> wait for thread to complete
What does Mutex stand for?
MUTual EXclusion
How to use a lock?
- __init__: self._lock = threading.Lock()
- in methods: with self._lock:
How does a Semaphore work?
- obj=threading.Semaphore(3)
- obj.acquire()
- obj.release()
Binary Tree vs. Binary Search Tree?
all left descendents <= n < all right descendents
Binary Tree vs. Binary Search Tree?
all left descendents <= n < all right descendents
Balanced vs. Unbalanced Trees
One way to think about it is that a “balanced” tree really means something more like “not terribly imbalanced”.
Maybe same depth.
Complete Binary Trees?
A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.
Complete Binary Trees?
A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.
Full Binary Trees
A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.
Full Binary Trees
A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.
Perfect Binary Trees?
A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.
Perfect Binary Trees?
A perfect binary tree is one that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.
Difference between:
Full
Complete
Perfect
- Full: each node is either a leaf or has both children
- Complete: last level from left to right - doesn’t need to be all!
- Perfect: The nodes on the alst leve are all filled.
Difference between:
Full
Complete
Perfect
- Full: each node is either a leaf or has both children
- Complete: last level from left to right - doesn’t need to be all!
- Perfect: The nodes on the alst leve are all filled.
Frequent errors:
- misspelled return
- missing :
- missing self in class method
- missing plural form e.g. num instaead of nums
- index instead of value
for i in range:
vs
for i in nums:
Permutations!!
def permutations(arr, result,sub=’’):
if len(arr) == 0:
result.append(sub)
else:
for i in range(len(arr)):
permutations(arr[:i] + arr[i+1:], result,sub + arr[i])
Ternary Operator
print(“a” if True else “b”)
- first the true condition
a=’012345’
print(a[2:4])
ans= ‘23’
‘str’ object does not support item assignment
- a=’hello world’
- a[1] works ans = ‘l’
- a[1] = ‘z’ throws error
choice function
- import random
- random.choice([1,2,3])
Remove key from dictionary
- my_dict.pop(‘key’, None)
Merge sort Main
def merge\_sort(list): list\_length = len(list) if list\_length == 1: return list mid\_point = list\_length // 2 left\_partition = merge\_sort(list[:mid\_point]) right\_partition = merge\_sort(list[mid\_point:])
return merge(left_partition, right_partition)
Merge sort Merge
def merge(left, right):
output = []
i = j = 0
while i if left[i] output.append(left[i])
i += 1
else:
output.append(right[j])
j += 1
output. extend(left[i:])
output. extend(right[j:])
return output
The Heavy Pill: You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.
- Take advantage of EACH pill weighing 0.1 more
- Number bottles and put them on the scale:
1,2,3,4 - Measure and directly know the answer!
Basketball: You have a basketball hoop and someone says that you can play one of two games.
Game 1: You get one shot to make the hoop.
Game 2: You get three shots and you have to make two of three shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?
Game 1
p
Game 2
all = p^3
2 out of 3 3*(1-p)*p^2
=3p^2-3p^3
adding all scenarios
=p^3+3p^2-p^3
=-2p^3+3p^2
Compare 1 and 2
p>-2p^3+3p^2
1>-2p^2+3p
0>-2p^2+3p-1
0<2p^2-3p+1
Factoring
2p^2-2p-1p+1
2p*(p-1)-1(p-1)
(2p-1)*(p-1)
p=0.5
p=1
Dominos: There is an 8x8 chessboard in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example or showing why it’s impossible).
- All dominos 8x8 = 64
- minus two diagonally opposite corners = 62
- Does Not work since we can’t place the 31 dominos
Ants on a Triangle: There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.
Similarly, find the probability of collision with n ants on an n-vertex polygon.
ALL ants need to walk in the same direction:
P (clockwise)= (0.5)^3
P (counter clockwise)= (0.5)^3
P (same direction)= (0.5)^3 + (0.5)^3 =
2*1/8=0.25
Collision: 1-0.25=0.75
General: 2* (0.5)^n = (0.5)^(n-1)
Collision: 1-(0.5)^(n-1)
Jugs of Water: You have a five-quart jug, a three-quart jug, and an unlimited supply of water (but no measuring cups). How would you come up with exactly four quarts of water? Note that the jugs are oddly shaped, such that filling up exactly “half” of the jug would be impossible.
Easy:
- Fill 3
- Pour 3 into 5
- Fill 3
- Pour 3 until 5 is full -> left 1
- Toss 5
- Pour 1 quart in 5
- Fill 3
- Pour into 5
- Voila 4
Blue-Eyed Island: A bunch of people are living on an island, when a visitor comes with a strange order: all blue-eyed people must leave the island as soon as possible. There will be a flight out at 8:00pm every evening. Each person can see everyone else’s eye color, but they do not know their own (nor is anyone allowed to tell them). Additionally, they do not know how many people have blue eyes, although they do know that at least one person does. How many days will it take the blue-eyed people to leave?
- solve for n=1,2,3
- n=1, leave first night
- n=2, guy is still there, so n==2, leave 2nd night
- n=3, see two others, leaves 3rd night
The Apocalypse: In the new post-apocalyptic world, the world queen is desperately concerned about the birth rate. Therefore, she decrees that all families should ensure that they have one girl or else they face massive fines. If all families abide by this policy-that is, they have continue to have children until they have one girl, at which point they immediately stop-what will the gender ratio of the new generation be? (Assume that the odds of someone having a boy or a girl on any given pregnancy is equal.) Solve this out logically and then write a computer simulation of it.
Sequence:
G
BG
BBG
BBBG
Can sum probs for G:
0.5, 0.25, 0.125, ….
One way to think about this is to imagine that we put all the gender sequence of each family into one giant
string. So if family 1 has BG, family 2 has BBG, and family 3 has G, we would write BGBBGG
The Egg Drop Problem: There is a building of 100 floors. If an egg drops from the nth floor or above, it will break. If it’s dropped from any floor below, it will not break. You’re given two eggs. Find n, while minimizing the number of drops for the worst case.
**100 Lockers:** There are 100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next, he closes every second locker. Then, on his third pass, he toggles every third locker (closes it if it is open or opens it if it is closed). This process continues for 100 passes, such that on each pass i, the man toggles every ith locker. After his 100th pass in the hallway, in which he toggles only locker #100, how many lockers are open?
A door is left open if the number of factors (which we will call x) is odd. You can think about this by pairing factors off as an open and a close. If there’s one remaining, the door will be open.
The value x is odd if n is a perfect square. Here’s why: pair n’s factors by their complements. For example,
if n is 36, the factors are (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Note that (6, 6) only contributes one factor, thus
giving n an odd number of factors.
There are 10 perfect squares. You could count them (1, 4, 9, 16, 25, 36, 49, 64, 81, 100)
Poison: You have 1000 bottles of soda, and exactly one is poisoned. You have 10 test strips which can be used to detect poison. A single drop of poison will turn the test strip positive permanently.
You can put any number of drops on a test strip at once and you can reuse a test strip as many times as you’d like (as long as the results are negative). However, you can only run tests once per day and it takes seven days to return a result. How would you figure out the poisoned bottle in as few days
as possible?
Follow up: Write code to simulate your approach.
Run 10 tests on 3 different days:
Check problem description! Duplicates can cause ambiguity.
Add another day and shift last digit.
Easiest binary encoding:
Translate bottle number into binary form
Each strip represents bit
Based on result we get the binary representation of the value
Setting up n*n matrix?
- [[0]*3 for i in range(3)]
Rows and columns in Python
Last n letter in word?
- negative index in the front!
- word[-n:]
Assign slice of array values?
- both sides need to be iterable!
- a[1:3]=[i for i in range(1:3)]
- make sure they have the same size!
Matrix multiplication
- cols(A) * rows(B)
- result
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
def subsets(self, nums: List[int]) -\> List[List[int]]: output = [[]]
for num in nums:
output += [curr + [num] for curr in output]
return output
Generator with conditions?
- if
- after ‘i in arr’
- [i for i in arr if i<4]
Iterate a set
s=set()
s. add(1)
s. add(2)
s. add(3)
s. add(4)
for i in s: print(i)
also
len(s)
Initialize set
- s=set()
- s=set([1,2,3,4,5])
sort first then second
points.sort(key=lambda x: (x[0],x[1]))
