CODESTAR Scale


หลายคนสงสัยว่าต้องเก่งขนาดไหนถึงจะหางานทำได้ ควรรู้เรื่องอะไร หรือ เน้นเรื่องไหนเป็นพิเศษ และถ้าอยากไปทำงานองค์กรชั้นนำของโลก ต้องเตรียมตัวยังไง ลองอ่านบทความนี้ดูครับ ถ้ายาวเกินไปก็จำง่ายๆเลยครับว่า เพียงแค่เขียน Code พื้นฐานเป็นก็หางานทำได้แล้วครับ
บทความนี้จะอธิบายสิ่งที่ผมขอตั้งชื่อว่า CODESTAR Scale ซึ่งเป็นวิธีการวัดระดับความสามารถในการเขียนโค้ด เหมือนกับการเอาเครื่องวัดไฟมาตรวจดูว่ามีกระแสไฟฟ้ามากขนาดไหน หรือ มีความสามารถระดับไหนนั่นเอง ปัญหาทางคอมพิวเตอร์สามารถแบ่งออกเป็น 5 ระดับตามความยากง่าย ซึ่งปัญหาเหล่านี้สามารถพบเห็นได้ทั่วไปในการสัมภาษณ์งาน ตั้งแต่บริษัท Top 5 ใหญ่ที่สุดในโลก อย่าง Apple, Google, Microsoft, Facebook, Amazon จนถึงบริษัทชั้นนำของเมืองไทย

ระดับ 1

เป็นปัญหาสำหรับฝึกหัดเขียนโปรแกรม วิธีคิดตรงมาตรงไป เช่น การหาค่าที่น้อยที่สุดใน Array หรือหาว่าใน Array ข้อมูลเรียงกันแล้วหรือยัง ถ้าสามารถตอบคำถามเหล่านี้ได้ สามารถหางานดีๆ ในบริษัทชั้นนำของไทยได้ เงินเดือนที่ได้ไม่ต่ำกว่า 30,000 บาทต่อเดือน หรือถ้าทำงานในต่างประเทศประมาณ $50,000 ต่อปีขึ้นไป แต่ถ้าทำไม่ได้ก็ไม่ต้องกังวลอะไรมากมาย เพราะหลายคนทำไม่ได้แต่เงินเดือนมากกว่านี้ก็มี ที่น่าแปลกคือหลายคนที่ไม่ผ่าน ระดับพื้นฐานการเขียน Program แต่ไปทำงานที่สูงขึ้น เช่น Artificial Intelligence, Machine Learning หรือ Big Data มันก็เหมือนกับคนที่ยังคูณเลขไม่เป็นแต่ข้ามไปหา ∫ อินทิกรัล เลย

ตัวอย่างปัญหา

1.1 มีเลขจำนวนเต็มอยู่ประมาณ 1,000 ตัว ให้หาว่ามีตัวเลข 2 ตัว ที่สามารถรวมกันได้ค่าที่กำหนดหรือไม่ เช่น มีเลข [1, 5, 8, 4, 7] มี 2 ตัวที่รวมกันได้ 10 หรือไม่? คำตอบคือ ไม่มี
1.2 มีหุ่นยนต์เดินได้ 4 ทิศทาง คือ ทิศเหนือ ทิศใต้ ทิศตะวันออก และ ทิศตะวันตก ใช้สัญลักษณ์แทน N,S,E,W ตามลำดับ การเดินแต่ละครั้งเดินได้ 1 เมตร จากเส้นทางที่กำหนดให้หาระยะห่างจากจุดเริ่มต้น ในตัวอย่างข้างล่างนี้เส้นทางคือ NNEES ได้ระยะทาง 2.23 เมตร

ระดับ 2

เป็นปัญหาที่ต้องใช้โครงสร้างข้อมูล เช่น การใช้ Binary Search Tree เพื่อให้ได้ผลลัพธ์อย่างรวดเร็ว, ปัญหาเกี่ยวกับ String หรือ Array อาจจะมี Greedy อย่างง่าย ถ้าแก้ปัญหาระดับนี้ได้ เงินเดือนที่ได้ไม่ต่ำกว่า 50,000 บาทต่อเดือนขึ้นไป หรือในต่างประเทศประมาณ $60,000 - $70,000 ต่อปี ที่สำคัญคือ 90% ของ Programmer ในบริษัทชั้นนำของไทยไม่ผ่านระดับนี้ และ 90% ของคนจบปริญญาโทด้าน Computer หรือ IT ไม่ผ่านระดับนี้

ตัวอย่างปัญหา

2.1 มีเลขจำนวนเต็มอยู่ประมาณ 1,000,000 ตัว ให้หาว่ามีตัวเลข 2 ตัว ที่สามารถรวมกันได้ค่าที่กำหนดหรือไม่ เช่น มีเลข [1, 5, 8, 4, 7] มี 2 ตัวที่รวมกันได้ 12 หรือไม่? คำตอบคือ มี เช่น 5 กับ 7
2.2 มีข้อมูลอยู่สองรายการ แต่ละรายการมีนับล้านตัว ให้เขียนโค้ดเพื่อหาว่ามีตัวไหนที่อยู่ทั้งสองแห่ง เช่น [1, 2, 4, 3, 7, 5] และ [2, 5, 8, 6] ได้ผลลัพธ์คือ [2,5]
2.3 ให้เขียน Code อ่านข้อมูลตารางจตุรัสจาก File มีข้อมูลจำนวนแถวและหลัก ตามด้วยข้อมูลแต่ละตัว จากนั้นหมุนไป 90 องศาตามเข็มนาฬิกา เช่น 
3
1 2 3
4 5 6
7 8 9

ได้ผลลัพธ์คือ 
7 4 1
8 5 2
9 6 3

ระดับ 3

เป็นปัญหา Algorithm มาตรฐานเช่น Greedy, Dynamic Programming, Divide and Conquer, Graph, BFS, Backtracking พบในการสัมภาษณ์งานทั่วไปใน Silicon Valley อาจจะมีในไทยบ้างเหมือนกัน เช่น พวกบริษัทต่างชาติที่มีมาตรฐานระดับสูง เงินเดือนที่ได้ไม่ต่ำกว่า 70,000 - 100,000 บาทต่อเดือน หรือถ้าทำงานในต่างประเทศก็ไม่ต่ำกว่า $70,000 - $100,000 ต่อปี ถ้าศึกษา Algorithm ตามหนังสือหรือ Web ทั่วไป ไม่นานก็สามารถผ่านระดับนี้ได้ เพราะปัญหาทาง Computer สามารถแปลงไปหากันได้

ตัวอย่างปัญหา

3.1 มีเลขจำนวนเต็มอยู่ประมาณ 100 ตัว ให้หาว่ามี Subset ที่รวมกันได้ค่าที่กำหนดหรือไม่ เช่น มีเลข [1, 5, 8, 4, 7] มี Subset ที่รวมกันได้ 10 หรือไม่? คำตอบคือ มี เช่น [1, 5, 4]
3.2 ให้เขียน Code เพื่อตัดแบ่งข้อมูลออกเป็น Palindrome หรือตัวที่อ่านจากซ้ายไปขวาได้เหมือนกับ อ่านจากขวามาซ้าย โดยต้องแบ่งให้น้อยครั้งที่สุด เช่น 
ATAA            // แบ่ง 1 ครั้ง เป็น ATA | A 
ATGCG           // แบ่ง 2 ครั้ง เป็น A | T | GCG
ATGTA           // แบ่ง 0 ครั้งเพราะเป็น Palindrome อยู่แล้ว

มหาวิทยาลัยในเมืองไทย มีสอนถึงระดับ 3 แน่นอน แต่คนทั่วไปเรียนแล้วจำอะไรไม่ได้ ลองถามง่ายๆว่า Binary Search คืออะไร น้อยคนที่จะตอบได้ ยิ่งถามว่ามันต่างจาก Binary Search Tree ยังไง ยิ่งไปกันใหญ่ รู้ไม่เกิน 10% ของคนที่เรียนจบปริญญาตรีสายตรง

ระดับ 4

เป็นปัญหาที่ใช้ในการทดสอบเข้าทำงานของบริษัทชั้นนำ เช่น Apple, Google, Microsoft, Facebook, Amazon ปัญหาระดับนี้ต้อง Devise หรือ คิดค้น Algorithm ขึ้นมาเอง และอาจจะต้องใช้การพิสูจน์ทางคณิตศาสตร์ หรือ Theory of Computation เข้ามาเกี่ยวข้องด้วย ถ้าผ่านระดับนี้ได้ สามารถส่งใบสมัครไปบริษัทชั้นนำเหล่านี้ได้ ไม่ว่าคุณจะถนัดภาษาอะไรก็ตาม คนระดับนี้เป็นที่ต้องการตัวของบริษัทระดับโลกตลอดเวลา รายได้ไม่ต่ำกว่า $100,000 ต่อปี

ตัวอย่างปัญหา

4.1 ในสนามกีฬาแบบจตุรัสแห่งหนึ่ง มีหลอดไฟจำนวน N * N ดวง เมื่อกดปุ่มเปิดปิดไฟดวงไหน หลอดไฟในแถวเดียวกันทั้งแนวตั้งและแนวนอน จะเปลี่ยนสถานะไปด้วย ให้เขียน Code หาว่าถ้าไฟทุกดวงเปิดอยู่ ต้องกดปุ่มอย่างน้อยที่สุดกี่ครั้งเพื่อปิดไฟทั้งหมด
4.2 ต้นไม้ถูกกำหนดให้มีคะแนนโดยใช้ผลรวมความยาวจากรากถึงใบ ตัวอย่างต้นไม้ที่มี 4 Nodes สามารถสร้างต้นไม้ได้ 4 แบบ มีคะแนน 3, 4, 3, 3 ตามลำดับ ให้เขียน Code รับจำนวน Node เข้ามาหาคะแนนที่มากที่สุด

ระดับ 5

ปัญหาระดับนี้จะไม่มีคำตอบถูกหรือผิด มีแต่คำตอบที่ดี คำตอบที่ใช้ได้ หรือยอมรับได้ ตัวอย่างเช่น
5.1 Google Maps จะแสดงได้ด้วยว่ารถติดบนถนนเส้นไหน ระบบนี้ไม่ได้แสดงข้อมูลที่แท้จริง ไม่ได้คำนวณจากปริมาณรถที่แท้จริง แต่แสดงข้อมูลที่ถูกต้องระดับหนึ่ง โดยคำนวณมาจากข้อมูลอื่นแทน
5.2 ตัวอย่างอีกปัญหานึงคือ ใส่ Latitude และ Longitude เข้ามา แล้วหาว่า อยู่ในตำบลอะไร อำเภออะไร จังหวัดอะไร