-
Practice programming and keep your brain sharp
Visualize Z Array
Txt a a a a
Txt a a a a
Z x 3 2 1 // Dont bother about x
Txt a b a b
Txt a b a b
Z x 0 2 0 // Dont bother about x
Txt a b c d
Txt a b c d
Z x 0 0 0 // Dont bother about xDP Formula From Past / Previous Occurences
DP & Past Think loop or nested loops & memo
f(n) ~ f(n-1)
f(x,y) ~ f(x-1,y-1) + f(x,y-1) + f(x-1,y)DP Formula Neighbours Derived from Center
DP & Neighbours Is BST
f(x+1,y) ~ f(x,y) Bottom ~ Neighbour
f(x-1,y) ~ f(x,y) Top ~ Neighbour
f(x,y-1) ~ f(x,y) Left ~ Neighbour
f(x,y+1) ~ f(x,y) Right ~ Neighbourvar p$t = fmt.Sprintf(%s$%s, pattern, txt)
z = ZArrayOf(p$t)
for i:=0; i<len(z); i++ {
if z[i] == len(P) {
return "P found in T"
}
}MinHeapify(Array, Pant) {
Min(L, P, R)
if MinNePant() {
Swap arr[min], arr[pant]
reCurse(arr, min)
}
}
MinHeapify(arr []int, p int) {
var l := 2*p + 1
var r := 2*p + 2
var min = p
if l <= len(arr) && arr[l] < arr[min] {
min = l
}
if r <= len(arr) && arr[r] < arr[min] {
min = r
}
if min != p {
arr[min], arr[p] = arr[p], arr[min]
MinHeapify(arr, min)
}
}fmt.Print("When DP & Recursion")
fmt.Print(" Think What Base Value To Return")
fmt.Print(" When to return 0 or 1 etc.")
fmt.Print("When DP & Recusion & Min / Max")
fmt.Print(" Max of all Combinations OR")
fmt.Print(" Min of all Combinations")
fmt.Print(" Double Check before Invoking A Combination")
fmt.Print(" Adding Condition before Invoking Might Be Wrong")// Given: str1 & str2
// Find: Minimum No of Operations to Transform str1 to str2
// Assumptions: Insert, Delete & Replace are Valid Operations
// Samples:
// amit & asmit
// amit & samit
// amit & amits
fmt.Print("Traverse Both Strings Together")
fmt.Print("Either From Left to Right or Vice-Versa")
// --
// O(3^N) runtime
//
// Optimise further via:
// 1/ memoization
// 2/ for loop instead of recursion
// --
func FindMinOps(str1, str2 string) int {
if len(str1) == 0 {
return len(str2)
}
if len(str2) == 0 {
return len(str1)
}
m := len(str1)
n := len(str2)
if str1[m-1] == str2[n-1] {
return findMinOps(str1[:m-1], str2[:n-1]) // EQUALS -- i.e. 0 Add
}
// ---
// BELOW IS WRONG !! DONT ADD CONDITIONS !!
// ---
// var i, r, d int
// if m < n {
// i = findMinOps(str1[:m], str2[:n-1]) // INSERT
// } else if m == n {
// r = findMinOps(str1[:m-1], str2[:n-1]) // REPLACE
// } else {
// d = findMinOps(str1[:m-1], str2[:n]) // DELETE
// }
return 1 + Minimum( // Add 1 Else Its 0 Always
findMinOps(str1[:m], str2[:n-1]),
findMinOps(str1[:m-1], str2[:n-1]),
findMinOps(str1[:m-1], str2[:n]),
)
}// Given: [1, 3, 5]
// Calc: No. of ways to form N from given items
// Assumption: Repetitions Allowed
// Assumption: Every Order is Unique
fmt.Print(" Derive the Formula First Then Logic")
fmt.Print(" Should Formula Use 1, 3 & 5")
fmt.Print(" Wrong Way of Thinking")
fmt.Print("How many ways to get:")
fmt.Print(" N=1")
fmt.Print(" N=2")
fmt.Print(" N=3")
fmt.Print("No Need To Find All Answers")
fmt.Print("Just Ways To Find Smallest States")
fmt.Print("Use Known Ways as Conditions")
fmt.Print("How Many Ways to Get N=4")
fmt.Print(" Add 3 to Ways_to_Get(1)")
fmt.Print(" Add 1 to Ways_to_Get(3)")
fmt.Print(" Add 5 to Ways_to_Get(0)")
fmt.Print(" Add X where X is an Arr Item")
fmt.Print(" Ways(Y) where Y is SMALL & CAN BE CALC easily")
fmt.Print("TIP: X = Each Item = Treated Exclusively")
fmt.Print("TIP: Y = Target / Final State = SMALL & KNOWN")
fmt.Print(Formula: f(4) = f(1) + f(3) + f(0)")
fmt.Print( i.e. f(n) = f(n-3) + f(n-1)")
fmt.Print("How Many Ways to Get N=6")
fmt.Print(" Add 3 to Ways_to_Get(3)")
fmt.Print(" Add 1 to Ways_to_Get(5)")
fmt.Print(" Add 5 to Ways_to_Get(1)")
fmt.Print("Formula: f(6) = f(3) + f(5) + f(1)")
fmt.Print(" i.e. f(n) = f(n-3) + f(n-1) + f(n-5)")
fmt.Print("Conditions:")
fmt.Print("1/ if n < 1 return 0")
fmt.Print("2/ if n == 1 return 1")
fmt.Print("Correct Formula: f(n) = f(n-3) + f(n-1) + f(n-5)")fmt.Print("Shortest Path: May Have Optimal Sub-Structure Property")
fmt.Print(" i.e. a Combination of Shortest Paths")
fmt.Print("Longest Path: DoNot Have Optimal Sub-Structure Property")// Given: Level Order Traversal of a Binary Tree
// Check: Is BinaryTree A MinHeap?
func IsMinHeap(arr []int) bool {
size := len(arr)
for parent:=(size-2)/2; parent>=0; parent-- {
l := 2*parent + 1
r := l + 1
if l < size && arr[parent] > arr[l] {
return false
}
if r < size && arr[parent] > arr[r] {
return false
}
}
return true
}fmt.Print("Binary Heap: Single Tree")
fmt.Print("Binomial Heap: Collection of Trees")
fmt.Print("Fibonacci Heap: Collection of Trees of Any Shape")
fmt.Print("Fibonacci Heap Property:")
fmt.Print(" All trees' root are connected")
fmt.Print(" Roots are connected via Circular Doubly Linked List")fmt.Print("Heap to Array: Level Order Traversal")
fmt.Print("Heap to Array: Zig Zag")
fmt.Print("Del Min from Min Heap: Remove & Heapify from Root")
fmt.Print("Delete from Min Heap: Replace the Val with MAX_MIN then DelMin")fmt.Print("Heapify: A recursive approach")
fmt.Print("Heap Conditions: l, r <= size & parent >= 0")fmt.Print("Heap Parent Idx:")
fmt.Print("= (childIdx-1)/2")
fmt.Print("= (len(arr)-2)/2")
fmt.Print("= len(arr)/2 - 1")fmt.Print("Heap QnA")
fmt.Print("Q: How to Ensure Lower SubTrees are Always Heapified?")
fmt.Print("A1: Start from Bottom Parent & Call Heapify (a recursive func)")
fmt.Print("A2: i.e. Loop In Reverse Order")
fmt.Print("A3: i.e. Loop from Bottom Parent To Root")
fmt.Print("Q: Why Leaf Nodes Dont Need to be Heapified?")
fmt.Print("A: Leaf Nodes Always Follow Heap property")// ----
// Given the root index heapify the tree recursively
//
// Assumption: subtrees are already heapified
// Aliter: use func instead of method
// Aliter: use []int instead of *MinHeap
// ----
func (m *MinHeap) MinHeapify(parent int) {
// ---
// Deal with indexes
// Since goal is to swap the array in-line
// ---
var l = m.Left(parent)
var r = m.Right(parent)
var smallest = parent
if l < m.Size && m.Items[l] < m.Items[smallest] {
smallest = l
}
if r < m.Size && m.Items[r] < m.Items[smallest] {
smallest = r
}
if smallest != parent {
// swap
m.Items[parent], m.Items[smallest] = m.Items[smallest], m.Items[parent]
// ---
// given index val was swapped
//
// heapify till it finds its right position
// ---
m.MinHeapify(smallest)
}
// If No Change then No Recursion
// Since SubTrees are ASSUMED to be Heapified
}// --
// Pure Function
// --
func MaxHeapify(arr []int, parent, size int) {
var l := 2*parent+1
var r := 2*parent+2
var largest = parent
// --
// Compare both Left & Right against Parent
// --
if l <= size && arr[l] > arr[largest] {
largest = l
}
if r <= size && arr[r] > arr[largest] {
largest = r
}
if largest != parent {
// --
// Array is the Heap
// No extra struct
// --
arr[parent], arr[largest] = arr[largest], arr[parent]
// --
// Recurse due to new largest
// --
MaxHeapify(arr, largest, size)
}
}// --
// Convert MinHeap to MaxHeap in O(N)
//
// Tip: Loop from "Bottom Parent" to "Root" & MaxHeapify
// Note: Ignore the leaves
// Note: This seems O(NlogN) but its O(N). HOW?
// --
func MinHeapToMaxHeap(arr []int) {
// --
// pIdx =(cIdx-1)/2, OR
// pIdx =(size-2)/2
// --
size := len(arr)
for i:=(size-2)/2; i>=0; i-- {
MaxHeapify(arr, i, size)
}
}// --
// O(NlogN) ~ O(N) - HOW?
// --
func BuildHeap(arr []int) {
if len(arr) == 0 {
return nil
}
size = len(arr)
for i:=(size-2)/2; i>=0; i-- { // N
Heapify(arr, i) // logN
}
}fmt.Print("Anagrams relevant to encode & decode")
fmt.Print("Ana enD")fmt.Print("Sum of at-least 2 numbers is k or n*k")
fmt.Print("Above Is Same As Sum of at-least 2 numbers % k == 0")
fmt.Print("(a + b)%k == 0 if (a%k + b)%k == 0")
fmt.Print("If Above Then (c + a + b)%k == c%k Since (a + b)%k == 0")
fmt.Print("When Programming Use map[int]int{0: -1} & Condition")
fmt.Print("Map's Key = 'Current Sum' & Value = 'Idx of Number In Array'")fmt.Print("2D Graph - graph [][]int")
fmt.Print("hasEdge: graph[u][v] == 1")fmt.Print("If BiPartite Graph")
fmt.Print("Then Red Blue Color Scheme @ Each Level")
fmt.Print("Visualize Graph as a Tree")
fmt.Print("If Node is Blue Then Its Neighbours in Red")
fmt.Print("If Node is Blue Then Its Neighbours' Neighbours in Blue")fmt.Print("BiPartite Graph")
fmt.Print("All Edges Joining Vertices belonging to 2 Independent Sets")
fmt.Print("If BPG[u][v] == 1 then u & v must be in different sets")fmt.Print("BiPartite Color Store")
fmt.Print("colors []int - colors[u] = -1 or 0 or 1")
fmt.Print("-1=no_color, 0=red, 1=blue")fmt.Print("Graph as 2D array vs. Adjacency List")
fmt.Print("Graph as 2D Array gives O(v^2) in BFS & other calculations")
fmt.Print("Graph as Adjacency List gives O(v+e) in BFS")
fmt.Print("Adjacency List == Sparse Graph == Space Efficient")fmt.Print("When Array of strings Then 2D Array Already")fmt.Print("When Alien Dictionary And Order of Chars is Given")
func OrderedAccess(order string) []int {
var res = make([]int, 26) // assume 26 is the max order
for i, c := range order {
res[c] = i // notice the reverse store
}
return res
}fmt.Print("When 'for loop' & use of '++' & lots of 'break' or 'continue'")
fmt.Print("Then better use 'for i:=0; i < size; i++' loop")fmt.Println("Dependency calculations use Topological Sort")
fmt.Println("Dictionary")
fmt.Println("Compilation of dependent programs")
fmt.Println("A depends on B & B depends on C")
fmt.Println("Then in Topological Sort: [C, B, A]")
fmt.Println("Ulta Topi")// ---
// EXTRA ELEMENTS CREEP IN; AVOID
// ---
var sarr = make([]int, len(arr))
for _, i := range arr {
sarr = append(sarr, i)
}
// ---
// EXTRA ELEMENTS CREEP IN; AVOID
// ---
var sarr = make([]int, len(arr))
sarr = append(sarr, arr...)
// ---
// SIMPLE OLD STYLE COPY; GOOD
// ---
var sarr = make([]int, len(arr))
for idx, elem := range arr {
sarr[idx] = elem
}// Terse; Is It Safe?
func msort(given []int) []int {
if len(given) == 1 {
return given
}
mid := int(len(given)/2)
left := given[0:mid]
right := given[mid:]
return merge(msort(left), msort(right))
}
// Vs.
// Verbose & Tricky But Perhaps Safer
func msort(given []int) []int {
size := len(given)
if size == 1 {
return given
}
mid := int(size/2)
var left = make([]int,mid)
var right = make([]int,size-mid) // WATCH OUT
for idx, item := range given {
if idx < mid {
left[idx] = given[idx]
} else {
right[idx-mid] = given[idx] // WATCH OUT
}
}
return merge(msort(left), msort(right))
}str[idx] // bytes
rune(str[idx]) // runestr[left:right+1] // SUBSTRING; LEFT & RIGHT INCLUDED
str[left:right] // RIGHT EXCLUDED// map[int]bool as seen
// map[rune]bool as seen
// TIP
// WHEN TO RESET
// RESET TO WHAT?
// - EMPTY?
// - SINGLE ELEMENT?
// - CURRENT ELEMENT?// ^ IS NOT POWER
// ^ IS XOR
// ^ IS BITWISE XOR OPERATOR FOR INTEGERS// rune is an alias for int32
fmt.Println("RUINED INTERNATIONAL MAN")// byte is an alias for unit8
fmt.Println("BYE TO UNIFY")// unit ; all positive numbers including 0
// uint ranges from 0 to 4294967295
// int ranges from –2147483648 to 2147483647// MAX INT = HALF OF MAX UNIT
// MIN INT = -(HALF OF MAX UNIT) - 1
var MinUint uint = 0
var MaxUint uint = ^MinUint // all ones
// Divide by 2
// i.e. arithmetic right shift
var MaxInt int = int(MaxUint >> 1) // all ones except high bit
// Either ^MaxInt
// OR -MaxInt-1
var MinInt int = ^MaxInt // all zeros except high bit
fmt.Println("TRY TO EAT BUFFET. YOU CAN'T. YOU END UP DIVIDING BY HALF")
fmt.Println("BUFFET EATS YOU. HE CAN. HIS MONEY GETS DOUBLED I.E. 2X")// ARRAY MUTATION
size := len(arr) // SOME ARRAY
top := arr[size-1] // TOP IS LAST ELEMENT
arr = arr[:size-1] // REMOVE LAST ELEM// BST ITERATOR - O(h) space - h is tree's height
// STORE ROOT && THEN LEFT NODES(s)
// I.E. STORE IN DESC ORDER
// IS ENOUGH TO PROVIDE ENTIRE TREE AS INORDER LIST
// NEXT() LOGIC IS TEASER
type BSTIter struct {
Stack []*BST
}
// ---
// push is the teaser function that
// helps you build a BST with O(h) space
// ---
func (i *BSTIter) push(b *BST) {
tmp := b
for tmp != nil {
// -------------------
// Store in DESC order
// -------------------
i.Stack = append(i.Stack, tmp)
tmp = tmp.Left // JUST THE LEFT
}
}// Product of Array Items Excluding Current
// --------
// HINT:
// --------
// - Loop 1 - L to R
// - Product All Lefts i.e. Already Seen Items
// - Loop 2 - R to L
// - Product All Rights i.e. Already Seen Items
// - Use a New Array that Stores Above Product
// - Loop 1 - Arr[idx] = Current Left Product
// - Loop 2 - Arr[idx] = Arr[idx] * Current Right Product
// TIP - Product Excluding Self is Two loops Two Directions Solution// Diameter of Binary Tree is all about maximums
// Having a maximum func helps a lot
func maximum(a, b int) int {
if a > b {
return a
}
return b
}// MaxSumPath of BinaryTree is mad about max
// Avoid initialising to Min Int etc
func maximum(first int, others ...int) int {
var max = first
for _, i := range others {
if max < i {
max = i
}
}
return max
}