海星科技技術(shù)面試題集錦與實(shí)戰(zhàn)技巧分享本文借鑒了近年相關(guān)經(jīng)典試題創(chuàng)作而成，力求幫助考生深入理解測(cè)試題型，掌握答題技巧，提升應(yīng)試能力。一、編程題1.題目：給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。輸入：鏈表的頭節(jié)點(diǎn)。輸出：返回一個(gè)布爾值，表示鏈表中是否有環(huán)。示例：輸入：head=[3,2,0,-4],pos=1輸出：true解釋：鏈表中有環(huán)，環(huán)的起始節(jié)點(diǎn)為節(jié)點(diǎn)2。提示：鏈表中的節(jié)點(diǎn)數(shù)目在范圍[0,104]內(nèi)-105<=Node.val<=105pos為-1或者鏈表中的節(jié)點(diǎn)數(shù)2.題目：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。輸入：排序數(shù)組。輸出：移除重復(fù)元素后的數(shù)組的新長(zhǎng)度。示例：輸入：nums=[1,1,2]輸出：2,nums=[1,2]解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度2，并且nums的前兩個(gè)元素應(yīng)該是1和2。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。提示：給定數(shù)組的長(zhǎng)度在[0,20000]范圍內(nèi)。輸入的數(shù)組是一個(gè)非遞減排序的數(shù)組。3.題目：給定一個(gè)包含n個(gè)整數(shù)的數(shù)組nums和一個(gè)目標(biāo)值target，判斷數(shù)組中是否存在四個(gè)元素a,b,c和d，使得a+b+c+d的值與target相等？找出所有滿足條件且不重復(fù)的四元組。輸入：整數(shù)數(shù)組nums和目標(biāo)值target。輸出：所有滿足條件且不重復(fù)的四元組。示例：輸入：nums=[1,0,-1,0],target=0輸出：[[-1,0,0,1],[-1,-1,0,2]]提示：給定數(shù)組nums的長(zhǎng)度不會(huì)超過(guò)200。給定數(shù)組中的整數(shù)范圍在[-1000,1000]。結(jié)果數(shù)組的整數(shù)順序不能重復(fù)。4.題目：實(shí)現(xiàn)Trie(前綴樹)。說(shuō)明：Trie（發(fā)音類似"try"）或者說(shuō)前綴樹是一種用于檢索字符串?dāng)?shù)據(jù)集中的鍵的有序樹數(shù)據(jù)結(jié)構(gòu)。實(shí)現(xiàn)Trie類：`Trie()`初始化前綴樹對(duì)象。`voidinsert(Stringword)`插入一個(gè)單詞到前綴樹中。`booleansearch(Stringword)`返回`true`如果`word`在前綴樹中，或者可以變?yōu)榍熬Y樹中的一個(gè)前綴。如果不是，返回`false`。`booleanstartsWith(Stringprefix)`返回`true`如果`prefix`是前綴樹中的一個(gè)前綴，或者可以變?yōu)榍熬Y樹中的一個(gè)前綴。如果不是，返回`false`。示例：```javaTrietrie=newTrie();trie.insert("apple");trie.search("apple");//返回truetrie.search("app");//返回falsetrie.startsWith("app");//返回truetrie.insert("app");trie.search("app");//返回true```提示：1<=word.length,prefix.length<=2000word和prefix僅由小寫英文字母組成。二、算法題1.題目：快速排序描述：給定一個(gè)數(shù)組nums，編寫一個(gè)函數(shù)quickSort(nums)來(lái)實(shí)現(xiàn)快速排序算法。輸入：一個(gè)包含n個(gè)整數(shù)的數(shù)組nums。輸出：對(duì)數(shù)組nums進(jìn)行快速排序后的結(jié)果。示例：輸入：nums=[10,7,8,9,1,5]輸出：[1,5,7,8,9,10]提示：數(shù)組的長(zhǎng)度在[1,1000]范圍內(nèi)。數(shù)組中的元素可以是任意整數(shù)。2.題目：二分查找描述：給定一個(gè)n個(gè)元素有序的（升序）整型數(shù)組nums和一個(gè)目標(biāo)值target，寫一個(gè)函數(shù)搜索nums中的target，如果目標(biāo)值存在返回其索引，否則返回-1。輸入：一個(gè)有序的整型數(shù)組nums和一個(gè)目標(biāo)值target。輸出：目標(biāo)值在數(shù)組中的索引，如果不存在返回-1。示例：輸入：nums=[-1,0,3,5,9,12],target=9輸出：4解釋：9出現(xiàn)在nums中并且下標(biāo)為4。提示：你可以假設(shè)nums中的所有元素是不重復(fù)的。n是一個(gè)正整數(shù)，表示nums中的元素個(gè)數(shù)。-10^9<=nums[i]<=10^9-10^9<=target<=10^93.題目：鏈表反轉(zhuǎn)描述：給定一個(gè)鏈表，反轉(zhuǎn)該鏈表。輸入：鏈表的頭節(jié)點(diǎn)。輸出：反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)。示例：輸入：head=[1,2,3,4,5]輸出：[5,4,3,2,1]提示：鏈表中的節(jié)點(diǎn)數(shù)目在范圍[0,5000]內(nèi)-5000<=Node.val<=50004.題目：合并兩個(gè)有序鏈表描述：給定兩個(gè)有序鏈表的頭節(jié)點(diǎn)head1和head2，將它們合并為一個(gè)新的有序鏈表并返回。新鏈表是由兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。輸入：兩個(gè)有序鏈表的頭節(jié)點(diǎn)head1和head2。輸出：合并后的有序鏈表的頭節(jié)點(diǎn)。示例：輸入：head1=[1,2,4],head2=[1,3,4]輸出：[1,1,2,3,4,4]提示：兩個(gè)鏈表長(zhǎng)度范圍在[0,5000]內(nèi)-104<=Node.val<=104三、系統(tǒng)設(shè)計(jì)題1.題目：設(shè)計(jì)一個(gè)URL緩存系統(tǒng)描述：設(shè)計(jì)一個(gè)URL緩存系統(tǒng)，支持以下操作：`cache.put(url,value)`:將URL緩存到系統(tǒng)中。`cache.get(url)`:返回緩存中URL對(duì)應(yīng)的值，如果沒(méi)有緩存則返回-1。要求：緩存容量有限，當(dāng)緩存滿時(shí)，需要?jiǎng)h除最近最少使用的URL。緩存命中時(shí)，需要將對(duì)應(yīng)的URL移動(dòng)到最近最常用的位置。輸入：一系列緩存操作，包括`put`和`get`操作。輸出：每個(gè)緩存操作的結(jié)果。示例：```plaintextcache.put("","HelloWorld")cache.get("")//返回"HelloWorld"cache.put("","Welcometothesite")cache.get("")//返回"HelloWorld"cache.put("","Anotherexample")cache.get("")//返回"HelloWorld"cache.get("")//返回"Welcometothesite"cache.get("")//返回"Anotherexample"```提示：緩存容量有限，假設(shè)為3。操作序列可能很長(zhǎng)，需要高效處理。2.題目：設(shè)計(jì)一個(gè)簡(jiǎn)單的消息隊(duì)列系統(tǒng)描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的消息隊(duì)列系統(tǒng)，支持以下操作：`enqueue(message)`:將消息加入隊(duì)列尾部。`dequeue()`:返回隊(duì)列頭部消息并從隊(duì)列中刪除。要求：隊(duì)列支持高效的入隊(duì)和出隊(duì)操作。隊(duì)列不應(yīng)該是空的。輸入：一系列入隊(duì)和出隊(duì)操作。輸出：每個(gè)出隊(duì)操作的結(jié)果。示例：```plaintextenqueue("Message1")enqueue("Message2")dequeue()//返回"Message1"enqueue("Message3")dequeue()//返回"Message2"dequeue()//返回"Message3"```提示：隊(duì)列長(zhǎng)度可能很長(zhǎng)，需要高效處理。操作序列可能很長(zhǎng)，需要高效處理。四、數(shù)據(jù)庫(kù)題1.題目：SQL查詢描述：假設(shè)有一個(gè)名為`Employees`的表，包含以下列：`EmployeeID`(主鍵)`Name``Department``Salary`編寫SQL查詢，返回以下結(jié)果：每個(gè)部門的平均工資。只有工資高于平均工資的員工的名字和部門。輸入：`Employees`表的數(shù)據(jù)。輸出：兩個(gè)查詢結(jié)果。示例：```sql--查詢每個(gè)部門的平均工資SELECTDepartment,AVG(Salary)ASAverageSalaryFROMEmployeesGROUPBYDepartment;--查詢只有工資高于平均工資的員工的名字和部門SELECTName,DepartmentFROMEmployeese1WHEREe1.Salary>(SELECTAVG(e2.Salary)FROMEmployeese2WHEREe1.Department=e2.Department);```提示：使用子查詢和聚合函數(shù)。確保查詢效率。2.題目：SQL連接描述：假設(shè)有兩個(gè)表：`Orders`表：包含訂單信息`OrderID`(主鍵)`CustomerID``OrderDate``Customers`表：包含客戶信息`CustomerID`(主鍵)`CustomerName``City`編寫SQL查詢，返回每個(gè)客戶的訂單數(shù)量和他們所在的城市。輸入：`Orders`和`Customers`表的數(shù)據(jù)。輸出：查詢結(jié)果。示例：```sqlSELECTCustomers.CustomerName,Customers.City,COUNT(Orders.OrderID)ASOrderCountFROMOrdersJOINCustomersONOrders.CustomerID=Customers.CustomerIDGROUPBYCustomers.CustomerName,Customers.City;```提示：使用內(nèi)連接。確保查詢效率。五、行為面試題1.題目：請(qǐng)描述一次你解決復(fù)雜問(wèn)題的經(jīng)歷。提示：描述問(wèn)題的背景和復(fù)雜性。解釋你采取的步驟和方法。分享你從中學(xué)到的東西。2.題目：請(qǐng)描述一次你與團(tuán)隊(duì)成員合作完成項(xiàng)目的經(jīng)歷。提示：描述項(xiàng)目的背景和目標(biāo)。解釋你在團(tuán)隊(duì)中的角色和貢獻(xiàn)。分享你從中學(xué)到的東西。3.題目：請(qǐng)描述一次你面對(duì)挑戰(zhàn)和失敗的經(jīng)歷。提示：描述挑戰(zhàn)或失敗的具體情況。解釋你是如何應(yīng)對(duì)和解決問(wèn)題的。分享你從中學(xué)到的東西。4.題目：請(qǐng)描述一次你主動(dòng)提出改進(jìn)建議的經(jīng)歷。提示：描述改進(jìn)建議的具體內(nèi)容。解釋你是如何提出和推動(dòng)改進(jìn)的。分享你從中學(xué)到的東西。六、答案和解析一、編程題1.答案：```javapublicclassSolution{publicbooleanhasCycle(ListNodehead){if(head==null||head.next==null){returnfalse;}ListNodeslow=head;ListNodefast=head.next;while(fast!=null&&fast.next!=null){if(slow==fast){returntrue;}slow=slow.next;fast=fast.next.next;}returnfalse;}}```解析：使用快慢指針?lè)?。慢指針每次移?dòng)一步，快指針每次移動(dòng)兩步。如果鏈表中存在環(huán)，快慢指針最終會(huì)相遇。如果快指針到達(dá)鏈表末尾，則鏈表中不存在環(huán)。2.答案：```javapublicclassSolution{publicintremoveDuplicates(int[]nums){if(nums==null||nums.length==0){return0;}intslow=0;for(intfast=1;fast<nums.length;fast++){if(nums[fast]!=nums[slow]){slow++;nums[slow]=nums[fast];}}returnslow+1;}}```解析：使用雙指針?lè)?。慢指針指向?dāng)前不重復(fù)的最后一個(gè)元素，快指針遍歷數(shù)組。如果快指針指向的元素與慢指針指向的元素不同，則將慢指針向前移動(dòng)一位，并復(fù)制快指針指向的元素。最終慢指針的位置加一即為新數(shù)組的長(zhǎng)度。3.答案：```javaimportjava.util.ArrayList;importjava.util.Arrays;importjava.util.List;publicclassSolution{publicList<List<Integer>>fourSum(int[]nums,inttarget){Arrays.sort(nums);List<List<Integer>>result=newArrayList<>();for(inti=0;i<nums.length-3;i++){if(i>0&&nums[i]==nums[i-1]){continue;}for(intj=i+1;j<nums.length-2;j++){if(j>i+1&&nums[j]==nums[j-1]){continue;}intleft=j+1;intright=nums.length-1;while(left<right){longsum=(long)nums[i]+nums[j]+nums[left]+nums[right];if(sum==target){result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(left<right&&nums[left]==nums[left+1]){left++;}while(left<right&&nums[right]==nums[right-1]){right--;}left++;right--;}elseif(sum<target){left++;}else{right--;}}}}returnresult;}}```解析：首先對(duì)數(shù)組進(jìn)行排序，以便使用雙指針?lè)?。使用四層循環(huán)，其中前兩層循環(huán)用于固定前兩個(gè)數(shù)，后兩層循環(huán)使用雙指針?lè)ㄕ业胶髢蓚€(gè)數(shù)。在內(nèi)層循環(huán)中，使用雙指針?lè)ㄕ业綕M足條件的四個(gè)數(shù)，并避免重復(fù)。最后返回結(jié)果列表。4.答案：```javapublicclassTrieNode{publicTrieNode[]children;publicbooleanisEndOfWord;publicTrieNode(){children=newTrieNode[26];isEndOfWord=false;}}publicclassTrie{privateTrieNoderoot;publicTrie(){root=newTrieNode();}publicvoidinsert(Stringword){TrieNodecurrent=root;for(charc:word.toCharArray()){intindex=c-'a';if(current.children[index]==null){current.children[index]=newTrieNode();}current=current.children[index];}current.isEndOfWord=true;}publicbooleansearch(Stringword){TrieNodecurrent=root;for(charc:word.toCharArray()){intindex=c-'a';if(current.children[index]==null){returnfalse;}current=current.children[index];}returncurrent.isEndOfWord;}publicbooleanstartsWith(Stringprefix){TrieNodecurrent=root;for(charc:prefix.toCharArray()){intindex=c-'a';if(current.children[index]==null){returnfalse;}current=current.children[index];}returntrue;}}```解析：Trie（前綴樹）是一種用于檢索字符串?dāng)?shù)據(jù)集中的鍵的有序樹數(shù)據(jù)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含一個(gè)字符和一個(gè)指向子節(jié)點(diǎn)的數(shù)組。`insert`方法將一個(gè)單詞插入到Trie中。`search`方法檢查Trie中是否存在一個(gè)單詞。`startsWith`方法檢查Trie中是否存在一個(gè)以給定前綴開頭的單詞。二、算法題1.答案：```javapublicclassSolution{publicvoidquickSort(int[]nums){quickSort(nums,0,nums.length-1);}privatevoidquickSort(int[]nums,intleft,intright){if(left<right){intpivotIndex=partition(nums,left,right);quickSort(nums,left,pivotIndex-1);quickSort(nums,pivotIndex+1,right);}}privateintpartition(int[]nums,intleft,intright){intpivot=nums[right];inti=left-1;for(intj=left;j<right;j++){if(nums[j]<=pivot){i++;swap(nums,i,j);}}swap(nums,i+1,right);returni+1;}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}```解析：快速排序是一種分治算法。選擇一個(gè)基準(zhǔn)元素（pivot），將數(shù)組分為兩部分，一部分小于等于基準(zhǔn)元素，另一部分大于等于基準(zhǔn)元素。遞歸地對(duì)兩部分進(jìn)行快速排序。分區(qū)操作通過(guò)交換元素實(shí)現(xiàn)。2.答案：```javapublicclassSolution{publicintsearch(int[]nums,inttarget){intleft=0;intright=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]==target){returnmid;}elseif(nums[mid]<target){left=mid+1;}else{right=mid-1;}}return-1;}}```解析：二分查找是一種在有序數(shù)組中查找特定元素的算法。每次將查找范圍縮小一半。如果中間元素等于目標(biāo)值，返回其索引。如果中間元素小于目標(biāo)值，則在右半部分繼續(xù)查找。如果中間元素大于目標(biāo)值，則在左半部分繼續(xù)查找。如果查找范圍為空，返回-1。3.答案：```javapublicclassSolution{publicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurrent=head;while(current!=null){ListNodenext=current.next;current.next=prev;prev=current;current=next;}returnprev;}}```解析：鏈表反轉(zhuǎn)可以通過(guò)迭代實(shí)現(xiàn)。使用三個(gè)指針：prev，current和next。初始時(shí)，prev為null，current為head。在每次迭代中，將current的next指向prev，然后移動(dòng)prev和current。最終，prev將指向反轉(zhuǎn)后的鏈表的頭節(jié)點(diǎn)。4.答案：```javapublicclassSolution{publicListNodemergeTwoLists(ListNodel1,ListNodel2){ListNodedummy=newListNode(0);ListNodecurrent=dummy;while(l1!=null&&l2!=null){if(l1.val<=l2.val){current.next=l1;l1=l1.next;}else{current.next=l2;l2=l2.next;}current=current.next;}if(l1!=null){current.next=l1;}else{current.next=l2;}returndummy.next;}}```解析：合并兩個(gè)有序鏈表可以通過(guò)迭代實(shí)現(xiàn)。使用一個(gè)虛擬頭節(jié)點(diǎn)dummy，方便操作。使用一個(gè)指針current指向dummy。在每次迭代中，比較l1和l2的當(dāng)前節(jié)點(diǎn)的值，將較小的節(jié)點(diǎn)連接到current的next，并移動(dòng)相應(yīng)的指針。最后，將剩余的鏈表連接到current的next。返回dummy的next作為合并后的鏈表的頭節(jié)點(diǎn)。三、系統(tǒng)設(shè)計(jì)題1.答案：```javaimportjava.util.LinkedHashMap;importjava.util.Map;publicclassLRUCache{privatefinalintcapacity;privatefinalMap<String,String>cache;publicLRUCache(intcapacity){this.capacity=capacity;this.cache=newLinkedHashMap<String,String>(capacity,0.75f,true){@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<String,String>eldest){returnsize()>LRUCache.this.capacity;}};}publicvoidput(Stringurl,Stringvalue){cache.put(url,value);}publicStringget(Stringurl){returncache.getOrDefault(url,"-1");}}```解析：使用LinkedHashMap實(shí)現(xiàn)LRU緩存。LinkedHashMap支持按訪問(wèn)順序遍歷。重寫`removeEldestEntry`方法，當(dāng)緩存容量超過(guò)限制時(shí)，刪除最久未使用的元素。`put`方法將URL和值插入緩存。`get`方法返回緩存中URL對(duì)應(yīng)的值，如果沒(méi)有緩存則返回-1。2.答案：```javapublicclassMessageQueue{privatefinalLinkedList<String>queue;publicMessageQueue(){queue=newLinkedList<>();}publicvoidenqueue(Stringmessage){queue.addLast(message);}publicStringdequeue(){if(queue.isEmpty()){thrownewIllegalStateException("Queueisempty");}returnqueue.removeFirst();}}```解析：使用LinkedList實(shí)現(xiàn)FIFO隊(duì)列。`enqueue`方法將消息加入隊(duì)列尾部。`dequeue`方法返回隊(duì)列頭部消息并從隊(duì)列中刪除。如果隊(duì)列為空，拋出異常。四、數(shù)據(jù)庫(kù)題1.答案：```sql--查詢每個(gè)部門的平均工資SELECTDepartment,AVG(Salary)ASAverageSalaryFROMEmployeesGROUPBYDepartment;--查詢只有工資高于平均工資的員工的名字和部門SELECTName,Depar