后端面试笔记(一)

/ 面试 / 没有评论 / 720浏览

以下是本人在以往的后端面试中遇到的一些题目的小整理,答案和分析仅供参考,未必正确,如果发现有错误的地方,欢迎指出。

1、有n个台阶,小明一次能跨i个台阶(如:3个台阶即是1或2或3个台阶),问小明有多少种上台阶的组合? 答: 当n为1时,1,共1; 当n为2时,1-1,2,共2; 当n为3时,1-1-1,1-2,2-1,3,共4; 当n为4时,1-1-1-1,1-1-2,1-2-1,1-3,2-1-1,2-2,3-1,4,共8; 当n为5时,1-1-1-1-1,1-1-1-2,1-1-2-1,1-1-3,1-2-1-1,1-2-2,1-3-1,1-4,2-1-1-1,2-1-2,2-2-1,2-3,3-1-1,3-2,4-1,5,共16; 从上可以看出,当n为4时,若第1个为1,后面的组合刚好就是n为3时(4-1=3)的组合,往前往后看都是这样,所以可以用递归法,StepCombination.java文件的代码如下:

import java.util.Scanner;

/**
 * 有n个台阶,小明一次能跨i个台阶(如:3个台阶即是1或2或3个台阶),问小明有多少种上台阶的组合
 */
public class StepCombination {
    static int m = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please input n:");
        int n = Integer.parseInt(scanner.next());
        scanner.close();
        combinate(n);
        System.out.println("m:" + m);
    }

    public static void combinate(int n) {
        for (int i = 1; i <= n; ++i) {
            if (n - i == 0) {
                ++m;
            } else {
                combinate(i);
            }
        }
    }
}

运行结果如下: 跨台阶组合问题运行结果

2、怎么从a表查出b表?又怎么从b表查出a表?数据如下:

 a表:
 name   subject    score
 张三    语文       70
 张三    数学       92
 张三    英语       95
 李四    语文       78
 李四    数学       85
 李四    英语       93
 b表:
 name    语文    数学    英语
 张三     70      92     95
 李四     78      85     93

答: 1)从a表查出b表:(mysql行转列)

select name, max(case subject when '语文' then score else 0 end) 语文, max(case subject when '数学' then score else 0 end) 数学, max(case subject when '英语' then score else 0 end) 英语 from a group by name;

运行结果: 从a表查出b表运行结果 分析:关键是利用case when then else end进行记录的筛选,case后面的subject表示条件变量,when表示把条件变量设为'语文',then表示取这时符合条件的记录中的score字段的值,else 0表示当when后设置的值不符合条件时取值为0,end作为结束的标识符。

注意:max函数比较的是每个组里的数据,这里的max函数比较的是在每个组的基础上再加上函数括号内的条件的数据,范围更小一点,所以比较的数据也包括0,如果改为min函数的话,查出的结果都会是0。

2)从b表查出a表:(mysql列转行)

select name, '语文' subject, chinese_score as score from b union select name, '数学' subject, math_score as score from b union select name, '英语' subject, english_score as score from b order by name;

运行结果: 从b表查出a表运行结果 分析:关键是利用union进行记录的纵向合并,最后再用order by以name排下序。

3、4个女人晚上过桥,她们都需要手电筒才能过桥,手电筒只能传递,女人1过桥需要1分钟,女人2过桥需要2分钟,女人3过桥需要5分钟,女人4过桥需要10分钟,过1次过桥最多2个女人,若2人一起过桥速度快的要迎合速度慢的,问怎么在17分钟内4个女人都过桥? 答: 女人1和女人2一起过桥,花费2分钟; 女人1回来,花费1分钟; 女人3和女人4一起过桥,花费10分钟; 女人2回来,花费2分钟; 女人1和女人2一起过桥,花费2分钟; 一共刚好就是17分钟。

4、用1条sql语句查出每门课程都大于79分的学生姓名,再用1条sql语句查出平均分大于80分的学生姓名,数据如下:

name  course  score
张三    语文      85
张三    数学      75
李四    语文      76
李四    数学      90
王五    语文      81
王五    数学      100
王五    英语      90
李四    英语      95

答: 1)查每门课程都大于79分的学生姓名:

select distinct name from grade where name not in (select distinct name from grade where score <= 79);

分析:先找出小于等于79分的学生姓名,然后再用not in找出不在这里面的学生姓名,要注意用distinct对名字去重。

或者:

select name from grade group by name having min(score) > 79;

分析:对表以学生姓名进行分组,再通过having对每组进行筛选,使用min函数找出每组的分数最小值,如果该组的分数最小值都大于79,那么就是每门课程都大于79。

运行结果: 每门课程都大于79分正确运行结果

以下写法是错误的:

 select name from grade where score > 79 group by name order by score desc;

分析:这里的where只能对整体结果进行筛选,后面的order by排序排的是分组后的整体结果,不是对每个组进行排序,而且用了group by,也就是每个组的数据都有了,但是每门课程都大于79分的学生不一定每个组都有,执行结果会是这样: 每门课程都大于79分错误运行结果

2)查平均分大于80分的学生姓名:

select name, avg(score) from grade group by name having avg(score) > 80;

运行结果: 平均分大于80分方法1运行结果 分析:通过姓名分组,用having找出平均分大于80分的组。

或者:

select name from (select count(*) count, sum(score) sum, name from grade group by name) as a where a.sum > 80 * count;

运行结果: 平均分大于80分方法2运行结果 分析:通过姓名分组找出每组的分数总和以及记录数,把此命名为表a,放到from后,再查这个表a,通过分数总和是否大于80乘以记录数,来判断平均分是否大于80分。

5、写1条sql语句找出各个部门中工资最高的员工,以下是表的结构:

表名:employee
id  name  salary  departmen_id
1   Joe   70000   1
2   Henry 80000   2
3   Sam   60000   2
4   Max   90000   1
5   Tommy 80000   2
表名:department
id  name
1   IT
2   Sales

要求结果如下:

  department  employee  salary
  Sales       Henry     80000
  IT          Max       90000
  Sales       Tommy     80000

答:

select dep.name as department, emp.name as employee, emp.salary from department dep, employee emp where emp.department_id = dep.id and emp.salary = (select max(salary) from employee e where e.department_id = dep.id);

或者用join on的方式合表:

select department.name as department, employee.name as employee, employee.salary as salary from employee join department on employee.department_id = department.id and employee.salary = (select max(salary) from employee e where e.department_id = employee.department_id);

或者把and改为where:

select department.name as department, employee.name as employee, employee.salary as salary from employee join department on employee.department_id = department.id where employee.salary = (select max(salary) from employee e where e.department_id = employee.department_id);

运行结果如下: 找部门工资最高员工正确运行结果 分析:先department表和employee表合表,再根据工资条件挑选记录。在合表中根据工资挑选记录时,是逐条比较是否符合条件的,例如:当id=1时,合表中salary为70000,department_id为1,这时子查询的employee表就要寻找department_id为1的记录,找到是id为1和id为4的,然后因为max(salary)所以找出工资最大值为90000,而70000不等于90000,所以合表中id=1的记录不符合子查询条件。也可以这么理解,判断合表的salary是否等于一个数,但是这个数是个可变的数,对合表的每条记录来说可能是不同的。

以下写法是错误的:

select department.name as department, employee.name as employee, max(employee.salary) as salary from employee join department on employee.department_id = department.id group by employee.department_id;

运行结果会是: 找部门工资最高员工错误运行结果 分析:因为max(employee.salary)的取最大值只针对这一字段,不会影响到其他字段,前面的department和employee字段还是取group by分组后的第一条记录,但salary就取了分组后组内的最大值。那么首先得到的结果就是名字部门和薪水不对应的;其次只能显示部门只有一个薪资最高的情况,如果部门内有多个人薪资同时达到最高,就只显示第一个了。

6、订单表user_order结构和数据如下,请编写sql语句查出首次下单日期是2018年05月22号的用户数量,注意是首次下单。

id  user_id  product  price  create_date
1   234      坚果Pro2  1400   '2018-05-21'
2   234      锤子TNT   8888   '2018-05-22'
3   356      小米mix   2400   '2018-05-22'
4   357      硅胶娃娃  10400  '2018-05-23'
5   234      华为Mate  5999   '2018-05-20'
6   356      魅族Note  2000   '2018-05-24'
7   234      荣耀畅玩  1999   '2018-05-23'
8   789      三星Note8 7999   '2018-05-19'
9   456      三星Note7 6999   '2018-05-22'
10  123      Vivo柔光  3999   '2018-04-28'

答: 执行以下sql语句,

select * from user_order group by user_id having min(create_date) = '2018-05-22';

运行结果是: 查出首次下单是某天的分析过程

但是题目要求的是查出用户数量,所以正确的是以下sql语句,

select count(*) from (select * from user_order group by user_id having min(create_date) = '2018-05-22') as a;

运行结果是: 查出首次下单是某天的正确运行结果 分析:先通过user_id分组,然后通过having以及min函数找出每组的最小值,判断最小值是否为'2018-05-22'(因为若一个组的create_date最小值为'2018-05-22',那就是首次下单日期是2018年05月22号的用户),然后再把这个整体结果作为from后的临时查询表,最后用count(*)统计出数量。

以下写法是错误的:

select count(*) from user_order group by user_id having min(create_date) = '2018-05-22';

运行结果是: 查出首次下单是某天的错误运行结果 分析:因为这里查到的是分组数据,分组后只显示每组的第1条记录,但实际的记录数是可能多于显示的记录数的,看上面的运行结果,2表示的是第1个分组的记录数是2(356有两条记录),1表示的是第2个分组的记录数是1(456只有一条记录)。

7、写一个函数,输入参数有两个,一个是int数组nums,另一个是int类型target,其中nums中的数据不重复并且一定有两个项相加等于target。要求该函数返回nums中相加等于target两个项的下标。比如nums=[3,8,11,15,16],target=19,因为8+11=19,所以返回[1,2],分别代表8和11的下标。要求算法复杂度n,也就是不要两个for嵌套进行计算,建议先考虑存储结构再考虑实现。 答: 第一遍遍历:遍历数组nums,将(target-nums[i])和i作为key和value,存入hash表,遍历时间复杂度为O(n)。 第二遍遍历:遍历数组nums,每次都查询在hash表中是否有和当前数相同的key,每次查询时间复杂度为O(1),遍历时间复杂度为O(n)。 所以,总的时间复杂度是O(2n),也就是O(n)。 为何hash表的containsKey方法的时间复杂度为O(1),可以参考下这篇文章,https://www.jianshu.com/p/06e2be54d4d6。 本题代码TwoSum.java如下:

import java.util.HashMap;
import java.util.Map;

/**
 * 在不重复数组中寻找两个数,使得两数等于一个目标值,返回两数的数组下标
 */
class TwoSum {
    public static void main(String[] args) {
        int[] nums = { 3, 8, 11, 15, 16 };
        int[] target_index_nums = new TwoSum().getIndexs(nums, 26);
        for (int i = 0; i < target_index_nums.length; ++i) {
            System.out.println(target_index_nums[i]);
        }
    }

    public int[] getIndexs(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        // 第一遍遍历:将(target-nums[i])和i作为key和value,存入hash表,遍历时间复杂度为O(n)
        for (int i = 0; i < nums.length; ++i) {
            map.put(target - nums[i], i);
        }
        // 保存结果下标的数组
        int[] target_index_nums = new int[2];
        // 第二遍遍历:查询在Hash表中是否有和当前数相同的key,每次查询时间复杂度为O(1),遍历时间复杂度为O(n)
        for (int i = 0; i< nums.length; ++i) {
            // 有可能出现两数相同,比如数组中有8,目标数为16,那么target-nums[i]=8,那返回的下标就会是两个都是8的下标
            // 用i != map.get(nums[i])可以避免这种情况
            if (map.containsKey(nums[i]) && i != map.get(nums[i])) {
                int j = map.get(nums[i]);
                // 确保返回的结果下标数组中小的下标在前面,大的下标在后面
                if (i < j) {
                    target_index_nums[0] = i;
                    target_index_nums[1] = j;
                } else {
                    target_index_nums[0] = j;
                    target_index_nums[1] = i;
                }
                break;
            }
        }
        return target_index_nums;
    }
}

运行结果是: 返回两数和的数组下标运行结果

8、删除员工表中姓名重复的数据,只保留重复数据中的一条数据(员工表:emp,员工姓名:name),这里录入的数据是:

id  name
1   Joe  
2   Henry
3   Henry
4   Max
5   Tommy
6   Tommy
7   Tommy

答:

delete from emp where id not in (select a.id from (select * from emp group by name) as a);

运行结果是: 删除重复数据正确运行结果 分析:通过姓名来分组找出一份不重复的姓名记录,把这份记录放到一个临时表a里,再查询这个临时表a找出这些记录的id,删除姓名重复数据就是删除不是这些id的记录。

以下写法是错误的:

delete from emp where id not in (select id from emp group by name);

运行结果会是: 删除重复数据错误运行结果 分析:会抛出错误ERROR 1093 (HY000): You can't specify target table 'emp' for update in FROM clause,这事因为在mysql中不能通过嵌套子查询来直接删除或者修改记录,就是说update或delete的where语句后不能有本表的子查询。解决的办法是,给嵌套子查询的结果取一个别名作为临时表,再从这个临时表中再次查询出记录,要删除或者修改就操作从这个临时表中查询出的记录即可。

这里引出一个值得注意的问题:分组后显示的数据和实际的数据不一定一样,分组后显示的数据是每组的第1条,而实际的数据还是全部,如果要获取分组后显示的数据,可用临时表的方法实现,这道题就是一个很好的验证,执行下面的sql语句进行姓名分组,

select * from emp group by name;

删除重复数据注意地方1 我们可以看到分组后显示的数据是,id为1,2,4,5的数据。再分别执行下面2条sql语句,

select * from emp where id in (select id from emp group by name);
select * from emp where id not in (select id from emp group by name);

删除重复数据注意地方2 执行第1条sql语句,显示的数据竟然是,id为1,2,3,4,5,6,7的数据,即全部数据;执行第2条sql语句,提示数据为空。所以证明了上面的select * from emp group by name;这条sql分组语句得到的实际的数据其实是全部的数据,而不是显示的数据。如果要获取分组后显示的数据,那就要生成临时表了,也就是把分组后显示的数据作为一个临时表来查询,等于把当前显示的数据保存为一个临时表,分别执行下面2条sql语句,

select * from emp where id in (select a.id from (select * from emp group by name) as a);
select * from emp where id not in (select a.id from (select * from emp group by name) as a);

删除重复数据注意地方3 执行第1条sql语句,显示的数据是,id为1,2,4,5的数据,正好就是分组后显示的数据;执行第2条sql语句,显示的数据是,id为3,6,7的数据,正好就是全部的数据除去分组后显示的数据而剩下的数据。

9、运行B.java程序,输出结果是什么?B.java程序如下:

class A {
    public int i = method();
    public static int j = method2();
    public int k = 0;
    public A() {
        System.out.println(1);
    }
    public int method() {
        System.out.println(2);
        return 2;
    }
    public static int method2() {
        System.out.println(3);
        return 3;
    }
}

public class B extends A {
    public int m = method3();
    public static int n = method4();
    public int t = 0;
    public B() {
        System.out.println(4);
    }
    public int method3() {
        System.out.println(5);
        return 5;
    }
    public static int method4() {
        System.out.println(6);
        return 6;
    }
    public static void main(String[] args) {
        System.out.println(7);
        A a = new B();
    }
}

答:输出结果是: A、B程序输出结果 分析: 1)首先加载两个类,加载类时先加载静态变量,先加载到的是A类的j静态变量,所以执行method2,输出3。 2)然后加载到B类的静态变量n,所以执行method4,输出6。 3)再到执行B类的main方法,执行System.out.println(7),输出7。 4)再到执行A a,首先加载A类的成员变量i,所以执行method,输出2。 5)然后加载A类的构造方法A(),所以执行System.out.println(1),输出1。 6)再到执行new B(),首先加载B类的成员变量m,所以执行method3,输出5。 7)然后加载B类的构造方法B(),所以执行System.out.println(4),输出4。

10、使用堵塞队列来实现一个简单的生产者-消费者模型。 答:

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;

public class PCBlockingQueue {
    // 堵塞队列的最大值,也可以不指定
    private static final int MAX_CAPACITY = 10;
    // 顺序堵塞队列,基于数组,必须指定最大值
    // private static BlockingQueue<Object> goods = new ArrayBlockingQueue<>(MAX_CAPACITY);
    // 链式堵塞队列,基于链表,最大值可以指定也可以不指定
    private static BlockingQueue<Object> goods = new LinkedBlockingQueue<Object>(MAX_CAPACITY);
    // 若不指定堵塞队列的最大值,队列会一直增长下去
    // private static BlockingQueue<Object> goods = new LinkedBlockingQueue<Object>();

    public static void main(String[] args) {
        new ProducerThread().start();
        new ConsumerThread().start();
    }

    static class ProducerThread extends Thread {
        @Override
        public void run() {
            while (true) {
                try {
                    Thread.sleep(500);
                    goods.put(new Object());
                    System.out.println("Produce goods, total: " + goods.size());
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    static class ConsumerThread extends Thread {
        @Override
        public void run() {
            while (true) {
                try {
                    Thread.sleep(1000);
                    goods.take();
                    System.out.println("Consume goods, total: " + goods.size());
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

运行结果是: 堵塞队列的生产者-消费者模型 分析:因为指定了堵塞队列的最大值MAX_CAPACITY为10,所以最后增长到了10的时候就不再增长了。若不指定最大值,会一直增长下去,因为这里的生产者每次只睡眠500毫秒,而消费者每次睡眠1000毫秒,生产比消费快。

个人微信公众号

微信公众号:纯洁的技术分享(chunjie_tech)

纯洁的技术分享