之前發了這篇iOS面試總結（2020年6月），沒想到挺受大家歡迎，本來是沒打算為它寫答案，但有幾個人建議我最好出一篇答案，提的人多了我就答應了下來，因為最近比較忙，斷斷續續總算補完了，就有了這篇文章，希望它對大家還有用處，這些都屬于參考答案，如果大家感覺有不對不準確的地方也歡迎指出，我會及時更新，

關于面試題

打個比方，如果把找作業理解成考大學，面試就是高考，市面上的“真題”就是模擬試卷，我們會很容易傾向于在面試前尋找對應公司的面試“真題”，重點準備，期待“押題”成功，但實際上，即使面試同一家公司，它會有不同部門，不同業務線，不同面試官，即使遇到同一面試官，他也不一定就每次考察完全一樣的內容，想想高考中那些考的好的同學，他們肯定不是靠“押題”才能取得好成績吧，他們大多靠的是平常積累及對知識點靈活掌握，那面試也一樣啊，執著于搜題，把面試題當做重點進行“復習”，還不如自己劃出“考綱”，各個知識點逐一檢查掌握情況，復習的更全面呢，

我對于面試題的看法一直是相對保守的，這類文章一般只是內容搬運，它會存在一些偏差和誤讀，最重要的那就是幾道題往那一扔，并沒有產出有價值的東西，這也是為什么我上篇面試總結，會加了一些面試技巧，整理面試題時，也沒提他們是出自哪家公司，就是不希望大家把題目區別看待，

說了這些并不是說面試題沒用啊，而是希望大家不要迷信面試題，更多地去關注那些有質量有深度的技術文章，面試考核的是知識點而不是具體的某些題目，面試題的作用在于，衡量我們的知識掌握情況，便于我們查漏補缺，越說越像是針對一次“考試”了??，

總結不易，希望這份參考答案能對你有所幫助，如果想持續關注我，歡迎訂閱微信公眾號：iOS成長之路，

面試題及參考答案

Swift

1、Swift中struct和class有什么區別？

struct是值參考，更輕量，存放于堆疊區，class是型別參考，存放于堆區，struct無法繼承，class可繼承，

2、Swift中的方法呼叫有哪些形式？

答：直接派發、函式表派發、訊息機制派發，派發方式受宣告位置，參考型別，特定行為的影響，為什么Swift有這么多派發形式？為了效率，

參考文章：深入理解 Swift 派發機制

3、Swift和OC有什么區別？

Swift和OC的區別有很多，這里簡要總結這幾條：

4、從OC向Swift遷移的時候遇到過什么問題？

可以參考這篇文章：OC專案轉Swift指南 里的混編注意事項，

5、怎么理解面向協議編程？

面向物件是以物件的視角觀察整體結構，萬物皆為物件，

面向協議則是用協議的方式組織各個類的關系，Swift底層幾乎所有類都構建在協議之上，

面向協議能夠解決面向物件的菱形繼承，橫切關注點和動態派發的安全性等問題，

參考喵神的面向協議編程與 Cocoa 的邂逅 (上)

OC語法

1、Block是如何實作的？Block對應的資料結構是什么樣子的？__block的作用是什么？它對應的資料結構又是什么樣子的？

block本質是一個物件，底層用struct實作，

資料結構如下：

struct Block_descriptor {
    unsigned long int reserved;
    unsigned long int size;
    void (*copy)(void *dst, void *src);
    void (*dispose)(void *);
};

struct Block_layout {
    void *isa;
    int flags;
    int reserved;
    void (*invoke)(void *, ...);
    struct Block_descriptor *descriptor;
    /* Imported variables. */
};

• isa 指標，所有物件都有該指標，用于實作物件相關的功能，

• flags，用于按 bit 位表示一些 block 的附加資訊，本文后面介紹 block copy 的實作代碼可以看到對該變數的使用，

• reserved，保留變數，

• invoke，函式指標，指向具體的 block 實作的函式呼叫地址，

• descriptor， 表示該 block 的附加描述資訊，主要是 size 大小，以及 copy 和 dispose 函式的指標，

• variables，capture 過來的變數，block 能夠訪問它外部的區域變數，就是因為將這些變數（或變數的地址）復制到了結構體中，

__block的作用是可以獲取對應變數的指標，使其可以在block內部被修改，通過反編譯的代碼我們可以看到該物件是這樣的：

struct __Block_byref_i_0 {
    void *__isa;
    __Block_byref_i_0 *__forwarding;
    int __flags;
    int __size;
    int val; //變數名
};

對于block的深入了解，可以參考《Objective-C高級編程》第二章或者唐巧的這篇談Objective-C block的實作

2、GCD中的Block是在堆上還是堆疊上？

堆上，可以通過block的isa指標確認，

3、NSCoding協議是干什么用的？

一種編碼協議，歸檔時和解檔時需要依賴該協議定義的編碼和解碼方法，Foundation和Cocoa Touch中的大部分類都遵循了這個協議，一般被NSKeyedArchiver做自定義物件持久化時使用，

4、KVO的實作原理

利用Runtime生成一個中間物件，讓原物件的isa指標指向它，然后重寫setter方法，插入willChangeValueForKey和didChangeValueForKey方法，當屬性變化時會呼叫，會呼叫這兩個方法通知到外界屬性變化，

5、NSOperation有哪些特性，比著GCD有哪些優點，它有哪些API？

NSOperation是對GCD的封裝，具有面向物件的特點，可以更方便的進行封裝，可以設定依賴關系，

API可以查看NSOperation檔案，

6、NSNotificaiton是同步還是異步的，如果發通知時在子執行緒，接收在哪個執行緒？

同步，子執行緒，

UI

1、事件回應鏈是如何傳遞的？

手勢的點擊會發生兩個重要事情，事件傳遞和事件回應，

事件傳遞：從UIApplication開始，到window，再逐步往下層（子視圖）找，直到找到最深層的子視圖，其為first responder，用到的判斷方法是pointInside:withEvent和hitTest:withEvent，

事件回應：從識別到的視圖（first responder）開始驗證能否回應事件，如果不能就交給其上層（父視圖）視圖，如果能相應將不再往下傳遞，如果直到找到UIApplication層還沒有相應，那就忽略該次點擊，用到的判斷方法是touchesBegan:withEvent、touchesMoved:withEvent等，

這兩個程序大致的相反的，

2、什么是異步渲染？

異步渲染就是在子執行緒進行繪制，然后拿到主執行緒顯示，

UIView的顯示是通過CALayer實作的，CALayer的顯示則是通過contents進行的，異步渲染的實作原理是當我們改變UIView的frame時，會呼叫layer的setNeedsDisplay，然后呼叫layer的display方法，我們不能在非主執行緒將內容繪制到layer的context上，但我們單獨開一個子執行緒通過CGBitmapContextCreateImage()繪制內容，繪制完成之后切回主執行緒，將內容賦值到contents上，

這個步驟可以參照YYText中YYTextAsyncLayer.m檔案中的實作方式，

3、layoutsubviews是在什么時機呼叫的？

• init初始化不會觸發，

• addSubview時，

• 設定frame且前后值變化，frame為zero且不添加到指定視圖不會觸發，

• 旋轉Screen會觸發父視圖的layoutSubviews，

• 滾動UIScrollView引起View重新布局時會觸發layoutSubviews，

4、一張圖片的展示經歷了哪些步驟？

這個可以參考我之前寫的一篇文章iOS開發圖片格式選擇 中的前半部分內容，

5、什么是離屏渲染，什么情況會導致離屏渲染？

如果要在顯示屏上顯示內容，我們至少需要一塊與螢屏像素資料量一樣大的frame buffer，作為像素資料存盤區域，如果有時因為面臨一些限制，無法把渲染結果直接寫入frame buffer，而是先暫存在另外的記憶體區域，之后再寫入frame buffer，那么這個程序被稱之為離屏渲染，

以陰影為例，為什么它會導致離屏渲染，因為GPU的渲染是遵循“畫家演算法”，一層一層繪制的，但陰影很特殊，它需要全部內容繪制完成，再根據外輪廓進行繪制，這就導致了，陰影這一層要一直占據一塊記憶體區域，這就導致了離屏渲染，

類似導致離屏渲染的情況還有：

• cornerRadius+clipsToBounds
• group opacity 組透明度
• mask 遮罩
• UIBlurEffect 毛玻璃效果

有一篇文章詳細的討論了這些情況：關于iOS離屏渲染的深入研究

如果你正在跳槽或者正準備跳槽不妨動動小手，添加一下咱們的交流群1012951431來獲取一份詳細的大廠面試資料為你的跳槽多添一份保障，

6、CoreAnimation這個框架的作用什么，它跟UIKit的關系是什么？

CoreAnimation雖然直譯是核心影片，但它其實是一個影像渲染框架，影片實作只是它的一部分功能，

看這張圖我們可以知道，它是UIKit和AppKit的底層實作，位于Metal、Core Graphics和GPU之上之上，

蘋果官方檔案：About Core Animation

參考計數

1、ARC方案的原理是什么？它是在什么時候做的隱式添加release操作？

ARC(Automatic Reference Cunting)自動參考計數，意即通過LLVM編譯器自動管理對應的參考計數狀態，ARC開啟時無需再次鍵入retain或者release代碼，

它是在編譯階段添加retain或者release代碼的，

2、回圈參考有哪些場景，如何避免？

回圈參考及兩個及以上物件出現參考環，導致物件無法釋放的情況，一般在block，delegate，NSTimer時容易出現這個問題，

解決方案就是讓環的其中一環節實作弱參考，

3、為什么當我們在使用block時外面是weak 宣告一個weakSelf，還要在block內部使用strong再持有一下？

block外界宣告weak是為了實作block對物件的弱持有，而里面的作用是為了保證在進到block時不會發生釋放，

4、Autoreleasepool是實作機制是什么？它是什么時候釋放內部的物件的？它內部的資料結構是什么樣的？當我提到哨兵物件時，會繼續問哨兵物件的作用是什么，為什么要設計它？

Autoreleasepool的原理是一個雙向串列，它會對加入其中的物件實作延遲釋放，當Autoreleasepool呼叫drain方法時會釋放內部標記為autorelease的物件，

class AutoreleasePoolPage {
    magic_t const magic;
    id *next;
    pthread_t const thread;
    AutoreleasePoolPage * const parent;
    AutoreleasePoolPage *child;
    uint32_t const depth;
    uint32_t hiwat;
};

哨兵物件類似一個指標，指向自動釋放池的堆疊頂位置，它的作用就是用于標記當前自動釋放池需要釋放內部物件時，釋放到那個地方結束，每次入堆疊時它用于確定添加的位置，然后再次移動到堆疊頂，

關于自動釋放池的底層探究可以看draveness的這篇自動釋放池的前世今生 ---- 深入決議 autoreleasepool

5、哪些物件會放入到Autoreleasepool中？

有兩種情況生成的物件會加入到autoreleasepool中：

• 非alloc/new/copy/mutablecopy 開始的方式初始化時，
• id的指標或物件的指標在沒有顯示指定時

參考計數帶來的一次討論

6、weak的實作原理是什么？當參考物件銷毀是它是如何管理內部的Hash表的？（這里要參閱weak原始碼）

runTime會把對weak修飾的物件放到一個全域的哈希表中，用weak修飾的物件的記憶體地址為key，weak指標為值，在物件進行銷毀時，用通過自身地址去哈希表中查找到所有指向此物件的weak指標，并把所有的weak指標置位nil，

Runtime

1、訊息發送的流程是怎樣的？

OC中的方法呼叫會轉化成給物件發送訊息，發送訊息會呼叫這個方法：

objc_msgSend(receiver, @selector(message))

該程序有以下關鍵步驟：

• 先確定呼叫方法的類已經都加載完畢，如果沒加載完畢的話進行加載

• 從cache中查找方法

• cache中沒有找到對應的方法，則到方法串列中查，查到則快取

• 如果本類中查詢到沒有結果，則遍歷所有父類重復上面的查找程序，直到NSObject

2、關聯物件時什么情況下會導致記憶體泄露？

關聯物件可以理解就是持有了一個物件，如果是retain等方式的持有，而該物件也持有了本類，那就是導致了回圈參考，

3、訊息轉發的流程是什么？

訊息轉發是發生在接收者（receiver）沒有找到對應的方法（method）的時候，該步驟有如下幾個關鍵步驟：

• 訊息轉發的時候，如果是實體方法會走resolveInstanceMethod:，如果是類方法會走resolveClassMethod:，它們的回傳值都是Bool，需要我們確定是否進行轉發，
• 如果第一步回傳YES，確定轉發就會進到下個方法forwardingTargetForSelector，這個方法需要我們指定一個被用receiver，
• methodSignatureForSelector用于指定方法簽名，forwardInvocation用于處理Invocation，進行完整轉發，
• 如果訊息轉發也沒有處理即為無法處理，會呼叫doesNotRecognizeSelector，引發崩潰，

更多了解可以參考iOS開發·runtime原理與實踐: 訊息轉發篇(Message Forwarding) (訊息機制，方法未實作+API不兼容奔潰，模擬多繼承)

4、category能否添加屬性，為什么？能否添加實體變數，為什么？

可以添加屬性，這里的屬性指@property，但跟類里的@property又不一樣，正常的@property為：實體變數Ivar + Setter + Getter 方法，分類里的@property這三者都沒有，需要我們手動實作，

分類是運行時被編譯的，這時類的結構已經固定了，所以我們無法添加實體變數，

對于分類自定義Setter和Getter方法，我們可以通過關聯物件（Associated Object）進行實作，

5、元類的作用是什么？

元類的作用是存盤類方法，同時它也是為了讓OC的類結構能夠形成倍訓，

對于為甚設計元類有以下原因；

• 在OC的世界里一切皆物件（借鑒于Smalltalk），metaclass的設計就是要為滿足這一點，

• 在OC中Class也是一種物件，它對應的類就是metaclass，metaclass也是一種物件，它的類是root metaclass，在往上根元類（root metaclass）指向自己，形成了一個倍訓，一個完備的設計，

如果不要metaclass可不可以？也是可以的，在objc_class再加一個類方法指標，但是這樣的設計會將訊息傳遞的程序復雜化，所以為了訊息傳遞流程的復用，為了一切皆物件的思想，就有了metaclass，

關于這一話題的深入討論可以參考這兩篇文章：

為什么要存在MetaClass

為什么要設計metaclass

6、類方法是存盤到什么地方的？類屬性呢？

類方法和類屬性都是存盤到元類中的，

類屬性在Swift用的多些，OC中很少有人用到，但其實它也是有的，寫法如下：

@interface Person : NSObject
// 在屬性類別中加上class
@property (class, nonatomic, copy) NSString *name;
@end
// 呼叫方式
NSString *temp = Person.name;

需要注意的是跟實體屬性不一樣，類屬性不會自動生成實體變數和setter，getter方法，需要我們手動實作，具體實作方法可以參考這個文章：Objective-C Class Properties

7、講幾個runtime的應用場景

• hook系統方法進行方法交換，
• 了解一個類（閉源）的私有屬性和方法，
• 關聯物件，實作添加分類屬性的功能，
• 修改isa指標，自定義KVO，

如果你正在跳槽或者正準備跳槽不妨動動小手，添加一下咱們的交流群1012951431來獲取一份詳細的大廠面試資料為你的跳槽多添一份保障，

Runloop

1、講一下對Runloop的理解？

Runloop就是一個運行回圈，它保證了在沒有任務的時候執行緒不退出，有任務的時候即使回應，Runloop跟執行緒，事件回應，手勢識別，頁面更新，定時器都有著緊密聯系，

深入了解推薦ibireme的這篇深入理解RunLoop

2、可以用Runloop實作什么功能？

• 檢測卡頓
• 執行緒保活
• 性能優化，將一些耗時操作放到runloop wait的情況處理，

性能優化

1、對TableView進行性能優化有哪些方式？

• 快取高度
• 異步渲染
• 減少離屏渲染

2、Xcode的Instruments都有哪些除錯的工具？

• Activity Monitor（活動監視器）：監控行程的CPU、記憶體、磁盤、網路使用情況，是程式在手機

  運行真正占用記憶體大小

• Allocations（記憶體分配）：跟蹤程序的匿名虛擬記憶體和堆的物件提供類名和可選保留/釋放歷史

• Core Animation（圖形性能）：顯示程式顯卡性能以及CPU使用情況

• Core Data：跟蹤Core Data檔案系統活動

• Energy Log：耗電量監控

• File Activity：檢測檔案創建、移動、變化、洗掉等

• Leaks（泄漏）：一般的措施記憶體使用情況，檢查泄漏的記憶體，并提供了所有活動的分配和泄漏模塊的類物件分配統計資訊以及記憶體地址歷史記錄

• Network：用鏈接工具分析你的程式如何使用TCP/IP和UDP/IP鏈接

• System Usage：記錄關于檔案讀寫，sockets，I/O系統活動，輸入輸出

• Time Profiler（時間探查）：方法執行耗時分析

• Zombies：測量一般的記憶體使用，專注于檢測過度釋放的野指標物件，也提供物件分配統計以及主動分配的記憶體地址歷史

3、講一下你做過的性能優化的事情，

這個根據自己情況來說吧，

4、如何檢測卡頓，都有哪些方法？

• FPS，通過CADisplayLink計算1s內重繪次數，也可以利用Instruments里的Core Animation，
• 利用Runloop，實時計算 kCFRunLoopBeforeSources 和 kCFRunLoopAfterWaiting 兩個狀態區域之間的耗時是否超過某個閥值
• 子執行緒檢測，每次檢測時設定標記位為YES，然后派發任務到主執行緒中將標記位設定為NO，接著子執行緒沉睡超時闕值時長，判斷標志位是否成功設定成NO，如果沒有說明主執行緒發生了卡頓，參考ANREye的實作

5、縮小包體積有哪些方案？

• 圖片壓縮，無用圖片洗掉
• 一些大圖可以動態下發
• 洗掉無用類，無用方法
• 減少三方庫的依賴

計算機相關

1、專案編譯的流程是什么？手機上的應用程式自點擊圖示開始到首屏內容展示都經歷了哪些步驟？

編譯流程：

• 預處理：處理宏定義，洗掉注釋，展開頭檔案，

• 詞法分析：把代碼切成一個個token，比如大小括號等于號還有字串

• 語法分析：驗證語法是否正確，合成抽象語法樹AST

• 靜態分析：查找代碼錯誤

• 型別檢查：動態和靜態

• 目標代碼的生成與優化，包括洗掉多余指令，選擇合適的尋址方式，如果開啟了bitcode，會做進一步的優化

• 匯編：由匯編器生成匯編語言

• 機器碼：由匯編語言轉成機器碼，生成.o檔案

應用啟動的流程：

啟動的前提是完成編譯，運行程式即運行編譯過后的目標程式，它分為main函式前和main函式后：

main前

• 加載可執行檔案（App的.o檔案集合）

• 加載元件（系統和應用的元件），進行rebase指標調整和bind符號系結

• Objc運行時的初始處理，包括Objc相關類的注冊，category注冊，selector唯一性檢查

• 初始化，包括執行+load()、attribute(constructor)修飾的函式的呼叫、創建C++靜態全域變數

main后

• 首頁初始化所需要組態檔的讀寫操作

• 首頁界面渲染

2、對于基本資料型別，一般是存盤到堆疊中的，它有沒有可能存在堆上，什么情況下會存盤到堆上？

堆疊和堆都是同屬一塊記憶體，只不過一個是高地址往低地址存盤，一個從低地址往高地址存盤，他們并沒有嚴格的界限說一個值只能放在堆上或者堆疊上，所以基本資料型別也是可以存盤到堆上的，

當該基礎型別變數被__block捕獲時，該變數連同block都會被copy到堆上，

3、資料庫中的事務是什么意思？

事務就是訪問并操作各種資料項的一個資料庫操作序列，這些操作要么全部執行，要么全部不執行，如果其中一個步驟出錯就要撤銷整個操作，回滾到進入事務之前的狀態，

4、使用過什么資料庫（我回答的Sqlite，Realm），Realm在使用時有哪些注意事項，如何實作批量操作？

對于Realm感興趣的同學可以看下其官方檔案，

Realm需要注意的主要就是不能直接跨執行緒訪問同一物件，

批量操作可以在一個單獨的事務中執行多個資料庫的修改，

5、LRU演算法是否了解，如何實作一套LRU演算法？

LRU（Least recently used 最近最少使用）演算法是一個快取淘汰演算法，其作用就是當快取很多時，該淘汰哪些內容，見名知意，它的核心思想是淘汰最近使用最少的內容，實作它的關鍵步驟是：

• 新資料插入到鏈表的頭部

• 每當快取命中時，則將資料移動到鏈表頭部

• 鏈表滿時，將尾部資料清除

這個演算法在SDWebImage和Kingfisher等需要處理快取的庫中都有實作，

6、知道哪些設計模式，怎么理解設計模式的作用？

工廠模式、觀察者模式、中介者模式、單例模式，這個根據實際情況說吧，

7、如果有1000萬個Int型別的數字，如何對他們排序？

這里的隱藏含義是，記憶體不夠用時如何排序，還有一個隱藏含義是硬碟足夠大，這是可以采用分而治之的方法，將資料分成若干塊，使每一小塊滿足當前內容大小，然后對每塊內容單獨排序，最后采用歸并排序對所有塊進行排序，就得到了一個有序序列，

8、設計一套資料庫方案，實作類似微信的搜索關鍵詞能快速檢索出包含該字串的聊天資訊，并展示對應數量（聊天記錄的資料量較大）

可以對聊天記錄的文本值加上索引，正常情況下資料庫搜索都是全量檢索的，加上索引之后只會檢索滿足條件的記錄，大大降低檢索量，

如果你正在跳槽或者正準備跳槽不妨動動小手，添加一下咱們的交流群1012951431來獲取一份詳細的大廠面試資料為你的跳槽多添一份保障，

簡歷相關問題

1、Lottie實作影片效果的原理是什么？

iOS里的影片基本都是基于CoreAnimation里的API實作的，Lottie也是如此，在AE上實作影片效果，通過插件匯出對應的json檔案，Lottie的庫決議該json，轉成對應的系統API方法，圖片的參考可以使用Base64編到json里，也可以通過專案集成，通過路徑參考，

2、OClint實作靜態分析的原理是什么，它是如何做到的？

具體可以參考我之前寫的如何通過靜態分析提高iOS代碼質量，

3、MVVM和MVC有什么區別？

對比架構時，可以從是否職責分離，可測驗性，可易維護性三個維度對比，

更多對比可以參考我翻譯的一篇文章：【譯】iOS 架構模式--淺析MVC, MVP, MVVM 和 VIPER

4、靜態庫和動態庫的區別是什么？

靜態庫：鏈接時被完整復制到可執行檔案中，多次使用就多份拷貝，

動態庫：鏈接時不復制，而是由系統動態加載到記憶體，記憶體中只會有一份該動態庫，

5、了解Flutter嗎？它有沒有使用UIKit？它是如何渲染UI的？

UIKit是基于CoreAnimation渲染的，而Flutter并沒有用到它，而是自己基于C++實作了一套渲染框架，

6、二進制重排的核心依據是什么？

修改鏈接順序，減少啟動時的缺頁中斷，

實踐步驟可以參考李斌同學的這篇iOS 優化篇 - 啟動優化之Clang插樁實作二進制重排

7、如何設計一套切換主題的方案？

核心思路是觀察者模式+協議（通知），當獲取到主題切換時，通知各個實作了主題協議的類進行更新，

8、AVPlayer和IJKPlayer有什么區別？用IJKPlayer如何實作一個快取視頻串列每條視頻前1s的內容？

因為對IJKPlayer和FFmpeg了解的不是很深，這個我也沒有確切答案，如果有了解的小伙伴可以評論告知我，

9、類似微博的短視頻串列，滑動停留播放，如何實作？

這個主要就是檢測contentOffset和螢屏中間位置，設定一些邊界條件，處理滑動程序中的切換行為，

10、使用python做過哪些事？如何理解腳本語言？

多語言管理，csv多語言檔案讀取，然后寫入到專案Localizable.strings中；抓取專案中的多語言字串，

腳本（script） 其實就是一系列指令，計算機看了指令就知道自己該做什么事情，像常見的Python，Shell，Ruby都是腳本語言，他們通常不需要編譯，通過解釋器運行，

資料結構與演算法

1、什么是Hash表，什么是Hash碰撞，解決Hash碰撞有什么方法？

哈希表（Hash Table，也叫散串列），是根據關鍵碼值 (Key-Value) 而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，我們常用的Dictionary就是一種Hash表，

那什么是Hash碰撞呢，我們知道Hash表的查找是通過鍵值進行定位的，當兩個不同的輸入對應一個輸出時，即為Hash碰撞，也被稱為Hash沖突，

如果使用字典的例子你可能聯想不到沖突的情況，我們假設另一種情況：假設hash表的大小為9（即有9個槽），現在要把一串資料存到表里：5,28,19,15,20,33,12,17,10，我們使用的hash函式是對9取余，這樣的話會出現hash(5)=5，hash(28)=1，hash(19)=1，28和19都對應一個地址，這就出現了Hash沖突，

解決Hash沖突的方式有開放定址法和鏈地址法，

2、如何遍歷二叉樹？

二叉樹的遍歷有三種方式，對于上面這棵二叉樹，他們的遍歷結果為：

前序遍歷：根節點 > 左子節點 > 右子節點，

10，6，4，8，14，12，16

中序遍歷：左子節點 > 根節點 > 右子節點，

4，6，8，10，12，14，16

后序遍歷：左子節點 > 右子節點 > 根節點，

4，8，6，12，16，14，10

3、簡述下快速排序的程序，時間復雜度是多少？

快排的思想是通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，

一個簡單的Swift實作方式如下：

func quicksort<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { return a }

  let pivot = a[a.count/2]
  let less = a.filter { $0 < pivot }
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }

  return quicksort(less) + equal + quicksort(greater)
}

快速排序是有好幾種的，他們的區別在于如何實作filter和磁區基準值的選取，

快排的時間復雜度是O(nlogn)，空間復雜度是O(logn)

4、有一個整數陣列，如何只遍歷一遍就實作讓該陣列奇數都在前面，偶數都在后面？

這個是《劍指offer》里的一道題，leedcode也有對應題目：劍指offer 21

這個相對比較簡單，因為不要求有序，可以采用收尾遍歷的方式，進行交換，我這有個參考答案：

func sorted( _ nums: inout [Int]) -> [Int] {
    guard !nums.isEmpty else {
        return []
    }
    var start = 0
    var end = nums.count - 1
    while start < end {
        if nums[start] % 2 != 0 {
            start += 1
            continue
        }
        if nums[end] % 2 == 0 {
            end -= 1
            continue
        }
        (nums[start], nums[end]) = (nums[end], nums[start])
    }
    return nums
}

5、假設你正在爬樓梯，需要 n 階你才能到達樓頂，每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

leetcode 20

6、給出一個 32 位的有符號整數，你需要將這個整數中每位上的數字進行反轉

leetcode 7

7、有紅、黃、藍三種顏色的氣球，在牛客王國，1個紅氣球+1個黃氣球+1個藍氣球可以兌換一張彩票

2個紅氣球+1個黃氣球可以兌換1個藍氣球，

2個黃氣球+1個藍氣球可以兌換1個紅氣球，

2個藍氣球+1個紅氣球可以兌換1個黃氣球，

現在牛牛有a個紅氣球，b個黃氣球， c個藍氣球，牛牛想知道自己最多可以兌換多少張彩票，

這個是牛客網里的一道演算法題，這里有個題解可以參考，

資料推薦

如果你正在跳槽或者正準備跳槽不妨動動小手，添加一下咱們的交流群1012951431來獲取一份詳細的大廠面試資料為你的跳槽多添一份保障，

標籤：其他

上一篇：Android 開發技術周報 Issue#294

下一篇：Sagit.Framework For IOS 開發框架入門教程15：表單校驗事件：require、requireGroup、requireBeforeClick用法。