#50 Coding 面試 - LeetCode #349 Intersection of Two Arrays

原文網址 https://leetcode.com/problems/intersection-of-two-arrays

這一題在原文網址上列為簡易型的題目，看了題目之後，只要你熟悉一些基本的資料結構，應該可以很快想出不錯的解法．題目輸入是兩個 integer array，然後輸出一個 array，這個 array 包含的元素要出現在兩個輸入的 array 裡．

若用最直覺的想法，你可以做一個 for loop 在第一個輸入 array 上，把每一個元素和第二個輸入 array 的元素相比較．以這樣的做法來看，時間複雜度將會是 O(n²)．以這個題目來說，這樣的時間複雜度並不理想．所以得再想想一個比較好的處理方式．

我在寫這題時一開始就想到利用 hash table 來運作，因為 hash table 有極佳的 O(1) 的動作速度．所以一開始把第一個輸入 array 所有的元素透過一個 for loop 加入到 hash table．然後再將第二個輸入 array 利用另一個 for loop 來查看是否有同樣的數字已經存在於 hash table 之中．如果有的話，它就是我們要尋找的對象，但把它加入到輸出的結果裡，這裡是用一個 List 來代表．最後再將整個 List 轉換成 array 輸出，這樣的轉換只需要 O(n). 因此，整個時間複雜度將是 O(n+n+n)．有二個 for loop 和最後的轉換，所以一共是三個 n.程式碼如下:

最後我還發現了 LeetCode 提供了與其他同樣語言解法的比較．上述的解法打敗使用同樣語言 75% 的解法．我想這是以他們電腦執行速度來計算的．由此可見，上述的程式碼在最佳化上還有很大的空間可以改進．

閱讀全文

#49 - 物件導向的最基礎 - Access Modifier

若我們用 Java 語言來做為說明，則 access modifier 有三種，分別是 public, protected, private. 他們分別控制了那些對象能使用他們所定義的東西.

在 https://docs.oracle.com/javase/tutorial/java/javaOO/accesscontrol.html 裡面有一個表格呈現出了整個控制力的對照圖．例如，private method 只能被同一個 class 裡面的 method 所使用，只要超過同一個 class 的範圍是無法使用的．public method 剛好相反，它可以被任何的 class 看到來使用，甚至也可以被其他元件看到來使用．因此，當你將 class, property, method 設定為 public 時，你就要非常地小心．這個稍後說明．最後一個是 protected，它能被同一個 class 裡的東西來使用，而也能被該 class 的 child class 來使用．

Private 的控制力道最嚴格，因為除了在同一個 class 的 method, property 以外，其他人都無法存取．因此，在最初的設計上時比較不會對 private method, class, property 等做太多的說明，甚至會跳過他們．Public 就完全相反了．誠如前面所說，一旦你將 class 設定為 public 時，那表示不止你的程式可以看到來使用，其他人的程式也可以看到來使用，這時候你就要非常小心，因為你得考慮到這個 class 一旦被使用了之後，它所執行的程式碼需要具有什麼意義．同時，也要注意在寫程式時是不是有做一些檢查．

來看一個很笨的例子，假設你今天要設計一個傳送訊息通知的 class，而訊息傳送的功能是透過其他的元件來執行，你需要設計的只是一個簡單的 wrapper ，將該元件包起來，然後只要露出一些你需要提供的功能即可．所以程式碼可能是這樣

public class MessageSender 
{
 private Some.Other.Sender _component;
 
 public void Start()
 {
  _component = new Some.Other.Sender();
  _component.OpenConnection();
 }
 
 public void Send(string message)
 {
  _component.Send(message);
 }
 
 public void End()
 {
  _component.CloseConnection();
 }
}

從上面的程式碼你可以看到 MessageSender class 的 access modifier 是 public，這表示全世界都可以看到它，因此任何人都可以使用它．在這個 class 裡面定義了三個 methods，分別是 Start(), Send(), End()．會這樣設計可能因為你想要讓使用它的人比較清楚知道該如何使用，因為顧名思義看起來就會覺得一開始的時候就要使用 Start()，需要傳送資料時就用 Send()，而最後在結束時就使用 End()．這樣的想法也沒什麼不對，只是漏掉了一點，那就是 public method 是大家都看的到．別人可以看的到不代表他就一定得用它．也就是說，當我 new MessageSender 時，有規定我一定要先呼叫 Start() 嗎 ? 似乎沒有．有規定我最後結束時一定要呼叫 End() 嗎 ? 似乎也沒有．如果我直接呼叫 Send 來傳送字串時，那會發生什麼事呢 ? 答案很明顯，會發生 null object 的現象．

用以上這個笨笨的例子來提醒大家，在設計 public class, public property, public method 時一定要注意到這些 public 的東西被使用時是沒有順序可言的，所以千萬不能自作主張去以為所有人會知道該如何使用，甚至你寫了說明文件該如何使用也不能這樣寫程式．因此，設計 public 時一定要非常地小心，要想到當 public class, public property, public method 是第一個被存取的對象時會發生什麼事．這樣你就會知道上面的程式碼是行不通的，而且相信你也能將上述的程式碼改成一個比較好的程式碼．

閱讀全文