面试常见之手写系列：技术岗位的核心能力考察

在技术岗位的面试中，手写代码环节是评估候选人核心能力的重要环节。无论是算法题、数据结构实现，还是设计模式的应用，手写代码都能直观反映候选人的编码习惯、逻辑思维和问题解决能力。本文将从基础算法、数据结构、设计模式和实际场景四个维度，深入解析面试中常见的手写代码类型，并提供可操作的备考建议。

一、基础算法：排序与搜索的经典考察

1. 快速排序与归并排序

快速排序和归并排序是面试中最常考察的排序算法。快速排序通过分治思想，以一个基准值将数组分为两部分，递归排序；归并排序则通过自底向上的合并过程，确保时间复杂度稳定在O(n log n)。

示例代码（快速排序）：

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

考察点：递归实现、边界条件处理、时间复杂度分析。

2. 二分查找与变种

二分查找是高效搜索有序数组的经典算法，其变种（如查找第一个/最后一个等于目标值的元素）常用于考察候选人对边界条件的处理能力。

示例代码（查找第一个等于目标值的元素）：

def binary_search_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 继续向左搜索
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

考察点：循环条件、指针移动逻辑、结果更新策略。

二、数据结构：链表与树的深度操作

1. 链表反转与环检测

链表操作是面试中的高频考点，尤其是单链表的反转和环检测。链表反转考察候选人对指针操作的熟练度，环检测则涉及快慢指针的数学推导。

示例代码（链表反转）：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

考察点：指针操作顺序、边界条件（如空链表或单节点链表）。

2. 二叉树遍历与深度计算

二叉树的遍历（前序、中序、后序）和深度计算是基础中的基础。递归实现简单，但面试中常要求用迭代方式实现，以考察候选人对栈的使用能力。

示例代码（迭代中序遍历）：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def inorder_traversal(root):
    stack = []
    result = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

考察点：栈的使用、循环条件、节点访问顺序。

三、设计模式：单例与工厂模式的实现

1. 单例模式

单例模式确保一个类只有一个实例，并提供全局访问点。面试中常考察线程安全的实现方式，如双重检查锁定（DCL）。

示例代码（线程安全单例）：

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

考察点：线程同步机制、双重检查的必要性。

2. 工厂模式

工厂模式通过定义一个创建对象的接口，让子类决定实例化哪个类。面试中常考察简单工厂和工厂方法的区别。

示例代码（简单工厂）：

class Animal:
    def speak(self):
        pass
class Dog(Animal):
    def speak(self):
        return "Woof!"
class Cat(Animal):
    def speak(self):
        return "Meow!"
class AnimalFactory:
    @staticmethod
    def create_animal(animal_type):
        if animal_type == "dog":
            return Dog()
        elif animal_type == "cat":
            return Cat()
        else:
            raise ValueError("Unknown animal type")

考察点：接口设计、扩展性、代码复用。

四、实际场景：缓存与限流的实现

1. LRU缓存

LRU（Least Recently Used）缓存是面试中常见的系统设计题，要求候选人实现一个固定大小的缓存，当缓存满时，优先淘汰最近最少使用的数据。

示例代码（基于有序字典的LRU）：

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

考察点：数据结构选择、时间复杂度优化（O(1)操作）。

2. 令牌桶限流

令牌桶算法是常用的限流策略，面试中常要求实现一个简单的令牌桶，控制请求的通过速率。

示例代码（令牌桶限流）：

import time
import threading
class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last_time = time.time()
        self.lock = threading.Lock()
    def _refill(self):
        now = time.time()
        elapsed = now - self.last_time
        new_tokens = elapsed * self.rate
        if new_tokens > 0:
            self.tokens = min(self.capacity, self.tokens + new_tokens)
            self.last_time = now
    def consume(self, tokens=1):
        with self.lock:
            self._refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

考察点：并发控制、时间计算、资源管理。

五、备考建议：提升手写代码能力的实用技巧

1. 多刷题，多总结：LeetCode、HackerRank等平台提供了大量手写代码题，建议按标签分类练习，总结解题模板。
2. 模拟面试环境：在白纸或白板手写代码，注意代码格式和可读性，避免依赖IDE的自动补全。
3. 注重边界条件：手写代码时，务必考虑空输入、极端值、并发访问等边界情况。
4. 沟通与解释：面试中，边写边解释思路，展示你的思考过程，而非单纯追求代码正确性。

手写代码环节是技术面试的核心，通过系统准备和实战练习，你可以显著提升这一环节的表现。记住，面试官不仅考察代码的正确性，更关注你的编码习惯、逻辑思维和问题解决能力。