首页 > 面试复盘|8.25~一点资讯~算法工程师~一二三面经
头像
helloRachel
编辑于 2021-08-25 20:58
+ 关注

面试复盘|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道

单选:

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

多选:

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

算法:

  1. 尽可能多的参加一些活动,给定多个活动的开始、结束时间(以字符串的形式给出),最后输出最多能参加的活动数。(活动时间可能重叠;同一时间只能参加一个活动)

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

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);
    }
}
  1. 最小路径和。需要从左上角第一个位置达到右下角最后一个位置,只能向下、右移动,采用动态规划的思路,建立一个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道论述题

一面

  1. 自我介绍:算法研究、开发工作

  2. 机器学习基础:ML如何分类(监督,无监督;分类,回归);朴素贝叶斯、逻辑回归、降维的方法

  3. 项目的推荐算法(爬虫、CF思路)、预测算法(GCN、扩张卷积、门控机制、transformer等)

  4. 手撕一:不使用除法、取余操作,计算出商(只需要输出整数部分)

    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哈哈哈没想出来~~】

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

    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] + " ");
           }
       }
    }
  6. 提问

二面

  1. 自我介绍

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

  3. 给一个场景,推荐的多样性问题,即给定一千条文章信息,每一个信息都包含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!");
        }
    }

三面:

面试30min,自我介绍,聊项目,项目的算法中抽出来问了问,GCN Transformer等,大概20min左右,之后聊了聊公司的业务等等。

许愿!多多学习!冲!

更多模拟面试

全部评论

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

相关热帖

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

热门推荐