給iOS中高級求職者的一份面試題解答

来源:https://www.cnblogs.com/Mayday9527/archive/2019/10/21/11700269.html
-Advertisement-
Play Games

前段時間更新了一篇 給iOS中高級面試官的一份招聘要求 收到很多小伙伴的點贊與關註。可能有很多小伙伴已經帶著我在那篇文章給大家提供的一些面試技巧 & 其中的面試題 已經開始招聘或者應聘了！這裡應大家要求，對裡面的面試題提供相關答案！相信無論是面試官還是求職者都是有所收穫的~~PS：篇幅有點長，大家可 ...


前段時間更新了一篇 給iOS中高級面試官的一份招聘要求 收到很多小伙伴的點贊與關註。可能有很多小伙伴已經帶著我在那篇文章給大家提供的一些面試技巧 & 其中的面試題 已經開始招聘或者應聘了！這裡應大家要求，對裡面的面試題提供相關答案！相信無論是面試官還是求職者都是有所收穫的~~
PS：篇幅有點長，大家可以關註或者點贊收藏以備不時之需！！！

 

iOS基礎


 1：講講你對atomic & nonatomic的理解

  •   1、原子操作對線程安全並無任何安全保證。被 atomic 修飾的屬性(不重載設置器和訪問器)只保證了對數據讀寫的完整性，也就是原子性，但是與對象的線程安全無關。
  •   2、線程安全有保障、對性能有要求的情況下可使用 nonatomic替代atomic，當然也可以一直使用atomic。
  •   3：[詳細參考]

 2：被 weak 修飾的對象在被釋放的時候會發生什麼？是如何實現的？知道sideTable 麽？裡面的結構可以畫出來麽？

被weak修飾的對象在被釋放時候會置為nil，不同於assign；

Runtime 維護了一個 weak表，用於存儲指向某個對象的所有 weak指針。weak表  其實是一個 hash（哈希）表，Key 是所指對象的地址，Value 是 weak指針 的地址（這個地址的值是所指對象指針的地址）數組。

  •  1、初始化時：runtime 會調用  objc_initWeak函數，初始化一個新的 weak指針 指向對象的地址。
  •  2、添加引用時：objc_initWeak函數 會調用 objc_storeWeak() 函數， objc_storeWeak()  的作用是更新指針指向，創建對應的弱引用表。
  •  3、釋放時，調用  clearDeallocating函數 。 clearDeallocating函數 首先根據對象地址獲取所有  weak指針地址 的數組，然後遍歷這個數組把其中的數據設為  nil，最後把這個  entry 從  weak表 中刪除，最後清理對象的記錄。
  •  4：[詳細參考]
struct SideTable {
// 保證原子操作的自旋鎖
spinlock_t slock;
// 引用計數的 hash 表
RefcountMap refcnts;
// weak 引用全局 hash 表
weak_table_t weak_table;
}

struct weak_table_t {
// 保存了所有指向指定對象的 weak 指針
weak_entry_t *weak_entries;
// 存儲空間
size_t num_entries;
// 參與判斷引用計數輔助量
uintptr_t mask;
// hash key 最大偏移值
uintptr_t max_hash_displacement;
};

3：`block` 用什麼修飾？strong 可以？

  • block 本身是像對象一樣可以 retain，和 release。但是，block 在創建的時候，它的記憶體是分配在棧(stack)上，而不是在堆(heap)上。他本身的作於域是屬於創建時候的作用域，一旦在創建時候的作用域外面調用block將導致程式崩潰。
  • 使用 retain 也可以，但是block的retain行為預設是用copy的行為實現的
  • 因為 block 變數預設是聲明為棧變數的，為了能夠在block的聲明域外使用，所以要把 block 拷貝（copy）到堆，所以說為了 block 屬性聲明和實際的操作一致，最好聲明為 copy。
  • [詳細參考]

 4：block 為什麼能夠捕獲外界變數？ __block 做了什麼事？

研究Block的捕獲外部變數就要除去函數參數這一項，下麵一一根據這4種變數類型的捕獲情況進行分析。

  • 自動變數
  • 靜態變數
  • 靜態全局變數
  • 全局變數

首先 全局變數global_i 和 靜態全局變數static_global_j 的值增加，以及它們被 Block  捕獲進去，這一點很好理解，因為是全局的，作用域很廣，所以 Block 捕獲了它們進去之後，在 Block 裡面進行 ++ 操作， Block 結束之後，它們的值依舊可以得以保存下來。

struct __main_block_impl_0 {
struct __block_impl impl;
struct __main_block_desc_0* Desc;
__Block_byref_a_0 *a; // by ref
__main_block_impl_0(void *fp, struct __main_block_desc_0 *desc, __Block_byref_a_0 *_a, int flags=0) : a(_a->__forwarding) {
impl.isa = &_NSConcreteStackBlock;
impl.Flags = flags;
impl.FuncPtr = fp;
Desc = desc;
}
};

 __main_block_impl_0結構體  就是這樣把自動變數捕獲進來的。也就是說，在執行 Block  語法的時候， Block  語法表達式所使用的自動變數的值是被保存進了 Block 的結構體實例中，也就是  Block 自身中。

這裡值得說明的一點是，如果 Block 外面還有很多自動變數，靜態變數，等等，這些變數在 Block 裡面並不會被使用到。那麼這些變數並不會被 Block 捕獲進來，也就是說並不會在構造函數裡面傳入它們的值。

`Block`捕獲外部變數僅僅只捕獲`Block`閉包裡面會用到的值，其他用不到的值，它並不會去捕獲。

 5：談談你對事件的傳遞鏈和響應鏈的理解

  • 一：響應者鏈  UIResponser 包括了各種 Touch message 的處理，比如開始，移動，停止等等。常見的  UIResponser 有  UIView及子類 ，UIViController , APPDelegate ， UIApplication 等等。

回到響應鏈，響應鏈是由 UIResponser 組成的，那麼是按照哪種規則形成的。

  •  A： 程式啟動  UIApplication 會生成一個單例，並會關聯一個 APPDelegate 。 APPDelegate 作為整個響應鏈的根建立起來，而 UIApplication 會將自己與這個單例鏈接，即 UIApplication 的 nextResponser (下一個事件處理者)為 APPDelegate 。
  •  B：創建UIWindow 程式啟動後，任何的 UIWindow 被創建時， UIWindow 內部都會把 nextResponser 設置為 UIApplication單例 。 UIWindow 初始化 rootViewController , rootViewController 的 nextResponser 會設置為 UIWindow 
  •  C：UIViewController初始化  loadView , VC 的 view 的 nextResponser 會被設置為 VC .
  •  D：addSubView ： addSubView 操作過程中，如果子subView不是VC的View,那麼 subView 的 nextResponser 會被設置為 superView 。如果是 VC 的 View ,那就是  subView -> subView.VC ->superView 如果在中途， subView.VC 被釋放，就會變成  subView.nextResponser = superView


我們使用一個現實場景來解釋這個問題：當一個用點擊屏幕上的一個按鈕，這個過程具體發生了什麼。

  • 1. 用戶觸摸屏幕，系統硬體進程會獲取到這個點擊事件，將事件簡單處理封裝後存到系統中，由於硬體檢測進程和當前App進程是兩個進程，所以進程兩者之間傳遞事件用的是埠通信。硬體檢測進程會將事件放到 APP 檢測的那個埠。
  • 2. APP 啟動主線程 RunLoop 會註冊一個埠事件，來檢測觸摸事件的發生。當事件到達，系統會喚起當前 APP 主線程的 RunLoop 。來源就是 App主線程事件 ，主線程會分析這個事件。
  • 3.最後，系統判斷該次觸摸是否導致了一個新的事件, 也就是說是否是第一個手指開始觸碰，如果是，系統會先從響應網中 尋找響應鏈。如果不是，說明該事件是當前正在進行中的事件產生的一個 Touch message ， 也就是說已經有保存好的響應鏈
  • 二：事件傳遞鏈

通過兩種方法來做這個事情。

// 先判斷點是否在View內部，然後遍歷subViews
- (nullable UIView *)hitTest:(CGPoint)point withEvent:(nullable UIEvent *)event; 
//判斷點是否在這個View內部
- (BOOL)pointInside:(CGPoint)point withEvent:(nullable UIEvent *)event; // default returns YES if point is in bounds

 

  • A: 流程
  • 1：先判斷該層級是否能夠響應`（1.alpha>0.01 2.userInteractionEnabled == YES 3.hidden = NO）`
  • 2：判斷改點是否在`view`內部,
  • 3：如果在那麼遍歷子`view`繼續返回可響應的view，直到沒有。
  • B：常見問題
  • 父view設置為不可點擊，子view可以點擊嗎
  • 不可以，hit test 到父view就截止了
  • 子view設置view不可點擊不影響父類點擊
  • 同父view覆蓋不影響點擊
  • 手勢對responder方法的影響
  • C：實際用法
  • 點一一個圓形控制項，如何實現只點擊圓形區域有效，重載`pointInside`。此時可將外部的點也判斷為內部的點，反之也可以。
  • 事件響應鏈在複雜功能界面進行不同控制項間的通信，簡便某些場景下優於代理和`block`

 6：談談 KVC 以及 KVO 的理解？

7：RunLoop 的作用是什麼？它的內部工作機制瞭解麽？

字面意思是“消息迴圈、運行迴圈”，runloop 內部實際上就是一個 do-while迴圈 ，它在迴圈監聽著各種事件源、消息，對他們進行管理並分發給線程來執行。

  •  1.通知觀察者將要進入運行迴圈。 線程和 RunLoop 之間是一一對應的
  •  2.通知觀察者將要處理計時器。
  •  3.通知觀察者任何非基於埠的輸入源即將觸發。
  •  4.觸發任何準備觸發的基於非埠的輸入源。
  •  5.如果基於埠的輸入源準備就緒並等待觸發，請立即處理該事件。轉到第9步。
  •  6.通知觀察者線程即將睡眠。
  •  7.將線程置於睡眠狀態，直到發生以下事件之一:
  1.  事件到達基於埠的輸入源。
  2.  計時器運行。
  3.  為運行迴圈設置的超時值到期。
  4.  運行迴圈被明確喚醒。
  •  8.通知觀察者線程被喚醒。
  •  9.處理待處理事件。
  1.  如果觸發了用戶定義的計時器，則處理計時器事件並重新啟動迴圈。轉到第2步。
  2.  如果輸入源被觸發，則傳遞事件。
  3.  如果運行迴圈被明確喚醒但尚未超時，請重新啟動迴圈。轉到第2步。
  •  10.通知觀察者運行迴圈已退出。

8：蘋果是如何實現 autoreleasepool 的？

arc下編譯器會優化成

void *context = objc_autoreleasePoolPush();
// {}中的代碼
objc_autoreleasePoolPop(context);
  • 向一個結構 AutoreleasePoolPage，中寫入需要自動釋放的對象，類似一種標記，調用 objc_autoreleasePoolPop(context) 後，就會把這中間的對象 release 一下。
  • 這裡要註意的是，方法返回值是怎麼做到自動釋放的？
  • 其使用 Thread Local Storage（TLS） 線程局部存儲，每次存入線程或者從線程取出來。
  • 我們沒有卸載`{}`中的自動釋放對象，會在每個 runloop 結束時候去釋放，相當於一個大的 autoreleasepool 中。
  • [參考文章]
  • [蘋果是如何實現autoreleasepool的]

9：談談你對  FRP (函數響應式)  的理解，延伸一下  RxSwift  或者  RAC ！

[參考文章:RxSwift（1）— 初探] 看這一篇文章也就夠了！然後結合  RxSwift  映射到  RAC ！函數響應式的思想是不變的！至於內部的封裝有所不同，但是最終卻是殊途同歸！

10：平時開發有沒有玩過 Instrument ？

分析：這裡的內容非常有意思，對於一個iOS高級開發人員，我覺得還有很有必要掌握的！尤其開發3-5年，如果沒有掌握這些內容我覺得是不合格的

 我個人建議在掌握面試題的同時還需要求職者更多的去分析和拓展！比如你的探索思路，你在這個知識點意外的延伸。還有你再實際開發過程的落地！而這些都是加分項！

Runtime


 1：什麼是 isa，isa 的作用是什麼？

2：一個實例對象的 isa 指向什麼？類對象指向什麼？元類 isa 指向什麼？

  • [參考文章]
  • 實例對象的 isa 指向類
  • 類對象的 isa 指向元類
  • 元類isa 指向根元類

  • 3：objc  中類方法和實例方法有什麼本質區別和聯繫？
  •  [參考文章]

類方法：

  •  1.類方法是屬於類對象的
  •  2.類方法只能通過類對象調用
  •  3.類方法中的self是類對象
  •  4.類方法可以調用其他的類方法
  •  5.類方法中不能訪問成員變數
  •  6.類方法中不能直接調用對象方法

實例方法：

  •  1.實例方法是屬於實例對象的
  •  2.實例方法只能通過實例對象調用
  •  3.實例方法中的self是實例對象
  •  4.實例方法中可以訪問成員變數
  •  5.實例方法中直接調用實例方法
  •  6.實例方法中也可以調用類方法(通過類名)

 4： load  和  initialize 的區別？

+load

  •  1、只要程式啟動就會將所有類的代碼載入到記憶體中（在main函數執行之前）, 放到代碼區(無論該類有沒有被使用到都會被調用)
  •  2、 +load 方法會在當前類被載入到記憶體的時候調用, 有且僅會調用一次
  •  3、當父類和子類都實現`+load`方法時, 會先調用父類的 +load 方法, 再調用子類的 +load 方法
  •  4、先載入原始類，再載入分類的 +load 方法
  •  5、當子類未實現 +load 方法時，不會調用父類的 +load 方法
  •  6、多個類都實現 +load 方法， +load 方法的調用順序，與 Compile Sources 中出現的順序一致

[load方法在Apple官方文檔中的描述]

＋initialize

  •  1、當類第一次被使用的時候就會調用(創建類對象的時候)
  •  2、`initialize`方法在整個程式的運行過程中只會被調用一次, 無論你使用多少次這個類都只會調用一次
  •  3、`initialize`用於對某一個類進行一次性的初始化
  •  4、先調用父類的 initialize 再調用子類的 initialize
  •  5、當子類未實現 initialize 方法時，會把父類的實現繼承過來調用一遍，再次之前父類的 initialize 方法會被優先調用一次
  •  6、當有多個 Category 都實現了 initialize 方法，會覆蓋類中的方法，只執行一個(會執行 Compile Sources  列表中最後一個 Category  的 initialize 方法)

[initialize方法在Apple官方文檔中的描述]

 5： _objc_msgForward  函數是做什麼的？直接調用會發生什麼問題？

當對象沒有實現某個方法 ，會調用這個函數進行方法轉發。 （某方法對應的`IMP`沒找到，會返回這個函數的`IMP`去執行）

  •  1.調用resolveInstanceMethod:方法，允許用戶在此時為該Class動態添加實現。如果有實現了，則調用並返回。如果仍沒實現，繼續下麵的動作。
  •  2.調用forwardingTargetForSelector:方法，嘗試找到一個能響應該消息的對象。如果獲取到，則直接轉發給它。如果返回了nil，繼續下麵的動作。
  •  3.調用methodSignatureForSelector:方法，嘗試獲得一個方法簽名。如果獲取不到，則直接調用doesNotRecognizeSelector拋出異常。
  •  4.調用forwardInvocation:方法，將地3步獲取到的方法簽名包裝成Invocation傳入，如何處理就在這裡面了。

如果直接調用這個方法，就算實現了想調用的方法，也不會被調用，會直接走消息轉發步驟。

 6：簡述下 `Objective-C` 中調用方法的過程

  •  Objective-C 是動態語言，每個方法在運行時會被動態轉為消息發送，即： objc_msgSend(receiver, selector) ，整個過程介紹如下：
  •  objc 在向一個對象發送消息時，`runtime`庫會根據對象的isa指針找到該對象實際所屬的類
  •  然後在該類中的方法列表以及其父類方法列表中尋找方法運行
  •  如果，在最頂層的父類（一般也就NSObject）中依然找不到相應的方法時，程式在運行時會掛掉並拋出異常  unrecognized selector sent to XXX
  • 但是在這之前，objc的運行時會給出三次拯救程式崩潰的機會，這三次拯救程式奔潰的說明見問題《什麼時候會報unrecognized selector的異常》中的說明

PS： Runtime  鑄就了 Objective-C 是動態語言的特性，使得C語言具備了面向對象的特性，在程式運行期創建，檢查，修改類、對象及其對應的方法，這些操作都可以使用runtime中的對應方法實現。

7：能否想向編譯後得到的類中增加實例變數？能否向運行時創建的類中添加實例變數？為什麼？

  • 1.不能向編譯後得到的類增加實例變數
  • 2.能向運行時創建的類中添加實例變數

解釋：

  • 1.編譯後的類已經註冊在 runtime 中,類結構體中的 objc_ivar_list 實例變數的鏈表和 instance_size 實例變數的記憶體大小已經確定,  runtime 會調用  class_setvarlayout  或  class_setWeaklvarLayout 來處理 strong weak 引用.所以不能向存在的類中添加實例變數
  • 2.運行時創建的類是可以添加實例變數,調用 class_addIvar函數 .但是的在調用 objc_allocateClassPair 之後, objc_registerClassPair 之前,原因同上.

8：談談你對切麵編程的理解

維基百科對於切麵編程(AOP)的解釋是這樣的：面向切麵的程式設計（ aspect-oriented programming，AOP，又譯作面向側面的程式設計、觀點導向編程、剖面導向程式設計）是電腦科學中的一個術語，指一種程式設計範型。該範型以一種稱為切麵的語言構造為基礎，切麵是一種新的模塊化機制，用來描述分散在對象、類、函數)中的橫切關註點。[參考文章]


 分析：Runtime 這個模塊iOS面試無論初中高都會面試。我覺得這個模塊不光只是僅僅問問關於知識點內容，我更新想要聽到求職者在這裡面的爬坑探索辛歷路程！Runtime 這個模塊是刷開頁面開發的關鍵點！

 網路&多線程


1：HTTP的缺陷是什麼？

HTTP 主要有這些不足，例舉如下。

  •  通信使用明文（不加密），內容可能會被竊聽
  •  不驗證通信方的身份，因此有可能遭遇偽裝
  •  無法證明報文的完整性，所以有可能已遭篡改

這些問題不僅在 HTTP上出現，其他未加密的協議中也會存在這類問題。

 2：談談三次握手，四次揮手！為什麼是三次握手，四次揮手？

[參考文章] 我覺得這個地方還是需要自我理解，用自己的話去表達出來！

 3： socket  連接和 Http 連接的區別

http 是基於 socket 之上的。socket 是一套完整的 tcp,udp 協議的介面。

  • HTTP協議：簡單對象訪問協議，對應於應用層，HTTP 協議是基於TCP連接的。
  • tcp協議：對應於傳輸層。
  • ip協議：對應於網路層。

TCP/IP是傳輸層協議，主要解決數據如何在網路中傳輸，而HTTP協議是應用層協議，主要解決如何包裝數據。

Socket是對TCP/IP 協議的封裝，它本身不是協議，而是一個調用介面，通過 Socket ，我們才能使用 TCP/IP協議 。

  • http連接：就是所謂的短連接，即客戶端向伺服器端發送一次請求，伺服器端響應後連接即會斷掉。
  • socket連接：就是所謂的長連接，理論上客戶端和伺服器端一旦建立起連接將不會主動斷掉，但是由於各種環境因素可能會使連接斷開。

 http 是客戶端用 http 協議進行請求，發送請求時候需要封裝 http 請求頭，並綁定請求的數據，伺服器一般有 web 伺服器配合。 http 請求方式為客戶端主動發起請求，伺服器才能給響應，一次請求完畢後則斷開連接以節省資源。伺服器不能主動給客戶端響應。 iPhone 主要使用的類是 NSUrlConnection 。 socket 是客戶端跟伺服器直接使用 socket“套接字” 進行拼接，並沒有規定連接後斷開，所以客戶端和伺服器可以保持連接，雙方都可以主動發送數據。一般在游戲開發或者股票開發這種即時性很強的並且保持發送數據量比較大的場合使用。主要類是 CFSocketRef。

  • UDP：是用戶數據報協議：主要用在實時性要求高以及對質量相對較弱的地方，但面對現在高質量的線路容易丟包。
  • TCP：是傳輸控制協議，是面向連接的，，運行環境必然要求其可靠性不可丟失包有良好的擁塞控制機制。

4：HTTPS，安全層除了SSL還有，最新的？ 參數握手時首先客戶端要發什麼額外參數

 

 5：什麼時候POP網路，有了 `Alamofire` 封裝網路 `URLSession`為什麼還要用`Moya` ？

 POP網路：面向協議編程的網路能夠大大降低耦合度！網路層下沉，業務層上浮。中間利用  POP網路 的 Moya 隔開。如果你的項目是  RxSwift  函數響應式的也沒有關係！因為有  RxMoya 

參考文章：

  • * [Moya]()
  • * [Swift - 面向協議編程（POP）](https://juejin.im/post/5d6e6b10f265da038f482a91)
  • * [Swift - 當Moya遇上RxSwift（網路架構優化）](https://juejin.im/post/5d6fb6ef51882520d46ab27e)


 6：如何實現  dispatch_once 

 

+ (instancetype)sharedInstance
{
/*定義相應類實例的靜態變數；
意義：函數內定義靜態變數，無論該函數被調用多少次，
在記憶體中只初始化一次，並且能保存最後一次賦的值
*/
static ClassName *instance = nil;
/*定義一個dispatch_once_t(其實也就是整型)靜態變數，
意義：作為標識下麵dispatch_once的block是否已執行過。
static修飾會預設將其初始化為0，當值為0時才會執行block。
當block執行完成，底層會將onceToken設置為1，這也就是為什
麽要傳onceToken的地址（static修飾的變數可以通過地址修改
onceToken的值），同時底層會加鎖來保證這個方法是線程安全的
*/
static dispatch_once_t onceToken;
/*只要當onceToken == 0時才會執行block，否則直接返回靜態變數instance*/
dispatch_once(&onceToken, ^{
instance = [[ClassName alloc] init];
//...
});
return instance;
}

[iOS原理之CGD-dispatch_once的底層實現]

7：能否寫一個讀寫鎖？談談具體的分析

8：什麼時候會出現死鎖？如何避免？

9：有哪幾種鎖？各自的原理？它們之間的區別是什麼？最好可以結合使用場景來說

分析：這個模塊可能是一般開發人員的盲區。對於這一塊一定要有自己的理解！學習的方向就是查漏補缺，一步一個吃掉！如果你一整塊去啃，你會發現很枯燥！雖然開發過程中你可能用不到，但是面試這一塊是你必須要掌握的！

 數據結構


 1.數據結構的存儲一般常用的有幾種？各有什麼特點？

數據的存儲結構是數據結構的一個重要內容。在電腦中，數據的存儲結構可以採取如下四中方法來表現。

  •  順序存儲方式：簡單的說，順序存儲方式就是在一塊連續的存儲區域 一個接著一個的存放數據。順序存儲方式把邏輯上相連的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關係由存儲單元的鄰接掛安息來體現。順序存儲方式也稱為順序存儲結構（sequentialstorage structure），一般採用數組或者結構數組來描述。 線性存儲方式主要用於線性邏輯結構的數據存放，而對於圖和樹等非線性邏輯結構則不適用。
  •  鏈接存儲方式：鏈接存儲方式比較靈活，其不要求邏輯上相鄰的結點在物理位置上相鄰，結點間的邏輯關係由附加的引用欄位表示。一個結點的引用欄位往往指導下一個結點的存放位置。 鏈接存儲方式也稱為鏈接式存儲結構（LinkedStorage Structure），一般在原數據項中增加應用類型來表示結點之間的位置關係。

 索引存儲方式

  • 索引存儲方式是採用附加索引表的方式來存儲結點信息的一種存儲方式。索引表由若幹個索引項組成。索引存儲方式中索引項的一般形式為：（關鍵字、地址）。其中，關鍵字是能夠唯一標識一個結點的數據項。
  •  索引存儲方式還可以細分為如下兩類：
  •  稠密索引（Dense Index）:這種方式中每個結點在索引表中都有一個索引項。其中，索引項的地址指示結點所在的的存儲位置；
  •  稀疏索引（Spare Index）：這種方式中一組結點在索引表中只對應一個索引項。其中，索引項的地址指示一組結點的起始存儲位置。
  •  散列存儲方式

散列存儲方式是根據結點的關鍵字直接計算出該結點的存儲地址的一種存儲的方式。 在實際應用中，往往需要根據具體數據結構來決定採用哪一種存儲方式。同一邏輯結構採用不同額存儲方法，可以得到不同的存儲結構。而且這四種節本存儲方法，既可以單獨使用，也可以組合起來對數據結構進行存儲描述。

 2.集合結構 線性結構 樹形結構 圖形結構 3.單向鏈表 雙向鏈表 迴圈鏈表 4.數組和鏈表區別 5.堆、棧和隊列

 

6.輸入一棵二叉樹的根結點，求該樹的深度？

如果一棵樹只有一個結點，它的深度為1。 如果根結點只有左子樹而沒有右子樹， 那麼樹的深度應該是其左子樹的深度加1，同樣如果根結點只有右子樹而沒有左子樹，那麼樹的深度應該是其右子樹的深度加1\. 如果既有右子樹又有左子樹， 那該樹的深度就是其左、右子樹深度的較大值再加1。

public static int treeDepth(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left > right ? (left + 1) : (right + 1);
}

 7.輸入一課二叉樹的根結點，判斷該樹是不是平衡二叉樹？

  • （1）需要重覆遍歷節點多次的解法
  • （2）每個節點只需遍歷一次的解法
  •  [參考文章]

演算法


1.時間複雜度

在[電腦科學]中，時間複雜性，又稱時間複雜度，[演算法]，它定性描述該演算法的運行時間。這是一個代表演算法輸入值的[字元串]的長度的函數。時間複雜度常用[大O符號]表述，不包括這個函數的低階項和首項繫數。使用這種方式時，時間複雜度可被稱為是[漸近]的，亦即考察輸入值大小趨近無窮時的情況。 [時間複雜性]

2.空間複雜度

空間複雜度(Space Complexity)是對一個演算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接[插入排序]的[時間複雜度],空間複雜度是O(1) 。而一般的[遞歸]演算法就要有O(n)的空間複雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要占用的存儲空間兩個方面[衡量]。 [時間複雜度&空間複雜度]

3.常用的排序演算法

  • 1、冒泡排序
  • 2、選擇排序
  • 3、插入排序
  • 4、希爾排序
  • 5、快速排序
  • 6、歸併排序
  • 7、堆排序
  • [常見的7種排序演算法]

 4.字元串反轉

- (NSString *)reversalString:(NSString *)originString{
NSString *resultStr = @"";
for (NSInteger i = originString.length -1; i >= 0; i--) {
NSString *indexStr = [originString substringWithRange:NSMakeRange(i, 1)];
resultStr = [resultStr stringByAppendingString:indexStr];
}
return resultStr;
}

5.鏈表反轉（頭差法）

public Node reverseList(){
Node cur = head;
Node prev = null;
Node curNext = head.next;
Node reverHead = null;
while(cur!=null){
cur.next = prev;
cur = curNext;
prev = cur;
curNext = curNext.next;
}
reverHead = cur;
return reverHead;
}

 6.有序數組合併

objc
- (void)merge {
/*
有序數組A：1、4、5、8、10...1000000，有序數組B：2、3、6、7、9...999998，A、B兩個數組不相互重覆，請合併成一個有序數組C，寫出代碼和時間複雜度。
*/
//(1).
NSMutableArray *A = [NSMutableArray arrayWithObjects:@4,@5,@8,@10,@15, nil];
// NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@17,@18, nil];
NSMutableArray *B = [NSMutableArray arrayWithObjects:@2,@6,@7,@9,@11,@12,@13, nil];
NSMutableArray *C = [NSMutableArray array];
int count = (int)A.count+(int)B.count;
int index = 0;
for (int i = 0; i < count; i++) {
if (A[0]<B[0]) {
[C addObject:A[0]];
[A removeObject:A[0]];
}
else if (B[0]<A[0]) {
[C addObject:B[0]];
[B removeObject:B[0]];
}
if (A.count==0) {
[C addObjectsFromArray:B];
NSLog(@"C = %@",C);
index = i+1;
NSLog(@"index = %d",index);
return;
}
else if (B.count==0) {
[C addObjectsFromArray:A];
NSLog(@"C = %@",C);
index = i+1;
NSLog(@"index = %d",index);
return;
}
}
//(2).
//時間複雜度
//T(n) = O(f(n)):用"T(n)"表示，"O"為數學符號，f(n)為同數量級，一般是演算法中頻度最大的語句頻度。
//時間複雜度:T(n) = O(index);
}

7.查找第一個只出現一次的字元（Hash查找）

兩個思路：

  • 1： hash �不同編譯器對字元數據的處理不一樣，所以hash之前先把字元類型轉成無符號類型；
  • 2，空間換時間，用`buffer數組`記錄當前只找到一次的字元，避免二次遍歷。
# define SIZE 256
char GetChar(char str[])
{
if(!str)
return 0;
char* p = NULL;
unsigned count[SIZE] = {0};
char buffer[SIZE];
char* q = buffer;
for(p=str; *p!=0; p++)
{
if(++count[(unsigned char)*p] == 1)
*q++ = *p;
}

for (p=buffer; p<q; p++)
{
if(count[(unsigned char)*p] == 1)
return *p;
}
return 0;
}

8.查找兩個子視圖的共同父視圖

這個問的其實是數據結構中的二叉樹，查找一個普通二叉樹中兩個節點最近的公共祖先問題 假設兩個視圖為 UIViewA 、 UIViewC ，其中  UIViewA 繼承於 UIViewB ， UIViewB 繼承於 UIViewD ， UIViewC 也繼承於 UIViewD ；即  A->B->D，C->D 

- (void)viewDidLoad {
[super viewDidLoad];
Class commonClass1 = [self commonClass1:[ViewA class] andClass:[ViewC class]];
NSLog(@"%@",commonClass1);
// 輸出：2018-03-22 17:36:01.868966+0800 兩個UIView的最近公共父類[84288:2458900] ViewD
}
// 獲取所有父類
- (NSArray *)superClasses:(Class)class {
if (class == nil) {
return @[];
}
NSMutableArray *result = [NSMutableArray array];
while (class != nil) {
[result addObject:class];
class = [class superclass];
}
return [result copy];
}

- (Class)commonClass1:(Class)classA andClass:(Class)classB {
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
for (NSUInteger i = 0; i < arr1.count; ++i) {
Class targetClass = arr1[i];
for (NSUInteger j = 0; j < arr2.count; ++j) {
if (targetClass == arr2[j]) {
return targetClass;
}
}
}
return nil;
}
  • 方法一明顯的是兩層for迴圈，時間複雜度為  O(N^2)  一個改進的辦法:我們將一個路徑中的所有點先放進NSSet中.因為NSSet的內部實現是一個hash表，所以查詢元素的時間的複雜度變成  O(1) ,我們一共有N個節點，所以總時間複雜度優化到了 O(N) 
- (Class)commonClass2:(Class)classA andClass:(Class)classB{
NSArray *arr1 = [self superClasses:classA];
NSArray *arr2 = [self superClasses:classB];
NSSet *set = [NSSet setWithArray:arr2];
for (NSUInteger i =0; i<arr1.count; ++i) {
Class targetClass = arr1[i];
if ([set containsObject:targetClass]) {
return targetClass;
}
}
return nil;
}

 9.無序數組中的中位數(快排思想)

[參考：求無序數組中的中位數]

 10.給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重覆利用。 示例:給定 nums = [2, 7, 11, 15], target = 9  ---  返回 [0, 1]  思路：

  •  第一層for迴圈從索引0到倒數第二個索引拿到每個數組元素，
  •  第二個for迴圈遍歷上一層for迴圈拿到的元素的後面的所有元素。
  •  [參考文章]
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int[] result = new int[2];
for(int i = 0; i < len; i++){
for(int j = i+1; j < len; j++){
if(nums[i] + nums[j] == target){
result[0] = i;
result[1] = j; 
return result;
}
}
}
return result;
}
}

分析：這個模塊是絕大部分開發人員的軟肋！這個模塊是最能測試求職者思維能力的！但是我不建議面試官直接讓求職者手寫 在那樣的面試緊張環境，手寫數據結構或者一些演算法代碼，是非常有挑戰的！思維到我覺得差不多！

架構設計


1：設計模式是為瞭解決什麼問題的？

設計模式（Design pattern）是一套被反覆使用、多數人知曉的、經過分類編目的、代碼設計經驗的總結。使用設計模式是為了可重用代碼、讓代碼更容易被他人理解、保證代碼可靠性。

設計模式最主要解決的問題是通過封裝和隔離變化點來處理軟體的各種變化問題。 隔離變化的好處在於，將系統中經常變化的部分和穩定的部分隔離，有助於增加復用性，並降低系統耦合度。很多設計模式的意圖中都明顯地指出了其對問題的解決方案，學習設計模式的要點是發現其解決方案中封裝的變化點。

三本經典書籍：[《GOF設計模式》]，[《設計模式解析》]，《Head First Design Pattern》

設計模式是軟體開發領域的精髓之一。學好設計模式是目前每一個開發人員的必修課，

 2：看過哪些第三方框架的源碼，它們是怎麼設計的？

這個題目就看你個人的感觸，考量你平時的功底！ 大家可以針對性一些常見的框架： RxSwift 、 Alamofire 、 Moya 、 AFNetworing 、 YYKit .... 掌握會用的同時，必須要掌握底層的核心思想！

3：可以說幾個重構的技巧麽？你覺得重構適合什麼時候來做？

  •  重覆代碼的提煉
  •  冗長方法的分割
  •  嵌套條件分支的優化
  •  去掉一次性的臨時變數
  •  消除過長參數列表
  •  提取類或繼承體系中的常量
  •  讓類提供應該提供的方法
  •  拆分冗長的類
  •  提取繼承體系中重覆的屬性與方法到父類

在新功能增加時候，在擴展不再簡單的時候。重構是一個不斷的過程。

4：開發中常用架構設計模式你怎麼選型?

這裡也是一道開放性題目！並不是說某一種架構就是最優秀的~只有最合適的！根據公司情況，項目現狀，以及開發者水平及時調整，設計！

 5：你是如何組件化解耦的？

 iOS 解藕 、組件化最常用的是使用統跳路由的方式，目前比較常用的 iOS 開源路由框架主要是 JLRoutes 、 MGJRouter 、 HHRouter 等，這些路由框架各有優點和缺點，基本可以滿足大部分需求。目前最常用來作路由跳轉，以實現基本的組件化開發，實現各模塊之間的解藕。但是，在實際中開發中會發現，無法徹底使用它們完成所有模塊間通信，比如模塊間的同步、非同步通信等。再比如，我們在配置了相關路由跳轉的 URL 後，如何在上線之後動態修改相關跳轉邏輯？在模塊間通信時，如何在上線後動態修改相關參數？APP 能否實現類似  Web 的302跳轉 ？[學習參考]

分析：架構設計這一層對於一個iOS中高級開發人員來說。這一塊那是他必須要去思考和感受總結的!如果這位求職者開發4-5年了，一直都在做應用層界面開發，那麼想必他未來的職業晉升是已經落後了的！面試官不妨在這一個模塊單獨設計成一面，就和求職者一起交流討論。畢竟這些思維的設計，也許能夠給面試官帶來一些不一樣的東西！

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • [20191013]oracle number類型存儲轉化腳本.txt
    [20191013]oracle number類型存儲轉化腳本.txt--//測試看看是否可以利用bc obase=100的輸出解決問題。另外以前腳本忘記考慮尾數的四捨五入問題。--//也許編程就是這樣，總有一些細節沒有考慮到...--//代碼如下num2raw_5.sh：#! /bin/bash# ...
  • [mybatis] sql語句無錯誤，但是執行多條sql語句時，拋出java.sql.SQLSyntaxErrorException
    錯誤內容 解決方法 本人連接的是mysql資料庫，檢查sql語法並無錯誤。而此處為 多條query語句，報錯信息指向分號後的第二條語句。 判斷可能是連接的datasource預設只允許執行單個query語句。 在連接datasource的url後面增加參數allowMultiQueries=true ...
  • Mysql資料庫 深度知識點
    停止命令：net stop mysql 啟動命令：net start mysql mysql登錄命令 mysql -h ip -P 埠 -u 用戶名 -p mysql --version 或者mysql -V用於在未登錄情況下，查看本機mysql版本 select version();：登錄情況下 ...
  • Redis總結
    資源列表: "Redis 命令參考" "Commands" Redis是什麼 是一個開源( )的記憶體中的數據結構存儲，用作資料庫、緩存和消息中間件。它支持多種數據結構，如 、`哈希表 列表 無序集合 有序集合 點陣圖 基數統計 地理空間索引 複製 Lua腳本 LRU回收 事務 磁碟持久化 哨兵 自動分 ...
  • 不就是SELECT COUNT語句嗎，竟然能被面試官虐的體無完膚
    資料庫查詢相信很多人都不陌生，所有經常有人調侃程式員就是CRUD專員，這所謂的CRUD指的就是資料庫的增刪改查。 在資料庫的增刪改查操作中，使用最頻繁的就是查詢操作。而在所有查詢操作中，統計數量操作更是經常被用到。 關於資料庫中行數統計，無論是MySQL還是Oracle，都有一個函數可以使用，那就是 ...
  • 什麼是全文檢索
    全文檢索技術被廣泛的應用於搜索引擎，查詢檢索等領域。我們在網路上的大部分搜索服務都用到了全文檢索技術。 對於數據量大、數據結構不固定的數據可採用全文檢索方式搜索，比如百度、Google等搜索引擎、論壇站內搜索、電商網站站內搜索等。 什麼是全文檢索呢？先看一下百度百科的專業定義。 為了能更好的理解，我 ...
  • 如何正確的在 Android 上使用協程 ？
    前言 你還記得是哪一年的 Google IO 正式宣佈 成為 Android 一級開發語言嗎？是 。如今兩年時間過去了，站在一名 Android 開發者的角度來看，Kotlin 的生態環境越來越好了，相關的開源項目和學習資料也日漸豐富，身邊願意去使用或者試用 Kotlin 的朋友也變多了。常年混跡掘 ...
  • 【Medium 萬贊好文】ViewModel 和 LIveData：模式 + 反模式
    原文作者： "Jose Alcérreca" 原文地址： "ViewModels and LiveData: Patterns + AntiPatterns" 譯者：秉心說 View 和 ViewModel 分配責任 理想情況下，ViewModel 應該對 Android 世界一無所知。這提升了可測 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類