How to: Work at Google - Example Coding/Engineering interview的心得摘要。
這部影片很好地示範coding interview是如何進行及應對面試官問題的方式。影片中是以C++解題，這邊我以較熟悉的Java改寫。本篇只限於影片的前半部部分（整數的集合有排序）。
寫下問題
把面試官提供的問題細節寫下來做為後面問更多問題或解題時的參考。
A:Give you a collection of numbers and find the matching pairs that is equal to a sum that give you as well. e.g. [1, 2, 3, 9] sum=8 [1, 2, 3, 4] sum=8
提出問題
詢問面試官對於問題不清楚的地方，有無空間限制，輸入參數是什麼，想得到什麼樣的結果。
Q:You are looking for a pair of numbers that add up to 8. A:Yes. Q:How are these numbers given? Can I assume that they are in memory, array or someting? A:They are in memory, array and you can assume they are ordered. Q:How about repeating the elements? Can I use a element repeatly? e.g. Use 3rd 4 twice to add up to 8? A:You cannot use the same element at the same index twice, but the same number may appear twice. Q:Are these numbres integer or floating point? Negatives, positives? A:You can assume they will always integers and negatives could happen.
說出先想到的解法
先說出腦袋中想到的可能解法，不論是否為最佳解，藉此讓面試官知道你的思考過程及確實了解問題。
Compare every single possible pair, could have two for-loops, one scanning the whole array, and one starting from I loop and then the J loop from I plus 1 so that I don't repeat the same value and just testing all of them if the sum is equal to the target sum.
分析時間及空間複雜度
對每一次想到的解法分析時間及空間複雜度以評估效能的好壞及思考是否有更加解。
The performance of the first simple solution is quadratic (O(n^2)).
Main.java
package com.abc.demo;
import java.util.List;
public class Main {
public static void main(String[] arges) {
int sum = 8;
System.out.println(hasPairWithSum(List.of(1, 2, 3, 9), sum)); // false
System.out.println(hasPairWithSum(List.of(1, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(2, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 7), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 6), sum)); // false
}
public static boolean hasPairWithSum(final List<Integer> data, int sum) {
for (int i = 0; i < data.size(); i++) {
for (int j = i + 1; j < data.size(); j++) {
if (data.get(i) + data.get(j) == sum) {
return true;
}
}
}
return false;
}
}
思考更加解
第一次直覺想到的解法通常沒那麼好，試著思考及和面試官討論是否有更加解法。
2nd way One for loop start from the first number and use binary search to search the rest elements to see if have the complement. (O(log(n)))
Main.java
package com.abc.demo;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] arges) {
int sum = 8;
System.out.println(hasPairWithSum(List.of(1, 2, 3, 9), sum)); // false
System.out.println(hasPairWithSum(List.of(1, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(2, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 7), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 6), sum)); // false
}
public static boolean hasPairWithSum(final List<Integer> data, int sum) {
for (int i = 0; i < data.size(); i++) {
int fromIndex = i + 1;
int toIndex = data.size();
int result = Arrays.binarySearch(data.toArray(), fromIndex, toIndex, sum - data.get(i));
if (result > 0) {
return true;
}
}
return false;
}
}
3nd way
Iteraring the numbers and moving the higher to lower and lower to higher
if the pairs are too large and too slow. (O(n))
[1, 2, 3, 9] -> 9 is larger then 8 so move higher to lower which is 3.
^
v
[1, 2, 3] -> 3 pair with 1 is 4 which is smaller then 8,
^ move lower to higer which is 2
v
[1, 2, 3] -> 3 pair with 2 is 5 which is smaller then 8,
^ move lower to higher which is 3
If the higer and lower cross then there is no pairs equal to target sum.
別急著寫code
在與面試官討論出認可的解法前別急著動手寫程式碼，不過可以先寫下虛擬碼紀錄解題步驟與細節。
解題前確認輸入和輸出的樣貌
撰寫程式碼前跟面試官確認輸入的參數及輸出的結果的樣貌。
解題時邊寫邊說出想法
撰寫程式碼的過程中同時說出當下這行程式碼的作用等。
Main.java
package com.abc.demo;
import java.util.List;
public class Main {
public static void main(String[] arges) {
int sum = 8;
System.out.println(hasPairWithSum(List.of(1, 2, 3, 9), sum)); // false
System.out.println(hasPairWithSum(List.of(1, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(2, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 7), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 6), sum)); // false
}
public static boolean hasPairWithSum(final List<Integer&t; data, int sum) {
int low = 0; // lower index
int high = data.size() - 1; // higher index
while (low < high) {
if (high > sum) {
high--; // move higher to lower
}
if (data.get(low) + data.get(high) == sum) { // find pairs
return true;
}
low++; // move lower to higher
}
return false;
}
}
題目變化
在解決了原本問題後，有時面試官會修改問題增加難度，例如增加限制條件或修改輸出結果，過程同上。
影片中面試官把原來的問題改為輸入的數字集合不保證是有排序的。
A:The numbers in this collection are not sorted. e.g. [8, 2, 3, 1] sum=8 [6, 4, 2, 1] sum=8
影片中解法我修改如下，我覺得把未配對的數直接記錄下來比較好懂，走訪時檢查這些紀錄中是否有與目前數值搭配的值。
Main.java
package com.abc.demo;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] arges) {
int sum = 8;
System.out.println(hasPairWithSum(List.of(1, 2, 3, 9), sum)); // false
System.out.println(hasPairWithSum(List.of(1, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(2, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(2, 2, 4, 4), sum)); // true
System.out.println(hasPairWithSum(List.of(1, 3, 4, 6), sum)); // false
System.out.println(hasPairWithSum(List.of(8, 2, 3, 1), sum)); // false
System.out.println(hasPairWithSum(List.of(6, 4, 2, 1), sum)); // true
}
public static boolean hasPairWithSum(final Listt<Integer> data, int sum) {
Set<Integer> complements = new HashSet<>(); // the container to store the iterated values as the complements.
for (int n : data) { // iterating the numbers in collection
if (complements.contains(sum - n)) { // check if the iterated values set has complement of current value, if yes then paired
return true;
}
complements.add(n); // add the value without paring to iterated values set
}
return false;
}
}
後來發現原來這題類似LeetCode的經典題two sum。
沒有留言:
張貼留言