Please enable JavaScript.

Coggle requires JavaScript to display documents.

fb screening - Coggle Diagram

- - - - start at root node (some node for graph) and explore through branch before backtracking
      - use stack
      - find destination
      - game / puzzle
      - O(V + E), V = vertices, E = edges
        O(V^2) if adjacency matrix is used
      - when el is far from source
    - - use queue
      - find shortest path
      - O(V + E), V = vertices, E = edges
        O(V^2) if adjacency matrix is used
      - when el is close to source
    - - looking for an X in an N-element sorted array
    - - merge sort
      - quick sort O(n * log(n))
        
        divide-and-conc
        
        pick pivot point
        
        ensure elements to the left are less than pivot
        
        ensure elements to the right are bigger than pivot
        
        apply algorithm to both parts recursively
      - selection sort O(n^2)
        
        divide to two parts: sorted and unsorted
        
        find least one in unsorted, move to sorted, etc.
      - insertion sort O(n^2)
        
        start -> end, pick an element
        
        find a place in the left (sorted) part of an array:
        
        find the index of the last element that is less and insert the current element after it (or swap 1-by-1)
      - heap sort O(n * log n)
        
        like selection: sorted and unsorted regions
        
        unsorted region = heap
        
        root of the heap = max elem, swap last elem and root, rebuild the heap, repeat
    - - search
      - insert
      - update
      - delete
  - - - disjoint set
        
        keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets
        
        for vertexes V and edges E
        store array of 'parents' and 'ranks': array index of parent element of the current element. Eventual top-level parent is a representative of a set.
        representative may be initially picked by biggest node value or index. E.g. for edge [1,2] it's 2
        
        union-find
        find = traverse through the parents to the top one + store a link to the top paren in the entry of interest
        union = find parents of each of the two nodes and set the same parent by rank.
        
        applications:
        
        search for a loop in an undirected graph
    - - tree-based
        
        P = parent, C = node
        
        min heap: P key <= C key
        
        max heap: P key >= C key
      - implementation of priority queue
      - complete tree = has smallest possible height
      - array, each elem = node
        
        parent / child defined by index
        
        node index i => children are (2i + 1) and (2i + 2); parent at floor((i - 1) / 2)
      - needs to be re-balanced (sift-up, sift-down)
      - application: find X min / max elements
    - - b-tree = generalization of binary search tree:
        
        search, access, insert, delete = O(log N)
        
        self-balanced
      - binary search tree:
        
        node's value greater than values in the left subtree
        
        node's value is less than values in the right subtree
    - - slow-fast pointers
        
        dummy node
  - - - stack (recursion)
      - memory usage (number of elements in arrays, etc)
    - - divide steps by K: O(logN), k is log base
      - recursively call branches:
        O(branches ^ depth)
      - 2 different inputs = both sizes matter
      - pick dominant:
        
        O(N + logN) = O(N)
        
        O(N + N/2) = O(N)
      - quick sort: O(N * logN)
      - string comparison: O(N)
  - - - permutations / перестановки
        порядок важен
        
        без повторений
        P из n по k:
        n! / (n - k)!
        
        Heap's alg
        https://en.wikipedia.org/wiki/Heap%27s_algorithm
        
        swap curr elem with each, push to result set
        for each elem in result set: curr + 1 and do the same
        alg can be both recursive and non-recursive
        
        с повторениями
        P из n по k:
        n^k
      - combinations / сочетания
        порядок не важен
        
        без повторений
        есть n объектов, хотим выбрать k из них
        C из n по k:
        n! / (k! (n - k)!)
        C из n по k = C из n-1 по k + C из n-1 по k-1
        
        с повторениями
        (k + n - 1)! / (k! * (n - 1)!)