最近我们的客户参加了Google的在线评测(OA),这是申请软件工程师职位的重要环节。在90分钟内,候选人需要解决两道算法题。这次评测对候选人的编程能力和解决问题的速度提出了很高的要求。现在,我想和大家分享一下这两道题目和我的解决方法,希望能帮助到准备参加Google面试的朋友们。
Recently, our client participated in Google's Online Assessment (OA), an important step in applying for a software engineering position. In 90 minutes, the candidate needed to solve two algorithm problems. This assessment placed high demands on the candidate's programming skills and problem-solving speed. Now, I would like to share these two problems and my solutions, hoping to help those preparing for Google interviews.
Problem 1: Locker Room
Description: A locker room is a place containing lockers where people can leave their belongings and pick them up later. Lockers can be found, for example, in changing rooms at the gym or in the sports hall.
An automatic locker system has been introduced in the locker room. When a client visits the room, the system works as follows:
- If the client has no locker assigned, the system assigns them a free locker with the lowest available number.
- If the client has a locker assigned, the system opens and frees the locker. After this, the locker can be reassigned to another client.
Lockers are numbered from 1. At the beginning of the day, all lockers are free.
The locker room is visited N times. Which locker was the last one assigned to some client?
Example:
- For clients = ["Alice", "Eve", "Bob", "Eve", "Carl", "Alice"], the following events happened:
- Locker 1 was assigned to Alice;
- Locker 2 was assigned to Eve;
- Locker 3 was assigned to Bob;
- Eve freed locker 2;
- Locker 2 was assigned to Carl;
- Alice freed locker 1.
- For clients = ["Alice", "Bob", "Bobby"], the function should return 3.
- For clients = ["Bob", "bob", "BoB", "bob", "BOB"], the function should return 2, because lowercase letters should be distinguished from uppercase letters.
- For clients = ["Alice", "Alice", "Bob", "Alice"], the function should return 2.
Assume that:
- N is an integer within the range [3..300];
- Each string in the array clients consists of at most 20 English letters ('A'-'Z', 'a'-'z').
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
更衣室是一个包含储物柜的地方,人们可以在这里放置物品,然后稍后取走。例如,在健身房或体育馆的更衣室中可以找到储物柜。
一个自动储物柜系统被引入到更衣室中。当客户访问房间时,系统的工作方式如下:
- 如果客户没有被分配到储物柜,系统会分配一个最低可用号码的储物柜给他们;
- 如果客户已分配到储物柜,系统会打开并释放储物柜。之后,该储物柜可以重新分配给其他客户。
储物柜的编号从1开始。在一天的开始时,所有储物柜都是空的。
更衣室被访问了N次。最后一个分配给某个客户的储物柜是哪一个?
示例
- 对于clients = ["Alice", "Eve", "Bob", "Eve", "Carl", "Alice"],以下事件发生了:
- 储物柜1分配给了Alice;
- 储物柜2分配给了Eve;
- 储物柜3分配给了Bob;
- Eve释放了储物柜2;
- 储物柜2分配给了Carl;
- Alice释放了储物柜1。
最后一个分配的储物柜是2,因此函数应返回2。
- 对于clients = ["Alice", "Bob", "Bobby"],函数应返回3。
- 对于clients = ["Bob", "bob", "BoB", "bob", "BOB"],函数应返回2,因为小写字母和大写字母应区分。
- 对于clients = ["Alice", "Alice", "Bob", "Alice"],函数应返回2。
假设条件
- N是范围[3..300]内的整数;
- 数组clients中的每个字符串由最多20个英文字母('A'-'Z', 'a'-'z')组成。
在你的解决方案中,专注于正确性。解决方案的性能不是评估的重点。
Problem: Heart Rate and Activity Level
Description: There are N consecutive measurements (numbered from 0 to N-1) taken by a health monitoring device. During the K-th measurement, the device recorded heartRate[K] and activityLevel[K] (possible levels are "Low", "Normal" or "High").
What is the largest difference between the highest and lowest values of the heart rate during a single period of the same activity level?
Write a function:
int solution(vector<int> &heartRate, vector<string> &activityLevel);
that, given an array of integers heartRate and an array of strings activityLevel, both of length N, returns the largest difference between the highest and lowest values of the heart rate during a single period of the same activity level.
Examples:
- Assume that heartRate = [82, 120, 78, 61] and activityLevel = ["Normal", "High", "Normal", "Low"]. All activity periods of the same level are of length 1, so the function should return 0.
- For heartRate = [100, 87, 90, 90, 125] and activityLevel = ["Normal", "Normal", "Normal", "High", "Low"], the function should return 13.
Assume that:
- N is an integer within the range [1..100];
- Each element of array heartRate is an integer within the range [40..200];
- Each element of array activityLevel is a string that can have one of the following values: Low, Normal, High.
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
题目:心率和活动水平
题目描述: 有一个健康监测设备记录了N次连续的测量(编号从0到N-1)。在第K次测量中,设备记录了心率heartRate[K]和活动水平activityLevel[K](可能的水平有“低”、“正常”或“高”)。
求在同一活动水平的单个周期内,心率最高值和最低值之间的最大差值。
编写一个函数:
int solution(vector<int> &heartRate, vector<string> &activityLevel);
该函数接收一个整数数组heartRate和一个字符串数组activityLevel,两者长度均为N。函数返回在同一活动水平的单个周期内,心率最高值和最低值之间的最大差值。
示例:
- 假设 heartRate = [82, 120, 78, 61] 和 activityLevel = ["Normal", "High", "Normal", "Low"]。所有相同级别的活动周期长度为1,因此函数应返回0。
- 对于 heartRate = [100, 87, 90, 90, 125] 和 activityLevel = ["Normal", "Normal", "Normal", "High", "Low"],函数应返回13。
假设条件:
- N是范围[1..100]内的整数;
- 数组heartRate的每个元素是范围[40..200]内的整数;
- 数组activityLevel的每个元素是一个字符串,可以有以下值之一:Low, Normal, High。
在你的解决方案中,专注于正确性。解决方案的性能不是评估的重点。
如果你也在为Google的在线评测(OA)而发愁,或者不想自己亲自完成这些繁琐的测试,我们提供专业的服务来帮助你顺利通过。我们的团队有丰富的经验,可以为你提供一对一的指导和全面的解决方案。联系我们,让我们一起迈向成功!
If you are also worried about Google's Online Assessment (OA) or simply don't want to go through the hassle of completing these tests on your own, we offer professional services to help you pass with flying colors. Our team has extensive experience and can provide you with one-on-one guidance and comprehensive solutions. Contact us and let's achieve success together!
![](https://csoahelp.com/wp-content/uploads/2024/07/image-24-1024x133.png)
![](https://csoahelp.com/wp-content/uploads/2024/02/image-35.png)