Python Flashcards
Data Structure: deque
import
from collections import deque
Data Structure: deque
method(s): append & appendleft
usage with space & time complexity
append(val) & appendleft(val) - adds item
Time: O(1)
Space: O(1)
Data Structure: deque
method(s): pop & popleft
usage with space & time complexity
pop() & popleft() - removes and returns item
Time: O(1)
Space: O(1)
Data Structure: deque
method(s): index
usage with space & time complexity
index(ele, beg, end) - returns first index of value
Time: O(n)
Space: O(1)
Data Structure: deque
method(s): insert
usage with space & time complexity
insert(i, a) - This function inserts the value mentioned in arguments(a) at index(i) specified in arguments.
Time: O(n)
Space: O(1)
Data Structure: deque
method(s): remove
usage with space & time complexity
remove(val) - This function removes the first occurrence of the value mentioned in arguments.
Time: O(n)
Space: O(1)
Data Structure: deque
method(s): count
usage with space & time complexity
count(val) - This function counts the number of occurrences of value mentioned in arguments.
Time: O(n)
Space: O(1)
Data Structure: deque
method(s): extend & extendleft
usage with space & time complexity
extend(iterable):- add multiple values at the right end of the deque.
extendleft(iterable):- add multiple values at the left end of the deque. Order is reversed as a result of left appends.
Time: O(K)
Space: O(1)
Data Structure: deque
method(s): reverse
usage with space & time complexity
reverse():- This function is used to reverse the order of deque elements.
Time: O(n)
Space: O(1)
Data Structure: deque
method(s): rotate
usage with space & time complexity
rotate():- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to the left. Else rotation is to right.
Time: O(K)
Space: O(1)
Data Structure: OrderedDict
import
from collections import OrderedDict
Data Structure: OrderedDict
method(s): get item
usage with space & time complexity
dict[key] - returns value
Time: O(1)
Space: O(n)
Data Structure: OrderedDict
method(s): set item
usage with space & time complexity
dict[key] = value
Time: O(1)
Space: O(n)
Data Structure: OrderedDict
method(s): popitem
usage with space & time complexity
popitem() - used to delete an item from the beginning
popitem(last=True) - used to delete an item from the end
Time: O(1)
Space: O(n)
Data Structure: OrderedDict
method(s): move_to_end
usage with space & time complexity
move_to_end(key, last = True) - move an existing key of the dictionary in the end or beginning
Time: O(1)
Space: O(1)
Data Structure: LifoQueue
import
from queue import LifoQueue
Data Structure: LifoQueue
method(s): instantiate
usage
queue = LifoQueue(maxsize=3)
Data Structure: LifoQueue
methods
qsize() - gets the max size of the stack
get() - gets the latest element on the stack
put(val) - adds an element on the stack
full() - displays if the stack is full
empty() - displays if the stack is empty
Data Structure: List
array concat/extend with space & time complexity
”+” method - O(n) space & time where n is all items in both lists
extend() - appends multiple items in O(n) time, where n is the new list items
Data Structure: List
method(s): copy
usage with space & time complexity
array.copy() - move an existing key of the dictionary in the end or beginning
Time: O(n)
Space: O(n)
Data Structure: List
method(s): append
usage with space & time complexity
array.append(val) - adds item to end of array
Time: O(1)
Space: O(1)
Data Structure: List
method(s): pop
usage with space & time complexity
array.pop(i) - removes item from end of array or at specific index
Time: O(1) at end or O(n) intermediate
Space: O(1)
Data Structure: List
method(s): insert
usage with space & time complexity
array.insert(i, val) - inserts an item at the specified position in the array
Time: O(n)
Space: O(1)
Data Structure: List
method(s): remove
usage with space & time complexity
array.remove(val) - removes the first matching item in the array
Time: O(n)
Space: O(1)
Algorithm: bubble sort
steps with space & time complexity
while loop with pointer at end
iterate over the array until the pointer
swap elements to “bubble up” the highest value to the end
move the pointer inward
Time: O(n^2)
Space: O(1)
Algorithm: cycle sort
steps with space & time complexity
while loop with pointer at start
value corresponds to the expected position
if the value is not equal its expected, then swap
Time: O(n)
Space: O(1)
Algorithm: select sort
steps with space & time complexity
- 2 pointers to track progress
- track smallest, starting with assumption of first value
- compare the value with the next value
- if its less, then swap
- if less than smallest, update that
- if the pointer is at the end, move smallest to start, update progress pointers, and reset smallest
Time: O(n^2)
Space: O(1)