面试篇：快手数据研发面试题

伊泽瑞尔

发布于 2022-06-01 08:37:00

9430

发布于 2022-06-01 08:37:00

1、SQL题

用户登陆记录表login，表中数据如下：

user_id,login_date
101,2021-01-01
101,2021-01-02
102,2021-01-03
101,2021-01-04
102,2021-01-05
102,2021-01-06
102,2021-01-07
102,2021-01-08

表中一行数据代表该用户在该日期登陆过，求每一位用户连续登陆天数最大分别是多少天。解题思路：

需要造一列数据，这个列日期连续的行值相同。

1）使用用户id分组，日期排序，增加升序排序列。

2）由于按照日期排序，如果列连续，使用日期减去排序列序号，则连续列的值相同，非连续列值不相同，这样可以达到造列的目的。

3）按照用户分组求连续次数最大值

select user_id,
       max(continue_days) as maxday
  from (
        select user_id,
               date_sub(login_date, rn) as date_group,
               count(1) as continue_days
          from (
                select user_id,
                       login_date,
                       row_number()over(partition by user_id order by login_date) rn
                  from login
               ) a
         group by user_id,
                  date_sub(login_date, rn)
       ) b
 group by user_id

2、JAVA题

写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

思路：

LeetCode第74题，将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。

代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。


class Solution {
    public boolean search(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

3、JAVA题

层序遍历二叉树。

示例：二叉树：[3,9,18,null,null,15,7],

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路：

LeetCode的102题，将二叉树按层输出，借助队列实现。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树