CodingTestPractices

This is the personal repo for the coding test practices

• Python3

• Complexity

  • Note for Time Complexity:

    • O(1)< O(logN) < O(N) < O(NlogN) < O(N^2) < {O(N^3) < O(2^N)}{those are not proper algorithm for the coding test, but if N < 500, then O(N^3) is fine}

  • Note for Space Complexity:

    • For the coding test, usually limited as 128~512MB. 1MB = 1,000,000 bytes

  • Big O notation (upper bound), Big theta (middle bound), Big omega(lower bound)

  • 1< 5 loglog n < 2logn < log^2 n < 2 log^3 n < 7sqrt(n) < N(|On)< sqrt(n)logn < sqrt(n)loglogn < nloglogn < 9nlogn < n log^2 n < N^(4/3)< N^2 (|On2)< N^4 < 2sqrt(n) <2^n < 2^n^2

Concepts

Greedy

  Finding the best solution in a situation

Implementation

  - Exhaustive Search: systematically checking all possible candidates for whether or not each candidate satisfies the problem's statement.
  - Simulation: to determine the execution time of each instruction in a trace

DFS/BFS

  - Stack(LIFO), Linear Queue(FIFO) 
     - or Circular Queue, Priority Queue(Complete Bin tree(Heap))
  - Recursive Function
  - DFS(Depth-First-Search):
  - BFS(Breadth-First-Search):

Sort

Binary Search

Dinamic Programing

Shortest Path

Graph Theory