How to find the longest possible quasi-constant subsequence of array?

How to find the longest possible quasi-constant subsequence of array?

This is my task2 challenge. I’ve tried to solve this question, but my result wasn’t good. Although there was no error after testing, I only got 33% score.😰

The summary of question shows as below:

I was given a non-empty unsorted array such as: A = [6, 10, 6, 9, 7, 8]. The amplitude of a subsequence of array A is the difference between the largest and the smallest element in this subsequence. The amplitude of the empty subsequence is assumed to be 0.

These are some of the subsequences of array A and their amplitudes:
[6, 6, 7] has amplitude 1;
[6, 10, 6, 9, 7, 8] has amplitude 4;
[6, 6, 7, 8] has amplitude 2.

If this subsequence of array is called quasi-constant, it means its amplitude does not exceed 1. In the example above, subsequence [6, 6, 7] is the longest possible quasi-constant subsequence of array A.

Now, you are expected to provide a method that takes in an array and returns the maximum number of quasi-constant subsequence of array. In above example, the function should return 3.

Here is my attempted solution below.

  1. Sort array A[] first, it becomes: A[] = [6, 6, 7, 8, 9, 10].
  2. Then I count the difference between every two elements, and put each difference into another array: diff[] = [0, 1, 1, 1, 1]
  3. Put array “diff[]” into a for-loop. If the element < 2, then counter++. (It is used to count the number of times when element < 2)
  4. Use a temporary integer object “cumulative” to record the value of cumulative element. If there is any element > 1 in array “diff[]”, then reset counter and cumulative.
  5. Because the number of element in diff[] is less than A[], when return counter, it should plus 1.
//This is a wrong function
public static int solution(int[] A) {
    Arrays.sort(A);

    int[] diff = new int[A.length - 1];
    for (int i = 0; i < A.length - 1; i++) {
        int temp = A[i + 1] - A[i];
        diff[i] = temp;
    }

    int counterTemp = 0;
    int cumulative = 0;
    int counter = 0;
    for (int i = 0; i < diff.length; i++) {
        if (diff[i] < 2) {
            counterTemp++;

            cumulative += diff[i];

            if (cumulative < 2) {
                counter = counterTemp;
            }
        } else {
            counterTemp = 0;
            cumulative = 0;
        }
    }
    return counter + 1;
}

I used the following method to test my code and got the correct results without any error.

public static void main(String[] args) {
    int[] a = {6, 10, 6, 9, 7, 8};//{6, 6, 7} -->3
    int[] b = {6, 10, 1, 2, 6, 6, 7};//{6, 6, 6, 7} -->4
    int[] c = {5, 5, 3, 3, 9};//{3, 3}, {5, 5} -->2
    int[] d = {5, 6, 1, 3, 2, 4}; //2

    System.out.println("Answer is: " + solution(a));
    System.out.println("Answer is: " + solution(b));
    System.out.println("Answer is: " + solution(c));
    System.out.println("Answer is: " + solution(d));
}

The output from console was:

Answer is: 3
Answer is: 4
Answer is: 2
Answer is: 2

Because I really didn’t know how to improve my code, I asked this question on StackOverflow. Fortunately, I received a good and correct response. I should modify my code as follows:

static int quasiConstant(int[] a) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : a)
        map.compute(i, (k, v) -> v == null ? 1 : v + 1);
    int max = 0;
    for (Entry<Integer, Integer> e : map.entrySet()) {
        int t = e.getValue() + map.getOrDefault(e.getKey() + 1, 0);
        if (t > max)
            max = t;
    }
    System.out.println(Arrays.toString(a) + " -> " + max);
    return max;
}

In this function, we can see the author using Java 8 BiFunction to compute the value of the maps: map.compute(i, (k, v) -> v == null ? 1 : v + 1);

It’s really brilliant.

(Visited 4,310 time, 8 visit today)
Facebooktwittergoogle_plusredditpinterestlinkedinmail

3 thoughts on “How to find the longest possible quasi-constant subsequence of array?

  1. It’s all right that you didn’t get it right at the first time. As long as you try to find out the correct answer and do more practice after the test, you will do better next time.

  2. 版主的第一個解法似乎忘記考慮到溢位(overflow)的問題, 所以跑測資的時候產生溢位的問題(32-bit整數極大 – 32-bit整數極小), 導致執行過程的數值不正確, 因為我的做法跟版主差不多, 不過我有過測資

    1. 謝謝你的分享。當初做這個題目是因為參加公司的面試測驗,有非常大的時間壓力,以至於寫code時想得不周全,跑出來的結果不佳。後來看到其他神人的解法只能說佩服。

Comments are closed.

Comments are closed.