Please enable JavaScript.

Coggle requires JavaScript to display documents.

LeetCode Python - Coggle Diagram

- - - - HashTable (dictionaries)/maps: O(N)
      - 2d array: O(NM)
  - - - Bao nhiêu assignment
      - bao nhiêu phép tính
      - if the number of operator needed DOESNT depend on the size of the ARRAY
        
        The time complexity O(1) - Constant
        
        hạn chế loop vì nó có thể đưa O lên O(n)
  - - - O(aN+b) = O(N)
      - O(5N^2+3N+1) = O(N^2)
- - - - Examples: National ID, Student ID
      - Ứng dụng Tìm kiếm số lần lặp lại của một dãy nào đấy
      - Value and Key
        
        Key: unique, hashable
        
        Value: repetitive, objects
      - Ứng dụng so sánh 2 object lớn, so sánh hai giá trị Hash vì H(x) != H(y) => x!=y
    - - Take a string of char (called a key) and maps it to a value with a certain length (called a hash)
      - A good hash fuction
        
        Easy to compute
        
        Uniform distribution
        
        Low collision
      - Better hash function: instead of sum, multiply each value with its respective indeces
      - h(x) = (x^2+2x+1)mod10
        
        luôn trả ra value [0,10]
        
        Map key thi nhan duoc index trong 1 range nhat dinh
    - - 2 values have a same key
      - Chaining
        
        Make each cell of the table link to a LinkedList
        
        easy to implement but extra spaces
        
        Search time can become O(N)
        
        Ads
        
        Hashtable never full
        
        Cache performance is not good
        
        used when numbers of keys are unknown
      - Open Addressing
        
        Values are stored in the hash table
        
        Gặp 1 đứa trùng key thì tìm ô tiếp theo để đút vào
        
        Linear Probing
        
        Quadratic probing
        
        Double hashing
        
        ads
        
        Not easy to implement
        
        Hash tables can get full
        
        better cache performance
        
        Frequencies and numbers of keys are not known