interview practice
1.0.0
หากคุณมีการสัมภาษณ์ที่เกิดขึ้นที่ บริษัท เช่น Google หรือ Amazon (และอื่น ๆ อีกมากมาย ... ) ที่คุณรู้ว่าจะถามคำถามทางเทคนิคแล้วคุณมาถึงสถานที่ที่ดีในการเตรียมตัวเอง! ที่ระบุไว้ใน readme นี้เป็นคำถามทางวิทยาศาสตร์คอมพิวเตอร์ที่จะตอบภายในแพ็คเกจ/ไฟล์ชั้นเรียนแยกต่างหาก โซลูชันแต่ละวิธีอาจรวมถึงไฟล์ตัวอย่างที่เกี่ยวข้องซึ่งจะมีคลาสหลักและการสาธิตที่โซลูชันแนะนำให้เล่นกับสิ่งเหล่านี้และเรียนรู้เกี่ยวกับกรณีมุมทั้งหมด!
มันไม่ได้จัดระเบียบเช่นนี้โดยไม่มีเหตุผล! ขอแนะนำให้มีความเข้าใจที่ดีเกี่ยวกับโครงสร้างข้อมูลและประเภทต่าง ๆ และการค้นหาก่อนที่จะย้ายไปยังปัญหาการสัมภาษณ์ทั่วไป สิ่งเหล่านี้จะเป็นเครื่องมือของคุณที่จะช่วยให้เข้าใจและแก้ปัญหาการสัมภาษณ์ที่แตกต่างกัน การทำทุกประเภทเป็นทางเลือก แต่ขอแนะนำให้คุณมีความเข้าใจที่ดีในการเรียงลำดับขั้นต่ำหนึ่ง o (nlogn)
readme นี้ได้รับการออกแบบให้เรียบง่ายและรวดเร็วในการเรียกดูโดยใช้ control-F เท่านั้น หากคุณต้องการข้ามไปยังที่ไหนสักแห่งใน readMe เพียงค้นหา (ใช้ control-F) สำหรับมันในวงเล็บสี่เหลี่ยมจัตุรัส ตรวจสอบให้แน่ใจว่าการค้นหาของคุณไม่ละเอียดอ่อน!
ตัวเลือกการค้นหาด่วน:
หากคุณพบข้อผิดพลาดใด ๆ ในรหัสของฉันและจะมีข้อผิดพลาดลองและแก้ไขเป็นแบบฝึกหัด! เมื่อคุณคิดว่าคุณมีการใช้งานที่ใช้งานได้แล้วยิงคำขอดึงฉันฉันมักจะขอบคุณความช่วยเหลือที่เป็นมิตร :) หากคุณมีความคิดสำหรับสิ่งที่คุณต้องการเพิ่มอย่าลังเลที่จะเขียนโค้ดและยิงคำขอดึงฉันเพียงแค่โปรดรักษารหัสของคุณให้สะอาด - รหัสสะอาดหรือไม่มีรหัสเลย อีกครั้งฉันมักจะขอบคุณความช่วยเหลือและขอบคุณล่วงหน้า :)
public Queue ( int maxSize )
public void enqueue ( int data )
public int dequeue ()
public int peek ()
public boolean isFull ()
public boolean isEmpty ()
public String toString () public StackQueue ()
public StackQueue ( Type [] list )
public void enqueue ( Type obj )
public Type dequeue ()
public boolean isEmpty () public LinkedList ()
public Node < Type > find ( Type data )
public int getLength ()
public void addDataAtHead ( Type data )
public void addNodeAtHead ( Node < Type > nextNode )
public Node < Type > deleteHead () throws ...
public String toString ()ทำเช่นเดียวกับคำถามที่ 2 แต่ใช้ DoublelinkedList คุณจะต้องมีคลาสโหนดใหม่
ย้อนกลับลิสต์ SinglelinkedList ส่วนหัววิธีการควรมีลักษณะ:
public void reverse () // put this method inside your LinkedList class public boolean cyclic () // put this method inside your LinkedList class public Stack ()
public Type pop ()
public void push ( Type data )
public Type peek ()
public String toString () public Heap ( int initialSize )
public Heap ( int [] initialValues )
public void add ( int integer )
public boolean delete ( int integer )
public int peek ()
public int pop ()
public boolean contains ( int integer )
public boolean isEmpty ()
public int size () public PriorityQueue ( int initialSize )
public PriorityQueue ( int [] list )
public void enqueue ( int data )
public int dequeue ()
public int peek ()
public boolean isEmpty () public BinarySearchTree ( Integer data )
public BinarySearchTree ()
public TreeNode find ( Integer searchKey )
public void insert ( TreeNode insertNode )
public boolean delete ( Integer searchKey ) // return true if object deleted, false if object not in list
public void inOrderTraversal ()
public void preOrderTraversal ()
public void postOrderTraversal ()
public TreeNode smallest ()
public TreeNode biggest ()สำหรับทุกประเภทให้วิเคราะห์ความเร็วโดยใช้สัญกรณ์ Big-O โปรแกรมทุกประเภทเป็นวิธีการคงที่ในแต่ละคลาสที่แต่ละชั้นมีวิธีการหลักที่ทดสอบการเรียงลำดับ
private static void bubbleSort ( int [] list ) private static void selectionSort ( int [] list ) private static void insertionSort ( int [] list ) private static void mergeSort ( int [] list ) private static void quickSort ( int [] list ) private static void shellSort ( int [] list ) private static void countingSort ( int [] list , int startRange , int endRange ) private static void radixSort ( int [] list ) private static void bucketSort ( int [] list ) private static void heapSort ( int [] list ) private static int binarySearchArray ( int [] list , int searchKey )[P1] ใช้แฟคทอเรียลซ้ำ นำไปใช้อีกครั้ง แต่คราวนี้ใช้การเรียกซ้ำหาง การเรียกซ้ำหางคืออะไร? Java ได้รับการปรับให้เหมาะสมสำหรับการเรียกซ้ำหางหรือไม่?
[P2] แก้ปัญหาหอคอยที่มีชื่อเสียงของฮานอย หางเรียกซ้ำหรือไม่? ทำไมหรือทำไมไม่?
[P3] สมมติว่าฉันให้ตัวเลขแก่คุณสมมติว่าพวกเขาเป็นตัวแทนของราคาหุ้นหาเงินมากที่สุดที่คุณสามารถทำได้ในวันนั้นโดยการซื้อและขายหุ้นเดียว หากหุ้นลดลงทั้งวันคุณควรหาเงินจำนวนน้อยที่สุดที่ฉันอาจสูญเสียในวันนั้น ส่วนหัวของวิธีการควรมีลักษณะ:
private static int bestStockTrade ( int [] stockPrices ) throws ...[P4] ได้รับอาร์เรย์ของจำนวนเต็มเช่น [1, 2, 3, 4], ส่งคืนอาร์เรย์ที่แต่ละดัชนีคุณจะได้รับผลลัพธ์ของการคูณด้วยค่าอื่น ๆ ทั้งหมด เช่น [1, 2, 3, 4] -> [2x3x4, 1x3x4, 1x2x4, 1x2x3] อย่าใช้แผนก ส่วนหัวของวิธีการควรมีลักษณะ:
private static int [] productAllButMe ( int [] data ) throws ...[P5] เมื่อได้รับจำนวนเต็มอาร์เรย์อะไรคือผลิตภัณฑ์สูงสุดที่คุณจะได้รับจากการคูณจำนวนเต็ม 3 ตัวใด ๆ ส่วนหัวของวิธีการควรมีลักษณะ:
private static int productOfThree ( int [] data ) throws ...[P6] ได้รับชุดจำนวนเต็มคู่เขียนฟังก์ชั่นที่ผ่านและดูว่าส่วนใดของไทม์ไลน์ที่ครอบคลุม เช่น ได้รับอาร์เรย์ของ [(1,4), (2,7), (9,11), (1,3), (12,14)] -> [(1,7), (9,14)] คุณสามารถจินตนาการได้ว่าสิ่งนี้มีประโยชน์ถ้าเรามีรายชื่อทุกตารางเวลาและเราต้องการดูว่าทุกคนว่างเมื่อใด สำหรับการแสดงที่แท้จริงของอินพุตให้ใช้คลาสต่อไปนี้:
class Schedule {
public int startTime ;
public int endTime ;
public Schedule ( int startTime , int endTime ) {
this . startTime = startTime ;
this . endTime = endTime ;
}
@ Override
public String toString () {
return "(" + startTime + " , " + endTime + ")" ;
}
}สำหรับส่วนหัววิธี:
private static List < Schedule > scheduler ( List < Schedule > schedules )[P7] ให้ผู้คนมากมายซึ่งบุคคลนั้นเป็นตัวแทนของเวลาเริ่มต้นและเวลาจบสำหรับการเปลี่ยนการทำงานของพวกเขากลับรายการที่สั้นที่สุดที่เป็นไปได้ของผู้คนที่คนเหล่านั้นเห็นคนอื่น ๆ ทั้งหมดในระหว่างการเปลี่ยนแปลงของพวกเขา ตัวอย่างเช่นหากได้รับคนเหล่านี้ (1, 2), (2, 10), (5, 6) คุณควรกลับมา (2, 10) เพราะคนนี้เห็นคนอื่นในระหว่างการเปลี่ยนแปลงของเขา หากได้รับ (1, 5), (4, 10), (2, 3), (11, 13) -> (1, 5), (11, 13) สำหรับการเป็นตัวแทนที่แท้จริงของบุคคลให้ใช้คลาสต่อไปนี้:
class Person {
public int startTime ;
public int finishTime ;
public Person ( int startTime , int finishTime ) {
this . startTime = startTime ;
this . finishTime = finishTime ;
}
@ Override
public String toString () {
return "(" + startTime + " , " + finishTime + ")" ;
}
}สำหรับส่วนหัววิธี:
private static List < Person > selectPeople ( List < Person > people ) throws ...[P8] ได้รับอาร์เรย์ของจำนวนเต็มซึ่งรับประกันได้ว่าจะมีหมายเลขหนึ่งที่ไม่ซ้ำกันให้ค้นหาหมายเลขนั้น โปรดทราบว่าในรายการหมายเลขคู่นี้มีเพียง 1 หมายเลขเท่านั้นที่ไม่มีการทำซ้ำและหมายเลขอื่น ๆ ทุกตัวมีหนึ่งเดียวที่ซ้ำกัน อินพุตที่เป็นไปได้: [1, 2, 2, 3, 3, 4, 4], [2], [3, 7, 3] ฯลฯ ...
สำหรับส่วนหัววิธี:
private static int uncoupledInteger ( int [] list ) คะแนนพิเศษ: คุณสามารถทำในหน่วยความจำคงที่และเวลาเชิงเส้นได้หรือไม่?
[P9] ได้รับสตริงที่เต็มไปด้วยตัวคั่นให้ตรวจสอบว่าสตริงมีตัวคั่นที่สมดุลหรือไม่ ตัวคั่นเพียงตัวเดียวที่เราจะกังวลในปัญหานี้มีดังต่อไปนี้: [] {} () ไม่มีอักขระอื่นในสตริงนี้ยกเว้นตัวคั่น สตริงต่อไปนี้มีความสมดุลและควรกลับมาเป็นจริง: "", "()", "{} () []", "([{}])" สตริงต่อไปนี้ไม่สมดุลและควรกลับมาเป็นเท็จ: "[", "{}}", "{{]}", "{[}]"
สำหรับส่วนหัววิธี:
private static boolean balancedDelimiters ( String delimiters ) [P10] ได้รับอาร์เรย์ของจำนวนเต็มและผลรวมเป้าหมายทำฟังก์ชั่นที่ส่งคืนจริงหากผลรวมเป้าหมายเป็นผลรวมของจำนวนเต็มสองตัวในอาร์เรย์ ตัวอย่างเช่นได้รับอาร์เรย์ [1, 2, 3, 4, -100, 0, 0] และเป้าหมาย 5 มันควรกลับมาเป็นจริงเพราะ 4 + 1 = 5. โปรดทราบว่าหากได้รับอาร์เรย์เดียวกัน แต่เป้าหมายคือ 8 คำตอบจะกลับเท็จ คุณไม่สามารถเพิ่มจำนวนเต็มให้กับตัวเองเพื่อสร้างเป้าหมายได้คุณต้องหาจำนวนเต็มสองตัวแยกกัน โปรดทราบว่าจำนวนเต็มสองอันที่แยกจากกันอาจมีค่าเท่ากันเช่น หากได้รับอาร์เรย์เดียวกัน แต่ได้รับ 0 เป็นเป้าหมายมันควรกลับมาเป็นจริงเพราะมีจำนวนเต็มสองตัวในอาร์เรย์ที่รวมเป็น 0 - 0 ในดัชนีที่ 5 และ 0 ในดัชนีที่ 6
สำหรับส่วนหัววิธี:
private static boolean targetSummable ( int [] array , int target ) 
