分享面试中常见的两道需要手写代码题的解题思路

用户3587585

发布于 2022-09-21 07:07:51

4310

发布于 2022-09-21 07:07:51

引言

之前参加过几场甲方公司的面试，当时有遇到面试官要求手写代码实现一个多线程有序打印和实现快速排序的两道题。当时写的心里不是很确定自己的答案在代码跑起来的时候会不会有问题，这两天终于有时间在家写两个demo在本地跑一跑验证一下了。后来上网一查，发现多线程实现交替有序打印和手写快速排序是Java程序员的高频面试题，那我就觉得有必要把自己的解题思路和测试代码分享出来了，希望能帮助到本公众号部分最近需要参加面试的小伙伴！

面试题一：如何实现多程交替有序打印字符串?

当时面试官的问题是：我有三个线程，如何让它们交替有序打印"AAA,BBB和CCC"等字符串？

我有两种思路：一种是启动三个线程，在每个线程构造参数的Runnable接口实现类的run方法中实现打印字符串，然后调用每个线程对象的start方法；另一种是把三个线程放到一个线程池里去处理，每个线程也是在其构造函数传递的Runnable类型参数的run方法中实现打印字符串逻辑。

思路一实现代码实现

package com.hsf.demo
public class ThreadTest {
  //定义一个多线程可见的变量count
  public volatile int count = 1;
  
    @Test
    public void test1(){
      Thread thread1 = new Thread(()->{
            //使用while循环实现多次打印
            while (count<100){
                //当count整除3余1时打印AAA
                if(count%3==1){
                    System.out.println("count="+count+",AAA");                 //打印完后count加1
                    count++;
                }
            }
        });

        Thread thread2 = new Thread(()->{
            while (count<100){
                //当count整除3余2时打印BBB
                if(count%3==2){
                    System.out.println("count="+count+",BBB");
                    count++;
                }
            }
        });

        Thread thread3 = new Thread(()->{
            while (count<100){
                //当count整除3余1时打印CCC
                if(count%3==0){
                    System.out.println("count="+count+",CCC");
                    count++;
                }
            }
        });
        //调用每个线程的start方法，等待分配CPU运行
        thread1.start();
        thread2.start();
        thread3.start();
    }

}

为了交替有序打印每个线程run方法中的字符串,本人定义了一个volatile关键字修饰的变量count，volatile修饰后的变量可以实现对同一台JVM上的多个线程可见。在IDEA中运行test1测试方法后控制台打印结果如下：

count=1,AAA
count=2,BBB
count=3,CCC
count=4,AAA
count=5,BBB
count=6,CCC
count=7,AAA
count=8,BBB
count=9,CCC
count=10,AAA
count=11,BBB
count=12,CCC
count=13,AAA
count=14,BBB
count=15,CCC
count=16,AAA
count=17,BBB
count=18,CCC
count=19,AAA
count=20,BBB
count=21,CCC
count=22,AAA
count=23,BBB
count=24,CCC
count=25,AAA
count=26,BBB
count=27,CCC
count=28,AAA
count=29,BBB
count=30,CCC
count=31,AAA
count=32,BBB
count=33,CCC
count=34,AAA
count=35,BBB
count=36,CCC
count=37,AAA
count=38,BBB
count=39,CCC
count=40,AAA
count=41,BBB

由控制台的打印结果可以看出程序实现了三个线程交替有序打印字符串，但是出现了一个新的问题，那就是我的总循环次数应该要出现99次，但是发现多次运行测试方法后都是在循环次数为50次左右程序便退出了，这个问题笔者暂时也没搞清楚具体是什么原因导致的。希望知道具体原因的读者能给我私信告知一下，笔者将不胜感激！

思路二代码实现

package com.hsf.demo

import org.junit.Test;
public class ThreadTest {
   public volatile int count = 1;
    @Test
    public void test1(){
      //构造工作队列，队列容量设置为10
      ArrayBlockingQueue<Runnable> workQueue = new ArrayBlockingQueue<>(10);
         //构造的核心线程池对象参数：核心线程数为3:最大线程数为20；超过核心线程数的线程最大闲置时间为5000ms；工作队列为线性阻塞队列；线程工程和拒绝策略都使用线程池默认的
        ThreadPoolExecutor poolExecutor = new ThreadPoolExecutor(3,20,5000,TimeUnit.MICROSECONDS,workQueue);

        poolExecutor.execute(()->{
            while (count<100){
                if(count%3==1){
                    System.out.println("count="+count+",AAA");
                    count++;
                }
            }
        });

        poolExecutor.execute(()->{
            while (count<100){
                if(count%3==2){
                    System.out.println("count="+count+",BBB");
                    count++;
                }
            }
        });

        poolExecutor.execute(()->{
            while (count<100){
                if(count%3==0){
                    System.out.println("count="+count+",CCC");
                    count++;
                }
            }
        });
    }
}

在第二中思路中，笔者使用线程池提交任务的方式，控制有序交替打印的逻辑和思路一中一致，运行结果如下：

count=1,AAA
count=2,BBB
count=3,CCC
count=4,AAA
count=5,BBB
count=6,CCC
count=7,AAA
count=8,BBB
count=9,CCC
count=10,AAA
count=11,BBB
count=12,CCC
count=13,AAA
count=14,BBB
count=15,CCC
count=16,AAA
count=17,BBB
count=18,CCC
count=19,AAA
count=20,BBB
count=21,CCC
count=22,AAA
count=23,BBB
count=24,CCC
count=25,AAA
count=26,BBB
count=27,CCC
count=28,AAA
count=29,BBB
count=30,CCC
count=31,AAA
count=32,BBB
count=33,CCC
count=34,AAA
count=35,BBB
count=36,CCC
count=37,AAA
count=38,BBB
count=39,CCC
count=40,AAA
count=41,BBB
count=42,CCC
count=43,AAA
count=44,BBB
count=45,CCC
count=46,AAA
count=47,BBB
count=48,CCC
count=49,AAA
count=50,BBB
count=51,CCC
count=52,AAA

这种方式也出现了总的循环次数不及99次进程就退出了。面试题一的解题思路就到这吧。

手写快速排序算法代码

什么是快速排序

快速排序（Quicksort）使用分治思想对冒泡排序作了改进，效率非常高。
其基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序的实现

从快速排序的基本思想可以分析出其实现思路：

1.选取一个枢轴元素（也叫基准元素）
2.将数组分割成两部分，一部分数据都小于或等于枢轴元素，另一部分数据都大于枢轴元素
3.对分割的子数组递归地执行步骤1和2，直到无法分割

快速排序代码实现

public void quickSort(int[] arr, int start, int end) {
        // 递归终止条件
        if (start >= end) {
            return;
        }
        // 第一步，找出分区后枢轴的下标，比如[2,1,3],枢轴为2，分区后枢轴的下标为1
        int pivotIndex = partition(arr, start, end);
        // 第二步，对左子数组排序
        quickSort(arr, start, pivotIndex - 1);
        // 第三步，对右子数组排序
        quickSort(arr, pivotIndex + 1, end);
    }

至此，快排的主干代码已经完成。接下来只要知道如何实现分区并返回枢轴元素的下标，我们的代码就可以完整实现，其实这才是实现快排要思考的核心问题

如何实现分区并返回枢轴元素的下标？

这里介绍两种方法：挖坑填数法和左右指针法

关于两种方法的具体实现图解过程和思路读者可跳转至CSDN博客网地址https://blog.csdn.net/unwrapping/article/details/108949204仔细阅读。由于微信公众号对于一篇文章一旦出现内容与之前某位作者原创的文章出现大量雷同的情况就会把整篇文章变成那篇原创文章的链接，这里就不方便拷贝过来了。在这里只提供两种方法的代码实现。

挖坑填数法代码实现

 public int partition(int[] arr,int start,int end){
        //确定参照元素
        int pivot = arr[low];
        //定义两个指针引用，一个指向数组左端，一个指向数组右端
        int left=low,right=high;
        while (left<right){
            // 从右往左扫描，寻找比枢轴元素小的，并填入坑中
            while (left<right && pivot<=arr[right]){
                right--;
            }
            if(left<right){
                arr[left]=arr[right];
                left++;
            }
            // 从左往右扫描，寻找比枢轴元素大的，并填入新坑中
            while(left<right && arr[left]<pivot){
                left++;
            }
            if(left<right){
                arr[right]=arr[left];
                right--;
            }
        }
        //扫描完成后将基准元素放入中间位置
        arr[left]=pivot;
        return left;
    }

左右指针法代码实现

 public int partition(int[] arr, int start, int end) {
        // 枢轴元素
        int pivot = arr[start];
        // 左指针，用于从左往右扫描元素
        int left = start + 1;
        // 右指针，用于从右往左扫描元素
        int right = end;
        while (true) {
            // 从左往右扫描，寻找比枢轴大的元素
            while (arr[left] <= pivot) {
                left++;
                // 防止越界
                if (left == end) break;
            }
            // 从右往左扫描，寻找比枢轴小的元素
            while (arr[right] > pivot) {
                right--;
                if (right == start) break;
            }
            if (left >= right) break;
            // 如果left<right, 交换a[left]和a[right]
            swap(arr, left, right);
        }
        // 交换轴枢和right所在位置元素
        swap(arr, start, right);
        return right;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

快速排序效果验证

写一个测试方法，验证快速排序的效果

@Test
    public void testQuickSort(){
        int[] arr = new int[]{90,70,89,17,12,68,79,55,35,23,12,1,5,98,56,78,57,24,99,105,15,45,86};
        long startTime = System.nanoTime();
        quickSort(arr,0,arr.length-1);
        long endTime = System.nanoTime();//12700ns,8801ns,9000ns
        System.out.println("快速排序耗时："+(endTime-startTime)+"ns");
        System.out.println(Arrays.toString(arr));
    }

运行快速排序测试方法，控制台打印结果如下：

快速排序耗时：10600ns
[1, 5, 12, 12, 15, 17, 23, 24, 35, 45, 55, 56, 57, 68, 70, 78, 79, 86, 89, 90, 98, 99, 105]

控制台打印结果表明快速排序代码逻辑准确实现了对数组的排序

运行程序三次，发现其耗时时间分别为10600ns、8801ns和9000ns，平均耗时为9467ns。我们将快速排序的耗时与冒泡排序的耗时结果进行了比较

冒泡排序实现代码

    @Test
    public void testMaoPaoSort(){
        int[] arr = new int[]{90,70,89,17,12,68,79,55,35,23,12,1,5,98,56,78,57,24,99,105,15,45,86};
        long startTime = System.nanoTime();
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    int temp = arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        long endTime = System.nanoTime();
        System.out.println("冒泡排序耗时："+(endTime-startTime)+"ns");//
        System.out.println(Arrays.toString(arr));

    }

运行测试方法后控制台打印如下结果：

冒泡排序耗时：36700ns
[1, 5, 12, 12, 15, 17, 23, 24, 35, 45, 55, 56, 57, 68, 70, 78, 79, 86, 89, 90, 98, 99, 105]

笔者对冒泡排序同样运行三次，发现三次耗时分别为11100ns、36700ns和9600ns，平均耗时为19133ns。在数组长度为23时，快速排序比冒泡排序节省了10000nas,由此可见在效率上快速排序明显优于冒泡排序。

参考文章

【1】java实现快速排序（https://blog.csdn.net/unwrapping/article/details/108949204）

往期文章推荐阅读

【1】BAT大厂面试官必问的HashMap相关面试题及部分源码分析

【2】看完此文，再也不怕面试官考你数据库事务方面的问题了!

【3】一篇文章带你彻底掌握线程池原理

【4】能让你Hold住面试官的Mysql 数据页结构及索引底层原理总结（文末附新春红包福利）

写文章不易，希望看过的读者都能点亮再看，你的支持是作者坚持的动力！

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

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

编程算法

腾讯云开发者社区

本文分享自阿福谈Web编程微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

腾讯云开发者社区

登录后参与评论

0 条评论

热度