Algorithm：算法方向——BAT公司問題面試之計算機基礎(進程與線程的區別)、經典概率問題等集錦

Algorithm：算法方向——BAT公司問題面試之計算機基礎(進程與線程的區別)、經典概率問題等集錦

目錄

計算機基礎問題

1、進程與線程的區別

概率問題

1、貂蟬與西施回頭率比美問題

計算機基礎問題

1、進程與線程的區別

進程：進程（Process）是計算機中的程序關于某數據集合上的一次運行活動，是系統進行資源分配和調度的基本單位，是操作系統結構的基礎。

線程：線程（thread）是操作系統能夠進行運算調度的最小單位。它被包含在進程之中，是進程中的實際運作單位。

一、進程與線程五大區別——進程是線程的boss

1、根本區別—進程管資源、線程管執行：進程是操作系統資源分配的基本單位，而線程是任務調度和執行的基本單位。進程是資源分配最小單位；線程是程序執行的最小單位。

2、內存分配—進程擁有獨立的地址空間——進程是線程的上司，進程擁有獨立辦公室：進程有自己獨立的地址空間，每啟動一個進程，系統都會為其分配地址空間，建立數據表來維護代碼段、堆棧段和數據段；線程沒有獨立的地址空間，它使用相同的地址空間共享數據。

(1)、系統在運行的時候會為每個進程分配不同的內存空間；而對線程而言，除了CPU外，系統不會為線程分配內存（線程所使用的資源來自其所屬進程的資源），線程組之間只能共享資源。

(2)、多進程程序更安全，生命力更強，一個進程死掉不會對另一個進程造成影響（源于有獨立的地址空間）；多線程程序更不易維護，一個線程死掉，整個進程就死掉了（因為共享地址空間）。

3、資源開銷—進程比線程開銷大、線程可頻繁切換——進程能住希爾頓而線程只能住如家：線程花費小、開銷小、效率高，CPU切換一個線程比切換進程花費?。粍摻ㄒ粋€線程比進程開銷小；線程占用的資源要?進程少很多。進程對資源保護要求高，開銷大，效率相對較低，線程資源保護要求不高，但開銷小，效率高，可頻繁切換。

4、內部通信—線程通信更方便、進程間通信需IPC——進程住高樓大廈通信需要電話：線程之間通信更方便，但多線程程序處理好同步與互斥是個難點；同一個進程下，線程共享全局變量，靜態變量等數據，進程之間的通信需要以通信的方式（IPC）進行。

(1)、進程間通信IPC，線程間可以直接讀寫進程數據段（如全局變量）來進行通信——需要進程同步和互斥手段的輔助，以保證數據的一致性。

5、資源開銷—線程可以看做輕量級的進程——進程減肥后就能瘦成線程：每個進程都有獨立的代碼和數據空間（程序上下文），程序之間的切換會有較大的開銷；線程可以看做輕量級的進程，同一類線程共享代碼和數據空間，每個線程都有自己獨立的運行棧和程序計數器（PC），線程之間切換的開銷小。

(1)、沒有線程的進程可以看做是單線程的，如果一個進程內有多個線程，則執行過程不是一條線的，而是多條線（線程）共同完成的；線程是進程的一部分，所以線程也被稱為輕權進程或者輕量級進程。

6、?環境運行—線程是進程的一部分、進程可有多個線程——進程位高權重擁有更多選擇權：一個線程只能屬于一個進程，而一個進程可以有多個線程，但至少有一個線程。在操作系統中能同時運行多個進程（程序）；而在同一個進程（程序）中有多個線程同時執行（通過CPU調度，在每個時間片中只有一個線程執行）。

概率問題

1、貂蟬與西施回頭率比美問題

結論1：貂蟬獲勝的概率是0.5，但并不是指貂蟬、西施獲勝的概率相等，即貂蟬獲勝的概率有可能是90%。

結論2：其實P(C)是接近于0即沒有用處的

結論3：如果有超過50%概率(比如60%)獲勝，那么盡量多進行一場比賽(前邊幾場隨機性比較強，比賽越多，越接近概率60%)

(1)、問題描述以及分析

(2)、代碼模擬驗證(10萬次)實現，得到0.50335

2、從1,2,3,......,98,99,2015這100個數中任意選擇若干個數(可能為0個數)求異或，試求異或的期望值。

解：計算每一位的期望。針對任何一個二進制位：取奇數個1異或后會得到1，取偶數個1異或后會得到0；與取0的個數無關。

? 給定的最大數2015=(11111011111)2，共11位。針對每一位分別計算，考慮第 i 位Xi，假定給定的100個數中第 i 位一共有N個1，M個0，某次采樣取到的1的個數為k。則有

(1)、11位二進制數中，每個位取1的期望都是0.5

(2)、采樣模擬

任務調度

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。