โจทย์ LeetCode ยากหลายข้อ จริง ๆ แล้วเป็นปัญหาเงื่อนไขที่ง่าย

(buttondown.com)

6 คะแนน โดย GN⁺ 2025-09-13 | 2 ความคิดเห็น | แชร์ทาง WhatsApp

แม้แต่ โจทย์ยากของ LeetCode ก็แก้ได้ง่ายขึ้นมากเมื่อใช้ constraint solver
แทนที่จะใช้ dynamic programming ที่ซับซ้อนหรืออัลกอริทึมที่เขียนเอง ก็สามารถใช้ constraint solver อย่าง MiniZinc เพื่อแก้ปัญหา optimization ทางคณิตศาสตร์ได้อย่างเรียบง่าย
ภาษาโปรแกรมแบบดั้งเดิมแสดงปัญหา optimization ทางคณิตศาสตร์ลักษณะนี้ได้ยาก จึงเป็นจุดแข็งของ แนวทางแบบอิงข้อจำกัด
ต่อให้มี กรณียกเว้นหรือเงื่อนไขเพิ่มเติม ก็แทบไม่ต้องเปลี่ยนโมเดลใน constraint solver มากนัก
แม้ความซับซ้อนด้าน runtime อาจช้ากว่าอัลกอริทึมที่ปรับแต่งเอง แต่ก็มีข้อดีมากในด้าน ความยืดหยุ่นและประสิทธิภาพการพัฒนา

โจทย์ LeetCode ที่แก้ด้วย constraint solver

การเลือกเครื่องมือที่เหมาะสม

ผู้เขียนเคยเจอโจทย์ “ปัญหาเงินทอนเหรียญ” ในการสัมภาษณ์ครั้งแรกหลังเรียนจบมหาวิทยาลัย
- เมื่อกำหนดมูลค่าเหรียญมาให้ ต้องหาว่าจำนวนเหรียญ น้อยที่สุด ที่ใช้ทอนเงินตามจำนวนที่กำหนดคือเท่าใด
- ตอนนั้นใช้ greedy algorithm แบบง่าย ๆ แต่ไม่สามารถรับประกันคำตอบที่ดีที่สุดได้ในทุกกรณี
- คำตอบที่ถูกต้องคือ dynamic programming แต่ผู้เขียนทำ implementation ไม่ได้ จึงสัมภาษณ์ไม่ผ่าน
แต่ถ้าไม่เขียนอัลกอริทึมเองโดยตรง แล้วใช้ constraint solver อย่าง MiniZinc ก็แก้ได้ง่ายมาก
- โค้ดตัวอย่าง:
```
int: total;
array[int] of int: values = [10, 9, 1];
array[index_set(values)] of var 0..: coins;

constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
solve minimize sum(coins);
```
- สามารถลองรัน ตัวอย่าง MiniZinc ได้โดยตรงบนออนไลน์
  โฆษณา
- ตัว solver จะค่อย ๆ หา optimal solution ให้เอง

ปัญหา optimization/satisfaction ที่หลากหลาย

ปัญหา optimization ทางคณิตศาสตร์ ที่พบบ่อยใน LeetCode และที่อื่น ๆ (มีทั้งการ maximize/minimize objective function และมีหลายข้อจำกัด)
มักยากเมื่อแก้ด้วยภาษาโปรแกรมทั่วไปเพราะต้องทำ implementation ระดับล่าง แต่กลับเหมาะกับ constraint solver มาก
ตัวอย่างเช่น ปัญหาหลายลักษณะด้านล่างนี้เข้าข่ายดังกล่าว

ตัวอย่าง 1: ปัญหาหากำไรจากหุ้นสูงสุด

“จากรายการราคาหุ้นที่ให้มา จงหาว่าหากซื้อหนึ่งครั้งแล้วขายในภายหลังหนึ่งครั้ง จะได้ กำไรสูงสุด เท่าใด”
- แบบดั้งเดิมต้องใช้ brute force O(n²) หรืออัลกอริทึมที่เหมาะที่สุด O(n)
- ใน MiniZinc สามารถนิยามเป็นปัญหาเงื่อนไขได้อย่างง่ายดังนี้
```
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
var int: buy;
var int: sell;
var int: profit = prices[sell] - prices[buy];

constraint sell > buy;
constraint profit > 0;
solve maximize profit;
```

ตัวอย่าง 2: ทำให้ได้ค่า 0 ด้วยการบวก/ลบจำนวนที่กำหนด (ปัญหา satisfaction)

“สามารถเลือกตัวเลขสามตัวจากลิสต์ แล้วบวกหรือลบให้ผลรวมเป็น 0 ได้หรือไม่?”
- ไม่ได้ต้องหาค่าที่ดีที่สุด แต่ต้องการแค่ คำตอบที่เป็นไปได้
- ใน constraint solver เขียนได้ดังนี้
```
include "globals.mzn";
array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array[index_set(numbers)] of var {0, -1, 1}: choices;

constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
constraint count(choices, -1) + count(choices, 1) = 3;
solve satisfy;
```
  โฆษณา

ตัวอย่าง 3: พื้นที่สี่เหลี่ยมผืนผ้าสูงสุดในฮิสโตแกรม

“จากฮิสโตแกรมที่กำหนดความสูงของแต่ละแท่งมา จงหาว่า พื้นที่ของสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุด ที่สร้างได้มีค่าเท่าใด”
- แบบดั้งเดิมต้องใช้อัลกอริทึมที่ซับซ้อนและต้องจัดการหลายสถานะ
- แต่สามารถอธิบายวิธีแก้ด้วยข้อจำกัดอย่างกระชับได้
```
array[int] of int: numbers = [2,1,5,6,2,3];

var 1..length(numbers): x; 
var 1..length(numbers): dx;
var 1..: y;

constraint x + dx <= length(numbers);
constraint forall (i in x..(x+dx)) (y <= numbers[i]);

var int: area = (dx+1)*y;
solve maximize area;

output ["(\(x)->\(x+dx))*\(y) = \(area)"]
```

แนวทางแบบ constraint solver ดีกว่าหรือไม่?

ในสถานการณ์สัมภาษณ์งาน มันยังมีจุดอ่อนในแง่คำถามเรื่อง time complexity
- runtime ของ constraint solver คาดเดาได้ยาก และโดยทั่วไปมักช้ากว่าอัลกอริทึมที่ออกแบบเฉพาะทางอย่างเหมาะสม
- แต่ก็ยังดีกว่าอัลกอริทึมคุณภาพต่ำที่เขียนผิดเอง และสำหรับโปรแกรมเมอร์ส่วนใหญ่ การจะเขียนวิธีที่ดีที่สุดขึ้นมาใหม่ทุกครั้งก็ไม่ใช่เรื่องง่าย
โฆษณา
จุดแข็งที่แท้จริงคือความยืดหยุ่นเมื่อเพิ่มข้อจำกัดใหม่
- ตัวอย่างเช่น ในโจทย์หุ้น ถ้าเปลี่ยนจากซื้อขายครั้งเดียวเป็นหลายครั้ง ความซับซ้อนของอัลกอริทึมจะเพิ่มขึ้นอย่างมาก
- แต่ในโมเดลข้อจำกัดของ MiniZinc สามารถรองรับความต้องการที่ซับซ้อนขึ้นมากได้ด้วยการแก้โค้ดเพียงเล็กน้อย
```
include "globals.mzn";
int: max_sales = 3;
int: max_hold = 2;
array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
array [1..max_sales] of var int: buy;
array [1..max_sales] of var int: sell;
array [index_set(prices)] of var 0..max_hold: stocks_held;
var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);

constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
constraint profit > 0;

constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
constraint alldifferent(buy ++ sell);
solve maximize profit;

output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];
```
ตัวอย่างปัญหา constraint บนออนไลน์มักเน้นพัซเซิลอย่าง Sudoku แต่ในความเป็นจริงสามารถนำไปใช้กับ business logic หรือข้อกำหนดด้าน optimization ได้อย่างน่าสนใจและเป็นประโยชน์มากกว่า
- เช่น ยังมีโอกาสใช้เทคนิค optimization ขั้นสูงอย่าง symmetry breaking ได้ด้วย

สรุปและข้อมูลอ้างอิง

บทความนี้มาจากจดหมายข่าวรายสัปดาห์ของผู้เขียน ซึ่งพูดถึง ประวัติศาสตร์ซอฟต์แวร์, formal methods, เทคโนโลยีใหม่ และทฤษฎีวิศวกรรมซอฟต์แวร์
หากสนใจ สามารถดู สมัครรับข้อมูล หรือ เว็บไซต์หลัก ของผู้เขียนได้
หนังสือใหม่ของผู้เขียน "Logic for Programmers" ก็กำลังวางจำหน่ายอยู่

2 ความคิดเห็น

kohs100 2025-09-15

ปกติแล้วโจทย์อัลกอริทึมก็มักจะมีเงื่อนไขด้าน time/space complexity กำกับอยู่ไม่ใช่เหรอ? การบอกว่าให้แก้ด้วย constraint solver ได้ จริง ๆ แล้วก็แสดงได้แค่ว่ามีความสามารถในการแปลงโจทย์ให้อยู่ในรูป constraint เท่านั้นเอง... แต่ผมก็ยังไม่ค่อยแน่ใจว่านั่นเป็นทักษะที่จำเป็นต่อการทำงานจริงแค่ไหนนะ...

GN⁺ 2025-09-13

ความคิดเห็นจาก Hacker News

ปัญหาใหญ่ที่สุดของคำถามสัมภาษณ์แบบ Leetcode คือเราไม่สามารถขอคำอธิบายเพิ่มเติมได้ วิธีคิดของฉันต่างจากคนทั่วไป เลยรู้สึกว่า Leetcode พึ่งการท่องจำคำตอบมากกว่า ถ้าเป็นโจทย์ที่มีบริบทมากพอก็ยังพอเข้าใจในโลกจริงได้ แต่ส่วนใหญ่คำอธิบายไม่พอจนจับประเด็นโจทย์ไม่ได้ ทุกวันนี้เลยปฏิเสธทั้ง Leetcode และด่านสัมภาษณ์แบบอัตโนมัติด้วย AI ไปเลย งานที่เป็นการบ้านหรือสัมภาษณ์แบบ 1:1 หรือแชร์หน้าจอนั้นโอเค ถ้าเว็บ Leetcode มีเฉลยและคำตอบที่ดีจริง การเรียนเองก็คงง่ายกว่านี้มาก แต่ความเป็นจริงมันยากเกินไป ไม่ใช่แค่เรื่องความสามารถ แต่เป็นเพราะวิธีคิดของฉันไม่เข้ากับรูปแบบปัญหานี้ การต้องทำข้อสอบแบบเลือกตอบต่อไปเรื่อย ๆ โดยห้ามถามอะไรเลยมันเหมือนระบบที่ออกแบบมาให้ล้มเหลว โดยเฉพาะกำลังพูดถึงโจทย์แนว AI/Leetcode สำหรับคัดกรองก่อนสัมภาษณ์ ถ้าเป็นสัมภาษณ์กับคนจริงที่มีการถามตอบกัน ฉันมองว่าดีพอสมควร
- การสัมภาษณ์แบบ LC(Leetcode) ก็เหมือนการทดสอบความเร็ววิ่ง 100 เมตรที่ฝึกมาโดยเฉพาะ แต่การทำงานจริงเหมือนมาราธอนยาว ๆ ที่หยุดแล้วกลับมาใหม่ได้หลายครั้ง ถึงอย่างนั้นตอนนี้ถ้าอยากได้เงินเดือนสูงจากบริษัทยักษ์ใหญ่อย่าง SMEGMA ก็ต้องเล่นเกมนี้ เช่น ฉันสร้าง 2D game engine เองได้ แต่คงไม่ผ่านสัมภาษณ์ LC ที่ต้องทำโจทย์ยากหลายข้อพร้อมตีลังกาหลังไปด้วยหรอก ฉันยอมรับเรื่องนั้นแล้ว engine ที่ฉันทำ
- มันไม่ใช่ว่าท่องเฉลยแล้วจะจบทั้งหมด ถึงท่องมาก็อาจไปตันกับคำถามต่อยอดได้ แต่ถ้าท่องมาแล้วแก้คำถามต่อยอดได้ดี ฉันก็คิดว่าไม่ได้มีปัญหาอะไรกับโจทย์สไตล์ Leetcode ความสามารถในการแก้ปัญหาคือความสามารถในการจับแพตเทิร์น และยิ่งรู้แพตเทิร์นมากก็ยิ่งแก้ปัญหาเก่งขึ้น ตอนนี้ GPT ก็ช่วยทั้งแก้โจทย์และอธิบายได้ ทำให้ฝึกความสามารถแบบนี้ได้ง่ายขึ้น ดังนั้นเริ่มฝึกตั้งแต่ตอนนี้ก็ดีกว่า
- เห็นด้วยสุด ๆ ฉันเองเพิ่งสัมภาษณ์ล่าสุด ได้คะแนนสูงสุดจากงานที่บ้าน และทั้งวิศวกรกับ CEO ก็ประทับใจ แต่ CTO ดันโผล่มาให้ทำ live coding แบบกะทันหัน สุดท้ายเลยไม่ผ่าน การสัมภาษณ์ 11 สัปดาห์กลายเป็นเสียเปล่า น่าหงุดหงิดที่กระบวนการงี่เง่านี้ยังมีอยู่ สิ่งที่ฉันเดโม/ทำไว้คือ ลิงก์ monumental และผลงาน, โค้ดบน GitHub
- หรือจริง ๆ แล้วการที่ถามคำถามให้ชัดเจนไม่ได้ นั่นแหละคือความสามารถที่เขาพยายามวัดอยู่? คือดูว่าผู้สมัครเข้าหาการแก้ปัญหาอย่างไร ถ้าบังคับให้ทุกคนเข้าหาแบบตายตัว ซอฟต์แวร์ทั้งหมดจะยิ่งซับซ้อนและเละเทะกว่าเดิม สิ่งที่ยากจริงไม่ใช่การเขียนโค้ดไม่กี่บรรทัด แต่คือกระบวนการแก้ปัญหา
- ที่ที่ฉันเคยสัมภาษณ์ แม้จะให้โจทย์ LC แค่หนึ่งหรือสองข้อ แต่ถ้าขอคำอธิบายเพิ่ม เขาก็เปลี่ยนเป็นคุยสดพร้อมเขียนโค้ดทันที วิธีนี้มีข้อเสียอยู่อย่างหนึ่งคือเพิ่มแรงกดดันทางจิตใจของการ live coding แบบเรียลไทม์
พอเจอโจทย์สัมภาษณ์แบบนี้ ฉันรู้สึกว่าเขาไม่ได้อยากให้เรา "ใช้" constraint solver แต่ต้องการให้เรา "เขียน" constraint solver ที่พอดีกับปัญหาที่จำกัดนั้นขึ้นมาเอง
- ใช่เลย เพราะงั้นฉันถึงคิดว่าวิธีสัมภาษณ์แบบนี้งุ่มง่ามตั้งแต่ราก ในสถานการณ์วิศวกรรมจริง เรานั่งดื่มกาแฟ อ่านเปเปอร์ เปิดดูในห้องสมุด เดินเล่นคิดไปด้วย และอ้างอิงเครื่องมือที่มีอยู่แล้ว (เช่น constraint solver หรือ LLM) เพื่อแก้ปัญหาให้จบ 100% ได้ แต่ในสถานการณ์สัมภาษณ์ฉันอาจแก้ไม่ได้แม้แต่ 0% ฉันไม่เคยแม้แต่คิดจะเข้าบริษัทที่ใช้การสัมภาษณ์แบบนี้
- ฉันก็คิดแบบนั้นจริง ๆ ปัญหา NP ส่วนใหญ่แปลงเป็นปัญหา constraint ได้ จริงอยู่ที่ constraint solver จะเป็นคำตอบที่เหมาะหรือไม่ขึ้นอยู่กับโดเมน และในบริบทสัมภาษณ์มันแทบไม่ใช่คำตอบที่ถูก เพราะ solver พวกนี้มักช้ากว่า dynamic programming ง่าย ๆ มาก
- บางบริษัทอาจใช่ แต่หลายที่ก็ไม่ใช่ โดยทั่วไปการใช้ LC ในสัมภาษณ์มักมีเหตุผลเดียวคือกระบวนการจ้างงานที่ไม่มีประสิทธิภาพ แม้แต่คนที่อยู่ในกระบวนการก็รู้ว่าควรยกเครื่องใหม่ แต่ไม่มีอำนาจหรือกระจัดกระจายเกินกว่าจะเปลี่ยนได้ บริษัทใหญ่บางแห่งให้ HR หมุนคำถามเดิมไปหลายทีมเพื่อ "มาตรฐาน" ส่วนบริษัทเล็กไม่มีเวลาสร้างโจทย์เองก็เลยคัดมาจากอินเทอร์เน็ต ในสถานการณ์แบบนี้ แม้แต่ผู้สัมภาษณ์สายเทคนิคเองก็มักวิจารณ์ LC interview และพยายามหาผู้สมัครที่โดดเด่นจริง ๆ ถ้าคุณแค่แสดงให้เห็นว่ามีความสนใจหรือมีความรู้เรื่อง constraint solver ก็ได้คะแนนค่อนข้างดีแล้ว
- ถ้ามีใครแก้โจทย์ LC hard ด้วย constraint solver แล้วไม่รับคนนั้นเข้าทำงาน คนโง่ก็คือผู้สัมภาษณ์เอง คนที่รู้ว่า constraint solver คืออะไร และนิยามปัญหาเพื่อเอาไปใช้เป็นนั้นหายากมาก ฉันเองเคยใช้ตอนปี 3 แค่การเขียนข้อจำกัดก็ซับซ้อนจนปวดหัวแล้ว
- ประเด็นนี้ทั้งถูกและผิด ฉันเคยถามคำถามแบบนี้ในการสัมภาษณ์ ถ้าผู้สมัครนึกถึง constraint solver ได้ ฉันให้คะแนนดีเลย เพราะในงานวิศวกรรมจริง constraint solver ถูกประเมินค่าต่ำเกินไป ทั้งยังเป็นตัวบ่งชี้ว่าเขารู้วิธีหาคำตอบที่ถูกต้องได้เร็วแน่ ๆ แน่นอนว่าหลังจากนั้นฉันก็คงมีคำถาม whiteboard ต่อเพื่อดูทักษะการเขียนโค้ดจริง แต่การเสนอ constraint solver เป็นคำตอบนั้น ฉันมองว่าไม่เลวเลย
เป็นมุมมองที่เจ๋ง แต่ฉันคิดว่าไม่ค่อยเข้ากับการสัมภาษณ์ในโลกจริง แก่นของโจทย์พวกนี้คือเขาอยากตรวจว่าเรามีความสามารถในการ "ใช้หัวคิด" แค่ไหน การแก้ด้วย constraint formulation อย่างเดียวจะแสดงแค่ระดับประสบการณ์และความรู้ แต่ไม่ได้เผยว่า "คิดเป็น" หรือไม่
- ผู้สัมภาษณ์มักชอบหยิบโจทย์ใน Leetcode "Top Interview 150" หมวด "Array String" มาใช้ สำหรับฉันที่เป็น backend Python developer มันรู้สึกไกลจากงานประจำมาก ส่วนใหญ่ต้องการอัลกอริทึมจัดการ array แบบ in-place ซึ่งปกติมีประโยชน์เฉพาะกับภาษาเน้นประสิทธิภาพอย่าง C หรือ Rust มากกว่า ตรงกันข้าม โจทย์หมวด "Hashmap" กลับมีประโยชน์กว่าในการแสดงการใช้เครื่องมือที่เหมาะกับภาษา และยังมีหลายโจทย์ที่คุมระดับความยากไม่ได้ เช่น โจทย์ระดับ "ง่าย" อย่าง Majority Element ที่ในความเป็นจริงต้องอาศัยอัลกอริทึมเชิงประวัติศาสตร์อย่าง Boyer–Moore จึงยากจะเรียกว่า "ง่าย"
- รอบสุดท้ายที่ฉันเจอจาก Meta ล่าสุดเป็นกระบวนการที่เอาไว้เช็กอย่างเดียวว่าคุณท่องโจทย์เฉพาะของเขามาซ้ำ ๆ มากแค่ไหน ถ้าตอบต่างจากคำตอบในตำรากลับทำให้เขางงเสียอีก เลยรู้สึกว่าความ "ฉลาดพลิกแพลง" ไม่ได้สำคัญเท่าไร
- อัลกอริทึม DP แบบ bottom-up ต้องใช้ความคิดอยู่บ้าง แต่ปัญหาส่วนใหญ่แก้แบบ top-down (recursion + memoization) ได้ เช่น ปัญหา coin change ก็อาจแก้ด้วยการค้นหาแบบ A* ได้ดีกว่า แต่ในโลกจริง โปรแกรมเมอร์ส่วนใหญ่แทบไม่มีวันต้องใช้อัลกอริทึมพวกนี้ สิ่งที่สำคัญจริงคือการมองออกว่าคุณเผลอเขียนโค้ดที่มี time complexity เป็น O(n^2) หรือเปล่า accidentallyquadratic.tumblr.com แสดงให้เห็นว่าคนเก่งในโปรเจกต์ดัง ๆ ก็พลาดแบบนี้กันบ่อย ดังนั้นความสามารถในการสร้างอัลกอริทึมตอนทดสอบจึงเป็นคนละเรื่องกับความสามารถในการจับพลาดเชิงอัลกอริทึมระหว่างทำงานจริง
- เวลาใช้การสัมภาษณ์เพื่อวัดทักษะแก้ปัญหา ฉันให้ความสำคัญกับกระบวนการคิด วิธีสื่อสาร และการแตกปัญหาออกเป็นส่วนย่อย ๆ ฉันคิดว่าสำคัญกว่ามากที่จะเตรียมคำถามที่ปรับระดับความยากได้ เพื่อให้ผู้สมัครทุกคนมีโอกาสแสดงศักยภาพ การตอบคำตอบที่นึกออกทันทีแบบโพล่งออกมา หรือการติดอยู่นานมากนั้น แทบไม่ได้ช่วยให้ผู้สัมภาษณ์รู้เรื่องอะไรเพิ่มเท่าไร เพราะงั้นคำถามสัมภาษณ์เชิงแก้ปัญหามีประโยชน์มากได้ แต่ก็น่าเสียดายที่ในโลกจริงมักใช้งานกันไม่ดี
- โจทย์พวกนี้ไม่ได้วัด "ความฉลาด" จริง ๆ แต่วัดว่าคุณจำแพตเทิร์นตายตัวสักประมาณ 12 แบบได้มากแค่ไหน ผู้สมัครแทบทั้งหมดถูกตัดสินจากความจำที่เตรียมมา ไม่ใช่การแก้ปัญหาอย่างสร้างสรรค์ของตัวเอง โจทย์ LeetCode ถูกทำให้เป็นเกมมากเกินไปจนเหมือนเป็นแค่เครื่องมือวัดว่าใครเต็มใจเตรียมตัวมากกว่า
การสัมภาษณ์ส่วนใหญ่นี่เหมือนตั้งโจทย์ว่า "ถ้าผู้ป่วยเบาหวานไม่สามารถสังเคราะห์อินซูลินเองที่บ้านได้ ก็ถือว่าโกงเกมชีวิต" ภรรยาฉันฉีดอินซูลินเมื่อระดับน้ำตาลสูง เช่นเดียวกัน ถ้าเป็นปัญหาแบบ constraint ก็ควรใช้ solver ถ้าบริษัทไม่ได้ทำซอฟต์แวร์ constraint solver เอง ฉันไม่เข้าใจว่าทำไมต้องตั้งสมมติฐานว่า "ซอฟต์แวร์แบบนี้ไม่มีอยู่" แล้วบังคับให้สร้างใหม่ตั้งแต่ศูนย์
- แก่นแท้คือมันไม่ใช่การวัดว่าคุณสังเคราะห์อินซูลินได้ในยามวิกฤตไหม แต่เป็นแบบทดสอบความถนัดก่อนสัมภาษณ์ว่าคุณท่องตำราได้ภายในหนึ่งสัปดาห์ และพูดมันออกมาทางโทรศัพท์ได้ดีแค่ไหน
- ถ้าคุณหาวิธีใช้ constraint solver เพื่อแก้โจทย์ได้อย่างมีประสิทธิภาพ คุณก็คงเขียน for loop สองชั้นกับ recursive helper function สักตัวเพื่อแก้โจทย์ของเล่นพวกนี้ได้สบาย
- (ไม่มีเนื้อหาสำคัญ)
- ถ้าจะปกป้อง coding test สักหน่อย คนส่วนใหญ่ที่แก้โจทย์ DP ง่าย ๆ ไม่ได้ก็มักทำงานจริงได้ไม่ดีเหมือนกัน แน่นอนว่าต้องมีข้อยกเว้น แต่จากประสบการณ์ของฉันมันเป็นแบบนั้น
ถ้าพูดถึงภาษา constraint programming ก็ต้องพูดถึง Håkan Kjellerstrand เสมอ เขาดูแลเว็บไซต์ที่ยอดเยี่ยมซึ่งรวมตัวอย่างและโจทย์จำนวนมหาศาล รวมถึง MiniZinc ด้วย hakank minizinc
- และเขาไม่ใช่แค่ทำเว็บไซต์ดี ๆ เท่านั้น แต่ยังเป็นคนที่ใจดีมากจริง ๆ
เมื่อนานมากแล้ว ตอนที่ฉันยังเป็นมือใหม่และยังไม่ได้เรียนเรื่อง constraint solver ในหลักสูตรวิศวกรรมคอมพิวเตอร์มหาวิทยาลัย ฉันเจอปัญหานี้ตอนเพื่อนขอให้ช่วยทำแอปจัดตารางให้สปอร์ตคลับ ตอนแรกดูเหมือนง่าย แต่พอลองทำจริงฉันกลับไม่รู้ตัวเลยว่ากำลังชนปัญหาใหญ่มหึมาอยู่ กว่าจะรู้ก็เป็นบทเรียนที่ดีเรื่องความทะนงตัว และประสบการณ์นั้นช่วยฉันได้มากเวลาคุยเรื่องตารางเวลา เดดไลน์ และความคาดหวัง
- อาจเป็นคำถามพื้นฐาน แต่ฉันสงสัยว่ามันน่าจะแก้ด้วย "linear optimization" ได้ง่ายกว่า constraint solver หรือเปล่า จากประสบการณ์ที่เคยเขียนเอง ข้อดีของ linear optimization คือมันจัดการความขัดแย้งระหว่างกฎต่าง ๆ ด้วยน้ำหนัก แล้วหาคำตอบที่มี "ผลข้างเคียง" น้อยที่สุดได้
- เมื่อ 25 ปีก่อนตอนเรียนมัธยม ช่วงที่เพิ่งเริ่มเรียน TI-Basic กับ VB6 และทำงานพาร์ตไทม์ที่ร้านเบอร์เกอร์ ฉันได้ยินผู้จัดการบ่นว่าการจัดตารางพนักงานแต่ละสัปดาห์มันยากมาก เลยพูดไปว่า "ผมพอรู้คอมพิวเตอร์ เดี๋ยวทำโปรแกรมจัดตารางให้ครับ!" แล้วก็พบอย่างรวดเร็วว่าการเขียน scheduler มันยากแค่ไหน จากนั้นก็ยอมแพ้ทันที
"ถ้าเอาโจทย์แบบนี้ไปใช้สัมภาษณ์ ประเด็นของผู้เขียนคือ ถ้าผู้สัมภาษณ์ถามว่า 'runtime complexity ของอัลกอริทึมนี้คืออะไร?' ก็จะไปต่อไม่ถูก" กล่าวคือ constraint solver เองก็ไม่ใช่คำตอบของโจทย์ Leetcode hard ถ้ามันไม่สามารถแก้ได้เร็วพอ ถ้าข้อกำหนดด้าน runtime ผ่อนคลาย วิธีง่าย ๆ ก็อาจพอใช้ได้ แต่การหาวิธีที่มีประสิทธิภาพคือส่วนสำคัญของความท้าทายทั้งหมด
- ในงานจริง สิ่งที่ต้องการบ่อยกว่าการหา "วิธีที่มีประสิทธิภาพที่สุด" คือการคิดวิธีแก้ที่ตอบรับความต้องการใหม่ ๆ ได้เร็ว ดังนั้นจึงน่าสงสัยว่ามาตรฐานประสิทธิภาพในสัมภาษณ์ที่ห่างไกลโลกจริงมีความหมายหรือไม่ (แน่นอนว่าอาจต่างกันตามบทบาทงาน) ฉันเห็นด้วยกับผู้เขียนตรงที่วิธีที่มีประสิทธิภาพที่สุดอาจไม่สะท้อนความสามารถในการทำงานจริง และนี่ก็เป็นบริบทหนึ่งของคำวิจารณ์ Leetcode ด้วย แม้เป็นปัญหาเดียวกัน แต่ถ้ามองจากมุมว่า "คุณปรับตัวกับ requirement ใหม่ได้ยืดหยุ่นแค่ไหน" ก็อาจวัดได้เป็นกลางกว่า
Constraint solver เหรอ? ฟังดูเป็นไอเดียที่ดีและฉันก็เคยได้ยิน แต่ในห้องสัมภาษณ์ความจริงคือเขาแค่อยากให้คุณลองเขียนมันเองด้วย Python เพื่อดู flow ความคิดมากกว่า (ฉันรู้สึกว่าแทบเป็นไปไม่ได้เลยที่จะโน้มน้าวให้เขายอมรับการใช้ constraint solver ในการสัมภาษณ์)
- อยากรู้ว่าคุณเคยพูดเรื่องนี้กับผู้สัมภาษณ์จริง ๆ หรือแค่คาดเดาเอาเอง
- import z3
ถ้าแก้ด้วย DP(ไดนามิกโปรแกรมมิง) ก่อน แล้วพูดต่อว่า "เดี๋ยวผมจะลองทำด้วย constraint solver ด้วย" แบบนี้รับเข้าทำงานได้เลย
- +1
จุดแข็งที่แท้จริงของ constraint solver คือการรองรับ "ข้อกำหนดใหม่" ได้ง่ายแค่ไหน ตอนที่ฉันทำ data center optimization ที่ Google ฉันได้สัมผัสประโยชน์ของ solver แบบทั่วไปพวกนี้อย่างมากในแง่ความยืดหยุ่นต่อการเปลี่ยน requirement