在这篇博客中，我将分享近期谷歌面试中的两道经典题目。这些题目不仅考察了候选人的算法基础，还测试了对问题的分析能力和思维的灵活性。通过还原面试场景，重现候选人与面试官的互动与对话，希望能帮助大家理解解题过程，并为大家在未来的技术面试中提供有用的参考。
In this blog, I'll share two classic questions from a recent Google interview. These questions not only test the candidate's algorithmic foundation but also examine their problem analysis skills and ability to think flexibly. By recreating the interview scenario and reconstructing the interaction between the candidate and the interviewer, I hope to help you better understand the problem-solving process and provide useful insights for future technical interviews.
第一题：硬币问题
题目原文：
Given a memoized list of how many ways there are to reach a coin value, return the original list of coins. If there is no list of coins that can yield the input memoization, return None.
中文翻译：
给定一个表示硬币组合方式的列表（memoization），找出可以达到这些组合方式的硬币列表。如果不存在可以生成这些组合方式的硬币列表，则返回 None。
输入示例：
Example 1:
dp = [1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 3]
output: [2, 5, 6]
Example 2:
dp = [1, 1, 1, 3, 2]
output: None
Example 3:
dp = [1,1]
output: [1]
解析：
这个问题的核心在于通过动态规划的思想，反推出满足特定组合的硬币列表。需要根据每个组合数，找出背后可能的硬币组合。如果没有合理的硬币组合，就返回 None。
在实际面试中，面试官可能会提供一些澄清，比如要求我们确保返回的硬币列表是唯一的。并且，在面试官的提示下，逐步优化解题思路，比如使用DFS或回溯算法来枚举所有可能的硬币组合。
Problem 1: Coin Combination Problem
Problem Statement:
Given a memoized list of how many ways there are to reach a coin value, return the original list of coins. If there is no list of coins that can yield the input memoization, return None.
Example:
Example 1:
dp = [1, 0, 1, 0, 1, 1, 2, 1, 2, 1, 3]
output: [2, 5, 6]
Example 2:
dp = [1, 1, 1, 3, 2]
output: None
Example 3:
dp = [1,1]
output: [1]
Analysis:
The key to this problem is to reverse-engineer a list of coins that can produce the given number of combinations using dynamic programming. Based on each number of combinations, we need to deduce the possible set of coins behind it. If no valid coin list can be derived, we return None.
During the interview, the interviewer might provide clarifications, such as ensuring that the coin list returned is unique. Also, with the interviewer's guidance, we might progressively optimize the solution using DFS or backtracking to enumerate all possible combinations of coins.
第二题：字符串宽度问题
题目原文：
Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz" Output: [3, 60] Explanation: You can write s as follows:
abcdefghij // 100 pixels wide
klmnopqrst // 100 pixels wide
uvwxyz // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.
中文翻译：
输入一个宽度列表和一个字符串，返回在每行固定像素数为100时，字符串可以被写成多少行，以及最后一行占用多少像素宽度。
输入示例：
输入：
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
s = "abcdefghijklmnopqrstuvwxyz"
输出：[3, 60]
解析：
题目的核心在于模拟字符串在一行中的排布情况。在每行最多100像素的限制下，我们需要不断计算当前字符所占的宽度，并确定是否需要换行。在换行后，继续计算剩余字符的宽度，直到遍历完整个字符串。
在面试中，面试官可能会提出一些边界情况的处理问题，比如当字符串特别短或特别长时的表现。同时，我们需要考虑性能，确保算法可以高效地处理大规模输入。
Problem 2: String Width Problem
Problem Statement:
Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz" Output: [3, 60] Explanation: You can write s as follows:
abcdefghij // 100 pixels wide
klmnopqrst // 100 pixels wide
uvwxyz // 60 pixels wide
There are a total of 3 lines, and the last line is 60 pixels wide.
Example:
Input:
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
s = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Analysis:
The core of this problem lies in simulating how the string is laid out in a line. With a maximum line width of 100 pixels, we need to constantly calculate the width of the current character and determine whether a line break is necessary. After breaking to a new line, we continue calculating the width of the remaining characters until we have processed the entire string.
In the interview, the interviewer might ask questions about edge cases, such as handling particularly short or long strings. At the same time, we need to consider the performance of the solution to ensure it can efficiently handle large inputs.
通过这两道题，我们可以看出，谷歌的面试更偏向考察候选人的分析与推理能力，而不仅仅是单纯的编写代码。每道题背后都有一些隐藏的复杂度，面试官通过引导和对话，逐步挖掘出候选人的解题思路。如果你也遇到类似的题目，重要的是冷静分析，逐步推导出最优解。
希望这些题目的讲解对你有所帮助，也祝你在未来的面试中取得成功！
From these two problems, it's evident that Google interviews focus more on evaluating a candidate's analytical and reasoning skills rather than just writing code. Each problem has hidden complexities, and through the interviewer's guidance and conversation, they gradually probe the candidate's problem-solving approach. If you encounter similar problems, it's important to stay calm, analyze the situation, and gradually derive the optimal solution.
I hope these explanations help, and I wish you success in your future interviews!
如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。
In this Google interview, I demonstrated my understanding of common algorithmic problems and my problem-solving abilities. Each problem presented different challenges, but all could be solved through logical algorithm strategies.
If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.
