20220901bilibili后端基础架构方向笔试记录

20220901bilibili后端基础架构方向笔试记录

题型描述：

• 5道单选题
• 10道多选题
• 三道问答题
  • 第一道是说让你想办法存储1000亿条数据，每条数据包含一个url一个ip一个时间；然后支持两种查询，第一个是给一个任意时间段，返回一个url在该时间段的访问量；第二个是给一个任意时间段，返回一个ip在该时间段的总访问量
  • 第二道是说给一个多叉树，然后输入三个数，第一个是结点数量，第二个是边数，第三个是要找的结点，然后要你求找到这个节点的概率，需要提供算法
  • 第三道是说从一个无穷尽的流中选1000个关键字（比如百度引擎不断有人键入关键字传到服务器），然后问你如何保证在无穷尽的流中选出1000个关键字，并用统计学方法分析
• 一道算法：给你一个数，找这个数的所有因数的最小和

解法：

• 问答题只写了第一题，描述了一个类似如图的分布式系统

• 算法题 ac算法如下

  import java.util.*;
  class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2;i<n+1;++i){
            dp[i] = i;
        }
        for(int i = 2;i<dp.length;++i){
            for(int j = i/2;j>=1;--j){
                if(i%j==0){
                    dp[i] = Math.min(dp[i],j+dp[i/j]);
                }
            }
        }
        System.out.println(dp[dp.length-1]);
  
    }
  }

以上，问答题后面两题属于完全没思路，就乱写了/摊手，然后时间基本都用在了第一个问答题上