หัวข้อ Algorithms & Data Structures

นี่คือหัวข้อหลักที่ครอบคลุมโจทย์สัมภาษณ์ส่วนใหญ่ ในแต่ละหัวข้อให้โฟกัสที่ pattern ไม่ใช่ท่องโจทย์เป็นข้อ ๆ

ทบทวน Big-O ก่อน

ทุกคำตอบต้องวิเคราะห์ได้ว่าใช้เวลาและหน่วยความจำเท่าไหร่ เรียงจากดีไปแย่: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Array & String

พื้นฐานที่สุดและเจอบ่อยที่สุด เทคนิคสำคัญคือ two pointers (จับสองตำแหน่งวิ่งเข้าหากันหรือไล่ไปด้วยกัน) และ sliding window (หน้าต่างเลื่อนสำหรับหา subarray/substring)

# ตัวอย่าง two pointers: เช็คว่าเป็น palindrome หรือไม่
def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i, j = i + 1, j - 1
    return True

Hash Table

ใช้เมื่อต้องค้นหา/นับ/จับคู่แบบเร็ว (เฉลี่ย O(1)) เป็นกุญแจของโจทย์ประเภท "หาคู่ที่รวมกันได้ค่าเป้าหมาย" หรือ "หาตัวซ้ำ" จำไว้ว่าเมื่อเจอคำว่า "นับ" หรือ "เคยเห็นมาก่อนไหม" มักใช้ hash table

Linked List, Stack & Queue

• Linked List — ฝึก reverse, หา cycle (fast & slow pointer), merge
• Stack — เหมาะกับการจับคู่วงเล็บ และโจทย์ "next greater element"
• Queue — ใช้คู่กับ BFS

Tree & Graph

หัวใจคือ DFS (ลงลึกก่อน — ใช้ recursion หรือ stack) และ BFS (กวาดทีละชั้น — ใช้ queue) โจทย์ tree ส่วนใหญ่แก้ด้วย recursion ได้สวยงาม ส่วน graph ต้องระวังเรื่อง visited set กันวนซ้ำ

# BFS บน graph
from collections import deque
def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return visited

Recursion & Backtracking

ใช้กับโจทย์ที่ต้องลองทุกความเป็นไปได้ เช่น permutation, combination, subset, การแก้ปริศนา (sudoku, N-queens) หัวใจคือ "เลือก → เรียกตัวเอง → ถอยกลับ (undo)"

Binary Search

ไม่ได้ใช้แค่กับ array ที่เรียงแล้ว แต่ใช้กับโจทย์ "หาค่าน้อยที่สุดที่ทำให้เงื่อนไขเป็นจริง" ได้ด้วย ระวัง off-by-one ตรงการอัปเดต left/right

Dynamic Programming

หัวข้อที่คนกลัวที่สุด แต่จับหลักได้ไม่ยาก: หาว่าปัญหาแบ่งเป็นปัญหาย่อยที่ซ้ำกันได้ไหม (overlapping subproblems) แล้วเก็บผลลัพธ์ย่อยไว้ใช้ซ้ำ (memoization) เริ่มจากเขียน recursion ปกติก่อน แล้วค่อยเพิ่ม cache

จับสัญญาณว่าโจทย์นี้ใช้ pattern ไหน

เคล็ดลับการแก้โจทย์เร็วคือจำ "สัญญาณ" ในโจทย์ที่บ่งบอก pattern ฝึกจนเห็นโจทย์แล้วนึกออกทันทีว่าจะใช้เทคนิคใด

Sorting ที่ควรรู้

ไม่ต้องท่อง implement ทุกตัว แต่ต้องรู้ complexity และเมื่อไหร่ใช้ตัวไหน