最新字节跳动面试题与答案: 无序数组的中位数 (快排思想O(N) 时间复杂度)

一個會寫詩的程序員 · · 1106 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

最新字节跳动面试题与答案

1.算法题一:无序数组的中位数 (快排思想O(N) 时间复杂度)

package com.lightsword.leetcodeproblems

import org.junit.jupiter.api.Test
import 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的最小堆是解决方案的精华之处。
    }

}


2.算法题二:给一数组,让你找一对满足:i<j && a[i]<a[j] (O(N)时间复杂度0(1)空间复杂度)

3.算法题三: 给一数组,让你找一对满足:i<j<k && a[i]<a[j]<a[k] (O(N)时间复杂度 O(N)空间复杂度)

4.三次握手过程

5.为什么是3次,而不是2次或4次?

6.介绍下TCP

7.TCP是如何确保传输安全的?

8.TCP和UDP的区别

9.介绍下hashmap

10.数据库有了解吗,介绍下数据库的索引以及作用

11.数据库的存储引擎,介绍一下,以及其数据结构

12.数据库的事务

13.事务的特点

14.同步和互斥,锁

15.DNS 域名系统

16.HTTP和HTTPS的区别

17.HTTPS的SSL(TLS)协议

18.进程和线程的区别

19.进程通信方式

20.介绍共享内存通信方式

21.线程的通信方式

22.synchronized和volatile介绍

23.synchronized和volatile的区别和应用

24.说下java的GC算法

25.影响一个Http服务最大连接数的因素是什么

26.一台服务器如何辨认一个请求是谁发送的

27.如何进行Token认证

28.说一下cookie,为什么要有cookie,cookie中放什么,cookie与session的区别

29.Https是什么,建立连接的过程

30.算法题:给出一个n*n数字矩阵,寻找一条最长上升路径(数字越来越大),每个位置只能向上下左右四个位置移动

31.智力题:2n个人围成一圈,两两握手,形成n条线段,线段没有交点。 一共多少种握手方式?

32.说说你所知道的Java中线程安全的集合类

33.Java中有什么办法使对象在各线程中隔离

34.说一下ThreadLocal是什么,如何实现的

35.Redis为什么速度快,多路复用讲一下

36.项目中为什么用ES,ES在超大数据量下如何优化

37.操作系统的分页存储,地址转换

38.概率题:两人抛硬币,抛到正面的人获胜,问先抛的人获胜的概率

39.算法题:给定一个非空二叉树,返回其最大路径和。

40.项目流程,亮点

41.令牌桶算法怎么实现的

42.线程池是自己创建的吗?

43.线程池七大参数都是什么?

44.各个参数都是怎样设置的?

45.线程池核心线程数和最大线程数为什么要设置成这样?

46.线程状态?怎样转换的?

47.object类的方法有哪些?

48.实现线程同步的方式有哪些?

49.synchronized和reentrantlock的区别

50.MYSQL事务隔离级别及产生的问题

51.数据库的死锁问题

52.MySQL索引为什么用b+树?

53.7层网络模型

54.tcp和udp的区别

55.常用的Linux命令

56.算法题:反转链表第m到第n个节点

57.面向对象和面向过程

58.继承多态封装及其体现

59.算法题:去除有序数组中元素重复出现两次以上的数字并返回数组长度

60.代理模式 spring aop

61.模板方法模式

62.线程池池化技术

63.何时创建核心线程,何时创建最大线程

64.线程池拒绝策略

65.jmm

66.jvm内存区域

67.垃圾回收算法

68.Java异常体系

69.有没有自定义过异常

70.项目中的数据库表有哪些映射关系(一对一,一对多,多对多)

71.算法题:字符串数组的最长公共前缀

总结

所有的面试题目都不是一成不变的,特别是像字节跳动这种大厂,上面的面试真题只是给大家一个借鉴作用,最主要的是给自己增加知识的储备,有备无患。

上面这些面试题总结一下,主要就是这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,知道大家在做什么,你对齐的大目标是什么,支持对齐你的人在做什么。

360评估:每个人都可以评估别人同样也会被别人评估,无论是领导还是普通员工。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:一個會寫詩的程序員

查看原文:最新字节跳动面试题与答案: 无序数组的中位数 (快排思想O(N) 时间复杂度)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1106 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传