面试复盘|8.25~一点资讯~算法工程师~一二三面经

一点资讯

岗位要求

1、熟悉Java及==SpringMvc、SpringBoot、Mybatis==等相关框架;

2、掌握常用数据结构和算法，具备==多线程，网络编程==等Java开发能力，了解==重构及设计模式==相关知识；

3、熟悉==数据库(mysql)、缓存(redis、codis)、消息中间件(RabbitMq、kafka)==的开发和使用，具备解决高并发，高可用等问题的能力和经验；

4、了解==微服务==体系，具备一定的应用服务分析与拆分能力，有良好、规范的编码习惯；沟通能力好；

5、精通一种C++/java编程语言，会python更佳；

6、具有==扎实的机器学习背景==，对于神经网络的基本常见模型有理解，在NLP，图像，推荐，广告或者其他的方向有实际场景的建模经验更佳；

7、乐观积极，能承受一定的压力，具有很好的自我驱动精神。

笔试：2021-07-30 19：00

基础题涉及到编程语言、操作系统、计算机网络等。单选、多选、编程题2道、问答题1道

单选：

甲乙双方通过TCP连接，甲收到 ACK为300，那么来自哪里？末字节号299的报文段
红黑树有n个节点，查询一个key的时间复杂度为：
C++中，定义类对象 Person p1和Person *p2 = new Person()的区别，前者存储在stack中，会自动调用析构函数释放资源；后者存储在heap中，需要显式调用delete方法来回收对象。

多选：

Unix进程通信
交换机，数据链路层，虚拟局域网
排序算法中的稳定算法
线程、进程
单例中的线程安全

算法：

尽可能多的参加一些活动，给定多个活动的开始、结束时间（以字符串的形式给出），最后输出最多能参加的活动数。（活动时间可能重叠；同一时间只能参加一个活动）

思路：先用二维数组存储；然后解析字符串；按照开始时间排序；采用贪心算法，选择最早结束的活动。

package yidianzixun;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 要求：尽可能多的活动
 * 限制：同一时间参加一个；不能中途推出；时间限制0.~23.59
 * 输入：
 * [["10:00","12:00"],["03:00","11:30"],["11:30","14:00"]]
 */
public class Solution {

    public static int countMaxActivity(ArrayList<ArrayList<String>> timeSchedule) {
        // 0 解析字符串
        ArrayList<ArrayList<Double>> times = new ArrayList<>();
        for (int i = 0; i < timeSchedule.size(); i++) {
            double start = StrParseInt(timeSchedule.get(i).get(0));
            double end = StrParseInt(timeSchedule.get(i).get(1));
            ArrayList<Double> time = new ArrayList<>();
            time.add(start);
            time.add(end);
            times.add(time);
        }
        System.out.println(times);
        // 1 排序
        times.sort(new Comparator<ArrayList<Double>>() {
            @Override
            public int compare(ArrayList<Double> o1, ArrayList<Double> o2) {
                return (int) (o1.get(0) - o2.get(0));
            }
        });
        System.out.println(times);
        // 2 以贪心的思路，将最早结束的活动加入到集合中
        int count = 1, n = times.size(), j = 0; // 记录最大活动数，活动总数
        boolean[] a = new boolean[n]; // 记录是否添加
        for (int i = 1; i < n; i++) {
            if (times.get(i).get(0) >= times.get(j).get(1)) { // 第i个活动开始时间 超过 j活动的结束时间
                a[i] = true;
                j = i;
                count++;
            } else {
                a[i] = false;
            }
        }
        return count;
    }

    public static double StrParseInt(String str) {
        String hour = str.split(":")[0];
        String mini = str.split(":")[1];
        double h = 0.0, m = 0.0;
        for (char c : hour.toCharArray()) {
            h = ((int) c - 48) + h * 10;
        }
        for (char c : mini.toCharArray()) {
            m = ((int) c - 48) + m * 10;
        }
        return h + m / 60;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<String>> timeList = new ArrayList<>();
        ArrayList<String> activity1 = new ArrayList<>();
        activity1.add("10:00");
        activity1.add("12:00");
        timeList.add(activity1);
        ArrayList<String> activity2 = new ArrayList<>();
        activity2.add("03:00");
        activity2.add("11:30");
        timeList.add(activity2);
        ArrayList<String> activity3 = new ArrayList<>();
        activity3.add("11:30");
        activity3.add("14:00");
        timeList.add(activity3);
        System.out.println(timeList);
        int res = countMaxActivity(timeList);
        System.out.println(res);
    }
}

最小路径和。需要从左上角第一个位置达到右下角最后一个位置，只能向下、右移动，采用动态规划的思路，建立一个dp矩阵，每一个值表示从起点到当前点的最小路径和；初始化首行首列（首行节点的值只可能从左传来；首列只可能从上传来），计算其余节点的值，为当前节点值，加上左侧或者上侧最小的值，最后终点位置的值就是最小路径和。

package yidianzixun;

/**
 * 最小路径和
 * <p>
 * [[1,3,1],[1,5,1],[4,2,1]]
 */
public class Solution2 {
    public static int findMin(int[][] mapArray) {
        int m = mapArray.length, n = mapArray[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = mapArray[0][0];
        // 初始化首行
        for (int i = 1; i < n; i++) {
            dp[0][i] = mapArray[0][i] + dp[0][i - 1];
        }
        // 初始化首列
        for (int i = 1; i < m; i++) {
            dp[i][0] = mapArray[i][0] + dp[i - 1][0];
        }
//        printArray(dp);
        // DP：dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + mapArray[i][j]
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + mapArray[i][j];
            }
        }
//        printArray(dp);
        return dp[m - 1][n - 1];
    }

    public static void printArray(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j] + ",");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] array = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        int res = findMin(array);
        System.out.println(res);
    }
}

简答：

广告点击率预测模型，特征选取、模型选取等方面共4道论述题

一面

自我介绍：算法研究、开发工作
机器学习基础：ML如何分类（监督，无监督；分类，回归）；朴素贝叶斯、逻辑回归、降维的方法
项目的推荐算法（爬虫、CF思路）、预测算法（GCN、扩张卷积、门控机制、transformer等）

手撕一：不使用除法、取余操作，计算出商（只需要输出整数部分）

public class Divide {
    public static void main(String[] args) {
        int a = 5;
        int b = 2;
        int cnt = 0;
        while (a > b) {
            a -= b;
            cnt++;
        }
        System.out.println(cnt);
    }
}

以上使用减法，时间复杂度为O(a//b)，可否使用位运算进行优化？【用了15min哈哈哈没想出来~~】

手撕二：两数相加，给定一个一维数组和目标值，输出数组中的索引位置

import java.util.HashMap;

public class Add {
   public static int[] func(int[] nums, int target) {
       HashMap<Integer, Integer> hashmap = new HashMap<>();

       for (int i = 0; i < nums.length; i++) {
           int j = hashmap.getOrDefault(target - nums[i], -1);
           if (j == -1) {
               hashmap.put(nums[i], i);
           } else
               return new int[]{i, j};
       }
       return new int[]{};
   }

   public static void main(String[] args) {
       int[] res = func(new int[]{2, 5, 8, 1, 9}, 9);
       for (int i = 0; i < res.length; i++) {
           System.out.print(res[i] + " ");
       }
   }
}

提问

二面

自我介绍
是否了解ML,DL?说一下LR和SVM的区别？说一下DNN的过程。为什么DNN中间激活函数一般不用sigmoid？

给一个场景，推荐的多样性问题，即给定一千条文章信息，每一个信息都包含ID、score、label三个属性，给定的信息是按照score从高到低的顺序排好序的，每篇文章对应一个label。当我们需要给用户推荐时，每推荐10篇文章中，重复的label不能超过2个，那么，请将这些文章重新排序。要保证相邻10篇文章的label数最多是2，且分数高的在前。

我的思路：每10篇检索一次，用hashmap对10篇的label进行计数，

class ShowMeBug {
    // paper的结构：{id, score, label}
    public static ArrayList<ArrayList<Integer>> paper;

    public static void rank(paper) {
        // 1 遍历所有的文章
        // 2 每10篇文章建立一个map，用于为label计数，当该label>2时，将此时的文章挪到后面
        for (int i = 0; i < paper.size() - 10; i++) {
            // 存储lable和数量
            HashMap<Integer, Integer> hashmap = new HashMap<>();
            for (int j = i; j < i + 10; j++) {
                // 如果当前label不存在
                int label = paper.get(i).get(2);
                if (hashmap.getOrDefault(label, -1) == -1) {
                    hashmap.put(label, 1);
                } else if (hashmap.get(label) < 2) { // label存在，但是次数少于2
                    hashmap.put(label, hashmap.get(label) + 1);
                } else { // label 次数超过2，需要将当前元素后移
                    ArrayList<Integer> temp = paper.get(i); // 需要挪动的文章
                    paper.remove(temp);
                    paper.add(i + 10, temp);
                }
            }
        }

    }

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}