Pola Soal Wawancara

Wawancara teknis di perusahaan seperti FAANG, Grab, atau Gojek jarang mengeluarkan soal yang benar-benar baru. Sebagian besar soal adalah variasi dari sekitar 10–15 pola dasar yang sudah dikenal. Setelah kita mengenali pola tersebut, soal yang terlihat rumit menjadi template: kita tinggal memilih pola, menyesuaikan dengan detail soal, lalu menulis kode. Pada Chapter ini kita akan memetakan delapan pola yang paling sering muncul, lengkap dengan contoh soal dan kerangka pendekatan. Tujuannya bukan menghafal solusi, melainkan melatih refleks: melihat soal, mengenali pola, lalu menulis skeleton code dalam waktu 5 menit.

Peta Pola Wawancara #

Tabel berikut merangkum delapan pola yang akan kita bahas. Kolom Sinyal Soal memetakan ciri-ciri soal yang menandakan pola tersebut layak dipertimbangkan.

Pola 1: Two Pointers #

Aturan: dua pointer bergerak pada array yang sama, biasanya dari arah berlawanan atau searah. Pola ini menggantikan nested loop O(n²) menjadi O(n).

Mekanisme: pointer left di awal, right di akhir. Bergantung pada kondisi (sum, area, difference), satu pointer maju/mundur. Karena array sorted, pergerakan selalu menuju solusi — tidak ada backtracking.

Contoh soal — Two Sum Sorted: diberi array nums terurut naik dan target, cari dua indeks berbeda sehingga nums[i] + nums[j] == target.

Kerangka pendekatan:

1. left = 0, right = n - 1
2. while left < right:
3.   s = nums[left] + nums[right]
4.   if s == target: return [left, right]
5.   elif s < target: left++    // butuh nilai lebih besar
6.   else:            right--   // butuh nilai lebih kecil
7. return [] (tidak ditemukan)

Soal lain dengan pola yang sama: Container With Most Water, 3Sum, Trapping Rain Water.

Pola 2: Sliding Window #

Aturan: jendela berukuran dinamis atau tetap “meluncur” di atas array/string. Pola ini efisien untuk masalah subarray berurutan yang otherwise butuh O(n²) atau O(n³).

Mekanisme: dua pointer left dan right membatasi window. right diperluas untuk menambah elemen; left dimajukan untuk menyusutkan window ketika kondisi terlanggar (misalnya duplikat, sum melebihi batas).

Contoh soal — Longest Substring Without Repeating Characters: cari panjang substring terpanjang tanpa karakter berulang.

Kerangka pendekatan:

1. left = 0, maxLen = 0, set<char> seen
2. for right = 0 .. n-1:
3.   while seen.count(nums[right]):
4.     seen.erase(nums[left]); left++
5.   seen.insert(nums[right])
6.   maxLen = max(maxLen, right - left + 1)
7. return maxLen

Soal lain: Minimum Window Substring, Longest Repeating Character Replacement, Permutation in String.

Pola 3: Binary Search #

Aturan: pencarian pada ruang solusi yang monoton. Bila jawaban terurut (atau predikat bersifat monotonic — false…false, true…true), binary search menemukan titik transisi dalam O(log n).

Mekanisme: maintain lo dan hi sebagai batas rentang jawaban. Hitung mid, uji predikat check(mid). Bila check true, jawaban valid di mid atau lebih kecil — geser hi = mid. Bila false, geser lo = mid + 1.

Contoh soal — Search in Rotated Sorted Array: array sorted dinaikkan lalu diputar pada pivot tak diketahui. Cari target.

Kerangka pendekatan:

1. lo = 0, hi = n - 1
2. while lo <= hi:
3.   mid = (lo + hi) / 2
4.   if nums[mid] == target: return mid
5.   if nums[lo] <= nums[mid]:           // bagian kiri sorted
6.     if nums[lo] <= target < nums[mid]: hi = mid - 1
7.     else:                              lo = mid + 1
8.   else:                                // bagian kanan sorted
9.     if nums[mid] < target <= nums[hi]: lo = mid + 1
10.    else:                              hi = mid - 1
11. return -1

Pola lain: Koko Eating Bananas (binary search pada answer), Median of Two Sorted Arrays, Find First and Last Position.

Pola 4: BFS dan DFS #

Aturan: traversing graph atau grid. BFS menemukan jalur terpendek pada bobot seragam; DFS cocok untuk backtracking, connected component, dan deteksi cycle.

Mekanisme BFS: queue FIFO, kunjungi tetangga level demi level. dist array melacak kedalaman.

Mekanisme DFS: stack (atau rekursi + call stack), eksplorasi sedalam mungkin sebelum backtrack.

Contoh soal — Number of Islands: grid 1 (daratan) dan 0 (laut). Hitung jumlah island (komponen terhubung 4-arah).

Kerangka pendekatan (DFS):

1. count = 0
2. for r in 0..rows-1, c in 0..cols-1:
3.   if grid[r][c] == '1':
4.     count++
5.     dfs(r, c)         // tandai seluruh cell island ini sebagai visited
6. return count

dfs(r, c):
  if out of bounds or grid[r][c] != '1': return
  grid[r][c] = '2'      // in-place marking
  dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)

Soal lain: Word Ladder (BFS level), Clone Graph, Pacific Atlantic Water Flow.

Pola 5: Topological Sort #

Aturan: pengurutan node pada DAG (Directed Acyclic Graph) sehingga untuk setiap edge u → v, u muncul sebelum v. Diterapkan pada masalah dependensi.

Mekanisme (Kahn’s algorithm): hitung in-degree tiap node. Masukkan node dengan in-degree 0 ke queue. Pop node, kurangi in-degree tetangga, masukkan yang in-degree-nya jadi 0. Urutan pop adalah topological order.

Contoh soal — Course Schedule: n kursus dan daftar prerequisite [a, b] (untuk ambil a harus b dulu). Tentukan apakah jadwal valid (tidak ada cycle).

Kerangka pendekatan:

1. build adjacency list + in-degree array
2. queue q; for each node v: if indeg[v] == 0: q.push(v)
3. visited = 0
4. while q not empty:
5.   u = q.pop(); visited++
6.   for each neighbor v of u:
7.     indeg[v]--
8.     if indeg[v] == 0: q.push(v)
9. return visited == n   // bila false, ada cycle

Soal lain: Alien Dictionary, Build Order, Parallel Courses.

Pola 6: Dynamic Programming #

Aturan: pecah masalah menjadi subproblem yang tumpang tindih, simpan hasilnya (memoization atau tabulation), hindari recomputation.

Mekanisme: definisikan state (misalnya dp[i][w]), transisi dari subproblem lebih kecil ke lebih besar, base case pada kasus terkecil, jawaban pada state terbesar.

Contoh soal — Coin Change: diberi koin denominasi tertentu, cari jumlah koin minimum untuk membentuk amount.

Kerangka pendekatan:

1. dp[0] = 0; dp[1..amount] = INF
2. for i = 1 .. amount:
3.   for coin in coins:
4.     if i - coin >= 0:
5.       dp[i] = min(dp[i], dp[i - coin] + 1)
6. return dp[amount] == INF ? -1 : dp[amount]

Soal lain dengan pola serupa: Knapsack 0/1, Longest Common Subsequence, Edit Distance, House Robber.

Pola 7: Tree Traversal #

Aturan: navigasi pohon dengan urutan tertentu (preorder, inorder, postorder, level-order). Banyak soal tree dapat diselesaikan dengan recursion + traversal.

Mekanisme: fungsi rekursif menerima node, melakukan aksi, lalu memanggil diri sendiri pada node.left dan node.right. Base case: node == nullptr.

Contoh soal — Validate BST: tentukan apakah sebuah binary tree adalah BST valid (kiri < root < kanan untuk setiap node).

Kerangka pendekatan (inorder terurut):

1. prev = -INF (sentinel)
2. inorder(node):
3.   if node == null: return true
4.   if not inorder(node.left): return false
5.   if node.val <= prev: return false
6.   prev = node.val
7.   return inorder(node.right)
8. return inorder(root)

Soal lain: Lowest Common Ancestor, Maximum Path Sum, Construct Tree from Preorder and Inorder.

Pola 8: Heap / Priority Queue #

Aturan: kapan kita butuh elemen max/min secara berulang dari kumpulan data yang berubah. Heap memberikan O(log n) insert dan O(log n) extract, jauh lebih baik dari sort ulang O(n log n) tiap kali.

Mekanisme: gunakan std::priority_queue (atau std::multiset) untuk menjaga “k elemen terbesar/terkecil”. Untuk top-k largest, gunakan min-heap berukuran k; keluarkan root bila elemen baru lebih besar.

Contoh soal — Top K Frequent Elements: cari k elemen dengan frekuensi tertinggi pada array.

Kerangka pendekatan:

1. count freq tiap elemen ke map<int,int>
2. min-heap<pair<int,int>> pq   // pair{freq, elemen}
3. for each (elem, freq) in map:
4.   pq.push({freq, elem})
5.   if pq.size() > k: pq.pop()   // buang freq terkecil
6. extract elemen dari pq -> hasil

Soal lain: Merge K Sorted Lists, Find Median from Data Stream (two-heap trick), Task Scheduler.

Kode: Katalog Pola Wawancara #

Program berikut menyimpan katalog pola dalam struct yang mudah di-scan. Kode dapat di-extend dengan menambah entry ke vector tanpa mengubah logika pencetakan.

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
using namespace std;

struct Pattern {
    string name;
    string signal;
    string example;
    string complexity;
    vector<string> related;
};

vector<Pattern> catalog() {
    return {
        {"Two Pointers",
         "Array sorted, pasangan/triplet, palindrom",
         "Two Sum Sorted",
         "O(n)",
         {"3Sum", "Container With Most Water", "Trapping Rain Water"}},
        {"Sliding Window",
         "Subarray/substring berurutan, panjang max/min",
         "Longest Substring Without Repeating Chars",
         "O(n)",
         {"Min Window Substring", "Longest Repeating Char", "Permutation in String"}},
        {"Binary Search",
         "Array sorted, 'min max', pencarian rentang",
         "Search in Rotated Sorted Array",
         "O(log n)",
         {"Koko Eating Bananas", "Median of Two Sorted Arrays", "Find First/Last Position"}},
        {"BFS / DFS",
         "Grid, graph, connected component, level-order",
         "Number of Islands",
         "O(V+E)",
         {"Word Ladder", "Clone Graph", "Pacific Atlantic Water Flow"}},
        {"Topological Sort",
         "Dependensi tugas, 'sebelum X harus Y'",
         "Course Schedule",
         "O(V+E)",
         {"Alien Dictionary", "Build Order", "Parallel Courses"}},
        {"Dynamic Programming",
         "Subproblem overlap, pilihan optimal, count ways",
         "Coin Change",
         "O(n*k)",
         {"Knapsack 0/1", "LCS", "Edit Distance", "House Robber"}},
        {"Tree Traversal",
         "Root, ancestor, validate, build tree",
         "Validate BST",
         "O(n)",
         {"LCA", "Maximum Path Sum", "Construct Tree from Preorder+Inorder"}},
        {"Heap / Priority Queue",
         "k-terbesar/terkecil, merge streams, scheduling",
         "Top K Frequent Elements",
         "O(n log k)",
         {"Merge K Sorted Lists", "Median from Data Stream", "Task Scheduler"}},
    };
}

void printCatalog(const vector<Pattern>& pats) {
    cout << left << setw(22) << "Pola"
         << setw(45) << "Sinyal Soal"
         << setw(40) << "Contoh Soal"
         << "Kompleksitas\n";
    cout << string(120, '-') << "\n";
    for (const auto& p : pats) {
        cout << left << setw(22) << p.name
             << setw(45) << p.signal
             << setw(40) << p.example
             << p.complexity << "\n";
    }
}

void printRelated(const vector<Pattern>& pats) {
    cout << "\n=== Soal Terkait per Pola ===\n";
    for (const auto& p : pats) {
        cout << "\n[" << p.name << "]\n";
        for (size_t i = 0; i < p.related.size(); ++i) {
            cout << "  " << (i + 1) << ". " << p.related[i] << "\n";
        }
    }
}

int main() {
    auto pats = catalog();
    cout << "=== Katalog Pola Soal Wawancara ===\n\n";
    printCatalog(pats);
    printRelated(pats);
    return 0;
}

Output yang Dihasilkan:

=== Katalog Pola Soal Wawancara ===

Pola                  Sinyal Soal                                  Contoh Soal                             Kompleksitas
------------------------------------------------------------------------------------------------------------------------
Two Pointers          Array sorted, pasangan/triplet, palindrom    Two Sum Sorted                          O(n)
Sliding Window        Subarray/substring berurutan, panjang max/minLongest Substring Without Repeating CharsO(n)
Binary Search         Array sorted, 'min max', pencarian rentang   Search in Rotated Sorted Array          O(log n)
BFS / DFS             Grid, graph, connected component, level-orderNumber of Islands                       O(V+E)
Topological Sort      Dependensi tugas, 'sebelum X harus Y'        Course Schedule                         O(V+E)
Dynamic Programming   Subproblem overlap, pilihan optimal, count waysCoin Change                             O(n*k)
Tree Traversal        Root, ancestor, validate, build tree         Validate BST                           O(n)
Heap / Priority Queue k-terbesar/terkecil, merge streams, schedulingTop K Frequent Elements                 O(n log k)

=== Soal Terkait per Pola ===

[Two Pointers]
  1. 3Sum
  2. Container With Most Water
  3. Trapping Rain Water

[Sliding Window]
  1. Min Window Substring
  2. Longest Repeating Char
  3. Permutation in String

[Binary Search]
  1. Koko Eating Bananas
  2. Median of Two Sorted Arrays
  3. Find First/Last Position

[BFS / DFS]
  1. Word Ladder
  2. Clone Graph
  3. Pacific Atlantic Water Flow

[Topological Sort]
  1. Alien Dictionary
  2. Build Order
  3. Parallel Courses

[Dynamic Programming]
  1. Knapsack 0/1
  2. LCS
  3. Edit Distance
  4. House Robber

[Tree Traversal]
  1. LCA
  2. Maximum Path Sum
  3. Construct Tree from Preorder+Inorder

[Heap / Priority Queue]
  1. Merge K Sorted Lists
  2. Median from Data Stream
  3. Task Scheduler

Bedah Kode Baris-per-Baris #

1. struct Pattern { string name; string signal; ... vector<string> related; }: model data untuk satu pola. Field related sebagai vector memungkinkan jumlah soal terkait bervariasi — pola tertentu punya 3 soal, pola lain 4 atau 5.
2. vector<Pattern> catalog(): fungsi pembuat katalog. Memisahkan data dari logika pencetakan; bila ingin menambah pola baru, cukup tambah satu entry tanpa mengubah main atau printCatalog.
3. return { {"Two Pointers", ...}, ... };: brace-init untuk vector of struct. Pendekatan deklaratif: seluruh katalog terbaca sebagai satu blok data.
4. cout << left << setw(22) << "Pola" ...: header tabel. left merapikan rata kiri; setw mengatur lebar kolom. Header harus disesuaikan dengan lebar kolom data di bawahnya.
5. for (const auto& p : pats): iterasi dengan const reference. const menegaskan bahwa loop tidak memodifikasi elemen; auto& menghindari copy struct besar.
6. setw(45) << p.signal: lebar 45 karakter untuk kolom sinyal. Bila teks lebih panjang, setw tidak memotong — teks meluap, kolom berikutnya bergeser. Untuk data terkontrol seperti katalog, ini acceptable.

Strategi Mengenali Pola #

Ketika membaca soal baru, jalankan checklist berikut sebelum memilih pendekatan:

Latihan Mandiri #

Untuk setiap pola, kerjakan minimal 3 soal di LeetCode atau HackerRank:

1. Easy — memvalidasi kita mengenali pola.
2. Medium — variasi yang menguji pemahaman.
3. Medium/Hard lain — memastikan kita bisa adaptasi pola ke kondisi baru.

Bila dalam satu sesi 3 soal pola yang sama berhasil diselesaikan dalam 30 menit, pola tersebut “kuasai”. Bila tidak, balik ke materi pola di Section 6–21 course ini.

Ringkasan #

• Delapan pola inti menutupi sebagian besar soal wawancara: Two Pointers, Sliding Window, Binary Search, BFS/DFS, Topological Sort, DP, Tree Traversal, Heap.
• Sinyal soal (sorted, subarray, dependensi, dst.) adalah petunjuk utama untuk memilih pola.
• Kerangka pendekatan tiap pola bisa diingat sebagai 5–10 baris pseudocode; sisanya adaptasi ke detail soal.
• Katalog pola disimpan sebagai vector of struct — mudah di-extend dan di-print.
• Latihan pola berulang (3 soal per pola) melatih refleks: lihat soal, kenali pola, tulis skeleton dalam 5 menit.