2025年信息通信科技集團(tuán)招聘中的算法題解析#2025年信息通信科技集團(tuán)招聘算法題解析一、編程實(shí)現(xiàn)題（3題，每題15分）題目1（15分）問題描述：實(shí)現(xiàn)一個(gè)函數(shù)，接收一個(gè)非空字符串?dāng)?shù)組，返回一個(gè)新數(shù)組，其中包含原數(shù)組中所有出現(xiàn)超過一次的字符串，并按出現(xiàn)次數(shù)降序排列。如果出現(xiàn)次數(shù)相同，則按字符串升序排列。示例：python輸入：["apple","banana","apple","orange","banana","banana"]輸出：["banana","apple"]要求：1.不使用任何外部庫(kù)。2.時(shí)間復(fù)雜度盡量?jī)?yōu)化。代碼實(shí)現(xiàn)：pythondeffind_repeated_strings(strings):#你的代碼實(shí)現(xiàn)pass題目2（15分）問題描述：實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持以下操作：1.`add(num)`：添加一個(gè)數(shù)字到數(shù)據(jù)結(jié)構(gòu)中。2.`find(k)`：返回小于等于k的最大數(shù)字的索引，如果不存在則返回-1。示例：pythonobj=Solution()obj.add(1)obj.add(3)obj.add(5)obj.find(4)#返回2obj.find(7)#返回3要求：1.`add`操作的時(shí)間復(fù)雜度為O(logn)。2.`find`操作的時(shí)間復(fù)雜度為O(logn)。代碼實(shí)現(xiàn)：pythonclassSolution:def__init__(self):#你的代碼實(shí)現(xiàn)passdefadd(self,num):#你的代碼實(shí)現(xiàn)passdeffind(self,k):#你的代碼實(shí)現(xiàn)pass題目3（15分）問題描述：給定一個(gè)整數(shù)數(shù)組，返回所有可能的子集。子集的順序不重要，但每個(gè)子集內(nèi)部的順序不能改變。示例：python輸入：[1,2,3]輸出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]要求：1.不使用任何外部庫(kù)。2.使用回溯算法實(shí)現(xiàn)。代碼實(shí)現(xiàn)：pythondefsubsets(nums):#你的代碼實(shí)現(xiàn)pass二、算法分析題（2題，每題20分）題目4（20分）問題描述：給定一個(gè)包含n個(gè)點(diǎn)的無(wú)向圖，每個(gè)點(diǎn)都有一個(gè)唯一的編號(hào)（從0到n-1）。圖以鄰接矩陣的形式給出，其中`graph[i][j]`為1表示點(diǎn)i和點(diǎn)j之間有邊，為0表示沒有邊。設(shè)計(jì)一個(gè)算法，找到圖中所有連通分量的大小。示例：python輸入：graph=[[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]輸出：[2,2,2,2]要求：1.解釋你的算法思路。2.分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。題目5（20分）問題描述：給定一個(gè)字符串`s`和一個(gè)字符集`t`，找到`s`中所有子串的最小字典序。如果有多個(gè)子串具有相同的最小字典序，選擇最長(zhǎng)的子串。示例：python輸入：s="abab",t="abc"輸出："aab"要求：1.解釋你的算法思路。2.分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。三、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題（1題，25分）題目6（25分）問題描述：設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持以下操作：1.`insert(key,value)`：插入一個(gè)鍵值對(duì)，如果鍵已存在，則更新其值。2.`delete(key)`：刪除一個(gè)鍵，如果鍵不存在，則不進(jìn)行任何操作。3.`get(key)`：返回鍵對(duì)應(yīng)的值，如果鍵不存在，則返回-1。4.`max_key()`：返回當(dāng)前數(shù)據(jù)結(jié)構(gòu)中鍵的最大值，如果數(shù)據(jù)結(jié)構(gòu)為空，則返回-1。要求：1.解釋你的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。2.描述每個(gè)操作的時(shí)間復(fù)雜度。設(shè)計(jì)思路：plaintext你的設(shè)計(jì)思路答案題目1答案（15分）pythondeffind_repeated_strings(strings):fromcollectionsimportCountercount=Counter(strings)repeated=[sfors,cntincount.items()ifcnt>1]repeated.sort(key=lambdax:(-count[x],x))returnrepeated題目2答案（15分）pythonclassSolution:def__init__(self):self.sorted=[]defadd(self,num):frombisectimportinsortinsort(self.sorted,num)deffind(self,k):frombisectimportbisect_rightidx=bisect_right(self.sorted,k)returnidx-1ifidx>0else-1題目3答案（15分）pythondefsubsets(nums):result=[]subset=[]defbacktrack(start):result.append(subset.copy())foriinrange(start,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult題目4答案（20分）算法思路：使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）來(lái)遍歷圖，找到所有連通分量。時(shí)間復(fù)雜度：O(n+m)，其中n是點(diǎn)的數(shù)量，m是邊的數(shù)量?？臻g復(fù)雜度：O(n)，用于存儲(chǔ)訪問標(biāo)記和遞歸棧。pythondeffind_connected_components(graph):n=len(graph)visited=[False]*ncomponents=[]defdfs(node,component):stack=[node]whilestack:v=stack.pop()ifnotvisited[v]:visited[v]=Truecomponent.append(v)foriinrange(n):ifgraph[v][i]==1andnotvisited[i]:stack.append(i)foriinrange(n):ifnotvisited[i]:component=[]dfs(i,component)components.append(component)returncomponents題目5答案（20分）算法思路：使用滑動(dòng)窗口的方法，維護(hù)一個(gè)窗口，窗口內(nèi)的子串字典序最小，且窗口盡可能大。時(shí)間復(fù)雜度：O(n)，其中n是字符串`s`的長(zhǎng)度?？臻g復(fù)雜度：O(1)，只需要常數(shù)級(jí)的額外空間。pythondeffind_min_lexicographical_substring(s,t):fromcollectionsimportCountert_count=Counter(t)min_substring=""min_len=float('inf')left=0matched=0window_count=Counter()forrightinrange(len(s)):char=s[right]ifcharint_count:window_count[char]+=1ifwindow_count[char]==t_count[char]:matched+=1whilematched==len(t_count):current_len=right-left+1ifcurrent_len<min_len:min_len=current_lenmin_substring=s[left:right+1]left_char=s[left]ifleft_charint_count:window_count[left_char]-=1ifwindow_count[left_char]<t_count[left_char]:matched-=1left+=1returnmin_substringifmin_len!=float('inf')else""題目6答案（25分）設(shè)計(jì)思路：使用哈希表存儲(chǔ)鍵值對(duì)，同時(shí)維護(hù)一個(gè)最大堆來(lái)快速找到最大鍵。時(shí)間復(fù)雜度：-`insert`和`delete`操作為O(logn)。-`get`操作為O(1)。-`max_key`操作為O(1)。pythonimportheapqclassCustomDataStructure:def__init__(self):self.map={}self.max_heap=[]definsert(self,key,value):ifkeyinself.map:self.map[key]=value#更新最大堆self.max_heap=[(v,k)fork,vinself.map.items()]heapq.heapify(self.max_heap)else:self.map[key]=valueheapq.heappush(self.max_heap,(-value,key))defdelete(self,key):ifkeyinself.map:delself.map[k