2026年軟件開發(fā)工程師算法設(shè)計(jì)面試題及答案一、編程實(shí)現(xiàn)題（共3題，每題20分）1.題目（20分）：設(shè)計(jì)一個函數(shù)，接收一個非空字符串列表`words`和一個整數(shù)`k`，返回所有長度至少為`k`的單詞的按字典序排序后的列表。要求時間復(fù)雜度盡可能低。示例輸入：pythonwords=["apple","banana","cherry","date","elderberry"],k=5示例輸出：python["apple","banana","cherry","elderberry"]答案：pythondeffilter_and_sort(words,k):returnsorted([wordforwordinwordsiflen(word)>=k])示例調(diào)用words=["apple","banana","cherry","date","elderberry"]k=5print(filter_and_sort(words,k))#輸出:['apple','banana','cherry','elderberry']解析：-使用列表推導(dǎo)式篩選出長度至少為`k`的單詞。-使用`sorted()`函數(shù)按字典序排序。-時間復(fù)雜度：`O(nlogn)`，其中`n`是`words`的長度。2.題目（20分）：設(shè)計(jì)一個函數(shù)，接收一個鏈表的頭節(jié)點(diǎn)`head`，返回一個包含鏈表所有節(jié)點(diǎn)值的數(shù)組。假設(shè)鏈表節(jié)點(diǎn)定義如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next示例輸入：python鏈表:1->2->3head=ListNode(1,ListNode(2,ListNode(3)))示例輸出：python[1,2,3]答案：pythondeflist_to_array(head):array=[]current=headwhilecurrent:array.append(current.val)current=current.nextreturnarray示例調(diào)用classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nexthead=ListNode(1,ListNode(2,ListNode(3)))print(list_to_array(head))#輸出:[1,2,3]解析：-使用`while`循環(huán)遍歷鏈表，將節(jié)點(diǎn)值逐個添加到數(shù)組中。-時間復(fù)雜度：`O(n)`，其中`n`是鏈表長度。3.題目（20分）：設(shè)計(jì)一個函數(shù)，接收一個整數(shù)`n`，返回一個包含所有`n`階楊輝三角的二維數(shù)組。楊輝三角的第`i`行有`i+1`個元素。示例輸入：pythonn=5示例輸出：python[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]答案：pythondefgenerate_pascals_triangle(n):triangle=[]foriinrange(n):row=[1](i+1)forjinrange(1,i):row[j]=triangle[i-1][j-1]+triangle[i-1][j]triangle.append(row)returntriangle示例調(diào)用n=5print(generate_pascals_triangle(n))解析：-使用嵌套循環(huán)生成楊輝三角：-外層循環(huán)遍歷每一行。-內(nèi)層循環(huán)計(jì)算當(dāng)前行的非首尾元素（`row[j]=triangle[i-1][j-1]+triangle[i-1][j]`）。-時間復(fù)雜度：`O(n^2)`。二、算法設(shè)計(jì)題（共3題，每題25分）1.題目（25分）：設(shè)計(jì)一個算法，將一個非降序排列的整數(shù)數(shù)組`nums`和一個目標(biāo)整數(shù)`target`，返回`target`在數(shù)組中的第一個出現(xiàn)位置。如果不存在，返回`-1`。要求時間復(fù)雜度盡可能低。示例輸入：pythonnums=[1,2,4,4,4,5,6],target=4示例輸出：python2答案：pythondeffind_first_occurrence(nums,target):left,right=0,len(nums)-1result=-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:result=midright=mid-1#繼續(xù)向左查找elifnums[mid]<target:left=mid+1else:right=mid-1returnresult示例調(diào)用nums=[1,2,4,4,4,5,6]target=4print(find_first_occurrence(nums,target))#輸出:2解析：-使用二分查找的變種：當(dāng)找到`target`時，繼續(xù)向左查找第一個出現(xiàn)的位置。-時間復(fù)雜度：`O(logn)`。2.題目（25分）：設(shè)計(jì)一個算法，給定一個字符串`s`，返回`s`中最長回文子串的長度。假設(shè)`s`非空。示例輸入：pythons="babad"示例輸出：python3答案：pythondeflongest_palindrome(s):ifnots:return0n=len(s)dp=[[False]nfor_inrange(n)]max_len=1foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truemax_len=2forlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truemax_len=lengthreturnmax_len示例調(diào)用s="babad"print(longest_palindrome(s))#輸出:3解析：-使用動態(tài)規(guī)劃（DP）解決：-`dp[i][j]`表示`s[i..j]`是否為回文。-初始化：單個字符是回文，相鄰相同字符也是回文。-遞推：當(dāng)`s[i]==s[j]`且`s[i+1..j-1]`是回文時，`s[i..j]`是回文。-時間復(fù)雜度：`O(n^2)`。3.題目（25分）：設(shè)計(jì)一個算法，給定一個正整數(shù)`n`，返回`n`的二進(jìn)制表示中`1`的個數(shù)。要求不使用內(nèi)置函數(shù)。示例輸入：pythonn=11示例輸出：python3答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount示例調(diào)用n=11print(count_bits(n))#輸出:3解析：-使用位運(yùn)算：-`n&1`獲取最低位的`0`或`1`。-`n>>=1`右移一位，繼續(xù)處理。-時間復(fù)雜度：`O(logn)`。三、系統(tǒng)設(shè)計(jì)題（共1題，50分）1.題目（50分）：設(shè)計(jì)一個簡單的URL短鏈接系統(tǒng)。系統(tǒng)需要支持以下功能：1.接收一個長URL，生成一個短URL（例如`/abc123`）。2.緩存長URL和短URL的映射關(guān)系，以便快速查詢。3.支持通過短URL查詢對應(yīng)的長URL。要求：-短URL應(yīng)該全局唯一且盡量短。-系統(tǒng)需要支持高并發(fā)訪問。答案：pythonimporthashlibfrombase64importurlsafe_b64encodefromrandomimportrandintclassShortLinkSystem:def__init__(self):self.url_map={}#存儲短URL和長URL的映射self.base_url="/"def_generate_short_key(self,long_url):使用MD5加密長URLhash_obj=hashlib.md5(long_url.encode())hash_bytes=hash_obj.digest()轉(zhuǎn)換為Base64并截取前6位short_key=urlsafe_b64encode(hash_bytes).decode()[:6]確保短URL全局唯一（可添加隨機(jī)數(shù)或時間戳）whileshort_keyinself.url_map:short_key=urlsafe_b64encode(f"{short_key}{randint(1000,9999)}".encode()).decode()[:6]returnshort_keydefshorten_url(self,long_url):short_key=self._generate_short_key(long_url)short_url=f"{self.base_url}{short_key}"self.url_map[short_url]=long_urlreturnshort_urldefget_long_url(self,short_url):returnself.url_map.get(short_url,"URLnotfound")示例調(diào)用system=ShortLinkSystem()long_url="/article/12345"short_url=system.shorten_url(long_url)print(short_url)#輸出:/abc123print(system.get_long_url(short_url))#輸出:/article/12345解析：1