­

各大公司面試題分類整理

前言

本人小白一枚,從18年入職工作到現在,工資不高,所在業務受重視程度更低。所以想趁著在家辦公的時間,看看外面的世界。下面對面試過程中的問題進行分類匯總,這些問題的答案有個人認知、有參考他人的觀點,也有一些直接引用別人的文章。本文給出的答案只是一個引子,如果想要深入探究還需要各位通過其他渠道進行詳細了解。

由於本人知識有限,答案不免有不足或者錯誤。還望各位犀利指出,小白一定積極改正,進行勘誤。

面試題匯總

工作相關篇

Q1: 自己所做過的項目中難點以及如何解決的,介紹系統的業務架構和技術架構
這是一個必問題,所以需要提前準備好項目中的難點以及自己的解決方案。如果是自己遇到並解決的最好,如果自己沒有遇到過,那麼把項目中其他人解決的難點融會貫通也可。總之:要有亮點,而且自己是深入思考和深入理解的。

Q2: 服務突然RT增大,後續又恢復了,如何定位

  1. 可能是網路抖動,導致介面短暫超時
  2. gc影響

Java篇

Java基礎

Q1: Java環境變數classpath和path的區別

  1. path環境變數:系統用來指定可執行文件的完整路徑,即使不在path中設置JDK的路徑也可執行JAVA文件,但必須把完整的路徑寫出來
  2. classpath環境變數:java查找類的路徑

Q2: 重寫和重載的區別,構造函數可以重寫嗎

class Person {
    String name;
    public Person() {}
    public Person(String name) {this.name = name;}
    public void talk() {System.out.println("person talk");}
}
class Student extends Person {
    String stuNumber;
    public Student() {}
    public Student(String name, String stuNumber) {
        super(name);
        this.stuNumber = stuNumber;
    }
    @Override
    public void talk() {System.out.println("student talk");}
}

重寫:需要有繼承關係,子類重寫父類的方法。一般使用@Override註解標識,不標識也無所謂。上面程式碼中Student類就重寫了Person類的talk方法。

重載:函數名相同,參數個數不同或者參數類型不同。注意方法返回值不同是不算重載的。上面程式碼中對構造函數就是通過參數個數不同進行重載。

構造函數不能被重寫,因為重寫要求方法名一致。而構造函數的方法名就是類名。子類不可能和父類同名,所以也不可能有相同的構造函數。所以構造函數不能重寫,但是可以重載。

Q3: 介紹一些常用的Java工具命令

命令 說明
jps 虛擬機進程狀態工具,可以列出虛擬機進程
jstat 虛擬機統計資訊監視工具,監視虛擬機各種運行狀態資訊
jinfo Java配置資訊工具
jmap 生成堆轉儲快照

集合

Q1: HashMap實現原理

請參考:Java HashMap工作原理及實現

Q2: HashMap為什麼執行緒不安全

請參考:HashMap為什麼不是執行緒安全?

Q3: currentHashMap如何保證執行緒安全

請參考:高並發編程系列:ConcurrentHashMap的實現原理(JDK1.7和JDK1.8)

Q4: Java容器有哪些?哪些是同步容器,哪些是並發容器?

詳細可參考:Java同步容器和並發容器

Java容器有Map、List、Set

Java中同步容器分為2類:

  1. Vector/Stack/HashTable,其方法都是同步方法,使用synchronized修飾
  2. Collections 類中提供的靜態工廠方法創建的類(由 Collections.synchronizedXxxx 等方法)

Java中的並發容器:
JDK 的 java.util.concurrent 包(即 juc)中提供了幾個非常有用的並發容器。

  1. CopyOnWriteArrayList – 執行緒安全的 ArrayList
  2. CopyOnWriteArraySet – 執行緒安全的 Set,它內部包含了一個 CopyOnWriteArrayList,因此本質上是由 CopyOnWriteArrayList 實現的。
  3. ConcurrentSkipListSet – 相當於執行緒安全的 TreeSet。它是有序的 Set。它由 ConcurrentSkipListMap 實現。
  4. ConcurrentHashMap – 執行緒安全的 HashMap。採用分段鎖實現高效並發。
  5. ConcurrentSkipListMap – 執行緒安全的有序 Map。使用跳錶實現高效並發。
  6. ConcurrentLinkedQueue – 執行緒安全的無界隊列。底層採用單鏈表。支援 FIFO。
  7. ConcurrentLinkedDeque – 執行緒安全的無界雙端隊列。底層採用雙向鏈表。支援 FIFO 和 FILO。
  8. ArrayBlockingQueue – 數組實現的阻塞隊列。
  9. LinkedBlockingQueue – 鏈表實現的阻塞隊列。
  10. LinkedBlockingDeque – 雙向鏈表實現的雙端阻塞隊列。

執行緒

Q1: 如何讓執行緒A在執行緒B執行之後再執行

  1. CountDownLatch。執行緒A中 latch.await(),執行緒B中latch.countDown()
  2. wait()、notify()。可能存在執行緒B的notify()先執行,導致執行緒A一直處於阻塞狀態

Q2: ThreadLocal的理解和適用場景

請參考:Java中的ThreadLocal詳解

Thread類裡面有2個變數,threadLocals和inheritableThreadLocals,類型均為ThreadLocalMap。

為什麼Thread類使用map,而不是直接一個value的存儲( T value),如果是一個T value的話,這個值就是多個執行緒共享的,會出現問題。ThreadLocal就是為了解決該問題而來的

使用ThreadLocal注意事項:
ThreadLocalMap中的Entry的key使用的是ThreadLocal對象的弱引用,在沒有其他地方對ThreadLoca依賴,ThreadLocalMap中的ThreadLocal對象就會被回收掉,但是對應的value不會被回收,這個時候Map中就可能存在key為null但是value不為null的項,這需要實際的時候使用完畢及時調用remove方法避免記憶體泄漏。

Q3: 一個執行緒的生命周期有哪幾種狀態?它們之間如何流轉的

請參考:Java多執行緒學習(三)—執行緒的生命周期

Q4: 執行緒池提交流程

Q5: 執行緒池中任務隊列已滿,如何處理

  • AbortPolicy:直接拋出RejectedExecutionException異常。是Executors裡面默認執行緒池的默認處理策略
  • DiscardPolicy:do nothing
  • DiscardOldestPolicy:拋棄最老的任務,執行新的
  • CallerRunsPolicy:調用執行緒執行

Q6: 保證執行緒安全的方式

  • automic:使用提供的原子類
  • syntronized:同步程式碼塊
  • lock:鎖
  • volatile:保證可見性

Q1: 同步方法的鎖是類還是對象
同步方法默認用this或者當前類class對象作為鎖;
同步程式碼塊是通過傳入的對象作為鎖。

Q2: 同步方法A調用同步方法B,能進入嘛
可以,因為synchronized是可重入鎖

Q3: synchonized和ReentrantLock的區別
不同點

  1. synchonized是java的關鍵字;ReentrantLock是類
  2. synchonized是非公平鎖;ReentrantLock默認是非公平鎖,但是有公平鎖和非公平鎖兩種實現方式。
  3. synchonized可用在同步程式碼塊、同步方法上;ReentrantLock的使用方式需要lock()unlock()

相同點

  1. 兩者都是可重入鎖
  2. 都是同步阻塞方式

Q4: 什麼是活鎖、飢餓、無鎖、死鎖?怎麼檢測一個執行緒是否擁有鎖

死鎖:
是指兩個或兩個以上的進程(或執行緒) 在執行過程中,因 爭奪資源而造成的一種互相等待 的現象,若無外力作用,它們都將無法推進下去。此時稱系統處於死鎖狀態或系統產生了死鎖,這些永遠在互相等待的進程稱為死鎖進程。

死鎖的條件:

  1. 互斥: 執行緒對資源的訪問是排他性的,如果一個執行緒對佔用了某資源,那麼其他執行緒必須處於等待狀態,直到資源被釋放。

  2. 請求和保持: 執行緒T1至少已經保持了一個資源R1佔用,但又提出對另一個資源R2請求,而此時,資源R2被其他執行緒T2佔用,於是該執行緒T1也必須等待,但又對自己保持的資源R1不釋放。

  3. 不可剝奪: 執行緒已獲得的資源,在未使用完之前,不能被其他執行緒剝奪,只能在使用完以後由自己釋放。

  4. 循環等待

活鎖
是指執行緒1可以使用資源,但它很禮貌,讓其他執行緒先使用資源,執行緒2也可以使用資源,但它很紳士,也讓其他執行緒先使用資源。這樣你讓我,我讓你,最後兩個執行緒都無法使用資源。

舉個例子:馬路中間有條小橋,只能容納一輛車經過,橋兩頭開來兩輛車A和B,A比較禮貌,示意B先過,B也比較禮貌,示意A先過,結果兩人一直謙讓誰也過不去。

飢餓
是指如果執行緒T1佔用了資源R,執行緒T2又請求封鎖R,於是T2等待。T3也請求資源R,當T1釋放了R上的封鎖後,系統首先批准了T3的請求,T2仍然等待。然後T4又請求封鎖R,當T3釋放了R上的封鎖之後,系統又批准了T4的請求……,T2可能永遠等待。

不公平鎖能夠提高吞吐量但不可避免的會造成某些執行緒的飢餓,或者優先順序低的執行緒容易產生飢餓

無鎖:
無鎖,即沒有對資源進行鎖定,即所有的執行緒都能訪問並修改同一個資源,但同時只有一個執行緒能修改成功。無鎖典型的特點就是一個修改操作在一個循環內進行,執行緒會不斷的嘗試修改共享資源,如果沒有衝突就修改成功並退出否則就會繼續下一次循環嘗試。所以,如果有多個執行緒修改同一個值必定會有一個執行緒能修改成功,而其他修改失敗的執行緒會不斷重試直到修改成功。CAS 原理及應用即是無鎖的實現。

檢測執行緒是否有鎖
Thread.holdsLock(Object obj):當且僅當 當前執行緒擁有obj對象鎖的時候,返回true
該方法用例斷言打當前執行緒是否持有鎖。assert Thread.holdsLock(obj);

Q5: synchronized實現原理

Q6: java中悲觀鎖、樂觀鎖的例子

  • Java中synchronized和ReentrantLock等獨佔鎖就是悲觀鎖思想的實現。
  • java.util.concurrent.atomic包下面的原子變數類就是使用了樂觀鎖的一種實現方式CAS實現的

jvm

Q1: 介紹一些了解的JVM參數

參數 說明 備註
-Xms 最小堆大小 一般-Xms和-Xmx大小相等,避免記憶體的擴展
-Xmx 最大堆大小 一般-Xms和-Xmx大小相等,避免記憶體的擴展
-Xmn 年輕代大小 其中分了1個Eden和2個Survivor;默認比例 8:1
-XX:SurvivorRatio eden和survivor的比例 默認8:1
-XX:PermSize 永久代大小 -XX:PermSize與-XX:MaxPermSize大小最好一致,避免運行時自動擴展
-XX:MaxPermSize 永久帶最大值 -XX:PermSize與-XX:MaxPermSize大小最好一致
-XX:+UserConcMarkSweepGC 使用CMS收集器

Q2: 為什麼 Java 要採用垃圾回收機制,而不採用 C/C++的顯式記憶體管理

在C++中,對象所佔的記憶體在程式結束運行之前一直被佔用,在明確釋放之前不能分配給其它對象;而在Java中,當沒有對象引用指向原先分配給某個對象 的記憶體時,該記憶體便成為垃圾。 垃圾回收能自動釋放記憶體空間,減輕編程的負擔,JVM的一個系統級執行緒會自動釋放該記憶體塊。釋放無用記憶體,避免記憶體泄漏

Java禁止顯示記憶體回收,jvm決定回收時機,而且避免開發人員忘記釋放記憶體的問題

Q3: JVM記憶體模型

Q4: JVM記憶體分配策略

  1. 對象優先分配在Eden區,當Eden區沒有足夠空間進行分配時,虛擬機將發起一次Minor GC。垃圾收集期間虛擬機對象全部無法放入Survivor空間,通過分配擔保機制提前轉移到老年代去。
  2. 大對象直接進入老年代
  3. 長期存活的對象進入老年代,可以通過-XX:MaxTenuringThreshold設置年齡
  4. 動態對象年齡判定。為了能更好地適應不同程式的記憶體狀況,HotSpot虛擬機並不是永遠要求對象的年齡必須達到-XX:MaxTenuringThreshold才能晉陞老年代,如果在Survivor空間中相同年齡所有對象大小的總和大於Survivor空間的一半,年齡大於或等於該年齡的對象就可以直接進入老年代,無須等到-XX:MaxTenuringThreshold中要求的年齡

Q5: 有哪些垃圾回收演算法

  • 標記-清除:會產生記憶體碎片
  • 標記-複製:年輕代採用該演算法進行垃圾收集
  • 標記-整理:讓所有存活的對象都向記憶體空間一端移動,延遲增大

類載入

關於類載入器看這一篇文章就夠了。深入理解Java類載入機制。但是這篇文章最後有一個錯誤:下面圖片中此時的counter2=1應該是counter2=0

Q1: classLoader和Class.forName()的區別

java中class.forName()和classLoader都可用來對類進行載入。
class.forName()前者除了將類的.class文件載入到jvm中之外,還會對類進行解釋,執行類中的static塊。
而classLoader只干一件事情,就是將.class文件載入到jvm中,不會執行static中的內容,只有在newInstance才會去執行static塊。
Class.forName(name, initialize, loader)帶參函數也可控制是否載入static塊。並且只有調用了newInstance()方法採用調用構造函數,創建類的對象

MySQL篇

Q1: MySQL存在哪些索引類型

  1. 唯一索引
  2. 全文索引
  3. 聯合索引
  4. 普通索引

Q2: InnoDB為什麼採用B+樹的索引結構

請參考騰訊技術工程的文章:深入理解 Mysql 索引底層原理

Q3: 介紹聚簇索引、非聚簇索引、索引覆蓋

請參考文章:mysql聚簇索引和非聚簇索引

Q4: 如何提高SQL性能,工作中SQL優化經驗

提高SQL的性能我認為一定要讓MySQL選擇正確的索引。

在工作中,小白曾優化過系統中的SQL。其體現主要表現在以下幾個方面(這只是小白在工作中遇到的,跟各位遇到的應該會有不同哦):

  1. MySQL錯誤選擇索引
  2. 欄位類型錯誤導致沒走索引
  3. 本可使用索引覆蓋的SQL語句,卻回表查了多餘數據

Q5: MySQL資料庫隔離級別

請參考:Mysql資料庫隔離級別

Spring篇

Q1: 介紹Spring IOC和AOP

請參考:深入理解Spring兩大特性:IoC和AOP

IOC:控制反轉。IOC之前對象A依賴對象B時,需要A主動去通過new創建B的實例,控制權是在對象A上。IOC就是將對象的控制權交給IOC容器處理。

AOP:面向切面編程(AOP)就是縱向的編程。比如業務A和業務B現在需要一個相同的操作,傳統方法我們可能需要在A、B中都加入相關操作程式碼,而應用AOP就可以只寫一遍程式碼,A、B共用這段程式碼。並且,當A、B需要增加新的操作時,可以在不改動原程式碼的情況下,靈活添加新的業務邏輯實現。AOP主要一般應用於簽名驗簽、參數校驗、日誌記錄、事務控制、許可權控制、性能統計、異常處理等

Q2: AOP如何實現

Spring通過動態代理實現AOP。

請參考:從代理機制到Spring AOP

Q3: Spring如何實現事務管理

請參考:可能是最漂亮的Spring事務管理詳解

Q4: Spring事務傳播機制

請參考:Spring事務傳播行為詳解

Redis篇

Q1: redis如何實現分散式鎖

使用setnx key value實現,並使用expire key 設置超時時間。

這種方式存在的問題:這2步操作由於不是一個事務,所以可能出現設置超時時間失敗的問題。如果超時時間設置失敗則會導致該key永不過期,佔用記憶體。

解決方式:

  1. 可使用lua腳本自己編寫,使之變成一個原子性操作
  2. redis提供了SET key value [EX seconds] [PX milliseconds] [NX|XX]

Q2: redis有支援幾種數據結構

String、List、Set、Zset、Map、GEO、Bitmap

Q3: 字元串數據結構底層實現

Redis的字元串底層由SDS簡單動態字元串實現。

特性

  1. 空間預分配:當修改字元串並需要空間擴展時,分為以下2種情況:
    1. 擴展之後空間小於1M,則預分配與已使用空間一樣大小的空間(已使用空間包含擴展之後的字元串)
    2. 擴展之後空間大於1M,則直接分配1M
  2. 惰性釋放:為了避免釋放之後再擴展的問題,redis採用了惰性釋放策略,使用free欄位來記錄未使用的長度,等待使用。同時也提供了相關的API再有需要時釋放空間。

Q4: Map數據結構底層實現

Redis的字典使用哈希表作為底層實現,一個哈希表裡面可以有多個哈希表節點,而每個哈希表節點就保存了字典中的一個鍵值對。

字典數據結構中是一個哈希表數組,共有2個哈希表。在擴容時使用。

Redis的hash演算法使用MurmurHash2演算法。

Q5: Redis過期鍵刪除策略

定時刪除: 在設置鍵的過期時間的同時,創建一個定時器(timer),讓定時器在鍵的過期時間來臨時,立即執行對鍵的刪除操作。
優點: 記憶體友好,可以實時釋放記憶體
缺點: 對CPU不友好,為了刪除過期鍵,大量佔用CPU

惰性刪除: 放任鍵過期不管,但是每次從鍵空間中獲取鍵時,都檢查取得的鍵是否過期,如果過期的話,就刪除該鍵;如果沒有過期,就返回該鍵
優點: 對CPU友好,只有使用到的時候才判斷
缺點: 對記憶體不友好
實現: 通過expireIfNeeded函數,讀寫redis命令之前都會調用該函數,判斷是否需要過期該鍵

定期刪除: 每隔一段時間,程式就對資料庫進行一次檢查,刪除裡面的過期鍵。至於要刪除多少過期鍵,以及要檢查多少個資料庫,則由演算法決定
優點: 兼顧記憶體和CPU
實現: Redis的伺服器周期性操作redis.c/serverCron函數執行時,activeExpireCycle函數就會被調用。函數每次運行時,都從一定數量的資料庫中取出一定數量的隨機鍵進行檢查,並刪除其中的過期鍵。

Q6: redis的淘汰策略

  • noeviction(默認策略):對於寫請求不再提供服務,直接返回錯誤(DEL請求和部分特殊請求除外)
  • allkeys-lru:從所有key中使用LRU演算法進行淘汰
  • volatile-lru:從設置了過期時間的key中使用LRU演算法進行淘汰
  • allkeys-random:從所有key中隨機淘汰數據
  • volatile-random:從設置了過期時間的key中隨機淘汰
  • volatile-ttl:在設置了過期時間的key中,根據key的過期時間進行淘汰,越早過期的越優先被淘汰

Q7: zset的底層實現

跳躍表。可參考通俗易懂的Redis數據結構基礎教程

Kafka篇

Q1: Kafka如何保證高性能和可靠性

請參考:Kafka 數據可靠性深度解讀

畫外音:該文章需要細細閱讀,理解每一塊內容。只要明白了該文章里所說內容,應對面試中的Kafka面試題應該不成問題。

Q2: Kafka支援事務嘛

請參考:Kafka 設計解析(八):Kafka 事務機制與 Exactly Once 語義實現原理

Q3: Kafka中zookeeper的作用

  • 再平衡消費者
  • 選主

編程題

基本都是Leetcode的中等難度的題目,各位小夥伴可以刷起來了

Q1: 求A/B,不能使用除法

詳細講解請看:兩數相除

public int divide(int dividend, int divisor) {
    if (dividend == 0) {
      return 0;
    }
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
      return Integer.MAX_VALUE;
    }
    int flag = -1;
    if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) {
      flag = 1;
    }
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    return flag * getRes(a, b);
  }

  private int getRes(long a, long b) {
    if (a < b) {
      return 0;
    }
    int count = 1;
    long tmp = b;
    while (a > b << 1) {
      b = b << 1;
      count = count << 1;
    }
    return count + getRes(a - b, tmp);
  }

Q2: 給定包含n個數字的數組,將這些數字進行拼接,求拼接成的最大數值

Q3: 鏈表中找到倒數第K個節點

Q4: 買賣股票的最佳時機

為了找到最大利潤,我們需要找到最小的買入價格。假設nums[i]是最低的買入價格,nums[j]是最高的買入價格。當滿足i < j時的最大利潤即為nums[j] - nums[i]

詳細描述請參考:121. 買賣股票的最佳時機

public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len <= 1) {
        return 0;
    }
    // 存儲最小的買入價格
    int minBuyPrice = prices[0];
    
    // 存儲最高的賣出價格
    int maxSellPrice = 0;
    
    for (int i = 1; i < len; i++) {
        // 計算最高的賣出價格:當前最高賣出價格與當天的賣出價格對比。其中price[i]-minBuyPrice就是當天的賣出價格
        maxSellPrice = Math.max(maxSellPrice, prices[i] - minBuyPrice);
        
        // 更新最小的買入價格
        minBuyPrice = Math.min(minBuyPrice, prices[i]);
    }
    return maxSellPrice;
}

Q5: 複製帶隨機指針的鏈表

Q6: 消除816。例如原字元串12881616,最終返回12。12881616 -> 12816 -> 12

提示:使用棧數據結構

Q7: 數組中奇數、偶數數量相同,交換內容最終使得奇數下標存儲奇數,偶數下標存儲偶數

Q8: leetcode 154題

鏈接:154. 尋找旋轉排序數組中的最小值II

解題思路,歡迎查閱小白的個人部落格:154. 尋找旋轉排序數組中的最小值II

Q9: 單鏈表結構,每個節點表示0-9的數字。給定2個鏈表,進行求和。例如 9->9和2->1。求和結果是1->2->2

三種思路,請參考:Leetcode 445. 兩數相加 II

Q10:實現一個LRU數據結構,插入和查詢要求$O(1)$時間複雜度

  1. 可以使用LinkedHashMap直接實現。
  2. 使用一個LinkedList存儲key的順序嗎,到達O(1)的插入,使用map存儲k-v映射關係,達到O(1)的查詢複雜度
public class Main {
    // 使用map存儲結構中已有的key,便於O(1)的查詢複雜度
	HashMap<String, Integer> map = new HashMap<>();
	// 存儲key的順序,對於最近訪問的key,移動到隊列的頭部
	LinkedList<String> lruKeys = new LinkedList<>();
	// LRU結構的大小
	int size = 4;

	public static void main(String[] args) {
		Main main = new Main();
		main.set("math", 100);
		main.set("chiness", 200);
		main.set("english", 210);
		main.print();

		System.out.println("-------");

		main.set("music", 250);
		main.set("draw", 250);
		main.print();

		System.out.println("-------");
		main.get("english");
		main.print();
	}

	private void print() {
		for (String key : lruKeys) {
			System.out.println(key + " = " + map.get(key));
		}
	}

	private void set(String key, int val) {
		if (map.containsKey(key)) {
			map.put(key, val);
			moveToFirst(key);
		} else {
			if (lruKeys.size() == size) {
				String removeKey = lruKeys.removeLast();
				map.remove(removeKey);
			}
			map.put(key, val);
			lruKeys.addFirst(key);
		}
	}

	private int get(String key) {
		if (map.containsKey(key)) {
			moveToFirst(key);
			return map.get(key);
		}
		return 0;
	}

	private void moveToFirst(String key) {
		lruKeys.remove(key);
		lruKeys.addFirst(key);
	}
}

Q11:最長迴文子串

Leetcode 5:最長迴文子串

思維題

Q1: 36輛車,6個跑道,最少多少次可以篩選出跑的最快的3輛車(不可用表計時)

8次 = 6 + 1 + 1。

分析:

  1. 首先將36輛車隨機分成6組進行比賽,對每組進行排名並選擇出每組的第一名(6次)
  2. 將步驟1結果的6輛車再進行一輪比賽,並選擇出前三名,假設分別為A車、B車、C車(1次)
  3. 然後從A車所在的組(步驟1的分組)選出第2、3名,從B車所在的組(步驟1的分組)選出第2名。(因為A車第一,所以存在A車所在組的第2、3名比B、C車塊的可能性;同理B車所在組的第2名存在比C車塊的可能性;由於只選最快的3輛車,所以無需從C車所在組進行選車)
  4. 然後將步驟3選擇出來的3輛車再加上A車、B車、C車進行一次比賽,選擇出前三名(1次)
  5. 步驟4的結果就是最快的3輛車

Q2: 1000w個數據中找出重複的

使用bitmap。不要使用布隆過濾器,因為布隆過濾器並非100%準確。

Q3: 有2個玻璃球和一棟256層的高樓,如何快速定位到使得玻璃球摔碎的最低樓層

方案一:拿玻璃球一層層由低到高測試。

方案二:二分法。但是如果在中間的時候玻璃球碎了,那就無法再二分了,只能一層層的實驗。

方案三:拿玻璃球測試樓層為n,2n,3n….這種。如果玻璃球在2n層摔壞了,則那另一個玻璃球從n+1 到 2n-1的樓層逐層實驗。

其實可以看出來方案三中n=1時,就是方案一逐層實驗;當n=128時,就是方案二。那我們如何求出n來使得結果最優呢?

假設使得玻璃球碎的樓層是256,步長n。則此時的次數為:256/n+n。要想該數值最小,則需要256/n = n。所以n = 16。

面試心得

面試前

  1. 準備簡歷,並保證簡歷中沒有錯別字。
  2. 簡歷中技能欄和項目欄中的項目一定要熟練。對於某技術熟悉就是熟悉、了解就是了解,要實事求是。否則被面試官問住是一件很尷尬的事情
  3. 準備1~2分鐘的自我介紹
  4. 先拿幾家不想去公司試試手,因為一開始面試被pass的幾率很大
  5. 臨近面試時,提前準備幾個給面試官的問題,面試之後進行溝通。

面試中

  1. 不要緊張,遇到問題會就是會,不會就是不會。即使不會也可以說一下自己的思考和理解。
  2. 針對編程題,需要充分考慮邊界問題和異常情況

面試後

  1. 對剛才的面試進行復盤。針對不會的問題或者答得不好的問題,進行總結並收集相關知識點。
Tags: