软件开发工程师算法设计面试题及答案

2026年软件开发工程师算法设计面试题及答案一、编程实现题（共3题，每题20分）1.题目（20分）：设计一个函数，接收一个非空字符串列表`words`和一个整数`k`，返回所有长度至少为`k`的单词的按字典序排序后的列表。要求时间复杂度尽可能低。示例输入：pythonwords=["apple","banana","cherry","date","elderberry"],k=5示例输出：python["apple","banana","cherry","elderberry"]答案：pythondeffilter_and_sort(words,k):returnsorted([wordforwordinwordsiflen(word)>=k])示例调用words=["apple","banana","cherry","date","elderberry"]k=5print(filter_and_sort(words,k))#输出:['apple','banana','cherry','elderberry']解析：-使用列表推导式筛选出长度至少为`k`的单词。-使用`sorted()`函数按字典序排序。-时间复杂度：`O(nlogn)`，其中`n`是`words`的长度。2.题目（20分）：设计一个函数，接收一个链表的头节点`head`，返回一个包含链表所有节点值的数组。假设链表节点定义如下：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示例调用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`循环遍历链表，将节点值逐个添加到数组中。-时间复杂度：`O(n)`，其中`n`是链表长度。3.题目（20分）：设计一个函数，接收一个整数`n`，返回一个包含所有`n`阶杨辉三角的二维数组。杨辉三角的第`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示例调用n=5print(generate_pascals_triangle(n))解析：-使用嵌套循环生成杨辉三角：-外层循环遍历每一行。-内层循环计算当前行的非首尾元素（`row[j]=triangle[i-1][j-1]+triangle[i-1][j]`）。-时间复杂度：`O(n^2)`。二、算法设计题（共3题，每题25分）1.题目（25分）：设计一个算法，将一个非降序排列的整数数组`nums`和一个目标整数`target`，返回`target`在数组中的第一个出现位置。如果不存在，返回`-1`。要求时间复杂度尽可能低。示例输入：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#继续向左查找elifnums[mid]<target:left=mid+1else:right=mid-1returnresult示例调用nums=[1,2,4,4,4,5,6]target=4print(find_first_occurrence(nums,target))#输出:2解析：-使用二分查找的变种：当找到`target`时，继续向左查找第一个出现的位置。-时间复杂度：`O(logn)`。2.题目（25分）：设计一个算法，给定一个字符串`s`，返回`s`中最长回文子串的长度。假设`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示例调用s="babad"print(longest_palindrome(s))#输出:3解析：-使用动态规划（DP）解决：-`dp[i][j]`表示`s[i..j]`是否为回文。-初始化：单个字符是回文，相邻相同字符也是回文。-递推：当`s[i]==s[j]`且`s[i+1..j-1]`是回文时，`s[i..j]`是回文。-时间复杂度：`O(n^2)`。3.题目（25分）：设计一个算法，给定一个正整数`n`，返回`n`的二进制表示中`1`的个数。要求不使用内置函数。示例输入：pythonn=11示例输出：python3答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount示例调用n=11print(count_bits(n))#输出:3解析：-使用位运算：-`n&1`获取最低位的`0`或`1`。-`n>>=1`右移一位，继续处理。-时间复杂度：`O(logn)`。三、系统设计题（共1题，50分）1.题目（50分）：设计一个简单的URL短链接系统。系统需要支持以下功能：1.接收一个长URL，生成一个短URL（例如`/abc123`）。2.缓存长URL和短URL的映射关系，以便快速查询。3.支持通过短URL查询对应的长URL。要求：-短URL应该全局唯一且尽量短。-系统需要支持高并发访问。答案：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()转换为Base64并截取前6位short_key=urlsafe_b64encode(hash_bytes).decode()[:6]确保短URL全局唯一（可添加随机数或时间戳）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")示例调用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