1 多益網(wǎng)絡面試

Q：博客項目里面如何驗證賬號密碼的？有沒有做什么安全措施

A：

• 在登錄表單中填寫用戶名和密碼后豹芯，表單對象會調用is_valid()方法驗證輸入的數(shù)據(jù)是否合法朗恳，如果合法的話就使用cleaned_data對數(shù)據(jù)進行清洗请唱，再調用authenticate()檢驗清洗后的數(shù)據(jù)能否正確匹配數(shù)據(jù)庫中的用戶讯赏，如果匹配到了义黎，那就調用login()方法實現(xiàn)登錄，否則提示“賬號或密碼輸入錯誤”姐呐。
• 安全措施：做了CSRF（跨站請求偽造）的防御殿怜。
  • CSRF解釋：當用戶C登錄A網(wǎng)站時，網(wǎng)站會驗證用戶賬戶密碼皮钠，驗證成功后返回一個sessionId存到用戶C的cookie中，下次想訪問A網(wǎng)站數(shù)據(jù)時會帶著cookie發(fā)起請求赠法，服務器會根據(jù)cookie中的sessionId驗證用戶身份是否合法麦轰。在網(wǎng)站A登錄的狀態(tài)下，如果用戶在同一個瀏覽器中訪問了黑客網(wǎng)站砖织，那么黑客網(wǎng)站也可以利用存儲在瀏覽器中的合法的cookie對網(wǎng)站A發(fā)起請求款侵，而網(wǎng)站A也會正常的響應，誤以為是用戶C自己的操作侧纯。
  • 防御機制：采用token機制新锈。要抵御CSRF，關鍵在于在請求中加入黑客網(wǎng)站不能偽造的信息眶熬，并且該信息不能存在于cookie中妹笆】榍耄可以在http請求中以參數(shù)的形式加入一個隨機產(chǎn)生的token，并由服務器端對這個token進行驗證拳缠，如果沒有token或者token錯誤墩新，則拒絕客戶端的請求。
  • token的產(chǎn)生：在客戶端對服務器端的請求認證成功時窟坐，服務器端會返回一個token給客戶端海渊。
  • token的存放位置：看了很多答案，大概知道了存放位置哲鸳，有兩種存放方式臣疑，一個是放在form的隱藏域里（這種做法行得通的原因好像是黑客網(wǎng)站不訪問用戶的前端，所以獲取不到token值徙菠，也就無法通過驗證讯沈。[2]中還介紹了除了token機制外的防御手段）；一個是放在具有http_only屬性的cookie字段中懒豹，當用了http_only屬性后芙盘，那么通過js腳本將無法讀取到cookie信息，只能使用cookie脸秽，而不能讀取cookie中的內(nèi)容儒老，當然也包括csrf_token了，所以服務器端只需要比較cookie中的csrf_token和請求頭中的csrf_token值是否相等即可判斷是否是CSRF攻擊了记餐。
  • 參考：
    [1] CSRF驮樊、cookie、session和token之間不得不說得那些事兒
    [2] csrf攻擊與防范

補充：

項目中如何

Q：在公司里實習學到了什么

Q：如何看待加班這件事

Q：進程和線程

Q：有沒有遇到過內(nèi)存泄漏問題片酝，如何解決

Q：python深拷貝與淺拷貝

Q：TCP和UDP的區(qū)別

• A：
  TCP：傳輸控制協(xié)議囚衔，是一種面向連接的可靠的傳輸協(xié)議。
  UDP：用戶數(shù)據(jù)包協(xié)議雕沿，是一種面向非連接的不可靠的傳輸協(xié)議练湿。
  面向連接：客戶端和服務器端傳輸前進行溝通和協(xié)商，確鄙舐郑互相可以發(fā)送數(shù)據(jù)肥哎。
  TCP適用于傳輸大量數(shù)據(jù)的場合，傳輸速度較慢疾渣，而UDP適用于對傳輸效率要求高的場合篡诽，例如網(wǎng)絡電視等，傳輸速度快榴捡。
  TCP和UDP的具體應用

  
  
  TCP和UDP的具體應用

參考面試官說：說說TCP和UDP吧

Q：STL里的迭代器

Q：了解哪些數(shù)據(jù)庫杈女，介紹一下

Q：編程題：給定一個集合S(沒有重復元素), 輸出它所有的子集 輸入 1 2 3 輸出 1, 2, 12, 3, 13, 23, 123

A：leetcode上類似題目子集

2 富途面試

Q：研究算法，為什么選開發(fā)呢

Q：（項目相關）用到了什么數(shù)據(jù)庫，用了數(shù)據(jù)庫中什么功能达椰，sqlite和mysql的區(qū)別翰蠢，數(shù)據(jù)庫事務

A：
用到了sqlite數(shù)據(jù)庫，存儲用戶名和密碼砰碴，存儲文章躏筏、刪除文章等功能；
sqlite是輕量級數(shù)據(jù)庫呈枉，適合做中小站點的內(nèi)容管理系統(tǒng)趁尼，很多語言中無需配置即可支持sqlite，在數(shù)據(jù)量不大的情況下讀取很快猖辫，沒有復雜的驗證操作酥泞；但是處理并發(fā)的能力較差，寫入速度較慢啃憎，為已有的表加索引較慢芝囤。
數(shù)據(jù)庫事務( transaction)是訪問并可能操作各種數(shù)據(jù)項的一個數(shù)據(jù)庫操作序列，這些操作要么全部執(zhí)行,要么全部不執(zhí)行辛萍，是一個不可分割的工作單位悯姊。事務由事務開始與事務結束之間執(zhí)行的全部數(shù)據(jù)庫操作組成。
特性：
原子性：事務中的操作是不可分割的贩毕，要么全部執(zhí)行悯许，要么全部不執(zhí)行；
一致性：幾個并行執(zhí)行的事務辉阶，其結果必須與按某一順序串行執(zhí)行的結果一致先壕；
隔離性：事務的執(zhí)行不受其它事務的干擾，事務執(zhí)行的中間結果對其它事務必須是透明的谆甜；不考慮隔離性可能會出現(xiàn)臟讀垃僚、幻讀、不可重復讀的問題规辱。
臟讀：事務A讀到了事務B修改后但還未提交的數(shù)據(jù)

image.png

不可重復讀：事務A兩次讀取同一數(shù)據(jù)谆棺，但結果不一樣

image.png

臟讀和不可重復讀的區(qū)別：前者讀到了其它事務未提交的數(shù)據(jù)，后者讀到了其它事務已提交的數(shù)據(jù)罕袋。
幻讀：在事務A中先后查詢兩次數(shù)據(jù)庫改淑，兩次查詢結果的條數(shù)不一樣

image.png

參考：
[1] Sqlite和mysql的區(qū)別及優(yōu)缺點
[2] 數(shù)據(jù)庫事務
[3] 一文說盡MySQL事務及ACID特性的實現(xiàn)原理

Q：python和其它語言的區(qū)別

A：
python是強類型的動態(tài)的解釋性語言。
強類型和弱類型：語言是否會隱式進行類型轉換询吴。如果會掠河，則是弱類型亮元，如果不會，則是強類型唠摹。
動態(tài)與靜態(tài)：動態(tài)語言在定義變量時不需要指定變量的類型爆捞，在運行期間才去做變量類型的檢查，而靜態(tài)語言則需要定義的時候就聲明類型勾拉。
解釋型語言與編譯型語言：解釋型語言是在代碼運行時進行解釋煮甥，不需要事先編譯；而編譯型語言則需要先將代碼翻譯成機器碼（C/C++會這么做）或者中間碼（Java會用虛擬機將中間碼映射成機器碼）藕赞。一般會經(jīng)歷編譯（將源碼編譯成機器碼）和鏈接（將各個模塊的機器碼和依賴庫連起來生成可執(zhí)行文件）兩個步驟
參考：[1] Python和其他語言有什么區(qū)別成肘？

Q：加密算法有了解嗎

A：加密算法有哈希算法、對稱加密算法和非對稱加密算法斧蜕。哈希算法中常見的有md5算法双霍、SHA系列算法，哈希算法不能解密批销，只能用來生成簽名洒闸；對稱加密就是收發(fā)雙方用同一個密鑰來加密解密；非對稱算法則是用一對密鑰來加密解密均芽，既可以用公鑰加密私鑰解密丘逸，也可以用私鑰加密公鑰解密。
md5加密算法骡技，是對原文進行加密鸣个，得到一個128bit的散列值，不可以被解密囤萤。常見的應用是很多網(wǎng)站數(shù)據(jù)庫存儲用戶密碼的時候存的都是密碼的md5值，當用戶登錄時富雅，只需要生成用戶輸入的密碼的md5值，與數(shù)據(jù)庫中存儲的該用戶的密碼md5值比較蛤奢，即可判斷密碼是否正確待秃，這樣可以避免密碼明文直接被看到。
參考：
[1] md5加密算法
[2] 漫畫：什么是加密算法暖庄？

Q：TCP協(xié)議下，數(shù)據(jù)傳輸錯誤了怎么辦

A：TCP有重傳機制。經(jīng)典的TCP重傳是發(fā)送端主動重傳的象缀，當數(shù)據(jù)包經(jīng)過一段時間后還沒有被接收端確認的情況下霞怀，發(fā)送端會主動重傳數(shù)據(jù)包；還有Fast Retransmit機制是接收端主動要求重傳的徐矩，當接收端收到了錯誤的數(shù)據(jù)包時會重復第二次握手的操作滤灯，讓發(fā)送端知道它第三次握手時傳的數(shù)據(jù)包是錯的鳞骤，觸發(fā)發(fā)送端重新發(fā)送數(shù)據(jù)包黍判。

Q：說一下進程和線程，進程之間如何通信美旧，補充：線程之間如何通信

A：

• 進程是資源分配的最小單位，線程是程序執(zhí)行的最小單位陈症，也是cpu調度的最小單位录肯，進程是線程的集合吊说；進程有獨立的地址空間厅贪，而線程共享進程中的數(shù)據(jù)养涮，使用相同的地址空間；多進程程序情況下悄谐，一個進程壞掉并不會影響另一個進程，但是多線程程序中只要有一個線程壞掉杂腰，整個進程也跟著壞掉了。
• 進程間通信方式：
  管道( pipe )：
  管道包括三種:
  · 普通管道PIPE：通常有兩種限制,一是單工,只能單向傳輸;二是只能在父子或者兄弟進程間使用.
  · 流管道s_pipe: 去除了第一種限制,為半雙工毒坛，只能在父子或兄弟進程間使用，可以雙向傳輸.
  · 命名管道:name_pipe：去除了第二種限制,可以在許多并不相關的進程之間進行通訊.
  信號量( semophore ) ：
  · 信號量是一個計數(shù)器，可以用來控制多個進程對共享資源的訪問劣摇。它常作為一種鎖機制钧惧，防止某進程正在訪問共享資源時艺栈，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內(nèi)不同線程之間的同步手段铐懊。
  消息隊列( message queue ) ：
  · 消息隊列是由消息的鏈表空闲，存放在內(nèi)核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少残邀、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。
  信號 ( sinal ) ：
  · 信號是一種比較復雜的通信方式蹋砚，用于通知接收進程某個事件已經(jīng)發(fā)生扼菠。
  共享內(nèi)存( shared memory ) ：
  · 共享內(nèi)存就是映射一段能被其他進程所訪問的內(nèi)存，這段共享內(nèi)存由一個進程創(chuàng)建坝咐，但多個進程都可以訪問循榆。共享內(nèi)存是最快的 IPC 方式，它是針對其他進程間通信方式運行效率低而專門設計的墨坚。它往往與其他通信機制秧饮，如信號量，配合使用泽篮，來實現(xiàn)進程間的同步和通信盗尸。
  套接字( socket ) ：
  · 套接字也是一種進程間通信機制，與其他通信機制不同的是帽撑，它可用于不同機器間的進程通信振劳。
• 線程之間通信方式：
  鎖；wait/notify機制油狂；管道历恐；信號量

Q：說一下http協(xié)議寸癌，在哪一層，補充：https協(xié)議弱贼，網(wǎng)絡七層協(xié)議

A：http是超文本傳輸協(xié)議蒸苇，用于客戶端和服務器端之間的通信，它是無狀態(tài)的吮旅，并且不安全溪烤，因為http協(xié)議的信息傳輸完全以明文方式，不做任何加密庇勃。http協(xié)議在應用層檬嘀。https是超文本傳輸安全協(xié)議，在http協(xié)議基礎上增加了SSL安全層责嚷，可進行加密傳輸和身份認證鸳兽。http使用的端口號是80，https使用的端口號是443

image.png

Q：說一下自己做的項目

Q：說一下b+樹爆班，mysql中為什么用b+樹而不用b樹

Q：用不用linux衷掷，說一些常見指令

A：ls、mkdir柿菩、cp戚嗅、mv、rm
參考：Linux常用命令大全『全集手冊』
)

3 美團面試

Q：死鎖是什么枢舶，死鎖產(chǎn)生的原因

A：死鎖是指兩個或兩個以上的進程渡处，在競爭資源或者彼此通信而造成的一種阻塞的現(xiàn)象，若無外力作用祟辟，它們都將無法推進下去医瘫。
產(chǎn)生的必要條件有四個：

• 互斥使用：當資源被一個進程使用時，其它進程不能使用
• 不可搶占：資源請求者不能強制從資源占有者手中奪取資源旧困，資源只能由資源占有者主動釋放
• 請求和保持：資源請求者在請求新資源的同時醇份，還保持對原有資源的占有
• 循環(huán)等待：存在一個等待隊列：P1占P2的資源，P2占有P3的資源吼具，P3占有P1的資源僚纷，這樣就形成了一個等待環(huán)路。
  產(chǎn)生的原因：競爭資源會引起死鎖（當資源數(shù)目不足以滿足進程所請求的資源數(shù)目拗盒，這會導致進程競爭資源而產(chǎn)生死鎖）
  如何預防死鎖：打破死鎖產(chǎn)生的條件怖竭，如下
• 打破互斥條件：將獨占式資源改成虛擬資源
• 打破不可搶占條件：當一個進程占有一獨占性資源后又申請新的資源而無法滿足，此時退出原占有的資源
• 打破占有且申請條件：采用資源預先分配策略陡蝇，即進程運行前申請全部資源痊臭，滿足則運行哮肚，不然則等待
• 打破循環(huán)等待條件：規(guī)定資源有序分配，對所有設備實現(xiàn)分類編號广匙，所有進程只能采用按序號遞增的形式申請資源

待補充：銀行家算法

參考：什么是死鎖允趟，發(fā)生原因是什么，如何解決和避免產(chǎn)生死鎖鸦致？

Q：進程和線程（什么情況下一個線程壞掉可能會導致整個進程都壞掉）

Q：linux下的指令

• ls常用指令
  
  
  參考：Linux ls 命令
• 遞歸地創(chuàng)建文件夾與其子文件夾
  mkdir -p test1/test2/test3 //遞歸創(chuàng)建
• 查看進程中各種指標
• 如何查看剩余內(nèi)存
  使用free命令潮剪，查看free列
• 如何查看端口是否被占用

1. netstat -anp|grep 端口號 //查看端口號是否被占用
2. netstat -nultp //查看當前所有已經(jīng)使用的端口情況
   補充：查看具體端口號時，必須要看到tcp分唾、端口號抗碰、狀態(tài)為listen，才表示端口被占用绽乔。
   參考

• 如何查看一個程序的PID以及它的所有子進程

  • 查看PID
  1. 可以用top命令查看所有進程信息弧蝇，通過進程名找到PID

  2. 用pgrep 進程名可以查看
  • 根據(jù)PID查看進程的子進程pstree -p 進程號
    
    
    補充：根據(jù)pid查看所有線程
    參考： Linux查看進程的所有子進程和線程

• 如何為一個目錄下的所有文件添加權限
  chmod -R 權限代碼 文件名，例如

  參考：linux 給所有文件下文件加權限

• 如果你對一個目錄具有寫權限迄汛，那么你是否具有對這個目錄下的所有文件具有刪除權限捍壤？（沒找到答案骤视，但是答案應該是不一定鞍爱，我應該屬于文件屬主，有寫權限专酗，但是刪除權限未指明睹逃，所以不知道有沒有）

• 修改IP地址的方法

  
  

• 根據(jù)文件名查找
  find / -name aabbcc 查找/目錄下名為 aabbcc的文件
  還有種方法使用grep來查找
• 以遞歸的方式查找符合條件的文件。例如祷肯，查找指定目錄/etc/acpi 及其子目錄（如果存在子目錄的話）下所有文件中包含字符串"update"的文件沉填，并打印出該字符串所在行的內(nèi)容
  grep -r update /etc/acpi
  參考：
  [1] 教程 | Linux常用命令大全

Q：說說有哪些樹吧，說說b+樹吧佑笋，b+樹有什么缺陷嗎

A：這里只回答b+樹的缺陷翼闹，由于b+樹的非葉節(jié)點只存放索引記錄，所以即便非葉節(jié)點中的值等于要查找的值時蒋纬，查找也并不會終止猎荠，而是繼續(xù)向下直到葉子節(jié)點，因此在b+樹中蜀备，無論查找成功與否关摇，都走了一條從根節(jié)點到葉子節(jié)點的路徑。而b樹由于非葉節(jié)點中既存放索引元素碾阁，也存放數(shù)據(jù)記錄输虱，所以當要查找的值恰好在非葉節(jié)點上時，找到后便會結束查詢脂凶。

Q：★★★★★進程調度的策略（有時間詳看）

A：進程調度的策略

• 先來先服務策略
  每次調度是從進程隊列中選擇一個最先進入該隊列的進程宪睹，為之分配資源投入運行愁茁，該進程一直運行完成或者發(fā)生某事件而阻塞后才繼續(xù)處理后面的進程。
• 短進程優(yōu)先策略
• 最高響應比優(yōu)先法
• 時間片輪轉算法
  系統(tǒng)還是按照先來先服務調度就緒進程横堡，但每次調度時埋市，CPU都會為隊首進程分配并執(zhí)行一個時間片（幾ms~百ms），時間片用完后計時器就產(chǎn)生時鐘中斷命贴，停止該進程并將它送到隊尾道宅，其他依次執(zhí)行，這樣可以保證系統(tǒng)在給定的時間內(nèi)執(zhí)行所有用戶進程的請求胸蛛。
• 多級反饋隊列
  （1）設置多個就緒隊列污茵，每個隊列優(yōu)先級依次減小，為各個隊列分配的時間片大小不同葬项，優(yōu)先級隊列越高泞当，里面進程規(guī)定的執(zhí)行時間片就越小民珍；
  （2）隊列中還是按照FCFS原則排隊等待襟士，如果第一隊列隊首進程在規(guī)定的時間片內(nèi)未執(zhí)行完，則直接調送至第二隊尾嚷量，依次向后放一個隊列的隊尾陋桂。因此一個長作業(yè)進程會分配到n個隊列的時間片執(zhí)行。
  （3）按照隊列先后依次執(zhí)行蝶溶，如果新進的待處理進程優(yōu)先級較高嗜历，則新進程將搶占正在運行的進程，被搶占的進程放置在正在運行的隊尾抖所。
  參考：操作系統(tǒng)中進程調度策略有哪幾種梨州？

補充：頁面置換的策略

• 最佳置換算法（OPT）
• 先進先出算法（FIFO）
• 最近最久未使用算法（LRU）

Q：說說hashmap吧，哈希表擴容的選擇有什么策略（2的n次方）

A：哈希表擴容一般有兩種方案田轧，最常用的是將哈希表的容量擴張為原容量的兩倍暴匠，還有一種方法是選擇一個更大的素數(shù)，這樣可以減少沖突傻粘。
補充：就第一種方法每窖，談談java和redis中擴容的實現(xiàn)
A：java中擴容的瞬間，需要先將原哈希表中的數(shù)據(jù)rehash到新哈希表中抹腿，這個過程較慢岛请，此時若插入新元素，等待時間較長警绩；而redis采用的是分攤轉移的方式崇败，在擴容的瞬間先將第一個不為空的桶中的數(shù)據(jù)轉移到新哈希表中，然后插入新元素，當下一次再插入時后室，繼續(xù)轉移第一個不為空的桶中的元素缩膝，然后插入新元素，重復此步驟岸霹，直到舊哈希表為空
補充：Java中哈希表機制：java中哈希表的默認大小是16疾层，當一個箱子中鏈表長度大于8的時候，將鏈表轉為紅黑樹贡避，當長度小于6時痛黎，將紅黑樹轉為鏈表（這么做的原因是根據(jù)泊松分布，當負載因子達到0.75時刮吧，某個箱子的鏈表長度為8的概率為0.00000006湖饱，這種可能性是小到可以忽略的。我們甚至可以斷言杀捻，如果有了這種情況的出現(xiàn)井厌，那一定是哈希函數(shù)設計的不合理所導致的），所以java中這種轉化機制一定程度上避免了不恰當?shù)墓：瘮?shù)導致的性能問題致讥。
補充：在redis中仅仆，新元素的插入位置是鏈表的頭部，而不是尾部垢袱，這么做的原因有兩個：1）頭插法時間復雜度是O(1)墓拜，而尾插法時間復雜度是O(n)；2）根據(jù)實際應用來考慮惶桐，最新插入的數(shù)據(jù)往往會更頻繁地被使用撮弧，這樣也能節(jié)省查找時間
參考：【數(shù)據(jù)結構之哈希表（二）】 哈希表的擴容實現(xiàn)機制

Q：mysql中一張表最多存儲多少數(shù)據(jù)

A：mysql中一張表最多有4096列潘懊，每行的大小最多是65535bytes姚糊，表的行數(shù)沒有要求（數(shù)據(jù)都來自官網(wǎng)）。

算法題

Q：二叉樹的前序遍歷（遞歸法與迭代法）

Q：快速排序找第K大數(shù)

閑聊

Q：您在我這個年紀（25授舟、6歲）的時候在干嘛呢救恨？

A：在玩，沒有規(guī)劃释树，非科班出身肠槽，起點比你們低很多，走到今天這步得益于好領導奢啥、好伴侶秸仙，他們會在人生路上不斷地扶正你、督促你桩盲，當然還有自己的努力寂纪，再加上一些運氣成分。

總結：

這個面試官很好，心平氣和嘻嘻哈哈捞蛋，第一次發(fā)問的問題都很簡單孝冒，看似隨意，但是涉及的范圍挺廣拟杉，第二次發(fā)問的問題就是根據(jù)我的回答來的庄涡，看我到底掌握的有多深。

快手測試開發(fā)面試（結束三面搬设，等通知）

數(shù)據(jù)庫是重中之重

Q：創(chuàng)建數(shù)據(jù)庫穴店，使用數(shù)據(jù)庫的語句

Q：在一張表（學號id,姓名name,性別sex,城市city,創(chuàng)建時間c_time）中插入一條數(shù)據(jù)該如何插入（兩種寫法）；統(tǒng)計男女生人數(shù)拿穴；統(tǒng)計每個城市中男女生人數(shù)

Q：創(chuàng)建一張主鍵自增的學生表迹鹅，創(chuàng)建一張主鍵自增，外鍵是課程名的學生成績表

Q：列表和元組的區(qū)別贞言，它們都適用于什么情況

A：

• 列表是可變類型斜棚，元組是不可變類型
• 列表的內(nèi)容和長度可以改變，元組的內(nèi)容和長度不能改變该窗，但是可以通過分片和元組相加的方式改變元組弟蚀，不過這樣的話就會指向一個新元組了
• 由于元組不可變，所以它可以作為字典的key和集合中的元素
• 元組比列表更精簡酗失，支持的操作更少义钉，創(chuàng)建元組比創(chuàng)建列表更快，元組占用的空間比列表更小
  補充：列表规肴、元組都是有序的捶闸，而字典和集合是無序的。（兩個對象中元素順序不同拖刃，結果是否相同删壮，如a={1,2,3},b={3,2,1},print(a==b)返回True）

Q：三次握手

Q：客戶端發(fā)送一個http請求后，都經(jīng)歷了什么

Q：ack和ACK的區(qū)別是什么

A：ACK是確認標志兑牡，為1時表示確認連接央碟；ack是確認號，它的值等于上一次遠端主機傳來的seq值+1均函，表示已成功接收上一次傳來的所有數(shù)據(jù)亿虽。

Q：http報文和tcp報文

Q：python寫一個客戶端與服務器端通信的程序

Q：字符串匹配的程序

Q：統(tǒng)計字符串中第一次出現(xiàn)的字符，統(tǒng)計字符串中出現(xiàn)m次的第n個字符

Q：問項目問的也比較多苞也，深度學習的項目洛勉，博客的項目為什么用django，你還知道哪些框架如迟，它們的區(qū)別是什么收毫，問公司里做的自動化發(fā)布項目

Q：正則表達式，匹配正整數(shù)（這也是根據(jù)公司的項目問的）

Q：Linux語句知道哪些，如何在某文件夾下查找a.txt文件

Q：堆和棧的區(qū)別

A：堆由程序員分配（通過new牛哺，malloc分配）釋放陋气，空間比較大，結構類似于鏈表引润，如果程序員未釋放返咱，在程序結束后可能由操作系統(tǒng)回收塑顺，堆中存放的是對象本身嵌牺；棧由系統(tǒng)分配釋放蒙保，空間比較小，結構類似于數(shù)據(jù)結構中的棧奴曙，存放的是函數(shù)的參數(shù)别凹、局部變量等
參考：
[1] 堆和棧的區(qū)別有哪些
[2] 堆和棧的區(qū)別是什么？
[3] 什么是堆洽糟？什么是棧炉菲？他們之間有什么區(qū)別和聯(lián)系？ - 思羽的回答 - 知乎

中國工商銀行測試開發(fā)（幾乎沒問技術問題坤溃，都是根據(jù)簡歷里寫的來問的）

Q：django是B/S框架拍霜，如果我想提高瀏覽器/系統(tǒng)性能，該怎么做呢薪介？

A：沒找到答案祠饺，改天再找

咪咕大數(shù)據(jù)算法工程師

Q：現(xiàn)在有文檔A和文檔B，每個文檔中有100萬條記錄汁政，如果想找出A道偷、B中最相似的記錄，在不做任何優(yōu)化的情況下记劈，時間復雜度是O(n^2)勺鸦，該如何優(yōu)化時間復雜度呢？

A：面試的時候沒回答好抠蚣，后來想了下祝旷，面試時候說的其實已經(jīng)有點說到點子上了履澳，那就是先對B文檔進行排序（用前綴樹）嘶窄，然后將其分為幾個類（假設是k個類），從這k個類中各取出一條記錄（怎么取距贷，去每個類中中間那條記錄嗎）柄冲，然后從A中取一條記錄a，用a記錄和B中k條記錄計算相似度忠蝗，會得到幾個相似度现横，假設k條記錄中，記錄b與記錄a最為相似，那么和a記錄最相似的記錄應該就在記錄b所在的那個類戒祠，然后挨個比較（可能還有優(yōu)化的余地骇两，不知道可不可以用二分比較），找出最相似的記錄姜盈。時間復雜度變成O(nk+nlogkn)（logkn是以k為底低千，n的對數(shù)）。

自己總結

Q：python如何創(chuàng)建線程（待實踐）

A：有兩種方式：一種是直接調用Threading模塊中的Thread類來創(chuàng)建馏颂，然后調用start方法示血；另一種是繼承Threading.Thread，然后重寫run方法救拉，然后調用start方法难审；
參考：python3 開啟多線程的兩種寫法

這兩種方式的區(qū)別
參考：python線程的幾種創(chuàng)建方式

Q：多線程如何執(zhí)行

A：如果線程數(shù)小于CPU核心數(shù)，則為每個線程分配一個核心亿絮，如果線程數(shù)大于CPU核心數(shù)告喊，則按時間片執(zhí)行線程，當某個線程的時間片結束了派昧，就會切換到別的線程葱绒，線程切換是會保存上下文的，這樣可以確保下次切回去的時候可以沿著上次切換的地方繼續(xù)執(zhí)行斗锭。
參考：多線程如何執(zhí)行

Q：http和https的區(qū)別

Q：mysql和redis的區(qū)別

A：mysql是關系型數(shù)據(jù)庫地淀，主要用于存放持久化數(shù)據(jù)，將數(shù)據(jù)存儲在硬盤中岖是，讀取速度較慢帮毁；而redis是緩存數(shù)據(jù)庫，主要用于存放使用較為頻繁的數(shù)據(jù)豺撑，將數(shù)據(jù)存儲在緩存中烈疚，讀取速度較快。兩個數(shù)據(jù)庫一般都是配合使用聪轿，mysql（主）+ redis（輔）爷肝，當應用訪問數(shù)據(jù)時，先在redis中查找是否存在陆错，如果不存在則去mysql中查找灯抛。
參考：
[1] mysql和redis的區(qū)別

Q：mysql索引講一下，聚簇索引講一下

A：

• 索引也叫做“鍵”音瓷，是一種用于快速找到數(shù)據(jù)庫中某條記錄的數(shù)據(jù)結構对嚼。mysql中索引的存儲類型有兩種：BTREE和HASH。
• 為什么數(shù)據(jù)庫索引用B樹绳慎，而不用二叉查找樹來實現(xiàn)呢纵竖？
  • 關鍵在于磁盤IO漠烧。從算法層面來說，二叉查找樹的查找速度和比較次數(shù)都是最小的靡砌，但是必須得考慮現(xiàn)實問題：磁盤IO已脓。數(shù)據(jù)庫索引是存放在磁盤上的，在索引文件比較大的情況下利用索引查詢的時候通殃，我們無法一次將整個索引全部加載到內(nèi)存中摆舟，我們只能逐一加載每個磁盤頁，這里的磁盤頁對應著索引樹的節(jié)點邓了。因為磁盤IO的次數(shù)對應了樹的高度恨诱，所以為了減小高度，需要把瘦高的二叉樹變成矮胖的b樹骗炉。其實b樹在查詢中的比較次數(shù)并不比二叉查找樹少照宝，但是比較是在內(nèi)存中進行的，速度很快句葵，和磁盤IO的耗時比起來幾乎可以忽略厕鹃。（b樹的每個節(jié)點最多包含m個孩子，m被成為b樹的階乍丈，m的大小取決于磁盤頁的大屑敛辍）

• b樹的特點
• 在聚簇索引中，葉子節(jié)點直接包含衛(wèi)星數(shù)據(jù)轻专；在非聚簇索引中忆矛，葉子節(jié)點帶有指向衛(wèi)星數(shù)據(jù)的指針（衛(wèi)星數(shù)據(jù)就是索引元素指向的數(shù)據(jù)記錄。在b樹中無論中間節(jié)點還是葉子節(jié)點都帶有衛(wèi)星數(shù)據(jù)请垛，而在b+樹中只有葉子節(jié)點帶有衛(wèi)星數(shù)據(jù)催训，其余中間節(jié)點僅僅是索引，沒有任何數(shù)據(jù)關聯(lián)）宗收。
  innodb中漫拭，聚簇索引和非聚簇索引（也叫二級索引或輔助索引）都是一棵b+樹，只是按照不同的值來構造的混稽，聚簇索引是按照主鍵值（一般是一個自增的主鍵采驻，沒有的話mysql會自己創(chuàng)建）構造的b+樹，葉子節(jié)點存放的是主鍵和主鍵對應的數(shù)據(jù)記錄匈勋；而輔助索引是根據(jù)其它字段（輔助鍵）構建的一棵b+樹礼旅，它的葉子節(jié)點中存放的是輔助鍵+主鍵；利用輔助索引查找數(shù)據(jù)記錄時颓影，其實最重要的還是找到主鍵各淀，然后去聚簇索引樹中找到數(shù)據(jù)記錄。（補充（from 徐悅）：覆蓋索引：當查詢的字段被索引覆蓋時诡挂，會直接輸出結果碎浇，而不會回表。例子： 比如璃俗，學生表 Student(id,name,age),主鍵是ID奴璃，你以(name,age)字段建立了索引，當你查詢 select name城豁，age where name = ? and age= ?時苟穆，你可以直接在二級索引就獲得這兩個字段，就不需要去聚簇索引樹查到真實數(shù)據(jù)行唱星，再獲得數(shù)據(jù)了）
  MyISAM中重點是非聚簇索引（為什么叫非聚簇：因為它的索引文件和數(shù)據(jù)文件是分離的雳旅，索引文件僅保存數(shù)據(jù)記錄的地址，而且與innodb中的聚簇也好區(qū)分開來）间聊，和innodb中的非聚簇不太一樣攒盈，不要混淆，MyISAM的非聚簇索引也是按照主鍵來構造的b+樹哎榴，只不過它的葉子節(jié)點中存放的是主鍵+數(shù)據(jù)記錄的地址型豁。
• 補充：哈希索引看[2]

參考：
[1] mysql索引
[2] MySQL中的Hash索引解讀
[3] 聚簇索引和非聚簇索引(通俗易懂 言簡意賅)

Q：B樹與B+樹

• b樹的特征：
  1.根結點至少有兩個子女。
  2.每個中間節(jié)點都包含k-1個元素和k個孩子尚蝌，其中 m/2 <= k <= m
  3.每一個葉子節(jié)點都包含k-1個元素迎变，其中 m/2 <= k <= m
  4.所有的葉子結點都位于同一層。
  

  5.每個節(jié)點中的元素從小到大排列飘言，節(jié)點當中k-1個元素正好是k個孩子包含的元素的值域分劃衣形。
  image.png

• b+樹的特征
  1.有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素），每個元素不保存數(shù)據(jù)姿鸿，只用來索引泵喘，所有數(shù)據(jù)都保存在葉子節(jié)點。
  2.所有的葉子結點中包含了全部元素的信息般妙，及指向含這些元素記錄的指針纪铺，且葉子結點本身依關鍵字的大小自小而大順序鏈接。
  

  3.所有的中間節(jié)點元素都同時存在于子節(jié)點碟渺，在子節(jié)點元素中是最大（或最邢拭）元素。
  image.png
• b+樹的優(yōu)勢：
  1.單一節(jié)點存儲更多的元素苫拍，使得查詢的IO次數(shù)更少芜繁。
  2.所有查詢都要查找到葉子節(jié)點，查詢性能穩(wěn)定绒极。
  3.所有葉子節(jié)點形成有序鏈表骏令，便于范圍查詢。
  參考：
  [1] 漫畫：什么是B+樹垄提？
  [2] 漫畫：什么是B-樹榔袋？

Q：post和get的區(qū)別

A：
1周拐、Get是用來從服務器上獲得數(shù)據(jù)，而Post是用來向服務器上傳遞數(shù)據(jù)凰兑。
2妥粟、Get將表單中數(shù)據(jù)的按照variable=value的形式，添加到action所指向的URL后面吏够，并且兩者使用“?”連接勾给，而各個變量之間使用“&”連接；Post是將表單中的數(shù)據(jù)放在form的數(shù)據(jù)體中锅知，按照變量和值相對應的方式播急，傳遞到action所指向URL。
3售睹、Get是不安全的桩警，因為在傳輸過程，數(shù)據(jù)被放在請求的URL中侣姆，而如今現(xiàn)有的很多服務器生真、代理服務器或者用戶代理都會將請求URL記錄到日志文件中，然后放在某個地方捺宗，這樣就可能會有一些隱私的信息被第三方看到柱蟀。另外，用戶也可以在瀏覽器上直接看到提交的數(shù)據(jù)蚜厉，一些系統(tǒng)內(nèi)部消息將會一同顯示在用戶面前长已。Post的所有操作對用戶來說都是不可見的，所以表單提交應該用post昼牛。
4术瓮、Get傳輸?shù)臄?shù)據(jù)量小，這主要是因為受URL長度限制贰健；而Post可以傳輸大量的數(shù)據(jù)胞四，所以在上傳文件只能使用Post（當然還有一個原因，將在后面的提到）伶椿。
5辜伟、Get限制Form表單的數(shù)據(jù)集的值必須為ASCII字符；而Post支持整個ISO10646字符集脊另。
6导狡、Get是Form的默認方法。
使用Post傳輸?shù)臄?shù)據(jù)偎痛，可以通過設置編碼的方式正確轉化中文旱捧；而Get傳輸?shù)臄?shù)據(jù)卻沒有變化。

Q：三次握手和四次斷開的過程

A：
三次握手：1）首先客戶端向服務器發(fā)送SYN（syn=a）包踩麦，進入SYN_SENT狀態(tài)枚赡，等待服務器確認氓癌；2）服務器收到SYN包，確認客戶端的SYN（ack=a+1）标锄，同時自己發(fā)送SYN（syn=b）包顽铸，即服務器發(fā)送SYN+ACK包茁计，此時服務器進入SYN_RCVD狀態(tài)料皇；3）客戶端受到服務器的SYN+ACK包，向服務器發(fā)送確認包ACK（ack=b+1）星压，發(fā)送完畢后践剂，客戶端和服務器進入ESTABLISHED（TCP連接成功）狀態(tài)，完成三次握手娜膘。

image.png

補充：前兩個包都是顯性確認逊脯，第三個包是隱形確認，操作方法是：服務器在收到第三個包之前會猜想竣贪，如果第三個包和自己猜想的一樣军洼，那么就不回復，如果受到的包和猜想的不一樣或者沒有收到包演怎，那么服務器就重新傳輸?shù)诙€包匕争，以至于客戶端知道自己發(fā)送的第三個數(shù)據(jù)包失敗。（服務器怎么知道第三個數(shù)據(jù)包的內(nèi)容呢爷耀？第三個數(shù)據(jù)包的內(nèi)容來自服務器發(fā)哦是那個的第二個數(shù)據(jù)包的內(nèi)容或者內(nèi)容+1甘桑，即ACK確認下一個想要對方的數(shù)據(jù)包）
四次斷開：
1）客戶端C發(fā)送一個FIN，用來關閉客戶端到服務器S的數(shù)據(jù)傳送
2）服務器S收到這個FIN歹叮，它發(fā)回一個ACK跑杭，確認序號為收到的序號加1。和SYN一樣咆耿，一個FIN將占用一個序號
3）服務器S關閉與客戶端C的連接德谅，發(fā)送一個FIN給客戶端C
4）客戶端C發(fā)回ACK報文確認，并將確認序號設置為收到序號加1
補充：為什么斷開需要四次萨螺？為什么FIN數(shù)據(jù)包和ACK數(shù)據(jù)包不能一起發(fā)窄做？

斷開雙方都要收到應用層的指令才可以，當對方收到斷開請求時并不清楚他自己的應用層要不要斷開屑迂，所以先回復收到的確認浸策，同時再問應用層要不要斷開，同意后再發(fā)送自己的斷開惹盼，另一方收到后確認最終斷開庸汗。

Q：mysql中最左匹配原則

Q：python內(nèi)存泄漏與垃圾回收

A：

• 內(nèi)存泄漏是指程序中已動態(tài)分配的堆內(nèi)存（為什么不是棧內(nèi)存，因為棧內(nèi)存是由系統(tǒng)自動分配和釋放的）由于某種原因（例如忘記釋放）程序未能釋放或者無法釋放手报，造成系統(tǒng)內(nèi)存的浪費蚯舱，導致程序運行變慢或者系統(tǒng)崩潰等后果改化。
  垃圾回收機制是針對內(nèi)存泄漏而提出的內(nèi)存管理方法。
• 垃圾回收機制有引用計數(shù)枉昏、標記清除陈肛、分代回收
  • 引用計數(shù)法的原理是對每個對象維護一個ob_ref，用來記錄當前對象被引用的次數(shù)兄裂，也就是來追蹤到底有多少引用指向了該對象句旱，如果引用數(shù)為0，銷毀該對象的內(nèi)存晰奖。引用計數(shù)的優(yōu)點是：高效谈撒、實時、對象有特定的生命周期匾南、易于實現(xiàn)啃匿；缺點是維護引用計數(shù)消耗內(nèi)存、無法解決循環(huán)引用的問題。
  • 標記清除（標記遍歷到的所有節(jié)點，清除沒有被標記過的節(jié)點）可以從圖論來理解嫌吠。對于一個有向圖佃乘，如果從一個節(jié)點出發(fā)進行遍歷，并標記其經(jīng)過的所有節(jié)點，那么在遍歷結束后，沒有被標記的節(jié)點就稱之為不可達節(jié)點，不可達節(jié)點的存在是沒有任何意義的灯帮，所以要對它們進行回收。缺點是每次遍歷全圖是一種巨大的性能浪費逻住，所以在python的垃圾回收視線中钟哥，標記清除算法使用了雙向鏈表，并且只考慮容器類的對象（因為只有容器類對象才有可能產(chǎn)生循環(huán)引用）瞎访。
  • 分代收集算法則是將python中所有對象分為三代腻贰。剛剛創(chuàng)立的對象是第0代，經(jīng)過一次垃圾回收后扒秸，依然存在的對象播演，便會一次從上一代挪到下一代，而每一代啟動自動垃圾回收的閾值是可以單獨制定的伴奥，當垃圾回收中新增對象減去刪除對象達到相應的閾值時写烤，就會對這一代對象啟動垃圾回收。分代收集算法讓新生的對象更有可能被回收拾徙，而存活更久的對象也有更高的概率繼續(xù)存活洲炊，因此，通過這種做法，可以節(jié)約不少計算量暂衡，從而提高python的性能询微。
    參考：
    [1] "神秘"的內(nèi)存泄漏
    [2] Python垃圾回收機制詳解
    [3] 深度解析Python垃圾回收機制（超級詳細）
    [4] Python深入06 Python的內(nèi)存管理

Q：Django的請求響應流程

A：一個http請求首先被轉為一個HttpRequest對象，然后該對象被傳遞給request中間件處理狂巢，如果該中間件返回了response撑毛，則直接傳遞給respoonse中間件處理，否則request中間件將訪問url配置唧领，確定請求該由哪個view來處理藻雌，在執(zhí)行view函數(shù)之前系統(tǒng)會把request傳遞給view中間件處理，如果中間件返回了response疹吃，則交給response中間件處理蹦疑，否則將執(zhí)行view函數(shù)并返回response西雀，如果在這個過程中引發(fā)了異常萨驶，將由Exception中間件進行處理。

image.png

Q：mysql存儲引擎

A：不同的存儲引擎會用不同的方式來存儲數(shù)據(jù)，最常用的是InnoDB和MyISAM冲九。
InnoDB：支持事務處理谤草，支持外鍵，支持崩潰修復能力和并發(fā)控制莺奸。如果需要對事務的完整性要求比較高（比如銀行）丑孩，要求實現(xiàn)并發(fā)控制（比如售票），那選擇InnoDB有很大的優(yōu)勢灭贷。如果需要頻繁的更新温学、刪除操作的數(shù)據(jù)庫，也可以選擇InnoDB甚疟，因為支持事務的提交（commit）和回滾（rollback）仗岖。

MyISAM：插入數(shù)據(jù)快，空間和內(nèi)存使用比較低览妖。如果表主要是用于插入新記錄和讀出記錄轧拄，那么選擇MyISAM能實現(xiàn)處理高效率。如果應用的完整性讽膏、并發(fā)性要求比 較低檩电，也可以使用。

MEMORY：所有的數(shù)據(jù)都在內(nèi)存中，數(shù)據(jù)的處理速度快是嗜，但是安全性不高愈案。如果需要很快的讀寫速度，對數(shù)據(jù)的安全性要求較低鹅搪，可以選擇MEMOEY站绪。它對表的大小有要求，不能建立太大的表丽柿。所以恢准，這類數(shù)據(jù)庫只使用在相對較小的數(shù)據(jù)庫表。

注意甫题，同一個數(shù)據(jù)庫也可以使用多種存儲引擎的表馁筐。如果一個表要求比較高的事務處理，可以選擇InnoDB坠非。這個數(shù)據(jù)庫中可以將查詢要求比較高的表選擇MyISAM存儲敏沉。如果該數(shù)據(jù)庫需要一個用于查詢的臨時表，可以選擇MEMORY存儲引擎炎码。

image.png

image.png

Q：mysql中如何實現(xiàn)ACID

A：

• 如何實現(xiàn)一致性盟迟？
  要分兩個層面，首先是數(shù)據(jù)庫層面潦闲，必須實現(xiàn)了原子性攒菠、隔離性和持久性，才有可能實現(xiàn)一致性歉闰；其次是應用層面辖众，需要用代碼判斷數(shù)據(jù)是否合法，然后來決定該回滾還是提交數(shù)據(jù)和敬。
• 如何實現(xiàn)原子性凹炸？
  利用undo log可以實現(xiàn)事務回滾，事務回滾可以撤銷所有已經(jīng)成功執(zhí)行的操作概龄，使數(shù)據(jù)復原到修改之前的樣子（undo log中記錄了要回滾的日志信息还惠，當事務執(zhí)行失敗或者調用rollback時，可以利用undo log進行回滾操作）私杜。
• 如何實現(xiàn)持久性蚕键？
  利用redo log。
  可能存在的問題：數(shù)據(jù)庫讀寫數(shù)據(jù)的時候都是對內(nèi)存中的數(shù)據(jù)進行讀寫衰粹，然后再存入到磁盤中锣光，如果在數(shù)據(jù)存入磁盤之前，mysql宕機了铝耻，就會導致數(shù)據(jù)的丟失誊爹。而redo log可以解決這個問題：當數(shù)據(jù)被修改時蹬刷，除了在內(nèi)存中修改數(shù)據(jù)，還要在redo log中記錄這次修改操作频丘，在事務提交時办成，會對redo log進行刷盤，即使mysql宕機搂漠，也可以在重啟后讀取redo log中的數(shù)據(jù)對數(shù)據(jù)庫進行恢復迂卢。
  采用redo log的好處？ 其實好處就是將redo log進行刷盤比對數(shù)據(jù)頁刷盤效率高桐汤，具體表現(xiàn)如下
  1）redo log體積小而克，畢竟只記錄了哪一頁修改了啥，因此體積小怔毛，刷盤快员萍。
  2）redo log是一直往末尾進行追加，屬于順序IO拣度。效率顯然比隨機IO來的快碎绎。
• 如何實現(xiàn)隔離性？
  利用鎖與MVCC（多版本并發(fā)控制）機制蜡娶。
  鎖機制的基本原理可以概括為：事務在修改數(shù)據(jù)之前混卵，需要獲得相應的鎖；獲得鎖之后窖张，事務可以修改數(shù)據(jù)；在事務操作數(shù)據(jù)期間蚁滋，數(shù)據(jù)是鎖定的宿接，其它事務如果想操作數(shù)據(jù)，需等待當前事務提交或回滾后釋放鎖辕录。鎖分為行鎖睦霎、表鎖以及位于二者之間的鎖，行鎖只鎖定需要操作的數(shù)據(jù)走诞，并發(fā)性能好副女，表鎖則會鎖定整張表，并發(fā)性能較差蚣旱。
  參考
  [1] 一文解析：MySQL事務ACID原理讓你面試不再害怕
  [2] 一文說盡MySQL事務及ACID特性的實現(xiàn)原理
  [3] [轉載]數(shù)據(jù)庫MVCC 隔離級別

Q：數(shù)據(jù)庫完整性約束

A：完整性約束包括實體（行）完整性約束碑幅、域（列）完整性約束、參照完整性約束塞绿。
實體完整性約束是對主鍵的約束沟涨，主鍵能唯一標識表中的每一條記錄，不能為空也不能有重復值异吻；
域完整性是對表中字段屬性的約束裹赴，通常是指數(shù)據(jù)的有效性，包括數(shù)據(jù)的值域、字段的類型等各種規(guī)則棋返；
參照完整性是對外鍵的約束延都，約束外鍵必須為另一張表的主鍵。
參考：
[1] 詳解MySQL:數(shù)據(jù)完整性
[2] 數(shù)據(jù)庫完整性

Q：mysql基本概念

每行稱為記錄睛竣；
每一列為記錄名稱所對應的數(shù)據(jù)域（Field）窄潭，也稱為字段；
主鍵：又稱主碼酵颁，用于唯一地標識表中的每一條記錄嫉你。可以定義表中的一列或多列為主鍵躏惋，主鍵列上不能有相同的值幽污，也不能為空值；
外鍵：是另一表的主鍵, 外鍵可以有重復的, 可以是空值簿姨，用來和其他表建立聯(lián)系用的距误。所以如果談到了外鍵，一定是至少涉及到兩張表扁位。
參考：【數(shù)據(jù)庫】MySQL進階一准潭、主外鍵講解

Q：django和其它web框架的區(qū)別

A：現(xiàn)在常用的框架主要有django、pyramid和flask域仇，前兩個常用于商業(yè)級web服務刑然，flask則是微框架的典范。flask是面向需求簡單的小應用暇务，而django和pyramid都是面向大應用泼掠，但是pyramid比django更靈活，開發(fā)者可以自由選擇數(shù)據(jù)庫垦细、url結構等择镇，而django則是提供一站式解決方案，所以自帶的模塊就比較多（和其它框架最顯著的區(qū)別就是就是內(nèi)建ORM模塊括改，省去了開發(fā)者很多麻煩腻豌，括號里的話可以不說）。
參考：Flask嘱能、Django吝梅、Pyramid 三個框架的對比

Q：同一進程下的線程共享什么？

A：線程共享進程代碼段焰檩、進程的公有數(shù)據(jù)(利用這些共享的數(shù)據(jù)憔涉，線程很容易的實現(xiàn)相互之間的通訊)、進程打開的文件描述符析苫、信號的處理器兜叨、進程的當前目錄和進程用戶ID與進程組ID穿扳。
參考：同一進程中的線程究竟共享哪些資源

Q：什么是僵尸進程，如何產(chǎn)生的国旷？

A：理論上矛物，進程停止后就會從進程表中移除，但是有時候進程停止了也不會從進程表中移除跪但，那些完成了生命周期但依然在進程表中的進程就被稱為“僵尸進程”履羞。
當運行一個程序時，它會產(chǎn)生一個父進程以及很多子進程屡久，這些子進程執(zhí)行完畢后會發(fā)送一個 Exit 信號然后死掉忆首，這個 Exit 信號需要被父進程所讀取，父進程隨后調用 wait 命令來讀取子進程的退出狀態(tài)被环，并將子進程從進程表中移除糙及。但若父進程未能讀取到子進程的 Exit 信號，則這個子進程雖然完成執(zhí)行處于死亡的狀態(tài)筛欢，但也不會從進程表中刪掉浸锨。
參考：什么是僵尸進程，如何找到并殺掉僵尸進程版姑？

Q：裝飾器

A：裝飾器本質上是個函數(shù)柱搜，它可以讓其它函數(shù)在不經(jīng)過修改的情況下增加一些功能。
參考：一文讀懂Python裝飾器剥险，這是一個會打扮的裝飾器

Q：線程的執(zhí)行（切換上下文聪蘸、時間片）

Q：并行和并發(fā)

A：并行是程序的執(zhí)行狀態(tài)，是指同時運行很多任務炒嘲，而并發(fā)是程序的組織結構宇姚，是一種設計，是指不同的程序可以在重疊的時間段內(nèi)啟動夫凸、運行、完成阱持。并行一定需要多核來實現(xiàn)夭拌，而并發(fā)和處理器無關，單線程也可以實現(xiàn)并發(fā)衷咽。
參考：
[1] 如何給女朋友解釋并發(fā)與并行的區(qū)別鸽扁？
[2] 并發(fā)與并行的區(qū)別
[3] 理解并行與并發(fā)

Q：什么是協(xié)程

A：首先得知道什么是例程，例程就是定義的函數(shù)镶骗，而協(xié)程則是多任務子例程的概括桶现，可以允許有多個入口點在例程中確定的位置來控制程序的暫停、恢復等操作鼎姊。
因為函數(shù)（例程）在線程中執(zhí)行骡和，所以協(xié)程也是在線程中執(zhí)行的相赁，多個協(xié)程共享線程內(nèi)的資源，在線程初始化時慰于，協(xié)程的數(shù)據(jù)結構存放在線程的棧內(nèi)存中钮科。
協(xié)程的切換，實際上是函數(shù)的調用婆赠，是由用戶操作在棧內(nèi)存中完成的绵脯；而進程和線程的切換，要保存的狀態(tài)復雜很多休里、內(nèi)存占用量很大蛆挫，而且是由操作系統(tǒng)來調度的，所以協(xié)程的切換比進程和線程切換所消耗的資源小很多妙黍。
參考：說清道明：協(xié)程是什么

Q：python中的并發(fā)場景以及解決方案

A：由于全局解釋器鎖（GIL）的存在悴侵，一個進程在同一時間內(nèi)只能執(zhí)行一個線程，而不能并行執(zhí)行多個線程废境，所以python多線程執(zhí)行效率并不高畜挨，在CPU密集型的任務上，多進程效率更高噩凹。在處理I/O密集型的任務上巴元，python引入了DMA（直接內(nèi)存訪問），它可以協(xié)調完成內(nèi)存到設備間的數(shù)據(jù)傳輸驮宴，中間過程不需要CPU介入逮刨。與進程的執(zhí)行模式相似，彌補了GIL帶來的不足堵泽，又由于線程的開銷遠遠小于進程的開銷修己，因此，在IO密集型場景中迎罗，多線程的性能更高睬愤。
CPU密集型：多進程
I/O密集型：多線程、協(xié)程
CPU密集型+I/O密集型：多進程+協(xié)程

Q：條件隨機場

A：給定隨機變量組X纹安，若隨機變量組Y符合馬爾可夫隨機場尤辱，則稱條件概率分布P(Y|X)為條件隨機場。馬爾可夫隨機場則是隨機變量間滿足成對馬爾可夫性厢岂、局部馬爾可夫性和全局馬爾可夫性光督。
參考：清晰易懂的條件隨機場原理總結

Q：哈希表

A：哈希表是根據(jù)鍵直接訪問數(shù)據(jù)的一種數(shù)據(jù)結構，它通過一個函數(shù)將數(shù)據(jù)映射到表中某個位置塔粒，這個函數(shù)叫做散列函數(shù)结借，這種做法加速了查找數(shù)據(jù)。
補充：哈希函數(shù)的選擇策略：

• 直接尋址法：取關鍵字或關鍵字的某個線性函數(shù)值為散列地址卒茬。即H(key)=key或H(key) = a·key + b船老；
• 隨機數(shù)法：選擇一隨機函數(shù)咖熟，取關鍵字的隨機值作為散列地址，即H(key)=random(key)其中random為隨機函數(shù),通常用于關鍵字長度不等的場合努隙；
• 折疊法
• 平方取中法
• 數(shù)字分析法
• 除數(shù)留余法：取關鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址球恤。即 H(key) = key MOD p,p<=m。
  最常用的是除數(shù)留余法

Q：哈希沖突解決方法

• 開放定址法
  • 線性探測法：發(fā)生沖突時荸镊，順序查看表中下一單元咽斧，直到找出一個空單元或者查遍全表才結束铣猩；
  • 再平方探測：發(fā)生沖突時躁垛，在表的左右進行跳躍式探測，探測序列是1的平方蝇更、-1的平方岭洲、2的平方宛逗。。盾剩。
  • 偽隨機探測：發(fā)生沖突時雷激，探測i=(i+p)%m單元，其中p是隨機數(shù)告私，m是表長屎暇。
  • 開放定址法缺點：為減少沖突，開放定址法要求裝載因子要小驻粟，這樣的話在數(shù)據(jù)規(guī)模很大的情況下會浪費較多的空間根悼。
• 拉鏈法：發(fā)生沖突時，用鏈表來存儲沖突的元素蜀撑；
  • 優(yōu)缺點：拉鏈法處理沖突簡單挤巡，且無堆積現(xiàn)象（非同義詞絕不會發(fā)生沖突），因此平均查找長度較短酷麦；拉鏈法中各鏈表上的節(jié)點空間是動態(tài)申請的矿卑，故它更適合于造表前無法確定表長的情況；拉鏈法裝載因子可以大于1沃饶，比較節(jié)省空間粪摘；拉鏈法構造的哈希表刪除操作易于實現(xiàn)；缺點就是由于節(jié)點空間是動態(tài)申請的绍坝，所以當指針占用較大空間時，會造成空間浪費苔悦。
• 再散列法：構造多個不同的哈希函數(shù)轩褐，假如哈希函數(shù)1生成的值發(fā)生沖突，那就換哈希函數(shù)2玖详，直到不沖突為止把介；
• 公共溢出區(qū)

Q：客戶端和服務器端通信過程

A：客戶端與服務器之間是通過socket通信的勤讽，socket工作于傳輸層和應用層之間。首先三次握手拗踢，建立連接脚牍，然后就是正常地收發(fā)數(shù)據(jù)，最后四次揮手斷開連接巢墅。
參考：Socket通信原理簡介

Q：常見的響應碼及其含義

A：

• 成功2xx 成功處理了請求的狀態(tài)碼诸狭。例如200，代表服務器已成功處理請求并提供了請求的網(wǎng)頁君纫；204驯遇，代表服務器成功處理了請求，但沒有返回任何內(nèi)容蓄髓。
• 重定向3xx 表示每次請求中使用重定向不要超過5次叉庐。例如301，表示請求的網(wǎng)頁已永久移動到新位置会喝；302陡叠，表示請求的網(wǎng)頁臨時移動到新位置；304肢执，表示如果網(wǎng)頁自請求者上次請求后沒有更新枉阵，則用304代碼告訴搜索引擎機器人，可節(jié)約帶寬和開銷蔚万。
• 客戶端錯誤4xx 代表請求可能出錯妨礙了服務器的處理岭妖。例如400，表示服務器不理解請求的語法反璃；403昵慌，表示服務器拒絕請求；404淮蜈，代表服務器找不到請求的網(wǎng)頁（服務器上不存在的網(wǎng)頁經(jīng)常會返回此代碼）斋攀；410，表示請求的資源永久刪除后梧田，服務器返回此響應（與404代碼相似）淳蔼。
• 服務器錯誤5xx 表示服務器在處理請求時內(nèi)部發(fā)生錯誤，可能是服務器本身的錯誤而非請求出錯裁眯；500代表服務器遇到錯誤鹉梨，無法完成請求；503穿稳，服務器目前無法使用（由于超載或停機維護）存皂，通常只是暫時狀態(tài)。
  參考：HTTP狀態(tài)碼知多少

Q：子網(wǎng)掩碼

A：可以根據(jù)每個子網(wǎng)的最大主機數(shù)求出子網(wǎng)掩碼，也可以根據(jù)題目中給的IP地址/數(shù)字求出子網(wǎng)掩碼
參考：根據(jù)子網(wǎng)掩碼計算最大主機數(shù)

Q：頁面調度

參考：頁面置換算法及例題

Q：深度優(yōu)先搜索和廣度優(yōu)先搜索

Q：python內(nèi)置類型各種操作的時間復雜度

A：發(fā)現(xiàn)集合有很多很實用的操作旦袋，比如有a骤菠、b兩個集合，看是否互為子集a.issubset(b)疤孕；找不同的元素a.difference(b)商乎；找交集a.intersection(b)；找并集a.union(b)等等祭阀，本來在列表中需要遍歷的操作鹉戚，放在集合中一個函數(shù)就解決了，而且內(nèi)置的函數(shù)實現(xiàn)的過程應該比自己寫的函數(shù)實現(xiàn)的更優(yōu)雅柬讨。以后碰到列表問題崩瓤，想想可否換成集合，并用內(nèi)置函數(shù)操作踩官。
參考：python內(nèi)置函數(shù)時間復雜度

Q：應用層協(xié)議有哪些却桶，傳輸層協(xié)議有哪些

A：

應用層協(xié)議

• HTTP：超文本傳輸協(xié)議，用于實現(xiàn)WWW服務
• FTP：文件傳輸協(xié)議蔗牡，用于實現(xiàn)交互式文件傳輸功能
• SNMP：簡單網(wǎng)絡管理協(xié)議颖系，用于管理與監(jiān)視網(wǎng)絡設備
• SMTP：用于實現(xiàn)電子郵箱傳送功能
• DNS：用于實現(xiàn)網(wǎng)絡設備名字到IP地址映射的網(wǎng)絡服務
• Telnet：遠程登錄協(xié)議，用于實現(xiàn)遠程登錄功能

傳輸層協(xié)議

• TCP：傳輸控制協(xié)議
• UDP：用戶數(shù)據(jù)報協(xié)議

網(wǎng)絡層協(xié)議

• IP：網(wǎng)絡協(xié)議
• ICMP：互聯(lián)網(wǎng)控制報文協(xié)議
• IGMP：互聯(lián)網(wǎng)組織管理協(xié)議
• ARP：地址解析協(xié)議
  參考：https://blog.csdn.net/hsd2012/article/details/51023539

Q：python中new和init的區(qū)別

A：init是初始化函數(shù)辩越，在對象創(chuàng)建完成后對其進行初始化嘁扼，而new則是創(chuàng)建并返回一個對象，當返回對象時黔攒，會自動調用init進行初始化趁啸。new是靜態(tài)方法，init是實例方法督惰。

Q：物理內(nèi)存和虛擬內(nèi)存（待看）

參考：虛擬內(nèi)存與物理內(nèi)存的聯(lián)系與區(qū)別

Q：淺拷貝與深拷貝不傅，你來設計deepcopy會如何實現(xiàn)？

A：淺拷貝只復制對象的引用赏胚，新舊引用還是指向同一塊內(nèi)存访娶，所以改變內(nèi)存中的值，二者都會改變觉阅；而深拷貝則是新建了一個有相同值的對象崖疤，兩個對象不共享內(nèi)存，修改任一對象不影響其它對象典勇。
deepcopy：對于不可變數(shù)據(jù)類型（整型劫哼、字符串、元組）直接賦值割笙；對于可變數(shù)據(jù)類型（列表沦偎、字典、集合）用遞歸來實現(xiàn)
參考：淺拷貝與深拷貝的實現(xiàn)方式、區(qū)別豪嚎；deepcopy如果你來設計，如何實現(xiàn)

Q：編碼和解碼

A：編碼是把unicode轉為字節(jié)流谈火，通過encode方法侈询，解碼是把字節(jié)流轉為指定編碼，通過decode方法
參考：python中的編碼與解碼

Q：推導式和生成式區(qū)別

A：推導式會將數(shù)據(jù)一次性加載到內(nèi)存中（平常見到的[ele for ele in nums]之類的都是推導式）糯耍，而生成式則是將數(shù)據(jù)一個個地加載到內(nèi)存中扔字，在處理大量數(shù)據(jù)時很有用。推導式有兩種方式温技，一是把推導式的[]改成()革为，二是用yield函數(shù)，使用yield的函數(shù)的生成器有保存狀態(tài)的特性舵鳞，即“在調用生成器運行的過程中震檩，每次遇到 yield 時函數(shù)會暫停并保存當前所有的運行信息，返回 yield 的值, 并在下一次執(zhí)行 next() 方法時從當前位置繼續(xù)運行”

def fibonacci(num):
    a,b,counter = 0,1,0
    while True:
        if (counter > num):
            return
        yield a
        print('這是第{}次'.format(counter))
        a,b = b, a+b
        counter += 1
f = fibonacci(10)

print(f)
print(next(f))
'''
<generator object fibonacci at 0x1076e7830>
0
'''

繼續(xù)執(zhí)行next函數(shù)

print(next(f))
'''
這是第0次
1
'''

補充：迭代器
迭代器的創(chuàng)建通過iter函數(shù)蜓堕，遍歷通過next函數(shù)抛虏，或者普通的for循環(huán)，其實生成器也可以理解為迭代器套才，因為它返回的是迭代器對象迂猴。
Python3 迭代器與生成器
參考：
列表推導式與生成器的區(qū)別
python中生成器與列表推導式的說明差異
列表推導式三種模式和生成器

Q：python創(chuàng)建單例模式的幾種方式

A：單例模式是指一個類只有一個實例（無論這個類被調用多少次，它也只有一個實例）背伴。

• 使用模塊沸毁。新建A文件，在文件A下新建B類傻寂，并實例化B類息尺，B的實例化對象為b，然后使用from A import b來使用B類崎逃。（原理：python的模塊就是天然的單例模式,因為模塊在第一次導入的時候,會生成.pyc文件,當?shù)诙螌氲臅r候,就會直接加載.pyc文件,而不是再次執(zhí)行模塊代碼.如果我們把相關的函數(shù)和數(shù)據(jù)定義在一個模塊中,就可以獲得一個單例對象了）
• 使用裝飾器掷倔。

def My_decorate(f):
    _dict = {}

    def fn(*args, **kwargs):
        if f not in _dict:
            _dict[f] = f(*args, **kwargs)
            print('decorate called')
        return _dict[f]

    return fn


@My_decorate
def fx():
    print('fx called')


fx()

# 輸出值
# fx called
# decorate called

• 使用類。
• 使用new个绍。

class Singleton(object):
    _instance = None
    def __new__(cls, *args, **kwargs):
        if cls._instance is None:
            cls._instance = object.__new__(cls, *args, **kwargs)

        return cls._instance

s1 = Singleton()
s2 = Singleton()
print(s1)
print(s2) 
# 輸出
<__main__.Singleton object at 0x7fdef58b1190>
<__main__.Singleton object at 0x7fdef58b1190>

Q：使用裝飾器構建的單例和使用其它方法構建的單例在后續(xù)使用中有什么不同嗎

A：使用裝飾器單例的屬性不會被覆蓋勒葱，因為裝飾器返回的是之前生成的對象，而用new構建的單例巴柿，會調用init方法初始化實例的屬性凛虽。

Q：socket短連接、長連接是什么意思

A：
短連接：連接->傳輸數(shù)據(jù)->關閉連接
短連接就是建立連接后广恢，只傳輸一次數(shù)據(jù)就斷開連接凯旋，http服務就是短連接的，因為web的訪問量很大，如果對服務器端對每個客戶端都保持長連接的話會消耗大量的資源至非。
長連接：連接->傳輸數(shù)據(jù)->保持連接->傳輸數(shù)據(jù)->....->關閉連接
長連接建立連接后不管是否使用都保持連接钠署，適用于操作頻繁，點對點的通信荒椭，而且連接數(shù)不能太多的情況（不然一直保持連接會消耗大量資源）谐鼎。比如數(shù)據(jù)庫的連接，因為如果數(shù)據(jù)庫用短連接通信會造成socket錯誤（不知道為什么）趣惠，而且頻繁的socket連接創(chuàng)建會對資源造成浪費狸棍。

image.png

Q：TIME_WAIT過多是因為什么？

TIME_WAIT是主動關閉連接的一方所保持的狀態(tài)味悄，一般主動關閉連接的一方是server端草戈，所以當存在多個高并發(fā)短連接時，會導致存在大量的TIME_WAIT（時長為2個max segment lifetime）侍瑟。（短連接表示“業(yè)務處理+傳輸數(shù)據(jù)的時間 遠遠小于 TIMEWAIT超時的時間”的連接唐片，那為什么是高并發(fā)短連接呢，我自己的理解是短連接消耗的資源少丢习，所以有高并發(fā)的可能牵触，而長連接本來就用于連接數(shù)不太多的操作頻繁的點對點通信，所以不太可能出現(xiàn)高并發(fā)情況）咐低。
補充：TIME_WAIT存在的原因：
（1）維持連接的狀態(tài)：當出現(xiàn)第四次揮手時ACK丟失揽思，而服務器端重新發(fā)送FIN的情況，因為有TIME_WAIT的存在见擦，連接狀態(tài)得以保持钉汗，客戶端可以正常地應答服務器端；
（2）允許老的重復分節(jié)在網(wǎng)絡中消逝：TCP分節(jié)可能由于路由器異常而“迷途”鲤屡，在迷途期間损痰，TCP發(fā)送端可能因確認超時而重發(fā)這個分節(jié)，迷途的分節(jié)在路由器修復后也會被送到最終目的地酒来，這個原來的迷途分節(jié)就稱為lost duplicate卢未。
在關閉一個TCP連接后，馬上又重新建立起一個相同的IP地址和端口之間的TCP連接堰汉，后一個連接被稱為前一個連接的化身（incarnation)辽社，那么有可能出現(xiàn)這種情況，前一個連接的迷途重復分組在前一個連接終止后出現(xiàn)翘鸭，從而被誤解成從屬于新的化身滴铅。
為了避免這個情況，TCP不允許處于TIME_WAIT狀態(tài)的連接啟動一個新的化身就乓，因為TIME_WAIT狀態(tài)持續(xù)2MSL汉匙，就可以保證當成功建立一個TCP連接的時候拱烁，來自連接先前化身的重復分組已經(jīng)在網(wǎng)絡中消逝。
參考：
[1] 解決TIME_WAIT過多造成的問題
[2] TIME_WAIT是什么噩翠？

Q：一次完整的http請求過程

A：域名解析 --> 發(fā)起TCP三次握手 --> 建立連接后瀏覽器發(fā)起http請求 --> 服務器響應請求戏自，瀏覽器獲得html代碼 --> 瀏覽器解析html代碼，請求其中的資源 --> 瀏覽器將頁面渲染后呈現(xiàn)給用戶
參考：一次完整的HTTP請求過程

Q：select和epoll你了解么绎秒，區(qū)別在哪

A：完全不了解浦妄，都沒聽說過，看了答案之后也不知道這是什么東西见芹。
參考：select、poll蠢涝、epoll之間的區(qū)別(搜狗面試)

Q：五種I/O模型

A：

• 阻塞I/O模型
• 非阻塞I/O模型
• 復用I/O模型
• 信號驅動I/O模型
• 異步I/O模型
  參考：
  [1] I/O多路復用技術（multiplexing）是什么玄呛？
  [2] IO 多路復用是什么意思？

Q：python中可變類型和不可變類型

A：在python中變量存儲的實際上是值的地址和二，可以用id函數(shù)看到
不可變數(shù)據(jù)類型（整型徘铝，字符串，元組）惯吕，不允許變量的值發(fā)生變化惕它，如果改變了變量的值，相當于新建一個對象废登，變量存儲的地址也隨之改變淹魄，而具有相同值的不同變量，無論有多少個堡距，這些變量中存儲的都是同一個地址甲锡。
可變數(shù)據(jù)類型（列表，字典羽戒，集合）缤沦，允許變量的值發(fā)生變化，如果改變了變量的值易稠，變量存儲的地址不會發(fā)生變化缸废。具有相同值的不同變量，它們存儲的地址也不同驶社，即這些值雖然相同企量，但是在內(nèi)存中有自己的地址。
參考：Python 可變類型和不可變類型衬吆，以及其引用

Q：什么是RESTful

A：過于復雜梁钾，應該用不到。簡單來說逊抡，REST是表述性狀態(tài)轉移姆泻，是一組架構約束條件和原則零酪，如果有架構符合REST約束，則稱它是RESTful架構拇勃。
參考：RESTful 架構詳解

Q：什么是orm

A：orm就是在關系型數(shù)據(jù)庫和對象之間建立映射四苇，這樣在操作數(shù)據(jù)庫的時候就不需要寫SQL語句了，而是像操作對象一樣操作數(shù)據(jù)庫方咆。
參考：什么是ORM?為啥要是用ORM月腋？

Q：面向過程和面向對象的區(qū)別

A：面向過程是按步驟來劃分問題，而面向對象則是按功能劃分問題瓣赂。
面向過程的優(yōu)點是符合人類思維榆骚，編寫起來比較簡單，缺點是面向過程編寫的代碼往往只適用于一個功能煌集，如果要實現(xiàn)其它功能妓肢，即使功能差異很小，也要重寫代碼苫纤，所以可復用性較低碉钠，維護較困難。
面向對象的優(yōu)點是可復用性高卷拘，可維護性好喊废，缺點是編寫起來比較不符合人類思維。
面向過程的語言有C栗弟；
面向對象的語言有C++污筷，java，python等
參考：
[1] 面向對象與面向過程的本質的區(qū)別
[2] 淺談編程語言中的面向過程和面向對象

Q：什么是類横腿，什么是對象

A：類是具有相同屬性和功能的對象的集合（抽象概念）颓屑，而對象是類的實例化（真實存在）。屬性表示對象有什么耿焊，功能表示對象能干什么揪惦。
參考：java中什么是類？什么是對象罗侯？
補充：python的各種方法聲明

class Person():
    # 對象方法
    def eat(self,food):
        print('人吃'+food)
    def study(self,type):
        print('學習'+type)
    # 類方法
    @classmethod
    def destroy(cls):
        # temp=cls()
        # cls.func1()
        # print('temp',temp)
        # print('cls',cls)
        print('人類破壞環(huán)境')
    # @classmethod
    # def func1(cls):
    #     print('臨時類方法')
    # 靜態(tài)方法
    @staticmethod
    def beat_animal():
        print('人類毆打小動物')
p1=Person()
p1.eat('面條')
p1.study('python')
p1.destroy()
p1.beat_animal()

Q：單鏈表逆置

class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


def reverse(node):
    # s = str(node.data)
    p = node
    cur = node.next
    p.next = None
    while cur:
        tmp = cur.next
        cur.next = p
        p = cur
        cur = tmp
    return p


node1 = node(1)
node2 = node(2)
node3 = node(3)
node4 = node(4)
node5 = node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node0=node1
s = str(node0.data)
while node0.next:
    s += str(node0.next.data)
    node0 = node0.next
print(s)
node = reverse(node1)
s = str(node.data)
while node.next:
    s += str(node.next.data)
    node = node.next
print(s)

Q：裝飾器函數(shù)執(zhí)行順序

A：重點是裝飾器函數(shù)在被裝飾函數(shù)定義好后立即執(zhí)行

廣度優(yōu)先搜索（沒找到用遞歸實現(xiàn)的方法）

用隊列實現(xiàn)

from collections import deque
class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
def bfs(node):
    # 用隊列實現(xiàn)bfs
    stack=[]
    queue=deque()
    if not node:
        return
    queue.append(node)
    while queue:
        node=queue.popleft()
        stack.append(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return stack
for i in range(1,8):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
stk=bfs(node1)
for ele in stk:
    print(ele.data,end=' ')

用棧實現(xiàn)（感覺比用隊列實現(xiàn)更簡單）

class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
stack=[]
queue=deque()
def bfs(node):
    # 用棧實現(xiàn)bfs
    if not node:
        return
    stack.append(node)
    for ele in stack:
        if ele.left:
            stack.append(ele.left)
        if ele.right:
            stack.append(ele.right)
    return stack
for i in range(1,10):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
node5.left=node8
node5.right=node9
stk=bfs(node1)
for ele in stk:
    print(ele.data,end=' ')

深度優(yōu)先搜索

用遞歸實現(xiàn)

from collections import deque
class node:
    def __init__(self,data=None):
        self.data=data
        self.left=None
        self.right=None
stack=[]
queue=deque()
def dfs(node):
    # 用遞歸實現(xiàn)dfs


    if not node:
        return
    # queue.append(node)
    # node=queue.popleft()
    stack.append(node)
    bfs(node.left)
    bfs(node.right)
    return stack
for i in range(1,10):
    string='node{}=node({})'.format(i,i)
    exec(string)
node1.left=node2
node1.right=node3
node2.left=node4
node2.right=node5
node3.left=node6
node3.right=node7
node5.left=node8
node5.right=node9
stk=dfs(node1)
for ele in stk:
    print(ele.data,end=' ')

用棧實現(xiàn)(關鍵在于先將右節(jié)點壓棧，再壓入左節(jié)點)

class node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None


stack = []
st = []


# queue=deque()
def dfs(node):
    # 用棧實現(xiàn)dfs
    if not node:
        return
    stack.append(node)
    while stack:
        ele = stack.pop()
        st.append(ele)
        if ele.right:
            stack.append(ele.right)
        if ele.left:
            stack.append(ele.left)
    return st


for i in range(1, 10):
    string = 'node{}=node({})'.format(i, i)
    exec(string)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7
node5.left = node8
node5.right = node9
stk = dfs(node1)
for ele in stk:
    print(ele.data, end=' ')

Q：給定一個鏈表纫塌，刪除鏈表的倒數(shù)第n個節(jié)點讲弄，并且返回鏈表的頭節(jié)點【leetcode 19】

class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


def delnode(head, n):
    fast = head
    slow = head
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head
def printnode(head):
    while head:
        print(str(head.data),end=' ')
        head=head.next
for i in range(1,6):
    string="node{}=node({})".format(i,i)
    exec(string)
node1.next=node2
node2.next=node3
node3.next=node4
node4.next=node5
p=delnode(node1,2)
printnode(p)

Q：已知先序和中序數(shù)組措左，求后序數(shù)組（難點在于返回列表后，如何防止出現(xiàn)列表中嵌套列表的情況避除，其實就是一個列表相加的操作）

class node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None
# li=[]
def postOrder(pre,tin):
    if len(pre)<=1:
        return pre
    root=pre[0]
    pos=tin.index(root)
    left=postOrder(pre[1:pos+1],tin[0:pos])
    right=postOrder(pre[pos+1:],tin[pos+1:])
    return left+right+[root]
pre=[1,2,4,5,3,6,7]
tin=[4,2,5,1,6,3,7]
print(postOrder(pre,tin))

Q：二分查找代碼

def binarySearch(li, n):
    l = 0
    r = len(li) - 1
    # 邊界條件需要注意
    while l <= r:
        mid = (l + r) // 2
        if li[mid] > n:
            r = mid - 1
        elif li[mid] < n:
            l = mid + 1
        else:
            return 'index是%d' % mid
    return '元素不在列表中'

Q：零錢兌換1（給定金額怎披，求組成金額所用的最少硬幣）????

內(nèi)循環(huán)和外循環(huán)交換位置是否有影響

# 給定金額amount和各種硬幣面值組成的列表items胸嘁，求組成金額的最少硬幣數(shù)
def ways(items, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for item in items:
        for x in range(item, amount + 1):
                dp[x] = min(dp[x],dp[x - item]+1)
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：零錢兌換2（給定金額，求組成金額的所有方法凉逛，不同順序算一種方法）?????

# 給定金額amount和各種硬幣面值組成的列表items性宏，求組成金額的所有方法，不同順序算一種方法
def ways(items, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for item in items:
        for x in range(item, amount + 1):
            dp[x] += dp[x - item]
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：零錢兌換3（給定金額状飞，求組成金額的所有方法毫胜，不同順序算不同的方法）

# 給定金額amount和各種硬幣面值組成的列表items，求組成金額的所有方法诬辈，不同順序算不同的方法
def ways(items, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for x in range(1, amount + 1):
        for item in items:
            if x >= item:
                dp[x] += dp[x - item]
    return dp[-1]


items = list(map(int, input().strip().split()))
amount = int(input())
print(ways(items, amount))

Q：python中字典和列表的底層實現(xiàn)

A：列表是由分離式的順序表實現(xiàn)酵使，它包括兩個部分，一個是信息區(qū)焙糟，一個是存儲區(qū)凝化，信息區(qū)中包括了列表的最大容量，已經(jīng)存儲的元素和存儲區(qū)的地址酬荞，而存儲區(qū)則是一塊連續(xù)的區(qū)域混巧，用于存放列表中的元素。（為什么用分離式傍衡，不用一體式？因為一體式不便于修改列表元素绣的，當修改列表元素時，必須將信息區(qū)和存儲區(qū)整體修改惩嘉，重新向內(nèi)存申請新的空間廷痘，而分離式只需要修改存儲區(qū)的地址即可鸽粉。）
字典是由哈希表實現(xiàn)的触机，字典也被稱為哈希數(shù)組偏友，數(shù)組的索引是字典的鍵經(jīng)過哈希函數(shù)處理后得到的值氛濒。
數(shù)據(jù)添加過程：將key通過哈希函數(shù)映射后得到的值對表長進行取余舞竿，取余得到的值作為數(shù)組的下標，將value存放在下標對應的空間里。
數(shù)據(jù)查詢過程：將key轉換為數(shù)組下標仰挣，取出下標對應的數(shù)組空間中的value。
參考：
[1] python基礎--數(shù)據(jù)結構
[2] python中列表與字典的底層實現(xiàn)

Q：鏈表和數(shù)組的區(qū)別

Q：哈希表的查找時間復雜度為什么是O(1)

Q：如何終止僵尸進程

A：子進程終止香椎，父進程尚未回收，子進程殘留資源存放于內(nèi)核中玛界，變成僵尸進程良狈。可以通過殺死父進程來使僵尸進程變成孤兒進程，隨后孤兒進程會被init進程回收漫玄。
參考：如何殺死僵尸進程？

Q：如何終止進程

A：有kill pid和kill -9 pid兩種刨秆，區(qū)別在于
1家凯、kill -9 id：一般不加參數(shù)kill是使用15來殺绊诲，這相當于正常停止進程脆丁，停止進程的時候會釋放進程所占用的資源槽卫；他們的區(qū)別就好比電腦關機中的軟關機（通過“開始”菜單選擇“關機”）與硬關機（直接切斷電源）震蒋，雖然都能關機，但是程序所作的處理是不一樣的。

2、kill - 9 表示強制殺死該進程籍嘹；而 kill 則有局限性泪掀，例如后臺進程头岔，守護進程等；

3颂碧、執(zhí)行kill命令，系統(tǒng)會發(fā)送一個SIGTERM信號給對應的程序呼寸。SIGTERM多半是會被阻塞的。kill -9命令瑟捣，系統(tǒng)給對應程序發(fā)送的信號是SIGKILL碱鳞，即exit贵白。exit信號不會被系統(tǒng)阻塞角撞，所以kill -9能順利殺掉進程。

Q：python中is和==的區(qū)別

A：is比較的是兩個對象的地址值是否相同谒所，而==比較的是兩個對象的值是否相同磷蜀。
補充：java中==和equals的區(qū)別：有點類似于python中 is 和 == 的區(qū)別。

Q：什么是WSGI百炬，作用是什么

A：WSGI（Web Server Gateway Interface）是web服務器網(wǎng)關接口，是web server和web app或框架之間的接口標準規(guī)范污它。它的作用是規(guī)范web服務器和web應用之間的交互固惯，在協(xié)議之間進行轉換。

Q：python模塊查找的機制

image.png