秋招日记（4.24）腾讯笔试广联达面试字节笔试

腾讯笔试后端方向，20点到22点
广联达提前批15点30分面试
青训营笔试任选90分钟做就OK

今天😳又是被拷打的一天，话说广联达是个啥公司，有没有了解的说几句😍

广联达秋招提前批
一面 25min
自我介绍
项目追问
数据库索引
B+树的优点
如何快速判断一个二进制数是不是二的幂次方
有哪些排序在特定情况下达到O(n)
成绩排名
最近在读什么书
不准备读研吗？为什么？
反问环节
流程是怎样的，应该是两轮面试
提前批过了也是要尽快入职吗？会结合学生时间

感慨一句，太快了xdm实在是太快了

字节青训营
大坏特坏，字节青训营是Go的，而我是Java，咱也不懂架构，想着就做做编程题就行了，第一题很简单DFS直接秒了，第二题当场坐大牢😥

腾讯笔试

100 70 50 0 0

第四题有思路，但是不好调试，其实整体代码写出来了，但是应该有一些细节错误，这种链表题不方便构造测试用例，只能硬刚😓

第四题，给定一个ListNode 数组，数组中存储的是一个环形链表片段，比如环形链表为 1 -> 2 - > 3 -> 4 -> 1 ...

数组中为 1 - > 2 - > 3 , 2 -> 3, 3 - > 4 - > 1这样的片段，找到使得这个环形链表的字典值最小的分割点，进行分割

第四题，代码如下，不知道对不对，我自己搞了个测试用例能用，蹲个大佬点评一下

 public static ListNode solve (ListNode[] a) {
        //拼接
        ListNode cur = a[0];
        HashMap<Integer, ListNode> map = new HashMap<>();
        for(int i = 0; i < a.length; i++){
            cur = a[i];
            boolean flag = true;
            while(cur != null){
                if(flag && map.containsKey(cur.val)){
                    ListNode tmp = map.get(cur.val);
                    tmp.next = cur.next;
                    flag = false;
                    if(i == a.length - 1)break;
                }
                map.put(cur.val, cur);
                cur = cur.next;
            }
        }
        //连成环
        ListNode head = a[0];
        while(head.next != null){
            head = head.next;
        }
        head.next = a[0];
        //查找字典序最小的数
        int min =  Integer.MAX_VALUE;
        ListNode pre = cur, start = cur, point = null;
        cur = cur.next;
        while(cur.val != start.val){
            if(min > cur.val){
                point = pre;
                min = cur.val;
            }
            pre = cur;
            cur = cur.next;
        }
        //截断链表
        assert point != null;
        ListNode ans = point.next;
        point.next = null;
        return ans;
    }

第三题，其实是前缀和后缀和，套了个动态规划的壳子，只过了百分之五十，求指教哪里错了（刚刚又改了一下，不知道现在有没有问题）

Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        int[] dpA = new int[str.length() + 1];
        int[] dpB = new int[str.length() + 1];

        for(int i = 1; i < dpA.length; i++){
            if(str.charAt(i - 1) == '0'){
                dpA[i] = dpA[i-1] + i;
            }else{
                dpA[i] = dpA[i-1];
            }
        }

        for(int i = dpB.length - 2; i >= 0; i--){
            if(str.charAt(i) == '1'){
                dpB[i] = dpB[i+1] + i + 1;
            }else{
                dpB[i] = dpB[i+1];
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < dpA.length; i++){
            ans = Math.min(ans,Math.abs(dpA[i]-dpB[i]));
        }
        ans = Math.min(ans,Math.abs(dpB[0]));
        ans = Math.min(ans,Math.abs(dpA[dpA.length - 1]));
        System.out.println(ans);

第二题，当时超时了，现在简单优化如下

                int[] a = new int[]{1,2,3,4};
        int min =  Integer.MAX_VALUE;
        List<Integer> list = new ArrayList<>();
        List<Integer> nums = new LinkedList<>();
        for(int i = 1; i <= a.length; i++){
            if(i == 1 || !check(i)){
                list.add(i);
            }
            nums.add(a[i-1]);
        }
        while(nums.size() > 1){
            for (int index : list) {
                if (nums.size() > 1 && index - 1 < nums.size()) {
                    nums.set(index-1, -1);
                }
            }
            for(int i = nums.size() - 1; i >= 0; i--){
                if(nums.get(i) == -1){
                    nums.remove(i);
                }
            }
        }
        System.out.println(nums.get(0));

第一题

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] strs = new String[n];
        in.nextLine();
        for (int i = 0; i < n; i++) {
            strs[i] = in.nextLine();
        }
        int len = strs[0].length();
        int[] nums = new int[len];
        for (int i = 0; i < len; i++) {
            StringBuffer sb = new StringBuffer();
            int index = i;
            for (int j = 0; j < n; j++) {
                sb.append(strs[j].charAt(i));
            }
            int num = Integer.parseInt(sb.toString());
            nums[index] = num;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }

#找呀找呀找工作##腾讯#