程序设计岗位面试要点及参考答案

2026年程序设计岗位面试要点及参考答案一、编程基础（5题，每题10分，共50分）1.题目（10分）：编写一个函数，实现将任意进制数（2-16进制）转换为十进制数。输入参数包括数字字符串和进制数，输出为十进制整数。假设输入合法，进制数不超过16。参考答案：pythondefbase_to_decimal(num_str,base):ifbase<2orbase>16:return"Invalidbase"digits="0123456789ABCDEF"decimal=0fori,charinenumerate(reversed(num_str)):value=digits.index(char.upper())decimal+=value(basei)returndecimal示例：将"1A3"（16进制）转换为十进制print(base_to_decimal("1A3",16))#输出：419解析：-从右到左遍历数字字符串，每个字符通过`digits`映射为对应数值（A-F转为10-15）。-使用`basei`计算当前位的权重，累加得到十进制结果。-异常处理：检查进制是否在2-16范围内。2.题目（10分）：实现一个快速排序算法，要求不使用递归，采用迭代方式（使用栈模拟递归）。输入一个整数数组，输出排序后的数组。参考答案：pythondefquick_sort_iterative(arr):ifnotarr:return[]stack=[(0,len(arr)-1)]whilestack:start,end=stack.pop()ifstart>=end:continuepivot=arr[end]left,right=start,end-1whileleft<=right:whileleft<=rightandarr[left]<=pivot:left+=1whileleft<=rightandarr[right]>=pivot:right-=1ifleft<right:arr[left],arr[right]=arr[right],arr[left]arr[left],arr[end]=arr[end],arr[left]stack.append((start,left-1))stack.append((left+1,end))returnarr示例print(quick_sort_iterative([3,1,4,1,5,9,2,6]))#输出：[1,1,2,3,4,5,6,9]解析：-使用栈记录当前需要排序的子数组范围。-模拟递归的分区操作：选择`end`为基准值，左右指针向中间移动，将小于基准的值移到左侧，大于基准的值移到右侧。-分区后，将子数组范围继续入栈处理，直到栈为空。3.题目（10分）：编写一个函数，检查一个字符串是否为“回文串”（忽略大小写和空格）。例如，"Aman,aplan,acanal:Panama"为回文串。参考答案：pythondefis_palindrome(s):s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]示例print(is_palindrome("Aman,aplan,acanal:Panama"))#输出：Trueprint(is_palindrome("raceacar"))#输出：False解析：-去除非字母数字字符，并统一转为小写。-判断处理后的字符串是否与反转字符串相同。4.题目（10分）：实现一个LRU（最近最少使用）缓存，要求支持`get`和`put`操作。容量为3，超出时删除最久未使用的元素。参考答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)示例lru=LRUCache(3)lru.put(1,1)lru.put(2,2)lru.put(3,3)print(lru.get(1))#输出：1lru.put(4,4)#删除key=2print(lru.get(2))#输出：-1解析：-使用字典`cache`存储键值对，列表`order`记录访问顺序。-`get`操作将键移到末尾，表示最近访问。-`put`操作若键存在则更新顺序，若超出容量则删除最久未使用的元素（`order[0]`）。5.题目（10分）：实现一个二叉树的层序遍历（广度优先遍历），要求返回列表形式，每层从左到右。参考答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevel_order(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult示例root=TreeNode(3,TreeNode(9),TreeNode(20,TreeNode(15),TreeNode(7)))print(level_order(root))#输出：[[3],[9,20],[15,7]]解析：-使用队列实现BFS，初始化时将根节点入队。-每次处理当前层的所有节点，将其子节点入队，并将当前层结果添加到`result`中。二、算法与数据结构（5题，每题10分，共50分）6.题目（10分）：给定一个整数数组，返回所有和为target的三元组（不重复）。例如，输入`[-1,0,1,2]`，target=0，输出`[[-1,0,1],[-1,2,1]]`。参考答案：pythondefthree_sum(nums,target):nums.sort()result=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnresult示例print(three_sum([-1,0,1,2],0))#输出：[[-1,0,1],[-1,2,1]]解析：-先排序数组，避免重复解。-固定第一个数，使用双指针（left,right）寻找另外两个数，使三数之和为target。-若找到解，跳过重复值继续查找；若总和小于target，left右移；否则right左移。7.题目（10分）：实现一个无重复字符的最长子串，返回其长度。例如，输入"abcabcbb"，输出"abc"（长度3）。参考答案：pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forright,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1char_map[char]=rightmax_len=max(max_len,right-left+1)returnmax_len示例print(length_of_longest_substring("abcabcbb"))#输出：3解析：-使用哈希表记录每个字符的最新位置。-维护一个滑动窗口`[left,right]`，若右指针遇到重复字符且位置在窗口内，则将左指针移动到重复字符的下一个位置。-每次更新最大长度。8.题目（10分）：给定一个非空二叉树，返回其最大深度（即根节点到最远叶子节点的最长路径上的节点数）。参考答案：pythondefmax_depth(root):ifnotroot:return0return1+max(max_depth(root.left),max_depth(root.right))示例构建二叉树：3/\920/\157root=TreeNode(3,TreeNode(9),TreeNode(20,TreeNode(15),TreeNode(7)))print(max_depth(root))#输出：3解析：-递归计算左子树和右子树的最大深度，取较大值加1（当前节点）。-基本情况：空树深度为0。9.题目（10分）：实现一个二分查找算法，输入有序数组和一个目标值，返回目标值的索引（若不存在则返回-1）。参考答案：pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1示例print(binary_search([1,2,3,4,5],3))#输出：2print(binary_search([1,2,3,4,5],6))#输出：-1解析：-初始化左右指针，每次取中间值`mid`比较：-若`nums[mid]==target`，返回`mid`。-若`nums[mid]<target`，搜索右半部分。-若`nums[mid]>target`，搜索左半部分。-若未找到，返回-1。10.题目（10分）：给定一个链表，反转其节点，并返回新链表头。参考答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev,current=None,headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev示例输入：1->2->3->4->5输出：5->4->3->2->1head=ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))new_head=reverse_list(head)whilenew_head:print(new_head.val,end="->")new_head=new_head.next解析：-使用三个指针：`prev`（初始为None），`current`（初始为head），`next_node`临时存储下一个节点。-每次将`current.next`指向前一个节点`prev`，然后移动指针。-最终`prev`成为新头节点。三、系统设计（3题，每题15分，共45分）11.题目（15分）：设计一个简单的短链接系统（如tinyURL）。要求：-输入任意URL，返回短链接（如/abc123）。-输入短链接，能反查回原始URL。-支持高并发访问。参考答案：-数据结构：-使用哈希表（内存+Redis）存储`短码<->原始URL`映射。-短码使用自增ID或随机生成（如6位base62：a-z,A-Z,0-9）。-流程：1.输入URL，生成短码（如`id_to_base62(自增ID)`），存入哈希表。2.返回短链接（`/短码`）。3.反查时，从短码解析ID，查哈希表获取原始URL。-高并发处理：-使用Redis分布式锁避免短码冲突。-基于内存+持久化（如RocksDB）保证数据一致性。12.题目（15分）：设计一个消息队列系统