DFS explores every subtree until it hits a dead end before switching to another path. It can be done recursively, or it can be done iteratively. Let’s reuse the TreeNode definition from our BFS post. 1. Recursive Solution The recursive approach achieves O(n)O(n) time in the worst case, O(logn)O(\log n) space in the best case,… Continue reading Depth-First Search (DFS)
Binary Heap
A binary heap is a complete binary tree that maintains the heap property: every parent is either less than or equal to its children (min-heap), or greater than or equal to its children (max-heap). Binary heaps are commonly used to implement priority queues (an abstract data type that finds its highest-priority item in O(1)O(1) time),… Continue reading Binary Heap
Breadth-First Search (BFS)
Suppose you’re given a binary tree implemented somewhat like this: Breadth-First Search (BFS) means you traverse the tree level by level, not diving deep into a child node every chance you get. The blocker here is not knowing how to link all nodes belonging to the same level, because in a binary tree, same-level nodes… Continue reading Breadth-First Search (BFS)
Binary Search
Binary Search I know, the word binary screams binary tree. But no, binary search doesn’t require a tree at all. It’s usually implemented in an array. In Go, we can simply use a slice to do this. Note that a binary search can only be performed on a sorted array. The generic signature [S ~[]E,… Continue reading Binary Search
Copying slices in Go
As we know, Go slices hover on top of fixed arrays; modifying elements in a slice also modifies the underlying array. In some scenarios, that’s unacceptable. Hence, we need slice copying! 1. Use slices.Clone slices.Clone is available from Go 1.21 onward. What’s cool about it is that it takes care of the pre-allocation of space… Continue reading Copying slices in Go
Stack & Queue in Go
1. Stack This is your good ol’ LIFO (last-in, first-out) structure. Just imagine a Pringles tube. A basic stack should have the following methods: In Go, you can use a slice as the underlying data structure. Notice how initiating the store slice in the NewStack[T any]() constructor is optional? This is because we have enough… Continue reading Stack & Queue in Go
Sorting a slice in Go
1. The slice Package If your Go package is anything newer than 1.21, and the items in the slice are of the cmp.Ordered type, you should definitely use the slice.Sort() function. It only works if you intend to sort it in place and in ascending order, though. So if we want to sort something in… Continue reading Sorting a slice in Go
Frequency map in Go
A frequency map is just a fancy word for a hash map that tracks the number of occurrences of an element in a collection. If we have a slice in Go and we want to know exactly how many times each element in the slice occurs in the slice, we can build a frequency map… Continue reading Frequency map in Go
Map-as-Set in Go
In programming languages like Go, there is no built-in type for set. A set essentially answers yes or no: is a given element present? We can use the built-in map type to implement sets. I used to implement map-as-set like this: Apparently, Gemini thinks there’s a better way: Gemini thinks this is better because it… Continue reading Map-as-Set in Go
KompacPlus
KompacPlus is marketed as a counter top material, and sometimes wall material. The sellers often claim it’s comparable to quartz and sintered stone. KompacPlus is made in Italy, but only sold in Singapore and Malaysia. It’s essentially “made from layers of resin-soaked kraft paper” and compressed with extremely high heat and pressure. It’s non-porous, somewhat… Continue reading KompacPlus