2025年信息技術(shù)公司校園招聘面試技巧及模擬題詳解一、編程能力測試（共5題，每題10分，總分50分）題目1：字符串反轉(zhuǎn)題目描述：給定一個字符串`s`，請將其反轉(zhuǎn)并返回。例如，輸入`"hello"`，輸出`"olleh"`。要求：-不使用內(nèi)置的反轉(zhuǎn)函數(shù)-時間復(fù)雜度O(n)，空間復(fù)雜度O(1)參考答案：pythondefreverse_string(s:str)->str:result=[]forcharins:result.insert(0,char)return''.join(result)#優(yōu)化版：使用雙指針defreverse_string_optimized(s:str)->str:s_list=list(s)left,right=0,len(s)-1whileleft<right:s_list[left],s_list[right]=s_list[right],s_list[left]left+=1right-=1return''.join(s_list)題目2：合并兩個有序鏈表題目描述：將兩個有序鏈表合并為一個新的有序鏈表。例如，輸入`1->2->4`和`1->3->4`，合并后為`1->1->2->3->4->4`。要求：-鏈表節(jié)點定義見下方-時間復(fù)雜度O(m+n)，空間復(fù)雜度O(1)參考答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmerge_two_lists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next題目3：斐波那契數(shù)列題目描述：斐波那契數(shù)列定義如下：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)，請計算F(10)。要求：-不使用遞歸-時間復(fù)雜度O(n)，空間復(fù)雜度O(1)參考答案：pythondeffibonacci(n:int)->int:ifn==0:return0a,b=0,1for_inrange(2,n+1):a,b=b,a+breturnb題目4：二叉樹遍歷題目描述：給定一個二叉樹，請分別實現(xiàn)前序遍歷、中序遍歷和后序遍歷。要求：-遞歸和非遞歸兩種方式實現(xiàn)-樹節(jié)點定義見下方參考答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right#前序遍歷-遞歸defpreorder_recursive(root:TreeNode):result=[]defdfs(node):ifnotnode:returnresult.append(node.val)dfs(node.left)dfs(node.right)dfs(root)returnresult#前序遍歷-非遞歸defpreorder_iterative(root:TreeNode):ifnotroot:return[]result,stack=[],[root]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult題目5：動態(tài)規(guī)劃-最長遞增子序列題目描述：給定一個整數(shù)數(shù)組，請找到其中最長的嚴格遞增子序列的長度。例如，輸入`[10,9,2,5,3,7,101,18]`，輸出`4`（子序列為`[2,5,7,101]`）。要求：-時間復(fù)雜度O(nlogn)-時間復(fù)雜度O(n)參考答案：python#方法一：二分查找，時間復(fù)雜度O(nlogn)deflength_of_LIS(nums):ifnotnums:return0tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)#方法二：動態(tài)規(guī)劃，時間復(fù)雜度O(n^2)deflength_of_LIS_dp(nums):ifnotnums:return0dp=[1]*len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[j]<nums[i]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)二、算法設(shè)計題（共3題，每題15分，總分45分）題目1：LRU緩存機制題目描述：設(shè)計一個LRU（最近最少使用）緩存機制。它應(yīng)該支持以下操作：-`get(key)`：獲取鍵`key`對應(yīng)的值，如果鍵不存在返回-1。-`put(key,value)`：向緩存中插入一個鍵值對。如果鍵已經(jīng)存在，則更新其值；如果緩存已滿，則刪除最久未使用的鍵。要求：-使用哈希表和雙向鏈表實現(xiàn)-`get`和`put`操作的時間復(fù)雜度為O(1)參考答案：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres題目2：N皇后問題題目描述：給定一個整數(shù)`n`，返回所有不同的`n`皇后問題的解決方案。每個解決方案包含一個明確的`n`皇后放置方式，其中`'Q'`和`'.'`分別代表一個皇后和一個空位。要求：-回溯算法實現(xiàn)-時間復(fù)雜度盡可能低參考答案：pythondefsolve_n_queens(n):defbacktrack(row,diagonals,anti_diagonals,cols,state):ifrow==n:result.append(state.copy())returnforcolinrange(n):diag=row-colanti_diag=row+colif(colincolsordiagindiagonalsoranti_diaginanti_diagonals):continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state.append(["."*col+"Q"+"."*(n-col-1)])backtrack(row+1,diagonals,anti_diagonals,cols,state)cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)state.pop()result=[]backtrack(0,set(),set(),set(),[])returnresult題目3：單詞搜索題目描述：給定一個`mxn`的網(wǎng)格和一個單詞列表，找出網(wǎng)格中是否存在一條路徑，使得該路徑可以構(gòu)成一個給定的單詞。路徑可以從網(wǎng)格中的任意格子開始，每次只能移動到相鄰的格子（上、下、左、右）。要求：-回溯算法實現(xiàn)-時間復(fù)雜度盡可能低參考答案：pythondefexist(board,word):ifnotboard:returnFalserows,cols=len(board),len(board[0])visited=set()defdfs(r,c,index):ifindex==len(word):returnTrueif(r<0orc<0orr>=rowsorc>=colsor(r,c)invisitedorboard[r][c]!=word[index]):returnFalsevisited.add((r,c))res=(dfs(r+1,c,index+1)ordfs(r-1,c,index+1)ordfs(r,c+1,index+1)ordfs(r,c-1,index+1))visited.remove((r,c))returnresforiinrange(rows):forjinrange(cols):ifdfs(i,j,0):returnTruereturnFalse三、系統(tǒng)設(shè)計題（共2題，每題20分，總分40分）題目1：設(shè)計Twitter題目描述：設(shè)計一個Twitter類，實現(xiàn)以下功能：-`postTweet(userId,tweetId)`：用戶`userId`發(fā)布一條推文`tweetId`-`getFeed(userId,k)`：獲取用戶`userId`的最近`k`條推文，包括自己發(fā)布的和關(guān)注的人發(fā)布的-`follow(followerId,followeeId)`：用戶`followerId`關(guān)注用戶`followeeId`-`unfollow(followerId,followeeId)`：用戶`followerId`取消關(guān)注用戶`followeeId`要求：-`getFeed`操作時間復(fù)雜度盡可能低-使用合適的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)參考答案：pythonimportcollectionsimportheapqclassTwitter:def__init__(self):self.timestamp=0self.user_tweets=collections.defaultdict(list)#userId->[(timestamp,tweetId),...]self.followees=collections.defaultdict(set)#userId->setoffolloweeIdsdefpostTweet(self,userId:int,tweetId:int)->None:self.user_tweets[userId].append((self.timestamp,tweetId))self.timestamp+=1defgetFeed(self,userId:int,k:int)->List[int]:tweets=[]forfolloweeinself.followees[userId]:tweets.extend(self.user_tweets[followee][-k:])#Removeduplicatesandsortbytimestampunique_tweets=collections.OrderedDict()fortimestamp,tweetIdinsorted(tweets,key=lambdax:x[0],reverse=True):unique_tweets[tweetId]=timestampreturnlist(unique_tweets.keys())[:k]deffollow(self,followerId:int,followeeId:int)->None:iffollowerId==followeeId:returnself.followees[followerId].add(followeeId)defunfollow(self,followerId:int,followeeId:int)->None:self.followees[followerId].discard(followeeId)題目2：設(shè)計LRU緩存（鏈表版本）題目描述：實現(xiàn)一個LRU（最近最少使用）緩存機制。它應(yīng)該支持以下操作：-`get(key)`：獲取鍵`key`對應(yīng)的值，如果鍵不存在返回-1。-`put(key,value)`：向緩存中插入一個鍵值對。如果鍵已經(jīng)存在，則更新其值；如果緩存已滿，則刪除最久未使用的鍵。要求：-使用雙向鏈表和哈希表實現(xiàn)-`get`和`put`操作的時間復(fù)雜度為O(1)參考答案：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres四、數(shù)據(jù)庫設(shè)計題（共1題，20分）題目1：設(shè)計社交媒體關(guān)注表題目描述：設(shè)計一個社交媒體的數(shù)據(jù)庫表來存儲用戶之間的關(guān)注關(guān)系。表應(yīng)支持以下功能：-添加關(guān)注關(guān)系-取消關(guān)注關(guān)系-查詢某個用戶關(guān)注的人-查詢某個用戶被多少人關(guān)注要求：-表結(jié)構(gòu)設(shè)計-SQL查詢示例參考答案：sql--創(chuàng)建關(guān)注表CREATETABLEFollow(follower_idINTNOTNULL,followee_idINTNOTNULL,follow_dateTIMESTAMPDEFAULTCURRENT_TIMESTAMP,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESUsers(id),FOREIGNKEY(followee_id)REFERENCESUsers(id));--添加關(guān)注關(guān)系--INSERTINTOFollow(follower_id,followee_i