Amazon SDE1 面试经验分享：Movie Player System设计题 - Oavoservice

🎤 Amazon SDE1 0624 T4Z 面经

👩‍💻 Candidate 在 Amazon SDE1 面试中遇到了一个经典的Movie Player System设计题。

面试官是烙印，但整体面试体验还不错！

📋 BQ 环节

BQ1: Most challenging project

• 需要说明难点在哪里
• fail to deliver result 需要强调scope
• 重点突出项目的技术挑战和解决方案

💻 Coding 环节

题目：设计一个 Movie Player System

📝 题目要求

• 每次返回一个 moviePlayList
• 每个电影有好感度（rating）
• 每次输入总时间和gapTime
• 要求总时间不超过 TargetTime
• 总好感度最高

❓ 问题分析

这是一个典型的0/1背包问题的变种：

• 物品：电影
• 重量：电影时长 + gapTime
• 价值：电影好感度
• 容量：TargetTime

💡 思路设计

使用动态规划解决0/1背包问题：

1. 定义状态：dp[i][j] 表示前i个电影在时间限制j下的最大好感度
2. 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-time[i]] + rating[i])
3. 边界条件：dp[0][j] = 0

💻 代码实现

import java.util.*;

public class MoviePlayerSystem {
    static class Movie {
        String name;
        int duration;
        int rating;
        
        public Movie(String name, int duration, int rating) {
            this.name = name;
            this.duration = duration;
            this.rating = rating;
        }
    }
    
    public List<Movie> getOptimalPlaylist(List<Movie> movies, int targetTime, int gapTime) {
        int n = movies.size();
        int totalTime = targetTime;
        
        // dp[i][j] = 前i个电影在时间j下的最大好感度
        int[][] dp = new int[n + 1][totalTime + 1];
        boolean[][] selected = new boolean[n + 1][totalTime + 1];
        
        // 填充DP表
        for (int i = 1; i <= n; i++) {
            Movie movie = movies.get(i - 1);
            int movieTime = movie.duration + gapTime; // 包含gap时间
            
            for (int j = 0; j <= totalTime; j++) {
                // 不选择当前电影
                dp[i][j] = dp[i - 1][j];
                
                // 选择当前电影（如果时间允许）
                if (j >= movieTime) {
                    int newValue = dp[i - 1][j - movieTime] + movie.rating;
                    if (newValue > dp[i][j]) {
                        dp[i][j] = newValue;
                        selected[i][j] = true;
                    }
                }
            }
        }
        
        // 回溯找到最优解
        List<Movie> result = new ArrayList<>();
        int i = n, j = totalTime;
        
        while (i > 0 && j > 0) {
            if (selected[i][j]) {
                result.add(movies.get(i - 1));
                j -= (movies.get(i - 1).duration + gapTime);
            }
            i--;
        }
        
        Collections.reverse(result);
        return result;
    }
    
    // 测试方法
    public static void main(String[] args) {
        MoviePlayerSystem system = new MoviePlayerSystem();
        
        List<Movie> movies = Arrays.asList(
            new Movie("Movie1", 90, 8),
            new Movie("Movie2", 120, 9),
            new Movie("Movie3", 100, 7),
            new Movie("Movie4", 80, 6)
        );
        
        int targetTime = 300; // 5小时
        int gapTime = 10;     // 10分钟间隔
        
        List<Movie> playlist = system.getOptimalPlaylist(movies, targetTime, gapTime);
        
        System.out.println("最优播放列表：");
        int totalTime = 0, totalRating = 0;
        for (Movie movie : playlist) {
            System.out.println(movie.name + " - 时长:" + movie.duration + "分钟, 评分:" + movie.rating);
            totalTime += movie.duration + gapTime;
            totalRating += movie.rating;
        }
        System.out.println("总时长: " + totalTime + "分钟, 总评分: " + totalRating);
    }
}

🚀 Follow-up 1: 优化时间复杂度

面试官问如何优化时间复杂度：

• 空间优化：使用一维数组代替二维数组，空间复杂度从O(n*W)降到O(W)
• 剪枝优化：如果当前电影时长超过剩余时间，直接跳过
• 排序优化：按单位时间好感度排序，优先考虑高性价比电影

// 空间优化版本
public List<Movie> getOptimalPlaylistOptimized(List<Movie> movies, int targetTime, int gapTime) {
    int[] dp = new int[targetTime + 1];
    int[] parent = new int[targetTime + 1];
    Arrays.fill(parent, -1);
    
    for (int i = 0; i < movies.size(); i++) {
        Movie movie = movies.get(i);
        int movieTime = movie.duration + gapTime;
        
        // 从后往前遍历，避免重复选择
        for (int j = targetTime; j >= movieTime; j--) {
            if (dp[j - movieTime] + movie.rating > dp[j]) {
                dp[j] = dp[j - movieTime] + movie.rating;
                parent[j] = i;
            }
        }
    }
    
    // 回溯找到最优解
    List<Movie> result = new ArrayList<>();
    int time = targetTime;
    while (time > 0 && parent[time] != -1) {
        int movieIndex = parent[time];
        result.add(movies.get(movieIndex));
        time -= (movies.get(movieIndex).duration + gapTime);
    }
    
    Collections.reverse(result);
    return result;
}

🎯 Follow-up 2: 客户偏好约束

面试官问："加一个constrain，每个客户preference type不一样怎么解决，比如需要看的genre"

解决方案：

• 多维度约束：在DP状态中加入genre维度
• 过滤预处理：先根据客户偏好过滤电影列表
• 权重调整：根据客户偏好调整电影好感度

static class MovieWithGenre extends Movie {
    String genre;
    
    public MovieWithGenre(String name, int duration, int rating, String genre) {
        super(name, duration, rating);
        this.genre = genre;
    }
}

public List<Movie> getPersonalizedPlaylist(List<MovieWithGenre> movies, 
                                          int targetTime, int gapTime, 
                                          Set<String> preferredGenres) {
    // 1. 过滤客户偏好的电影
    List<MovieWithGenre> filteredMovies = movies.stream()
        .filter(movie -> preferredGenres.contains(movie.genre))
        .collect(Collectors.toList());
    
    // 2. 根据偏好调整评分
    for (MovieWithGenre movie : filteredMovies) {
        if (preferredGenres.contains(movie.genre)) {
            movie.rating = (int)(movie.rating * 1.2); // 偏好类型加分
        }
    }
    
    // 3. 使用优化后的算法
    return getOptimalPlaylistOptimized(filteredMovies, targetTime, gapTime);
}

🔍 算法分析

• 时间复杂度：O(n * W)，其中n是电影数量，W是目标时间
• 空间复杂度：O(W)（优化后）
• 核心思想：0/1背包问题的动态规划解法

✨ 面试官反馈

面试官对解决方案很满意："Great approach! You've correctly identified this as a knapsack problem and provided both the basic solution and optimizations. The follow-up solutions for personalization are also well thought out."

面试技巧分享

在 Amazon SDE1 面试中，除了算法实现，面试官还会关注：

1. 问题识别能力

能够快速识别出这是一个背包问题的变种，并建立正确的数学模型。

2. 优化思维

主动思考时间复杂度和空间复杂度的优化方案。

3. 扩展性设计

能够处理follow-up问题，考虑系统的扩展性和个性化需求。

4. 代码质量

写出清晰、可读的代码，包含适当的注释和测试用例。

Oavoservice 实时辅助服务

在这次 Amazon SDE1 面试中，我们的实时辅助系统发挥了关键作用：

• 问题分析：帮助候选人快速识别背包问题的本质
• 算法指导：提供动态规划的标准解法
• 优化建议：在follow-up环节提供空间优化思路
• 扩展设计：协助设计个性化推荐系统

结语

Movie Player System虽然是一道系统设计题，但核心算法是经典的背包问题。在面试中，能够快速识别问题类型并正确实现算法是关键。同时，处理follow-up问题展现了候选人的技术深度和系统设计能力。

如果你正在准备 Amazon 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。

Oavoservice - 让每一次面试都成为成功的机会！

需要辅助的同学随时dd哦，vo开始前支持mock！