โครงสร้างข้อมูลและอัลกอริทึมที่ผมใช้จริงในการทำงาน

 (blog.pragmaticengineer.com)
20 คะแนน โดย xguru 2020-07-17 | 3 ความคิดเห็น | แชร์ทาง WhatsApp

มักมีคนพูดกันว่าโจทย์อัลกอริทึมที่ชอบถามกันในสัมภาษณ์งานนั้นไม่ได้ถูกใช้จริงในการทำงาน

ผู้เขียนจึงได้รวบรวมสิ่งที่ตัวเองใช้บ่อยจริงระหว่างทำงานที่ Skype/Uber เป็นต้น พร้อมตัวอย่าง และแนะนำสิ่งที่ควรอ่านเป็นพื้นฐาน

กราฟและการท่องกราฟ : Skype & Uber

กราฟถ่วงน้ำหนักและเส้นทางที่สั้นที่สุด : SkyScanner

การเรียงลำดับ : Skype

ตารางแฮชและการแฮช : ทุกที่

สแตกและคิว : บางครั้ง

การเข้ารหัสลับ (Crypto), ทฤษฎีความน่าจะเป็นและการประมาณคาดเดา, Hexagonal Grid และ hierarchical index : Uber

  • เกี่ยวกับอัลกอริทึมและโครงสร้างข้อมูลในการสัมภาษณ์

การรู้จักอัลกอริทึมยอดนิยมหรือโครงสร้างข้อมูลแปลก ๆ ไม่ใช่สิ่งสำคัญ

คุณควรรู้ว่าอัลกอริทึมคืออะไร และควรสามารถคิดอัลกอริทึมง่าย ๆ อย่างเช่นอัลกอริทึมแบบ Greedy ได้

ควรรู้จักโครงสร้างข้อมูลพื้นฐานอย่าง hash table, queue & stack แต่ไม่จำเป็นต้องท่องจำอัลกอริทึมเฉพาะทางอย่าง Dijkstra หรือ A*

งานส่วนใหญ่ที่ผมทำเกี่ยวกับอัลกอริทึมที่ซับซ้อนกว่าการเรียงลำดับ ก็มีแค่ค้นคว้าแล้วพยายามทำความเข้าใจเท่านั้น

โครงสร้างข้อมูลเฉพาะทางอย่าง Red-Black หรือ AVL tree ก็เช่นกัน

ในความเป็นจริงผมไม่เคยต้องใช้โครงสร้างข้อมูลพวกนี้เลย และถึงจำเป็นจริงก็คงกลับไปค้นหาใหม่อยู่ดี

ในซิลิคอนแวลลีย์ การถามคำถามเรื่อง dynamic programming หรือโครงสร้างข้อมูลเฉพาะทางกำลังกลายเป็นเรื่องปกติมากขึ้นเรื่อย ๆ

คำถามแบบนี้อาจช่วยคัดเลือกวิศวกรที่ยอดเยี่ยมได้ แต่ก็ทำให้พลาดคนที่ทำงานได้ดีมากในงานที่จริง ๆ แล้วไม่ต้องใช้ความรู้อัลกอริทึมขั้นสูง

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

โครงสร้างข้อมูลและอัลกอริทึมเป็นเพียงชุดเครื่องมือเท่านั้น

เป็นเครื่องมือที่คุณควรใช้ได้อย่างมั่นใจเมื่อพัฒนาซอฟต์แวร์

ถ้าคุณรู้จักเครื่องมือเหล่านี้ดี คุณก็จะคุ้นเคยกับการอ่านโค้ดที่ใช้สิ่งเหล่านี้มากขึ้น

และยังจะมีความมั่นใจมากขึ้นในการลงมือทำโซลูชันเพื่อแก้ปัญหาที่ยาก

หากต้องการเรียนรู้พื้นฐาน ผมแนะนำสิ่งต่อไปนี้ (ลิงก์อยู่ในคอมเมนต์)

  • Data Structures Overview ของ GeekforGeeks (ชุดบทความออนไลน์)

  • DataStructure Collection ของ HackerRank (เรียนรู้ผ่านการแก้โจทย์)

  • Grokking Algorithms : ทำความเข้าใจแนวคิดอัลกอริทึมด้วยภาพประกอบ (มีฉบับแปล)

  • The Algorithm Design Manual และ Algorithms: Fourth Edition ค่อนข้างแห้งเกินไป และไม่ค่อยเหมาะกับการใช้งานจริงทุกวัน

บทความที่เกี่ยวข้อง

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

 
xguru 2020-07-17
  • Data Structures Overview ของ GeekforGeeks

https://geeksforgeeks.org/overview-of-data-structures-set-1-linear-dat…

  • DataStructure Collection ของ HackerRank

https://www.hackerrank.com/domains/data-structures

  • Grokking Algorithms : อัลกอริทึมที่ช่วยให้เข้าใจแนวคิดผ่านภาพประกอบ

อังกฤษ : https://www.amazon.com/gp/product/1617292230/?tag=amzneu-20

ฉบับภาษาเกาหลี (Hanbit Media): https://www.hanbit.co.kr/store/books/look.php?p_code=B5896248244

The Algorithm Design Manual https://www.amazon.com/gp/product/1848000693?tag=amzneu-20

Algorithms : 4th Edition https://www.amazon.com/gp/product/032157351X/?tag=amzneu-20
 
xguru 2020-07-17

เกร็ดเล่าที่ Max Howell ผู้พัฒนา Homebrew ซึ่งถูกกล่าวถึงช่วงต้นบทความ สอบตกสัมภาษณ์กับ Google เพราะเขียนการกลับด้านไบนารีทรีบนกระดานไม่ได้ เป็นเรื่องที่โด่งดังมาก

ทั้งที่ในบรรดาวิศวกรของ Google จริง ๆ แล้ว 90% ใช้ Homebrew กันอยู่ แต่กลับเป็นความย้อนแย้งที่ตัวผู้พัฒนาเองสอบไม่ผ่าน..
 
lazinism 2020-07-19

90% นั้นเป็นตัวเลขที่นักพัฒนา Homebrew พูดขึ้นมาเอง แล้วเหมือนว่าในทวีตนั้นก็มีนักพัฒนาของ Google มาตอบว่าไม่มีทางถึง 90% แน่นอน..

ยังไงที่ Google ก็ใช้ Ubuntu สำหรับเดสก์ท็อป แล้วแล็ปท็อปก็เป็น shell machine อยู่แล้ว เลยไม่ได้มีโอกาสต้องใช้มันเป็นพิเศษเท่าไร