Recently, our PROGRAMHELP team assisted several candidates with their Google onsite interview for graduate/internship software engineer positions, and most of them received their dream offer from Google. This series will analyze some of the onsite questions that our team met during the Google onsite interviews.
最近，我们的PROGRAMHELP团队给好几个候选人的谷歌onsite面试提供了辅导和代面辅助，他们中的绝大多数在我们团队成员的帮助下都成功拿下了Google的offer。这个系列我们来分析一下最近几次Google onsite面试遇到的算法题，供大家学习。
Onsite Algorithm Questions
Given an Array A, find the minimum amplitude you can get after changing up to 3 elements. Amplitude is the range of the array (basically the difference between the largest and smallest element).
Example 1
Input: [-1, 3, -1, 8, 5 4]
Output: 2
Explanation: we can change -1, -1, 8 to 3, 4 or 5Example 2
Input: [10, 10, 3, 4, 10]
Output: 0
Explanation: change 3 and 4 to 10Analysis
At first glance of the question, our team offers an initial solution for the candidate, i.e. using sort and greedy. The time complexity is O(n * logn). The solution is listed below: (in Typescript)
拿到题目第一眼，我们的团队成员便直接给候选人提供了一个初步的解决方法，即 使用排序和贪心算法。这一算法的时间复杂度是O(n * logn)。以下是解决方案的Typescript源码：
function minDifference(nums: number[]): number {
if (!nums || nums.length === 0) return undefined;
if (nums.length <= 4) return 0;
nums.sort((a: number, b: number) => a - b);
let min = Number.MAX_SAFE_INTEGER;
for (
let left = 0, right = nums.length - 4;
left < 4 && right < nums.length;
left++, right++
) {
min = Math.min(min, nums[right] - nums[left]);
}
return min;
}Of course, the capability of our team members is not limited to an O(n * logn) solution. We further offer a Partial Sort solution (To learn more about Partial Sort, please refer to the leetcode question: 215. Kth Largest Element in an Array), which has the time complexity of O(n). As we only sort the min 4 and the max 4 numbers in an array. As there is no priority queue in Typescript, we use Java for the solution:
当然，我们团队成员的能力不会止步于时间复杂度O(n * logn)的解决方案。我们进一步提出了基于部分排序的，时间复杂度为O(n)的解决方法 （关于部分排序，可以参考leetcode 215. Kth Largest Element in an Array）。此方法中，我们只需要拿到一个数组中最小的，和最大的4个数字。因为Typescript没有提供PriorityQueue, 因此我们提供了基于Java的解决方法：
public class Solution {
public int minDifference(int[] nums) {
int numsSize = nums.length;
if (numsSize <= 4) {
return 0;
}
// Find the four smallest elements using a fixed-size max heap
PriorityQueue maxHeap = new PriorityQueue<>(
Collections.reverseOrder()
);
for (int num : nums) {
maxHeap.offer(num);
if (maxHeap.size() > 4) {
maxHeap.poll();
}
}
List smallestFour = new ArrayList<>(maxHeap);
Collections.sort(smallestFour);
// Find the four largest elements using a fixed-size min heap
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > 4) {
minHeap.poll();
}
}
List largestFour = new ArrayList<>(minHeap);
Collections.sort(largestFour);
int minDiff = Integer.MAX_VALUE;
// Four scenarios to compute the minimum difference
for (int i = 0; i < 4; i++) {
minDiff = Math.min(
minDiff,
largestFour.get(i) - smallestFour.get(i)
);
}
return minDiff;
}
}The interviewer was, surely, very content when we offered an O(n) solution. The interviewer was also been able to see the way our team members explained the thinking process clearly and neatly. These certainly help the candidate pass this round and finally get the offer from Google.
面试官对我们团队提供的O(n)的方案非常满意。面试官也能够看到我们团队成员帮助候选人提供的解决问题思路的清晰和简洁的解释。这些要素都帮助候选人通过了此轮面试，并最终拿到了Google的offer。
Contact Us
经过我们的强力面试辅助，OA代写，Onsite面试辅助，候选人通过这些面试题的解析和沟通，面试官不仅了解了候选人的编程能力，也看到了我在解决问题过程中清晰的思路和有效的沟通技巧。这些不仅有助于应对Google的面试，同时也能提升我们解决实际编程问题的能力。祝大家面试顺利！
The Candidate observed my problem-solving and thinking process clearly through our interview support service, which is applicable to Google interviews and can also strengthen programming abilities. Wishing everyone luck with their interview!
If you also need our interview assistance services, please contact us immediately.
