> For the complete documentation index, see [llms.txt](https://garylai.gitbook.io/algorithm-and-data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garylai.gitbook.io/algorithm-and-data-structure/problems/object-oriented-design.md).

# Object Oriented Design 物件導向設計

物件導向程式設計的題目通常敘述會很複雜，因為這類型的題目是希望可以模擬處理現實生活的問題，因為現實生活中，「資料」是會一直變動的，要考慮的邊角案例也多，而一般的演算法考題的輸入通常都是固定的，所以我們通常不用擔心運算途中，資料有增、刪、改的行為。

我的心得是物件導向程式設計的題目，首先要先想清楚資料應該要用什麼樣的資料結構來做處理，常見的 [LRU Cache 最久未使用演算法](/algorithm-and-data-structure/classic-problems/cache/lru-cache.md) 、 [LFU Cache 最近最少使用演算法](/algorithm-and-data-structure/classic-problems/cache/lfu-cache.md) ，其實問題核心的底層是我們要怎麼建立起需要的資料結構？像是題目中的雙向 `Linked List` 加上 `Hash Table` 的組合。如果說要幫助在面試時減少失誤，是不是可以想起來程式語言有類似的 API 可以實作？例如： LRU 題目中，真的非常非常清楚了概念後，絕大多數的時間是要實踐 `Linked List + Hash Table` ，不過在 Java 中可以用 `LinkedHashMap` 取代，在 Python 中，可以用 `OrderDict` 取代，我相信如果可以很清楚理解演算法加上清楚的資料結構理解，在面試的時候使用這些比較進階的 API 是會被允許的，當然如果面試的職位是需要實踐很多底層資料結構、演算法的職位，那被要求要從零寫出也是有可能的。

第二個難點是如何考量時間複雜度，因為物件導向設計的題目通常不會是一個資料結構可以完成的，又會有很多增、刪、查、改的操作，當選擇物件導向的題目的時候，也要考慮是重度寫、重度讀還是讀寫各半？最常見的就是現實世界資料是會一直進來的，一直進來的同時，我們又要一直保持著資料的排序，那我們應該是要在加入的時候就排序好？還是要在查詢的時候排序好？或是只要有操作就要檢查排序？當然也可以在一開始就想那有沒有什麼好用的有序資料結構？

第三個難點是「Corner Case 邊角案例」，物件導向設計的時候要考慮的情境非常多！這時候最好是可以將各種情況用狀態機的方式呈現，這樣在寫出來的時候，我們就可以透過狀態機的情況，去一個一個檢查，在程式中是否有考量到所有的情況。

最後是要注意的事項是，題目只會寫出主要的 API ，但是多數時候要自己去想是不是需要額外的變數，或是額外的函式可以幫助解題，有些操作是很重複的，例如 [Trie](/algorithm-and-data-structure/problems/trie.md) 這種資料結構非常愛考物件導向程式設計題，在其增、刪、查、改的時候都會要從頭遍歷，在面試時不求一定要寫出來，不過會很建議多練習，多試幾次後，就容易把需要整理出來的程式碼給整理好，可以減少寫錯的機率。