算法题一：无序数组的中位数 (快排思想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(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优化等；

③ 熟悉大规模分布式系统架构设计，熟悉CAP、Quorum、Consistent Hashing等原理和算法。

绩效考核与晋升

字节跳动内部的绩效考核一共有八级，从低到高为F、I、M-、M、M+、E、E+、O，并会进行强制分布，对应年终奖和月薪百分比的涨薪。M就有涨薪机会。晋升面试也是主要还是看绩效考核。

每年两次考核，一般在三月和九月。考核方式借鉴了google的OKR+360模式：头条是双月OKR，可以在lark 上看到所有人的OKR，知道大家在做什么，你对齐的大目标是什么，支持对齐你的人在做什么。