To learn
bisect moduleBelow is a collection of (technical) tips for coding interviews. This list is based on my experience and might not be exhaustive.
[0] * n
[[0] * cols for _ in range(rows)]
l = []
l.index('foo')
l[start:end] where start is inclusive and end is exclusivel[-1]
M * N has M + N - 1 diagonals-i + j or i + j, depending on the direction and then added to a map / dict.p2 and then check for violation of constraints. Afterwards advance the pointer p1 until the violation is resolvedrange(start, stop, step) has start inclusive and stop exclusivearr = [1,2,3,4]
item = 3
def search(arr, item):
left = 0
right = len(arr) - 1
while left <= right:
middle = (left + right) // 2
if arr[middle] == item:
return middle
if arr[middle] > item:
right = middle - 1
else:
left = middle + 1
return -1
search(arr, item)def sliding_window(arr):
idx_start = 0
for idx_end in range(len(arr)):
# Condition to stop the sliding window
if arr[idx_end] == 5:
condition = True
# Move start pointer
while condition:
if arr[idx_start] == 5:
condition = False
idx_start += 1
# idx_start is now on the conditionTrue + True + False == 2
l.pop(0), otherwise l.pop() pops the last item.sortedcontainers.SortedList is a special (open-source) implementation of a sorted listdict
d = collections.defaultdict(list) provides a dictionary with a factory method
d['missing_key'].append(...) to append to a missing keys = set()
list(s)[0]
intersect = a & b
union = a | b
dict.keys()
l.append(item) to add a new item to the stackl.pop() to return and remove an item from the stackpop will return an IndexError if no item is on the stack, it should be checked before callingord('a')
ord('a') - ord('b')
ord('a') - ord('z') == -25 % 26 == 1 == ord('b') - ord('a')
s.isdecimal() returns true if s is a decimal numbers.isalnum() returns True if s is alphanumeric [0-9a-z]
heapq library which implements a min-heap
heapq.heappush(heap, item)
heapq.heappop(heap)
heap[0]
O(n * log n)
O(log n)
pow(2, height) - 1
h = log2(n)
import collections
graph = collections.defaultdict(list)
def build_graph(cur, parent):
if cur and parent:
graph[cur.val].append(parent.val)
graph[parent.val].append(cur.val)
if cur.left:
build_graph(cur.left, cur)
if cur.right:
build_graph(cur.right, cur)
build_graph(root, None)def cloneGraph(node: Optional['Node']) -> Optional['Node']:
# Handle edge case
if node is None:
return None
# Define queue with the root node
q = [node]
# Memorize visited nodes
m = {node.val: Node(node.val)}
# Clone root node
node_clone = m[node.val]
while len(q) > 0:
curr = q.pop(0)
# Clone the node if not already cloned
if curr.val in m:
curr_clone = m[curr.val]
else:
curr_clone = Node(curr.val)
m[curr.val] = curr_clone
for neighbor in curr.neighbors:
if neighbor.val not in m:
n = Node(neighbor.val)
m[neighbor.val] = n
q.append(neighbor)
curr_clone.neighbors.append(m[neighbor.val])
for node in m.values():
print(node.val, node.neighbors)
return node_cloneVisit the current node. Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.
Recursively traverse the current node’s left subtree. Recursively traverse the current node’s right subtree. Visit the current node. Post-order traversal can be useful to get postfix expression of a binary expression tree.
Recursively traverse the current node’s left subtree. Visit the current node. Recursively traverse the current node’s right subtree. In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.[7]
queue, stop when queue is emptydirections = [[1,0], [0,1], [-1,0], [0,-1], [1,1], [-1,-1], [1,-1], [-1,1]]
queue = [(node1, distance1)] to find nodes within a distance from origin. Important to keep track of visited = set() nodes to avoid loopsn from target nodeShort for retrieval tree.
Example Python implementation
# TODO37^100 is 37 * 37^99 is 37^50 * 37^50, Thus we only have to compute the left part and need log2(100) iterations. This is useful for implementing pow(x,y)
random.choice(list) to pick a random element from a listthreading.Semaphore(n) provides a semaphore with n capacity that can be used via acquire() and release()
threading.Barrier(n) provides a barrier where all threads have to wait() until the capacity is reachedresponse = requests.get('https://github.com/timeline.json')
print(response.json())response = requests.post('https://github.com/timeline.json', headers={}, data={}, json={})
print(response.json())/companies, /companies/1)GET, PUT, POST, DELETE)