Python Flashcards

(193 cards)

1
Q

Example O(log n)

A

Binary search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Example O(n)

A
  • Simple search
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Example O(n * log n)

A

quicksort (fast)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Example O(n2)

A
  • selection sort (slow)
actually O(n × 1/2 × n)
list get's smaller each time you find an element
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

O(n!)

A

traveling salesperson

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain O(n)

A

Big O and n = number of operations
time factor would be c*O(n)

Average cost for execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

binary search algo

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

log 8

A

3: 23

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

log 1,024

A

10: 210

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

log 256

A
  • 8: 28
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Big O of reading array

A

O(1)

a[5]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Big O of reading linked list

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Big O of inserting array

A

O(n)

array with 4 elements and you add another requires new array and moving elements over

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Big O of inserting linked list

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Minimal implementation of linked list

A
class Node:
 def \_\_init\_\_(self, **val=None**):
 self.val = val # the value
 self.next = None # reference to next node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

find smallest element in array

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Selection sort

A
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Remove element from array\list
and return the value

A
  • val=array.pop(index)
  • from end arr.pop()
  • from start arr.pop(0)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Count down using recursion

A
def countdown(i):
 print(i)

base case
if i <= 0:
return
else:
# recursion
countdown(i-1)

Runtime O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Explain call stack

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Library to import type List?

A

from typing import List

others:

from typing import Mapping, Optional, Sequence, Union

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Library to import Optional?

A
  • from typing import Optional
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Get Maximum, Minimum

A

max() and min() no import required

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Mutable vs immutable

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Array slicing: from start index to end index?
arr[2:4]
26
Array slicing: from start **index** to end?
arr[3:] a=[0,1,2,3,4,5,6] a[3:]
27
Array slicing: from start to end **index**?
arr[:4] ans = [0, 1, 2, 3]
28
Array slicing: negative index?
Counting **from the end.**
29
Array slicing: index with step?
print(list(range(0,13,**3**))) [0, 3, 6, 9, 12] Last index-1!
30
Array slicing: stepping entire array?
arr=list(range(0,13)) print(arr[::**3**])
31
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]
32
Array slicing: 2d array?
arr=[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]] arr[1][2:4] ans = [8, 9]
33
Deque translation
**Double Ended** Queue
34
Main methods in deque
from collections import deque d=deque([0,1,2,3,4,5]) **append(item)** and **pop()** but also **appendleft() popleft()**
35
deque vs list
list: append and pop is O(n)
36
FIFO queue
first In, first Out from queue import Queue q=Queue(maxsize=10) Methods: qsize() **empty()** full() **put()** **get()**
37
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
38
Quick sort
* recursiv * pivot * generator for left and right ## Footnote 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)**
39
Hash Function
“maps strings to numbers.”
40
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
41
Creating a dictionary?
x={} or x=dict()
42
What is a a Palindrome?
* Number or word that spells the same forward and backwards. * Can be **odd and even** Anna level
43
**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
44
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.
45
BUD Principle
**B**ottlenecks **U**nnecesssary Work **D**uplicated work
46
Sort string
sorted(string)
47
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.
48
Class stub
A Sample class with init method ``` class Person: def \_\_init\_\_(self, name): self.name = name ```
49
Create print() method in Class
``` def \_\_repr\_\_(self): return "Test()" def \_\_str\_\_(self): return "member of Test" ```
50
Linked list, delete middle node:
def delete\_middle\_node(node): node. val=node.next.val node. next = node.next.next
51
Base Methods for stack?
A stack is a last in - first out **(LIFO)** queue! list methods: append, pop LifoQueue methods: put, get, qsize, empty
52
Base methods for Queue?
* put * get * empty * qsize * full ## Footnote Initialize: from queue import Queue q=Queue(5)
53
Inherit class, show constructor?
``` class Student(Person): def \_\_init\_\_(self, fname, lname): **super().\_\_init\_\_**(fname, lname) ```
54
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 ```
55
Manually raise error
* raise Exception('I know Python!') * SyntaxError * ValueError * Warning
56
Tree definitions
Binary tree: each node has at most 2 children A node is called a "leaf" node if it has no children.
57
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.
58
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.
59
Full Binary Tree?
* Each node has 0 = leaf or 2 children ## Footnote 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**.
60
Perfect Binary Trees
A perfect binary tree is one that is **both full and complete**. ## Footnote **All leaf nodes will be at the same level, and this level has the maximum number of nodes.**
61
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
62
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
63
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
64
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**.
65
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
66
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=[]** ```
67
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.)
68
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
69
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, ...
70
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
71
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.
72
Fibonacci number
* sum of previous 2 numbers * starts with 0 and 1 ## Footnote 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, ...
73
Horizontal vs. Vertical Scaling
* Vertical scaling means increasing the resources of a specific node. For example, you might add addi­tional 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.
74
Load Balancer
* distribute the load evenly ## Footnote 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.
75
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.
76
Chr and Ord
Ord('A') and Chr(2)
77
Modulo operator
% Example: n % 26
78
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.
79
Networking Metrics
* Bandwidth = maximum * Throughput = actual * Latency = delay ## Footnote **​** * **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.
80
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] ```
81
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
82
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() ## Footnote 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
83
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)
84
Arithmetic operators
+ - \* / % modulo // Integer division \*\* Exponent
85
Comparison operators
\> \< = != **not equal** \>= \<=
86
Logical operators
and or not
87
Bitwise operators
& and | or ~ not ^ xor: or with false for (true,true) » shift right -\> //2 « shift left -\> \*2
88
Identity operators
is is not
89
Membership operators
* in * not in
90
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:
91
Time function execution time?
import timeit print(timeit.timeit(lambda: fib(8),number=1000))
92
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).
93
What is \_\_str\_\_ ?
Called by the **str() built-in function** and by the print statement to compute the **"informal"** string representation of an object.
94
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
95
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
96
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
97
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')
98
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)
99
enumerate
Gives both the value and index! def function(s:str): for **i, c in enumerate(s)**:
100
Sparse Vector
A vector where the 0's are compressed away. Maybe dictionary class.
101
Enumerate dictionary?
for k, v in d.items(): print(k, v)
102
sorted with key
sorted("This is a test string from Andrew".split(),key=str.lower) ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
103
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
104
random
import random * randome.choice([1,2,3,4]) * r=random.random() * rint=random.**randint**(1,3)
105
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.
106
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.
107
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)
108
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)
109
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
110
Split string
s='abcd efgh' temp=s.split()
111
Join String
Can only join string arrays! ## Footnote ``` text = ['Python', 'is', 'a', 'fun', 'programming', 'language'] # join elements of text with space print(' '.join(text)) ```
112
The "Runner" Technique
Linked List Working with two pointer - maybe one runing ahead of the other
113
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.
114
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
115
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
116
Find collision in Single Search
117
Find collision in Bidirectional Search
118
Given a **sorted (increasing order) array** with unique integer elements, write an algo­rithm 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 ```
119
What is a tuple?
a=**(1,2)**
120
x ^ 0s = x x ^ ls = ~x x ^ x = 0
XOR **exclusive Or** 0 0 = 0 1 0 = 1 0 1 = 1 **1 1 = 0**
121
x | 0s = x x | 1s = 1s x | x = x
**Or** 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1
122
x & 0s = 0 x & 1s = x x & x = x
0 0 = 0 1 0 = 0 0 1 = 0 1 1 = 1
123
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 =\> 2n-1 = 8 - K = 1 ``` binary representation: **1**001 Example 7: the usual: **0**111
124
Logical vs Arithmetic Right Shift
* Logical **left==0** * Arithmetic **left==1** ## Footnote In a logical right shift, we shift the bits and put a 0 in the most significant bit. It is indicated with a \>\>\> operator: 1001100**1** **0**1001100 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: 1001100**1** **1**1001100
125
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** ```
126
Set bit and return value
**or** ``` def setBit(val,k): mask=1«k return (val **|** mask) ```
127
Clear bit
``` def clearBit(val,k): mask= 1«k mask = ~mask # **set all other bits and clear the on** ``` return val & mask
128
Clear all bits from the most significant bit through i (inclusive).
* mask=1\< * mask=mask-1 * example 00000111 * num & mask
129
Clear all bits from i through 0 (inclusive).
mask=1«k mask=mask-1 example: **00000111** mask=~mask example: **11111000** num & mask
130
Convert binary string to decimal?
int('0010',2)
131
nonlocal vs global variable
* global: access of global variable in method * nonlocal: access to global method in nested method
132
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)
133
Check if char is number?
'A'.isdigit() False 'A'.isalpha() True '1'.isdigit() True '1'.isalpha() False
134
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, ...)
135
yield vs return
* return = single value * yield = sequence of values * yiel is used as a generator
136
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]
137
Sort list of tuples by second item?
tup.sort(key = lambda x: x[1])
138
Lamda function?
* lambda arguments : expression * **f** = lambda **x** : x + 10 * print(**f(5)**)
139
Abs value?
* abs(-3.1) =3.1 * no import reuqired!
140
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 *
141
Evaluate string expression?
* eval('2+3') * ans=5
142
Get only the bits from an integer?
* bin(1234235)[2:] * ans = '100101101010100111011'
143
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.
144
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**.
145
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.
146
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.
147
Lock vs Mutex vs Semaphore
* A lock allows only one thread to enter the part that's locked and the l**ock 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.
148
Python default threading.
* Single threaded due to GIL = Global Interpreter Lock * GIL is a mutex
149
How to do string interpolation?
* variable in brackets {} * needs the f' aprt name = **'World'** program = **'Python'** print(**f'**Hello **{name}**! This is **{program}**')
150
How to create a thread?
1. import **threading** 2. x = threading.Thread(target=**thread\_function**, * *args=(1,)**, daemon=**False**) 3. **x.start()** 4. **x.join()** -\> wait for thread to complete
151
What does Mutex stand for?
MUTual EXclusion
152
How to use a lock?
* \_\_init\_\_: self.\_lock = threading.Lock() * in methods: with self.\_lock:
153
How does a Semaphore work?
* obj=threading.Semaphore(**3**) * obj.acquire() * obj.release()
154
Binary Tree vs. Binary Search Tree?
all left descendents \<= n \< all right descendents
155
Binary Tree vs. Binary Search Tree?
all left descendents \<= n \< all right descendents
156
Balanced vs. Unbalanced Trees
One way to think about it is that a "balanced" tree really means something more like **"not terribly imbal­anced".** ## Footnote **Maybe same depth.**
157
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**.
158
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**.
159
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.**
160
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.**
161
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.**
162
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.**
163
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.
164
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.
165
Frequent errors:
* misspelled return * missing **:** * missing **self** in class method * missing plural form e.g. num instaead of num**s** * index instead of value for i in range: vs for i in nums:
166
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])
167
Ternary Operator
print("a" if True else "b") * **first the true condition**
168
a='012345' print(a[2:4])
ans= '23'
169
'str' object does not support item assignment
* a='hello world' * a[1] works ans = 'l' * a[1] = 'z' throws error
170
choice function
* import random * random.choice([1,2,3])
171
Remove key from dictionary
* my\_dict.pop('key', None)
172
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)
173
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
174
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!
175
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
176
**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
177
**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)
178
**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
179
**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
180
**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
181
**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**.
182
``` **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)
183
**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
184
Setting up n\*n matrix?
* [[0]\*3 for i in range(3)]
185
Rows and columns in Python
186
Last n letter in word?
* negative index in the front! * word[-n:]
187
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!
188
Matrix multiplication
* cols(A) \* rows(B) * result
189
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
190
Generator with conditions?
* **if** * **after 'i in arr'** * [i for i in arr if i\<4]
191
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)
192
Initialize set
* s=set() * s=set([1,2,3,4,5])
193
sort first then second
points.sort(key=lambda x: (x[0],x[1]))