【Algorithm】 Coding test/interview

18 Apr 2022 in Ubuntu / Language / Algorithm

• 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 = [ [0]*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

• Linked structure: (1) Key(data) / (2,3) left+right child address / (4) parent address
• 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.
  • Additional properties
    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]
  • BFS (Breadth-First Search)
    • 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