一、插入排序
介紹
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。
演算法適用於少量數據的排序，時間復雜度為O(n^2)。
插入排演算法是穩定的排序方法。
步驟
①從第一個元素開始，該元素可以認為已經被排序
②取出下一個元素，在已經排序的元素序列中從後向前掃描
③如果該元素（已排序）大於新元素，將該元素移到下一位置
④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
⑤將新元素插入到該位置中
⑥重復步驟2
排序演示
演算法實現
二、冒泡排序
介紹
冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
原理
循環遍歷列表，每次循環找出循環最大的元素排在後面；
需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。
步驟
①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
③針對所有的元素重復以上的步驟，除了最後一個。
④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
演算法實現：
三、快速排序
介紹
快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填數 + 分治法。
首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
實現步驟
①從數列中挑出一個元素，稱為 「基準」（pivot）；
②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；
③對所有兩個小數列重復第二步，直至各區間只有一個數。
排序演示
演算法實現
四、希爾排序
介紹
希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；
·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。
基本思想
①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；
②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。
排序演示
演算法實現
五、選擇排序
介紹
選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。
基本思想
選擇排序的基本思想：比較 + 交換。
第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；
第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；
以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。
排序演示
選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。
演算法實現
六、堆排序
介紹
堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。
利用數組的特點快速指定索引的元素。
基本思想
堆分為大根堆和小根堆，是完全二叉樹。
大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。
在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
排序演示
演算法實現
七、歸並排序
介紹
歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
基本思想
歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。
演算法思想
自上而下遞歸法（假如序列共有n個元素）
① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；
② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；
③ 重復步驟②，直到所有元素排序完畢。
自下而上迭代法
① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；
② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；
④ 重復步驟③直到某一指針達到序列尾；
⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。
排序演示
演算法實現
八、基數排序
介紹
基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。
基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。
在某些時候，基數排序法的效率高於其他的穩定性排序法。
基本思想
將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。
基數排序按照優先從高位或低位來排序有兩種實現方案：
MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。
LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。
排序效果
演算法實現
九、總結
各種排序的穩定性、時間復雜度、空間復雜度的總結：
平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；
從時間復雜度來說：
線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；
O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；
線性階O(n)排序：基數排序，此外還有桶、箱排序。
❷ go面試題整理（附帶部分自己的解答）
原文：【 http://alblue.cn/articles/2020/07/04/1593837537036.html 】
如果有解答的不對的，麻煩各位在評論寫出來~
go的調度原理是基於GMP模型，G代表一個goroutine，不限制數量；M=machine，代表一個線程，最大1萬，所有G任務還是在M上圓腔執行；P=processor代表一個處理器，每一個允許的M都會綁定一個G，默認與邏輯CPU數量相等（通過runtime.GOMAXPROCS(runtime.NumCPU())設置）。
go調用過程：
可以能，也可以不能。
因為go存在不能使用==判斷類型：map、slice，如果struct包含這些類型的欄位，則不能比較。
這兩種類型也不能作為map的key。
類似棧操作，後進先出。
因為go的return是一個非原子性操作，比如語句 return i ，實際上分兩步進行，即將i值存入棧中作為返回值，然後執行跳轉，而defer的執行時機正是跳轉前，所以說defer執行時還是有機會操作返回值的。
select的case的表達式必須是一個channel類型，所有case都會被求值，求值順序自上而下，從左至右。如果多個case可以完成，則會隨機執行一個case，如果有default分支，則執行default分支語句。如果連default都沒有，則select語句會一念纖直阻塞，直到至少有一個IO操作可以進行。
break關鍵字可跳出select的執行。
goroutine管理、信息傳遞。context的意思是上下文，在線程、協程中都有這個概念，它指的是程序單元的一個運行狀態、現場、快照，包含。context在多個goroutine中是並發安全的。
應用場景：
例子參考： https://www.jianshu.com/p/6def5063c1eb
waitgroup
channel
len：切片的長度，訪問時間復雜度為O(1)，go的slice底層是對數組的引用。
cap：切片的容量，擴容是以這個值為標准。默認擴容是2倍，當達到1024的長度後，按1.25倍。
擴容：每次擴容slice底層都將先分配新的容量的內存空間，再將老的數組拷貝到新的內存空間，因為這個操作不是並發安全的。所以並發進行append操作，讀到內存中的老數組可能為同一個，最終導致append的數據丟失。
共享：slice的底層是對數組的引用，因此如果兩個切片引用了同一個數組片段，就會形成共享底層數組。當sliec發生內存的重新分配（如擴容）時，會對共享進行隔斷。詳細見下面例子：
make([]Type,len,cap)
map的底層是hash table(hmap類型)，對key值進行了hash，並將結果的低八位用於確定key/value存在於哪個bucket（bmap類型）。再將高八位與bucket的tophash進行依次比較，確定是否存在。出現hash沖撞時，會通過bucket的overflow指向另一個bucket，形成一個單向鏈表。每個bucket存儲8個鍵值對。
如果要實現map的橘高衫順序讀取，需要使用一個slice來存儲map的key並按照順序進行排序。
利用map，如果要求並發安全，就用sync.map
要注意下set中的delete函數需要使用 delete(map) 來實現，但是這個並不會釋放內存，除非value也是一個子map。當進行多次delete後，可以使用make來重建map。
使用sync.Map來管理topic，用channel來做隊列。
參考：
https://studygolang.com/articles/8231
多路歸並法:
<pre class="vditor-reset" placeholder="" contenteditable="true" spellcheck="false"><p data-block="0">(1)假設有K路<a href="https://ke..com/item/%E6%95%B0%E6%8D%AE%E6%B5%81/3002243">數據流</a>，流內部是有序的，且流間同為升序或降序；
</p><p data-block="0">(2)首先讀取每個流的第一個數，如果已經EOF，pass；
</p><p data-block="0">(3)將有效的k(k可能小於K)個數比較，選出最小的那路mink，輸出，讀取mink的下一個；
</p><p data-block="0">(4)直到所有K路都EOF。
</p></pre>
假設文件又1個G，內存只有256M，無法將1個G的文件全部讀到內存進行排序。
第一步：
可以分為10段讀取，每段讀取100M的數據並排序好寫入硬碟。
假設寫入後的文件為A,B，C...10
第二步:
將A，B,C...10的第一個字元拿出來，對這10個字元進行排序，並將結果寫入硬碟，同時記錄被寫入的字元的文件指針P。
第三步：
將剛剛排序好的9個字元再加上從指針P讀取到的P+1位數據進行排序，並寫入硬碟。
重復二、三步驟。
go文件讀寫參考：
https://www.jianshu.com/p/93772ececf65
保證排序前兩個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同的排序叫穩定排序。
快速排序、希爾排序、堆排序、直接選擇排序不是穩定的排序演算法。
基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。
參考：
https://www.jianshu.com/p/abe27f16b7b5
head只請求頁面的首部。多用來判斷網頁是否被修改和超鏈接的有效性。
get請求頁面信息，並返回實例的主體。
參考:
https://blog.csdn.net/ysh1042436059/article/details/80985574
https://www.jianshu.com/p/ef692148a59c
401：未授權的訪問。
403: 拒絕訪問。
普通的http連接是客戶端連接上服務端，然後結束請求後，由客戶端或者服務端進行http連接的關閉。下次再發送請求的時候，客戶端再發起一個連接，傳送數據，關閉連接。這么個流程反復。但是一旦客戶端發送connection:keep-alive頭給服務端，且服務端也接受這個keep-alive的話，兩邊對上暗號，這個連接就可以復用了，一個http處理完之後，另外一個http數據直接從這個連接走了。減少新建和斷開TCP連接的消耗。這個可以在Nginx設置，
這個keepalive_timout時間值意味著：一個http產生的tcp連接在傳送完最後一個響應後，還需要hold住keepalive_timeout秒後，才開始關閉這個連接。
特別注意TCP層的keep alive和http不是一個意思。TCP的是指：tcp連接建立後，如果客戶端很長一段時間不發送消息，當連接很久沒有收到報文，tcp會主動發送一個為空的報文（偵測包）給對方，如果對方收到了並且回復了，證明對方還在。如果對方沒有報文返回，重試多次之後則確認連接丟失，斷開連接。
tcp的keep alive可通過
net.ipv4.tcp_keepalive_intvl = 75 // 當探測沒有確認時，重新發送探測的頻度。預設是75秒。
net.ipv4.tcp_keepalive_probes = 9 //在認定連接失效之前，發送多少個TCP的keepalive探測包。預設值是9。這個值乘以tcp_keepalive_intvl之後決定了，一個連接發送了keepalive之後可以有多少時間沒有回應
net.ipv4.tcp_keepalive_time = 7200 //當keepalive起用的時候，TCP發送keepalive消息的頻度。預設是2小時。一般設置為30分鍾1800
修改：
可以
tcp是面向連接的，upd是無連接狀態的。
udp相比tcp沒有建立連接的過程，所以更快，同時也更安全，不容易被攻擊。upd沒有阻塞控制，因此出現網路阻塞不會使源主機的發送效率降低。upd支持一對多，多對多等，tcp是點對點傳輸。tcp首部開銷20位元組，udp8位元組。
udp使用場景：視頻通話、im聊天等。
time-wait表示客戶端等待服務端返回關閉信息的狀態，closed_wait表示服務端得知客戶端想要關閉連接，進入半關閉狀態並返回一段TCP報文。
time-wait作用：
解決辦法：
close_wait:
被動關閉，通常是由於客戶端忘記關閉tcp連接導致。
https://blog.csdn.net/yucdsn/article/details/81092679
根據業務來啊~
重要指標是cardinality（不重復數量），這個數量/總行數如果過小（趨近於0）代表索引基本沒意義，比如sex性別這種。
另外查詢不要使用select *，根據select的條件+where條件做組合索引，盡量實現覆蓋索引，避免回表。
僵屍進程：
即子進程先於父進程退出後，子進程的PCB需要其父進程釋放，但是父進程並沒有釋放子進程的PCB，這樣的子進程就稱為僵屍進程，僵屍進程實際上是一個已經死掉的進程。
孤兒進程：
一個父進程退出，而它的一個或多個子進程還在運行，那麼那些子進程將成為孤兒進程。孤兒進程將被init進程(進程號為1)所收養，並由init進程對它們完成狀態收集工作。
子進程死亡需要父進程來處理，那麼意味著正常的進程應該是子進程先於父進程死亡。當父進程先於子進程死亡時，子進程死亡時沒父進程處理，這個死亡的子進程就是孤兒進程。
但孤兒進程與僵屍進程不同的是，由於父進程已經死亡，系統會幫助父進程回收處理孤兒進程。所以孤兒進程實際上是不佔用資源的，因為它終究是被系統回收了。不會像僵屍進程那樣佔用ID,損害運行系統。
原文鏈接： https://blog.csdn.net/Eunice_fan1207/article/details/81387417
產生死鎖的四個必要條件：
（1） 互斥條件：一個資源每次只能被一個進程使用。
（2） 請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。
（3） 不剝奪條件：進程已獲得的資源，在末使用完之前，不能強行剝奪。
（4） 循環等待條件：若干進程之間形成一種頭尾相接的循環等待資源關系。
避免方法：
https://blog.csdn.net/IT_10/article/details/97301736
埠佔用：lsof -i:埠號 或者 nestat
cpu、內存佔用：top
發送信號：kill -l 列出所有信號，然後用 kill [信號變化] [進程號]來執行。如kill -9 453。強制殺死453進程
git log:查看提交記錄
git diff ：查看變更記錄
git merge：目標分支改變，而源分支保持原樣。優點：保留提交歷史，保留分支結構。但會有大量的merge記錄
git rebase：將修改拼接到最新，復雜的記錄變得優雅，單個操作變得(revert)很簡單；缺點：
git revert:反做指定版本，會新生成一個版本
git reset:重置到某個版本，中間版本全部丟失
etcd、Consul
https://www.cnblogs.com/xybaby/p/10124083.html
pprof
https://www.cnblogs.com/weiweng/p/12497274.html
http://alblue.cn/articles/2020/07/07/1594131614114.html
節省空間（非葉子節點不存儲數據，相對b tree的優勢），減少I/O次數（節省的空間全部存指針地址，讓樹變的矮胖），范圍查找方便（相對hash的優勢）。
explain
其他的見：
https://blog.csdn.net/chengxuyuanyonghu/article/details/61431386
runtime2.go 中關於 p 的定義： 其中 runnext 指針決定了下一個要運行的 g，根據英文的注釋大致意思是說：
所以當設置 runtime.GOMAXPROCS(1) 時，此時只有一個 P，創建的 g 依次加入 P， 當最後一個即 i==9 時，加入的最後 一個 g 將會繼承當前主 goroutinue 的剩餘時間片繼續執行，所以會先輸出 9， 之後再依次執行 P 隊列中其它的 g。
https://studygolang.com/articles/23333?fr=sidebar
方法一：
方法二：
[圖片上傳失敗...(image-4ef445-1594976286098)]
方法1：to_days，返回給的日期從0開始算的天數。
方法2：data_add。向日期添加指定時間間隔
[圖片上傳失敗...(image-b67b10-1594976286098)]
https://blog.csdn.net/itcastcpp/article/details/80462619
❸ 電子專業 面試題
我也是電子專業的，主要是考察數電模電和單片機，如果你是搞通訊設備，信號與系統和數字信號處理也要准備的，以下是我搜集的一些試題和部分答案，希望對你有幫助！
模擬電路
1、 基爾霍夫定理的內容是什麼？（仕蘭微電子）
基爾霍夫電流定律是一個電荷守恆定律,即在一個電路中流入一個節點的電荷與流出同一個節點的電荷相等.
基爾霍夫電壓定律是一個能量守恆定律,即在一個迴路中迴路電壓之和為零.
2、平板電容公式(C=εS/4πkd)。（未知）
3、最基本的如三極體曲線特性。（未知）
4、描述反饋電路的概念，列舉他們的應用。（仕蘭微電子）
5、負反饋種類（電壓並聯反饋，電流串聯反饋，電壓串聯反饋和電流並聯反饋）；負反饋的優點（降低放大器的增益靈敏度，改變輸入電阻和輸出電阻，改善放大器的線性和非線性失真，有效地擴展放大器的通頻帶，自動調節作用）（未知）
6、放大電路的頻率補償的目的是什麼，有哪些方法？（仕蘭微電子）
7、頻率響應，如：怎麼才算是穩定的，如何改變頻響曲線的幾個方法。（未知）
8、給出一個查分運放，如何相位補償，並畫補償後的波特圖。（凹凸）
9、基本放大電路種類（電壓放大器，電流放大器，互導放大器和互阻放大器），優缺 點
，特別是廣泛採用差分結構的原因。（未知）
10、給出一差分電路，告訴其輸出電壓Y+和Y-,求共模分量和差模分量。（未知）
11、畫差放的兩個輸入管。（凹凸）
12、畫出由運放構成加法、減法、微分、積分運算的電路原理圖。並畫出一個晶體管級的
運放電路。（仕蘭微電子）
13、用運算放大器組成一個10倍的放大器。（未知）
14、給出一個簡單電路，讓你分析輸出碰局電壓的特性（就是個積分電路），並求輸出端某點
的 rise/fall時間。(Infineon筆試試題)
15、電阻R和電容C串聯，輸入電壓為R和C之間的電壓，輸出電壓分別為C上電壓和R上電壓，要求制這兩種電路輸入電壓的頻譜，判斷這兩種電路何為高通濾波器，何為低通濾波器。當RC<< period - setup ? hold
16、時鍾周期為T,觸發器D1的建立時間最大為T1max，最小為T1min。組合邏輯電路最大延遲晌吵知為T2max,最小為T2min。問，觸發器D2的建立時間T3和保持時間應滿足什麼條件.（華為）
17、給出某個一般時序電路的圖，有Tsetup,Tdelay,Tck->q,還有 clock的delay,寫出決定最大時鍾的因素，同時給出表達式。（威盛VIA 2003.11.06 上海筆試試題）
18、說說靜態、動態時序模擬的優缺點。（威盛VIA
2003.11.06 上海筆試試題）
19、一個四級的Mux,其中第二級信號為關鍵信號 如何改善timing。（威盛VIA2003.11.06 上海筆試試題）
20、給出一個門級的圖，又給了各個門的傳輸延時，問關鍵路徑是什麼，還問給出輸入,使得輸出依賴於關鍵路徑。（未知）
21、邏輯方面數字電路的卡諾圖化簡，時序（同步非同步差宴消異），觸發器有幾種（區別，優點），全加器等等。（未知）
22、卡諾圖寫出邏輯表達使。（威盛VIA 2003.11.06 上海筆試試題）
____________________________________________________________
信號與系統
1、的話音頻率一般為300~3400HZ，若對其采樣且使信號不失真，其最小的采樣頻率應為多大？若採用8KHZ的采樣頻率，並採用8bit的PCM編碼，則存儲一秒鍾的信號數據量有多大？（仕蘭微面試題目）
2、什麼耐奎斯特定律,怎麼由模擬信號轉為數字信號。（華為面試題）
3、如果模擬信號的帶寬為 5khz,要用8K的采樣率，怎麼辦？lucent) 兩路？
4、信號與系統:在時域與頻域關系。（華為面試題）
5、給出時域信號，求其直流分量。（未知）
6、給出一時域信號，要求（1）寫出頻率分量，（2）寫出其傅立葉變換級數；（3）當波形經過低通濾波器濾掉高次諧波而只保留一次諧波時，畫出濾波後的輸出波形。（未知）
7、sketch 連續正弦信號和連續矩形波(都有圖)的傅立葉變換 。（Infineon筆試試題）
8、拉氏變換和傅立葉變換的表達式及聯系。（新太硬體面題）
____________________________________________________________
DSP、嵌入式、軟體等
1、請用方框圖描述一個你熟悉的實用數字信號處理系統，並做簡要的分析；如果沒有，也可以自己設計一個簡單的數字信號處理系統，並描述其功能及用途。（仕蘭微面試題目）
2、數字濾波器的分類和結構特點。（仕蘭微面試題目）
3、IIR，FIR濾波器的異同。（新太硬體面題）
4、拉氏變換與Z變換公式等類似東西，隨便翻翻書把如.h(n)=-a*h(n-1)+b*δ(n) a.求h(n)的z變換；b.問該系統是否為穩定系統；c.寫出FIR數字濾波器的差分方程；（未知）
5、DSP和通用處理器在結構上有什麼不同，請簡要畫出你熟悉的一種DSP結構圖。（信威dsp軟體面試題）
6、說說定點DSP和浮點DSP的定義（或者說出他們的區別）（信威dsp軟體面試題）
7、說說你對循環定址和位反序定址的理解.（信威dsp軟體面試題）
8、請寫出【－8，7】的二進制補碼，和二進制偏置碼。用Q15表示出0.5和－0.5.（信威dsp軟體面試題）
9、DSP的結構（哈佛結構）；（未知）
10、嵌入式處理器類型(如ARM)，操作系統種類（Vxworks,ucos,winCE,linux），操作系統
方面偏CS方向了，在CS篇裡面講了；（未知）
11、有一個LDO晶元將用於對手機供電，需要你對他進行評估，你將如何設計你的測試項目？
12、某程序在一個嵌入式系統（200M CPU，50M SDRAM）中已經最優化了，換到零一個系統
（300M CPU，50M SDRAM）中是否還需要優化？ （Intel）
13、請簡要描述HUFFMAN編碼的基本原理及其基本的實現方法。（仕蘭微面試題目）
14、說出OSI七層網路協議中的四層（任意四層）。（仕蘭微面試題目）
15、A） （仕蘭微面試題目）
＃i nclude
void testf(int*p)
{
*p+=1;
}
main()
{
int *n,m[2];
n=m;
m[0]=1;
m[1]=8;
testf(n);
printf("Data v alue is %d ",*n);
}
------------------------------
B)
＃i nclude
void testf(int**p)
{
*p+=1;
}
main()
{int *n,m[2];
n=m;
m[0]=1;
m[1]=8;
testf(&n);
printf(Data v alue is %d",*n);
}
下面的結果是程序A還是程序B的？
Data v alue is 8
那麼另一段程序的結果是什麼？
16、那種排序方法最快? （華為面試題）
17、寫出兩個排序演算法,問哪個好？（威盛）
18、編一個簡單的求n!的程序 。（Infineon筆試試題）
19、用一種編程語言寫n!的演算法。（威盛VIA 2003.11.06 上海筆試試題）
20、用C語言寫一個遞歸演算法求N！；（華為面試題）
描述反饋電路的概念，列舉他們的應用。
反饋，就是在電子系統中，把輸出迴路中的電量輸入到輸入迴路中去。
反饋的類型有：電壓串聯負反饋、電流串聯負反饋、電壓並聯負反饋、電流並聯負反饋。
負反饋的優點：降低放大器的增益靈敏度，改變輸入電阻和輸出電阻，改善放大器的線性和非線性失真，有效地擴展放大器的通頻帶，自動調節作用。
電壓負反饋的特點：電路的輸出電壓趨向於維持恆定。
電流負反饋的特點：電路的輸出電流趨向於維持恆定。
3、有源濾波器和無源濾波器的區別
無源濾波器：這種電路主要有無源元件R、L和C組成
有源濾波器：集成運放和R、C組成，具有不用電感、體積小、重量輕等優點。
集成運放的開環電壓增益和輸入阻抗均很高，輸出電阻小，構成有源濾波電路後還具有一定的電壓放大和緩沖作用。但集成運放帶寬有限，所以目前的有源濾波電路的工作頻率難以做得很高。
數字電路
1、同步電路和非同步電路的區別是什麼？
同步電路：存儲電路中所有觸發器的時鍾輸入端都接同一個時鍾脈沖源，因而所有觸發器的狀態的變化都與所加的時鍾脈沖信號同步。
非同步電路：電路沒有統一的時鍾，有些觸發器的時鍾輸入端與時鍾脈沖源相連，這有這些觸發器的狀態變化與時鍾脈沖同步，而其他的觸發器的狀態變化不與時鍾脈沖同步。
2、什麼是"線與"邏輯，要實現它，在硬體特性上有什麼具體要求？
將兩個門電路的輸出端並聯以實現與邏輯的功能成為線與。
在硬體上，要用OC門來實現，同時在輸出埠加一個上拉電阻。
由於不用OC門可能使灌電流過大，而燒壞邏輯門。
3、解釋setup和hold time violation，畫圖說明，並說明解決辦法。（威盛VIA2003.11.06上海筆試試題）
Setup/hold time是測試晶元對輸入信號和時鍾信號之間的時間要求。建立時間是指觸發器的時鍾信號上升沿到來以前，數據穩定不變的時間。輸入信號應提前時鍾上升沿（如上升沿有效）T時間到達晶元，這個T就是建立時間-Setup time.如不滿足setup time,這個數據就不能被這一時鍾打入觸發器，只有在下一個時鍾上升沿，數據才能被打入觸發器。
保持時間是指觸發器的時鍾信號上升沿到來以後，數據穩定不變的時間。如果hold time不夠，數據同樣不能被打入觸發器。
建立時間(Setup Time)和保持時間（Hold time）。建立時間是指在時鍾邊沿前，數據信號需要保持不變的時間。保持時間是指時鍾跳變邊沿後數據信號需要保持不變的時間。如果數據信號在時鍾沿觸發前後持續的時間均超過建立和保持時間，那麼超過量就分別被稱為建立時間裕量和保持時間裕量。
4、什麼是競爭與冒險現象？怎樣判斷？如何消除？（漢王筆試）
在組合邏輯中，由於門的輸入信號通路中經過了不同的延時，導致到達該門的時間不一致叫競爭。
產生毛刺叫冒險。如果布爾式中有相反的信號則可能產生競爭和冒險現象。
解決方法：一是添加布爾式的消去項，二是在晶元外部加電容。
5、名詞：SRAM、SSRAM、SDRAM
SRAM：靜態RAM
DRAM：動態RAM
SSRAM：Synchronous Static Random Access Memory同步靜態隨機訪問存儲器。它的一種類型的SRAM。SSRAM的所有訪問都在時鍾的上升/下降沿啟動。地址、數據輸入和其它控制信號均於時鍾信號相關。這一點與非同步SRAM不同，非同步SRAM的訪問獨立於時鍾，數據輸入和輸出都由地址的變化控制。
SDRAM：Synchronous DRAM同步動態隨機存儲器
6、FPGA和ASIC的概念，他們的區別。（未知）
答案：FPGA是可編程ASIC。
ASIC:專用集成電路，它是面向專門用途的電路，專門為一個用戶設計和製造的。根據一個用戶的特定要求，能以低研製成本，短、交貨周期供貨的全定製，半定製集成電路。與 門陣列等其它ASIC(Application Specific IC)相比，它們又具有設計開發周期短、設計製造成本低、開發工具先進、標准產品無需測試、質量穩定以及可實時在線檢驗等優點。
7、什麼叫做OTP片、掩膜片，兩者的區別何在？
OTP means one time program，一次性編程
MTP means multi time program，多次性編程
OTP（One Time Program）是MCU的一種存儲器類型
MCU按其存儲器類型可分為MASK(掩模)ROM、OTP(一次性可編程)ROM、FLASHROM等類型。
MASKROM的MCU價格便宜，但程序在出廠時已經固化，適合程序固定不變的應用場合；
FALSHROM的MCU程序可以反復擦寫，靈活性很強，但價格較高，適合對價格不敏感的應用場合或做開發用途；
OTP ROM的MCU價格介於前兩者之間，同時又擁有一次性可編程能力，適合既要求一定靈活性，又要求低成本的應用場合，尤其是功能不斷翻新、需要迅速量產的電子產品。
8、單片機上電後沒有運轉，首先要檢查什麼？
首先應該確認電源電壓是否正常。用電壓表測量接地引腳跟電源引腳之間的電壓，看是否是電源電壓，例如常用的5V。
接下來就是檢查復位引腳電壓是否正常。分別測量按下復位按鈕和放開復位按鈕的電壓值，看是否正確。
然後再檢查晶振是否起振了，一般用示波器來看晶振引腳的波形，注意應該使用示波器探頭的「X10」檔。另一個辦法是測量復位狀態下的IO口電平，按住復位鍵不放，然後測量IO口（沒接外部上拉的P0口除外）的電壓，看是否是高電平，如果不是高電平，則多半是因為晶振沒有起振。
另外還要注意的地方是，如果使用片內ROM的話（大部分情況下如此，現在已經很少有用外部擴ROM的了），一定要將EA引腳拉高，否則會出現程序亂跑的情況。有時用模擬器可以，而燒入片子不行，往往是因為EA引腳沒拉高的緣故（當然，晶振沒起振也是原因只一）。經過上面幾點的檢查，一般即可排除故障了。如果系統不穩定的話，有時是因為電源濾波不好導致的。在單片機的電源引腳跟地引腳之間接上一個0.1uF的電容會有所改善。如果電源沒有濾波電容的話，則需要再接一個更大濾波電容，例如220uF的。遇到系統不穩定時，就可以並上電容試試（越靠近晶元越好）。
1、二極體的導通時的壓降。
答：0.7V。
2、三極體的工作條件。
答：B極（基極）在有一定的電壓時，發射極電壓應該在0.3V以上。
3、TTL電平的電壓值。
答：5V上下浮動10%，即4.5V―5.5V。
4、電路分析主要講的是什麼，或者是圍繞著什麼講的？
答：兩個定理，即基爾霍夫電壓定理，基爾霍夫電流定理。
5、數字信號處理的實質。
答：數字演算法或數學演算法。通過數學或數字演算法實現頻譜搬移，從而達到濾
波的效果。
6、單片機匯流排。
答：數據匯流排、控制匯流排、地址匯流排。P0口為I/O口，即可以是數據線，也可以是地址線，倘若都要使用時，要用鎖存器將二者分開，做地址線時，充當地址線的低8位，高8位由P2口充當。
7、晶振的接法或分類。
答：內接晶振和外接晶振。晶振與口線的距離越近越好。否則，會對其他部分造成高頻干擾。
8、鍵盤與控制器（或者是單片機）連接時時如何工作的。
答：通過控制器（或者是單片機）對鍵盤掃描，即：通過鍵盤與控制器相連導線上的電平值來判斷按下的鍵盤，從而判斷相應的鍵盤值，通過中斷，調用相應的中斷服務子程序。一般是通過鍵盤的行掃描和列掃描判斷鍵盤。
9、通信的三種解調方式。
答：調頻、調相、調幅。
10、語音信號的范圍和傳輸比特。
答：語音信號的頻率為300―3400赫茲，取上限頻率。一般取4000赫茲，有抽樣定理可知最低抽樣頻率為8000赫茲，中國採用PCM編碼調制，即位8段，因此傳輸比特為64K。（順便提一點，中國採用的是A律，與歐洲是一樣的，即13折線，日本、美國用的是u律，15折線）
11、2M帶寬。
答：語音傳輸是64K,中國用的是30/32線路系統，64K*32=2048k,即為我們所說的2M.
12、無線傳輸為什麼都是用的高頻。
答：從客觀上來說，使用的頻段是已經訂好的，常用的是80M―120M。從專業角度上來分析，是因為在高頻段上能提供較為理想的信道，達到信息良好的傳輸和帶寬的資源有效利用，而且這樣所提供的信道帶寬也比較寬。
13、CDMA技術。
答：CDMA技術是碼分多址技術，是無線通訊產品和服務的新時代率先開發的、用於提供十分清晰的語音效果的數字技術。通過利用數字編碼"擴譜"無線電頻率技術，CDMA能夠提供比其他無線技術更好的、成本更低的語音效果、保密性、系統容量和靈活性，以及更加完善的服務。
14、CDMA的工作。
答：CDMA利用擴譜技術將語音分解成數字化的小片斷，然後進行編碼，以區別每個電話。因而，大量的用戶能夠共享相同的頻譜，從而大大提高系統的性能。也就是說，CDMA使無線服務提供商將更多的數字化信號擠壓到一定的無線網路片斷中去。
15、常用的信道復用技術。
答：頻分多路復用(FDM)，時分多路復用(TDM)，頻分多址 (FDMA)，時分多址(TDMA)，碼分多址(CDMA)。
16、單片機對系統的濾波。
答：單片機對系統只能實現數字濾波，即通過一種數字演算法對系統進行濾波。常用的有中值濾波，平滑濾波，程序濾波等
❹ 有關演算法快速排序的問題
先說一下快速排序中最好的排序情況，最好的情況下，每次進行一次分區，我們會把一個序列剛好分為幾近相等的兩個子序列，這個情況也每次段攔遞歸調用的是時候也就剛好處理一半大小的滑雀子序列。這看起來其實就是一個完全二叉樹，樹的深度為 O(logn)，所以需要做 O(logn) 次嵌套調用。但是在同一信燃早層次結構的兩個程序調用中，不會處理為原來數列的相同部分。因此，程序調用的每一層次結構總共全部需要 O(n) 的時間。所以這個演算法在最好情況下的時間復雜度為 O(nlogn)。
但是將遞減數據調用快速排序進行遞增排序，是快速排序中情況最差的，你可以試想一下，假設每次分區後都出現子序列的長度一個為 1 一個為 n-1，這會導致我們的表達式變成：
T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1)
這是時間復雜度就是 O(n²)。
❺ 面試官常問十大經典演算法排序（用Python實現）
演算法是一種與語言無關的東西，更確切地說就算解決問題的思路，就是一個通用的思想的問題。代碼本身不重要，演算法思想才是重中之重
我們在面試的時候總會被問到一下演算法，雖然演算法是一些基礎知識，但是難起來也會讓人非常頭疼。
排序演算法應該算是一些簡單且基礎的演算法，但是我們可以從簡單的演算法排序鍛煉我們的演算法思維。這里我就介紹經典十大演算法用python是怎麼實現的。
十大經典演算法可以分為兩大類：
比較排序： 通過對數組中的元素進行比較來實現排序。
非比較排序： 不通過比較來決定元素間的相對次序。
演算法復雜度
冒泡排序比較簡單，幾乎所有語言演算法都會涉及的冒泡演算法。
基本原理是兩兩比較待排序數據的大小 ，當兩個數據的次序不滿足順序條件時即進行交換，反之，則保持不變。
每次選擇一個最小（大）的，直到所有元素都被輸出。
將第一個元素逐個插入到前面的有序數中，直到插完所有元素為止。
從大范圍到小范圍進行比較-交換，是插入排序的一種，它是針對直接插入排序演算法的改進。先對數據進行預處理，使其基本有序，然後再用直接插入的排序演算法排序。
該演算法是採用 分治法 對集合進行排序。
把長度為n的輸入序列分成兩個長度為n/2的子序列，對這兩個子序列分別採用歸並排序，最終合並成序列。
選取一個基準值，小數在左大數在在右。
利用堆這種數據結構所設計的一種排序演算法。
堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。利用最大堆和最小堆的特性。
採用字典計數-還原的方法，找出待排序的數組中最大和最小的元素，統計數組中每個值為i的元素出現的次數，對所有的計數累加，將每個元素放在新數組依次排序。
設置一個定量的數組當作空桶；遍歷輸入數據，並且把數據一個一個放到對應的桶里去；對每個不是空的桶進行排序；從不是空的桶里把排好序的數據拼接起來。
元素分布在桶中：
然後，元素在每個桶中排序：
取得數組中的最大數，並取得位數；從最低位開始取每個位組成新的數組；然後進行計數排序。
上面就是我整理的十大排序演算法，希望能幫助大家在演算法方面知識的提升。看懂之後可以去試著自己到電腦上運行一遍。最後說一下每個排序是沒有調用數據的，大家記得實操的時候要調用。
參考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
❻ 面試經典數據結構和演算法匯總
如果說數據結構是骨架，那麼演算法就是靈魂。沒了骨架，靈魂沒有實體寄託；沒了靈魂，骨架也是個空殼。兩者相輔相成，缺一不可，在開發中起到了砥柱中流的作用。
現在我對各種數據結構和演算法做一總結，對比一下它們的效率
1.數據結構篇
1. 如果讓你手寫個棧和隊列，你還會寫嗎？
2. 開發了那麼多項目，你能自己手寫個健壯的鏈表出來嗎？
3. 下次面試若再被問到二叉樹，希望你能對答如流！
4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！
2.排序演算法篇
1. 幾個經典的基礎排序演算法，你還記得嗎？
2. 手把手教你學會希爾排序，很簡單！
3. 快速排序演算法到底有多快？
4. 五分鍾教你學會歸並排序
5. 簡單說下二叉樹排序
6. 學會堆排序只需要幾分鍾
7. 圖，這個玩意兒竟然還可以用來排序！
掌握了這些經典的數據結構和演算法，面試啥的基本上沒什麼問題了，特別是對於那些應屆生來說。接下來再總結一下不同數據結構和演算法的效率問題，做一下對比，這也是面試官經常問的問題。
數據結構常用操作效率對比：
常用排序演算法效率的對比：
關於經典的數據結構和演算法，就總結到這，本文建議收藏，利用等公交、各種排隊之時提升自己。這世上天才很少，懶蛋卻很多，你若對得起時間，時間便對得起你。
❼ O(n) 排序演算法
第一：一共多少個數？？是不是一共只有有限個數
第二：數據范圍是什麼閉絕？如果橡亂只有有限轎如姿歌曲之的話可以向樓上說的那樣桶排
對於一般情形，O(n)是不可能的
❽ 十五道海量數據處理面試題
給定 a b 兩個文件 各存放 億個 url 每個 url 各占 位元組 內存限制是 G 讓你找出 a b 文件共同的 url ？
方案 可以估計每個文件安的大小為 G× = G 遠遠大於內存限制的 G 所以不可能將其完全載入到內存中處理 考慮採取分而治之的方法
方案 如果允許有一定的錯誤率 可以使用Bloom filter G內存大概可以表示 億bit 將其中一個文件中的url使用Bloom filter映射為這 億bit 然後挨個讀取另外一個文件的url 檢查是否與Bloom filter 如果是 那麼該url應該是共同的url（注意會有一定的錯誤率）
讀者反饋 @crowgns
有 個文件 每個文件 G 每個文件的每一行存放的都是用戶的 query 每個文件的 query 都可能重復 要求你按照 query 的頻度排序
方案
方案
一般query的總量是有限的 只是重復的次數比較多而已 可能對於所有的query 一次性就可以加入到內存了 這樣 我們就可以採用trie樹/hash_map等直接來統計每個query出現的次數 然後按出現次數做快速/堆/歸並排序就可以了
（ 讀者反饋 @店小二 原文第二個例子中 找一台內存在 G左右的機器 依次對用hash_map(query query_count)來統計每個query出現的次數 由於query會重復 作為key的話 應該使用hash_multimap hash_map不允許key重復 此反饋是否正確 待日後考證）
方案
與方案 類似 但在做完hash 分成多個文件後 可以交給多個文件來處理 採用分布式的架構來處理（比如MapRece） 最後再進行合並
有一個 G 大小的一個文件 裡面每一行是一個詞 詞的大小不超過 位元組 內存限制大小是 M 返回頻數最高的 個詞
方案 順序讀文件中 對於每個詞x 取 然後按照該值存到 個小文件（記為）中 這樣每個文件大概是 k左右 如果其中的有的文件超過了 M大小 還可以按照類似的方法繼續往下分 知道分解得到的小文件的大小都不超過 M 對每個小文件 統計每個文件中出現的詞以及相應的頻率（可以採用trie樹/hash_map等） 並取出出現頻率最大的 個詞（可以用含 個結點的最小堆） 並把 詞及相應的頻率存入文件 這樣又得到了 個文件 下一步就是把這 個文件進行歸並（類似與歸並排序）的過程了
海量日誌數據 提取出某日訪問網路次數最多的那個 IP
方案 首先是這一天 並且是訪問網路的日誌中的IP取出來 逐個寫入到一個大文件中 注意到IP是 位的 最多有 ^ 個IP 同樣可以採用映射的方法 比如模 把整個大文件映射為 個小文件 再找出每個小文中出現頻率最大的IP（可以採用hash_map進行頻率統計 然後再找出頻率最大的幾個）及相應的頻率 然後再在這 個最大的IP中 找出那個頻率最大的IP 即為所求
在 億個整數中找出不重復的整數 內存不足以容納這 億個整數
方案 採用 Bitmap（每個數分配 bit 表示不存在 表示出現一次 表示多次 無意義）進行 共需內存 ^ * bit= GB內存 還可以接受 然後掃描這 億個整數 查看Bitmap中相對應位 如果是 變 變 保持不變 所描完事後 查看bitmap 把對應位是 的整數輸出即可
方案 也可採用上題類似的方法 進行劃分小文件的方法 然後在小文件中找出不重復的整數 並排序 然後再進行歸並 注意去除重復的元素
海量數據分布在 台電腦中 想個辦法高效統計出這批數據的 TOP
方案
（更多可以參考 第三章 尋找最小的 k 個數 以及第三章續 Top K 演算法問題 的實現）
讀者反饋 @QinLeopard
第 題的方法中 是不是不能保證每個電腦上的前十條 肯定包含最後頻率最高的前十條呢？ 比如說第一個文件中 A( ) B( ) C( ) D( ) 第二個文件中 A( ) B( ) C( ) D( ) 第三個文件中: A( ) B( ) C( ) D( ) 如果要選Top( ) 選出來的結果是A 但結果應該是B
@July 我想 這位讀者可能沒有明確提議 本題目中的 TOP 是指最大的 個數 而不是指出現頻率最多的 個數 但如果說 現在有另外一提 要你求頻率最多的 個 相當於求訪問次數最多的 個IP地址那道題 即是本文中上面的第 題 特此說明
怎麼在海量數據中找出重復次數最多的一個？
方案 先做hash 然後求模映射為小文件 求出每個小文件中重復次數最多的一個 並記錄重復次數 然後找出上一步求出的數據中重復次數最多的一個就是所求（具體參考前面的題）
上千萬或上億數據（有重復） 統計其中出現次數最多的錢 N 個數據
方案 上千萬或上億的數據 現在的機器的內存應該能存下 所以考慮採用hash_map/搜索二叉樹/紅黑樹等來進行統計次數 然後就是取出前N個出現次數最多的數據了 可以用第 題提到的堆機制完成
萬字元串 其中有些是重復的 需要把重復的全部去掉 保留沒有重復的字元串 請怎麼設計和實現？
方案 這題用trie樹比較合適 hash_map也應該能行
一個文本文件 大約有一萬行 每行一個詞 要求統計出其中最頻繁出現的前 個詞 請給出思想 給出時間復雜度分析
方案 這題是考慮時間效率 用trie樹統計每個詞出現的次數 時間復雜度是O(n*le)（le表示單詞的平準長度） 然後是找出出現最頻繁的前 個詞 可以用堆來實現 前面的題中已經講到了 時間復雜度是O(n*lg ) 所以總的時間復雜度 是O(n*le)與O(n*lg )中較大的哪一個
一個文本文件 找出前 個經常出現的詞 但這次文件比較長 說是上億行或十億行 總之無法一次讀入內存 問最優解
方案 首先根據用hash並求模 將文件分解為多個小文件 對於單個文件利用上題的方法求出每個文件件中 個最常出現的詞 然後再進行歸並處理 找出最終的 個最常出現的詞
w 個數中找出最大的 個數
尋找熱門查詢
搜索引擎會通過日誌文件把用戶每次檢索使用的所有檢索串都記錄下來 每個查詢串的長度為 位元組 假設目前有一千萬個記錄 這些查詢串的重復讀比較高 雖然總數是 千萬 但是如果去除重復和 不超過 百萬個 一個查詢串的重復度越高 說明查詢它的用戶越多 也就越熱門 請你統計最熱門的 個查詢串 要求使用的內存不能超過 G
( ) 請描述你解決這個問題的思路
( ) 請給出主要的處理流程 演算法 以及演算法的復雜度
方案 採用trie樹 關鍵字域存該查詢串出現的次數 沒有出現為 最後用 個元素的最小推來對出現頻率進行排序
關於此問題的詳細解答 請參考此文的第 節 第三章續 Top K 演算法問題的實現
一共有 N 個機器 每個機器上有 N 個數 每個機器最多存 O(N) 個數並對它們操作 如何找到 N^ 個數中的中數？
方案 先大體估計一下這些數的范圍 比如這里假設這些數都是 位無符號整數（共有 ^ 個） 我們把 到 ^ 的整數劃分為N個范圍段 每個段包含（ ^ ）/N個整數 比如 第一個段位 到 ^ /N 第二段為（ ^ ）/N到（ ^ ）/N … 第N個段為（ ^ ）（N ）/N到 ^ 然後 掃描每個機器上的N個數 把屬於第一個區段的數放到第一個機器上 屬於第二個區段的數放到第二個機器上 … 屬於第N個區段的數放到第N個機器上 注意這個過程每個機器上存儲的數應該是O(N)的 下面我們依次統計每個機器上數的個數 一次累加 直到找到第k個機器 在該機器上累加的數大於或等於（N^ ）/ 而在第k 個機器上的累加數小於（N^ ）/ 並把這個數記為x 那麼我們要找的中位數在第k個機器中 排在第（N^ ）/ x位 然後我們對第k個機器的數排序 並找出第（N^ ）/ x個數 即為所求的中位數的復雜度是O（N^ ）的
方案 先對每台機器上的數進行排序 排好序後 我們採用歸並排序的思想 將這N個機器上的數歸並起來得到最終的排序 找到第（N^ ）/ 個便是所求 復雜度是O（N^ *lgN^ ）的
最大間隙問題
給定n個實數 求著n個實數在實軸上向量 個數之間的最大差值 要求線性的時間演算法
方案 最先想到的方法就是先對這n個數據進行排序 然後一遍掃描即可確定相鄰的最大間隙 但該方法不能滿足線性時間的要求 故採取如下方法
將多個集合合並成沒有交集的集合
給定一個字元串的集合 格式如 要求將其中交集不為空的集合合並 要求合並完成的集合之間無交集 例如上例應輸出
( ) 請描述你解決這個問題的思路
( ) 給出主要的處理流程 演算法 以及演算法的復雜度
( ) 請描述可能的改進
方案 採用並查集 首先所有的字元串都在單獨的並查集中 然後依掃描每個集合 順序合並將兩個相鄰元素合並 例如 對於 首先查看aaa和bbb是否在同一個並查集中 如果不在 那麼把它們所在的並查集合並 然後再看bbb和ccc是否在同一個並查集中 如果不在 那麼也把它們所在的並查集合並 接下來再掃描其他的集合 當所有的集合都掃描完了 並查集代表的集合便是所求 復雜度應該是O(NlgN)的 改進的話 首先可以記錄每個節點的根結點 改進查詢 合並的時候 可以把大的和小的進行合 這樣也減少復雜度
最大子序列與最大子矩陣問題
數組的最大子序列問題 給定一個數組 其中元素有正 也有負 找出其中一個連續子序列 使和最大
方案 這個問題可以動態規劃的思想解決 設b[i]表示以第i個元素a[i]結尾的最大子序列 那麼顯然 基於這一點可以很快用代碼實現
最大子矩陣問題 給定一個矩陣（二維數組） 其中數據有大有小 請找一個子矩陣 使得子矩陣的和最大 並輸出這個和
lishixin/Article/program/sjjg/201405/30744
❾ X分之3.6等於3分之二節比例
排序演算法第一篇-排序演算法介紹
在面試中，現在無論大小公司都會有演算法的。其中排序演算法也是一種很常見的面試題。比如冒泡，快排等。這些，排序演算法自己看了一次又一次，可是過一段時間，又忘掉了。所以，這次就把演算法是怎麼推導出來的，詳細記錄下來。看看這次多久還會忘記。
本文主要介紹排序演算法的分類、時間復雜度、空間復雜。為了後面的學習做准備的。
通過本文學習，將收獲到：排序演算法分幾類？什麼是演算法的時間復雜度？是怎麼算出來的？什麼是演算法的空間復雜度？常見的時間復雜度比較。
如果這些您都已經知道了，可以不用耽誤時間看了。
約定：
文中的n2表示的是n的2次方(n²),n^2也是表示n的2次方；
n3表示的是n的3次方；
n^k表示的是n的k次方；
long2n表示的是以2為底的對數。
本文出自：凱哥java(微信：kaigejava)學習Java版數據結構與演算法筆記。
一：介紹
排序又稱排序演算法(Sort Algorithm),排序是將一組數據，依據指定的順序進行排序的過程。
二：分類
排序的分類分為兩大類
2.1：內部排序
內部排序是指將需要處理的所有數據一次性都載入到內存中進行排序的。
如：冒泡、快排等這些演算法都是內部排序的
2.2：外部排序
數據量過大，無法全部載入到內存中，需要藉助於外部存儲進行排序的。
如：資料庫中數據8個G，內存只有4個G的這種。
2.3：參加分類如下圖：
三：演算法的時間復雜度
3.1：分類
衡量一個程序(演算法)執行時間有兩種方法
3.1.1：事後統計的方法
所謂的事後統計方法，顧名思義，就是程序(演算法)已經寫完了，運行後得到的結果。
這種方法雖然是可行的，但是有兩個問題：
①：要想對設計的演算法運行的性能進行評估，需要實際運行該程序(浪費時間)；
②：運行所得的時間統計嚴重依賴於機器的硬體、軟體等環境因為。
這種方法有個嚴苛的要求：要在同一台機器在相同狀態(軟硬體)下運行，才能比較哪個演算法更快。
3.1.2：事前估算的方法
通過分析某個演算法的時間復雜度來判斷哪個演算法更優。
3.2：時間頻度
概念：一個演算法花費的時間與演算法中語句執行的次數成正比。哪個演算法中語句執行次數多，那麼這個演算法所花費的時間就多(這不廢話嗎)。
一個演算法中語句執行次數稱為語句頻度或時間頻度。記為：T(n).
(復雜的概念是，時間頻度：一個演算法執行所消耗的時間，從理論上是 不能算出來的，想要具體數值，必須要將程序上機運行測試才能知道。但是我們不可能也沒必要對每個演算法都上機進行測試的，只需要知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句執行的次數成正比的，哪個演算法中語句執行次數多，那麼這個程序花費的時間就多。一個演算法中的語句執行次數稱為語句頻度或者時間頻度，即為：T(n))
例如：我們知道的技術從1到100所有數字的和。這個就有兩種演算法。分別如下：
①：使用for循環，從1到100循環出來，然後累加出來。代碼如下：
根據上面概念(注意對概念的理解,total和end這兩行相對於for循環來說，可以忽略。後面我們還會詳細講解還會忽略哪些)，我們來看下這個演算法的時間頻度是多少呢？
在for循環中，實際需要執行101次(+1的原因是因為，在for循環的時候，需要做最後一次判斷，才能推出。因此n個數的計算一共是n+1次操作)。所以其時間頻度就是：T(n)=n+1;
我們再來看看第二種演算法：
是不是很簡單，只要一行代碼就執行完成了。所以第二種演算法的T(n)=1了。是不是很快呢？
時間頻度是不是一眼就看出來了？是不是不用在代碼運行下來比較運行時間了？
(ps：從上面簡單地從1到100求和演算法中，我們是不是感受到演算法的魅力了？感受到編程之美了？)
3.3：時間復雜度
在上面3.2中提到的時間頻度中,n稱為問題的規模，當n不斷變化的時候，時間頻度T(n)也會不斷變化。但是有時我們想知道它在變化的時候呈現什麼樣的規律呢？為此，我們引入了時間復雜度概念。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示。若有某個輔助函數f(n)，是的當n趨近於無窮大的時候，T(n)/f(n)的極限值為不等於零的參數，則稱為f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n))為演算法的漸進的時間復雜度。簡稱時間復雜度。這就是大O法。
在計算時間復雜度的時候，我們會忽略以下幾個數據值
3.3.1：忽略常數項
比如上面，我們計算1到100的第一種演算法中，有兩行int total=0；和 int end = 100;這兩行代碼，這個數值是2，我們一般計算時間復雜度的時候，會忽略這個常數項的。為什麼呢？請看下面四個函數，隨著n的增大而增大運行時間。
T(n) = 2n+20
T(n) = 2*n
T(n)=3n+10
T(n)=3*n
請看下圖隨著n的增大所呈現的規律：
我們來看看，把這些數據使用折線圖展示：
圖例說明：上面兩個是3*n及3n+10的，下面兩個是2n及2n+10的
從上面兩個圖表中我們可以得到以下結論：
①：2n+20和2*n隨著n的增加，執行曲線無限接近(折線圖中下面兩個)，常量值20可以忽略了
②：3n+10和3*n隨著n的增加，執行曲線無限接近(折線圖中上面兩個)，常量值10可以忽略了
所以，綜上所述，在計算程序(演算法)時間復雜度的時候,常量值是可以忽略的
3.3.2：忽略低次項
請看下面四個函數，隨著n的增大又會呈現什麼規律嗎？
T(n)=2n^2+3n+10
T(n)=2n^2
T(n)=n^2+5n+20
T(n)=n^2
說明：n^2表示n的2次方
我們來看看隨著n的增加，運行所消耗的時間。如下圖：
把上面數據，用折線圖表示，如下圖：
圖例說明：上面兩個是2n^2及2n^2+3n+10，下面兩個是n^2及 n^2+5n+20
從上面兩個圖中我們可以得到如下結論：
①：2n^2+3n+10和2n^2隨著n的增大，執行曲線無限接近，可以忽略低次項及常量項：3n+10
②：n^2+5n+20和n^2隨著n的增大，執行曲線無限接近，可以忽略低次項及常量項：5n+20
綜上所述，我們可以得到結論：在計算程序(演算法)時間復雜度的時候，低次項(3n=3*n^1比n^2項數少)是可以忽略的
3.3.3：忽略系數
我們再來看看下面四個函數，看看它們隨著n的增大呈現出什麼樣的規律
T(n)=3n^2+2n
T(n)=5n^2+7n
T(n)=n^3+5n
T(n)=6n^3+4n
隨著n的增加，運行時間所消耗耗時如下圖：
折線圖如下：
從上圖可以得到如下：
①：隨著n值變大，5n^2+7n和3n^2+2n，執行曲線重合，說明這種情況下，系數5和3可以忽略；
②：n^3+5n和6n^3+4n，執行曲線分離，說明多少次方是關鍵
3.3.4：總結：
計算時間復雜度的時候忽略常數項、忽略低次項、忽略系數
T(n)不同，但時間復雜度可能相同。
如：T(n)=n2+7n+6與T(n)=3n^2+2n+2它們的T(n)不同，但時間復雜相同，都為O(n^2).
計算時間復雜度的方法用常數1代替運行時間中的所有加法常數T(n)=n^2+7n+6 =>T(n)=n^2+7n+1修改後的運行次數函數中，只保留最高階項T(n)=n^2+7n+1 => T（n）=n^2去除最高階項的系數T(n)=n^2 =>T(n)=n^2 => O(n^2)
3.4：常見的時間復雜度
常數階O(1)
對數階O(log2n)
線性階O(n)
線性對數階O(nlog2n)
平方階O(n^2)
立方階O(n^3)
K次方階(n^k)
指數階O(2^n)
各個時間復雜度復雜度折線圖如下圖：
總結：
常見演算法時間復雜度由小到大依次為：
O(1)
從上圖折線圖中，我們可以看出，程序(演算法)盡可能的避免使用指數階段的演算法。
3.5：常見演算法時間復雜度舉例
3.5.1：常數階O(1)
無論代碼執行多少行，只要是沒有循環等復雜結構，那這個代碼的時間復雜度就是O(1)
(計算時間復雜度的時候，忽略常數項)
代碼demo:
上述代碼在執行的時候，消耗的時間並不是隨著某個變數的增長而增長，那麼無論這類代碼有多長，即使有有幾萬幾十萬行，都是可以用O(1)來表示它的時間復雜度。
3.5.2：對數階O(log2n)
代碼敬上：
說明：
在while循環裡面，每次都是將i*2的。n的值是固定的，所以在i乘完之後，i距離n就越來越近了。假設循環x次之後，i就大於n了，此時這個循環就退出了。也就是說2的x次方等於n了。那麼x=log2n。也就是說當循環了log2n次以後，代碼就結束了。因此這個代碼的時間復雜度就是
O(log2n)。
O(log2n)的這個2時間上是隨著代碼變化的。如果i = i*3，那麼時間復雜度就是O(log3n)
回顧下log的理解(這是初中知識點)：
如果a的x次方等於N（a>0,且a≠1），那麼熟x就叫做以a為底的對數(logarithm)，記作x=logaN.
其中，a叫做對數的底數，N叫做真數，x叫做「以a為底N的對數」。
3.5.3：線性階O(n)
代碼如下：
說明：
這段代碼，for循環裡面的代碼會執行n次。因此它所消耗的時間隨著n的變化而變化的，因此這類代碼都是可以用O(n)來表示它的時間復雜度。
3.5.4：線性對數階O(nlogn)
代碼如下：
說明：
線性對數階O(nlogN)其實非常容易理解的。將時間復雜度為O(logn)的代碼循環了N次的話，那麼它的時間復雜度就是n*O(logn)，也就是O(nlogN)
3.5.5：平方階O(n2)
代碼：
說明：
平方階O(n2)就容易理解了。如果把O(n)的代碼再嵌套循環一遍，它的時間復雜度就是O(n2)，
上圖中的代碼起始就是嵌套了2層n循環，它的時間復雜度就是O(n*n)，即時O(n2)。如果將其中一層循環的n修改成m，那麼它的時間復雜度就變成了O(m*n).
3.5.6：立方階O(n3)、K次方階O(n^k)
說明：參考上面的O(n2)去理解就好了。O(n3)起始就相當於是三層n循環了。其他的一次類推。
3.6：平均時間復雜度和最壞時間復雜度
平均時間復雜度：
是指所有可能的輸入實例均以概率出現的情況下，該演算法的運行時間
最壞時間復雜度：
是指在最壞情況下的時間復雜度稱為最壞時間復雜度。一般討論時間復雜度均是最壞情況下的時間復雜度。
這樣做的原因：最壞情況下的時間復雜度是演算法在任何輸入實例上運行時間的界限。這就保證了演算法的運行時間不會比最壞情況更長了。
平均時間復雜度和最壞時間復雜度是否一致，和演算法有關。具體如下圖：
四：演算法的空間復雜度
空間復雜度介紹
類似於時間復雜度的討論。一個演算法的空間復雜度(Space Complexity)定義為該演算法所消耗的存儲空間，它也是問題規模n的函數；
空間復雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。有的演算法需要佔用臨時工作單元數與解決問題的規模n有關。它們隨著n的增大而增大，當n較大的時候，將佔用較多的存儲單元(存儲空間)。例如：在快排(快速排序)和歸並排序演算法就屬於這種情況。
在做演算法分析的時候，主要討論的是時間的復雜度。因為從用戶的使用體驗上來看，更看重的是程序執行的速度的快慢。一般緩存產品(比如Redis)和技術排序演算法本質就是拿空間換時間的。
下節預告：
下節我們將講講冒泡排序和選擇排序。使用的是圖解+代碼一步一步推導出來演示的。歡迎大家一起學習
❿ 騰訊面試題整理及經驗技巧
本人IT屌絲一枚，畢業4年，5年經驗(大四在騰訊實習一年，實習生工資，工作內容同正式員工一樣)。非常幸運，先後收到過騰訊、網路和阿里的offer，在這里跟大家分享下騰訊面試經驗，同諸君共勉。
本人職業生涯的起點開始於騰訊，能入職騰訊其實非常偶然。09年騰訊校招的時候，在本人的學校(學校是2本就不說名字了)開宣講會，學院很多同學都去了，因為當時對騰訊興趣不大所以沒去，當時希望去中軟金蝶這樣的傳統軟體公司。一個宿舍的兄弟要去參加騰訊校招的筆試，我作為親友團陪他一起去。騰訊的hr很nice給了我一張筆試題和意願表讓我填。本來我想從學校北門直接坐車回家，既然來了反正也沒什麼事就寫了，算是為以後找工作熱身。騰訊面試筆試內容主要是編程基礎和排序查找演算法之類的題，還有用程序實現遞歸這樣的，具體的忘記了。
筆試題感覺很簡單，附加題也答上了(本人專業課學霸、其他科學渣)。答完也沒檢查就坐車回家了，吃飯的時候收到騰訊叫我第二天去一面的簡訊，剛好我爸爸媽媽在南山的同學去我家做客，就乘阿姨的順風車回學校準備第二天的面試。
騰訊一面的面試官非常的nice也是我後來的組長，非常有人格魅力的一個人，我去的時候還特意給我倒了一杯水。騰訊面試官員主要問我了解的技術，我就介紹了下在大學期間做的C++、.Net和J2EE項目，規則引擎、財務系統、學業預警系統、爬蟲引擎這些。因為完全沒准備所以回憶起來有點吃力，還好面試官沒有刁難，發揮還可以。問了Java的內存機制，會不會導致內存泄漏，這個答的不太好;問了下hibernate的機制和作用都回答上了，讓寫了下爬蟲程序的核心代碼和正則表達式。
一面整整面了30分鍾感覺有戲，就回去好好准備2面的內容，把當年工程代碼翻出來復習以免再出現忘記的尷尬。很快第二天就通知去進行技術二面。技術二面就是傳說中的壓力面，被好一頓虐待。項目中的問題一個沒問，問的全是操作系統、數據結構的問題。還好專業都是A+，大多數題都回答上了。問了下我樹轉二叉樹，這個小意思。還問了Java內存機制和是否會有內存泄漏什麼情況下會泄漏，good這個在一面回去之後就看了，回答的完美。最後一題是問的查找QQ號。小case，寫了個二分查找;他說你認為我會滿意嗎，我想了想又寫了一個哈希查找，他說還是不滿意。這個時候我已經有點小不爽了，就說不知道。在有點尷尬的氣氛中結束了面試。當時覺得沒戲了，有點失落。回家看了下演算法導論，原來有一個極為高效的演算法是二叉查找，騰訊面試，唉，人家已經提示了，但是還沒想到，有點小遺憾。
過了一周收到騰訊的hr面試邀請的時候，說實話非常的意外。聽說我們學校本科生全軍覆沒，就我一個過了2面，研究生只有3個過了2面。hr面沒問什麼特別的，此處不表。一周後收到騰訊的正式offer，還是有點小激動的。薪水方面超過了我的預期，但最主要的是一面的面試官看起來很厲害的樣子，感覺騰訊也是一家很厲害的公司。
在騰訊幹了四年，正式三年，實習一年。後來開始負責招聘，我們部門在選擇求職者的時候主要看聰明程度、視野、大局觀、氣場等軟實力。當時我負責面了一個孩子，各方面挺不錯的，組長覺得也還行，但是被總監斃掉了，原因是太軟不夠霸氣。還有一個哥們技術和基礎感覺都還行，但是被組長斃掉了，原因是視野和聰明度不夠。
所以准備面試騰訊的同學，建議多留意近期的互聯網的最新動態，多練練表達。如果能在面試中批判一下近期騰訊的決策失誤和產品缺陷，無論對錯都會認為這個孩子不錯，那麼一定會加分的;但是也不能過了，完全說的不對還侃侃而談會讓人覺得你這個人很浮誇也是會被斃掉的。尺度的拿捏很重要。還有一點，語速快而且語氣堅決目光堅毅自信的比語速慢表達不流暢的同學成功幾率高。我面過一個哥們，後來他頂替了我領域負責人的位置，這是後話。他在面試的時候就非常的自信，如果問一些「弱智」問題會被他反諷，當時大家就覺得這個人很厲害，面試也很順利，1天連續面了5面，當天就發了offer。騰訊面試，騰訊社招是電話面、技術一面、組長面、平台總監面、部門經理面、hr面。總共6面，面談是5面。
面試的時候首先要自信，如果能做到不卑不亢其實就已經成功了一半。我感覺大多數程序員都不太自信，給人感覺有點文弱，如果你自己都對自己不自信，怎麼能奢求公司對你自信呢。但是也不能太自信，自信心爆棚就是自大，面過一個2年開發經驗的問他技術都不知道，就談項目。騰訊面試，問他項目中做了什麼就談項目是什麼。在我這就被斃掉了還問你們能不能開到30w，我只能讓他回家等消息了。
騰訊面試題整理——並附有網友的解答，感興趣的同學參考下
一不定項選擇題(共25題，每題4分，共100分，少選、錯選、多選均不得分)
1已知一棵二叉樹，如果先序遍歷的節點順序是：ADCEFGHB，中序遍歷是：CDFEGHAB，則後序遍歷結果為：(D)
A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA
根據先序遍歷和中序遍歷能唯一確定二叉樹：
注意：要想唯一確定一顆二叉樹，必須已知兩種遍歷，並且其中必須有中序，因為先序和後序不能確定左右子樹，如下圖所示：
從上圖中我們可以看出，沒有中序是不能確定一顆樹的!
2下列哪兩個數據結構，同時具有較高的查找和刪除性能?(CD)
A.有序數組B.有序鏈表C.AVL樹D.Hash表
數組的刪除性能比較差，而鏈表的查找性能比較差!
3下列排序演算法中，哪些時間復雜度不會超過nlogn?(BC)
A.快速排序B.堆排序C.歸並排序D.冒泡排序
快排和冒泡排序在最壞情況下的時間復雜度是O(n^2);
4初始序列為18625473一組數採用堆排序，當建堆(小根堆)完畢時，堆所對應的二叉樹中序遍歷序列為：(A)
A.83251647
B.32851467
C.38251674
D.82351476
建立小根堆的過程如下圖所示：
5當n=5時，下列函數的返回值是：(A)
intfoo(intn){
if(n<2){
returnn;
}
else
returnfoo(n-1)+foo(n-2);
}
A.5B.7C.8D.10
6S市A，B共有兩個區，人口比例為3：5，據歷史統計A的犯罪率為0.01%，B區為0.015%，現有一起新案件發生在S市，那麼案件發生在A區的可能性有多大?(C)
A.37.5%B.32.5%C.28.6%D.26.1%
3*0.01%/(3*0.01%+5*0.015%)=28.6%
7Unix系統中，哪些可以用於進程間的通信?(ABCD)
進程間通信主要包括管道,系統IPC(包括消息隊列,信號量,共享存儲),SOCKET.
A.SocketB.共享內存C.消息隊列D.信號量
8靜態變數通常存儲在進程哪個區?(C)
A.棧區B.堆區C.全局區D.代碼區
棧區一般用於存儲比較小的臨時變數;
堆區一般用於存儲比較大的臨時變數;
代碼區用於存儲代碼;
全局區用於存儲全局變數，靜態變數等。
9查詢性能(B)
A.在Name欄位上添加主鍵
B.在Name欄位上添加索引
C.在Age欄位上添加主鍵
D.在Age欄位上添加索引
如果經常依據特定的欄位搜索表或對表的記錄進行排序，則可以通過創建該欄位的索引來加快執行這些操作的
10IP地址131.153.12.71是一個(B)類IP地址。
A.AB.BC.CD.D
A類：0打頭
B類：10打頭
C類：110打頭
D類：1110打頭
11下推自動識別機的語言是：(C)
A.0型語言B.1型語言C.2型語言D.3型語言
參考：維基網路
12下列程序的輸出是：(D)
#defineadd(a+b)a+b
intmain()
{
printf("%d\n",5*add(3+4));
return0;
}
5*3+4=19
A.23B.35C.16D.19
13瀏覽器訪問某頁面，HTTP協議返回狀態碼為403時表示：(B)
A找不到該頁面
B禁止訪問
C內部伺服器訪問
D伺服器繁忙
14如果某系統15*4=112成立，則系統採用的是(A)進制。
A.6B.7C.8D.9
逐個帶入即可：
對於6進制而言：15的十進制就是11;112的十進制就是44，11*4=44。
15某段文本中各個字母出現的頻率分別是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼編碼，則哪種是可能的編碼：(A)
Aa(000)b(001)h(01)i(10)o(11)
Ba(0000)b(0001)h(001)o(01)i(1)
Ca(000)b(001)h(01)i(10)o(00)
Da(0000)b(0001)h(001)o(000)i(1)