演算法題一：無序陣列的中位數 (快排思想O(N) 時間複雜度)

演算法的核心是使用最小堆（heap），你想到了嗎？

首先將陣列的前（n+1）／2個元素建立一個最小堆。

然後，對於下一個元素，和堆頂的元素比較，如果小於等於，丟棄之，接著看下一個元素。如果大於，則用該元素取代堆頂，再調整堆，接著看下一個元素。重複這個步驟，直到陣列為空。

當陣列都遍歷完了，那麼，堆頂的元素即是中位數。

可以看出，長度為（n＋1）／2的最小堆是解決方案的精華之處。

package com.lightsword.leetcodeproblemsimport org.junit.jupiter.api.Testimport java.util.*/** * 1.演算法題一：無序陣列的中位數 (快排思想O(N) 時間複雜度) * 中位數定義: 如果陣列長度是奇數，最中間就是位置為（n+1）／2的那個元素。如果是偶數，就是位置為n/2和位置為n/2+1的兩個元素的和除以2的結果. * 例如，[2,3,4] 的中位數是 3[2,3] 的中位數是 (2 + 3) / 2 = 2.5 */class ArrayMidNum {    @Test    fun main() {        val m1 = median(intArrayOf(2, 3, 4))        val m2 = median(intArrayOf(2, 3))        println("m1=$m1")        println("m2=$m2")       //m1=3.0       //m2=2.5    }    fun median(array: IntArray): Double {        val N = array.size        val heapSize = N / 2 + 1        // PriorityQueue透過二叉小頂堆實現，可以用一棵完全二叉樹表示（任意一個非葉子節點的權值，都不大於其左右子節點的權值），        // 也就意味著可以透過陣列來作為PriorityQueue的底層實現。        // 首先將陣列的前（n+1）／2個元素建立一個最小堆。        val heap = PriorityQueue<Int>(heapSize)        for (i in 0..heapSize - 1) {            heap.add(array[i])        }        // 然後，對於下一個元素 array[i] ，和堆頂的元素 heap.peek() 比較，如果 array[i] <= heap.peek() ，丟棄之，接著看下一個元素。        // 如果 array[i] > heap.peek()  ，則用該元素取代堆頂，再調整堆，接著看下一個元素。重複這個步驟，直到陣列為空。        for (i in heapSize..N - 1) {            if (array[i] > heap.peek()) {                heap.poll()                heap.add(array[i])            }        }        // 當陣列都遍歷完了，那麼，堆頂的元素即是中位數。        // 如果陣列長度是奇數，最中間就是位置為（n+1）／2的那個元素。如果是偶數，就是位置為n/2 和位置為 n/2+1 的兩個元素的和除以2的結果        if (N % 2 == 1) {            return (heap.peek()).toDouble()        } else {            // poll()方法獲取並刪除隊首元素            val a = heap.poll()            val b = heap.peek()            return (a + b) / 2.0        }        // 可以看出，長度為（n＋1）／2的最小堆是解決方案的精華之處。    }}

參考資料：

https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/java-priorityqueuejie-fa-by-caixiaoxin/

https://www.cnblogs.com/shizhh/p/5746151.html

一般大廠的面試題主要就是這6類：

（1）多執行緒、集合和Java基礎

（2）spring框架、mybatis框架

（3）MySQL資料庫

（4）高併發、分散式

（5）JVM調優、快取最佳化、資料庫調優

（6）演算法

關於位元組跳動崗位層級，績效考核晉升職級研發序列

不少人對位元組跳動技術崗的體系結構和技術要求設定不太清楚，想去面試心裡沒底，下面簡單介紹一下位元組跳動技術崗要求體系，並給大家分享一份最新入職位元組跳動的同事總結出的完整面試題！

位元組跳動的職級研發序列一共5級，各細分2級，共10 級：

1-1

1-2

2-1

2-2

3-1

3-2

4-1

4-2

5-1

5-2

不同序列間月薪base差異較大，技術base整體偏高。比如2-1月薪會在20k+，2-2的package會在60w-100w左右（算上期權，大概會佔30%左右）。T2-2級別的薪資約40k，500股票/每年。

位元組跳動對技術崗的要求

1、3年以上開發經驗；

2、精通Java，理解io、泛型、多執行緒、集合等Java基礎使用和實現原理；

3、熟悉Spring、SpringBoot等框架，理解JVM的實現機制及效能調優;

4、掌握MySQL使用，熟悉資料庫效能最佳化；

5、熟悉主流Key-Value儲存系統，能夠進行系統性能調優；

6、掌握Linux 作業系統；熟練使用一種指令碼語言，Shell或Python；

7、擁有高併發、分散式系統經驗優先；

8、有業務系統中臺化經驗者優先。

有以下經驗者優先：

① 熟練掌握Golang/Python並能靈活運用；

② 具有大規模分散式系統的調優經驗，如JVM調優、SQL調優、快取最佳化、RPC最佳化等；

績效考核與晉升

位元組跳動內部的績效考核一共有八級，從低到高為F、I、M-、M、M+、E、E+、O，並會進行強制分佈，對應年終獎和月薪百分比的漲薪。M就有漲薪機會。晉升面試也是主要還是看績效考核。