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 onsiteinterviews.
最近，我們的PROGRAMHELP團隊為好幾個候選人的Googleonsite面試提供了輔導和代面輔助，他們中的絕大多數在我們團隊成員的幫助下都成功拿下了Google的offer。這個系列我們來分析一下最近幾次Google onsite面試遇到的演算法題，供大家學習。
Onsite 演算法題
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 differencebetween 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 thethinking 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 Googleinterviews and can also strengthen programming abilities. Wishing everyone luck with their interview!
If you also need our interview assistance services, please contact us immediately.
