-
Notifications
You must be signed in to change notification settings - Fork 1
/
Notes
46 lines (34 loc) · 1.57 KB
/
Notes
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
1. check for odd number => int_variable & 1
2. key in sorting:
a = [[1,2], [3,10]]
# sort array with second index
print(sorted(a, key=lambda x: x[1]))
# sort array with both index
print(sorted(a, key=lambda x: (x[0],x[1])))
# sort dictionary --- sorted function returns only the sorted order of keys
1. by key(default) -> sorted(dict)
2. by value -> sorted(dict, key = lambda x: dict[x])
3. by value and then key ->sorted(dict, key = lambda x: (dict[x], x))
3. (2n!)/((n+1!).n!) => no of unique bsts catalan formula
4. prefix sum:
sum=0 subarray => prefix sum becomes zero or repeat again
5. Binary Search: mid = l + (r - l) // 2 -------> formula to find mid in binary search
6. palindrome condition ---> number of characters with odd number of occurences <= 1
7. Tree types:
1. Balanced -> (max ht - min ht) <= 1
2. Full -> no nodes with single child
3. complete -> All nodes except for the level before the last must have 2 children.
All nodes in the last level are as far left as possible.
4. perfect -> (max ht - min ht) = 0 and leaves should be filled completely
8. Tree properties:
If heap or any complete tree is stored as array
1. range of leaves -> n // 2 to n - 1
2. range of internal nodes -> 0 to n // 2 - 1
3. left child -> 2*i + 1
4. right child -> 2*i + 2
5. parent -> ceil(i / 2) - 1
6. no of internal nodes = no of leaves - 1
ht = floor(log2 N), n = no of nodes
if height = ht (0 indexed),
max nodes at h -> 2**h
max nodes in the entire tree -> 2**(h + 1) - 1