【随笔】论一个面试题的解决思路

框架师

发布于 2022-03-08 18:23:47

1970

发布于 2022-03-08 18:23:47

前言

是这样的，最近准备跳槽啦，开始面试了，遇到这样一个问题：给你一个无穷字符串类型的 IP ，IP 之间以 ， 分割，类似这样 String ipStr = "192.168.10.222,192.168.10.43,192.168.10.243",现在需要你写一个方法，入参为 ipStr，出参为 ipStr 的最后一个 Ip。我比较蠢。。。。当面试官问我的时候，我想到的解决方案就是遍历这个数组，然后存入一个集合，根据索引来定位最后一个 IP ，但是面试官讲我这个有性能问题，我自己尝试了一遍，在一千万以内的数据量内，感觉是不存在性能问题的🤣🤣🤣，但是一亿条数据后直接堆溢出了，丢。。。。下面附代码，请多吐槽，让我意识到自己的不足。

遍历list

package com.mobaijun.streamtest;

import org.springframework.util.StopWatch;

import java.util.ArrayList;

/**
 * Software：IntelliJ IDEA 2021.2 x64
 * Author: https://www.mobaijun.com
 * Date: 2022/2/21 16:48
 * ClassName:IpStr
 * 类描述：
 */
public class IpStr {

    /**
     * 计时器
     */
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        // N
        for (int i = 1; i <= 10000000; i++) {
            str.append(i)
                    .append("." + i)
                    .append("." + i)
                    .append("." + i)
                    .append(",");
        }
        stopWatch.start();
        String s = ipStr(String.valueOf(str));
        stopWatch.stop();
        System.out.println("运算耗时为：" + stopWatch.prettyPrint());
        System.out.println("计算值为： = " + s);
    }

    public static String ipStr(String str) {
        String[] ipList = str.split(",");
        ArrayList<String> arrayList = new ArrayList<>();
        for (String s : ipList) {
            arrayList.add(s);
        }
        str = arrayList.get(arrayList.size() - 1);
        return str;
    }
}

打印结果为：

运算耗时为：StopWatch '': running time = 5084789100 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
5084789100  100%  

计算值为： = 10000000.10000000.10000000.10000000

在运算一亿条数据的时候，直接堆溢出

Exception in thread "main" java.lang.OutOfMemoryError
    at java.lang.AbstractStringBuilder.hugeCapacity(AbstractStringBuilder.java:161)
    at java.lang.AbstractStringBuilder.newCapacity(AbstractStringBuilder.java:155)
    at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:125)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:448)
    at java.lang.StringBuilder.append(StringBuilder.java:136)
    at com.mobaijun.streamtest.IpStr.main(IpStr.java:27)

在经过几个群的讨论后，我换了方式来实现这道题，一种是反转 list，一样影响效率，一种是直接倒叙遍历。

反转List

public class IpStr2 {

    /**
     * 计时器
     */
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        // N
        for (int i = 1; i <= 10000000; i++) {
            str.append(i)
                    .append("." + i)
                    .append("." + i)
                    .append("." + i)
                    .append(",");
        }
        stopWatch.start();
        String s = ipStr(String.valueOf(str));
        stopWatch.stop();
        System.out.println("运算耗时为：" + stopWatch.prettyPrint());
        System.out.println("计算值为： = " + s);
    }

    public static String ipStr(String str) {
        ArrayList<String> list = new ArrayList<>();
        String[] split = str.split(",");
        for (String s : split) {
            list.add(s);
        }
        // 反转list
        Collections.reverse(list);
        return list.get(0);
    }
}

耗时时间为：

运算耗时为：StopWatch '': running time = 2156518100 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
2156518100  100%  

计算值为： = 10000000.10000000.10000000.10000000

这个结果也不是很理想，只要存入 list 必然有性能问题。

使用substring实现

public class IpStr3 {
    /**
     * 计时器
     */
    private static StopWatch stopWatch = new StopWatch();

    public static void main(String[] args) {

        StringBuilder str = new StringBuilder();
        // N
        for (int i = 1; i <= 10000000; i++) {
            if (i == 10000000) {
                str.append(i)
                        .append("." + i)
                        .append("." + i)
                        .append("." + i);
            } else {
                str.append(i)
                        .append("." + i)
                        .append("." + i)
                        .append("." + i)
                        .append(",");
            }
        }
        stopWatch.start();
        String s = ipStr(String.valueOf(str));
        stopWatch.stop();
        System.out.println("运算耗时为：" + stopWatch.prettyPrint());
        System.out.println("计算值为： = " + s);
    }

    public static String ipStr(String str) {
        int one = str.lastIndexOf(',');
        str = str.substring(one + 1);
        return str;
    }
}

耗时为：

运算耗时为：StopWatch '': running time = 219355000
--------------------------------------------
ns         %     Task name
--------------------------------------------
219355000  100%  
计算值为： = 10000000.10000000.10000000.10000000