某大廠面試題1

1. 分布式事務的一致性問題

事務的四大特性（ACID）

原子性（Atomicity）：一個事務（transaction）要么沒有開始，要么全部完成，不存在中間狀態，

一致性（Consistency）：事務的執行不會破壞資料的正確性，即符合約束，

隔離性（Isolation）：多個事務不會相互破壞，

持久性（Durability）：事務一旦提交成功，對資料的修改不會丟失，

其中原子性、持久性、隔離性都是為了保證一致性的，

事務型資料庫必須要解決的問題是資料的一致性問題，這里的一致性指的是ACID中的C，如果不滿足C，會有多種資料例外，如臟讀、不可重復讀、幻讀、讀偏序、寫偏序等資料例外，隔離性這一特性的出現就是為了解決一類由于并發事務而導致的資料不一致問題，

舉例：

用戶通過手機支付購買商家的商品，在支付程序中需要在一系列的系統進行處理：支付系統中需要創建支付單，在賬務系統進行用戶余額扣減，隨后通知上游系統完成支付，在這個支付程序中，三種系統之間需要嚴格保證一致性，不能出現支付單成功但是余額沒扣，也不能出現余額扣除后商家不發貨的情況，

分布式系統屬于異步系統（Asynchronous system model）：不同行程的處理器速度可能差別很大，時鐘偏移可能很大，訊息傳播延遲可能很大（可能很大意味著沒有最大值限制），這樣就帶來一個很大的問題：超時，超時一定有可能發生，但是超時又無法判斷究竟是成功還是失敗了，導致整個業務狀態例外，而單臺計算機屬于同步系統（Synchronous system model），即使不同行程的處理器速度差異、時鐘偏移延遲、訊息延遲都有最大值的，

CAP理論

一個分布式系統最多只能同時滿足一致性（Consistency）、可用性（Availability）和磁區容錯性（Partition tolerance）這三項中的兩項，

• Consistency 一致性：每次讀取獲得的都是最新寫入的資料，即寫操作之后的讀操作，必須回傳該值
• Availability 可用性：服務在正常回應時間內一直可用，回傳的狀態都是成功
• Partition-tolerance 磁區容錯性：即使遇到某節點或網路故障的時候，系統仍能夠正常提供服務

盡管CAP狹義上針對的是分布式存盤系統，但它一樣可以應用于普遍的分布式系統，由于磁區容錯性（P）是分布式系統最重要的特點，因此CAP可以理解為：當網路發生磁區（P）時，要么選擇C一致性，要么選擇A可用性，
??舉例來說，具體到上文描述的用戶支付的例子中，當網路存在例外時，要么用戶可能暫時無法支付，要么用戶的余額可能不會立刻扣減，這兩種選擇就是在架構設計中對可用性和一致性的權衡，

2. 堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法，堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點，堆排序可以說是一種利用堆的概念來排序的選擇排序，復雜度是O(nlogn)

堆排序是利用堆這種資料結構所設計的一種排序演算法，堆實際上是一個完全二叉樹結構，問：那么什么是完全二叉樹呢？答：假設一個二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹，

小頂堆滿足： Key[i] <= key[2i+1] && Key[i] <= key[2i+2]
大頂堆滿足： Key[i] >= Key[2i+1] && key >= key[2i+2]每個結點的值都大于或等于其左右孩子的值

步驟

1. 將待排序的陣列初始化為大頂堆，該程序即建堆，
2. 將堆頂元素與最后一個元素進行交換，除去最后一個元素外可以組建為一個新的大頂堆，
3. 由于第二步堆頂元素跟最后一個元素交換后，新建立的堆不是大頂堆，需要重新建立大頂堆，重復上面的處理流程，直到堆中僅剩下一個元素，

假設我們有一個待排序的陣列 arr = [4, 6, 7, 2, 9, 8, 3, 5]， 我們把這個陣列構造成為一個二叉樹，如下圖：

此時9跟4交換后，4這個節點下面的樹就不是不符合大頂堆了，所以要針對4這個節點跟它的左右節點再次比較，置換成較大的值，4跟左右子節點比較后，應該跟6交換位置，

那么至此，整個二叉樹就是一個完完整整的大頂堆了，每個節點都不小于左右子節點，此時我們把堆的跟節點，即陣列最大值9跟陣列最后一個元素2交換位置，那么9就是排好序的放在了陣列最后一個位置，

2到了跟節點后，新的堆不滿足大頂堆，我們需要重復上面的步驟，重新構造大頂堆，然后把大頂堆根節點放到二叉樹后面作為排好序的陣列放好，就這樣利用大頂堆一個一個的數字排好序，

值得注意的一個地方是，上面我們把9和2交換位置后，2處于二叉樹根節點，2需要跟右子樹8交換位置，交換完位置后，右子樹需要重新遞回調整大頂堆，但是左子樹6這邊，已經是滿足大頂堆屬性，因為不需要再操作，

class Solution(object):
    def heap_sort(self, nums):
        i, l = 0, len(nums)
        self.nums = nums
        # 構造大頂堆，從非葉子節點開始倒序遍歷，因此是l//2 -1 就是最后一個非葉子節點
        for i in range(l // 2 - 1, -1, -1):
            self.build_heap(i, l - 1)
        # 上面的回圈完成了大頂堆的構造，那么就開始把根節點跟末尾節點交換，然后重新調整大頂堆
        for j in range(l - 1, -1, -1):
            nums[0], nums[j] = nums[j], nums[0]
            self.build_heap(0, j - 1)
            print("第{}輪堆排序：{}".format(l - j, nums))
        return nums

    def build_heap(self, i, l):
        """構建大頂堆"""
        nums = self.nums
        left, right = 2 * i + 1, 2 * i + 2  ## 左右子節點的下標
        large_index = i
        if left <= l and nums[i] < nums[left]:
            large_index = left

        if right <= l and nums[left] < nums[right]:
            large_index = right

        # 通過上面跟左右節點比較后，得出三個元素之間較大的下標，如果較大下表不是父節點的下標，說明交換后需要重新調整大頂堆
        if large_index != i:
            nums[i], nums[large_index] = nums[large_index], nums[i]
            self.build_heap(large_index, l)

s = Solution()
li =  [4, 6, 7, 2, 9, 8, 3, 5]
s.heap_sort(li)

    
第1輪堆排序：[8, 6, 7, 5, 4, 2, 3, 9]
第2輪堆排序：[7, 6, 3, 5, 4, 2, 8, 9]
第3輪堆排序：[6, 5, 3, 2, 4, 7, 8, 9]
第4輪堆排序：[5, 4, 3, 2, 6, 7, 8, 9]
第5輪堆排序：[4, 2, 3, 5, 6, 7, 8, 9]
第6輪堆排序：[3, 2, 4, 5, 6, 7, 8, 9]
第7輪堆排序：[2, 3, 4, 5, 6, 7, 8, 9]

3. 快速排序

快速排序是一種非常高效的排序演算法，采用 “分而治之” 的思想，把大的拆分為小的，小的拆分為更小的，其原理是，對于給定的記錄，選擇一個基準數，通過一趟排序后，將原序列分為兩部分，使得前面的比后面的小，然后再依次對前后進行拆分進行快速排序，遞回該程序，直到序列中所有記錄均有序，

首先取序列第一個元素為基準元素pivot=R[low]，i=low,j=high， 2：從后向前掃描，找小于等于pivot的數，如果找到，R[i]與R[j]交換，i++， 3：從前往后掃描，找大于pivot的數，如果找到，R[i]與R[j]交換，j--， 4:重復2~3，直到i=j,回傳該位置mid=i,該位置正好為pivot元素， 完成一趟排序后，以mid為界，將序列分為兩部分，左序列都比pivot小，有序列都比pivot大，然后再分別對這兩個子序列進行快速排序，

以序列（30，24，5，58，16，36，12，42，39）為例，進行演示：

1、初始化，i=low,j=high,pivot=R[low]=30：

2、從后往前找小于等于pivot的數，找到R[j]=12

• R[i]與R[j]交換，i++

3、從前往后找大于pivot的數，找到R[i]=58

• R[i]與R[j]交換，j--

4、從后往前找小于等于pivot的數，找到R[j]=16

• R[i]與R[j]交換，i++

5、從前往后找大于pivot的數，這時i=j,第一輪排序結束，回傳i的位置，mid=i

此時已mid為界，將原序列一分為二，左子序列為（12，24，5，18）元素都比pivot小，右子序列為（36，58，42，39）元素都比pivot大，然后在分別對兩個子序列進行快速排序，最后即可得到排序后的結果，

def quick_sort(lists,i,j):
    if i >= j:
        return list
    pivot = lists[i]
    low = i
    high = j
    while i < j:
        while i < j and lists[j] >= pivot:
            j -= 1
        lists[i]=lists[j]
        while i < j and lists[i] <=pivot:
            i += 1
        lists[j]=lists[i]
    lists[j] = pivot
    quick_sort(lists,low,i-1)
    quick_sort(lists,i+1,high)
    return lists

if __name__=="__main__":
    lists=[30,24,5,58,18,36,12,42,39]
    print("排序前的序列為：")
    for i in lists:
        print(i,end =" ")
    print("\n排序后的序列為：")
    for i in quick_sort(lists,0,len(lists)-1):
        print(i,end=" ")

4. 行程間通信的方法

行程和執行緒

行程是對運行時程式的封裝，是系統進行資源調度和分配的基本單位，實作了作業系統的并發；

執行緒是行程的子任務，是CPU調度和分派的基本單位，用于保證程式的實時性，實作行程內部的并發；執行緒是作業系統可識別的最小執行和調度單位，每個執行緒都獨自占用一個虛擬處理器：獨自的暫存器組，指令計數器和處理器狀態，每個執行緒完成不同的任務，但是共享同一地址空間（也就是同樣的動態記憶體，映射檔案，目標代碼等等），打開的檔案佇列和其他內核資源，

區別：

1. 一個執行緒只能屬于一個行程，而一個行程可以有多個執行緒，但至少有一個執行緒，執行緒依賴于行程而存在，
2. 行程在執行程序中擁有獨立的記憶體單元，而多個執行緒共享行程的記憶體，（資源分配給行程，同一行程的所有執行緒共享該行程的所有資源，同一行程中的多個執行緒共享代碼段（代碼和常量），資料段（全域變數和靜態變數），擴展段（堆存盤），但是每個執行緒擁有自己的堆疊段，堆疊段又叫運行時段，用來存放所有區域變數和臨時變數，）
3. 行程是資源分配的最小單位，執行緒是CPU調度的最小單位；
4. 系統開銷： 由于在創建或撤消行程時，系統都要為之分配或回收資源，如記憶體空間、I／o設備等，因此，作業系統所付出的開銷將顯著地大于在創建或撤消執行緒時的開銷，類似地，在進行行程切換時，涉及到整個當前行程CPU環境的保存以及新被調度運行的行程的CPU環境的設定，而執行緒切換只須保存和設定少量暫存器的內容，并不涉及存盤器管理方面的操作，可見，行程切換的開銷也遠大于執行緒切換的開銷，
5. 通信：由于同一行程中的多個執行緒具有相同的地址空間，致使它們之間的同步和通信的實作，也變得比較容易，行程間通信IPC，執行緒間可以直接讀寫行程資料段（如全域變數）來進行通信——需要行程同步和互斥手段的輔助，以保證資料的一致性，在有的系統中，執行緒的切換、同步和通信都無須作業系統內核的干預
6. 行程編程除錯簡單可靠性高，但是創建銷毀開銷大；執行緒正相反，開銷小，切換速度快，但是編程除錯相對復雜，
7. 行程間不會相互影響 ；執行緒一個執行緒掛掉將導致整個行程掛掉
8. 行程適應于多核、多機分布；執行緒適用于多核

行程間通信的方式有：1、無名管道( pipe )；2、高級管道(popen)；3、有名管道 (named pipe)；4、訊息佇列( message queue )；5、信號量( semophore )；7、共享記憶體( shared memory )；8、套接字( socket )，

1 、無名管道 ( pipe ) ：

管道是一種半雙工的通信方式，資料只能單向流動，而且只能在具有親緣關系的行程間使用，行程的親緣關系通常是指父子行程關系，

2 、高級管道 (popen) ：

將另一個程式當做一個新的行程在當前程式行程中啟動，則它算是當前程式的子行程，這種方式我們成為高級管道方式，

3 、有名管道 (named pipe) ：

有名管道也是半雙工的通信方式，但是它允許無親緣關系行程間的通信，

4 、訊息佇列 ( message queue ) ：

訊息佇列是由訊息的鏈表，存放在內核中并由訊息佇列識別符號標識，訊息佇列克服了信號傳遞資訊少、管道只能承載無格式位元組流以及緩沖區大小受限等缺點，

5 、信號量 ( semophore ) ：

信號量是一個計數器，可以用來控制多個行程對共享資源的訪問，它常作為一種鎖機制，防止某行程正在訪問共享資源時，其他行程也訪問該資源，因此，主要作為行程間以及同一行程內不同執行緒之間的同步手段，

6 、信號 ( sinal ) ：

信號是一種比較復雜的通信方式，用于通知接收行程某個事件已經發生，

7 、共享記憶體 ( shared memory ) ：

共享記憶體就是映射一段能被其他行程所訪問的記憶體，這段共享記憶體由一個行程創建，但多個行程都可以訪問，共享記憶體是最快的 IPC 方式，它是針對其他行程間通信方式運行效率低而專門設計的，它往往與其他通信機制，如信號兩，配合使用，來實作行程間的同步和通信，

8 、套接字 ( socket ) ：

套解口也是一種行程間通信機制，與其他通信機制不同的是，它可用于不同機器間的行程通信，

為什么要行程間通信

由于每個行程都是相對獨立運行的，且每個用戶請求都可能導致多個行程在作業系統中運行，如果多個行程之間需要協作完成任務，那么行程間可能就需要進行相互通信獲取資料，這種通信方式就稱作為行程間通信（Inter-process communication IPC），

5. 作業系統記憶體回識訓制

記憶體回收指的是對用戶空間中的堆段和檔案映射段進行回收（用戶使用 malloc、mmap 等分配出去的空間），用戶可以手動地使用 free()等進行記憶體釋放，當沒有空閑的物理記憶體時，內核就會開始自動地進行回收記憶體作業，回收的方式主要是兩種：后臺記憶體回收和直接記憶體回收，

• 后臺記憶體回收（kswapd）：在物理記憶體緊張的時候，會喚醒 kswapd 內核執行緒來回收記憶體，這個回收記憶體的程序異步的，不會阻塞行程的執行，
• 直接記憶體回收（direct reclaim）：如果后臺異步回收跟不上行程記憶體申請的速度，就會開始直接回收，這個回收記憶體的程序是同步的，會阻塞行程的執行，

如果直接記憶體回收后，空閑的物理記憶體仍然無法滿足此次物理記憶體的申請，那么內核就會觸發 OOM （Out of Memory）機制，根據演算法選擇一個占用物理記憶體較高的行程，然后將其殺死，釋放記憶體資源，直到釋放足夠的記憶體，

本文來自博客園，作者：ivanlee717，轉載請注明原文鏈接：https://www.cnblogs.com/ivanlee717/p/17267314.html

標籤：Python

上一篇：Django筆記十之values_list指定欄位取值及distinct去重處理

下一篇：PyQt5學習 （3）--QWidget（下）