网易笔试真题

🏢 公司简介

网易是中国领先的互联网技术公司，笔试题目注重游戏开发、音视频技术和创新算法。

📝 题目特点

• 游戏算法：考查游戏开发相关的算法和数据结构
• 音视频处理：涉及多媒体技术和信号处理
• 创新思维：注重算法的创新性和实用性
• 性能优化：重视代码的执行效率

🎯 2024年春招真题

题目1：游戏匹配算法 🟡

题目描述： 设计一个多人在线游戏的玩家匹配算法，根据玩家等级、技能水平和延迟进行匹配。

输入：

• 玩家信息列表（等级、技能分数、网络延迟）
• 匹配房间大小

输出：

• 匹配成功的玩家组合

解题思路：

1. 多维度评分系统
2. 使用优先队列进行匹配
3. 考虑等待时间权重

public class GameMatching {
    public List<List<Player>> matchPlayers(List<Player> players, int roomSize) {
        List<List<Player>> matches = new ArrayList<>();
        
        // 按综合分数排序
        players.sort((a, b) -> {
            double scoreA = calculateMatchScore(a);
            double scoreB = calculateMatchScore(b);
            return Double.compare(scoreA, scoreB);
        });
        
        // 滑动窗口匹配
        for (int i = 0; i <= players.size() - roomSize; i++) {
            List<Player> room = new ArrayList<>();
            for (int j = i; j < i + roomSize; j++) {
                room.add(players.get(j));
            }
            
            if (isValidMatch(room)) {
                matches.add(room);
                // 移除已匹配的玩家
                for (Player p : room) {
                    players.remove(p);
                }
                i--; // 重新调整索引
            }
        }
        
        return matches;
    }
    
    private double calculateMatchScore(Player player) {
        return player.getLevel() * 0.4 + 
               player.getSkillScore() * 0.4 + 
               (1000 - player.getLatency()) * 0.2;
    }
    
    private boolean isValidMatch(List<Player> players) {
        // 检查等级差距、技能差距和延迟差距
        int maxLevel = players.stream().mapToInt(Player::getLevel).max().orElse(0);
        int minLevel = players.stream().mapToInt(Player::getLevel).min().orElse(0);
        
        return (maxLevel - minLevel) <= 5; // 等级差距不超过5级
    }
}

class Player {
    private int playerId;
    private int level;
    private double skillScore;
    private int latency;
    private long waitTime;
    
    // getters and setters
}

题目2：音频压缩算法 🔴

题目描述： 实现一个简单的音频数据压缩算法，要求在保证音质的前提下尽可能减小文件大小。

输入：

• 原始音频数据数组
• 压缩质量参数

输出：

• 压缩后的数据

解题思路：

1. 使用差分编码减少数据冗余
2. 应用霍夫曼编码进行无损压缩
3. 根据质量参数调整量化精度

public class AudioCompression {
    public byte[] compress(short[] audioData, int quality) {
        // 差分编码
        int[] differences = new int[audioData.length];
        differences[0] = audioData[0];
        for (int i = 1; i < audioData.length; i++) {
            differences[i] = audioData[i] - audioData[i-1];
        }
        
        // 量化
        int quantizationStep = getQuantizationStep(quality);
        for (int i = 0; i < differences.length; i++) {
            differences[i] = (differences[i] / quantizationStep) * quantizationStep;
        }
        
        // 霍夫曼编码
        return huffmanEncode(differences);
    }
    
    private int getQuantizationStep(int quality) {
        // 质量越高，量化步长越小
        return Math.max(1, 10 - quality);
    }
    
    private byte[] huffmanEncode(int[] data) {
        // 构建霍夫曼树并编码
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int value : data) {
            frequency.put(value, frequency.getOrDefault(value, 0) + 1);
        }
        
        // 简化实现，实际需要构建完整的霍夫曼树
        ByteArrayOutputStream output = new ByteArrayOutputStream();
        // ... 霍夫曼编码实现
        return output.toByteArray();
    }
}

题目3：实时弹幕系统 🟡

题目描述： 设计一个高并发的实时弹幕系统，支持弹幕的发送、接收和碰撞检测。

解题思路：

1. 使用WebSocket进行实时通信
2. 弹幕轨道管理避免重叠
3. 限流机制防止刷屏

public class DanmakuSystem {
    private final Map<String, List<Danmaku>> roomDanmakus = new ConcurrentHashMap<>();
    private final int MAX_TRACKS = 10;
    
    public boolean sendDanmaku(String roomId, Danmaku danmaku) {
        // 限流检查
        if (!rateLimitCheck(danmaku.getUserId())) {
            return false;
        }
        
        // 分配轨道
        int track = allocateTrack(roomId);
        if (track == -1) {
            return false; // 无可用轨道
        }
        
        danmaku.setTrack(track);
        danmaku.setTimestamp(System.currentTimeMillis());
        
        roomDanmakus.computeIfAbsent(roomId, k -> new ArrayList<>()).add(danmaku);
        
        // 广播给房间内所有用户
        broadcastToRoom(roomId, danmaku);
        
        return true;
    }
    
    private int allocateTrack(String roomId) {
        List<Danmaku> danmakus = roomDanmakus.get(roomId);
        if (danmakus == null) return 0;
        
        boolean[] trackUsed = new boolean[MAX_TRACKS];
        long currentTime = System.currentTimeMillis();
        
        // 检查哪些轨道被占用
        for (Danmaku d : danmakus) {
            if (currentTime - d.getTimestamp() < d.getDuration()) {
                trackUsed[d.getTrack()] = true;
            }
        }
        
        // 返回第一个可用轨道
        for (int i = 0; i < MAX_TRACKS; i++) {
            if (!trackUsed[i]) {
                return i;
            }
        }
        
        return -1; // 无可用轨道
    }
}

🎯 2023年秋招真题

题目1：游戏地图寻路 🟡

题目描述： 在游戏地图中实现智能NPC的寻路算法，考虑障碍物和移动成本。

public List<Point> findPath(int[][] map, Point start, Point end) {
    // A*算法实现
    PriorityQueue<Node> openSet = new PriorityQueue<>(
        Comparator.comparingInt(n -> n.fCost)
    );
    Set<Point> closedSet = new HashSet<>();
    
    openSet.offer(new Node(start, 0, heuristic(start, end), null));
    
    while (!openSet.isEmpty()) {
        Node current = openSet.poll();
        
        if (current.point.equals(end)) {
            return reconstructPath(current);
        }
        
        closedSet.add(current.point);
        
        for (Point neighbor : getNeighbors(current.point, map)) {
            if (closedSet.contains(neighbor)) continue;
            
            int gCost = current.gCost + getMoveCost(current.point, neighbor, map);
            int hCost = heuristic(neighbor, end);
            
            openSet.offer(new Node(neighbor, gCost, gCost + hCost, current));
        }
    }
    
    return new ArrayList<>(); // 无路径
}

💡 备考建议

1. 游戏开发：了解游戏引擎原理和常用算法
2. 多媒体技术：学习音视频编解码基础
3. 实时系统：掌握高并发和实时通信技术
4. 创新算法：培养算法设计和优化能力

📚 推荐资源

• 《游戏编程精粹》系列
• 《实时渲染》
• 《音视频开发进阶指南》
• 网易技术博客