笔试题

1. 单链表，打印倒数第k个节点

思路：两个指针遍历单链表，一前一后相隔k个单位

/**
 * 打印链表的倒数第k个元素
 * 使用两个指针的方式
 */
public class PrintLastK {

    static class Node {
        public final int value;
        public final Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(int value) {
            this(value, null);
        }
    }

    /**
     * 获取链表的倒数第k个元素(从0开始的)
     *
     * @param node
     * @param k
     * @return
     */
    public static int getLastNode(Node node, int k) {
        Node firstNode = node;
        Node secondNode = node;
        // 第一个指针先走k步
        for (int i = 0; i < k && firstNode.next != null; i++) {
            firstNode = firstNode.next;
        }
        // 两个指针一起往前走
        while (firstNode.next != null) {
            firstNode = firstNode.next;
            secondNode = secondNode.next;
        }
        return secondNode.value;
    }

    public static void main(String[] args) {
        Node node = null;
        for (int i = 0; i < 50; i++) {
            node = new Node(i, node);
        }
        for (int i = 0; i < 20; i++) {
            System.out.println("倒数第" + i + "个:" + getLastNode(node, i));
        }

    }

}

2. sql 题目
   有三张表
   表user

name	id
张三	1
李四	2
王二	3

表 subject

name	id
语文	1
数学	2
英语	3

表score

user_id	subject_id	score
1	2	81
1	3	55
1	3	76
2	2	89

仅用一条SQL语句，查询出至少参加过3门功课，且每门功课都大于80分的学生姓名。

思路就是user_id 分组，having 过滤，然后用left join 查出用户名

SELECT
    user.name AS user_name 
FROM
    score
    LEFT JOIN user ON score.id = user.id 
WHERE
    score > 80 
GROUP BY
    id 
HAVING
    COUNT( * ) >= 3;

3. 字符串类型的二进制数相加
   假设 String a="1011";String b="1001“,计算这个结果为"10100"

先给出一个使用系统api的示例

  /**
     * 二进制的字符串相加，等到二进制的字符串
     * 使用系统api实现的范本
     *
     * @param a
     * @param b
     * @return
     */
    public static String add2(String a, String b) {
        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
    }

按照要求不使用系统api的代码

思路：主要是二进制相加

   /**
     * 二进制的字符串相加，等到二进制的字符串
     *
     * @param a
     * @param b
     * @return
     */
    public static String add(String a, String b) {
        final char[] chars = new char[Math.max(a.length(), b.length())];
        boolean carryBit = false;// 是否进位
        for (int i = chars.length - 1; i >= 0; i--) {
            final int j = chars.length - 1 - i;
            int value = 0;
            // 获得对应位数上的值
            if (a.length() > j) {
                value += a.charAt(a.length() - 1 - j) - '0';
            }
            if (b.length() > j) {
                value += b.charAt(b.length() - 1 - j) - '0';
            }
            // 进位的话+1
            if (carryBit) {
                value += 1;
            }
            // 判断是否进位
            if (value > 1) {
                carryBit = true;
                chars[i] = (char) ('0' + Math.abs(value - 2));
            } else {
                carryBit = false;
                chars[i] = (char) ('0' + value);
            }
        }

        if (carryBit) {
            return "1" + new String(chars);
        } else {
            return new String(chars);
        }
    }
  public static void main(String[] args) {
        String a = "1011";
        String b = "1001";
        String result = add2(a, b);
        System.out.println(Integer.parseInt(a, 2) + " + " + Integer.parseInt(b, 2) + " = " + Integer.parseInt(result, 2));
        System.out.println(a + " + " + b + " = " + result);
        System.out.println(add(a, b));
        final Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            String s1 = Integer.toBinaryString(random.nextInt(100000));
            String s2 = Integer.toBinaryString(random.nextInt(100000));
            String v1 = add(s1, s2);
            String v2 = add2(s1, s2);
            if (!v1.equals(v2)) {
                throw new RuntimeException(s1 + " + " + s2 + " expect is " + v2 + " but is " + v1);
            }
        }
        System.out.println("测试通过");
    }

简答题:

• 内存泄漏
• 内存优化
• 卡顿优化
• oom处理
• JVM 内存模型
• 几种B树的区别
• 文件下载这块，容错的处理
  进程被杀，文件长度超出
• kotlin 相关
  • 泛型 in out 的使用场景
  • object 对象的 invoke 和init 的执行顺序
  • internal 的实现原理以及与java调用的反应
• sqlite
  • 锁
  • wal模式
  • 亲缘性类型
  • 索引类型
• contentProvider
  • UriMatcher 原理
    感觉百度的面试官还是挺不错，回答的不好，来年继续努力。
• 画UML类图
  *泛型通配符