大三暑假找拼多多研发实习岗的笔试题

一、编程题

1.输入是一个只含有 0 和 1 的二维矩阵，每一行都是排过序的，也就是说每一行前一部分都是 0，剩下的全都是 1。请找哪些行包含的 1 最多。要求对于 MxN 的矩阵，时间复杂度是O(M+N)，空间复杂度是 O(1)。

示例:

[0 0 0 0 0 0 0 1 1 1 1 1 ]

[0 0 0 0 1 1 1 1 1 1 1 1 ]

[0 0 0 0 0 0 1 1 1 1 1 1 ]

[0 0 0 0 0 0 0 0 0 1 1 1 ]

[0 0 0 0 0 0 0 1 1 1 1 1 ]

[0 0 0 0 1 1 1 1 1 1 1 1 ]

对于上面的函数，第 2 行和第 6 行都有 8 个 1。所以输出[2,8] 和 [6,8]。

 /**
 * Created by loumoon on 2018/7/15.
 * 我的思路是用一个数组rowMax保存有最多1的行。指针从这个矩阵的右上角开始，
 * 如果当前数为1且左边数也为1，指针向左移一个位置，且清空rowMax；
 * 如果当前数为1且左边数为0，或者左边已经没有数了，把当前行存进rowMax，然后指针向下移动一个位置；
 * 如果当前数为0，指针向下移动一个位置。
 * 这样遍历完后，rowMax中就保存了所有拥有最多1的行索引，1的个数可以用总列数减去遍历结束后的列索引
 * 得到
 */

public class Solution1 {
    public static List<List<Integer>> findRow(int [][] array) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();//保存返回结果
        int rows=array.length;//总行数
        if(rows==0)return result;//输入空矩阵，返回空的result即可
        int columns=array[0].length;//总列数

        int row=0;//行指针
        int column=columns-1;//列指针，从右上角开始

        ArrayList<Integer> rowMax=new ArrayList<Integer>();//保存拥有最多1的行

        while(row<=rows-1&&column>=0){
            /*当前位置为1且左边为0，或者左边已经没有数了(说明这一行全都是1)，注意||左右两边表达式的判断顺序，如果反过来会抛出超出索引的异常*/
            if(array[row][column]==1&&(column==0||array[row][column-1]==0)){
                rowMax.add(row);//说明在当前情况下，这是一个有最多1的行
                row++;//指针下移
            }

            /*当前位置为1且左边为1，说明此时找到了1更多的行，*/
            else if(array[row][column]==1&&array[row][column-1]==1){
                rowMax.clear();//清空，说明之前的最多1数目的记录已经被刷新了
                column--;//指针左移
            }

            else if(array[row][column]==0){
                row++;//当前行的1数达不到最高纪录，淘汰
            }
        }

        int numMax=columns-column;//最多1数的记录
        for(int i=0;i<rowMax.size();i++){
            List singleRow=new ArrayList<Integer>();
            singleRow.add(rowMax.get(i));
            singleRow.add(numMax);
            result.add(singleRow);
        }

        return result;
    }

    /*测试*/
    public static void main(String[] args){
        int[][] array={{1,1,1},{0,1,1},{0,1,1},{0,0,0},{1,1,1}};
        List<List<Integer>> result=findRow(array);
        System.out.println(result);
    }
}

2.输入一个字符串比如{[(2+3)(1-3)] + 4}(14-3)，分析它的括号使用是否正确，括号有三种：小括号()，中括号[]，大括号{}

正确的括号使用必须满足以下条件(和数学上定义一致):

(1)左右括号必须匹配

(2)每一种类型括号只能和同一类型的括号匹配，即(和)匹配 [和]匹配 {和}匹配

(3)括号有优先级，小括号在最内层，中括号必须嵌套在小括号外面，大括号必须嵌套在中括号外面

(4)比如{},([ ])这样的都是非法的

(5)除了最外层可以连续嵌套大括号外，小括号和中括号不能连续嵌套，比如(( )),[[( )]]都是非法的，但是{{[( )]}}是合法的

(6)不需要考虑除了括号之外的其他字符是否违反了数学上的规定

/**
 * Created by loumoon on 2018/7/14.
 * 注意题设要求的：小括号在最内层，中括号必须嵌套在小括号外面，大括号必须嵌套的中括号外面，也就是说
 * 出现了大括号，其内部一定得有中括号，出现了中括号，其内部一定得有小括号。
 * 因此不仅需要入栈之前对栈顶进行检测，而且还要对之后的入栈情况进行检测。比如入栈了左大括号，在右大
 * 括号闭合之前要检测是否有中括号出现，若没有则不合法。同理如果入栈了左中括号，在右中括号闭合之前要
 * 检测是否有小括号出现，若没有则不合法。
 */

public class Solution2 {
    public static boolean bracketsJudge(String string){
        Stack<Character> stack=new Stack<Character>();
        boolean hasMiddleBrackets=false;
        boolean hasLittleBrackets=false;
        for(int i=0;i<string.length();i++){
            char cur=string.charAt(i);
          
            if(cur=='{'){
                if(!stack.isEmpty()&&(stack.peek()=='['||stack.peek()=='(')){
                    return false;
                }
                hasMiddleBrackets=true;//如果有大括号出现，其后面必有跟着的中括号才不合法
                stack.push(cur);
            }

            else if(cur=='['){
                if(!stack.isEmpty()&&(stack.peek()=='['||stack.peek()=='(')){
                    return false;
                }
                hasMiddleBrackets=false;//出现了中括号，置为false
                hasLittleBrackets=true;//如果有中括号出现，其后面必有跟着的小括号，否则不合法
                stack.push(cur);
            }

            else if(cur=='('){
                if(!stack.isEmpty()&&(stack.peek()=='('||stack.peek()=='{')) {
                    return false;
                }
                hasLittleBrackets=false;//出现了小括号，置为false
                stack.push(cur);
            }

            else if(cur=='}'){
                if(stack.isEmpty())return false;
                if(hasMiddleBrackets==true)return false;//大括号闭合之前依然没有出现中括号，不合法
                if(stack.pop()!='{')return false;
            }

            else if(cur==']'){
                if(stack.isEmpty())return false;
                if(hasLittleBrackets==true)return false;//中括号闭合之前依然没出现小括号，不合法
                if(stack.pop()!='[')return false;

            }

            else if(cur==')'){
                if(stack.isEmpty())return false;
                if(stack.pop()!='(')return false;
            }

        }

        if(!stack.isEmpty())return false;
        return true;
    }

    /*测试*/
    public static void main(String[] args){
        boolean check=bracketsJudge("");
        System.out.println(check);
    }
}

3.房间里面有一个机器人位于位置(0, 0)。房间的形状和面积都是未知的。你可以通过一个遥控器来控制机器人往前后左右四个方向中的任何一个移动一个格子。

移动的函数是 boolean move(int direction), direction: 0, 1, 2, 3。如果机器人发现移动方向上被墙壁挡住，这个方法会返回 false，否则这个函数就会返回 true，机器人就会移动到相应的位置。

请实现一个函数，来找到房间的面积。注:房间的形状是不规则的，但是是由许多大小为 1x1 的格子组成的，比如下图表示的房子里面，每一个 X 表示一个格子，房间的总面积是 10

X

XXX X

XXXXX

 /**
 * Created by loumoon on 2018/7/14.
 * 深度优先搜索，将不重复地走过的所有的位置保存在集合set中，遍历结束后set的size就是房间面积
 */

public class Solution3 {
    public int quadrature(){
        Set<String> record=new HashSet<String>();//集合存储到达过的位置，位置用字符串表示
        recursion(record,0,0);//进行递归
        return record.size();//递归完毕后所有的位置都被遍历了，集合中的元素个数就是面积
    }

    /*递归*/
    private void recursion(Set<String> set,int x,int y){
        set.add(x+","+y);//当前位置加入集合
        if(!set.contains(x+","+(y+1))&&move(x,y,0)){//向上
            recursion(set,x,y+1);
        }

        if(!set.contains(x+","+(y-1))&&move(x,y,1)){//向下
            recursion(set,x,y-1);
        }

        if(!set.contains((x-1)+","+y)&&move(x,y,2)){//向左
            recursion(set,x-1,y);
        }

        if(!set.contains((x+1)+","+y)&&move(x,y,3)){//向右
            recursion(set,x+1,y);
        }
    }
    
    /*这个move()自定义的，是测试用的*/
    private boolean move(int x,int y,int dir){//判断从(x,y)位置往dir方向是否可行
        return true;
    }
}

4.给定 K 个有序数组 a1, a2, … , ak，求一个最小长度的区间 [s, t],使得每个数列 ai 都至少有一个元素 aij 在这个区间内。如果有多个长度相等的区间满足条件，则选择起始点 s 最小的那一个。
示例:

​ 输入:[1, 3, 5] [4, 8] [2, 5]

​ 输出: [4, 5]

/**
 * Created by loumoon on 2018/7/15.
 * 找到所有数组最小值中的最大值，和所有数组最大值中的最小值，分别作为所求区间的最小值和最大值
 */

public class Solution4 {
    public List<Integer> findInterval(List<List<Integer>> input){
        int min=input.get(0).get(0);//保存所有数组最小值中的最大值
        int max=input.get(0).get(input.get(0).size()-1);//保存所有数组最大值中的最小值

        for(int i=1;i<input.size();i++){
            if(input.get(i).get(0)>min){
                min=input.get(i).get(0);
            }
          
            if(input.get(i).get(input.get(i).size()-1)<max){
                max=input.get(i).get(input.get(i).size()-1);
            }
        }

        if(min>max){//如果min>max，交换二者的值
            int exch=min;
            min=max;
            max=exch;
        }

        List<Integer> result=new ArrayList<Integer>();
        result.add(min);
        result.add(max);
        return result;
    }
}

二、问答题

1.请简述线程和进程的区别

（1）进程是一个执行中的程序的实例。具有独立的逻辑控制流和私有的地址空间，提供一个抽象，好像应用程序在独占地使用处理器和存储器系统。线程自己基本不拥有系统资源，运行时只是暂用一些计数器、寄存器和栈。

（2）一个进程由一个或多个线程组成，线程是一个进程中代码的不同执行路线；

（3）进程之间相互独立，但同一进程下的各个线程之间共享进程的内存空间。

（4）线程上下文切换比进程上下文切换要快得多。

2.请简述抢占式和非抢占式进程的区别

非抢占式进程调度就是让进程运行到结束或阻塞的调度方式。采用非抢占式进程调度，当就绪队列中某进程的最高优先级高于正在处理器中运行的进程的最高优先级时，并不会让正在运行的进程退出处理器，而是将更高优先级的进程排在就绪队列的首部。

抢占式进程调度是允许将逻辑上可继续运行的进程暂停的调度方式，可防止单一进程长时间独占CPU。采用抢占式最高优先级进程调度，更高优先级的进程会直接抢占处理器，让正在处理的进程强制退出处理器，处于就绪队列。

3.两个不同的线程之间如何通信？两个进程之间呢？

（1）线程之间的通信方式：

–共享变量。线程可以在共享对象的变量里设置信号值，从而实现在线程间的信号发送。

–wait()\notify机制。可以使用Object类提供的wait()、notify()、notifyAll()三个方法。

–管道。但是管道流只能在两个线程之间传递数据。而且管道流只能实现单向发送，如果要两个进程之间相互通讯，需要两个管道流。

（2）进程间的通信方式

–管道。管道可用于具有亲缘关系进程间的通信，允许一个进程和另一个与它有共同祖先的进程之间进行通信。

–命名管道。命名管道除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。

–信号。

–消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。

–共享内存。使得多个进程可以访问同一块内存空间，是最快的可用进程间通信形式。

4.如何实现一个线程安全的hash map？

线程安全的hash map有HashTable和ConcurrentHashMap，二者相对于HashMap都具有线程安全的优点。

HashTable使用synchronized同步锁，使同一时间仅有一个线程能拿到锁并更改HashTable，因此其缺点是效率低。

ConcurrentHashMap则将内部分为若干个segment，每次操作对segment加锁，保证每个segment是线程安全的，从而保证整个ConcurrentHashMap是线程安全的，因此若干个线程可同时访问并更改ConcurrentHashMap，其相对于HashTable效率更高。