-
Notifications
You must be signed in to change notification settings - Fork 0
/
notes.txt
107 lines (95 loc) · 3.52 KB
/
notes.txt
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
103
104
105
106
107
Algorithms:
Notations:
Big O Notation: Upper Bound
Θ Notation: Average
Ω Notation: Lower Bound
Searching:
Linear -> Search with all element -> O(n)
Binary -> Skip half of the array -> O(Log n)
Jump -> Skip with blocks -> O(√n)
Interpolation -> Like binary but compute position -> O(log log n)) -> Worst case O(n)
Extrapolation -> Identify the range and recursive binary search -> O(Log n)
Sorting:
Selection -> Sort by index -> O(n^2)
Bubble -> One Iteration for each element -> O(n^2)
Insertion -> Sort new element on its index -> O(n*2)
Heap -> -> O(n log(n))
Shortest Path:
Using Greedy Algorithm:
Dijkstra’s shortest path algorithm
Prim’s Minimum Spanning Tree
------------------------------------------------------------------------------------------------------------------------
DS:
Array:
Rotation:
M1: Using temp array
Time complexity : O(n)
Auxiliary Space : O(d)
M2: Rotate one by one
Time complexity : O(n * d)
Auxiliary Space : O(1)
M3: Juggling Algorithm (GCD)
Time complexity : O(n)
Auxiliary Space : O(1)
M4: Reversal Algorithm
Time Complexity : O(n)
------------------------------------------------------------------------------------------------------------------------
Linked List:
Type:
Single, Double, Circular
------------------------------------------------------------------------------------------------------------------------
Queue:
Enqueue: Add item to queue
Dequeue: Remove item to queue
Types:
Priority -> Element with priority -> O(n)
------------------------------------------------------------------------------------------------------------------------
Trees:
Types:
Binary Tree:
Properties:
******************* Brush Up *******************
Types:
Full (0, 2 Childrens)
Complete (All level are filled and leaves are toward left)
Perfect (Leaves at same level and all intermediate nodes filled)
Balance (Height is O(Log n) - Difference of right and left subtree is 1)
Binary Search Tree:
Left sub tree: Lesser than root node.
Right sub tree: Greater than root node.
Left and Right should also be a binary search tree.
Traversal:
Time Complexity: O(n)
Space Complexity:
BFS: More (When tree is more balanced)
DFS: More (When tree is less balanced)
BFS (Breadth First Search)
Root, Left, Right
Desc:
Start searching from Root.
Maximum width of Binary Tree at Dept 'h' is 2^h
Space Complexity:
O(w), w: maximum width of the tree
Queue:
Stores intermediate nodes
DFS (Depth First Search)
Desc:
Start searching from Leaves.
Space Complexity:
O(h), h: maximum height of the tree
Stack:
Stores intermediate nodes
Types:
Inorder (Left, Root, Right)
Preorder (Root, Left, Right)
Postorder (Left, Root, Right)
Factor to decide:
Extra Space
Recursive method calls
Root to leaves / Leaves to root
------------------------------------------------------------------------------------------------------------------------
Graph:
Adjacency Matrix
Adjacency List
Vertex(Node), Edge(Connection Line)
------------------------------------------------------------------------------------------------------------------------