1、字符串反转，不能使用内置reverse方法

核心：手动遍历，从后往前拼接。

def reverse_str(s: str) -> str: res = [] # 倒序遍历 for i in range(len(s)-1, -1, -1): res.append(s[i]) return "".join(res) # test print(reverse_str("abcdef")) # fedcba

Java版本思路：转char数组，首尾交换。

public static String reverseStr(String s){ char[] arr = s.toCharArray(); left = 0; right = arr.length-1; while(left < right){ char tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } return new String(arr); }

禁止使用s[::-1]属于Python切片语法糖，如果面试明确不让用切片，则只能循环拼接。

2、手写二分查找 + 边界条件处理

前提：有序数组，找目标值target下标，找不到返回-1。

def binary_search(nums, target): left = 0 right = len(nums) - 1 # 闭区间 [left, right] while left <= right: mid = left + (right - left) // 2 # 防止溢出，不要写 (left+right)//2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1

边界条件说明

1. 区间定义：上面是闭区间[left,right]，循环条件left <= right；
   如果写成左闭右开[left, right)，则right = len(nums)，循环条件left < right，更新right=mid。区间定义要全程统一，最容易出错。
2. mid计算：left + (right‑left)//2避免left+right数值溢出；
3. 边界case：空数组、目标小于全部元素、目标大于全部元素、数组只有一个元素。

变体：查找左边界、右边界，比如有序数组有重复数字找第一个出现位置。

3、两数之和：数组，找和为target的两个下标

题目：nums = [2,7,11,15], target=9 → 返回[0,1]

方法1：暴力双层循环

def two_sum_brute(nums, target): n = len(nums) for i in range(n): for j in range(i+1, n): if nums[i] + nums[j] == target: return [i,j] return []

• 时间复杂度：O(n2)O(n^2)O(n2)
• 空间复杂度：(O(1))(O(1))(O(1))
  缺点：大数据量很慢。

方法2：哈希表（最优）

def two_sum_hash(nums, target): hashmap = dict() for idx, val in enumerate(nums): need = target - val if need in hashmap: return [hashmap[need], idx] hashmap[val] = idx return []

• 时间复杂度：(O(n))(O(n))(O(n))，一次遍历
• 空间复杂度：(O(n))(O(n))(O(n))，哈希表存储元素

⚠️注意：不能先全部put进map再遍历，会出现自己和自己匹配；边遍历边存可以规避。
注意：数组不一定有序，所以不能直接双指针；双指针方案需要先排序，会丢失原始下标。

4、判断单链表是否有环；找环入口节点

链表节点定义

class ListNode: def __init__(self, x): self.val = x self.next = None

判断是否有环：快慢指针（龟兔赛跑）

快指针每次走2步，慢指针每次走1步；如果有环，快慢一定会相遇；快指针走到None则无环。

def has_cycle(head: ListNode): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

找到环入口节点

相遇之后，慢指针留在相遇点；头指针新建一个p从head出发，p和slow每次各走一步，相遇点就是环入口。

def detect_cycle(head: ListNode): slow = fast = head has_loop = False while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: has_loop = True break if not has_loop: return None p = head while p != slow: p = p.next slow = slow.next return p

原理数学推导：设头到环入口距离a，环长b；相遇时快比慢多走n圈，数学推导可得 a = (n‑1)*b + (b‑相遇点距离)。

5、两个栈实现队列；两个队列实现栈

5.1 两个栈实现队列

栈：后进先出；队列：先进先出。
思路：stack1负责入队；stack2负责出队。出队时如果stack2为空，把stack1全部弹入stack2。

class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, x): self.stack1.append(x) def pop(self): if not self.stack2: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop() def peek(self): if not self.stack2: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2[-1] def empty(self): return len(self.stack1)==0 and len(self.stack2)==0

5.2 两个队列实现栈

队列q1存元素；q2做辅助。push直接往q1；pop时把q1除最后一个全部挪q2，弹出最后一个，再交换q1 q2。

from collections import deque class MyStack: def __init__(self): self.q1 = deque() self.q2 = deque() def push(self, x): self.q1.append(x) def pop(self): while len(self.q1) > 1: self.q2.append(self.q1.popleft()) res = self.q1.popleft() self.q1, self.q2 = self.q2, self.q1 return res def top(self): while len(self.q1) > 1: self.q2.append(self.q1.popleft()) res = self.q1[0] self.q2.append(self.q1.popleft()) self.q1, self.q2 = self.q2, self.q1 return res def empty(self): return len(self.q1) == 0

6、快速排序 & 归并排序对比

稳定：相等元素相对顺序排序后不变。

• 快排：不稳定；数据有序时退化；实际工程最常用。
• 归并排序：稳定，需要额外内存；适合链表排序、外部大文件排序。

简易快排Python示例（非原地）

def quick_sort(arr): if len(arr) <=1: return arr pivot = arr[len(arr)//2] left = [x for x in arr if x < pivot] mid = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left)+mid+quick_sort(right)

归并排序

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr)//2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left,right) def merge(a,b): res = [] i=j=0 while i<len(a) and j<len(b): if a[i] <= b[j]: res.append(a[i]) i+=1 else: res.append(b[j]) j+=1 res.extend(a[i:]) res.extend(b[j:]) return res

7、最长无重复字符子串长度

滑动窗口，双指针 + set。s=“abcabcbb” →输出3。

def length_of_longest_substring(s: str) -> int: char_set = set() left = 0 max_len = 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left += 1 char_set.add(s[right]) max_len = max(max_len, right-left+1) return max_len

时间：(O(n))(O(n))(O(n))；空间：最多字符集大小。

8、两个大数字符串相加，不能直接转int

例如 num1=“12345678901234567890”, num2=“98765432109876543210”，输出字符串结果。
思路：从尾部逐位相加，维护进位carry。

def add_str(num1: str, num2: str) -> str: i = len(num1)-1 j = len(num2)-1 carry = 0 res = [] while i >=0 or j >=0 or carry>0: a = int(num1[i]) if i>=0 else 0 b = int(num2[j]) if j>=0 else 0 total = a + b + carry res.append(str(total % 10)) carry = total // 10 i -=1 j -=1 return "".join(reversed(res)) print(add_str("123","4567")) # "4690"

9、线程安全单例模式（Java DCL双重检查锁）

Python GIL下多线程写单例仍会有初始化竞争；经典面试考Java DCL。

public class Singleton { // volatile 禁止指令重排 private static volatile Singleton instance; private Singleton(){} public static Singleton getInstance(){ if(instance == null){ // 第一次检查 synchronized (Singleton.class){ if(instance == null){ //第二次检查 instance = new Singleton(); } } } return instance; } }

关键点：volatile，防止new对象时指令重排，出现半初始化对象。

Python单例简单写法：

import threading class Singleton: _instance = None _lock = threading.Lock() def __new__(cls): if cls._instance is None: with cls._lock: if cls._instance is None: cls._instance = super().__new__(cls) return cls._instance

10、装饰器；统计函数运行时间装饰器

装饰器：Python语法，在不修改原函数代码前提下，对函数做增强（埋点、计时、日志、鉴权），本质高阶函数。

import time def cost_time(func): def wrapper(*args, **kwargs): start = time.time() ret = func(*args, **kwargs) end = time.time() print(f"函数 {func.__name__} 耗时 {end-start:.4f} s") return ret return wrapper # 使用 @cost_time def demo(n): s=0 for i in range(n): s+=i return s demo(1000000)

如果需要保留原函数元信息，需要from functools import wraps，wrapper上加@wraps(func)。

11、面向对象三大特性；多态实现方式

三大特性：封装、继承、多态

1. 封装：把属性方法封装到类，对外隐藏内部实现，提供访问接口。
2. 继承：子类复用父类代码，扩展功能。
3. 多态：同一个行为，不同对象表现不同结果。

多态实现方式：

• Java：重写override；接口interface实现；抽象类abstract；父类引用指向子类对象。
• Python：鸭子类型（duck typing），不需要显式继承，只要有同名方法就可以多态调用。

12、Python深拷贝、浅拷贝区别

• 浅拷贝：拷贝对象第一层；内部嵌套可变对象，仍然共用引用。修改嵌套对象，新旧都会变。
  实现：copy.copy()；切片[:]；list/dict构造。
• 深拷贝：递归拷贝所有层级对象；完全独立，修改一方互不影响。
  实现：copy.deepcopy()。

示例：

import copy a = [1, [2,3]] b = copy.copy(a) #浅拷贝 c = copy.deepcopy(a) #深拷贝 a[1].append(4) print(b) # [1, [2,3,4]] 嵌套列表共享 print(c) # [1, [2,3]] 不受影响

不可变对象（int str tuple）深浅拷贝看不出差异。

13、数据库连接池，实现思路

数据库创建连接开销很大；连接池预创建一批连接，复用连接，避免频繁创建销毁。
实现思路：

1. 初始化创建一定数量数据库连接放入池子；维护空闲队列、活跃连接计数。
2. 获取连接：优先取空闲连接；达到最大连接数时阻塞等待或者抛异常。
3. 归还连接：不是close销毁，放回空闲队列。
4. 配置参数：最小空闲连接、最大连接数、最大等待时间、连接存活检测，回收坏连接。
   代表：Java HikariCP、Druid；Python DBUtils pool。

14、日志文件统计访问量最高Top10 IP

场景：日志很大，可能超过内存。

1. 小文件：全部读入，字典统计ip计数，排序取Top10。
2. 大文件（超出内存）：
   • step1：分桶（hash分片）：按ip hash打散输出到N个小文件；相同IP一定落在同一个分片文件。
   • step2：每个小文件单独统计top10；
   • step3：合并所有分片top10，全局排序输出最终Top10。>

   这是经典MapReduce思想；如果允许使用第三方：可以用Counter。

简易小文件版本：

from collections import Counter def top10_ip(file_path): cnt = Counter() with open(file_path,"r",encoding="utf8") as f: for line in f: ip = line.split()[0] cnt[ip] +=1 return cnt.most_common(10)

15、LRU缓存淘汰算法

LRU：最近最少使用；容量满的时候淘汰最久没有访问的数据。
要求：get (O(1))，put (O(1))。
实现：哈希表 + 双向链表；哈希存key映射链表节点；链表头部放最近访问，尾部放待淘汰。
Python可以借助collections.OrderedDict快速实现。

from collections import OrderedDict class LRUCache: def __init__(self, capacity:int): self.cap = capacity self.cache = OrderedDict() def get(self, key): if key not in self.cache: return -1 val = self.cache.pop(key) self.cache[key] = val #移到末尾代表最新访问 return val def put(self, key, value): if key in self.cache: self.cache.pop(key) else: if len(self.cache) >= self.cap: self.cache.popitem(last=False) #弹出头部，最久未使用 self.cache[key] = value

OrderedDict last=False FIFO弹出队首。手写双向链表版本面试也有可能要求。