经典面试题总结

整理一些经典的面试题，这些题大部分出自牛客网，还有平时面试碰到的一些。这些题并不是很难，只是自认为比较有代表性，在工作中可能也会碰到。

递归问题

思考下面代码，x函数执行了多少次，i=?

    public static void main(String[] args) {
        int i;
        i = x(x(8));
    }

    static int x(int n) {
        if (n <= 3)
            return 1;
        else
            return x(n - 2) + x(n - 4) + 1;
    }

思路

    // x(8) => x(6)+x(4)+1 = 5+3+1 = 9
    // x(6) => x(4)+x(2)+1 = 5
    // x(4) => x(2)+x(0)+1 = 3
    // x(8) x(6) x(4) x(2) x(0) x(2) x(4) x(2) x(0)

    // x(9) => x(7)+x(5)+1
    // x(7) => x(5)+x(3)+1
    // x(5) => x(3)+x(1)+1
    // x(9) x(7) x(5) x(3) x(1) x(1) x(5) x(3) x(1)

LRU算法

题目来源

一进程刚获得3个主存块的使用权,若该进程访问页面的次序是1,2,3,4,1,2,5,1,2,3,4,5.当采用LRU算法时,发生的缺页此次数是(10)

访问页号顺序	1	2	3	4	1	2	5	1	2	3	4	5
访问页号顺序	1	2	3	4	1	2	5	1	2	3	4	5
第三个内存页			3	4	1	2	5	1	2	3	4	5
第二个内存页		2	2	3	4	1	2	5	1	2	3	4
第一个内存页	1	1	1	2	3	4	1	2	5	1	2	3
是否缺页中断	×	×	×	×	×	×	×	√	√	×	×	×

进制转换

题目来源

大整数845678992357836701转化成16进制表示,最后两位字符是? D<br /><br />
A. AB<br />
B. EF<br />
C. 8B<br />
D. 9D<br />

利用同余关系做。845678992357836701除以4余数为1( 845678992357836700能被4整除 )，在16进制数中，决定除以4后余数的只有最后一位（前面位都是16的倍数，自然被4整除），算算也只有D（13）除以4余1，所以选D.

二进制最后两位是01.只有D符合

十进制转十六进制的方法：用16整除十进制整数，可到一个商和余，再用16去除商，又得到一个商和余...直到商为0，然后将余数逆向排序，即为所求。

例如

求1000的十六进制数。

1000/16 商为62 余数为8
62/16   商为3  余数为14
3/16    商为0  余数为3

则1000的十六进制数为3E8

同理，求二进制时依次用2整除。

例如

求29的二进制数。

29/2  商为14  余数为1
14/2  商为7   余数为0
7/2   商为3   余数为1
3/2   商为1   余数为1
1/2   商为0   余数为1

则29的二进制数为11101

基于这个我们可以手写个简单的进制转换

    static String convert(int input, int p) {
        StringBuilder sb = new StringBuilder();
        while(input/p != 0){
            int y = input % p;
            if(p == 16){
                sb.append(to16(y));
            }else {
                sb.append(y);
            }
            input = input/p;
        }
        sb.append(input%p);
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        int x = 1000;

        String r = convert(x,8);

        System.out.println(r);
    }

    static char to16(int x){
        String match = "123456789abcdef";
        return match.charAt(x-1);
    }

数据类型

Integer a = 1;
Integer b = 1;
Integer c = 500;
Integer d = 500;
System.out.print(a == b);
System.out.print(c == d);

上述代码返回结果为： true false

Integer a = 1 是自动装箱会调用Interger.valueOf(int)方法，查看该方法如下所示：

    public static Integer valueOf(int i) {
        if (i >= IntegerCache.low && i <= IntegerCache.high)
            return IntegerCache.cache[i + (-IntegerCache.low)];
        return new Integer(i);
    }

    /**
     * Cache to support the object identity semantics of autoboxing for values between
     * -128 and 127 (inclusive) as required by JLS.
     *
     * The cache is initialized on first usage.  The size of the cache
     * may be controlled by the {@code -XX:AutoBoxCacheMax=<size>} option.
     * During VM initialization, java.lang.Integer.IntegerCache.high property
     * may be set and saved in the private system properties in the
     * sun.misc.VM class.
     */

    private static class IntegerCache {
        static final int low = -128;
        static final int high;
        static final Integer cache[];

        static {
            // high value may be configured by property
            int h = 127;
            String integerCacheHighPropValue =
                sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
            if (integerCacheHighPropValue != null) {
                try {
                    int i = parseInt(integerCacheHighPropValue);
                    i = Math.max(i, 127);
                    // Maximum array size is Integer.MAX_VALUE
                    h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
                } catch( NumberFormatException nfe) {
                    // If the property cannot be parsed into an int, ignore it.
                }
            }
            high = h;

            cache = new Integer[(high - low) + 1];
            int j = low;
            for(int k = 0; k < cache.length; k++)
                cache[k] = new Integer(j++);

            // range [-128, 127] must be interned (JLS7 5.1.7)
            assert IntegerCache.high >= 127;
        }

        private IntegerCache() {}
    }

也就是说IntegerCache类缓存了-128到127的Integer实例，在这个区间内调用valueOf不会创建新的实例。