ដាក់ឲ្យរួមគ្នា

មាតិកា

1. អ្វីដែលអ្នកបានសាងសង់
2. អានបញ្ហាដើម្បីរកសញ្ញា
3. Pattern Cheat Sheet
4. Cost Cheat Sheet
5. វិធីសាស្ត្រប្រាំពីរជំហាន
6. ឧទាហរណ៍ដែលដោះស្រាយពេញលេញ
7. កំហុសទូទៅ
8. ក្រៅពី Interview ការជ្រើសនៅកន្លែងធ្វើការ
9. រូបមន្ត៖ index.ts សម្រាប់ algolab
10. សាកល្បងដោយខ្លួនឯង
11. កន្លែងដែលត្រូវទៅបន្ត

1. អ្វីដែលអ្នកបានសាងសង់

សូមចំណាយពេលមើលត្រឡប់ក្រោយបន្តិច។ ក្នុងរយៈពេលដប់បីជំពូក អ្នកបានរៀនវាក្យសព្ទរបស់អ្នកសរសេរកម្មវិធីដែលកំពុងធ្វើការ៖

• Structure ប្រចាំថ្ងៃ៖ array និង string, hash map និង set, linked list, stack និង queue។
• បច្ចេកទេសស្នូល៖ recursion, searching និង sorting។
• Structure សម្រាប់ឋានានុក្រម និងទំនាក់ទំនង៖ tree, heap និង graph។
• Structure ឯកទេស៖ trie និង union-find។
• របៀបរចនា៖ ជម្រើសបែប greedy និង dynamic programming។

អ្នកក៏បានសរសេរ library មួយឈ្មោះ algolab ជាមួយ test ដែលផ្ទុកកំណែផ្ទាល់ខ្លួនរបស់អ្នកនៃភាគច្រើនក្នុងចំណោមទាំងនេះ។ នោះសំខាន់ជាងដែលវាអាចហាក់ដូចជា។ ពេលនរណាម្នាក់និយាយថា "priority queue គឺ O(log n) សម្រាប់ push" អ្នកមិនចាំបាច់ជឿពាក្យគេទេ ព្រោះអ្នកបានសរសេរ loop sift-up ហើយបានឃើញវាផ្ទាល់។

ជំពូកនេះមិនបន្ថែមទ្រឹស្តីថ្មីទេ។ វាធ្វើបីយ៉ាង៖

1. វាបំប្លែងស៊េរីនេះទៅជា cheat sheet សម្រាប់ជ្រើសឧបករណ៍ត្រឹមត្រូវ។
2. វាផ្តល់ វិធីសាស្ត្រ សម្រាប់បញ្ហាដែលមិនធ្លាប់ស្គាល់ ទាំងក្នុង interview ឬក្នុងការងារ។
3. វាភ្ជាប់ algolab ចូលគ្នាដោយឯកសារចូលតែមួយ។

2. អានបញ្ហាដើម្បីរកសញ្ញា

បញ្ហាភាគច្រើនប្រាប់អ្នកថាវាត្រូវការអ្វី ប្រសិនបើអ្នកអានដោយប្រុងប្រយ័ត្ន។ល្បិចគឺចាត់ទុកពាក្យក្នុងបញ្ហាជា សញ្ញា ដូចគ្រូពេទ្យចាត់ទុករោគសញ្ញា។ នេះគឺជាសញ្ញាដែលលេចឡើងញឹកញាប់បំផុត៖

គ្មានឃ្លាតែមួយណាសម្រេចអ្វីបានដោយខ្លួនឯងទេ។ ប្រើតារាងដើម្បីបង្កើត បេក្ខជន រួចពិនិត្យពួកវាធៀបនឹងលក្ខខណ្ឌ។

ទំហំ input ក៏ជាសញ្ញាដែរ។ វាប្រាប់អ្នកថាមានការងារប៉ុន្មានត្រូវបានអនុញ្ញាត៖

ទាំងនេះគឺជាច្បាប់ប្រហាក់ប្រហែលសម្រាប់ដែនកំណត់ពេលប្រហែលមួយវិនាទី។ ប្រសិនបើអ្នកសម្ភាសន៍និយាយថា "រហូតដល់មួយលានធាតុ" ចម្លើយ O(n^2) ត្រូវបានច្រានចោលមុនអ្នកសរសេរមួយបន្ទាត់ផង។

3. Pattern Cheat Sheet

នេះគឺជាស៊េរីទាំងមូលក្នុងមួយទំព័រ។ សម្រាប់ structure ឬបច្ចេកទេសនីមួយៗ៖ វាពូកែអ្វី ថ្លៃចំណាយធម្មតា និងជំពូកដែលត្រូវត្រឡប់ទៅមើលឡើងវិញ។

ចលនាមួយចំនួនលេចឡើងញឹកញាប់គ្រប់គ្រាន់ ដែលគួរទន្ទេញ៖

• "ខ្ញុំត្រូវការរកអ្វីមួយឲ្យលឿន"៖ ដាក់វាក្នុង Map ឬ Set។ ចលនាតែមួយនេះបំប្លែងចម្លើយ O(n^2) ជាច្រើនទៅជា O(n)។
• "ខ្ញុំត្រូវការធាតុខ្លាំងបំផុត ម្តងហើយម្តងទៀត"៖ heap។
• "ខ្ញុំត្រូវការឲ្យវា sort រួចឆ្លងកាត់ម្តង"៖ sort មុន។ បញ្ហាជាច្រើនក្លាយជាងាយ នៅពេលអ្នកជិតខាងនៅជាប់គ្នា (interval, ស្ទួន, គូ)។
• "ចម្លើយគឺលេខក្នុង range ហើយខ្ញុំអាចពិនិត្យការស្មាន"៖ binary search លើចម្លើយ។
• "ស្វែងរកលទ្ធភាពទាំងអស់"៖ backtracking រួច កាត់ (prune) ឬ memoize ដើម្បីបង្កើនល្បឿន។
• "លំដាប់នៃជម្រើសសំខាន់តិចតួច មានតែចំនួនប៉ុណ្ណោះ"៖ DP។

4. Cost Cheat Sheet

នៅពេលអ្នកជ្រើស structure មួយ អ្នកក៏ជ្រើសថ្លៃចំណាយរបស់វាដែរ។ ចងចាំតារាងនេះក្នុងក្បាល ដូចដែលអ្នកបានប្រៀបធៀបថ្លៃចំណាយទាំងនេះជាច្រើនក្នុងជំពូកមុនៗ។

ហើយដូចគ្នាសម្រាប់ sorting៖

នៅក្នុងការអនុវត្ត អ្នកនឹងប្រើ sort ដែលមានស្រាប់ (ជាមួយ comparator) ស្ទើរតែរាល់ពេល។ ចំណុចនៃការរៀនអ្នកផ្សេងទៀតគឺដើម្បី ស្គាល់ គំនិត និងថ្លៃចំណាយរបស់ពួកវា មិនមែនដើម្បីសរសេរឡើងវិញនៅកន្លែងធ្វើការទេ។

5. វិធីសាស្ត្រប្រាំពីរជំហាន

ពេលអ្នកជួបបញ្ហាដែលអ្នកមិនស្គាល់ ការភ័យស្លន់ស្លោគឺជាសត្រូវពិតប្រាកដ។ ទម្លាប់ថេរមួយផ្តល់អ្វីឲ្យអ្នកធ្វើ ខណៈដែលខួរក្បាលរបស់អ្នកតាមទាន់។ វាក៏ប្រាប់អ្នកសម្ភាសន៍ពីរបៀបដែលអ្នកគិត ដែលជាអ្វីដែលពួកគេមកដើម្បីដឹង។ ប្រាំពីរជំហានគឺ៖

1. បញ្ជាក់ (Clarify)។ និយាយបញ្ហាឡើងវិញជាពាក្យរបស់អ្នក។ សួរអំពី input៖ ធំប៉ុនណា? អាចទទេឬទេ? អាចមានលេខអវិជ្ជមាន ឬស្ទួនឬទេ? ត្រូវបាន sort ឬទេ? តើគួរកើតអ្វីឡើងនៅពេល input មិនត្រឹមត្រូវ?
2. ឧទាហរណ៍ (Examples)។ សរសេរឧទាហរណ៍ពីរ ឬបី រួមទាំង edge case ដ៏ពិបាកមួយ (ទទេ, ធាតុតែមួយ, ដូចគ្នាទាំងអស់)។ ដោះស្រាយមួយដោយដៃ។ ជារឿយៗអ្នករកឃើញ algorithm ពេលកំពុងធ្វើនេះ។
3. Brute force។ និយាយដំណោះស្រាយសាមញ្ញបំផុត ទោះបីយឺត និងថ្លៃចំណាយរបស់វា។ នេះបញ្ជាក់ថាអ្នកយល់បញ្ហា ហើយផ្តល់ជម្រើសបម្រុងដែលត្រឹមត្រូវ។
4. បង្កើនប្រសិទ្ធភាព (Optimize)។ សួរថាការងារអ្វីត្រូវបានធ្វើម្តងទៀត ឬខ្ជះខ្ជាយ។ ពិនិត្យសញ្ញាពីផ្នែកទី 2។ តើ hash map លុប loop ខាងក្នុងបានទេ? តើ sorting ជួយទេ? តើអ្នកអាចប្រើចម្លើយមុនឡើងវិញបានទេ (window, prefix sum, តារាង DP)?
5. កូដ (Code)។ សរសេរកំណែដែលបានបង្កើនប្រសិទ្ធភាព ជាជំហានតូចៗដែលមានឈ្មោះ។ និយាយថាអ្នកកំពុងធ្វើអ្វីពេលកំពុងសរសេរ។ ប្រើឈ្មោះ variable ច្បាស់លាស់។
6. សាកល្បង (Test)។ ដំណើរការឧទាហរណ៍របស់អ្នកតាមកូដដោយដៃ (ឬរត់ពិតប្រាកដ)។ បន្ទាប់មកសាកល្បង edge case៖ ទទេ, ធាតុមួយ, ស្ទួន, តម្លៃធំបំផុត។ កែអ្វីដែលអ្នករកឃើញដោយមិនខ្មាស់អៀន។
7. Complexity។ និយាយថ្លៃពេលវេលា និងទំហំ ហើយប្រាប់ហេតុផល។ លើកឡើងពី trade-off៖ "ខ្ញុំអាចប្រើទំហំ O(1) ជាមួយ sorting ប៉ុន្តែនោះចំណាយពេល O(n log n)។"

ទម្លាប់ពីរសំខាន់ជាងល្បិចណាមួយ៖

• គិតឮៗ។ អ្នកសម្ភាសន៍មិនអាចឮភាពស្ងៀមស្ងាត់ទេ។ សូម្បីតែគំនិតខុស ដែលបាននិយាយហើយកែ ក៏បង្ហាញទម្លាប់ល្អដែរ។
• ចាប់ផ្តើមដោយត្រឹមត្រូវ រួចទើបលឿន។ Brute force ដែលដំណើរការ ឈ្នះដំណោះស្រាយឆ្លាតដែលមិនទាន់ចប់។ អ្នកអាចកែលម្អកំណែដែលដំណើរការបានជានិច្ច។

6. ឧទាហរណ៍ដែលដោះស្រាយពេញលេញ

តោះដំណើរការវិធីសាស្ត្រលើបញ្ហាពិតមួយ។

ដោយមាន string s ត្រឡប់ប្រវែងនៃ substring វែងបំផុតដែលមិនមានតួអក្សរដដែលៗ។

1. បញ្ជាក់។ Substring គឺជាប់គ្នា (មិនដូច subsequence)។ "តួអក្សរ" មានន័យថាតួអក្សរណាមួយ ដែលប្រកាន់អក្សរធំតូច។ String ទទេត្រឡប់ 0។ សន្មតថា s អាចមានរហូតដល់ 100,000 តួអក្សរ ដែលច្រានចោល O(n^2) យ៉ាងលឿន។

2. ឧទាហរណ៍។

ករណី "abba" គឺជាករណីពិបាក ហើយយើងនឹងត្រឡប់មកវិញ។

3. Brute force។ សម្រាប់រាល់ទីតាំងចាប់ផ្តើម ពង្រីកទៅស្តាំរហូតដល់ឃើញស្ទួន ដោយចងចាំប្រវែងល្អបំផុត៖

function longestUniqueBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

វាត្រឹមត្រូវ។ ថ្លៃចំណាយគឺពេលវេលា O(n^2) ក្នុងករណីអាក្រក់បំផុត (string ដែលគ្មានស្ទួន ដូចជាតួអក្សរខុសគ្នាច្រើន) និងទំហំ O(min(n, alphabet))។ សម្រាប់ 100,000 តួអក្សរ នោះយឺតពេក ដូច្នេះយើងបន្ត។

4. បង្កើនប្រសិទ្ធភាព។ តើអ្វីត្រូវបានខ្ជះខ្ជាយ? បន្ទាប់ពីយើងរកឃើញស្ទួននៅទីតាំង j យើងបោះអ្វីៗទាំងអស់ចោល ហើយចាប់ផ្តើមឡើងវិញពី i + 1។ ប៉ុន្តែ substring ពី i + 1 ដល់ j - 1 ត្រូវបានដឹងរួចហើយថាមិនស្ទួន។ សញ្ញាពី cheat sheet៖ "ផ្នែក ជាប់គ្នា វែងបំផុតតាមច្បាប់" មានន័យថា sliding window (ជំពូកទី 2) ហើយ "តើខ្ញុំធ្លាប់ឃើញតួអក្សរនេះឬទេ" មានន័យថា hash map (ជំពូកទី 3)។

ផែនការ៖ រក្សា window [start, end] ដែលគ្មានស្ទួនជានិច្ច។ ផ្លាស់ទី end ទៅស្តាំមួយជំហានរាល់ពេល។ ប្រសិនបើ s[end] ត្រូវបានឃើញ នៅក្នុង window ផ្លាស់ទី start ទៅហួសទីតាំងមុនរបស់វា។ រក្សាទុក index ចុងក្រោយនៃតួអក្សរនីមួយៗក្នុង Map។

5. កូដ។

function longestUnique(s: string): number {
  const lastSeen = new Map<string, number>(); // char -> last index
  let start = 0;
  let best = 0;

  for (let end = 0; end < s.length; end++) {
    const ch = s[end];
    const prev = lastSeen.get(ch);
    if (prev !== undefined && prev >= start) {
      start = prev + 1; // jump past the earlier copy
    }
    lastSeen.set(ch, end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}

6. សាកល្បង។ ដំណើរការឧទាហរណ៍តាមកំណែទាំងពីរ៖

for (const s of ["abcabcbb", "bbbbb", "pwwkew", "", "abba", "dvdf"]) {
  console.log(JSON.stringify(s), longestUniqueBrute(s), longestUnique(s));
}

"abcabcbb" 3 3
"bbbbb" 1 1
"pwwkew" 3 3
"" 0 0
"abba" 2 2
"dvdf" 3 3

ទាំងពីរស្របគ្នា។ ការមានកំណែ brute-force នៅក្បែរគឺជាអំណោយពិតប្រាកដ៖ វាជា test oracle។ រាល់ពេលអ្នកសរសេរដំណោះស្រាយឆ្លាត ចូរប្រៀបធៀបវាជាមួយកំណែយឺតងាយៗលើ input ចៃដន្យជាច្រើន។ ការមិនស៊ីគ្នាចង្អុលត្រង់ទៅ bug របស់អ្នក។

ឥឡូវត្រឡប់ទៅ "abba"។ នៅ end = 3 តួ a ទីពីររកឃើញ prev = 0 ប៉ុន្តែ start គឺ 2 រួចហើយ (ត្រូវបានផ្លាស់ទីដោយ b ទីពីរ)។ បើគ្មានការពិនិត្យ prev >= start យើងនឹងផ្លាស់ទី start ថយក្រោយ ទៅ 1 ហើយរាប់ "bba" ដែលមានស្ទួន។ ការប្រៀបធៀបតែមួយនោះគឺជាបន្ទាត់ដែលមនុស្សភាគច្រើនភ្លេច។ ការសាកល្បងឧទាហរណ៍ពិបាកគឺជាអ្វីដែលចាប់បានវា។

7. Complexity។ តួអក្សរនីមួយៗត្រូវបានទស្សនាម្តងដោយ end ហើយ start ផ្លាស់ទីតែទៅមុខ ដូច្នេះពេលវេលាគឺ O(n)។ Map ផ្ទុកយ៉ាងច្រើនមួយធាតុក្នុងមួយតួអក្សរខុសគ្នា ដូច្នេះទំហំគឺ O(min(n, ទំហំ alphabet))។ យើងបំប្លែង O(n^2) ទៅជា O(n) ដោយរកឃើញការងារខ្ជះខ្ជាយ និងបន្ថែម hash map។ នោះគឺជារូបរាងធម្មតានៃចម្លើយ interview។

7. កំហុសទូទៅ

បន្ទាប់ពីបញ្ហាជាច្រើន កំហុសដដែលៗលេចឡើង។ ពិនិត្យកូដរបស់អ្នកសម្រាប់កំហុសទាំងនេះ មុនពេលអ្នកនិយាយថា "រួចហើយ"៖

• Off-by-one ក្នុង loop និង range។ < ទល់នឹង <=, length ទល់នឹង length - 1, range ពាក់កណ្តាលបើក [lo, hi) ទល់នឹងបិទ (ជំពូកទី 7)។
• ភ្លេច input ទទេ។ Array ទទេ, string ទទេ, 0 ធាតុ, head null នៃបញ្ជី។
• កែប្រែ input។ sort() ផ្លាស់ប្តូរ array ដើម។ ចម្លងវាមុន ([...arr].sort(...)) លុះត្រាតែបញ្ហាអនុញ្ញាត។
• sort() លំនាំដើមលើលេខ។ វាប្រៀបធៀបជា string ដូច្នេះ [10, 9, 1].sort() ផ្តល់ [1, 10, 9]។ តែងតែបញ្ជូន (a, b) => a - b (ជំពូកទី 8)។
• shift() ក្នុង loop។ វាគឺ O(n) លើ array ធម្មតា។ សម្រាប់ queue ប្រើ index pointer ឬ queue ពិត (ជំពូកទី 5)។
• ការភ្ញាក់ផ្អើលនៃ key ក្នុង hash map។ Map ប្រៀបធៀប object តាម identity៖ ប្រើ key ជា string ដូចជា `${x},${y}` សម្រាប់កូអរដោនេ។
• ខ្វះ base case ឬ visited set។ ទីមួយបណ្តាលឲ្យ stack overflow ទីពីរបណ្តាលឲ្យ loop គ្មានទីបញ្ចប់ក្នុង graph (ជំពូកទី 6, 11)។
• ប្រើ greedy ដោយគ្មានភស្តុតាង។ សាកល្បងវាជាមួយ counter-example តូចមួយ មុនពេលទុកចិត្ត (ជំពូកទី 13)។
• ដែនកំណត់ integer។ លេខបាត់បង់ភាពជាក់លាក់ក្រោយ 2^53 - 1។ ប្រើ BigInt នៅពេលចំនួនអាចកើនធំដល់ម្ល៉ឹង (មើលស៊េរី Math)។
• មិននិយាយ complexity។ តែងតែនិយាយវា។ វាជាពាក់កណ្តាលនៃចម្លើយ។

8. ក្រៅពី Interview ការជ្រើសនៅកន្លែងធ្វើការ

បញ្ហា interview តូច និងរៀបរយ។ កម្មវិធីពិតធំ និងរញ៉េរញ៉ៃ ប៉ុន្តែ ការគិតដូចគ្នា អនុវត្តបាន។ ការណែនាំស្មោះត្រង់មួយចំនួន៖

• វាស់មុន។ កូដភាគច្រើនមិនមែនជា bottleneck ទេ។ Loop O(n^2) ច្បាស់លាស់លើ 50 ធាតុគឺមិនអីទេ។ Profile (ក្នុង Node.js ប្រើ --cpu-prof ឬផ្ទាំង Performance របស់ browser) មុនអ្នកសរសេរអ្វីឡើងវិញ។
• ពេញចិត្តនឹងអ្វីដែលមានស្រាប់។ Map, Set, Array.prototype.sort និង library ដែលបានសាកល្បងល្អ ឈ្នះកំណែផ្ទាល់ខ្លួនរបស់អ្នកទាំងភាពត្រឹមត្រូវ និងល្បឿន។ ការសរសេរ structure ផ្ទាល់ខ្លួនគឺសម្រាប់ការរៀន ឬនៅពេល library មិនសម។
• គិតអំពីរូបរាងនៃទិន្នន័យ។ តើទំហំធំបំផុតដែលវាទៅដល់ក្នុងមួយឆ្នាំគឺប៉ុន្មាន? បញ្ជី 20 ធាតុ និង feed 20 លានជួរគឺជាបញ្ហាខុសគ្នា។
• ចងចាំ database។ WHERE លើជួរឈរដែលមាន index គឺជាការស្វែងរក B-tree ហើយ JOIN គឺជា algorithm hash ឬ merge។ គំនិតក្នុងស៊េរីនេះពន្យល់ថា ហេតុអ្វី query លឿន ឬយឺត។ នោះគឺជាស្ពានទៅកាន់ស៊េរី SQL។
• ភាពអានបាន សំខាន់។ កំណែយឺតបន្តិចដែលក្រុមរបស់អ្នកយល់ជារឿយៗជាជម្រើសវិស្វកម្មល្អជាង។ សរសេរមតិយោបល់ខ្លីមួយនៅពេលអ្នកជ្រើស structure មិនធម្មតា ហើយប្រាប់ហេតុផល។

9. រូបមន្ត៖ index.ts សម្រាប់ algolab

ដល់ពេលភ្ជាប់ library របស់អ្នកចូលគ្នា។ Module នីមួយៗដែលអ្នកបានសរសេរក្លាយជា namespace ក្នុងឯកសារចូលតែមួយ ដូច្នេះគ្មានការប៉ះទង្គិចឈ្មោះរវាង module ដែលចៃដន្យ export ឈ្មោះស្រដៀងគ្នា។

បង្កើត src/index.ts៖

export * as arrays from "./arrays.ts";
export * as hashMap from "./hash-map.ts";
export * as linkedList from "./linked-list.ts";
export * as stack from "./stack.ts";
export * as queue from "./queue.ts";
export * as recursion from "./recursion.ts";
export * as searching from "./searching.ts";
export * as sorting from "./sorting.ts";
export * as bst from "./bst.ts";
export * as priorityQueue from "./priority-queue.ts";
export * as graph from "./graph.ts";
export * as trie from "./trie.ts";
export * as unionFind from "./union-find.ts";
export * as greedy from "./greedy.ts";
export * as dp from "./dp.ts";

ឈ្មោះឯកសារខាងលើធ្វើតាមរូបមន្តក្នុងស៊េរីនេះ មួយ module ក្នុងមួយជំពូក។ ប្រសិនបើអ្នកដាក់ឈ្មោះខុសគ្នា ឬដាក់ structure ពីរក្នុងឯកសារតែមួយ សូមផ្លាស់ប្តូរ path នៅបន្ទាត់នោះឲ្យត្រូវគ្នា។ រត់ ls src ដើម្បីមើលអ្វីដែលអ្នកមាន។

ឥឡូវនេះជា demo តូចមួយដែលប្រើ library ដូចអ្នកប្រើប្រាស់។ បង្កើត demo.ts ក្នុងថត algolab៖

import { trie, unionFind, dp, greedy } from "./src/index.ts";

// A tiny autocomplete.
const words = new trie.Trie();
for (const w of ["dog", "door", "dot", "cat"]) words.insert(w);
console.log(words.suggest("do"));

// How many separate networks?
console.log(unionFind.countComponents(5, [[0, 1], [1, 2], [3, 4]]));

// Fewest coins, and a case where greedy loses.
console.log(dp.coinChange([4, 3, 1], 6));
console.log(greedy.greedyCoins([4, 3, 1], 6));

// Longest common subsequence.
console.log(dp.lcs("AGGTAB", "GXTXAYB"));

npx tsx demo.ts

[ 'dog', 'door', 'dot' ]
2
2
[ 4, 1, 1 ]
4

បន្ថែមបន្ទាត់សម្រាប់ module ផ្សេងទៀតរបស់អ្នក (HashMap, PriorityQueue, Graph) ហើយហៅវាតាមរបៀបដូចគ្នា ឧទាហរណ៍ new graph.Graph() បន្ទាប់ពីអ្នកពិនិត្យឈ្មោះ class ដែលអ្នកបានជ្រើសក្នុងជំពូកទាំងនោះ។

ជាចុងក្រោយ រត់ test suite ទាំងមូលម្តង ដើម្បីមើលពេញ library ដំណើរការ៖

npx tsx --test

Test suite ដែលជាប់ ដែល អ្នក បានសរសេរ សម្រាប់ structure ដែល អ្នក បានសាងសង់ គឺជារឿងល្អមួយដែលត្រូវមាន។ Commit វា ហើយរក្សាទុកជាឯកសារយោងដែលអ្នកអាចត្រឡប់មកមើលមុន interview។

10. សាកល្បងដោយខ្លួនឯង

1. រត់វិធីសាស្ត្រ។ ជ្រើសបញ្ហាដែលអ្នកមិនទាន់ឃើញ៖ "ដោយមាន array នៃ integer ត្រឡប់ប្រវែងនៃលំដាប់លេខជាប់គ្នាវែងបំផុត (ដូច 100, 4, 200, 1, 3, 2 ផ្តល់ 4) ក្នុង O(n)។" ឆ្លងកាត់ប្រាំពីរជំហានទាំងអស់លើក្រដាស មុនសរសេរកូដ។ ជំនួយ៖ Set និងការពិនិត្យ "តើនេះជាការចាប់ផ្តើមនៃលំដាប់ឬទេ?" (បែប interview។)
2. Brute force ជា oracle។ សរសេរ random tester សម្រាប់ longestUnique៖ បង្កើត string ចៃដន្យ 1,000 ដែលមានអក្សរ a ដល់ d (ប្រវែង 0 ដល់ 12) ហើយ assert ថាវាស្មើនឹង longestUniqueBrute សម្រាប់នីមួយៗ។ តើវាមិនស៊ីគ្នាដែរឬទេ? លុបការពិនិត្យ prev >= start ហើយរត់ម្តងទៀត ដើម្បីមើល test ចាប់ bug។
3. ជ្រើសឧបករណ៍។ សម្រាប់នីមួយៗ ហៅឈ្មោះ structure ឬបច្ចេកទេស និងថ្លៃចំណាយ ដោយមិនសរសេរកូដ៖ (a) "បង្ហាញប្រកាសដែលមានអ្នកចូលចិត្តច្រើនបំផុត 10 ក្នុងចំណោម 5 លាន។" (b) "តើពាក្យពីរនេះមានអក្សរដូចគ្នាដែរឬទេ?" (c) "ជើងហោះហើរតិចបំផុតដើម្បីទៅពីទីក្រុង A ទៅទីក្រុង B។" (d) "ពិនិត្យថាតើបញ្ជីការងារ build មាន dependency វិលជុំឬទេ។" (e) "Merge ឯកសារ log k ដែលបាន sort ចូលជាមួយ។"
4. Mock interview។ យកបញ្ជីលំហាត់នៃជំពូកណាមួយ ជ្រើសបញ្ហាមួយដោយចៃដន្យ ហើយដោះស្រាយក្នុង 25 នាទីដោយនិយាយឮៗ ដូចកំពុងនិយាយទៅកាន់អ្នកសម្ភាសន៍។ ថតខ្លួនឯងប្រសិនបើអាច ហើយស្តាប់រកភាពស្ងៀមស្ងាត់យូរ និងជំហានដែលរំលង។
5. បំពេញ algolab។ ប្រាកដថារាល់ module មាន test យ៉ាងតិចមួយ ហើយ npx tsx --test ជាប់ទាំងអស់។ បន្ទាប់មកបន្ថែម README.md ដែលរាយ សម្រាប់ module នីមួយៗ ថាវាសម្រាប់អ្វី និងថ្លៃចំណាយនៃប្រតិបត្តិការចម្បងរបស់វា។
6. Two-sum បីវិធី។ ដោះស្រាយ "រកលេខពីរដែលបូកបានគោលដៅ" ជាមួយ (a) loop ពីរជាន់, (b) sorting និង two pointers និង (c) hash map។ ប្រៀបធៀបពេលវេលា និងទំហំនៃនីមួយៗ ហើយសរសេរប្រយោគមួយអំពីពេលដែលអ្នកនឹងជ្រើសនីមួយៗ។

11. កន្លែងដែលត្រូវទៅបន្ត

ឥឡូវនេះអ្នកមានមូលដ្ឋានគ្រឹះដែល technical interview និងវិស្វកម្មប្រចាំថ្ងៃភាគច្រើនត្រូវបានសាងសង់លើ។ វិធីមួយចំនួនដើម្បីបន្ត៖

• អនុវត្តបន្តិចរាល់ថ្ងៃ។ ជំនាញលូតលាស់ដោយការធ្វើម្តងហើយម្តងទៀតលើបញ្ហាដែលអ្នកមិនធ្លាប់ឃើញ។ ជ្រើសសំណុំបញ្ហាដែលដាក់ជាក្រុមតាម pattern (array, graph, DP) ហើយធ្វើពីរឬបីក្នុងមួយសប្តាហ៍។ គុណភាពឈ្នះបរិមាណ៖ បន្ទាប់ពីបញ្ហានីមួយៗ សរសេរ សញ្ញា ដែលនាំអ្នកទៅរកបច្ចេកទេស។
• ស្វែងយល់ជ្រៅអំពី database។ អ្វីៗអំពី tree, hashing និង sorting លេចឡើងក្នុងរបៀបដែល database រក្សាទុក និង query ទិន្នន័យ។ ស៊េរី SQL នៅលើគេហទំព័រនេះសាងសង់លើនេះដោយផ្ទាល់៖ index គឺជា B-tree, join គឺជា algorithm hash ឬ merge ហើយ ORDER BY គឺជា sorting។
• រៀន system design។ ជំហានបន្ទាប់នៃមាត្រដ្ឋានគឺការបញ្ចូលបំណែកទាំងនេះគ្នា៖ cache គឺជា hash map ដែលមានច្បាប់ eviction, job queue គឺជា queue, rate limiter គឺជា sliding window, leaderboard គឺជា heap ឬ structure ដែលបាន sort, search service គឺជា trie ឬ index ហើយ feed គឺជាការ merge នៃបញ្ជីដែលបាន sort។ ការគិតជា structure ធ្វើឲ្យការរចនាធំៗកាន់តែងាយវិភាគ។
• ត្រឡប់ទៅមើលជំពូកឡើងវិញ។ ជ្រើសមួយដែលអ្នកយល់ថាពិបាកបំផុត។ វានឹងមានអារម្មណ៍ងាយជាងនៅលើកទីពីរ ហើយឥឡូវអ្នកមានជំពូកក្រោយៗដើម្បីផ្តល់បរិបទ។ ស៊េរី Math for Programmers ជាពិសេស ជំពូក Big-O គឺជាមិត្តរួមដ៏ល្អសម្រាប់ផ្នែកវិភាគ។
• បន្តសាងសង់។ ប្រើ algolab ក្នុងគម្រោងពិតតូចមួយ ដូចជា autocomplete ក្នុង command-line, កម្មវិធីរកផ្លូវ ឬ task scheduler។ ការសរសេរអ្វីមួយដែលអ្នកពិតជាចង់ប្រើ ពង្រឹងគំនិតបានល្អជាងលំហាត់ណាមួយ។

សូមអរគុណដែលបានរៀនតាមស៊េរីនេះ។ អ្នកបានចាប់ផ្តើមពី "ហេតុអ្វី data structure សំខាន់" ហើយឥឡូវអ្នកអាចមើលបញ្ហាមួយ ហៅឈ្មោះរូបរាងរបស់វា ជ្រើស structure ដោយគិតដល់ថ្លៃចំណាយរបស់វា និងពន្យល់ហេតុផលរបស់អ្នកឲ្យច្បាស់។ នោះគឺជាជំនាញពិតប្រាកដ ហើយវានៅជាមួយអ្នករហូតដល់ក្រោយពេលព័ត៌មានលម្អិតរសាត់បាត់។

ដើម្បីចាប់ផ្តើមឡើងវិញពីដើម ឬពិនិត្យមើលប្រធានបទមួយ សូមត្រឡប់ទៅ ហេតុអ្វី Data Structure និង Algorithm សំខាន់។