美团笔试真题

🏢 公司简介

美团是中国领先的生活服务电子商务平台，笔试题目注重算法实用性、业务场景和系统效率。

📝 题目特点

• 业务导向：结合外卖、出行、酒店等实际业务场景
• 算法实用：考查解决实际问题的算法能力
• 系统效率：关注大规模数据处理和系统性能
• 逻辑清晰：重视解题思路的条理性

🎯 2024年春招真题

题目1：外卖配送路径优化 🟡

题目描述： 给定一个配送员的位置和多个订单的取餐点、送餐点，设计算法找到最优的配送路径，使总配送时间最短。

输入：

• 配送员起始位置
• 订单列表（每个订单包含取餐点和送餐点坐标）
• 各点之间的距离矩阵

输出：

• 最优配送路径
• 总配送时间

解题思路：

class Order {
    int id;
    Point pickupPoint;
    Point deliveryPoint;
    int priority; // 订单优先级
    
    public Order(int id, Point pickup, Point delivery, int priority) {
        this.id = id;
        this.pickupPoint = pickup;
        this.deliveryPoint = delivery;
        this.priority = priority;
    }
}

class Point {
    double x, y;
    
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    
    public double distanceTo(Point other) {
        return Math.sqrt(Math.pow(x - other.x, 2) + Math.pow(y - other.y, 2));
    }
}

class DeliveryOptimizer {
    public List<Integer> optimizeRoute(Point start, List<Order> orders) {
        // 使用贪心算法 + 动态规划优化
        List<Integer> route = new ArrayList<>();
        Set<Integer> completed = new HashSet<>();
        Point currentPos = start;
        
        while (completed.size() < orders.size()) {
            int bestOrder = findBestNextOrder(currentPos, orders, completed);
            route.add(bestOrder);
            completed.add(bestOrder);
            
            // 更新当前位置到送餐点
            currentPos = orders.get(bestOrder).deliveryPoint;
        }
        
        return route;
    }
    
    private int findBestNextOrder(Point currentPos, List<Order> orders, Set<Integer> completed) {
        int bestOrder = -1;
        double bestScore = Double.MAX_VALUE;
        
        for (int i = 0; i < orders.size(); i++) {
            if (completed.contains(i)) continue;
            
            Order order = orders.get(i);
            double score = calculateOrderScore(currentPos, order);
            
            if (score < bestScore) {
                bestScore = score;
                bestOrder = i;
            }
        }
        
        return bestOrder;
    }
    
    private double calculateOrderScore(Point currentPos, Order order) {
        double pickupDistance = currentPos.distanceTo(order.pickupPoint);
        double deliveryDistance = order.pickupPoint.distanceTo(order.deliveryPoint);
        double priorityFactor = 1.0 / (order.priority + 1);
        
        return (pickupDistance + deliveryDistance) * priorityFactor;
    }
}

题目2：酒店房间分配算法 🟠

题目描述： 酒店有不同类型的房间，客户有不同的需求和预算，设计算法实现最优的房间分配，最大化酒店收益。

输入：

• 房间列表（类型、价格、数量）
• 客户需求列表（房间类型偏好、预算、入住时间）

输出：

• 房间分配方案
• 总收益

解题思路：

class Room {
    String type;
    double price;
    int available;
    Set<String> amenities;
    
    public Room(String type, double price, int available, Set<String> amenities) {
        this.type = type;
        this.price = price;
        this.available = available;
        this.amenities = amenities;
    }
}

class Customer {
    int id;
    String preferredType;
    double budget;
    Date checkIn;
    Date checkOut;
    Set<String> requiredAmenities;
    
    public Customer(int id, String preferredType, double budget, 
                   Date checkIn, Date checkOut, Set<String> requiredAmenities) {
        this.id = id;
        this.preferredType = preferredType;
        this.budget = budget;
        this.checkIn = checkIn;
        this.checkOut = checkOut;
        this.requiredAmenities = requiredAmenities;
    }
}

class HotelAllocation {
    public Map<Integer, String> allocateRooms(List<Room> rooms, List<Customer> customers) {
        Map<Integer, String> allocation = new HashMap<>();
        
        // 按预算从高到低排序客户
        customers.sort((a, b) -> Double.compare(b.budget, a.budget));
        
        for (Customer customer : customers) {
            String allocatedRoom = findBestRoom(customer, rooms);
            if (allocatedRoom != null) {
                allocation.put(customer.id, allocatedRoom);
                // 减少可用房间数量
                updateRoomAvailability(rooms, allocatedRoom);
            }
        }
        
        return allocation;
    }
    
    private String findBestRoom(Customer customer, List<Room> rooms) {
        String bestRoom = null;
        double bestScore = -1;
        
        for (Room room : rooms) {
            if (room.available > 0 && room.price <= customer.budget) {
                double score = calculateRoomScore(customer, room);
                if (score > bestScore) {
                    bestScore = score;
                    bestRoom = room.type;
                }
            }
        }
        
        return bestRoom;
    }
    
    private double calculateRoomScore(Customer customer, Room room) {
        double score = 0;
        
        // 房间类型匹配度
        if (room.type.equals(customer.preferredType)) {
            score += 50;
        }
        
        // 价格匹配度（价格越接近预算越好）
        double priceRatio = room.price / customer.budget;
        score += (1 - Math.abs(priceRatio - 0.8)) * 30; // 期望价格为预算的80%
        
        // 设施匹配度
        long matchedAmenities = customer.requiredAmenities.stream()
                .mapToLong(amenity -> room.amenities.contains(amenity) ? 1 : 0)
                .sum();
        score += (matchedAmenities * 20.0) / customer.requiredAmenities.size();
        
        return score;
    }
    
    private void updateRoomAvailability(List<Room> rooms, String roomType) {
        for (Room room : rooms) {
            if (room.type.equals(roomType)) {
                room.available--;
                break;
            }
        }
    }
}

题目3：美团优选商品推荐 🔴

题目描述： 基于用户的购买历史、商品特征和实时行为，设计一个商品推荐系统。

输入：

• 用户购买历史
• 商品特征矩阵
• 用户实时行为（浏览、收藏、加购物车）

输出：

• 个性化推荐商品列表

解题思路：

class Product {
    int id;
    String category;
    double price;
    double rating;
    Set<String> tags;
    int salesVolume;
    
    public Product(int id, String category, double price, double rating, 
                  Set<String> tags, int salesVolume) {
        this.id = id;
        this.category = category;
        this.price = price;
        this.rating = rating;
        this.tags = tags;
        this.salesVolume = salesVolume;
    }
}

class UserBehavior {
    enum ActionType { VIEW, FAVORITE, ADD_TO_CART, PURCHASE }
    
    int userId;
    int productId;
    ActionType action;
    long timestamp;
    
    public UserBehavior(int userId, int productId, ActionType action, long timestamp) {
        this.userId = userId;
        this.productId = productId;
        this.action = action;
        this.timestamp = timestamp;
    }
}

class RecommendationEngine {
    private Map<Integer, Map<String, Double>> userCategoryPreference;
    private Map<Integer, Set<String>> userTagPreference;
    private Map<Integer, Double> userAveragePurchasePrice;
    
    public List<Integer> recommend(int userId, List<Product> products, 
                                  List<UserBehavior> userHistory, int k) {
        // 构建用户画像
        buildUserProfile(userId, userHistory, products);
        
        // 计算商品推荐分数
        List<ProductScore> scores = new ArrayList<>();
        for (Product product : products) {
            if (!hasPurchased(userId, product.id, userHistory)) {
                double score = calculateRecommendationScore(userId, product);
                scores.add(new ProductScore(product.id, score));
            }
        }
        
        // 返回Top-K推荐
        return scores.stream()
                .sorted((a, b) -> Double.compare(b.score, a.score))
                .limit(k)
                .map(ps -> ps.productId)
                .collect(Collectors.toList());
    }
    
    private void buildUserProfile(int userId, List<UserBehavior> history, List<Product> products) {
        Map<String, Integer> categoryCount = new HashMap<>();
        Set<String> allTags = new HashSet<>();
        List<Double> purchasePrices = new ArrayList<>();
        
        for (UserBehavior behavior : history) {
            if (behavior.userId == userId) {
                Product product = findProduct(behavior.productId, products);
                if (product != null) {
                    // 统计类别偏好
                    categoryCount.put(product.category, 
                        categoryCount.getOrDefault(product.category, 0) + getActionWeight(behavior.action));
                    
                    // 收集标签偏好
                    allTags.addAll(product.tags);
                    
                    // 记录购买价格
                    if (behavior.action == UserBehavior.ActionType.PURCHASE) {
                        purchasePrices.add(product.price);
                    }
                }
            }
        }
        
        // 计算偏好权重
        userCategoryPreference.put(userId, normalizeCategoryPreference(categoryCount));
        userTagPreference.put(userId, allTags);
        
        if (!purchasePrices.isEmpty()) {
            double avgPrice = purchasePrices.stream().mapToDouble(Double::doubleValue).average().orElse(0);
            userAveragePurchasePrice.put(userId, avgPrice);
        }
    }
    
    private double calculateRecommendationScore(int userId, Product product) {
        double score = 0;
        
        // 类别偏好分数
        Map<String, Double> categoryPref = userCategoryPreference.getOrDefault(userId, new HashMap<>());
        score += categoryPref.getOrDefault(product.category, 0.0) * 0.3;
        
        // 标签匹配分数
        Set<String> userTags = userTagPreference.getOrDefault(userId, new HashSet<>());
        long matchedTags = product.tags.stream().mapToLong(tag -> userTags.contains(tag) ? 1 : 0).sum();
        score += (matchedTags * 0.2) / Math.max(product.tags.size(), 1);
        
        // 价格匹配分数
        Double avgPrice = userAveragePurchasePrice.get(userId);
        if (avgPrice != null) {
            double priceScore = 1.0 - Math.abs(product.price - avgPrice) / avgPrice;
            score += Math.max(0, priceScore) * 0.2;
        }
        
        // 商品质量分数
        score += (product.rating / 5.0) * 0.15;
        
        // 热度分数
        score += Math.log(product.salesVolume + 1) / Math.log(10000) * 0.15;
        
        return score;
    }
    
    private int getActionWeight(UserBehavior.ActionType action) {
        switch (action) {
            case VIEW: return 1;
            case FAVORITE: return 2;
            case ADD_TO_CART: return 3;
            case PURCHASE: return 5;
            default: return 0;
        }
    }
    
    // 其他辅助方法...
}

🔍 历年高频考点

算法类

• 图算法（最短路径、最小生成树）
• 动态规划（背包问题、路径问题）
• 贪心算法（调度问题、分配问题）
• 排序和搜索算法

数据结构类

• 堆和优先队列
• 哈希表和布隆过滤器
• 树结构（二叉树、B+树）
• 图结构和邻接表

业务场景类

• 配送路径优化
• 商品推荐算法
• 价格策略算法
• 库存管理系统

💡 备考建议

1. 业务理解：了解美团的核心业务场景
2. 算法应用：注重算法在实际业务中的应用
3. 系统思维：考虑大规模数据处理的效率
4. 代码质量：编写清晰、可维护的代码
5. 优化意识：时刻考虑算法和系统的优化空间