爱喝茶的仙人掌

Try to write something.

DophinDB笔试题

Posted on In Views: Valine:
Symbols count in article: 4.7k Reading time ≈ 4 mins.

日期和ID的双射问题

Description：假设日期1969.01.01用0表示，请开发一个函数输出任意日期的整数表示（日期小于1969.01.01的用负数表示）。反过来，给定日期的整数表示，开发一个函数求日期对应的年月日。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
class Solution {
    static int YEAR = 1969;
    static int MONTH = 1;
    static int DAY = 1;
    int[] DaysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    boolean isLeapYear(int year) {
        boolean flag = false;
        flag = year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
        if(flag) {
            DaysInMonth[2] = 29;
        } else {
            DaysInMonth[2] = 28;
        }
        return flag;
    }

    boolean checkValid(int year, int month, int day) {
        isLeapYear(year);
        if (month > 12 || month < 0) {
            return false;
        } else return day >= 0 && day <= DaysInMonth[month];
    }

    int DateToNums(int year, int month, int day) {
        int num = 0;
        if (!checkValid(year, month, day)) {
            System.out.println("输入有误");
            return 0;
        }
        if (year >= YEAR) {
            while (year >= YEAR) {
                day--;
                num++;
                if (day <= 0) {
                    month--;
                    if (month <= 0) {
                        year--;
                        isLeapYear(year);
                        month = 12;
                        day = 31;
                    } else {
                        day = DaysInMonth[month];
                    }
                }
            }
            return num - 1;
        } else {
            while (year < YEAR) {
                day++;
                num--;
                if (day > DaysInMonth[month]) {
                    day = 1;
                    month++;
                    if (month > 12) {
                        month = 1;
                        year++;
                        isLeapYear(year);
                    }
                }
            }
            return num;
        }
    }

    String NumsToDate(int num) {
        int year = YEAR;
        int month = MONTH;
        int day = DAY;
        boolean isLeapYear = false;
        if (num >= 0) {
            while (num > 0) {
                day++;
                if (day > DaysInMonth[month]) {
                    day = 1;
                    month++;
                }
                if (month > 12) {
                    year++;
                    month = 1;
                    isLeapYear(year);
                }
                num--;
            }
        } else {
            while (num < 0) {
                day--;
                num++;
                if (day <= 0) {
                    month--;
                    day = DaysInMonth[month];
                    if (month <= 0) {
                        month = 12;
                        day = DaysInMonth[month];
                        year--;
                        isLeapYear(year);
                    }
                }
            }
        }
        return year + "年" + month + "月" + day + "日";
    }

    public static void main(String[] args) {
        Solution test = new Solution();

        System.out.println(test.DateToNums(1972,1,1));
        for (int i = -740; i < 1100; i++) {
            System.out.print(i+"  ");
            System.out.println(test.NumsToDate(i));
        }
    }
}

测试如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import org.junit.Test;
import static org.junit.Assert.*;

public class SolutionTest {

    Solution solution = new Solution();

    @Test
    public void testDateToNum() {
        assertEquals(0, solution.DateToNums(1969, 1, 1));
        assertEquals(364, solution.DateToNums(1969, 12, 31));
        assertEquals(1460, solution.DateToNums(1972, 12, 31));
        assertEquals(-1, solution.DateToNums(1968,12,31));
        assertEquals(-366, solution.DateToNums(1968,1,1));
    }

    @Test
    public void testNumToDate() {
        assertEquals("1969年1月1日", solution.NumsToDate(0));
        assertEquals("1969年12月31日", solution.NumsToDate(364));
        assertEquals("1972年12月31日", solution.NumsToDate(1460));
        assertEquals("1968年12月31日", solution.NumsToDate(-1));
        assertEquals("1968年1月1日", solution.NumsToDate(-366));

    }

}

重复的部分排序输出

Description：函数cumrank接受1个数组v为参数，对v中的每一个元素，返回其在从第一个元素到此元素为止的向量中的排序。每个元素的排序仅仅与其之前的元素相关，与其之后的元素无关。返回一个与v相同长度的的向量。

示例：cumrank([1,3,2,3,4]) 返回结果： [0,1,1,2,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Arrays;

class Solution{
    int[] cumrank1(int[] input) {
        int count = 0;
        int len = input.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (input[i] > input[j]) {
                    count++;
                }
            }
            res[i] = count;
            count = 0;
        }
        return res;
    }
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] input = {1,3,2,3,4};
        int[] res = test.cumrank1(input);
        System.out.println(Arrays.toString(res));
    }
}

海量数据求中位数

Description：一个长度未知的巨型向量分布在n台机器上，如何快速找到(近似)中位数？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution{
    public static float findMedianFromRandomArray(int[] arr){
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for(int i = 0; i < arr.length; i++){
            //下标偶数存入最小堆，奇数存入最大堆
            if(i % 2 == 0){
                // 存入最小堆前判断当前元素是否小于最大堆的堆顶元素
                if(!maxHeap.isEmpty() && (arr[i] < maxHeap.peek()) ){
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(arr[i]);
                }else{
                    minHeap.offer(arr[i]);
                }

            }else{
                // 存入最大堆前判断当前元素是否大于最小堆的堆顶元素
                if(!minHeap.isEmpty() && (arr[i] > minHeap.peek())) {
                    maxHeap.offer(minHeap.poll());
                    minHeap.offer(arr[i]);
                }else{
                    maxHeap.offer(arr[i]);
                }
            }
        }
        return (maxHeap.size() == minHeap.size()) ? (float) (maxHeap.peek() + minHeap.peek()) / 2 : minHeap.peek();
    }

    public static void main(String args[]){
        int[] arr = {2,5,4,9,3,6,8,7,1,10};
        System.out.println(findMedianFromRandomArray(arr));
    }
}

Reference

无序数组求中位数