สารบัญ[ซ่อน][แสดง]
- 1. คุณกำหนด Array อย่างไร?
- 2. ไดนามิกอาร์เรย์: มันคืออะไร? อะไรทำให้พวกเขาแตกต่างจาก Basic Arrays?
- 3. อาร์เรย์และพจนานุกรมแตกต่างกันอย่างไร
- 4. ระบุข้อดีและข้อเสียของอาร์เรย์
- 5. “Sparse Array” หมายถึงอะไร?
- 6. คุณจะเลือกรายการที่เชื่อมโยงผ่านอาร์เรย์เมื่อใด
- 7. อะไรที่ทำให้อาร์เรย์ที่จัดทำดัชนีแตกต่างจากอาร์เรย์ที่เชื่อมโยงกัน
- 8. Heap มีข้อดีอะไรมากกว่าการจัดเรียงอาร์เรย์?
- 9. เราสามารถกำหนดขนาดของอาร์เรย์ให้เป็นค่าลบได้หรือไม่?
- 10. คุณจะหาจำนวนเต็มที่หายไปในอาร์เรย์ 1 ถึง 100 องค์ประกอบได้อย่างไร
- 11. คุณจะพบดัชนีขององค์ประกอบในอาร์เรย์ได้อย่างไร?
- 12. คุณจะกำจัดองค์ประกอบเฉพาะออกจากอาร์เรย์ได้อย่างไร?
- 13. จะตรวจสอบความเท่าเทียมกันของสองอาร์เรย์ได้อย่างไร?
- 14. เมื่อเราพูดถึงอาร์เรย์ คุณหมายถึงอะไรโดยวลี "ไดเมนชัน" และ "ตัวห้อย"?
- คำถามสัมภาษณ์การเข้ารหัส
- 15. หาคู่ในอาร์เรย์ที่มีค่า sum . ที่ระบุ
- 16. การเรียงลำดับอาร์เรย์ไบนารีด้วยเวลาเชิงเส้น
- 17. ค้นหาผลิตภัณฑ์สองอินต์ที่ใหญ่ที่สุดในอาร์เรย์
- 18. วิธีเปลี่ยนศูนย์ของอาร์เรย์ทั้งหมดไปที่จุดสิ้นสุด
- 19. วิธีการเรียงลำดับอาร์เรย์ที่มีสองรายการที่สลับในการดำเนินการเดียว
- 20. วิธีรวมอาร์เรย์ที่จัดเรียงไว้สองชุดเข้าด้วยกัน
- 21. จะเรียงลำดับอาร์เรย์ของรายการใหม่โดยสลับตำแหน่งสูงและต่ำได้อย่างไร?
- 22. วิธีการแทนที่แต่ละองค์ประกอบของอาร์เรย์โดยไม่ต้องใช้ตัวดำเนินการหารด้วยผลคูณของแต่ละองค์ประกอบในอาร์เรย์?
- 23. ค้นหาองค์ประกอบที่แปลกที่สุดในอาร์เรย์ในเวลาลอการิทึม
- 24. จะหาองค์ประกอบที่ใหญ่กว่าที่ตามมาสำหรับแต่ละองค์ประกอบในอาร์เรย์แบบวงกลมได้อย่างไร?
- 25. ค้นหาจำนวนผกผันของอาร์เรย์?
- 26. ปัญหาการดักจับน้ำฝนคืออะไร?
- สรุป
การสัมภาษณ์การเข้ารหัสประกอบด้วยชุดคำถาม DSA คุณควรมีทักษะด้านอาร์เรย์หากคุณพร้อมสำหรับการสัมภาษณ์ด้านเทคนิคที่จะเกิดขึ้นกับ FAANG หรือธุรกิจเทคโนโลยีระดับ Tier-1 อื่นๆ
ในการสัมภาษณ์เขียนโค้ดส่วนใหญ่จะอยู่อันดับสองของ Strings อาร์เรย์คือการจัดกลุ่มขององค์ประกอบข้อมูลที่เกี่ยวข้องซึ่งเก็บไว้ใกล้กันในหน่วยความจำ
เนื่องจากมีการเชื่อมต่อกับภาษาการเขียนโปรแกรมทั้งหมด เช่น C, C++, Java, Python, Perl และ Ruby พวกเขาจึงอยู่ทุกที่ อ่านต่อเพื่อฝึกเขียนโค้ดที่ท้าทายและคำถามสัมภาษณ์และคำตอบตามอาร์เรย์
Python จะใช้ในโพสต์นี้เพื่อจัดการกับปัญหาการเขียนโค้ด เพราะใช้งานง่าย เข้าใจ และคนส่วนใหญ่ต้องคุ้นเคย
เอาล่ะ.
1. คุณกำหนด Array อย่างไร?
- กลุ่มของชนิดข้อมูลที่เกี่ยวข้องคืออาร์เรย์
- อาร์เรย์ได้รับการแก้ไขเสมอ
- ตัวแปรชนิดเดียวกันถูกเก็บไว้ในหลาย ๆ ที่โดยวัตถุอาร์เรย์
- ทั้งประเภทดั้งเดิมและการอ้างอิงอ็อบเจ็กต์นั้นเข้ากันได้
2. ไดนามิกอาร์เรย์: มันคืออะไร? อะไรทำให้พวกเขาแตกต่างจาก Basic Arrays?
การปรับขนาดอัตโนมัติที่อาร์เรย์ไดนามิก (เรียกอีกอย่างว่าอาร์เรย์ที่ขยายได้ อาร์เรย์ที่ปรับขนาดได้ อาร์เรย์ที่เปลี่ยนแปลงได้ หรือ ArrayLists ใน Java) ถือเป็นข้อได้เปรียบที่สำคัญ
คุณต้องทราบจำนวนองค์ประกอบที่อาร์เรย์ของคุณจะจัดเก็บไว้ล่วงหน้าเสมอเนื่องจากอาร์เรย์มีขนาดคงที่ ในทางกลับกัน อาร์เรย์ไดนามิกจะเติบโตขึ้นเมื่อคุณเพิ่มสมาชิกเข้าไป ดังนั้นคุณไม่จำเป็นต้องรู้ขนาดที่แน่นอนล่วงหน้า
3. อาร์เรย์และพจนานุกรมแตกต่างกันอย่างไร
นี่คือคำถามสัมภาษณ์ตามพื้นฐานที่มักถูกถามเป็นประจำ ต่อไปนี้เป็นข้อแตกต่างที่สำคัญระหว่างอาร์เรย์และพจนานุกรม:
- อาร์เรย์คือรายการที่เรียงลำดับของรายการที่คล้ายคลึงกัน ในทางกลับกัน พจนานุกรมมีคู่คีย์-ค่า
- ขนาดอาร์เรย์สามารถเปลี่ยนแปลงได้แบบไดนามิก แนวคิดแบบไดนามิกดังกล่าวไม่มีอยู่ในพจนานุกรม
- ก่อนใช้อาร์เรย์ ต้องระบุขนาดของอาร์เรย์ ไม่จำเป็นต้องปรับแต่งขนาดพจนานุกรม
- ใช้คำสั่ง Redim หากคุณต้องการขยายขนาดของอาร์เรย์ ในพจนานุกรม คุณสามารถเพิ่มองค์ประกอบโดยไม่ต้องประกาศ
4. ระบุข้อดีและข้อเสียของอาร์เรย์
ข้อดี:
- อาร์เรย์สามารถจัดเรียงองค์ประกอบหลายอย่างพร้อมกันได้
- อื่นๆ โครงสร้างข้อมูลเช่น สแต็ค คิว รายการที่เชื่อมโยง ต้นไม้ กราฟ ฯลฯ สามารถนำมาใช้ในอาร์เรย์ได้
- ดัชนีสามารถใช้เพื่อเข้าถึงองค์ประกอบของอาร์เรย์
ข้อเสีย:
- ต้องประกาศขนาดของอาร์เรย์ล่วงหน้า ในขณะที่ประกาศอาร์เรย์ เราอาจไม่ทราบขนาดที่เราต้องการ
- โครงสร้างของอาร์เรย์เป็นแบบคงที่ หมายความว่าขนาดของอาร์เรย์จะคงที่เสมอ และการจัดสรรหน่วยความจำไม่สามารถเพิ่มหรือลดได้
5. “Sparse Array” หมายถึงอะไร?
อาร์เรย์แบบกระจายคืออาร์เรย์ข้อมูลที่มีรายการจำนวนมากโดยมีค่าเป็นศูนย์ ในทางตรงกันข้าม อาร์เรย์หนาแน่นประกอบด้วยรายการส่วนใหญ่ที่มีค่าไม่เป็นศูนย์ ดัชนีของอาร์เรย์กระจัดกระจาย ซึ่งแปลงตัวเลขเป็นวัตถุ อาจมีช่องว่าง เมื่อเทียบกับ HashMap พวกมันจะมีประสิทธิภาพหน่วยความจำมากกว่า
6. คุณจะเลือกรายการที่เชื่อมโยงผ่านอาร์เรย์เมื่อใด
เมื่อใช้รายการที่เชื่อมโยงแทนอาร์เรย์ ให้พิจารณา:
- คุณไม่จำเป็นต้องมีองค์ประกอบใด ๆ เพื่อเข้าถึงโดยสุ่ม
- ในกรณีที่จำเป็นต้องคาดการณ์ได้ชั่วคราว คุณต้องมีการแทรกและนำออกจากรายการตามเวลาคงที่
- ในการสร้างลำดับความสำคัญ คุณอาจต้องวางรายการไว้ตรงกลางของรายการ
- คุณไม่รู้ว่ารายการจะนานแค่ไหน หากขนาดอาร์เรย์เพิ่มขึ้น คุณต้องประกาศซ้ำและทำซ้ำหน่วยความจำ เช่นเดียวกับอาร์เรย์ทั่วไป
7. อะไรที่ทำให้อาร์เรย์ที่จัดทำดัชนีแตกต่างจากอาร์เรย์ที่เชื่อมโยงกัน
ความแตกต่างหลักระหว่างอาร์เรย์ที่เชื่อมโยงและที่จัดทำดัชนีแสดงอยู่ในตารางต่อไปนี้
- คู่คีย์-ค่าในรูปแบบข้อความหรือตัวเลขใช้เพื่อจัดเรียงอาร์เรย์ที่เชื่อมโยง คีย์ของอาร์เรย์ที่จัดทำดัชนีเป็นตัวเลขทั้งหมด และแต่ละคีย์เชื่อมต่อกับค่าที่แตกต่างกัน
- ในอาเรย์ที่เชื่อมโยง คีย์อาจเป็นสตริง อาร์เรย์ที่จัดทำดัชนีด้วยคีย์จำนวนเต็มเริ่มต้นที่ 0
- ตารางสองคอลัมน์เลียนแบบพฤติกรรมของอาเรย์ที่เชื่อมโยง คล้ายกับตารางคอลัมน์เดียวคืออาร์เรย์ที่ทำดัชนี
- แผนที่เป็นประเภทอาเรย์ที่เชื่อมโยง อาร์เรย์ดัชนีไม่ใช่แผนที่
8. Heap มีข้อดีอะไรมากกว่าการจัดเรียงอาร์เรย์?
ประสิทธิภาพด้านเวลาของการใช้ Heap over Sorted Arrays เป็นประโยชน์หลัก แม้ว่าการดำเนินการฮีปจะเร็วกว่า การจัดเรียงอาร์เรย์ต้องใช้เวลามาก ฮีปสามารถค้นพบองค์ประกอบที่เล็กที่สุดได้เร็วกว่าอาร์เรย์ที่สามารถจัดเรียงได้
คอลเลกชันของตัวเลขที่กำหนดสามารถจัดเรียงได้สองวิธีโดยใช้ Sorted Arrays ในทางกลับกัน สำหรับคอลเล็กชันตัวเลขที่กำหนด อาจมีฮีปที่เป็นไปได้มากกว่าหนึ่งฮีป
9. เราสามารถกำหนดขนาดของอาร์เรย์ให้เป็นค่าลบได้หรือไม่?
ไม่ เราไม่สามารถกำหนดจำนวนเต็มลบให้เป็นขนาดของอาร์เรย์ได้ จะไม่มีข้อผิดพลาดในการคอมไพล์ถ้าเราประกาศ อย่างไรก็ตาม ที่รันไทม์ เราจะพบกับ NegativeArraySizeException
10. คุณจะหาจำนวนเต็มที่หายไปในอาร์เรย์ 1 ถึง 100 องค์ประกอบได้อย่างไร
สามารถคำนวณผลรวมของอนุกรมได้โดยใช้ฟังก์ชันต่อไปนี้: n (n + 1) / 2
เฉพาะในกรณีที่อาร์เรย์ไม่มีข้อมูลซ้ำกันหรือมีจำนวนเต็มหายไปมากกว่าหนึ่งจำนวนเท่านั้นที่ฟังก์ชันนี้จะดำเนินการ ไม่ว่าอาร์เรย์จะมีองค์ประกอบที่ซ้ำกันหรือไม่ คุณสามารถจัดเรียงอาร์เรย์เพื่อดูว่ามีองค์ประกอบใดที่เทียบเท่าหรือไม่
11. คุณจะพบดัชนีขององค์ประกอบในอาร์เรย์ได้อย่างไร?
ดัชนีขององค์ประกอบสามารถค้นพบได้ผ่านการค้นหาแบบเชิงเส้นหรือแบบไบนารี จนกว่าจะหาตำแหน่งที่ตรงกันขององค์ประกอบที่ต้องการ ฟังก์ชันการค้นหาเชิงเส้นจะวนซ้ำทุกองค์ประกอบในอาร์เรย์ จะส่งคืนดัชนีเมื่อพบองค์ประกอบที่ตรงกัน ดังนั้น ความซับซ้อนชั่วคราวของการค้นหาเชิงเส้นคือ O. (n) ทั้งอาร์เรย์ที่เรียงลำดับแล้วและไม่ได้เรียงลำดับสามารถใช้การค้นหาเชิงเส้นได้
การใช้การค้นหาแบบไบนารีซึ่งแบ่งอาร์เรย์เป็นครึ่งหนึ่งอย่างต่อเนื่องจนกว่าค่ามัธยฐานของช่วงเวลาจะตรงกับองค์ประกอบที่ต้องการและจัดทำดัชนี คุณจะได้รับดัชนีขององค์ประกอบหากจัดเรียงอาร์เรย์ ดังนั้น ความซับซ้อนชั่วคราวของการค้นหาแบบไบนารีคือ O. (log n)
12. คุณจะกำจัดองค์ประกอบเฉพาะออกจากอาร์เรย์ได้อย่างไร?
เนื่องจากคุณไม่สามารถลบองค์ประกอบออกจากอาร์เรย์ดั้งเดิมได้เนื่องจากเป็นชุดคงที่ซึ่งมีขนาดที่กำหนดไว้ ผู้สัมภาษณ์จึงต้องการให้คุณแนะนำแนวทางที่แตกต่างออกไปและจัดการกับปัญหาที่คำถามเกิดขึ้น แนวทางปฏิบัติที่ดีที่สุดคือการสร้างอาร์เรย์ใหม่เพื่อลบองค์ประกอบ คุณสามารถทำซ้ำองค์ประกอบจากอาร์เรย์แรกในอาร์เรย์นี้และรวมเฉพาะองค์ประกอบที่คุณต้องการลบเท่านั้น
อีกกลยุทธ์หนึ่งเกี่ยวข้องกับการค้นหาองค์ประกอบเป้าหมายในอาร์เรย์แล้วย้อนกลับลำดับของรายการทั้งหมดที่อยู่ทางด้านขวาขององค์ประกอบเป้าหมาย
13. จะตรวจสอบความเท่าเทียมกันของสองอาร์เรย์ได้อย่างไร?
คุณต้องตรวจสอบความยาวของสองอาร์เรย์ที่ให้มาก่อน รายการที่ตรงกันของทั้งสองอาร์เรย์จะถูกเปรียบเทียบเมื่อความยาวเท่ากัน ทั้งสองอาร์เรย์จะถือว่าเท่ากัน ถ้าแต่ละคู่ขององค์ประกอบในการโต้ตอบทุกครั้งเท่ากัน วิธีนี้ไม่แนะนำให้ตรวจสอบความเท่าเทียมกันของสองอาร์เรย์หากอาร์เรย์มีขนาดใหญ่เนื่องจากจะใช้เวลานาน คุณสามารถใช้วิธี equals() ที่รวมอยู่ในคลาส Arrays ได้ อย่างไรก็ตาม หากผู้สัมภาษณ์ขอให้คุณเปรียบเทียบอาร์เรย์สองอาร์เรย์โดยไม่ต้องใช้เมธอดในตัว วิธีนี้จะเป็นประโยชน์
14. เมื่อเราพูดถึงอาร์เรย์ คุณหมายถึงอะไรโดยวลี "ไดเมนชัน" และ "ตัวห้อย"?
"มิติข้อมูล" ของอาร์เรย์คือจำนวนของดัชนีหรือตัวห้อยที่จำเป็นในการระบุสมาชิกแต่ละคน ตัวห้อยและขนาดอาจไม่ชัดเจน มิติข้อมูลคือคำอธิบายของช่วงของคีย์ที่อนุญาต ในขณะที่ตัวห้อยคือตัวเลข จำเป็นต้องมีตัวห้อยเพียงตัวเดียวสำหรับแต่ละมิติอาร์เรย์
ตัวอย่างเช่น อาร์เรย์ arr[10][5] มีสองมิติ ไซส์ 10 ตัวหนึ่งและอีกตัว 5 ตัว คุณต้องมีตัวห้อยสองตัวเพื่อจัดการกับคอมโพเนนต์ ทั้งคู่อยู่ระหว่าง 0 ถึง 4; รวมหนึ่งระหว่าง 0 ถึง 9
คำถามสัมภาษณ์การเข้ารหัส
15. หาคู่ในอาร์เรย์ที่มีค่า sum . ที่ระบุ
ตัวอย่างเช่น
Input:
- ตัวเลข = [8, 7, 2, 5, 3, 1]
- เป้าหมาย = 10
Output:
- พบคู่ (8, 2)
- Or
- พบคู่ (7, 3)
Input:
- ตัวเลข = [5, 2, 6, 8, 1, 9]
- เป้าหมาย = 12
Output:
- ไม่พบคู่
16. การเรียงลำดับอาร์เรย์ไบนารีด้วยเวลาเชิงเส้น
จัดเรียงอาร์เรย์ไบนารีในเวลาเชิงเส้นและในพื้นที่คงที่ ผลลัพธ์ควรแสดงศูนย์ทั้งหมดก่อน จากนั้นจึงแสดงทั้งหมด
ตัวอย่างเช่น
- อินพุต: { 1, 0, 1, 0, 1, 0, 0, 1 }
- เอาท์พุต: { 0, 0, 0, 0, 1, 1, 1, 1 }
แนวทางที่ตรงไปตรงมาคือการคำนวณจำนวนรวมของอาร์เรย์ที่เป็น 0 พูดว่า k แล้วเติมดัชนี k ตัวแรกในอาร์เรย์ด้วย 0 และดัชนีที่เหลือด้วย 1 อีกทางหนึ่ง เราอาจคำนวณว่า 1 ทั้งหมดมีทั้งหมดกี่ตัวในอาร์เรย์ อาร์เรย์ k เติมดัชนี k สุดท้ายในอาร์เรย์ด้วย 1 และปล่อยให้ดัชนีที่เหลือเติมด้วย 0
วิธีการที่กำหนดให้มีความซับซ้อนของเวลา O(n) และไม่ใช้พื้นที่จัดเก็บเพิ่มเติม โดยที่ n คือขนาดของอินพุต
17. ค้นหาผลิตภัณฑ์สองอินต์ที่ใหญ่ที่สุดในอาร์เรย์
ค้นหาผลคูณที่ใหญ่ที่สุดของตัวเลขสองตัวในอาร์เรย์จำนวนเต็ม
ลองนึกถึงอาร์เรย์ 10 3 5 6 2 เป็นตัวอย่าง คู่ (-10, -3) หรือ (5, 6) เป็นผลิตภัณฑ์สูงสุด
การคิดเกี่ยวกับการผสมผสานทุกองค์ประกอบและค้นหาผลิตภัณฑ์ของพวกเขาเป็นแนวทางที่โง่เขลา หากผลิตภัณฑ์ของคู่ปัจจุบันมากกว่าผลิตภัณฑ์สูงสุดที่ได้รับ ให้อัปเดตผลิตภัณฑ์สูงสุด พิมพ์ส่วนประกอบของผลิตภัณฑ์ขั้นสุดท้าย
วิธีแก้ปัญหาข้างต้น โดยที่ n คือจำนวนอินพุต มีความซับซ้อนของเวลา O(n2) และไม่กินพื้นที่อีกต่อไป
18. วิธีเปลี่ยนศูนย์ของอาร์เรย์ทั้งหมดไปที่จุดสิ้นสุด
ย้ายศูนย์ทั้งหมดในอาร์เรย์จำนวนเต็มไปที่จุดสิ้นสุด คำตอบควรหลีกเลี่ยงการใช้พื้นที่คงที่และรักษาลำดับสัมพัทธ์ของส่วนประกอบของอาร์เรย์
อินพุต: {1,2,3,0,8,0,4,7}
ผลลัพธ์จะเป็น {1,2,3,8,4,7,0,0}
วางองค์ประกอบในตำแหน่งที่มีอยู่ต่อไปนี้ในอาร์เรย์หากองค์ประกอบปัจจุบันไม่ใช่ศูนย์ เติมดัชนีที่เหลือทั้งหมดด้วย 0 เมื่อรายการของอาร์เรย์ได้รับการประมวลผลทั้งหมดแล้ว
โซลูชันก่อนหน้านี้มีความซับซ้อนของเวลา O(n) โดยที่ n คือขนาดของอินพุต
19. วิธีการเรียงลำดับอาร์เรย์ที่มีสองรายการที่สลับในการดำเนินการเดียว
จัดเรียงอาร์เรย์ในเวลาเชิงเส้นที่กำหนดสองรายการที่สลับและอาร์เรย์ที่มีองค์ประกอบทั้งหมดจัดเรียงตามลำดับจากน้อยไปมาก แสร้งทำเป็นว่าอาร์เรย์ไม่มีรายการที่ซ้ำกัน
อินพุต:= [1,9,3,4,7,2] หรือ [9,3,7,2,1,4] หรือ [2,4,1,7,3,9]
เอาท์พุต: = [1,2,3,4,7,9]
เริ่มต้นด้วยองค์ประกอบที่สองในอาร์เรย์ วัตถุประสงค์คือเพื่อเปรียบเทียบแต่ละองค์ประกอบกับองค์ประกอบก่อนหน้า ตำแหน่งของข้อพิพาทถูกเก็บไว้โดยใช้ตัวชี้สองตัวคือ x และ y
อัปเดต x เป็นดัชนีขององค์ประกอบก่อนหน้า และ y เป็นดัชนีขององค์ประกอบปัจจุบัน หากอดีตมีขนาดใหญ่กว่าตัวหลัง อัปเดต y เป็นดัชนีขององค์ประกอบปัจจุบัน หากปรากฎว่าองค์ประกอบก่อนหน้ามีค่ามากกว่าองค์ประกอบปัจจุบัน
สุดท้าย เปลี่ยนองค์ประกอบที่ดัชนี x และ y เมื่อเราประมวลผลองค์ประกอบที่อยู่ติดกันแต่ละคู่เสร็จแล้ว
เนื่องจากวิธีการดังกล่าวทำการสแกนอาร์เรย์อินพุตขนาด n เพียงครั้งเดียว ความซับซ้อนของเวลาคือ O(n) ไม่จำเป็นต้องใช้พื้นที่เพิ่มเติมสำหรับการแก้ปัญหา
20. วิธีรวมอาร์เรย์ที่จัดเรียงไว้สองชุดเข้าด้วยกัน
รวมรายการของอาร์เรย์ X[] และ Y[]—อาร์เรย์ที่จัดเรียงสองรายการที่มีขนาด m และ n แต่ละรายการ—โดยคงลำดับการเรียงลำดับ นั่นคือ โดยการเติม X[] ด้วยองค์ประกอบที่เล็กที่สุด m ตัวแรก และเติม Y[] ด้วย องค์ประกอบที่เหลือ
หากองค์ประกอบในอาร์เรย์ X[] อยู่ที่ตำแหน่งที่ถูกต้องอยู่แล้ว (เช่น องค์ประกอบที่เล็กที่สุดในบรรดาองค์ประกอบที่เหลือ) ให้ไม่สนใจองค์ประกอบนั้น มิฉะนั้น ให้แทนที่ด้วยองค์ประกอบที่เล็กที่สุด ซึ่งเป็นสมาชิกคนแรกของ Y[] ด้วย หากต้องการเก็บลำดับการจัดเรียงหลังจากสลับ ให้โอนองค์ประกอบ (ตอนนี้ที่ Y[0]) ไปยังตำแหน่งที่เหมาะสมใน Y[]
ขนาดของอาร์เรย์แรกคือ m และขนาดของอาร์เรย์ที่สองคือ n และความซับซ้อนของเวลาคือ O(mn)
21. จะเรียงลำดับอาร์เรย์ของรายการใหม่โดยสลับตำแหน่งสูงและต่ำได้อย่างไร?
จัดเรียงอาร์เรย์จำนวนเต็มใหม่เพื่อให้สมาชิกที่ตามมาแต่ละตัวมีขนาดใหญ่กว่าองค์ประกอบก่อนหน้าและที่ตามมา สมมติว่าอาร์เรย์ไม่มีองค์ประกอบที่ซ้ำกัน
การเรียงลำดับอาร์เรย์หรือใช้พื้นที่เพิ่มเติมไม่จำเป็นสำหรับแนวทางที่มีประสิทธิภาพ แผนคือ เริ่มต้นด้วย สมาชิกที่สองของอาร์เรย์และเพิ่มขึ้นสองสำหรับการวนซ้ำแต่ละครั้ง
สลับส่วนประกอบหากองค์ประกอบสุดท้ายเกินองค์ประกอบแรก ในแนวทางเดียวกัน ให้สลับทั้งสองรายการหากองค์ประกอบต่อไปนี้ใหญ่กว่าองค์ประกอบปัจจุบัน เราจะได้อาร์เรย์ที่ต้องการซึ่งเป็นไปตามข้อจำกัดที่ระบุในตอนท้ายของลูป
22. วิธีการแทนที่แต่ละองค์ประกอบของอาร์เรย์โดยไม่ต้องใช้ตัวดำเนินการหารด้วยผลคูณของแต่ละองค์ประกอบในอาร์เรย์?
โดยไม่ต้องใช้ตัวดำเนินการหาร ให้แทนที่แต่ละองค์ประกอบในอาร์เรย์จำนวนเต็มด้วยผลคูณขององค์ประกอบอื่นๆ ทั้งหมด
ในเวลาเชิงเส้นและปริภูมิคงที่ เราสามารถใช้การเรียกซ้ำเพื่อแก้ไขปัญหานี้ การคำนวณผลคูณของแต่ละองค์ประกอบในอาร์เรย์ย่อยด้านขวาซ้ำๆ และส่งผ่านผลิตภัณฑ์ย่อยในอาร์เรย์ย่อยด้านซ้าย เนื่องจากพารามิเตอร์ของฟังก์ชันคือแนวคิด
ความซับซ้อนของเวลาคือ O(n)
23. ค้นหาองค์ประกอบที่แปลกที่สุดในอาร์เรย์ในเวลาลอการิทึม
กำหนดอาร์เรย์จำนวนเต็มซึ่งสมาชิกทั้งหมดยกเว้นหนึ่งรายมีจำนวนเหตุการณ์เป็นคู่กัน ปัญหาคือการกำหนดจำนวนครั้งที่องค์ประกอบนี้ปรากฏขึ้น ค้นหาองค์ประกอบที่เกิดขึ้นคี่ในเวลาลอการิทึมและพื้นที่คงที่หากองค์ประกอบเดียวกันเกิดขึ้นเป็นคู่ในอาร์เรย์และไม่สามารถมีองค์ประกอบที่กำหนดได้เกินสองอินสแตนซ์ในแถว
การดำเนินการ XOR ช่วยให้เราสามารถแก้ไขปัญหานี้ได้ในเวลาเชิงเส้น เป้าหมายคือ XOR ทุกองค์ประกอบในอาร์เรย์ มีเพียงองค์ประกอบที่เกิดขึ้นคี่เท่านั้นที่ยังคงอยู่หลังจากที่องค์ประกอบที่เกิดขึ้นคู่กันจะแยกออกจากกัน
ปัญหานี้สามารถแก้ไขได้ในเวลา O(log(n))
24. จะหาองค์ประกอบที่ใหญ่กว่าที่ตามมาสำหรับแต่ละองค์ประกอบในอาร์เรย์แบบวงกลมได้อย่างไร?
องค์ประกอบที่ใหญ่กว่าถัดไปสำหรับแต่ละองค์ประกอบในอาร์เรย์จำนวนเต็มวงกลมควรอยู่ จำนวนเต็มที่มากกว่าตัวแรกหลังองค์ประกอบ x ในอาร์เรย์คือองค์ประกอบที่มากกว่าขององค์ประกอบนั้น
จากขวาไปซ้าย เราอาจดำเนินการกับรายการอาร์เรย์ เป้าหมายคือการวนซ้ำสำหรับแต่ละองค์ประกอบ x จนกว่าสแต็กจะว่างเปล่าหรือเรามีองค์ประกอบที่สูงกว่าอยู่ด้านบน ตั้งค่าองค์ประกอบที่ใหญ่กว่าถัดไปของ x ให้ปรากฏบนสแต็กเมื่อปรากฏ
25. ค้นหาจำนวนผกผันของอาร์เรย์?
ค้นหาจำนวนการผกผันของอาร์เรย์ทั้งหมด คู่ I j) หมายถึงการผกผันของอาร์เรย์ A ถ้าฉัน j) และ (A[i] > A[j]) เราต้องนับคู่เหล่านี้ทุกคู่ในอาร์เรย์
การนับสมาชิกอาร์เรย์ทั้งหมดที่น้อยกว่าทางด้านขวาและเพิ่มผลลัพธ์ไปยังเอาต์พุตเป็นวิธีการที่ตรงไปตรงมา
โซลูชันนี้มีความซับซ้อน O(n2) โดยที่ n คือขนาดของอินพุต
26. ปัญหาการดักจับน้ำฝนคืออะไร?
การหาปริมาณน้ำที่สามารถกักขังได้มากที่สุดในชุดของแท่งที่มีความกว้างหนึ่งหน่วยแต่ละอันเรียกว่าปัญหา "การดักจับปริมาณน้ำฝน"
เป้าหมายคือการกำหนดแถบสูงสุดที่อาจวางไว้ทางซ้ายและขวาของแต่ละแถบ ค่าต่ำสุดของแถบนำทางด้านซ้ายและด้านขวา ซึ่งน้อยกว่าความสูงของแถบปัจจุบัน คือปริมาณน้ำที่เก็บไว้ด้านบนของแต่ละแท่ง
สรุป
เมื่อเทียบกับหัวข้อโครงสร้างข้อมูลอื่นๆ อาร์เรย์จะง่ายกว่า เพื่อที่จะตอบคำถามสัมภาษณ์อาเรย์ คุณต้องมีความเข้าใจพื้นฐานเกี่ยวกับอาร์เรย์
คุณควรตรวจสอบพื้นฐานของอาร์เรย์อย่างละเอียด รวมถึงการดำเนินการอาร์เรย์ (ตั้งแต่การประกาศ/การสร้างอาร์เรย์ไปจนถึงการเข้าถึง/แก้ไขรายการอาร์เรย์) ตลอดจนแนวคิดการเขียนโปรแกรม เช่น การวนซ้ำ การเรียกซ้ำ และโอเปอเรเตอร์พื้นฐาน เพื่อที่จะตอบคำถามสัมภาษณ์อาร์เรย์ได้สำเร็จ ตระหนักถึงปัญหาอย่างสมบูรณ์
คุณควรขอคำชี้แจงหากคุณมีข้อสงสัยใดๆ ลองนึกถึงการแบ่งปัญหาออกเป็นส่วนๆ ที่จัดการได้มากขึ้น ตรวจสอบให้แน่ใจว่าคุณมีอัลกอริทึมอยู่ในใจก่อนเริ่มเขียนโปรแกรม จดหรือนึกภาพไว้ในผังงาน แล้วเริ่มเขียนโค้ด
เขียนความเห็น