C+、Python、編程題、智商題等10個方向的面試常考題型總結!大概這就是大佬吧
大量面經總結
包括牛客網的和我聽來的
作者:ShawnNg
來源:牛客網
前言
謝謝牛客網幫助我成功拿到心儀的offer(自然語言演算法工程師),也感覺各位大佬分享的面經,所以想回饋一波。
在這期間我找到很多面經資料,自己用代碼過濾整理了出來。
我個人覺得這個資料是十分有用的,我希望也能幫助到各位。祝大家也能夠早日找到心儀的工作!
目錄
Python
C++
智商題
大數據
計算機基礎
概率題
HR常問問題
開放題
機器學習
編程題
Phython
Python的元組和列表的區別。
a = [1, 2, 3, 4], b = a, b[0] = 100, 請問print(a)結果是什麼
list是怎樣實現的。
list有哪幾種添加元素的方法,能否從表頭插入元素?
如何提高Python的運行效率
如何獲取list中最後一個元素
常用的數據結構及應用場景(list,dict,tuple)
C++
Makefile文件,提示未定義的引用,是什麼原因(我答的是使用C庫忘記加extern,其實應該是沒有在makefile指定編譯順序)
STL中set怎麼實現的,假設有「I like love」三個詞,如何存。每個節點是直接指向這個單詞的指針嗎)
STL中vector是怎樣實現的
const
虛函數
c++如何實現一個介面?(抽象類、純虛函數)
c++的數據成員的可見性,繼承到子類之後的可見性(這裡我是分了不同繼承方式討論的),子類友原函數對父類private能否可見。
g++中-L,-I,-l的作用,有什麼區別。-l指定鏈接庫的時候,如何a庫依賴b庫,是否a庫必須放在b庫前面
傳遞一個指針進某函數體內,為什麼不能對它重新分配空間,如果想要分配,應該怎麼做?(指針的指針)
如何想讓變數a=100的時候中斷,如何寫gdb代碼
如何用gdb調試core文件,
對stl的了解程度,map的內部實現原理,為什麼選擇紅黑樹,紅黑樹的由來,與平衡二叉樹的區別
拷貝構造函數和重載=符分別在什麼情況下被調用,實現有什麼區別
是否有用C++寫過實際的工程項目。
程序有錯誤如何調試(回答打log,如何段錯誤,gdb調試core文件)
虛函數的目的,虛函數和模板類的區別,如何找到虛函數
說一下TreeMap的實現原理?紅黑樹的性質?紅黑樹遍歷方式有哪些?如果key衝突如何解決?
智商題
100張牌,每次只能抽一張,抽過的牌會丟掉,怎麼選出最大的牌。
36匹馬,6條跑道,選出最快3匹,最少賽多少場?
5個海盜搶到了100顆寶石,每一顆都一樣的大小和價值連城。他們決定:抽籤決定自己的號碼(1,2,3,4,5)。首先,由1號提出分配方案(你抽到1號),然後大家5人進行表決,當且僅當超過半數的人同意時,按照他的提案進行分配,否則將被扔入大海喂鯊魚。 如果1號死後,再由2號提出分配方案,依此類推。條件:每顆寶石都是一樣的價值。海盜都想保命,盡量多得寶石,盡量多殺人。問題:你會提出怎樣的分配方案才能夠使自己的收益最大化?
一個人要過一座80米的橋,每走一米需要吃一顆豆子,他最多可以裝60顆豆子,問最少需要吃多少顆豆子才能走完橋?證明一下為什麼你給的答案是最少的?橋長81米呢?當橋長n米,最多裝m顆的時候結果用公式怎麼表示?
一個繩子燒完需要1個小時,假設所有繩子的材質都不一樣,也不均勻,怎麼取出1小時加 15分鐘。
把1~9這9個數填入九格宮裡,使每一橫、豎、斜相等。
有100個黑球,100個白球。兩個桶,桶的容量無限,每個球都可以任意放在任何一個桶中,沒有限制,請設計一種分配方法,使得白黑球分配到兩個桶之後, 某個人從某個桶中取出的球是白球的概率最大化。(這個人去第一個桶取球的概率是1/2,第二個桶也是1/2)
有1億個貨物,不能單個單個檢測,只能通過兩兩對比來找出其中的次品,請設計一個演算法來找出次品。
有25匹馬 ,5個跑道,一次只能比5匹馬,得到跑得最快的前3,至少需要比幾次?
有3盞燈,房間外有3個開關,你只有1次機會進入房間,怎麼判斷哪個開關對應哪盞燈?
給一堆螺母和螺栓,它們可以一一對應,但是現在順序亂了,只能用螺母和螺栓比較,將它們一一對應起來。
大數據
100億數字,怎麼統計前100大的?
10億個url,每個url大小小於56B,要求去重,內存4G。
1KW句子算相似度(還是那套分塊+hash/建索引,但是因為本人不是做這個的,文本處理根本說一片空白,所以就不誤導大家了),之後就是一直圍繞大數據的題目不斷深化。
Q1:給定一個1T的單詞文件,文件中每一行為一個單詞,單詞無序且有重複,當前有5台計算機。請問如何統計詞頻?
Q2:每台計算機需要計算200G左右的文件,內存無法存放200G內容,那麼如何統計這些文件的詞頻?
Q3:如何將1T的文件均勻地分配給5台機器,且每台機器統計完詞頻生成的文件只需要拼接起來即可(即每台機器統計的單詞不出現在其他機器中)
一個大文件A和一個小文件B,裡面存的是單詞,要求出在文件B中但不在文件A中的單詞。然後大文件A是無法直接存到內存中的。
一道題目是如果有一個人註冊一個qq,如何保證這個qq號碼和之前已存在的qq號碼不重複呢?
扔硬幣,連續出現兩次正面即結束,問扔的次數期望
有100W個集合,每個集合中的word是同義詞,同義詞具有傳遞性, 比如集合1中有word a, 集合2中也有word a, 則集合1,2中所有詞都是同義詞,對這100W個集合進行歸併,同義詞都在一個集合當中。
有幾個 G 的文本,每行記錄了訪問 ip 的 log ,如何快速統計 ip 出現次數最高的 10 個 ip,如果只用 linux 指令又該怎麼解決;
海量數據的topk問題
計算機基礎
Linux下的一些指令,$$(進程id),$?(上一條命令退出時狀態),怎麼查看進程,按照內存大小,CPU佔用排序等等。
Linux的命令:pwd、ln、which
Linux線程通信
hash表是怎麼實現的?有衝突的時候怎麼處理?
linux 文件詞頻統計
介紹一下hash,怎麼解決衝突。
你說一下hashmap的原理
內存泄露出現原因。
悲觀鎖樂觀鎖
把兩個表按id合併怎麼搞?
資料庫transaction
淺拷貝深拷貝
第二題是兩題 sql ,涉及 join,group by,max,min,sum,count 等操作的結合,以及同個題目多種寫法。
線程安全是什麼意思?新線程什麼情況下會影響原有線程?
網路基礎TCP三次握手
計算機網路:描述他發一句hello world到我這邊顯示,中間經歷了哪些過程,我從應用層開始一層層往下分析答的,主要說http和tcp,網路層和鏈路層有些忘,但主要的幾個協議和子網劃分什麼的也答了,面試官比較滿意
詞向量的推導,混合高斯,linux硬鏈接,三次握手,linux inode
進程線程的區別
概率題
100人坐飛機,第一個乘客在座位中隨便選一個坐下,第100人正確坐到自己坐位的概率是?
X是一個以p的概率產生1,1-p的概率產生0的隨機變數,利用X產生1/2概率是0,1/2概率是1的隨機變數。
X,Y均服存於 [0,1] 的均勻分布,求X+Y。
一個國家重男輕女,只要生了女孩就繼續生,直到生出男孩為止,問這個國家的男女比例?
一個有7個格子的環,三種顏色染色,相鄰不能顏色重複,問多少種方案
一個袋子里有很多種顏色的球,其中抽紅球的概率為1/4,現在有放回地抽10個球,其中7個球為紅球的概率是多少?
一枚硬幣,扔了一億次都是正面朝上,再扔一次反面朝上的概率是多少?
一道概率題,54張牌,平均分成三堆,大小王在同一堆的概率?
一道概率題,一個六位的密碼,由0~9組成,問你正過來看和倒過來看密碼是一樣的概率。
一道組合數學題。10盞燈,滅三盞,兩頭的必須亮著,不能滅掉相鄰的兩盞燈,問組合數?
三個硬幣,分別是正正,反反,正反。隨機拋一個硬幣,結果是正面,問選的是那個硬幣
個人玩遊戲,100個球,每次挑5個,如何保證必勝。52張牌,四個人抽,黑桃A和紅桃A同時在一個人手裡的概率。
好像是問有70%的人喜歡玩遊戲,30%的人不喜歡玩遊戲,現在推送的資源必須是50%遊戲,50%非遊戲。問怎麼分配比較合理。
有n個elements和1個Compare(A, B)函數,用Compare函數作為排序演算法中的比較運算元給elements排序。Compare函數有p的可能比較錯。排序完取Top m個元素,本來就在Top m並被正確分在Top m的元素個數是x。問x的數學期望。
有兩個隨機數產生器,R1以0.7的概率產生1,以0.3的概率產生0,而R2以0.3的概率產生1,0.7的概率產生0.問如何組合這兩種產生器,使新得到的隨機數產生器以0.5的概率產生1,0.5的概率產生0。隨機數產生器可復用。
有兩枚硬幣A和B,A正面的概率為0.6,B正面的概率為0.5.現在扔了一枚硬幣顯示為正面,問:該枚硬幣是A的概率是多少?
概率題:有種癌症,早期的治癒率為0.8,中期的治癒率為0.5,晚期的治癒率為0.2.若早期沒治好就會轉為中期,中期沒治好就會變成晚期。現在有一個人被診斷為癌症早期,然後被治癒了,問他被誤診為癌症的概率是多少?
給一個函數,返回0和1,概率為p和1-p,請你實現一個函數,使得返回01概率一樣。
給定一個分類器p,它有0.5的概率輸出1,0.5的概率輸出0。Q1:如何生成一個分類器使該分類器輸出1的概率為0.25,輸出0的概率為0.75?Q2:如何生成一個分類器使該分類器輸出1的概率為0.3,輸出0的概率為0.7?
問了一個概率題 54張牌,分成6份,每份9張牌,大小王在一起的概率
HR常問問題
為什麼不讀博、對讀博報以什麼態度。
為什麼選擇百度,谷歌百度都給你offer你選哪個。
為什麼選擇跨專業學計算機?
為什麼選擇阿里
以後可能要學習很多新技術,你怎麼看。
你平時喜歡做什麼?看過哪些書?最近在看什麼書?
你覺得最有挑戰的項目是什麼。
你覺得最難忘的事情是什麼?
你認為你的優(缺)點是什麼。
你還有什麼想問的?
加班怎麼看。
印象最深刻的事?
壓力最大的情況是什麼時候。
在面試過程中覺得自己那些當面有進步
場景分析題,有一個任務給你,要求一個月完成,但是以目前的能力一個月完成不了,現在你知道有一個同事擅長這部分工作,但是他有自己的活,幫助你就可能耽誤他的進度,問你咋辦。
大學令你覺得最不爽的事情是什麼
如何學習的?
如何看待加班。
實習期間項目,在組內擔任的角色,是否熟悉其他組員的工作。
家庭教育觀念?
家裡什麼情況?獨生子女?
將來的職業規劃?
工作地點
工作地點的問題
平時有什麼興趣愛好。
我覺得我會先去專心鑽研技術,到達一定的
最後問了一下我興趣愛好
有什麼問題問我。
有沒其他offer
有沒有想過去創業公司
現在在哪裡實習?實習主要做些什麼?
簡單介紹一下自己
聊聊offer情況,有什麼考慮之類的。
聊聊實驗室生活。
能不能來北京
自己有什麼優點缺點?
自己本科生和研究生相比有哪些進步
要求用兩個字評價大學生涯。
講一下你覺得你突出的地方,有亮點的地方。
評價一下你自己的優點缺點?
詳細介紹項目。
說下你的優缺點
說說你的經歷。
說說你自己的性格。
說說研究生階段最有成就的事,遇到問題具體怎麼解決的。
請你說一下你對應聘該崗位的優勢。
遇到的最大挫折是什麼。
問你的職業規劃,遇到挑戰怎麼處理,有沒有之前和同事發生過較大分歧。
開放題
2016年每個項目有個上線和下線時間段,統計每天在線的項目數量
一堆問題和答案的pair,算它們的相關性
一面現場面,自我介紹加挑一個項目細講,還有場景題,第一題是QQ添加好友按名稱搜索時,怎麼區別廣告號,詐騙號;
為什麼之前沒有深度網路出現(數據量不夠+機器性能)
為今日頭條設計一個熱門評論系統,支持實時更新。
從項目中在哪一方面體會最深。
假設一個文檔,連續的K個詞,認為是一個時間窗口,一個時間窗口的詞有關係,如何得到所有的時間窗口。
假設你擁有一切搜索數據,問怎麼在不同場景下進行推薦,具體場景忘了(核心點:共線性、語義相似度、主題聚類等等)
假設有100W個單詞,如何存儲(我答的是trie樹,面試官問每個節點會有很多子節點,每個子節點是一個指針,佔用8個位元組,如何節省空間,我說不知道,面試官提示雙數組trie樹)
假設要對一場nba球賽進行自動解說,會遇到哪些困難,又該怎麼解決呢?
做過哪些項目?項目中遇到哪些難點,你是怎樣解決的?
關於集群調度的一些經驗 trick 掌握多少;
分詞時,為了提高效率,怎麼存儲詞典?(鍵樹)如何壓縮存儲?
在微信的場景下,如何判斷用戶的職業?開放問題
場景題如何鑒別淘寶上賣假貨的商家,價格維度可以用什麼策略等
如何做一個新聞推薦
如何在語料中尋找頻繁出現的字串,分析複雜度。
如何用儘可能少的樣本訓練模型同時又保證模型的性能;
如何預測雙十一支付寶的負載峰值。
對推薦演算法的未來看法。
平面上有n個點,讓你設計一個數據結構,能夠返回這個這n個點中距離某特定點最近的一個點。一開始講了下kd樹,然而太複雜面試官不滿意,就講了一個類似GeoHash的方案。
建立一個數據結構,基於此寫一段程序用於存儲sparse vector,同時編寫一個函數實現兩個sparse vector的相加運算
很多單詞,如何計算單詞之間的相似度(或者對單詞進行分類)
怎麼預測降雨量。
我只有一大批實體詞, 如何對他們進行聚類(無監督聚類), 如何找出這些詞中, 哪些詞之間有關係, 是強關係還是弱關係, 具體是什麼關係,(如劉德華和朱麗倩 屬於娛樂分類, 是強關係, 關係為夫妻)
拼車軟體是如何定價的以及如何優化。
推薦演算法(基於用戶的協同過濾,基於內容的協同過濾)
推薦系統的冷啟動問題如何解決
文本挖掘中,分詞演算法?如何選取特徵?如何進行相似度計算,文本聚類結果如何評估?
無給定條件,預測蔬菜價格。
有100W個集合,每個集合中有一些詞,對於每個集合,找出他是哪些集合的真子集。
有一堆已經分好的詞,如何去發現新的詞?
比賽相關問題提特徵特徵選擇等
海量的 item 算文本相似度的優化方法;
特徵工程經驗。
用兩分鐘介紹自己的項目,創新點在哪裡。
用戶給三個item(query),如何給出查詢網頁。
第三題是如何鑒別實施詐騙的QQ用戶;
第二題是微信朋友圈內容的安全鑒別;
第四題是如何做反作弊,例如公眾號的刷閱讀量。
系統設計題,給一個query,如何快速從10億個query中找出和它最相似的 (面試官說可以對每個query找1000個最相似的,存起來,每天離線更新)
線性代數:特徵線性依賴,出現冗餘,會導致什麼問題?
給一堆數據找找到最佳擬合的直線,數據有較多雜訊
給你一個系統(面試官好像是無人車部門的),後台的邏輯已經實現了,但是前端載入很慢,怎麼檢測。
給你兩個文件a和b,大小大概100M,兩個文件每行一個整數,要求找到兩個文件中相同的整數,存到文件c里,問我怎樣儘快的完成這項工作?
給出一個演算法實現如何確定快遞郵件上的地址,要求從國家到省市到縣到鄉鎮的一個識別,要求效率高(有陷阱,比如有的人把縣寫到市的前面,有人喜歡寫地域名稱的省略詞比如安徽省寫成安徽或者皖)。
給定淘寶上同類目同價格範圍的兩個商品A和B,如何利用淘寶已有的用戶、商品數據、搜索數據、評論數據、用戶行為數據等所有能拿到的數據進行建模,判斷A和B統計平均性價比高低。統計平均性價比的衡量標準是大量曝光,購買者多則高。
給很多單詞,統計某個子串出現次數,我給的方法還是用Trie,只不過一個單詞要分成多個插入到Trie數中就行了。
給很多單詞,要求統計出現某個前綴出現次數。
統計全球會彈鋼琴的人數,我用機器學習的思路答的,面試官還比較滿意
自己項目中有哪些可以遷移到其他領域的東西。
講了講自己在深度學習的認識,問的問題是幾個具體場景的設計,包括怎麼從海量數據中提取熱點問題。
設計 LRU 系統
設計一個合理的電梯調度策略,調度兩個電梯 ,考慮滿足基本的接送需求,滿足能耗最小,滿足用戶等待時間最短
設計一個系統可以實時統計任意ip在過去一個小時的訪問量;
設計一個結構存取稀疏矩陣(面試官最後告訴我了一個極度壓縮的存法,相同行或列存偏差,我當時沒聽懂,還不懂裝懂,最後還是沒記住)
設計實現一個git diff
說一下最能代表你技術水平的項目吧?
項目:具體問了特徵怎麼做的。
(難到我了,我想的方法不好,面試告訴我了他的想法,類似於一個進程調度問題,每一時刻只可能有一個用戶按按鈕,把這條指令接收,判斷當前電梯能否滿足,能滿足就執行,不能滿足則放入一個隊列里,實際情況還要細化)
機器學習
Boost演算法
CART(回歸樹用平方誤差最小化準則,分類樹用基尼指數最小化準則)
GBDT與隨機森林比較。
GBDT(利用損失函數的負梯度在當前模型的值作為回歸問題提升樹演算法中的殘差的近似值,擬合一個回歸樹)
KKT條件用哪些,完整描述
KNN(分類與回歸)
L1 與 L2 的區別以及如何解決 L1 求導困難。
L1和L2函數。
L1和L2正則相關問題。
L1和L2正則項,它們間的比較
L1正則為什麼可以把係數壓縮成0,坐標下降法的具體實現細節
LR為什麼用sigmoid函數。這個函數有什麼優點和缺點?為什麼不用其他函數?
LR和SVM有什麼區別,libsvm和liblinear有什麼區別。
Logistics與隨機森林比較
Logistics(推導)
Logistic回歸的推導,怎麼得到objective function。
SVM與隨機森林比較
SVM為什麼要引入拉格朗日的優化方法。
SVM原問題和對偶問題關係?
SVM在哪個地方引入的核函數, 如果用高斯核可以升到多少維。
SVM怎麼防止過擬合
SVM的目標函數。常用的核函數。
SVM的過程,講了推導過程,可能表達不清晰,都是淚
bagging、adaboost、boosting
em 與 kmeans 的關係;
k-means的k怎麼取等等
k-means演算法初始點怎麼選擇?你的項目裡面推薦演算法是怎麼實現的?
kmeans的原理,優缺點以及改進。
k折交叉驗證中k取值多少有什麼關係
l2懲罰項是怎麼減小Overfitting的?l1,l2等範數的通式是什麼?他們之間的區別是什麼?在什麼場景下用什麼範數?l1在0處不可導,怎麼處理?
randomforest,GBDT
rf, gbdt, xgboost的區別。
softmax公式
為什麼要做數據歸一化?
主要問最優化方面的知識,梯度下降法的原理以及各個變種(批量梯度下降,隨機梯度下降法,mini 梯度下降法),以及這幾個方法會不會有局部最優問題,牛頓法原理和適用場景,有什麼缺點,如何改進(擬牛頓法)
什麼情況下一定會發生過擬合?
什麼是貝葉斯估計
介紹LR、RF、GBDT ,分析它們的優缺點,是否寫過它們的分散式代碼
介紹SVD、SVD++
會哪些機器學習演算法
信息熵公式
假設面試官什麼都不懂,詳細解釋 CNN 的原理;
決策樹原理
決策樹處理連續值的方法。
決策樹如何防止過擬合
決策樹過擬合哪些方法,前後剪枝
分類模型可以做回歸分析嗎?反過來可以嗎?
分類模型和回歸模型的區別
判別模型,生成模型
各個模型的Loss function,牛頓學習法、SGD如何訓練。
因為面我的總監是做nlp的,所以講了很多rnn、lstm、還有HMM的東西。不算很熟,但是接觸過,以前稍微看過一些相關論文,所以還是勉強能聊的。
在平面內有坐標已知的若干個點P0...Pn,再給出一個點P,找到離P點最近的點。
在模型的訓練迭代中,怎麼評估效果。
如何減少參數(權值共享、VGG的感受野、GoogLeNet的inception)
如何防止過擬合(增加數據,減少模型複雜度->正則化)
對於同分布的弱分類器,求分類器均值化之後的分布的均值跟方差。
對於機器學習你都學了哪些?講一個印象深的。
常見分類模型( svm,決策樹,貝葉斯等)的優缺點,適用場景以及如何選型
歸一化方式
手寫k-means的偽代碼。
手寫k-means的偽代碼和代碼。(Code)
手撕svm硬軟間隔對偶的推導
手撕邏輯回歸(損失函數及更新方式推導)
接著寫一下信息增益的公式。
推一下bp演算法等等
改變隨機森林的訓練樣本數據量,是否會影響到隨機森林學習到的模型的複雜度。
數據挖掘各種演算法,以及各種場景下的解決方案
是否了解mutual infomation、chi-square、LR前後向、樹模型等特徵選擇方式。
是否了解線性加權、bagging、boosting、cascade等模型融合方式
有哪些常見的分類器,簡單介紹下原理
機器學習與深度學習的區別
機器學習基礎(線性回歸與邏輯回歸區別等)
機器學習:幾種樹模型的原理和對比,樸素貝葉斯分類器原理以及公式,出現估計概率值為 0 怎麼處理(拉普拉斯平滑),缺點; k-means 聚類的原理以及缺點及對應的改進;
梯度下降牛頓擬牛頓原理
梯度下降的優缺點。
深度學習和普通機器學習有什麼不同?
深度學習有很大部分是CNN,給他用通俗的語言解釋下卷積的概念,解釋下CNN中的優勢及原因
激活函數的選擇(sigmoid->ReLu->LReLU->PReLU)
然後20分鐘內手寫k-means
牛頓法、隨機梯度下降演算法和直接梯度下降演算法的區別?
牛頓法推導
特徵選擇的方法
由數據引申到數據不平衡怎麼處理(10W正例,1W負例,牛客上有原題)
聊聊SVM,這段說了好久,從基本的線性可分到不可分,相關升維,各種核函數,每個是如何實現升。以及出現了XX問題,分析是樣本的原因還是其他原因。針對不同情況,採取什麼解決方案較好。
自己實現過什麼機器學習演算法
解決過擬合的方法有哪些?
解釋 word2vec 的原理以及哈夫曼樹的改進。
解釋一下過擬合和欠擬合,有哪些方法防止過擬合。
讓我一步一步地構造決策樹,怎麼計算信息熵、信息增益、然後C4.5 ID3 CART的區別,還說了一下優缺點
詳細討論了樣本採樣和bagging的問題
說一下Adaboost,權值更新公式。當弱分類器是LR時,每個樣本的的權重是w1,w2...,寫出最終的決策公式。
說了一下bagging跟boosting。
說明L1L2正則的效果與為什麼形成這種情況(L1正則稀疏,L2正則平滑,之後說明就是畫圖說明正則化)
過擬合的解決方法;
選個你熟悉的機器學習方法 ,著重介紹一下產生原因,推導公式,背後統計意義什麼等等
邏輯回歸估計參數時的目標函數,如果加上一個先驗的服從高斯分布的假設,會是什麼樣。
邏輯回歸估計參數時的目標函數
邏輯回歸的值表示概率嗎?
問了會不會RNN,LSTM。
問了很多數據挖掘的基礎知識,包括SVM,邏輯回歸、EM、K-means等,然後給我很多場景問我遇到這些情況我要怎麼來處理數據,怎麼進行建模等等,問得很細
隨機梯度下降,標準梯度
隨機森林和GBDT的區別?LR的參數怎麼求解?有沒有最優解?
隨機森林(Bagging+CART)
編程題
1~n這n個數現在去掉兩個,如何找到去掉的兩個數。 假設去掉的兩個數是a和b,那麼通過求和,平方和可以知道a+b和a^2+b^2,然後解方程就行了。
char a[4] = ; char *b = a; b[0] = 100; 請問輸出a的結果是什麼?
一個 N*M 的矩陣,從左上走到右下最小需要(N+M)步走完,問一共有多少種走法。
一個嚴格遞增的數組,將前綴取一部分放在後面,在修改後的數組上找到最小的數。(劍指Offer原題)
一個大寫字元串如ABABB(len
一個字元數組中,每個字元都出現了3次,只有一個出現了2次,如果快速找出這個出現2次的?
一個字元矩陣,只可能是R,G,B三種字元。判斷是否滿足某個條件。這個條件是每種符號連成一個長方體,三個長方體長寬一致,且橫著平行
一個廣告,它有一個id,一個上線時間,一個下線時間,現在我有很多這樣的廣告,如果現在給你一個時間,告訴我有多少個廣告在這個時間在線的
一個數據流中,如何採樣得到100個數,保證採樣得到的100個數是隨機的?
一個數組中某個數出現次數大於一半,最快找出該數。
一個數組只有一個數字是單獨出現,其他出現了三次。
一個數組存著1-1000連續的整數,假如我取出其中一個數,怎麼能快速找到(用類二分查找)
一個數組存著負數與正數,將正數放在前面,負數放在後面
一個運算序列只有+、*、數字,計算運算序列的結果。(Code)
一堆ip地址區間,不會重疊,來一個新的ip地址,看它在不在,在哪個區間。
一維數組,swap 其中的幾對數字(每個數字只屬於一次 swap 操作),實現查找(與二分有關);
一維有序數組,經過循環位移後,最小的數出現在數列中間,如果原數組嚴格遞增或遞減,如何找這個最小數;
一維有序數組,經過循環位移後,最小的數出現在數列中間,如果原數組嚴格遞增,如何找這個最小數。
一維有序數組,經過循環位移後,最小的數出現在數列中間,如果原數組非嚴格遞增或遞減,如何找這個最小數;
一維有序數組,經過循環位移後,最小的數出現在數列中間,數組可能是遞增、遞減、遞減後遞增、遞增後遞減四種情況,遞增遞減都是非嚴格的,如果有轉折點,返迴轉折點的值,否則返回-1;
一道題:給定一個整數數組,裡面有兩個數相同,其他數都是不同的,如何儘快找到這兩個數(答,用hash表,O(N),有更好的方法么?)
一題是多位數用鏈表存儲( e.g. 123 用 1->2->3 存儲),實現相加功能函數
不創建臨時產量換兩個數
兩個同樣大小有序數組求中位數,寫代碼
兩個大整數相乘。(Code)
兩棵樹相加——對應位置兩棵樹都有值則相加,對應位置只有一棵樹有值則取該值;
中序遍歷二叉樹,利用O(1)空間統計遍歷的每個節點的層次。(Bug Free Code)
中綴表達式轉逆波蘭表達式,逆波蘭表達式求值;
為分析用戶行為,系統常需存儲用戶的一些 query ,但因 query 非常多,故系統不能全存,設系統每天只存 m 個 query ,現設計一個演算法,對用戶請求的 query 進行隨機選擇 m 個,請給一個方案,使得每個 query 被抽中的概率相等,並分析之,注意:不到最後一刻,並不知用戶的總請求量。
二分查找
二分查找,查找target,在區間[start,end]之間,如果有重複元素,返回最後一個下標,其他情況返回-1
二叉樹前序遞歸遍歷演算法(手寫代碼)
二叉樹的前中後遍歷
二叉樹的文件存儲,也就是序列化。
二叉樹遍歷,描述下層序遍歷。
二維數組,每行遞增,每列遞增,任意交換其中的兩數,發現並恢復。
二維數組,每行遞增,每列遞增,實現查找。
二維數組,每行遞增,每列遞增,求第k大的數。
什麼樣的數據結構可以滿足多次插入刪除,取最小數,給出時間複雜度。
介紹二叉樹前序遍歷非遞歸遍歷演算法(手寫代碼)
介紹大頂堆和小頂堆
從一組數中找出和為sum的三個數(leetcode原題,先sort再找,並且剪枝),寫代碼,四個數呢?說思路。
假設有個M*N的方格,從最左下方開始往最右上方走,每次只能往右或者往上,問有多少種走法,假設中間有若干個格子不能走,又有多少種走法。
允許兩個元素交換一次的最大連續子序列和。
全排列
全排列。
冒泡排序(手寫代碼)
寫 find 函數,在目標串中匹配模式串(要考慮中文字元的情況)
寫一個二叉樹的非遞歸的後續遍歷
寫一個簡單的正則匹配表達式(將文本中的123.4匹配出來)
寫個動態規劃,最長公共子序列
判斷一個字元串是否為另外一個字元串旋轉之後的字元串
前k大的數
單鏈表的翻轉
去掉連續的重複數字,輸出新數組,例如:1,2,2,2,1,3,5——> 3,5。
去除字元串S1中的字元使得最終的字元串S2不包含』ab』和』c』。(Code)
合法括弧匹配
在一個字元串中,找出最長的無重複字元的字串
在二叉樹結點結構中加一個指針域,使其指向層次遍歷的下一個結點,特別地,每一層的最後一個結點為空。(Code)
堆排序(手寫代碼)
堆是怎麼調整的。
複雜鏈表的複製。
如果給出一個二叉搜索樹的後續能不能建立(可以,因為只要將遍歷結果排序就可以得到中序結果)。
字元串反轉(手寫代碼)
字元串移位,給出字元串abc##dfg##gh,實現將所有#移至字元串串頭。輸出####abcdfggh。
字元串轉整數
字元串,給一個url,求中間的site
字元串,給一個url,求中間的site。
定義滿足$n=x^a+y^b$($x,y,a,b$是非負整數)的n是神奇數。如$4?=?2^0?+?3^1,17?=?2^3?+?3^2$。輸入l和r,請求出閉區間$[l,r]$里,最長的一段不含有神奇數的連續區間長度。$x,y,l,r=2,y>=2$,如$3 5 10 22$,在$[10,22]$區間內,$x=3,y=5$的條件下,區間內[14]是神奇數,所以最長的區間是$[15,22]$長度為$8$,如$2,3,1,10$,在$[1,10]$區間內,$x=2,y=3$的條件下,$2,3,4,5,7,9$都是神奇數,所以最長的區間只有長度$1$。
實現棧,使得 添加、刪除、max 操作的複雜度為 O(1)。
對於一個字元串,請設計一個演算法,只在字元串的單詞間做逆序調整,也就是說,字元串由一些由空格分隔的部分組成,你需要將這些部分逆序。給定一個原字元串A和它的長度,請返回逆序後的字元串。
對於一個字元串,請設計一個演算法,將字元串的長度為len的前綴平移到字元串的最後。
尋找字元串中第一個只出現一次的字元;
將字元串連續重複出現的字元刪到只剩一個,這個可以用雙指針,時間複雜度n,空間複雜度1。
常用排序演算法的時間和空間複雜度
平衡二叉樹是什麼
歸併排序(手寫代碼)
快速排序(手寫代碼)
快速排序+二分查找
手寫快排(easy)
列印數組的組合數。
列印螺旋數組;
把一個bst轉化成一個雙向鏈表。
把一個字元串的大寫字母放到字元串的後面,各個字元的相對位置不變,不能申請額外的空間。例如AbcDeFGhi ->bceiADFG
排序二叉樹轉雙向鏈表。(Code)
描述Dijkstra最短路徑演算法
插入排序(手寫代碼)
數列中找第 k 大的數字(與快排或堆排序有關)
數據解壓縮,3(a4(ab)) -> aababababaababababaabababab;
數組有隻有一個數出現一次,其他數都出現三次,找出那個數。
旋轉數組
最少時間複雜度求數組中第k大的數。(Code)
最短路徑代碼。
最長公共子串(動態規劃有關);
最長公共子序列
有一堆無向好友列表 1-2, 3-4, 2-3 之類的,問能不能把這些用戶劃分兩組,組內都不互為好友。
有序數組尋找和為某數的一對數字;
正數數組,找三個數使積最小,問有多少種選擇。
母雞、公雞和小雞問題:公雞五塊一隻,母雞三塊一隻,小雞一塊三隻,用100元買100隻雞的所有方法。
求double類型的二進位1的個數。
求二叉樹最近公共祖先(leetcode原題)
求連續子數組最大乘積,還讓考慮邊界問題(最後問了:連乘有可能導致溢出,存不下了)
用一個隊列,將每個二叉樹的root先放入隊列。
用數組實現隊列,各操作的複雜度分析。
用速度不同的指針可以判斷鏈表中是否有環,問兩速度滿足怎樣的關係可以保證發現環。
直接插入排序寫代碼
看段代碼,問輸出是啥。(就是段求二進位中1的個數)
矩陣求最長連續遞增的路徑長度
矩陣求最長連續遞增的路徑長度。
第一題是鏈表倒數第 k 節點;第二題是二叉樹列印路徑,第三題是矩陣中將 0 元素所在行列全置 0 的最優空間解法
第二輪是寫出一個演算法輸出二叉樹的 s 序列,何為 s 序列,比如現在有個二叉樹 1-2,3-4,5 6,7 這是一顆完全二叉樹, S 序列輸出就是按照 1237654 這個順序輸出,用兩個棧就能實現比較簡單。
演算法題,也只記得一個了:存在一個數組,大小98,裡面的元素均為在[1,100],且無重複, 不申請額外空間的情況下,在時間複雜度為O(N)情況下,找出缺失的兩個元素值。
給一個n*n的矩陣,矩陣中滿足每行每列都是遞增的,要查找矩陣是否存在某個數.(leetcode原題)
給一個數組,只有一個元素出現了一次,其他都出現了兩次,找出出現一次的數。
給一個數組,數組種存在一種數,它的左邊都比它小,右邊都比它大,找出所有這些數的位置。
給一個股票,n天的價格,只能兩次買入賣出,而且只能只能先賣再買,問最多賺多少錢?
給一個股票,n天的價格,只能進行一次買入和賣出,問最多賺多少錢?
給一個股票,n天的價格,可以買入賣出k次,而且只能只能先賣再買,問最多賺多少錢?
給一個股票,n天的價格,可以無限次買入賣出,問最多賺多少錢?
給了一個鏈表,第1個結點標號為1,把鏈表中標號在M到N區間的部分反轉。
給你一個無重複的數組輸出全排列。
給你一顆二叉樹按層輸出每一層輸出後都換行
給出一個二維矩陣,從(0,0)出發走到右下角,只能向右或向下走,找到一條路徑,是這條路徑上的總和最大。
給出一段代碼問代碼作用(二進位數據1的個數)
給出一顆二叉樹,兩個葉節點,找到這兩個葉節點互連通的一條最短路徑。
給定一個數組,只有一個元素出現了一次,其他都出現了3次,找出出現一次的數。
給定一個數組,有兩個元素出現了一次,其他都出現了兩次,找出兩個出現一次的數。
給定一個正整數向量,判斷這個向量是否存在一個片段,使得反轉這個片段後能夠使該向量升序排列。如:[1, 2, 4, 3],就可以通過反轉[4, 3]使得向量變為[1, 2, 3, 4]。
給定二叉樹的先序跟後序遍歷,能不能將二叉樹重建(不能,因為先序:父節點-左節點-右節點,後序:左節點-右節點-父節點,兩者的拓撲序列是一樣的,所以無法建立)
給定循環遞增數組 $a=[7,8,9,1,2,3]$和一個值$k=2$,返回該值得再數組中的下標。
給定數組A[]=和一個數T。求和為T的A中的數最少要幾個。A中的數可復用。 我寫了個遞歸,面試官不建議使用,因為效率不高。但沒有反對。
給定數組,尋找 next big(堆排序有關);
給我一個數組[1,2,5,10,20,50,100],可以從裡面取若干個數,要求得出和為100的不同取法有多少?(說出思路)
統計數列中的逆序對(歸併排序有關);
編程題:實現求正整數平方根整數部分的函數(使用梯度下降)
翻轉二叉樹(Code)
若干個二叉樹,如何按照層序遍歷
設 rand ( s , t )返回 [s,t] 之間的隨機小數,利用該函數在一個半徑為 R 的圓內找隨機 n 個點,並給出時間複雜度分析。
輸入一個大長方形,長寬ab,和一堆小長方形。選擇兩個小長方形,它能放進大長方形,而這個小長方形面積和最大
輸入一個宿舍樓亮燈描述圖,計算把所有燈關掉的最短時間,管理員起點在左下角,只能在最左或最右的樓梯往上一層,不可往下一層。每次往上一層花費1分鐘,每次往左或往右一間宿舍花費1分鐘,關燈不花時間。輸入的高
如圖:
再如:
輸入兩個正數數組,在兩個數組分別選一個數,要求第一個數組選的數的下標小於第二個數組選的數的下標。使得兩個數的乘積最大。
輸出字元串中的所有重複子串,例如:abcab,輸出: a, b, ab
連續子數組最大和
迷宮的深度搜索、廣度搜索;
選取任意數據結構實現添加、刪除、隨機返回三個功能,分析複雜度。
選擇排序(手寫代碼)
鏈表上的快速排序。
長度為N的序列Sequence=abc......Z,問有多少不同的二叉樹形態中序遍歷是這個。(Code)
問了一兩個演算法題,記不清了,只記得其中一個是:找數組中2個出現兩次的數字,還有3個兩次的數字
問了一個1的平方加到100的平方結果
非常經典的0-1背包問題
TAG:Python |