# 【Algorithm】 Coding test/interview

• Coding test/interview

# Python

1. mutable vs Immutable [post1]
1. import copy
2. 메모리 공유 (1) =
3. 딕,리스트 내부 딕 리스트는 메모리 공유 (2) .copy(), copy.copy(), [:]
4. 딕,리스트 내부 딕 리스트까지 메모리 재할당(3) copy.deepcopy()
2. Initializing a two-dim list: a = [ *3 for i in range(3)]
3. collections.namedtuple, collections.deque
4. copilot 사용법:
1. Let the copilot know what types of methods or strategies to use exactly. E.g. “Check if the list is repeating using a set of names.”
2. Ask the copilot step by step. E.g.\ [No] # return the player at the given rank ⇒ \ [YES] (1) #Sort self.standings by score, then games_played (2) #return the player at the given rank

# 1. Recursion

• recursive function: a function calls itself.
• Base case: to stop the recursion
• Recursive case: where the function calls on itself
• Examples
• Easy: Factorial, Fibonacci number, Euclid method
• Hard: Towers of Hanoi, Maze, Cells in a Blob, N-Queens, Permutation
• Any problem solved recursively can also be solved through the use of iteration.
• 🪡 Binary search
• Finding a needed item from a sorted list, from the right or left. [[logN, bisect]
• left right valuable → calculate middle and use it → break when (left≥right)
• 🪡 Backtracking: (1) non-promising:fail (2) success:return (3) visit recursion.
• 🪡 State-space tree

# 2. Sort

• Selection sort
• Find the largest value in the list.
• Bubble sort
• left to right. Push back a larger one among 2 items. x N times
• Insertion sort
• left to right. The item finds its position in the its-left list.
• Merge sort
• not in-place
• divide and conquer
• mergesort(left) / mergesort(right) / merge
• Quick sort
• in-place
• pivot
• From the left, find an item smaller than the pivot. From the right, find an item larger than the pivot.
• Heap sort
• in-place
• Max heap / Min heap / complete binary trees / Max-heapify(: only top node is positioned incorrectly according to max-heap rules)
• Main operation:
1. Build heap: From non-leaf (internal) node, apply max-heapify.
2. Insert: bottom 2 top
3. Delete: Delete top node. Last leaf node is placed on the top. Compare top 2 bottom

# 3. Search tree

• Tree traversal
• Recursively: Inorder(left root right) / Preorder(root left right) / Postorder (left right root)
• Binary search tree (=ordered tree)
• Definition: 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.
• (oper1) Search: O(hight=logN), min(leftmost), max(rightmost), Successor, Predecessor
• (oper2) Insert: O(hight=logN), Just need to find empty leaf.
• (oper3) Delete: if the number of child node is 0,1, no problem. But if that is 2, need to find successor
• Weakness: worst-case → O(N) → Keep balanced → red-black tree
• Red-black tree
• It is a kind of Binary search tree.
1. Every node is either red or black.
2. All NIL nodes (leaf node + root node) are considered black.
3. A red node does not have a red child. (Red can not exist consecutively)
4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes. [Example image]
• h: Hight from itself to NIL - bh: From itself to NIL, the number of black nodes (including itselfs)
• Left and Right rotation are key operations when doing Search, Insert, Delete.

# 4. Hasing

• Hash table: Key and value
• Solutions of Collision:
• Chaining (linked list): worst-case → value unbalance problem
• Open addressing (Finding other empty space)
1. linear probing: h(key) + i. Clustering problem
2. quadratic probing: h(key) + i^2
3. double hashing: use two different hash functions
• A critical problem of the above methods is the difficulty to delete & search.
• Good hash function is an almost random distribution function.

# 5. Graph - DFS,BFS

• Node, Edge, and adjacency matrix.
• Graph traversal [Reference image]
• Queue: [pseudo code] (1) While queue is not empty (2) Remove a node v (3) For each unchecked neighbor w_s of v (4) Insert w into the queue and check it.
• Shortest path [pseudo code]: Needed valuables are d (distance) and π (predecessor, previous node).
• DFS (Depth-First Search)
• Recursive: [pseudo code] (1) DFS(G,v) (2) Check v (3) For each adjacent nodes w_s (4) If unchecked w, DFS(G,w)

# 6. Graph2 - Minimum spanning tree

• Node, Edge, Weight(cost) → To connect all nodes, select minimum edges with minimum cost.
• Properties: (1) non unique solution (2) non-cycle (3) edges of solutions can represent tree-structure (4) # edges = 1-#nodes
• Generic MST algorithms
• Goal: Finding a safe edge, which can be contained to A (one MST solution)
• Prerequisite: (1) Cut: 2subset S, V-S of nodes (2) Cross: edge cross 2subset (3) Respect: no cross edges in A
• Fact: If A is a subset of MST, the lightest edge, among edges cross the cut, respect A.
• Kruskal algorithm
• Method: Sorted edges are sequentially selected, unless the edge makes a cycle, untill #nodes-1 == #edges.
• Proof: Sorting = the lightest edge / no cycle edge = Cross edge
• Key: checking whether a cycle exists. (1) Connected nodes represent a subset, e.g. [{a},{b,c,f},{e},{g,h}] (2) Using linked list, check wheter the root is same.
• Prim algorithm
• Method: From a random node, select the lightest cross-edge.
• Key: finding cross-edge: nodes in subset V-S need to contain two valuable, key and pie. ‘key’ is the lightest weight connecting with nodes in S. ‘pie’ is the connected node in S.
• Details: (1) Among nodes in V-S, find a node with the lightest ‘key’ value. (2) the node is inserted into S, nodes in V-S connected to the node update the value of ‘key’ and ‘pip’.
• Addition: Methods(1) needs to use Priority Queue (= min-heap, max-heap), so that the MST whole complexity is changed from O(n^2) to O(NlogN).

# 7. Shortest path

• Note: Path is different from Tree. MST is to find a tree with minimum cost. Dijkstra aims to find a path with minimum cost in a directed graph.
• Basics
• Properties: (1) sub-path inside the lightest path is also the lightest. (2) No-cycle
• Needs available: (1) d[node]: initialized ‘inf’, distance from the start node s. (2) π[node]: predecessor
• Basic operation: Relaxation (if finding a better path, update d and π)
• Bellman-ford algorithm
• If there are negative weights.
• [Example image] O(n*m) is too big. Thus, Dijkstra does not depend on m!
• Dijkstra algorithm
•  Assume that there is no negative weight. Checked node is never checked again.
• In a set of unchecked nodes, a node with minimum d[node] must be the node for the next step. [reference image]
• [Pseudo code]

# 8. Dynamic programming

1. Key
1. Building recursive equation.[Example image]
2. Problems can divide into sub-problems. The optimal solution of sub-problem is a part of the Optimal solution to the entire problem.
3. Memoization (For overlapped sub-problem)
4. Bottom-up