在这篇文章中，我将详细描述我在谷歌面试中的一次技术问题的讨论。面试的主要内容是一个系统设计的编程问题，要求设计一个数据结构来管理产品和相关的优惠信息。整场面试流程包含了澄清问题、解题思路分析、面试官的追问、以及最后的复杂度分析和行为面试（BQ）环节。

In this blog, I’ll share my experience of a technical interview at Google, which focused on designing a data structure to manage product offers and their corresponding prices. The interview process covered clarifying the problem, discussing the solution, answering follow-up questions, analyzing time and space complexity, and behavioral questions (BQ). This post will walk you through the entire conversation and the approach I took during the interview.

---

问题描述：

首先，面试官提供了一个具体的题目描述，如下：

In Google Shopping we have products which are identified by a unique id.  
Each product can have multiple offers associated with it, and each offer has a corresponding price.  

Design a data structure to support the following operations:
- void AddOffer(int64 offer_id, int64 product_id, double price)
  - Adds offer_id, with the specified price, for product_id. 
- void RemoveOffer(int64 offer_id)
  - The offer is not valid anymore. 
- int64 QueryClosestOffer(int64 product_id, double price)
  - Returns the id of an offer corresponding to the specified product, which has its prices closest to the query parameter.

面试官接着提供了一个简单的示例帮助理解：

// Add(offer1, product1, 2.3)
// Add(offer2, product1, 2.6)
// QueryClosestOffer(product1, 2.5) -> offer2
// QueryClosestOffer(product1, 2) -> offer1
// Remove(offer2)
// QueryClosestOffer(product1, 2.5) -> offer1
// QueryClosestOffer(product2, 1) -> -1

---

澄清问题阶段：

在面试题目给出后，我首先通过提问澄清了几个关键细节，以确保对问题的完全理解：

1. 候选人提问：“我们需要定义一个类来包含所有接口吗？”
   • 面试官回答：“是的，你可以创建一个类来实现这些方法。”
2. 候选人提问：“当查询接近的价格时，如果有多个优惠的价格与查询价格相同或相近，我们应该返回哪一个？”
   • 面试官回答：“返回找到的第一个即可。”

澄清完这些问题后，我对整个系统的功能和预期行为有了清晰的理解。

Clarification Stage:

After hearing the problem, I asked a few clarifying questions to ensure I fully understood the requirements:

1. Candidate Question: “Are we expected to define a class that encapsulates all the methods?”
   • Interviewer Response: “Yes, you can create a class to implement these methods.”
2. Candidate Question: “When querying the closest price, what should we do if there are multiple offers with the same or very similar prices?”
   • Interviewer Response: “You can return the first one found.”

After these clarifications, I felt confident in my understanding of the system's functionality and behavior.

---

解题思路讨论：

接下来，我开始与面试官讨论我的解题思路：

• 候选人解释思路：“为了有效地管理每个产品的优惠和价格信息，我打算使用两个数据结构：
  1. 一个字典 product_offers，键为 product_id，值为该产品的所有优惠及其价格。这些优惠会以价格升序排列，以便后续快速查询。
  2. 另一个字典 offer_to_product，键为 offer_id，值为该优惠所对应的 product_id。这个字典主要用于当我们需要移除一个优惠时，能够快速找到对应的产品。”

面试官对此表示认可，并让我继续实现具体的方案。

Solution Discussion:

Next, I shared my solution approach with the interviewer:

• Candidate Explanation: “To efficiently manage the product offers and their prices, I plan to use two data structures:
  1. A dictionary product_offers, where the key is the product_id and the value is a list of offers sorted by price. This will allow fast lookups when querying for the closest price.
  2. Another dictionary offer_to_product, where the key is the offer_id and the value is the corresponding product_id. This mapping will be helpful when removing an offer since it allows us to quickly locate the product it belongs to.”

The interviewer acknowledged this approach and encouraged me to proceed with the implementation.

---

解题细节讨论：

接下来，我详细解释了我的解题步骤，面试官对此进行了持续的追问和确认。

1. 初始化数据结构：

我打算用两个字典来分别存储产品与优惠信息以及优惠到产品的映射。
这样设计可以保证添加、删除、查询操作都能在高效的时间内完成。

2. 添加优惠：

在添加优惠时，我计划使用二分法将新优惠按价格顺序插入到产品对应的优惠列表中。
通过这种方式，每次插入操作的时间复杂度将降至 $O(\log n)$，其中 n 是产品的优惠数量。

3. 移除优惠：

移除优惠时，我会通过 offer_id 找到对应的 product_id，再从产品的优惠列表中移除该优惠。
这可以通过遍历和过滤的方式快速完成。

4. 查询最接近的优惠：

对于查询操作，我计划通过二分查找快速找到离查询价格最近的优惠。
在找到价格相等或最接近的优惠后，我会返回对应的 offer_id。

面试官对这个解题思路表示理解，并询问了具体的数据结构在边界情况（如优惠列表为空）的处理方式。
我解释说，对于没有任何优惠的产品，我会直接返回 -1，表示无有效优惠可供查询。

Solution Details:

After presenting my approach, I began discussing the details of the solution, step by step. The interviewer occasionally asked questions to dig deeper into specific parts of the design.

1. Data Structure Initialization:

I explained that I would initialize two dictionaries to store the product-offer relationships and offer-product mappings. This design ensures that adding, removing, and querying offers would be efficient.

2. AddOffer Operation:

For the AddOffer method, I described how I would use binary search to insert the new offer into the product's list of offers in sorted order.
By using a binary insertion, the insertion time complexity would be reduced to $O(\log n)$, where n is the number of offers for the given product.

3. RemoveOffer Operation:

For the RemoveOffer method, I explained that I would first look up the offer_id in the offer_to_product dictionary to find the associated product_id. I would then remove the offer from the product's offer list by filtering out the target offer.

4. QueryClosestOffer Operation:

For the QueryClosestOffer method, I explained that I would use binary search to efficiently find the offer whose price is closest to the query price. If an exact match is not found, I would return the offer with the closest price.

At this point, the interviewer asked how I would handle edge cases, such as when a product has no offers. I clarified that in such cases, I would return -1 to indicate no available offers.

---

复杂度分析：

面试官接下来要求我对整个算法的时间复杂度和空间复杂度进行分析。

• 时间复杂度：
  • AddOffer 方法的时间复杂度为 $O(\log n)$，其中 n 是该产品现有的优惠数量，因为我们使用二分法插入优惠。
  • RemoveOffer 的时间复杂度为 $O(n)$，因为我们需要遍历所有优惠以找到并删除指定的优惠。
  • QueryClosestOffer 的时间复杂度为 $O(\log n)$，因为我们使用二分查找来找到最接近的优惠。
• 空间复杂度：
  • 该方案的空间复杂度为 $O(m)$，其中 m 是所有优惠的总数。每个优惠都会存储在 product_offers 和 offer_to_product 两个字典中。

Complexity Analysis:

The interviewer then asked me to analyze the time and space complexity of my solution.

• Time Complexity:
  • The AddOffer method has a time complexity of $O(\log n)$ due to the binary insertion, where n is the number of offers for a given product.
  • The RemoveOffer method has a time complexity of $O(n)$ because it may require filtering through all the offers to remove the desired one.
  • The QueryClosestOffer method also has a time complexity of $O(\log n)$ since it uses binary search to find the closest price.
• Space Complexity:
  • The space complexity of the entire system is $O(m)$, where m is the total number of offers stored across all products. This is because each offer is stored in both the product_offers and offer_to_product dictionaries.

The interviewer seemed satisfied with the analysis and moved on to behavioral questions.

---

行为面试问题（BQ）讨论：

在技术问题结束后，面试官提出了一些行为问题（Behavioral Questions）：

1. 面试官提问：“在团队合作中，你如何处理冲突？”
   • 候选人回答：“在面对冲突时，我通常会首先倾听对方的意见，确保了解他们的立场。在有了充分的理解后，我会表达我的观点，尝试找到一个双方都能接受的解决方案。团队合作的关键在于沟通。”
2. 面试官提问：“你在工作中遇到的最大的挑战是什么？你是如何克服的？”
   • 候选人回答：“我曾遇到过一个项目中需求不断变化的挑战。面对这种情况，我和团队一起调整了我们的开发流程，采用了更加灵活的敏捷开发模式，分阶段进行交付，从而应对频繁的变化。”
3. 反问环节：
   • 候选人提问：“您最喜欢在这里工作的是什么？”
   • 候选人提问：“加入团队后，一般的入职流程是怎样的？会有哪些项目或任务？”

面试官对我的问题进行了详细的回答，解释了团队结构、日常工作流程以及新人入职的培训和指导安排。

Behavioral Questions (BQ):

After finishing the technical discussion, the interviewer asked some behavioral questions to assess my communication skills and teamwork experience:

1. Interviewer Question: “How do you handle conflicts in a team setting?”
   • Candidate Response: “When faced with conflicts, I try to listen carefully to the other person's point of view to fully understand their perspective. After that, I share my own thoughts and try to find a solution that works for both parties. I believe communication is the key to resolving conflicts.”
2. Interviewer Question: “What is the biggest challenge you’ve faced in your work, and how did you overcome it?”
   • Candidate Response: “One of the biggest challenges I faced was when the requirements for a project changed frequently. To handle this, my team adopted a more flexible approach by switching to Agile methodology, breaking the project into smaller deliverables and iterating on feedback. This helped us manage the changes more effectively.”
3. Questions from Me:
   • Candidate Question: “What do you like most about working here at Google?”
   • Candidate Question: “What is the onboarding process like for new hires?”

The interviewer was happy to answer my questions, explaining the team structure, onboarding process, and some of the projects new hires typically work on.

---

总结：

通过这次面试，我展示了如何设计一个有效的数据结构来管理产品和优惠信息，并通过合理的算法优化来提高查询效率。整个解题过程中，我与面试官进行了多次交流，确保解决方案满足问题的需求。在面试的行为问题部分，我分享了自己的团队合作经验和解决问题的思路，面试官对此表示了认可。

如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。

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.