คำถามสัมภาษณ์ DSA

คุณแก้โจทย์มาแล้วหลายร้อยข้อแต่ก็ยังรู้สึกไม่พร้อม ซึ่งมักหมายความว่าคุณฝึกฝนผิดครึ่งหนึ่งของแบบฝึกหัด หัวข้อนี้จะระบุว่าอะไรคือสิ่งที่ถูกให้คะแนนจริง ๆ เพื่อให้การฝึกฝนตรงจุด

การสัมภาษณ์สดเรื่องโครงสร้างข้อมูลและอัลกอริทึมวัดสี่อย่างพร้อมกัน คือคุณจำได้หรือไม่ว่าโจทย์เป็นรูปแบบไหน คุณบอกแนวทางได้ก่อนเขียนโค้ดหรือไม่ การเขียนโค้ดถูกต้องตรงกรณีขอบเขตหรือไม่ และคุณอธิบายความซับซ้อนออกมาดัง ๆ ได้หรือไม่ ผู้สมัครมักทุ่มเทให้ข้อสามและละเลยข้อสอง แล้วก็ถูกหักคะแนนเพราะคำตอบที่ถูกต้องมาโดยไม่มีคำอธิบาย

ขั้นตอนการจำแนกรูปแบบนี้เองคือเหตุผลที่การฝึกรูปแบบเอาชนะการฝึกปริมาณ โจทย์แทบไม่เคยใหม่จริง ๆ มันคือการผสมผสานรูปแบบเดิม ทันทีที่คุณพูดได้ภายในนาทีแรกว่า นี่คือสไลดิงวินโดว์บนแผนที่ความถี่ ที่เหลือก็แค่การลงมือทำ คลังคำถามที่เกี่ยวข้องแยกตามภาษาและตำแหน่งงานอยู่ที่ ศูนย์รวมคำถามสัมภาษณ์

รูปแบบเหล่านี้คือส่วนใหญ่ของสิ่งที่ถูกถาม ให้ฝึกจับสัญญาณที่ชี้ไปยังแต่ละรูปแบบ

• ทูพอยน์เตอร์ อินพุตที่เรียงลำดับแล้ว ผลรวมคู่ การแบ่งพาร์ทิชันในที่เดิม การตรวจพาลินโดรม
• สไลดิงวินโดว์ ซับอาร์เรย์ต่อเนื่องที่ยาวที่สุดหรือสั้นที่สุดภายใต้เงื่อนไข
• การนับด้วยแฮชแมป แอนาแกรม ค่าซ้ำ การเปรียบเทียบความถี่ องค์ประกอบที่ไม่ซ้ำตัวแรก
• การค้นหาแบบไบนารี อาร์เรย์ที่เรียงลำดับแล้ว และการค้นหาบนพื้นที่คำตอบเมื่ออาร์เรย์ไม่ได้เรียงลำดับ
• การค้นหาแบบกว้างและแบบลึก ต้นไม้ กริด องค์ประกอบที่เชื่อมต่อกัน เส้นทางสั้นที่สุดแบบไม่ถ่วงน้ำหนัก
• ฮีปและคิวลำดับความสำคัญ โจทย์ top-k การรวมสตรีมที่เรียงลำดับแล้ว การหาค่ามัธยฐานต่อเนื่อง
• อินเทอร์วัล การรวม การแทรก และการตรวจจับการซ้อนทับหลังเรียงลำดับตามจุดเริ่มต้น
• ไดนามิกโปรแกรมมิง ปัญหาย่อยที่ซ้อนทับกัน เช่น การขึ้นบันได การทอนเหรียญ ระยะแก้ไข ลำดับย่อย
• แบ็กแทรกกิง การเรียงสับเปลี่ยน การจัดหมู่ เซตย่อย ปริศนาที่มีเงื่อนไขบังคับ
• อัลกอริทึมกราฟ การเรียงลำดับเชิงทอพอโลยี ยูเนียนไฟนด์ เส้นทางสั้นที่สุดแบบถ่วงน้ำหนัก

ตัวอย่างโจทย์ที่พบบ่อย เขียนในแบบที่ผู้สัมภาษณ์มักใช้จริง

• หาตัวเลขสองตัวในอาร์เรย์ที่รวมกันได้เท่ากับค่าเป้าหมาย แล้วทำโดยไม่ใช้พื้นที่เพิ่ม
• คืนค่าความยาวของซับสตริงที่ยาวที่สุดที่ไม่มีตัวอักษรซ้ำ
• กำหนดอาร์เรย์ที่เรียงลำดับแล้วถูกหมุน ให้หาค่าเป้าหมายในเวลาลอการิทึม
• รวมอินเทอร์วัลที่ซ้อนทับกันและอธิบายว่าทำไมการเรียงลำดับถึงคุ้มค่า
• สลับต้นไม้ไบนารี แล้วหาความลึกสูงสุดของมัน
• ตรวจสอบต้นไม้ค้นหาแบบไบนารี และบอกว่าการตรวจแบบง่าย ๆ พลาดอะไรไป
• นับจำนวนเกาะในกริด แล้วบอกว่าจะจัดการกริดที่ใหญ่เกินหน่วยความจำอย่างไร
• หาองค์ประกอบที่พบบ่อยที่สุด k ตัว และอธิบายเหตุผลของโครงสร้างข้อมูลที่เลือก
• คำนวณจำนวนเหรียญขั้นต่ำสำหรับจำนวนเงินหนึ่ง และระบุสูตรความสัมพันธ์เวียนเกิด
• ตรวจจับวงจรในลิงก์ลิสต์ แล้วคืนค่าโหนดที่มันเริ่มต้น
• ทำซีเรียลไลซ์และดีซีเรียลไลซ์ต้นไม้ไบนารี
• กำหนดเงื่อนไขวิชาบังคับก่อนของคอร์ส ให้ตัดสินว่าตารางเรียนเป็นไปได้หรือไม่

บัณฑิตจบใหม่ที่สัมภาษณ์ตำแหน่งแบ็กเอนด์ได้รับโจทย์ซับสตริงและเริ่มพิมพ์โค้ดทันที โค้ดเกือบถูกต้อง แต่ผู้สัมภาษณ์ใช้เวลาทั้งรอบถามว่ามันทำอะไร และคะแนนสะท้อนความเงียบมากกว่าตัวบั๊ก ผู้สมัครที่ใช้เวลาสี่สิบวินาทีพูดว่า วินโดว์บนแผนที่ตัวอักษร ขยายทางขวา หดทางซ้ายเมื่อเจอค่าซ้ำ ติดตามค่าสูงสุด ได้ผ่านส่วนที่แก้ไขยากที่สุดไปแล้ว

การแก้โจทย์แบบเงียบ ๆ สร้างปฏิกิริยาที่ผิด การสัมภาษณ์สดต้องการทั้งการเล่าและการเขียนโค้ดพร้อมกัน ซึ่งเป็นทักษะที่แยกจากการทำแต่ละอย่างเพียงลำพัง

เปลี่ยนวิธีฝึก ไม่ใช่ชุดโจทย์ ก่อนเขียนอะไรก็ตาม ให้พูดออกมาดัง ๆ ถึงรูปแบบ แนวทาง และความซับซ้อนที่คาดไว้ เขียนโค้ดไปพร้อมกับเล่าต่อเนื่อง เมื่อเสร็จแล้วให้บอกความซับซ้อนอีกครั้งและระบุกรณีขอบเขตหนึ่งที่คุณจัดการแล้วกับอีกหนึ่งที่คุณจะถาม การทำแบบนี้กับสิบโจทย์สร้างความสามารถในการสัมภาษณ์ได้มากกว่าการแก้ห้าสิบโจทย์แบบเงียบ ๆ

เซสชันสัมภาษณ์จำลองให้คำถามต่อเนื่องซึ่งเป็นส่วนที่ฝึกคนเดียวไม่ได้ และให้บันทึกเสียงการเล่าของคุณเองไว้ทบทวน ข้อจำกัดที่ตรงไปตรงมาข้อหนึ่งใช้ได้เสมอ คือแบบทดสอบเขียนโค้ดในเบราว์เซอร์ที่มีผู้คุมสอบไม่ใช่บทสนทนา และไม่ควรมีผู้ช่วยสดเข้าไปเกี่ยวข้อง ศูนย์รวมประเภทการสัมภาษณ์อธิบายว่ารูปแบบการเขียนโค้ดแบบไหนเป็นแบบสดและแบบไหนเป็นแบบอัตโนมัติ