let's code: แก้โจทย์ Interviewstreet

Interviewstreet เป็นเว็บหางานสำหรับโปรแกรมเมอร์แนวใหม่ ที่ตัดสินคัดเลือกคนขั้นต้นด้วยการจัดให้เขียนโปรแกรมแข่งกันซะเลย (แล้วค่อยไปยื่น resume + สัมภาษณ์ทีหลัง) เพียงแค่ทำโจทย์ผ่าน 7 ข้อ ก็มีสิทธิยื่นใบสมัครกับบริษัทเช่น Facebook, Microsoft, Amazon.com, Dropbox ฯลฯ เรียกได้ว่า นอกจากจะได้ฝึกสมองแก้โจทย์แล้ว ยังมีโอกาสลุ้นไปทำงานกับบริษัทเหล่านี้อีกด้วย

แม้ว่าตอนนี้เว็บจะมีโจทย์ให้ไปเล่นไม่มากเท่าไหร่ แต่ความยากนั้นรับรองว่าไม่ธรรมดาแน่นอน (โจทย์ค่อนข้างง่ายแต่ test case โหดมาก) นอกจากที่จะต้องใช้ algorithm ที่มีประสิทธิภาพควบคู่ไปกับ data structure ที่เหมาะสมแล้ว ยังต้องแม่นในการพิสูจน์ทางคณิตศาสตร์เพื่อนำมาลดขนาดของ big-O ด้วยครับ

ภาษาที่ใช้ได้
C/C++, C#, Java,
Haskell, Clojure, Scala,
PHP, Ruby, Python, Perl

ปล. ไม่ต้องกังวลจนเกินไปว่า เขียนภาษาในกลุ่ม script แล้วจะเสียเปรียบกลุ่ม native/managed นะครับ เพราะทางเว็บได้ชดเชยเวลาให้ตามสัดส่วนครับ

รูปแบบการตรวจคำตอบ
ส่ง source code ให้ server ประมวลผลกับ test case

ตัวอย่างโจทย์

• Meeting Point: หมู่บ้านแห่งหนึ่ง บ้านแต่ละหลังจะสามารถสร้างอยู่บนจุดตัดของกริดได้เท่านั้น จากบ้านหลังหนึ่งถ้าเดินทางตรงๆ ไปจุดถัดไปในทิศทั้ง 4 จะใช้เวลา 1 หน่วย แต่ถ้าเดินทางทะแยงในทิศทั้ง 4 ก็จะใช้เวลา 1 หน่วยเช่นกัน ถ้าให้พิกัดของบ้านทุกหลังในหมู่บ้านแห่งหนึ่งมา จงหาบ้านหลังที่ถ้าทุกคนในหมู่บ้านเดินทางมาประชุมที่บ้านหลังนั้น เวลารวมของการเดินทางของทุกคนจะมีค่าน้อยที่สุด
• String Reduction: ในระบบภาษาระบบหนึ่ง มีตัวอักษรแค่ 3 ตัวคือ abc เท่านั้น ถ้าต้องการย่อคำในภาษานั้น โดยกฎการย่อคือ จะย่อตัวอักษรไม่เหมือนกัน 2 ตัวที่อยู่ติดกันให้กลายเป็นตัวอักษรตัวที่ 3 ถ้าให้คำๆ หนึ่งมา ให้บอกว่าคำนั้นสามารถย่อให้สั้นที่สุดเหลือกี่ตัวอักษร
• Changing Bit: ให้บิตของตัวเลขขนาดใหญ่มาก (ใหญ่ได้ถึง 100,000 บิต) มา 2 ชุด ถ้าให้การคิวรี่อีกจำนวนหนึ่งมา ซึ่งสามารถ 1. ทำการเปลี่ยนข้อมูลบิตใดบิตหนึ่งในเลขทั้งสอง และ 2. นำเลขทั้งสองมาบวกกัน แล้วพิมพ์ค่าของบิตในตำแหน่งที่ร้องขอ จงสร้างระบบสำหรับตัวเลขและการคิวรีนี้