第一题 给出场景写SQL,设计索引,设计缓存

衍生Redis，B+树，索引最左前缀原则，Redis ZSET,底层的ziplist,skiplist

第二题 演唱会安排 求出最大安排场数和安排的对应方案

public class VocalConcert {
    static ArrayList<int[]> concert = new ArrayList<>();
    static ArrayList<String> ans = new ArrayList<>();
    public static void main(String[] args){
        concertInit();
        int maxCount = 0;
        for(int i = 0;i<concert.size();i++){
            //记录从0-concert.size()-1为起点的所有情况
            maxCount = Math.max(maxCount,findMax(i,i+1,1,String.valueOf(i)));
        }
        System.out.println("MAX COUNT "+maxCount);
        for(String s:ans){
            if(s.length()==maxCount) {
                System.out.println(s);
            }
        }
    }

    /**
     * 初始化
     */
    private static void concertInit(){
        concert.add(new int[]{1,10});
        concert.add(new int[]{2,4});
        concert.add(new int[]{4,6});
        concert.add(new int[]{3,7});
        concert.add(new int[]{5,7});
        concert.add(new int[]{5,8});
        concert.add(new int[]{3,8});
        concert.add(new int[]{7,10});
    }

    /**
     * 找出所有符合条件的场次
     * @param lastIndex 上一次的演出索引
     * @param index 当前演出索引
     * @param count 当前的安排演唱会场数
     * @param a 演出的安排
     * @return 最大的演出场数
     */
    private static Integer findMax(int lastIndex,int index,int count,String a){
        int result = count;
        if(index>=concert.size()){
            if (!ans.contains(a)) {
                ans.add(a);
            }
            return result;
        }
        if(concert.get(lastIndex)[1]>concert.get(index)[0]){
            //前后两场演唱会重叠
            while(index<concert.size()){
                index++;
                result = Math.max(result,findMax(lastIndex,index,count,a));
            }
        }else{
            //前后两场演唱会不重叠
            count+=1;
            int curIndex = index;
            while(index<concert.size()){
                //不重叠 以新的情况往下走
                result = Math.max(result,findMax(curIndex,index+1,count,a+curIndex));
                index++;
            }
        }
        return result;
    }
}

第三题 AB赌徒 两次获胜概率都是0.5 A获胜两个小场最终胜利，B获胜三个小场最终胜利，求AB获胜概率

public static void main(String[] args) {
        /**
         * 这题后来想了一下就是求出A就可以求出B了，因为在aGamblerWinCount+bGamblerWinCount-1回合内就肯定会结束
         */
        int min = aGamblerWinCount > bGamblerWinCount ? bGamblerWinCount : aGamblerWinCount;
        float a = 0;
        int maxGameCount = aGamblerWinCount + bGamblerWinCount - 1;
        //公式为 1/2^index * [C index-1 min-1](组合) 即在最后一位已经定好的情况下，求min-1个胜利在index-1局里面的组合数
        for (int index = min; index <= maxGameCount; index++) {
            a += Math.pow((double) 1 / 2, index) * tri((index - 1),min-1);
        }
        System.out.println(a);
        System.out.println(1-a);
    }

    //杨辉三角求组合
    static int tri(int x,int y){
        if(x<y){
            return 1;
        }
        int[][] a = new int[x+1][x+1];
        for(int i=1; i<=x; i++ )
        {
            a[i][0] = a[i][i] = 1;  //初始化第一列和对角线位置全为1，即最两边的位置
            for( int j=1; j<i; j++ )
                a[i][j] = (a[i-1][j] + a[i-1][j-1]) % 1007;
        }
        return a[x][y];
    }