資料結構和演算法

鏈表

• 鏈表，常見的面試題有寫一個鏈表中洗掉一個節點的演算法、單鏈表倒轉、兩個鏈表找相交的部分，這個一般必須得完全無誤的情況下寫出來；
• 給出兩個鏈表的頭結點，找出這兩個鏈表的交點，
• java 中陣列和鏈表的區別，各自優勢 如何設計擁有高效的隨機讀取能力的的鏈表（跳表） 設計跳表，跳表插入開銷，跳表隨機讀取程序
• 給你一個單向鏈表，給這個鏈表做K反轉，例如 k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 反轉后為： 3 -> 2 -> 1 -> 6 -> 5 -> 4 鏈表長度保證為K的倍數
• 給定一個鏈表，回傳鏈表開始入環的第一個節點
• n個降序的鏈表回傳前K個大的節點構成的鏈表
• 鏈表合并：給出n個有序的鏈表，將他們合并為一個有序鏈表，
• 有k個有序單鏈表，怎么合并成一個有序單鏈表？
• 鏈表逆序，不能用修改指標的方法，用遞回如何實作，
• 反轉單鏈表
• 知道雙向鏈表怎么翻轉嗎
• 有兩個數字非常大已經超出了long型的范圍，現在以鏈表的方式存盤其中鏈表頭表示最高位，例如1->2->3->4表示1234，請設計一個演算法求出兩數之和；
• 反轉數字，不能把數字變成字串
• 鏈表找環的入口
• 單鏈表的逆序
• 兩個鏈表合并，最長公共子串問題
• 單鏈表逆序，快排，陣列中找兩個數和等于目標值

陣列

• 在M個大小的陣列中找到第K大的數（最大堆）
• 我現在有一個陣列[1,2,3,4]，請實作演算法，得到這個陣列的全排列的陣列，如[2,1,3,4]，?[2,1,4,3]，，，，你這個演算法的時間復雜度是多少
• 陣列A，2*n個元素，n個奇數、n個偶數，設計一個演算法，使得陣列奇數下標位置放置的都是奇數，偶數下標位置放置的都是偶數 ?先說下你的思路 ?下一個奇數？怎么找？ ?有思路么？ ?你這樣時間復雜度有點高，如果要求O(N)要怎么做
• 手寫演算法，兩個有序陣列的合并，
• 十萬行二維陣列，每行長度為10，每個陣列降序，找出最大的15個數，先跟面試官說了思路，然后又在白紙上寫了出來
• 對一個陣列進行絕對值排序的演算法；
• 非降序陣列，列印某個值最后出現的位置
• 找出陣列中超過半數的那個數字（摩爾投票）
• 一個陣列反轉，o(logn)復雜度用什么排序演算法；
• 一個 100長度陣列, 里面是 固定的亂數, 要求列出重復的數字的最優演算法.；
• 給定兩個陣列，每個陣列中都有重復的數字，不用類別庫函式，對這兩個陣列排序，
• 給定一個陣列，求該陣列所有的自子陣列 去掉一個字串中的所有空格
• 給定一個陣列，元素的大小0~25，有重復元素，按出現頻次的高低輸出所有的數字
• 給定一個亂序陣列，求陣列內最大連續的數；
• 無序陣列找第k大的數
• 給一個陣列，和k，求陣列中的哪兩個數之和為k，除了雙層for回圈和字典的方式還能用什么方式實作；

查找

• 寫二分查找演算法
• 有主字串A，子字串B，在A中查找B
• 手撕一個有序陣列的二分查找演算法
• 請說出二分查找的實作思路及時空復雜度，
• 用二分法查找一個長度為18的，排好的線性表，當查找不成功時，最多需要比較多少次

排序

• 快排怎么實作的，快速排序（包括演算法步驟、平均演算法復雜度、最好和最壞的情形）
• 5億整數的大檔案，怎么排？
• 兩個1G排好序的檔案，按序合并
• 手寫歸并排序， 兩個有序陣列合并，
• 常見的排序演算法有哪些？各種排序演算法的平均時間復雜度和最壞情況下的時間復雜度？
• 寫出你熟悉的排序演算法，并說明其優缺點
• 給了長度為N的有重復元素的陣列，要求輸出第10大的數，
• 手寫一下快速排序吧，我看你參加過ACM，所以用非遞回實作一下，
• 快排聽過嗎？他是怎么實作的？
• 如果是單鏈表的快速排序，你怎么做？
• 快排時間空間復雜度，最好最壞的情況，優化方案？
• 手寫了冒泡排序
• 手寫遞回排序等
• 兩個排序好的陣列，構思演算法把一個按序插入另一個陣列
• 手工實作一個快速排序演算法
• 列舉資料的幾個排序演算法
• 快速排序？快速排序是穩定的么？ 如何實作一個快速排序的穩定性？
• 給定一個非空陣列，回傳此陣列中第三大的數，如果不存在，則回傳陣列中最大的數，要求演算法時間復雜度必須是O(n)，
• 快排會嗎？知道原理嗎？
• 排序演算法，介紹一下快速排序，快速排序時間復雜度，是不是穩定排序，介紹幾種你所知道的穩定排序演算法
• 10億個數選最大的K個，用什么方法，復雜度多少
• 說一下冒泡排序的原理
• 請對3個有序陣列進行歸并排序

樹

• AVL樹和B樹的概念、細節，比如會問mysql資料庫的索引的實作原理，基本上就等于問你B樹了，
• 紅黑樹，這個基本上必問的一個資料結構，包括紅黑樹的概念、平均演算法復雜度、最好最壞情況下的演算法復雜度、左右旋轉、顏色變換，
• 找出二叉樹中任意兩個節點的最低公共根節點, 如果樹是BST呢. 深度優先搜索+二分查找樹性質
• B+樹如何分裂？
• 二叉樹前中后遍歷 二叉樹層次遍歷 二叉樹深度優先遍歷(遞回、非遞回) 二叉樹廣度優先遍歷(遞回、非遞回) 和為n的二叉樹路徑 二叉樹深度 二叉樹是否對稱 鏈表反轉
• 紅黑樹有啥特性?
• 二叉樹層序遍歷輸出，每一層輸出陣列（手寫演算法），
• JDK1.8采用的紅黑樹特性，以及采用紅黑樹的理由而不采用AVL和B樹的原因？
• 一個二叉搜索樹，找出某兩個節點的公共祖先，
• 給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先， 例如，輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節點 2 和節點 8 的最近公共祖先是 6， 示例 2: 輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 輸出: 2 解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身，
• 平衡二叉樹的基本概念 簡單介紹一下b+樹
• 多叉樹的生成 給定一個陣列【[a,b]、[c,b]、[e,a]、[h,a]、[k,h]】，陣列前一個代表子節點、后一個代表父節點，生成一顆多叉樹，回傳根節點
• 按照Z字形分層遍歷二叉樹，要求bug free，并且構造二叉樹進行測驗
• 二叉樹的右視圖，
• 寫一個二叉樹的深度遍歷
• 二叉樹翻轉
• 二叉樹的s型遍歷，層序遍歷的變種，簡單，不過要寫測驗用例，等于還要寫一個陣列轉二叉樹的函式
• 一顆非平衡二叉樹，如何最快的方式找到距離最遠的兩個葉子節點，
• 給一個二叉樹和一個目標值，找到和等于這個值的所有路徑
• B和B+樹，B+樹的搜索次數、為什么不用二叉樹，
• 紅黑樹最差旋轉幾次
• 給定一棵二叉樹，找到兩個節點的最近公共父節點(LCA)， 最近公共祖先是兩個節點的公共的祖先節點且具有最大深度， 假設給出的兩個節點都在樹中存在，
• 層次遍歷二叉樹，回傳一個二維陣列，每行表示一層
• 不用迭代方法計算樹的高度；
• 假設一棵二叉樹的后序遍歷序列為DFGGEBHICA,中序遍歷序列為：DBFEGAHCI,則前序遍歷序列為？
• 多叉樹的第n層 層次遍歷 2.遞回太深會怎樣？答堆疊溢位，為什么會堆疊溢位？python函式中的臨時變數存在哪？那很深的時候，用回圈會怎樣呢？為什么不會堆疊溢位？
• 給定一個二叉樹，依次列印出每一行
• 前序遍歷 中序遍歷 后序遍歷 知道那些可以恢復二叉樹，只知道前序和后序可以嗎？
• 有N個節點的滿二叉樹的高度

其他

• 哈希表，對哈希表的細節要求很高，比如哈希表的沖突檢測、哈希函式常用實作、演算法復雜度；比如百度二面就讓我寫一個哈希表插入元素演算法，元素型別是任意型別，
• 找出兩個有序陣列中的重復項，分析時間和空間復雜度，然后就是不斷優化優化優化，， 要是陣列長度非常大會出現什么情況？
• 倆執行緒分別持續列印奇數和偶數，實作倆執行緒的交替列印（從小到大）
• 給定一個經過編碼的字串，回傳它解碼后的字串， 編碼規則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次，注意 k 保證為正整數， 你可以認為輸入字串總是有效的；輸入字串中沒有額外的空格，且輸入的方括號總是符合格式要求的， 此外，你可以認為原始資料不包含數字，所有的數字只表示重復的次數 k ，例如不會出現像 3a 或 2[4] 的輸入， 示例: s = "3[a]2[bc]", 回傳 "aaabcbc". s = "3[a2[c]]", 回傳 "accaccacc". s = "2[abc]3[cd]ef", 回傳 "abcabccdcdcdef".
• leetcode213 你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，這個地方所有的房屋都圍成一圈，這意味著第一個房屋和最后一個房屋是緊挨著的，同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警， 給定一個代表每個房屋存放金額的非負整數陣列，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額， 示例 1: 輸入: [2,3,2] 輸出: 3 解釋: 你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的， 示例 2: 輸入: [1,2,3,1] 輸出: 4 解釋: 你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）， 偷竊到的最高金額 = 1 + 3 = 4 ，
• 有15個瓶子，其中最多有一瓶有毒，現在有四只老鼠，喝了有毒的水之后，第二天就會死，如何在第二天就可以判斷出哪個瓶子有毒
• 看你簡歷提到了raft演算法，講下raft演算法的基本流程？raft演算法里面如果出現腦裂怎么處理？有沒有了解過paxos和zookeeper的zab演算法，他們之前有啥區別？
• 根據身高重建佇列 假設有打亂順序的一群人站成一個佇列， 每個人由一個整數對(h, k)表示，其中h是這個人的身高，k是排在這個人前面且身高大于或等于h的人數， 撰寫一個演算法來重建這個佇列， 注意： 總人數少于1100人， 示例 輸入: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 輸出: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
• 一個二維陣列，每一列的數字從左往右增大，每一行從上往下增大，求一個指定的數字在這個陣列中的位置
• 給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先， 百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），” 例如，輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節點 2 和節點 8 的最近公共祖先是 6， 示例 2: 輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 輸出: 2 解釋: 節點 2 和節點 4 的最近公共祖先是 2, 因為根據定義最近公共祖先節點可以為節點本身，
• 股票買賣的一道題 給定一個整數陣列，其中第 i 個元素代表了第 i 天的股票價格 ， 設計一個演算法計算出最大利潤，在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）， 賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)， 示例: 輸入: [1,2,3,0,2] 輸出: 3 解釋: 對應的交易狀態為: [買入, 賣出, 冷凍期, 買入, 賣出]
• 給你一個 n * m 的二維整數陣列，數字都是大于等于0，現在要你對陣列做一種操作，對于所有0，將0所在的行和列全部變為0，要求使用盡量少的空間和時間，
• 給你一個整數陣列，陣列中的元素定義一種距離 d[i] 為將陣列排序后，該元素移動的距離，現在給你一個K陣列，即陣列中所有元素的距離d <= k，對這個K陣列排序，希望盡量小的時間復雜度，
• 輸入一個不含相同整數的整數集合，輸出所有子集 輸入：[1,2,3] 輸出：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 有三十瓶水，十個桶，每個桶能放0-10瓶水，有多少種方案
• 給定一個字串和一個整數 k，你需要對從字串開頭算起的每個 2k 個字符的前k個字符進行反轉，如果剩余少于 k 個字符，則將剩余的所有全部反轉，如果有小于 2k 但大于或等于 k 個字符，則反轉前 k 個字符，并將剩余的字符保持原樣， 示例: 輸入: s = "abcdefg", k = 2 輸出: "bacdfeg" 要求: （1）該字串只包含小寫的英文字母， （ 2）給定字串的長度和 k 在 [1, 10000]范圍內，
• 翻轉字串，反轉句子等，
• 判斷一串字串里括號的最大有效長度，用動態規劃實作
• 給一個字串，找出連續相同的字符，如果有兩個以上相同的，取ASCII碼小的，
• 給一個字串，洗掉最大連續相同的字串并回傳
• 有一組未排序的整形陣列，你設計一個演算法，對陣列的元素兩兩配對，然后輸出最大的絕對值差和最小的絕對值差的"對數"
• m*n二維陣列整體有序，查找value
• 回傳一個數字陣列的排序值，比如資料[6,2,5,0]的回傳是[4,2,3,1]；
• 一個正數陣列，長度為N，且陣列元素<N，統計每個正數出現的次數，要求時間復雜度O(n)，空間復雜度O(1)；
• 實作一個fibonacci函式，輸入數字n，輸出fibonacci數列的第n項數字，并給該函式加入快取功能，
• 100G文本找某個單詞出現的頻率
• 是否連接紅黑樹 ?
• 是否了解資料結構的“堆”
• 斐波拉契數列非遞回實作
• 演算法n的階乘末尾0的個數
• 我一個檔案,有45億個阿拉伯數字,如何進行去重啊?如何找出最大的那個數啊?
• 寫一個fibnaccio的相關例子
• 輸入兩個字串str1 str2和整數n，要求兩個數以n進制相加，然后輸出字串str3
• 就是二位陣列如何進行螺旋輸出 然后第二道的演算法題是如何從25匹馬中通過賽馬的形式找到最快的3匹，每次最多只能5匹馬參賽，問最少需要賽幾次？答案是7次，我思路對了，不過我把次數給弄錯了，多了2次沒必要的比賽，
• 6個元素1.2.3.4.5.6的順序進堆疊，請問下列哪個不是合法的出堆疊序列？ a:345261 b:436521 c:245316 d:124653 e:543612
• 圖的最短路徑問題
• 演算法題（爬樓梯，問一個人爬樓梯，每次只能爬一個臺階或兩個臺階，問有N個臺階，總共能有多少種爬法）；
• 實作一個random(m,n)方法，回傳m到n的亂數
• 64只球隊找到最強的，找前二強的，前k強的
• 就是m*n的矩形從左上面到右下面的路徑有多少條
• 求N內的所有素數
• 判斷字串是否是一個數字
• 當一個文本檔案中有200萬行資料，如何在在每一行的尾部追加一個字符；
• 求一個字串中最長不重復子串的長度
• 三個有符號的整型（long）數a, b, c，怎么判斷a+b > c?實作并且設計測驗用例（在main函式中呼叫，列印結果） （考慮同號越界問題）
• 給一個字串和一個k，要求找到不超過k個不同字符的最長子串的長度
• 10進制轉16進制（緊張了，有點費時間，嘖嘖嘖）
• f(0)=0;f(1)=1; f(n)=f(n-1)+f(n-2) 求f（n）
• 有主字串A，子字串B，在A中查找B

歡迎搜索關注本人與朋友共同開發的微信面經小程式【大廠面試助手】和公眾號【微瞰技術】

標籤：其他

上一篇：阿里巴巴開發手冊強制使用SLF4J作為門面擔當的秘密，我搞清楚了

下一篇：IT人必知，互聯網主流商業模式