記一道超級簡單的 Java 演算法面試題，但無人通過

• 2020 年 2 月 20 日
• 筆記

作者：方誌宏（已獲作者授權轉載，禁止二次轉載）

來源：https://zhuanlan.zhihu.com/p/57859872

這可能是歷史上最簡單的一道 Java 演算法面試題了。

題目很簡單，完成程式碼，判斷一個整數是否是奇數：

public boolean isOdd(int i)  

相信相當數量的人都已經在準備吐槽了，只要看過《編程珠璣》的人都知道這道題的答案和其中極為簡單的道理。不過別著急罵街，不管你信不信，這道筆試題我拿到的答案好多都長這樣：

//@五分鐘學演算法public boolean isOdd(int i) {      if (i % 2 == 1) {          System.out.println("是奇數");      } else {          System.out.println("是偶數");      }  }  

然後編譯一下，發現錯誤了，撓撓頭，頂多改成這樣：

//@五分鐘學演算法public boolean isOdd(int i) {    if (i % 2 == 1) {          return true;      } else {          return false;      }  }  

好吧，我承認我在篩選簡歷的能力可能有一些問題，不過不管你信不信，好多大廠工作了幾年的程式設計師，都會寫出如上風格的程式碼。

於是我繼續進行引導：

我：「這個函數的定義要求返回一個什麼類型的值？」

候選人看了看題干：「布爾類型。」

我：「那麼，你if後面的括弧裡面的表達式的值是一個什麼類型的？」

引導到這一步的時候，依然有高達兩成的候選人選擇了放棄，表示他們不知道。好吧，我真的不知道你們來面試這個職位的信心何在。不過大部分人想了想，還會回答出正確答案：

候選人：「也是布爾類型。」

我：「然後呢？」

有少量候選人雖然沒說出來，但是我能看出來他們覺得這只是一個巧合，並不知道怎麼進行下一步。不過，大多數人想了想之後，還是會優化成如下程式碼：

//@五分鐘學演算法public boolean isOdd(int i) {      return i % 2 == 1;  }  

終於過了第一關了，進行第二關的引導：

我：「那我傳進來一個-1呢？」

將近一半的人在想了想之後會嘴硬地表示他們從小被教導只有自然數才有奇數偶數之分，負數沒有奇偶這一說。剩餘的人接受了這個設定，想了一會兒，改成這樣：

//@五分鐘學演算法public boolean isOdd(int i) {      return i % 2 == 1 || i % 2 == -1;  }  

並且在提示之後優化成這樣：

//@五分鐘學演算法public boolean isOdd(int i) {      return i % 2 != 0;  }  

好吧，這是迄今為止第一個能通過編譯且完全滿足了需求的程式碼實現了。說實話，一開始就寫成這樣的人，如果沒有其他什麼明顯的缺點的話，我這裡基本就能通過了。我承認我的要求比較低，但是來面試的人能直接寫出這樣的真的不太多，粗略地估計的話，大概佔一到兩成吧。

但是這裡還沒完呢，還有最重要的第三關呢：

我：「有更好的辦法嗎？」

候選人：「？」

我：「我覺得取模操作比較慢，有更快的解決方案嗎？」

除了少數人能自己想想就想出來了之外，絕大部分（毫不誇張）候選人表示沒有或者不知道，於是進行下一步提示：

我：「奇數和偶數轉換成二進位有什麼區別？」

相當一部分候選人表示自己不懂什麼叫二進位和位運算，有的還表示java不是c語言，不用研究這些，就跟很多評論會吐槽我在裝逼一樣。少部分候選人想了想，會怯怯地回答。

候選人：「奇數最後一位是1，偶數最後一位是0。」

我：「然後呢？」

這裡很奇怪的點是，大部分能聊到這裡來的候選人會想起來移位操作，我真的不知道是為什麼，雖然這道題確實可以有這種操作：

//@五分鐘學演算法public boolean isOdd(int i) {      return i >> 1 << 1 != i;  }  

但是這根本不是重點好吧！！！

總之，無論如何，能在第三關的各種引導之後，能寫出下面這個結果來的人，真的不多。能一開始沒有任何引導的就寫出來的人，至今只見過兩個，一個我去哪兒都帶著，一個拒了我的offer。

//@五分鐘學演算法public boolean isOdd(int i) {      return (i & 1) == 1;  }  

別以為這就完了！終極boss來了：

我：「這樣是不是比上面取模運算要快？」

候選人：「那當然了，位運算肯定快啊。」

我：「但是我們實際程式碼測試過，發現上面的按位與操作和取模操作，實際運行的時間是差不多的，為什麼呢？」

候選人心裡mmp：「鬧了半天你這是在逗我玩啊？？？」

然而真正能回答出原因來的人，面試過程中我沒見過，可能是大牛都看不上我所在的公司吧。

只有在某公司的時候，一個同事想了想，給出了我正確答案。

難道是我經歷的公司都太low了么……

(點擊空白處查看答案)

▼

編譯器會將對2的指數的取模操作，優化成位運算操作。