Technical Coding Interview: Panduan Persiapan Lengkap

# Array: kumpulan elemen berurutan di memory
# Akses: O(1) by index, Search: O(n), Insert/Delete: O(n) di tengah

# Two Pointer Technique pada Array
def two_sum_sorted(arr, target):
    """Cari dua angka yang jumlahnya = target pada sorted array"""
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

# Sliding Window pada Array
def max_subarray_sum(arr, k):
    """Cari maximum sum subarray dengan panjang k"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

# String Manipulation
def is_palindrome(s):
    """Cek apakah string palindrome (aba-aba)"""
    s = ''.join(c.lower() for c in s if c.isalnum())
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# Hash Map: key-value pair, lookup O(1) average
# Hash Set: unique values, lookup O(1) average
# Paling sering muncul di interview!

from collections import Counter, defaultdict

# Pattern 1: Frequency Counting
def group_anagrams(strs):
    """Kelompokkan string yang merupakan anagram"""
    anagram_map = defaultdict(list)
    for s in strs:
        # Sort huruf sebagai key → anagram punya key sama
        key = ''.join(sorted(s))
        anagram_map[key].append(s)
    return list(anagram_map.values())

# Pattern 2: Two Sum dengan Hash Map (O(n) vs O(n²) brute force)
def two_sum(nums, target):
    """Cari index dua angka yang jumlahnya = target"""
    seen = {}  # value → index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Pattern 3: Counting Elements
def find_duplicates(nums):
    """Temukan semua elemen yang muncul lebih dari 1 kali"""
    count = Counter(nums)
    return [num for num, freq in count.items() if freq > 1]

# Pattern 4: Sliding Window dengan Hash Map
def longest_substring_no_repeat(s):
    """Panjang substring terpanjang tanpa karakter berulang"""
    char_index = {}
    left = max_len = 0
    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Linked List: node-based, insert/delete O(1) di head
# Tapi access by index O(n) — harus traverse

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Reverse Linked List — SOAL PALING SERING MUNCUL
def reverse_list(head):
    """Balik linked list secara in-place"""
    prev = None
    current = head
    while current:
        next_node = current.next  # Simpan next
        current.next = prev       # Balik pointer
        prev = current             # Geser prev
        current = next_node        # Geser current
    return prev  # prev sekarang adalah head baru

# Detect Cycle (Floyd's Algorithm)
def has_cycle(head):
    """Deteksi apakah linked list punya cycle"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next        # Langkah 1
        fast = fast.next.next   # Langkah 2
        if slow == fast:        # Bertemu = ada cycle
            return True
    return False

# Merge Two Sorted Lists
def merge_sorted(l1, l2):
    """Gabungkan dua linked list yang sudah terurut"""
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 or l2  # Sambungkan sisa
    return dummy.next

# Stack: LIFO (Last In First Out) — push, pop di O(1)
# Queue: FIFO (First In First Out) — enqueue, dequeue di O(1)

# Stack: Valid Parentheses — Soal klasik interview
def is_valid_parentheses(s):
    """Cek apakah kurung valid: (), [], {}"""
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:
            # Tutup kurung → cek apakah cocok dengan top stack
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            # Buka kurung → push ke stack
            stack.append(char)
    return len(stack) == 0

# Stack: Next Greater Element
def next_greater_element(nums):
    """Temukan elemen terbesar berikutnya untuk setiap elemen"""
    result = [-1] * len(nums)
    stack = []  # Stack berisi index
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

# Queue: BFS (Breadth-First Search) pada Graph
from collections import deque
def bfs(graph, start):
    """BFS traversal pada graph"""
    visited = set([start])
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

# Binary Tree: setiap node punya max 2 children
# Binary Search Tree (BST): left < root < right

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# DFS: Inorder, Preorder, Postorder
def inorder(root):
    """Inorder: Left → Root → Right (BST → sorted order)"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Validate BST
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    """Cek apakah binary tree adalah BST yang valid"""
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

# Lowest Common Ancestor
def lowest_common_ancestor(root, p, q):
    """Temukan LCA dari node p dan q di BST"""
    if not root:
        return None
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)
    return root  # Split point — ini LCA

# Graph: Adjacency List Representation
def build_graph(edges):
    """Bangun graph dari edge list"""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # Hapus baris ini untuk directed graph
    return graph

# DFS pada Graph
def dfs(graph, start, visited=None):
    """DFS traversal pada graph"""
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# Merge Sort — O(n log n), stable, divide & conquer
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Binary Search — O(log n)
def binary_search(arr, target):
    """Cari target di sorted array"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Binary Search: Search in Rotated Array
def search_rotated(nums, target):
    """Cari target di rotated sorted array"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # Bagian kiri terurut
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Bagian kanan terurut
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

# DP: Break masalah jadi sub-masalah, cache hasilnya
# Dua pendekatan: Top-down (memoization) & Bottom-up (tabulation)

# 1. Fibonacci — DP paling dasar
def fib(n):
    """O(n) time, O(n) space"""
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 2. Climbing Stairs
def climb_stairs(n):
    """Berapa cara naik n tangga (1 atau 2 langkah sekaligus)"""
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# 3. Longest Common Subsequence
def lcs(text1, text2):
    """Panjang subsequence terpanjang yang sama"""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# 4. 0/1 Knapsack
def knapsack(weights, values, capacity):
    """Maximize value tanpa melebihi kapasitas"""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]  # Tidak ambil item i
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

# === TIME COMPLEXITY ===

# 1. Sequential statements → tambahkan
# for i in range(n):        → O(n)
#     for j in range(m):    → O(n × m)
# Total: O(n × m)

# 2. If-else → ambil yang paling besar
# if condition:
#     O(n)  operation
# else:
#     O(n²) operation
# Total: O(n²)

# 3. Loop dengan pembagian → log
# while n > 0:
#     n = n // 2
# Total: O(log n)

# 4. Rekursi → gunakan recurrence relation
# T(n) = 2T(n/2) + O(n) → O(n log n) (Master Theorem)

# === SPACE COMPLEXITY ===

# 1. Variable biasa → O(1)
# 2. Array/hash map berukuran n → O(n)
# 3. Rekursi: kedalaman stack × ruang per frame
#    - Binary tree balanced → O(log n) stack
#    - Linked list traversal → O(n) stack (jika rekursif)
# 4. Matriks n×m → O(n × m)

# === COMMON PATTERNS COMPLEXITY ===
# Two Pointers on sorted array → O(n) time, O(1) space
# Sliding Window → O(n) time, O(k) space
# BFS/DFS → O(V + E) time, O(V) space
# Sorting → O(n log n) time, O(n) space (merge sort)
# Binary Search → O(log n) time, O(1) space

# Soal: Given [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]
# Karena [1,3] dan [2,6] overlap → merge jadi [1,6]

def merge_intervals(intervals):
    """
    Approach: Sort by start time, lalu linear scan
    Time: O(n log n) karena sorting
    Space: O(n) untuk output
    """
    if not intervals:
        return []

    # Step 1: Sort berdasarkan start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]  # Mulai dengan interval pertama

    for current in intervals[1:]:
        last = merged[-1]

        # Cek overlap: current start <= last end?
        if current[0] <= last[1]:
            # Merge: extend end time
            last[1] = max(last[1], current[1])
        else:
            # Tidak overlap → tambahkan interval baru
            merged.append(current)

    return merged

# Test cases
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# Output: [[1,6],[8,10],[15,18]]

print(merge_intervals([[1,4],[4,5]]))
# Output: [[1,5]]

# Edge cases yang perlu dipertimbangkan:
# - Input kosong: []
# - Satu interval: [[1,2]]
# - Semua overlap: [[1,5],[2,3],[3,4]] → [[1,5]]
# - Tidak ada overlap: [[1,2],[3,4],[5,6]] → tetap

# Soal: Temukan K elemen yang paling sering muncul
# Input: nums=[1,1,1,2,2,3], k=2
# Output: [1,2]

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    """
    Approach 1: Heap — O(n log k)
    Approach 2: Bucket Sort — O(n)
    """
    # === APPROACH 1: Min Heap ===
    count = Counter(nums)
    # Heap dengan size k, simpan k elemen dengan frekuensi tertinggi
    return heapq.nlargest(k, count.keys(), key=count.get)

def top_k_frequent_bucket(nums, k):
    """
    Approach 2: Bucket Sort — O(n) time, O(n) space
    Lebih optimal karena tidak perlu sorting
    """
    count = Counter(nums)
    # Bucket: index = frekuensi, value = list elemen
    # Frekuensi max = len(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result = []
    # Traverse dari frekuensi tertinggi ke terendah
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

# Test
print(top_k_frequent([1,1,1,2,2,3], 2))       # [1, 2]
print(top_k_frequent_bucket([1,1,1,2,2,3], 2)) # [1, 2]

# === JADWAL HARIAN INTERVIEW PREP (2-3 jam) ===

# 06:00 - 06:30  Review soal kemarin (spaced repetition)
# 06:30 - 07:15  Soal baru #1 — tanpa bantuan, timer 45 menit
# 07:15 - 07:30  Break / review solution
# 07:30 - 08:15  Soal baru #2 — pattern yang sama atau berbeda
# 08:15 - 08:30  Refactor kode, catat pattern/template
#
# Minggu: Review semua soal dalam seminggu
# Sabtu: Mock interview dengan teman (1 jam)
#
# TIPS: Konsistensi > Intensitas
# 2 jam setiap hari LEBIH BAIK dari 10 jam di weekend saja