Neetcode questions:
Arrays and Hashing
| problem | code | solutions | my notes |
|---|---|---|---|
| 🟢 Contains Duplicate | php | hash map or hash set | |
| 🟢 Valid Anagram | py | hash map or sort string | |
| 🟢 Two Sum | go | hash map | |
| 🟡 Group Anagrams | py | hash map or sorted string | |
| 🟡 Kth Largest Element in an Array | go | sort or heap queue or quick select or counting (bucket) sort | ⭐ |
| 🟡 Top K Frequent Elements | go | hash map + heap queue or quick select or counting (bucket) sort | ⭐⭐ full of ds, good for interview |
| 🟡 Product of Array Except Self | go | array | |
| 🟡 Valid Sudoku | go | ||
| 🟡 Encode and Decode Strings | py | encoding and decoding concepts | implementation, encode, decode |
| 🟡 Longest Consecutive Sequence | go | hash set, implementing range with hash map | ⭐⭐⭐ creative solution |
Leetcode questions:
Array / String
Hash Map / Set
| problem | code | solutions | my notes |
|---|---|---|---|
| 🟢 Find the Difference of Two Arrays | go | ||
| 🟢 Unique Number of Occurrences | go | ||
| 🟡 Determine if Two Strings Are Close | go | ||
| 🟡 Equal Row and Column Pairs | go |
Cracking the coding interview questions
(Chapter 1: Arrays and Strings)
| problem | leetcode problem | code | solutions | my notes |
|---|---|---|---|---|
| ⚠️ 1.1 Is Unique | 🟢 217. Contains Duplicate | php (hash map) | ||
| 1.2 Check Permutation | 🟢 242. Valid Anagram, 567. Permutation in String | python | ||
| 1.3 URLify | ||||
| 1.4 Palindrome Permutation | 🟢 266. Palindrome Permutation | |||
| 1.5 One Away | 🟡 161. One Edit Distance, 🟡 72. Edit Distance |
python (top-down DP), python (bottom-up DP) | ||
| 1.6 String Compression | 🟡 443. String Compression | |||
| 1.7 Rotate Matrix | 🟡 48. Rotate Image | python | ||
| 1.8 Zero Matrix | 🟡 73. Set Matrix Zeroes | python | ||
| 1.9 String Rotation | 🟢 796. Rotate String | go |
covered data structures and algorithms:
- hash map
- hash set
- sorting
- heap
- quick select
- quick sort
notes:
sorting for arrays with limited value range
- when the range of numbers are limited compared to the count of numbers, instead of sorting the array you can create another array with length of all the element’s range and put the elements in those (kind of like the bucket sort).
freq = [[] for i in range(len(nums) + 1)]
// instead of sorting the key_value array based on their value
for n, c in key_value.items():
freq[c].append(n)
heap queue in go
you can use container/heap package for using the heap queue. however you have to implement the heap interface which is
as follows:
package main
import (
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
// create a new intHeap instance
nums := &IntHeap{3, 1, 4, 5, 1, 1, 2, 6}
// The Init function reorders the numbers into a heap
heap.Init(nums)
// The slice is now reordered to conform to the heap property
fmt.Println(nums)
// Pop the minimum value from the heap
min := heap.Pop(nums)
fmt.Println("min: ", min, " heap: ", *nums)
}
quick sort and random quick sort
both quick sort and quick select use a function named partition which takes an index named pivotIndex, and returns
the true index of that element.
function partition(list, left, right, pivotIndex) is
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right − 1 do
if list[i] < pivotValue then
swap list[storeIndex] and list[i]
increment storeIndex
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
the difference between quick sort and random quick sort is that the pivotIndex in quick sort is the first index of the
array while in random quick sort it’s random
// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function quickSort(list, left, right) is
if left = right then // If the list contains only one element,
return list[left] // return that element
pivotIndex := ... // select a pivotIndex between left and right,
// e.g., left + floor(rand() % (right − left + 1))
pivotIndex := partition(list, left, right, pivotIndex)
return select(list, left, pivotIndex − 1, k)
return select(list, pivotIndex + 1, right, k)
quick select
it’s like quick sort, with the difference that after finding the pivotIndex, we only partition one of left or right
parts, which we want the kth element to be in
// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function select(list, left, right, k) is
if left = right then // If the list contains only one element,
return list[left] // return that element
pivotIndex := ... // select a pivotIndex between left and right,
// e.g., left + floor(rand() % (right − left + 1))
pivotIndex := partition(list, left, right, pivotIndex)
// The pivot is in its final sorted position
if k = pivotIndex then
return list[k]
else if k < pivotIndex then
return select(list, left, pivotIndex − 1, k)
else
return select(list, pivotIndex + 1, right, k)
solution of Longest Consecutive Sequence problem:
this solution was simple ,interesting and creative which I couldn’t come up with it
package main
func longestConsecutive(nums []int) int {
set := map[int]bool{}
for _, num := range nums {
set[num] = true
}
res := 0
for _, num := range nums {
// check if it's the start of a sequence
if set[num-1] {
continue
}
sequence := 1
temp := num + 1
for set[temp] {
sequence++
temp++
}
if sequence > res {
res = sequence
}
}
return res
}
GCD (greates common divisor)
func GCD(a, b int) int {
for b != 0 {
a, b = b, a % b
}
return a
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a % b)
}