首页 > (答案2)字节跳动算法题+智力题+场景题100题
头像
星尘coding
编辑于 2020-05-18 20:13
+ 关注

(答案2)字节跳动算法题+智力题+场景题100题

接上贴:

这是第二个答案贴,包括剩下的算法题,所有的场景题和智力题。很多题目楼主难以给出准确答案,只是给出了个人理解和从网络搜集到的思路,能力一般水平有限,难免有错误和遗漏,欢迎各位大佬指正。
有一些题目楼主的确不会,放在了文章最后,希望有思路的牛友们可以分享一下,谢谢大家。
(别光收藏,顺手点个赞呀,亲!)给您笔芯了。

其他

  • 单例模式,手写双重检验单例模式 懒汉式,DCL(8)
饿汉式:
public class Singleton{
    private static Singleton singleton = new Singleton();
    private Singleton(){}
    public static Singleton getSingleton(){
        return singleton;
    }
}

懒汉式(线程不安全):
public class Singleton{
    private static Singleton singleton = null;
    private Singleton(){}
    public static Singleton getSingleton(){
        if(singleton == null){
            singleton = new Singleton();
        }
        return singleton;
    }
}
双重校验单例模式(DCL):
public class Singleton{
    private volatile static Singleton singleton;
    private Singleton(){}
    public static Singleton getSingleton(){
        if(singleton == null){
            //类对象加锁
            synchronized (Singleton.class) {
                if(singleton == null){
                    singleton = new Singleton();
                }
            }
        }
        return singleton;
    }
}

  • 写一个函数,求平方根,函数参数为目标数字和精度,测试案例 fn(4.1,0.001) fn(501.1,0.001) fn(0.045,0.001)
有多种数学方法来实现,这里给出最简单的二分法的实现。
二分法:n为数字,e为精度
//float型是8位有效数字,占4个字节,double双精度类型,是17位有效数字,占8个字节
public static float fn(float n, float e){
    float x = 0;
    if (n > 0 && e > 0){
        float low = 0;
        float high = n;
        while (low < high){
            float mid = (low + high)/2;
            if (mid * mid < n - e){
                low = mid;
            }else if(mid * mid > n + e){
                high = mid;
            }else {
                x = mid;
                break;
            }
        }
    }
    return x;
}
  • 给定一个 0-4随机数生成器 如何生成0-6随机数
这个题的难点在于如何保证数字出现的概率都是相等
0-6通过对7取余可以得到,那么就想办法凑对7取余的场景。
public class Frequency {
    public static int rand7(){
        while(true){
            int num=5*rand5()+rand5();//0-24
            if(num<21)
                return num % 7;
        }
    }
}

//变形:如果用0-6随机生成器生成0-9随机数
public class Frequency {
    public static int rand10(){
        while(true){
            int num=7*rand7()+rand7();
            if(num<41)
            //排除41-48,因为他们不能生成9,会造成各个数字出现的概率不同
                return num % 10;
        }
    }
}
  • LeetCode 59题 螺旋矩阵II(同类:螺旋打印矩阵)
时间复杂度O(n^2)
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int num = 1;

        int up = 0;
        int right = n - 1;
        int down = n - 1;
        int left = 0;
        while(num <= n*n){
            for(int col = left; col <= right; col++){
                nums[up][col] = num;
                num++;
            }
            up++;
            for(int row = up; row <= down;row++){
                nums[row][right] = num;
                num++;
            }
            right--;
            for(int col = right; col >= left; col--){
                nums[down][col] = num;
                num++;
            }
            down--;
            for(int row = down;row >= up;row--){
                nums[row][left] = num;
                num++;
            }
            left++;
        }
        return nums;
    }
}
  • 翻转字符串中的单词 leetcode151原题 并且只能用O(1) extra space
因为Java语言中String是不可变的,修改String底层会复制成新的字符串,所以无法达到O(1)的空间复杂度。
将原字符串用" "分割存入Stirng[ ]数组,然后逆序遍历数组,将各个字符串拼接成起来。
class Solution {
    public String reverseWords(String s) {
        String emptyStr = " ";
        String[] splits = s.trim().split(emptyStr);
        StringBuilder sb=new StringBuilder();
        //为了后面处理方法统一,先拼接上最后一个单词
        sb.append(splits[splits.length-1]);
        for(int i=splits.length-2;i>=0;i--){
            if (!splits[i].isEmpty()) {
                sb.append(emptyStr);
                sb.append(splits[i]);
            }
        }
        return sb.toString();
    }
}
  • 最长不含重复字符的子字符串(剑指offer48题)
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

双指针+哈希表 时间复杂度O(N) 空间复杂度O(1):字符的 ASCII 码范围为 0 ~ 127 ,
哈希表 dicdic 最多使用 O(128) = O(1)大小的额外空间。
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

  • 加油站(LeetCode134)
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int sumTank = 0;//总油量
        int curTank = 0;//当前油箱内的油量
        int startStation = 0;
        for(int i = 0; i < n;i++){
            sumTank += gas[i] - cost[i];
            curTank += gas[i] - cost[i];
            if(curTank < 0){
                startStation = i + 1;
                curTank = 0;
            }
        }
        return sumTank >= 0 ? startStation : -1;
    }
}
  • 剑指offer62:圆圈剩下的数字(约瑟夫环问题)

  • 合并区间 (LeetCode56题)
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

  • [1,2,3,4,5,6,7,8,9] 输出 [64,36,16,4] 逆序输出偶数的平方
public class Solution {
    public ArrayList findpow(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = nums.length - 1; i > 0; i--) {
            if ((nums[i] & 1) == 0)
                list.add(nums[i] * nums[i]);
        }
        return list;
    }
}
  • 算法:中文数字转阿拉伯数字,字符串处理问题
中文数字格式:一万三千五百四十一
阿拉伯数字格式:13541
中文数字中要分单位数字分别处理,可以用两个数组分别保存中文数字和中文单位,每次循环扫描给的中文数字,去匹配对应的数字。中文数字数字可以用数组下标对应数字。
public class Solution{
   static char[] cnArr = {'零','一', '二', '三', '四', '五', '六', '七', '八', '九'};
   static char[] chArr = {'十', '百', '千', '万', '亿'};
public static int chineseNumToArabicNum(String chineseNum) {
    int result = 0;
    int temp = 1;//存放一个单位的数字如:十万
    int count = 0;//判断是否有表示单位的文字
    for (int i = 0; i < chineseNum.length(); i++) {
        boolean b = true;//判断是否是单位
        char c = chineseNum.charAt(i);
        for (int j = 0; j < cnArr.length; j++) {//非单位,即数字
            if (c == cnArr[j]) {
                if (count != 0) {//添加下一个单位之前,先把上一个单位值添加到结果中
                    result += temp;
                    temp = 1;
                    count = 0;
                }
                // 下标+1,就是对应的值
                temp = j;
                b = false;
                break;
            }
        }
        if (b) {//单位{'十','百','千','万','亿'}
            for (int j = 0; j < chArr.length; j++) {
                if (c == chArr[j]) {
                    switch (j) {
                        case 0:
                            temp *= 10;
                            break;
                        case 1:
                            temp *= 100;
                            break;
                        case 2:
                            temp *= 1000;
                            break;
                        case 3:
                            temp *= 10000;
                            break;
                        case 4:
                            temp *= 100000000;
                            break;
                        default:
                            break;
                    }
                    count++;
                }
            }
        }
        if (i == chineseNum.length() - 1) {//遍历到最后一个字符
            result += temp;
        }
    }
    return result;
}
}
  • 三个线程循环打印ABC
本题有多种方法实现,如wait,notify,synchronized等,这里给出基于Lock的实现
//使用Lock
public class ABCPrint{
    private static int state = 0;
    public static void main(String[] args) {
        final Lock lock = new ReentrantLock();

        Thread A = new Thread(new Runnable() { @Override public void run() {
                while (state <= 30) {
                    lock.lock();

                    try {
                        if (state % 3 == 0) {
                            System.out.print("A");
                            state++;
                        }
                    } finally {
                        lock.unlock();

                    }
                }
            }
        });

        Thread B = new Thread(new Runnable() { @Override public void run() {
                while (state <= 30) {
                    lock.lock();

                    try {
                        if (state % 3 == 1) {
                            System.out.print("B");
                            state++;
                        }
                    } finally {
                        lock.unlock();

                    }
                }
            }
        });

        Thread C = new Thread(new Runnable() { @Override public void run() {
                while (state <= 30) {
                    lock.lock();
                    try {
                        if (state % 3 == 2) {
                            System.out.println("C");
                            state++;
                        }
                    } finally {
                        lock.unlock();

                    }
                }
            }
        });
        A.start();
        B.start();
        C.start();
    }
}
  • 以下代码题输出什么?(巨坑,输出100,从泛型+向上转型+map+equals原理上想)
Map<Short, String> map = new HashMap<>(); 
for(short i = 0; i <100; i++) {
     map.put(i, String.valueOf(i));
     map.remove(i-1);
}
System.out.println(map.size());
map的key和value是Short和String,都是包装类,short型的i与Integer类型的1进行加减运算时,short会向上转型成为Integer(泛型只允许自动向上转型,不允许自动向下转型),在Integer的equals方法中,Short Instanceof Integer会返回false,所以每次都无法匹配成功,也就不能移除成功。可以将i-1强转成short,这样可以移除成功,但是向下强转可能会出现数据位丢失的问题。

智力题

  • 一硬币,一面向上概率0.7,一面0.3,如何公平?(4)
抛两次,正反A胜,反正B胜。

  • 概率:两个人轮流抛硬币,先抛到正面的赢,问先抛的人赢的概率(2)
2/3
每一轮抛硬币,A先抛赢得概率是1/2,B后抛赢得概率是(1/2)*(1/2)= 1/4。那么每一轮A赢得概率都是B赢得概率的2倍,总概率为1,所以A赢的概率是2/3。

  • 两根香,一根烧完1小时,如何测量15分钟
开始时一根香两头点着,一根香只点一头,两头点着的香烧完说明过去了半小时,这时将只点了一头的香另一头也点着,从这时开始到烧完就是15分钟。

  • 智力题,海盗分金币。
从后往前想,如果只剩两个人了会怎么样,如果只剩三个?
这个过程比较复杂,这里给出两篇讲解比较详细的博客。

  • 思考题:64匹马,8个跑道,选跑最快的4匹马需要比赛多少次。
(锦标赛排序算法) sum = 11
第一步:首先每8匹马跑一次,总共需要8次,假设结果中A1>A2>A3>......,B1>B2>B3>....等。 sum=8;
第二步:这8组中的第一名拉出来跑一次,那么这次最快的是总的第一名,假设是A1,同时假设B1>C1>D1。这时还要角逐2,3,4名,那这一轮中的第五到第八组都可以直接舍弃,因为他们所有的马一定进不了前4名。sum=9。
第三步:从A组中选A2,A3,A4,B组中B1,B2,B3,C组中C1,C2,D组中D1,这些才有资格角逐2,3,4名。这时需要再比赛两次。 sum=11。(但是如果第10轮选择A4不上场,如果A3获得了第4名,那么A4就不需要比赛了,这样sum=10)。

  • 坐标系中有一个球桌,四个角坐标:
(0,0), (0,4), (2,4), (2,0)
一颗球在(1,1),请问从哪些角度可以射入洞内(可无限次碰撞)?

解答:
一般想法是将球镜像对称,但这道题是把洞镜像对称
将这个桌面在这个平面无限延展,可类比成无限张球桌紧密放置
那么每一个和球洞的连线都是合法路径

  • 概率:54张扑克牌,平均分成3份,大小王在一份的概率
首先大王一定会在某一份中,然后要计算这一份中还要包含小王的概率。去掉大王还剩53张牌,这一份还可以分17张牌,那么每次分到小王的概率是1/53,所以总概率是17/53。
规范算法:

场景题
  • 场景题:让你设计一个微信发红包的api,你会怎么设计,不能有人领到的红包里面没钱,红包数值精确到分。
传入参数有总钱数,分的份数,随机分还是等分。先判断钱数能不能分那么多份,这个直接用总钱数>=0.01*份数判断就可以了。然后根据分发策略,选择随机还是等分,随机的话就给 1到总钱数-(总份数-1)*0.01 的随机数(总钱数以分为单位),等分的话直接除判断能不能除开,有余数就将余数加到最后一份里面。

  • 场景题:需求:谁关注了我,我关注了谁,谁与我互相关注。表该如何设计,索引怎么建。查询语句怎么写
粉丝关注表使用四列,主键id,userId,fansId,是否互相关注。用两行数据来保存互相的关注关系,这样查询起来更方便,用空间换时间。
主键有主键索引,剩下的字段不适合建索引,因为字段重复太多。

  • 场景题,分布式多个机器生成id,如何保证不重复?
1.snowflake方案
snowflake是Twitter开源的分布式ID生成算法,结果是一个long型的ID。其核心思想是:使用41bit作为毫秒数,10bit作为机器的ID(5个bit是数据中心,5个bit的机器ID),12bit作为毫秒内的流水号(意味着每个节点在每毫秒可以产生 4096 个 ID),最后还有一个符号位,永远是0。
优点
1.毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。
2.不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。
3.可以根据自身业务特性分配bit位,非常灵活。
缺点
强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。
2.用Redis生成ID:
因为Redis是单线程的,也可以用来生成全局唯一ID。可以用Redis的原子操作INCR和INCRBY来实现。
此外,可以使用Redis集群来获取更高的吞吐量。假如一个集群中有5台Redis,可以初始化每台Redis的值分别是1,2,3,4,5,步长都是5,各Redis生成的ID如下:
A:1,6,11,16
B:2,7,12,17
C:3,8,13,18
D:4,9,14,19
E:5,10,15,20
这种方式是负载到哪台机器提前定好,未来很难做修改。3~5台服务器基本能够满足需求,都可以获得不同的ID,但步长和初始值一定需要事先确定,使用Redis集群也可以解决单点故障问题。
另外,比较适合使用Redis来生成每天从0开始的流水号,如订单号=日期+当日自增长号。可以每天在Redis中生成一个Key,使用INCR进行累加。
优点:
1)不依赖于数据库,灵活方便,且性能优于数据库。
2)数字ID天然排序,对分页或需要排序的结果很有帮助。
缺点:
1)如果系统中没有Redis,需要引入新的组件,增加系统复杂度。
2)需要编码和配置的工作量较大。
  • LRU算法知道吗,怎么实现的?
LRU算法:最近最少使用算法,常用于进程调度,缓存淘汰,内存页面置换等场景。
使用LinkedHashMap可以实现,相对于HashMap,增加了双向链表,用于记录节点之间的先后顺序。LinkedHashMap的构造函数提供了一个参数accessOrder,这个参数可以指定链表是按照插入顺序排队还是按照访问顺序排队。参数为true时,就是按照访问顺序(插入,查询)排队,每次访问后这个节点就会被放到链表头,而长时间不被访问的节点逐渐就到了列表尾部,当需要淘汰时,就将链表尾部的节点抛弃。

  • 数据库连接池怎么设计?
需要考虑的问题:
  1. 限制连接池中最多、可以容纳的连接数目,避免过度消耗系统资源。
  2. 当客户请求连接,而连接池中所有连接都已被占用时,该如何处理呢?一种方式是让客户一直等待,直到有空闲连接,另一种方式是为客户分配一个新的临时连接。
  3. 当客户不再使用连接,需要把连接重新放回连接池。
  4. 连接池中允许处于空闲状态的连接的最大项目。假定允许的最长空闲时间为十分钟,并且允许空闲状态的连接最大数目为5,
那么当连接池中有n个(n>5)连接处于空闲状态的时间超过十分钟时,就应该把n-5个连接关闭,并且从连接池中删除,这样才能更有效的利用系统资源。

  • 扫码登录是如何实现的?

  • B+树和红黑树
红黑树和一般的平衡二叉树,增、删、改、查的过程和效率、时间复杂度

大数据类场景题
  • 1亿个正整数,范围是0-42亿。求出现次数是2的数字,空间复杂度
使用位图bitMap。位图是以bit位为单位进行数据存储,这样每个字节8个位就可以存储8个数字,普通的一个int占4个字节,32位,用了位图之后可以将空间节省32倍。
开一个42亿大小的位图,将这一亿个数字存进数字大小对应的位置,一个bit每存进去一个数字,就将value+1,比如第一次存8,就将索引为8的位置的value置为1,第二次就置为2,存完之后搜索value为2的key是多少。
32位机器最大能表示的数字是42亿9千多万。
42亿bit /(8*1024*1024) = 500MB

  • 算法:有一个IP地址库,假设有几十万条ip,如何判断某个ip地址是否在这个库中?
思路一:分治法,将ip地址根据前三位分成256份,然后看这个ip地址对应的网段,只比对这个网段里面是否有这个ip,当然还可以继续分下去,根据数据量来决定分成多少份。
思路二:位图,将每一条ip对应位图中的一个位,2^32次方(42亿多)个数据只需要512M空间。可以实现O(1)的时间搜索,O(n)的时间存储。

  • 场景题:2g内存,要求一个10g文件的中位数

  • 带权重抽奖:100万个人,100个奖品,每个人中奖倍率不同,抽完为止,每人最多中奖一次。
(面经中给的解释先用古典概型写了一个:基础中奖几率*中奖倍率,但是这样做对前面的人有优势,于是重新思考后用几何概型写了一个,List表示线段,List中存对应人的id。)

  • 情景题,一个5T的文件,里面全是id,1-10^9 ,如何计算不同id的个数?
哈希到不同的文件,再逐个文件内找不同的。



楼主目前无法给出答案的题目
算法题:
  • 代码题,版本数字比较,比如"1.10.0"版本比"1.8.1"版本新,不允许使用split等函数
  • 算法:输入List<String>,删除当中形如”1_”的,返回原来的List (2)

  • 算法:1,4,5拼数字,最少数字(给了一个提示,n=5*i+4*j+k,result=min(i+j+k))

  • 有一个会议室里有一个录音麦,有n个人抢着说话,麦只能录到声音最大的人,给定每个人开始的说话时间s,结束的说话时间t,说话音量vol,然后求这个麦最后录到的声音序列。
数据范围:n 2e5。 s,t,vol 1e9

两个做法:
离散化后用线段树区间更新
扫描线+用set做优先队列维护最大音量
第一反应是第一个,但是面试官不让离散化
  • 穿墙术,三维的bfs,类似走迷宫
  • 算法题,一辆公交车,有m站,最多坐n人,输入一路上票的信息(即上车下车站),输出会不会超载
我说了下开数组算前缀和的思路,面试官把m改为很大,不让直接开数组,接着我说了下用map离散化一下解决,就让我写了下map里存的结构 map<int,pair<int,int>> ,其余代码面试官也觉得没啥难度就过了.


  • 算法题,全排列

  • leetcode 688 棋盘算概率问题

  • 算法题,一个形如 123456789101112……的字符串,输入一个n(很大很大),输出字符串第n个字符
我的做法是先预处理出不同位数数字占的位数,之后找到n对应的数字位数、数字、数位。写完没跑过去,面试官指出我数错个数了(我算的时候,2位数算了100个,3位数1000个……),不过查找函数逻辑没问题,就下一题了
(2位数 90 个,三位数900个,四位数90000个)



场景题:
  • 场景题:redis设置高并发抢单一的东西,如何避免高并发对一个键进行访问?

  • 场景设计:系统中有几万个任务需要在各自的特定时刻触发执行,怎么做?

  • 场景题:游戏里,一个玩家可能吃到很多种debuff,每个debuff有一定持续时间。给你一个定时器,怎么设计数据结构,来维护玩家的debuff状态?

  • 一个很复杂的场景,大概是微博用户有个关注列表,以及知道各种大V的动态,设计数据结构啥的,到最后在用户这边显示一个更新微博列表这样。最后扯了一堆围绕红黑树的实现

全部评论

(29) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐