HHR的小站
享受代码带来的快乐吧
首页

下午收到了腾讯北极光工作室的面试邀请,晚上进行面试。

面试记录

  • 面试老师介绍了自己的团队,然后?问我 玩不玩游戏
    不玩,我更喜欢鼓捣些有趣的小玩意。(然后带跑了节奏)最近在研究GitHub的GitHub Actions
  • 这应该属于一个CI/CP的工具。你觉得它的技术难点主要在哪呢?
    我觉得这个工具其实挺方便的,对于我而言可能阅读文档相对比较难。
  • 你们说一下它的技术原理吗?
    我最近在做一个Spring Boot的项目。在提交的时候,它会先使用gradlew bootjar进行打包,然后使用SFTP协议传输到我的服务器,最后使用SSH协议执行jar包,完成部署。
  • 揣测一下它是怎么实现提交时构建版本的?
    我猜测是一个触发器的机制,在提交版本时进行处理。
  • 如果让你来做,怎么让Git来调用我的编译服务?
    这是GitHub提供的服务。GitHub会启动一个docker容器来进行构建操作。
  • 编译时的环境部署信息怎么输入?
    使用GitHub的secret,将TOKENRSA的私钥上传。在yml配置文件中进行调用。
  • 考虑极端情况,让我做这样一个系统,在用户量比较大的时候,怎么来分配资源?
    在收到请求时,挑选一台空闲的服务器进行运行。
  • 我说的是资源管理的问题,假设我只能起100个docker容器,但是有一千个人要用,该怎么分配?
    做一个FIFO的队列,先来先服务。
  • 那如果我要对资源进行限制,不能让一个人占用过多的资源呢?
    给每个人分配时间片,时间片用完了换人。
  • 如果时间片当前不在用,不是就浪费了嘛?
    大家轮流用,不存在时间片空闲的情况。
  • 如果人数是动态变化的呢?
    如果有新的请求,就把它放到最空闲的服务器。因为时间随机分布,可以让每台服务器尽量忙碌。
  • 在资源不够时该怎么协调资源,该怎么做呢?
    那就将I/O密集型和CPU密集型的任务并在一起做,这样可以吗?
  • 怎么讲这些方法组合起来呢?
    那就在收到请求时将他们放到一个FIFO的队列里,如果有服务器是空闲的,就从队列取出一个服务,为其分配时间片。在时间片用完之后,将其移入队尾。
  • 每个任务都要分配相同的时间片吗?
    我觉得是的,如果想要做到公平,就要给每个任务分配相同的时间片,大概十分钟那样。
  • 你是计算机专业的对嘛?你们学过操作系统吗?
    学过
  • 操作系统里进程和线程调度的算法有哪些?
    FIFO,最短时间,最高响应比,时间片轮转
  • 那你想一下这个case,在操作系统里怎么实现是最合理的?
    我觉得是一个带优先级的优先队列,让优先级高的进程先进性工作
  • 那怎么进行调度呢?
    比如一个优先级高的进程进入,就让其抢占原有的进程。
  • 那原有的进程呢?
    将其挂起?那应该让之前的进程先做完,然后让新的服务执行。
  • 我注意到你提到了使用.NET CORE完成了一个井字棋游戏,可以介绍一下吗?
    这是一个前后端分离的桌面应用,后端用的是ASP .Net Core
  • 前端呢?
    用的是WinForm
  • 这个游戏的规则怎么样?
    在一个三乘三的棋盘上,黑白双方轮流下棋,如果一方获得了连续的三颗棋子,就获得胜利。
  • 那你有遇到过什么技术难点吗?
    开始时我使用了同步的网络请求,这样在请求的时候会导致主线程被挂起,让用户认为游戏卡死了。后来我使用了异步的网络请求,提高了用户体验。
  • 会延迟多久
    大概两三百毫秒
  • 这个服务器在哪?
    在上海的阿里云,但是我的数据库不在上海,所以延迟会比较久。
  • 为什么ping命令30-40毫秒,为什么操作延迟会到200到300毫秒?
    首先是TCP握手和SSL握手消耗的时间,然后要连接数据库。
  • 那你觉得可以怎么优化呢?
    使用连接池加速数据库连接,使用WebSocket进行网络请求
  • 怎么获取对方下棋的结果?
    每隔一段时间向服务器请求,进行轮询。现在我应该会用WebSocket来进行实现。
  • 可以实现多少人同时对战
    我觉得瓶颈应该在数据库的并发上
  • 如果需要改呢?
    讲棋局信息存储在内存中。
  • 如果服务器down了呢?
    游戏数据会丢失。那局游戏就没了。
  • 连接还在吗?
    session会作废,连接应该也没了
  • 为什么会作废呢?
    原理不是非常了解。
  • 那怎么实现重连呢?
    使用token机制,重新验证登录状态。
  • 那怎么实现数据的保存呢?
    我认为存在前端是不合理的,因为前端是不安全的,所以应该存放在后端。我觉得可以使用类似于radis的服务。
  • 那你有用过redis吗?
    了解过,但是没在项目里用过。
  • 我对你项目的情况大概了解了。你现在倾向于读研还是工作呢?
    倾向于工作,因为非专业课不占优势。
  • 你现在学了那些专业课
    计算机网络,数据库,组成原理和操作系统
  • 那TCP和UDP有什么区别
    TCP面向连接,URP面向无连接。TCP提供可靠传输,UDP不能提供可靠传输。TCP的延迟比UDP大。
  • 为什么TCP的延迟大?
    需要发送ACK报文,UDP不需要。
  • TCP发包需要每发一个包,就接受一个ACK吗?
    不一定,可以数个包进行一次ACK。
  • TCP是怎么实现这样的呢?
    是一个滑动窗口的机制。
  • 如果报文丢失呢?
    接收方就不会发送ACK报文,发送方会进行超时重传。
  • 那后面没有丢失的报文呢?
    会被丢弃,等待重传。
  • 那为什么会被丢到呢?
    (不是很清楚呢,有点忘了)
  • 栈内存和堆内存的区别
    new 方法动态生成的对象会被放到堆里,使用类似 int a=5这样生成的变量会被放到栈里。
  • 那class可以被放到栈里吗?
    如果static的可能可以?不了解。
  • JVM实现了GC的机制,那GC什么时候会失效呢?
    循环依赖?
  • 那怎么检查和解除呢?
    类似于操作系统里解除死锁的算法?
  • 那对象怎么检查呢?
    查引用的列表,找有没有他自己?
  • 那这是深度优先还是广度优先呢?
    我觉得是深度优先。我对这块了解不深
  • 那你有什么想问的呢?
    你们是一个做游戏的部门,那后端应该是基于C++的,而我现在的开发大多基于Java,那应该怎么学习C++的后端开发比较好呢?
  • 我觉得应该从项目入手,做项目来进行学习。
  • 你还有什么想问的吗?
    没有了
  • 辛苦了
    你也辛苦了

面试总结

待完善

什么是 GitHub Actions

GitHub Actions是GitHub提供的一个持续集成,持续部署工具。您可以直接在 GitHub 仓库中通过 GitHub Actions 创建自定义持续集成 (CI) 和持续部署 (CD) 工作流程。

如何使用 GitHub Actions

在git项目中开启Actions功能

打开GitHub项目的主页,找到这个按钮,点击,即可进入Actions页面。
屏幕截图 2021-02-24 194455.jpg
选择一个合适的配置文件,将其加入你的项目中,即完成了持续集成的配置工作。

配置文件的样例

这是一个配置文件的样例。使用该配置文件,可以用于gradle构建的Spring Boot项目。在项目进行更新时,自动生成Spring Bootjar文件,并发布release

# This workflow will build a Java project with Gradle
# For more information see: https://help.github.com/actions/language-and-framework-guides/building-and-testing-java-with-gradle

name: Java CI with Gradle

on:
  push:
    branches: [ master ]
  pull_request:
    branches: [ master ]

jobs:
  build:

    runs-on: ubuntu-latest

    steps:
      - uses: actions/checkout@v2
      - name: Set up JDK 11
        uses: actions/setup-java@v1
        with:
          java-version: 11
      - name: Modify gradle config file
        run: |
          sed -e '/maven.aliyun.com/d' build.gradle >> build.gradle.1
          sed -e '/maven.aliyun.com/d' settings.gradle >> settings.gradle.1
          mv build.gradle.1 build.gradle
          mv settings.gradle.1 settings.gradle
      - name: Grant execute permission for gradlew
        run: chmod +x gradlew
      - name: Build with Gradle
        run: ./gradlew bootjar
      - name: Get Release Info
        id: get_info
        run: |
          VERSION=`grep version build.gradle | grep '=' | grep -Eo \'.*\' | grep -Eo '[a-z|A-Z|0-9|.|_]*'`
          NAME=`grep "rootProject.name" settings.gradle | grep -Eo \'.*\' | grep -Eo '[a-z|A-Z|0-9|.|_]*'`
          FILE_PATH="./build/libs/"$NAME"-"$VERSION".jar"
          FILE_NAME=$NAME"-"$VERSION".jar"
          VERSION=$VERSION.`git rev-parse --short HEAD`
          echo ::set-output name=file_path::$FILE_PATH
          echo ::set-output name=file_name::$FILE_NAME
          echo ::set-output name=version::$VERSION
      - name: Create Release
        id: create_release
        uses: actions/create-release@master
        env:
          GITHUB_TOKEN: ${{secrets.TOKEN}}
        with:
          tag_name: Release_${{steps.get_info.outputs.version}}
          release_name: Release of version ${{steps.get_info.outputs.version}}
          draft: false # 是否是草稿
          prerelease: false # 是否是预发布
      - name: Upload Release Asset
        id: upload-release-asset
        uses: actions/upload-release-asset@master
        env:
          GITHUB_TOKEN: ${{secrets.TOKEN}}
        with:
          upload_url: ${{steps.create_release.outputs.upload_url}}
          asset_path: ${{steps.get_info.outputs.file_path}}
          asset_name: ${{steps.get_info.outputs.file_name}}
          asset_content_type: application/java-archive
      - name: rename file
        run: |
          mv ./build/libs/${{steps.get_info.outputs.file_name}} ./build/libs/${{steps.get_info.outputs.file_name}}.`git rev-parse --short HEAD`
      - name: deploy file
        uses: wlixcc/SFTP-Deploy-Action@v1.0
        with:
          username: 'server_runner'
          server: 'huhaorui.com'
          ssh_private_key: ${{ secrets.SSH_PRIVATE_KEY }}
          local_path: './build/libs/*'
          remote_path: '/www/wwwroot/fridge.huhaorui.com'
          args: '-o ConnectTimeout=5'
      - name: restart server
        run: |
          mkdir ~/.ssh
          ssh-keyscan huhaorui.com >> ~/.ssh/known_hosts
          echo "${{ secrets.SSH_PRIVATE_KEY }}" >> ~/.ssh/id_rsa
          chmod 600 ~/.ssh/id_rsa
          ssh 'server_runner@huhaorui.com' "kill -9 \`ps -x | grep fridge_server | sed -n '1p' | grep -Eo [0-9]{4}[0-9]+\`"
          ssh 'server_runner@huhaorui.com' "nohup java -jar /www/wwwroot/fridge.huhaorui.com/${{steps.get_info.outputs.file_name}}.`git rev-parse --short HEAD` >/dev/null 2>&1 &"

如何写一个配置文件

通过研究上面的配置,可以发现,我们可以在配置中使用已有的action,如actions/upload-release-asset@master,也可以自己编写bash脚本,用于实现特定的功能。
更多使用方法可以参阅GitHub提供的文档

什么是Stream API

关于stream,IBM对其有一个概括。链接

Stream 作为 Java 8 的一大亮点,它与 java.io 包里的 InputStream 和 OutputStream 是完全不同的概念。它也不同于 StAX 对 XML 解析的 Stream,也不是 Amazon Kinesis 对大数据实时处理的 Stream。Java 8 中的 Stream 是对集合(Collection)对象功能的增强,它专注于对集合对象进行各种非常便利、高效的聚合操作(aggregate operation),或者大批量数据操作 (bulk data operation)。Stream API 借助于同样新出现的 Lambda 表达式,极大的提高编程效率和程序可读性。同时它提供串行和并行两种模式进行汇聚操作,并发模式能够充分利用多核处理器的优势,使用 fork/join 并行方式来拆分任务和加速处理过程。通常编写并行代码很难而且容易出错, 但使用 Stream API 无需编写一行多线程的代码,就可以很方便地写出高性能的并发程序。所以说,Java 8 中首次出现的 java.util.stream 是一个函数式语言+多核时代综合影响的产物。

怎么使用stream API

获得一个stream对象

对于实现了List接口的对象,获取stream非常简单。

        List<Integer> nums = new ArrayList<>();
        Stream<Integer> stream = nums.stream();

调用Liststream()方法,即可得到一个Stream对象。
而对于int[]一类的数组,获取stream也不是很困难。

        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        IntStream stream = Arrays.stream(nums);

由于Java的基本数据类型导致的问题,此处的stream不再为Stream<T>类型(毕竟int并不是对象),而是一个所谓的IntStream,不过这并不影响其的使用。要获得Stream<Integer>类型的stream,我们只需要将数组更换为Integer[]类型。

        Integer[] nums = {1, 2, 3, 4, 5, 6, 7};
        Stream<Integer> stream = Arrays.stream(nums);

stream有什么用?

获得了一个stream对象之后,我们就可以开始利用它。

求数组长度

最简单的,调用stream.count()方法,即可获得数组的长度。

        Integer[] nums = {1, 2, 3, 4, 5, 6, 7};
        Stream<Integer> stream = Arrays.stream(nums);
        long size = Arrays.stream(nums).count();
        //上下两行代码等价
        size = nums.length;

有人可能会说,就这?这只是stream最简单的使用,接着来些好玩的例子。

统计不及格学生的学号

        Map<String, Integer> score = new HashMap<>();
        score.put("201806061100", 95);
        score.put("201806061101", 75);
        score.put("201806061102", 53);
        score.put("201806061103", 54);
        score.put("201806061104", 77);
        score.keySet().stream()
                .filter(key -> score.get(key) < 60)
                .forEach(key -> System.out.println(key));

该例子使用了stream的filter方法,其中使用了一个lambda表达式,传入一个key,返回key所对应的value是否小于60。这个filter会返回所有成绩低于60分的学生的学号。
接下来,使用了forEach方法,继续利用lambda表达式,将这些学号依次输出。

将stream转回List<T>

        List<String> blame = score.keySet().stream()
                .filter(key -> score.get(key) < 60)
                .collect(Collectors.toList());

使用collect方法,指定转换方式为toList,即可将其转回List<String>

对值进行额外的处理

        score.keySet().stream()
                .filter(key -> score.get(key) < 60)
                .map(key -> key.substring(8))
                .forEach(key->System.out.println(key));

在这里,我们使用了一个新方法 map,可以将其解释为映射.map(key -> key.substring(8)),会返回一个新的stream对象,其中的每一项都执行了 .substring(8)的操作。

排序

        Map<String, Integer> score = new HashMap<>();
        score.put("201806061100", 95);
        score.put("201806061101", 75);
        score.put("201806061102", 53);
        score.put("201806061103", 54);
        score.put("201806061104", 77);
        score.keySet().stream()
                .sorted((k1, k2) -> score.get(k2) - score.get(k1))
                .forEach(key -> System.out.println(key));

使用 sorted方法,并在其中实现一个比较器,即可完成按照成绩从高到低的顺序进行排序。

更多有趣的方法

有关stream的方法还有很多,读者可自行进入Java的文档进行了解,本文不再进行介绍。

引言

一直以来,Java有一个为人所不满的缺点:啰嗦。有些简单的东西,可能需要撰写更多代码才能完成。
幸好,Java为我们推出了很多新功能,来解决其中的问题。本文主要想介绍Java8的lambda表达式。

lambda

之前的版本

先来看这么一串代码

        String[] name = {"Mike", "Tom", "Jerry", "Potty", "Moggy"};
        Arrays.sort(name, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });

有五个小朋友,他们有不同的名字。我们希望按照字母的顺序为其排序。按照Java7的写法,我们需要完成一个Comparator接口,并实现其中的compare方法。以完成排序。

使用lambda的写法

使用IDEA的朋友们可能发现,之前的代码被标为了黄色。IDEA会将你的代码改成这样

Arrays.sort(name, (o1, o2) -> o1.compareTo(o2));

原本的compare函数消失了,变成了 (o1, o2) -> o1.compareTo(o2)。这是怎么回事呢?

什么是lambda

其实这就是lambda表达式,Lambda 允许把函数作为一个方法的参数(函数作为参数传递进方法中)。使用 Lambda 表达式可以使代码变的更加简洁紧凑。
(o1, o2) -> o1.compareTo(o2)意为,传入了o1,o2两个参数,将 o1.compareTo(o2) 的值作为返回值。简单的语法就完成了原本五六行代码的工作量。

还能更简单吗?

能!如果使用Java8的另外一个特性,方法引用,撰写的代码量会更少。有关方法引用的使用,我会在之后的文章里进行介绍。

lambda的更多示例

启动子线程

new Thread(() -> System.out.println("Hello World")).start();

等价于

        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println("Hello World");
            }
        }).start();

显而易见,使用lambda语句,可以使代码更为简洁。

使用滑动窗口算法解决一些问题

在Leetcode上做到了一道题

题目

给你两个长度相同的字符串,st

s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。

解答

删去其中繁杂的题干,题意大概是从一个自然数串中,找出最长的和小于 maxCost 的串。此题可以用滑动窗口的思路解决。

滑动窗口

定义一个左指针 leftPtr,一个右指针 rightPtr ,开始时将两个指针都置于最左边。右侧指针每次向右移动一格,判断左指针所处的位置是否符合题意。如果不符合,将其向右移动,直到符合题意为止。存储最大的符合题意的距离,即为答案。

简单说来,可以理解成右指针拉着左指针向右动,它们之间用一根线(maxCost)相连。如果线足够长(rightPtr - leftPtr <= maxCost),左指针就不会动,否则它也会跟着向右移。

代码

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int length = s.length();
        int[] cost = new int[length];
        for (int i = 0; i < length; i++) {
            cost[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int rightPtr = 0, leftPtr = 0, max = 0, nowCost = 0;
        while (rightPtr < length) {
            nowCost += cost[rightPtr];
            while (nowCost > maxCost) {
                nowCost -= cost[leftPtr];
                leftPtr++;
            }
            if (rightPtr - leftPtr + 1 > max) {
                max = rightPtr - leftPtr + 1;
            }
            rightPtr++;
        }
        return max;
    }
}