計算機崗位求職應聘必備基本知識

冒泡排序（Bubble Sort）：最壞時間複雜度 O(n^2)，平均時間複雜度 O(n^2)，最好時間複雜度 O(n)。

選擇排序（Selection Sort）：最壞時間複雜度 O(n^2)，平均時間複雜度 O(n^2)，最好時間複雜度 O(n^2)。

插入排序（Insertion Sort）：最壞時間複雜度 O(n^2)，平均時間複雜度 O(n^2)，最好時間複雜度 O(n)。

希爾排序（Shell Sort）：最壞時間複雜度 O(n^2)，平均時間複雜度取決于增量序列，最好時間複雜度 O(n)。

歸并排序（Merge Sort）：最壞時間複雜度 O(nlogn)，平均時間複雜度 O(nlogn)，最好時間複雜度 O(nlogn)。

快速排序（Quick Sort）：最壞時間複雜度 O(n^2)，平均時間複雜度 O(nlogn)，最好時間複雜度 O(nlogn)。

堆排序（Heap Sort）：最壞時間複雜度 O(nlogn)，平均時間複雜度 O(nlogn)，最好時間複雜度 O(nlogn)。

關系資料模型的三要素是：

資料結構：關系資料模型使用表格（也稱為關系）來表示資料結構。

表格由行和列組成，行代表實體或記錄，列代表屬性或字段。

資料操作：關系資料模型支援基本的資料操作，如插入、更新、删除和查詢等。

這些操作通過結構化查詢語言（SQL）進行。

資料限制：關系資料模型支援各種資料限制，如主鍵、外鍵、唯一限制、預設值、非空限制等。

這些限制確定資料的完整性和一緻性，避免了資料的不正确性和備援。

死鎖是由于系統資源被有限地占用和共享而導緻的問題，具有以下四個必要條件：

互斥條件：至少有一個資源在任意時刻隻能被一個程序所占用，如果資源被占用，其他程序必須等待該資源被釋放後才能使用。

請求與保持條件：一個程序在占用了某些資源的同時還可以請求其他資源，此時該程序可以保持原有資源不釋放。

不剝奪條件：已經配置設定給程序的資源不能被強制性地搶占，隻能在該程序用完該資源之後自動釋放。

循環等待條件：存在一個程序資源請求的環形鍊，即程序集合中每個程序都在等待隻有其他程序才能釋放的資源。

當這四個必要條件同時滿足時，就會導緻死鎖問題的出現。是以，在設計和實作系統時，需要避免或減少這四個必要條件的出現，以避免死鎖的發生。

死鎖是指兩個或多個程序在執行過程中，因争奪系統資源而造成的一種僵局，若無外力作用，它們都将無法繼續執行下去。

在并發程式設計中，當多個線程同時請求通路共享資源，并且每個線程都持有一個其他線程需要的資源時，就可能會發生死鎖。

為了避免死鎖，可以采取以下政策：

避免循環等待：即在系統設計時，對資源的配置設定順序進行規定，避免線程對資源進行循環等待。

避免資源搶占：即對線程已經持有的資源進行保護，防止其他線程搶占已被占用的資源。

避免無法滿足資源請求：即對資源的配置設定進行合理的規劃和管理，保證系統能夠滿足所有線程的資源請求。

實作逾時機制：即為資源的請求設定逾時時間，在規定時間内無法獲得所需資源，則釋放已持有的資源，避免死鎖的發生。

檢測死鎖并進行恢複：即在系統設計時，設定死鎖檢測機制，并在檢測到死鎖時，通過釋放資源或終止線程等方式進行恢複。

以上是幾種常用的避免死鎖的政策，具體選用哪種政策需要根據具體的應用場景和需求進行判斷和選擇。

person表，寫出優先輸出30-40年齡段的人的資訊，其他人的資訊正常輸出的SQL語句

可以使用CASE語句來實作這個要求：

SELECT

name, age, gender, address

FROM

person

ORDER BY

CASE WHEN age BETWEEN 30 AND 40 THEN 1 ELSE 2 END, age;

上述SQL語句會先按照CASE語句的條件排序，即将年齡在30-40歲之間的人排在前面，其他人排在後面，

然後再按照年齡升序排序輸出。這樣可以保證輸出的結果中，30-40歲之間的人排在前面，而其他人的順序與原表中相同。

怎麼解決TCP粘包問題？

TCP粘包問題是由于TCP協定是面向流的協定，在發送資料時可能會将多個資料包合并成一個或者将一個資料包拆分成多個，

這就可能導緻接收端接收到的資料不是按照發送端發送的順序進行的，甚至會将多個資料包合并在一起，造成粘包問題。

下面介紹幾種解決TCP粘包問題的常見方法：

1.消息定長：在傳輸資料時，将每條消息固定為固定長度，不足的部分使用特殊字元進行填充。這樣接收方可以按照固定的長度進行消息的接收和解析，進而避免了粘包和拆包問題。

2.特殊字元分隔：在消息的末尾加入特定的字元或字元串作為消息分隔符，接收方根據分隔符将接收到的資料切割成多條消息進行處理。但是需要注意的是，如果消息中本身就包含了分隔符，就會導緻解析錯誤。

3.将消息分為消息頭和消息體：在消息頭中包含消息體的長度資訊，接收方先接收到消息頭，根據消息頭中的長度資訊再接收對應長度的消息體。這樣可以保證接收方可以正确地将消息拆分成多條完整的消息。

4.使用消息隊列：将接收到的資料存儲到消息隊列中，由消費者進行消費和解析。這種方式可以避免粘包和拆包問題，但是會增加一定的系統開銷。

上述方法可以根據具體的場景和需求進行選擇，以解決TCP粘包問題。

程式設計題目描述：

給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c，使得 a + b + c = 0？找出所有滿足條件且不重複的三元組。

注意：答案中不可以包含重複的三元組。

示例：

輸入：nums = [-1,0,1,2,-1,-4]

輸出：[[-1,-1,2],[-1,0,1]]

思路：

首先對數組進行排序，然後使用雙指針周遊數組。在周遊過程中，将第一個指針指向目前元素的下一個元素，

将第二個指針指向數組的最後一個元素。然後不斷地調整第一個和第二個指針的位置，直到找到三個數使得它們的和為 0。

具體而言，我們從數組的第一個元素開始周遊，對于每一個周遊到的元素 nums[i]，我們使用兩個指針 left = i + 1 和 right = n - 1，

其中 n 表示數組的長度。然後，如果 nums[i] + nums[left] + nums[right] = 0，則說明找到了一組解。

否則，如果 nums[i] + nums[left] + nums[right] > 0，則說明和太大了，需要将 right 指針左移；

如果 nums[i] + nums[left] + nums[right] < 0，則說明和太小了，需要将 left 指針右移。在移動指針的過程中，需要注意避免重複解的産生。

代碼實作：

class Solution:

def threeSum(self, nums: List[int]) -> List[List[int]]:

n = len(nums)

res = []

nums.sort()

for i in range(n):

if i > 0 and nums[i] == nums[i-1]:

continue

left, right = i+1, n-1

while left < right:

if nums[i] + nums[left] + nums[right] == 0:

res.append([nums[i], nums[left], nums[right]])

left += 1

right -= 1

while left < right and nums[left] == nums[left-1]:

left += 1

while left < right and nums[right] == nums[right+1]:

right -= 1

elif nums[i] + nums[left] + nums[right] > 0:

right -= 1

else:

left += 1

return res

時間複雜度：O(n^2)，其中 n 是數組的長度。周遊數組需要 O(n)的時間，對于數組中的每個元素，使用雙指針周遊其餘元素的時間複雜度是 O(n)，是以總時間複雜度是 O(n^2)。

假設我們有一個名為“students”的資料表，它包含以下列：id，name，age，gender和grade。

現在我們要建立一個存儲過程，根據指定的年級傳回學生資訊。

以下是一個存儲過程的示例：

CREATE PROCEDURE get_students_by_grade(IN grade INT)

BEGIN

SELECT * FROM students WHERE grade = grade;

END

在上面的示例中，存儲過程名為“get_students_by_grade”，它有一個輸入參數“grade”，它是整數類型。

該存儲過程使用輸入參數來過濾學生資料，然後傳回與指定年級比對的所有學生資訊。你可以根據你的需求調整此存儲過程，例如按照不同的條件進行過濾或傳回特定的列等。

什麼是大端存儲和小端存儲？

大端存儲和小端存儲是兩種不同的二進制資料存儲方式。在計算機内部，數字被表示為二進制數值，而不同的處理器架構可能會采用不同的方式來存儲這些二進制數值。

大端存儲（Big-Endian）和小端存儲（Little-Endian）之間的差別在于存儲位元組的順序。在大端存儲中，最高位位元組（MSB）被存儲在最低的記憶體位址中，而最低位位元組（LSB）則被存儲在最高的記憶體位址中。而在小端存儲中，最低位位元組（LSB）被存儲在最低的記憶體位址中，而最高位位元組（MSB）則被存儲在最高的記憶體位址中。

舉個例子，如果要存儲十六進制數值0x12345678，那麼在大端存儲中，這個值會按照如下順序存儲：

0x12 0x34 0x56 0x78

而在小端存儲中，則會按照如下順序存儲：

0x78 0x56 0x34 0x12

由于不同的處理器架構采用的存儲方式不同，是以在進行資料交換或資料傳輸時，需要進行位元組序的轉換，以確定資料能夠被正确解析。

翻譯下面英文

Beautiful is better than ugly.

Explicit is better than implicit.

Simple is better than complex.

Complex is better than complicated.

Flat is better than nested.

Sparse is better than dense.

Readability counts.

Special cases aren’t special enough to break the rules.

美總比醜好。

顯性比隐性好。

簡單比複雜好。

複雜勝過複雜。

扁平比嵌套好。

稀疏比密集好。

可讀性。

特殊情況并不特别到可以打破規則。

程式設計題目：有n個樣品，第i個樣品的權重對應i，權重大的個體被抽到的機率大，權重小的個體被抽到的機率小，現在要求按比重從中随機選取一個樣品。（c語言）

以下是一個可能的 C 語言實作，可以實作按比重從給定樣品集合中随機選取一個樣品。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int weighted_random_sample(int n, int weights[]) {

// 計算權重總和

int weight_sum = 0;

for (int i = 0; i < n; i++) {

weight_sum += weights[i];

}

// 生成一個 [0, weight_sum) 範圍内的随機數

int r = rand() % weight_sum;

// 在樣品集合中周遊，根據權重計算目前樣品被選中的機率，進行随機選擇

int cum_weight = 0;

for (int i = 0; i < n; i++) {

cum_weight += weights[i];

if (cum_weight > r) {

return i;

}

}

// 如果代碼執行到這裡，說明出現了錯誤，傳回 -1

return -1;

}

int main() {

// 設定随機數種子

srand(time(NULL));

// 示例樣品集合和對應的權重

int samples[] = {1, 2, 3, 4, 5};

int weights[] = {1, 2, 3, 4, 5};

int n = sizeof(samples) / sizeof(int);

// 進行 10 次随機采樣并輸出結果

for (int i = 0; i < 10; i++) {

int index = weighted_random_sample(n, weights);

printf("Sample %d with weight %d is selected.\n", samples[index], weights[index]);

}

return 0;

}

這個實作中， weighted_random_sample 函數接受一個整數數組 weights，它包含了每個樣品對應的權重。

函數首先計算權重總和，并生成一個 [0, weight_sum) 範圍内的随機數。然後在樣品集合中周遊，根據權重計算目前樣品被選中的機率，

并進行随機選擇。最後，函數傳回被選中的樣品的索引。在 main 函數中，我們給出了一個樣品集合和對應的權重，然後進行了 10 次随機采樣，并輸出結果。

動态連結庫和靜态連結庫的差別

靜态連結庫和動态連結庫都是将代碼和資源打包成庫的一種方式，以友善在其他程式中使用。它們之間的主要差別在于連結方式和庫檔案的使用方式。

靜态連結庫是将庫檔案的代碼和資源完整地複制到目标程式中，生成一個獨立的可執行檔案。

在編譯時，編譯器将庫檔案中的代碼和資源複制到目标程式中的可執行檔案中，這樣目标程式就可以在不依賴于外部庫的情況下獨立運作。

由于靜态連結庫的代碼和資源是完整地複制到目标程式中的，是以它的體積較大。同時，如果多個程式都使用同一個靜态連結庫，

那麼這個靜态連結庫的代碼和資源将會在每個程式中都複制一遍，造成了代碼備援，浪費了磁盤空間。

動态連結庫則是将庫檔案的代碼和資源儲存在一個獨立的檔案中，在程式運作時動态地将庫檔案加載到記憶體中，并與目标程式進行連結。

由于動态連結庫的代碼和資源不會被複制到目标程式中，是以它的體積較小。同時，如果多個程式都使用同一個動态連結庫，

那麼這個動态連結庫的代碼和資源隻需要加載一次，可以被多個程式共享，進而避免了代碼備援和浪費磁盤空間的問題。

總的來說，靜态連結庫的優點在于便于程式分發，因為它是一個完整的可執行檔案，不依賴于外部庫，可以直接在目标機器上運作；

而動态連結庫的優點在于節省空間和避免代碼備援，因為它的代碼和資源可以被多個程式共享。

但是，動态連結庫需要在運作時動态加載和連結，是以它的啟動時間可能會比靜态連結庫長一些。

此外，由于動态連結庫依賴于外部庫，如果目标機器上沒有相應的庫，就需要手動安裝這些庫，這可能會增加程式分發的難度。

什麼是弱引用？

弱引用（Weak Reference）是一種在程式設計語言中常見的引用類型，它是指一種不會增加所引用對象引用計數的引用。也就是說，當一個對象隻被弱引用所引用時，如果沒有其他強引用指向該對象，垃圾回收機制就可以在下一次運作時将其回收。

弱引用主要有以下好處：

1.記憶體管理：通過使用弱引用，程式可以更有效地管理記憶體。它可以讓程式在不需要某個對象時，将其釋放掉，

而不必擔心因為還有其他引用指向該對象而導緻對象無法被回收。

2.緩存管理：在一些需要緩存資料的應用場景中，弱引用可以用來實作緩存。當緩存資料不再被程式所引用時，可以通過弱引用将其自動釋放。

3.防止記憶體洩漏：在一些需要長時間運作的應用程式中，可能會存在一些對象因為被長時間持有引用而導緻記憶體洩漏的情況。

使用弱引用可以避免這種情況的發生，保證程式的健壯性。

需要注意的是，由于弱引用不會增加對象的引用計數，是以如果一個對象隻被弱引用所引用時，垃圾回收機制随時可以将其回收。

是以，在使用弱引用時需要特别小心，避免出現意外的對象被回收的情況。