algorithms-bigocoding/LT.txt at master · penguin126/algorithms-bigocoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
TIME COMPLEXITY

ARRAYLIST:
    Add: Amortized O(1)
    Remove: O(n)
    Contains: O(n)
    Size: O(1)

LINKED LIST:
    Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
    Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
    Searching: O(n)

DLINKED LIST:
    Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
    Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
    Searching: O(n)
STACK:
    Push: O(1)
    Pop: O(1)
    Top: O(1)
    Search (Something like lookup, as a special operation): O(n) (I guess so)

QUEUE:
    Insert: O(1)
    Remove: O(1)
    Size: O(1)
BST:
    Insert, delete and search: Average case: O(log n), Worst Case: O(n)

Red-Black Tree:
    Insert, delete and search: Average case: O(log n), Worst Case: O(log n)

Heap/PriorityQueue (min/max):
    Find Min/Find Max: O(1)
    Insert: O(log n)
    Delete Min/Delete Max: O(log n)
    Extract Min/Extract Max: O(log n)
    Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST

HashMap/Hashtable/HashSet:
    Insert/Delete: O(1) amortized Search: O(1)
    Re-size/hash: O(n)
    Contains: O(1)

                Best-case       Average         Worst
Selection Sort	Ω(n^2)	        θ(n^2)      	O(n^2)
Bubble Sort	    Ω(n)	        θ(n^2)      	O(n^2)
Insertion Sort	Ω(n)        	θ(n^2)      	O(n^2)
Heap Sort	    Ω(n log(n)) 	θ(n log(n))	    O(n log(n))
Quick Sort  	Ω(n log(n))	    θ(n log(n))	    O(n^2)
Merge Sort	    Ω(n log(n))	    θ(n log(n)) 	O(n log(n))
Bucket Sort	    Ω(n+k)	        θ(n+k)	        O(n^2)
Radix Sort	    Ω(nk)	        θ(nk)	        O(nk)

Linear Search   O(1)            O(n)            O(n)
Binary Search   O(1)            O(log(n))       O(log(n))

PreOrder: NLR
InOrder: LNR
PostOrder: LRN


Sr. No.	    Key     	BFS	                                                     DFS

2	Data structure	    Queue	                                                Stack
3	Source	        BFS is better when target is closer to Source.	DFS is better when target is far from source.
4	Suitablity for
decision tree	    As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games.	DFS is more suitable for decision tree. As with one decision, we need to traverse further to augment the decision. If we reach the conclusion, we won.
5	Speed	        BFS is slower than DFS.     	DFS is faster than BFS.
6	Time Complexity	Time Complexity of BFS = O(V+E) where V is vertices and E is edges.	Time Complexity of DFS is also O(V+E) where V is vertices and E is edges.


- SOLID: https://topdev.vn/blog/solid-la-gi/


3 loại ràng buộc
    - Inherent model based constraints
    - Schema based constraints
    - Application based constraints
ASSERTION: Element of database scheme => conditions that database must alwyas satify
TRIGGER is Store Procedure without params. Thuc thi khi co bien co tren DB
TRANSACTION: Neu thanh cong se commit, neu fail se rollback
INDEX: Tao chi muc de de truy van
PROCEDURE: Là một tập hơp các câu SQL có thể lấy đầu vào và gửi đầu ra


14. IDENTITY trong SQL là gì?
Một cột IDENTITY trong SQL sẽ tự động sinh ra các giá trị số tự tăng

15. NOMALIZATION – Chuẩn hóa là gì?
Quá trình thiết kế bảng để giảm thiểu sự thừa số liệu được gọi là chuẩn hóa.

- Các thuộc tính của TRANSACTION(ACID)
Tính nguyên tử (Atomicity)
Tính nhất quán (Consistency)
Cô lập (Isolation)
Độ bền (Durability)

* Phân biệt PK, UNIQUE
- Một bảng có thể có nhiều UNIQUE nhưng chỉ có 1 PK
- UNIQUE có thể chứa NULL còn PK thì không