Algorithms: Interview Pattern Recognition Guide

Data Structure Operations:
  Array access:        O(1)
  Array search:        O(n)
  Hash map get/set:    O(1) average, O(n) worst
  Binary search tree:  O(log n) balanced, O(n) worst
  Heap push/pop:       O(log n)
  Heap peek:           O(1)

Sorting:
  QuickSort:    O(n log n) avg, O(n²) worst
  MergeSort:    O(n log n) always, O(n) space
  HeapSort:     O(n log n) always, O(1) space
  Counting/Radix: O(n) for small range

Graph:
  BFS/DFS:      O(V + E)
  Dijkstra:     O((V+E) log V)
  Bellman-Ford: O(VE)
  Floyd-Warshall: O(V³)
  Topological Sort: O(V + E)
  Union-Find:   O(α(n)) ≈ O(1)

1. Repeat     — Nhắc lại bài, confirm constraints
2. Refine     — Hỏi edge cases, input size, negative numbers?
3. Think      — Nói ra brute force trước, rồi optimize
4. Execute    — Code với variable names rõ ràng
5. Debug      — Trace qua example nhỏ

- Input size n? (ảnh hưởng O(n²) vs O(n log n))
- Có thể có negative numbers không?
- Array đã sorted chưa?
- Có duplicate không?
- Return value khi không tìm thấy? (-1, [], error?)
- Modify in-place hay return mới?

nums = [2, 1, 2, 4, 3]
result = [4, 2, 4, -1, -1]

Stack duy trì các element chưa tìm được "next greater"
Khi gặp nums[i] > stack.top() → stack.top() tìm thấy answer

func nextGreaterElement(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    for i := range result { result[i] = -1 }
    stack := []int{} // lưu index

    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[idx] = nums[i]
        }
        stack = append(stack, i)
    }
    return result
}

nums = [1, 2, 3, 4, 5]
prefix = [0, 1, 3, 6, 10, 15]
sum(l, r) = prefix[r+1] - prefix[l]  // O(1) query

func buildPrefix(nums []int) []int {
    prefix := make([]int, len(nums)+1)
    for i, v := range nums {
        prefix[i+1] = prefix[i] + v
    }
    return prefix
}

func rangeSum(prefix []int, l, r int) int {
    return prefix[r+1] - prefix[l]
}

func backtrack(path []int, choices []int, result *[][]int) {
    if isSolution(path) {
        *result = append(*result, append([]int{}, path...))
        return
    }
    for _, choice := range choices {
        if isValid(choice, path) {
            path = append(path, choice)         // choose
            backtrack(path, nextChoices, result) // explore
            path = path[:len(path)-1]           // unchoose
        }
    }
}

// 1. Binary Search (Lower Bound)
left, right := 0, n
for left < right {
    mid := left + (right-left)/2
    if condition(mid) { right = mid } else { left = mid + 1 }
}
return left

// 2. Sliding Window (Variable)
left := 0
for right := 0; right < n; right++ {
    add(arr[right])
    for invalid() { remove(arr[left]); left++ }
    updateAnswer(right - left + 1)
}

// 3. BFS
queue := []int{start}; visited[start] = true
for len(queue) > 0 {
    node := queue[0]; queue = queue[1:]
    for _, nb := range graph[node] {
        if !visited[nb] { visited[nb] = true; queue = append(queue, nb) }
    }
}

// 4. DFS (recursive)
func dfs(node int) {
    visited[node] = true
    for _, nb := range graph[node] { if !visited[nb] { dfs(nb) } }
}

// 5. Union-Find
func find(x int) int {
    if parent[x] != x { parent[x] = find(parent[x]) }
    return parent[x]
}
func union(x, y int) { parent[find(x)] = find(y) }