Test results - Codility

Tasks Details

medium

1. Flags

Find the maximum number of flags that can be set on mountain peaks.

100%

A non-empty array A consisting of N integers is given.

A peak is an array element which is larger than its neighbours. More precisely, it is an index P such that 0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1].

For example, the following array A:

A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

has exactly four peaks: elements 1, 3, 5 and 10.

You are going on a trip to a range of mountains whose relative heights are represented by array A, as shown in a figure below. You have to choose how many flags you should take with you. The goal is to set the maximum number of flags on the peaks, according to certain rules.

Flags can only be set on peaks. What's more, if you take K flags, then the distance between any two flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.

For example, given the mountain range represented by array A, above, with N = 12, if you take:

two flags, you can set them on peaks 1 and 5;

three flags, you can set them on peaks 1, 5 and 10;

four flags, you can set only three flags, on peaks 1, 5 and 10.

You can therefore set a maximum of three flags in this case.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the maximum number of flags that can be set on the peaks of the array.

For example, the following array A:

A[0] = 1 A[1] = 5 A[2] = 3 A[3] = 4 A[4] = 3 A[5] = 4 A[6] = 1 A[7] = 2 A[8] = 3 A[9] = 4 A[10] = 6 A[11] = 2

the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..400,000];

each element of array A is an integer within the range [0..1,000,000,000].

Solution

Programming language used Java 8

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 03:32:43 UTC, java, autosave

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

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    public int solution(int[] A) {
        // write your code in Java SE 8
        if (A == null || A.length == 0) {
            return 0;
        }
        // 1. find all peaks.
        List<Integer> peaks = getAllPeaks(A);
        // find max flags, range from 1 - k
        // 2. binary search.
        return binarySearch(peaks);
    }

    private List<Integer> getAllPeaks(int[] A) {
        List<Integer> peaks = new ArrayList();
        for (int i = 1; i < A.length - 1; i++) {
            if (A[i] > A[i + 1] && A[i] > A[i - 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    private Integer binarySearch(List<Integer> peaks) {
        int begin = 1, end = peaks.size();
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (canPutFlags(peaks, mid)) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (canPutFlags(peaks, end)) {
            return end;
        }
        if (canPutFlags(peaks, begin)) {
            return begin;
        }
        return null;
    }

    public boolean canPutFlags(List<Integer> peaks, int flags) {
        if (peaks.size() == 0) {
            return false;
        }
        int lastIndex = peaks.get(0);
        int usedFlags = 1;
        for (int p = 1; p < peaks.size(); p++) {
            int pIndex = peaks.get(p);
            if (pIndex - lastIndex >= flags) {
                usedFlags++;
                lastIndex = pIndex;
            }
            if (usedFlags == flags) {
                return true;
            }
        }
        // ensure only one peek.
        return usedFlags == flags;
    }
}

Code: 03:32:46 UTC, java, verify, result: Passed

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

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    public int solution(int[] A) {
        // write your code in Java SE 8
        if (A == null || A.length == 0) {
            return 0;
        }
        // 1. find all peaks.
        List<Integer> peaks = getAllPeaks(A);
        // find max flags, range from 1 - k
        // 2. binary search.
        return binarySearch(peaks);
    }

    private List<Integer> getAllPeaks(int[] A) {
        List<Integer> peaks = new ArrayList();
        for (int i = 1; i < A.length - 1; i++) {
            if (A[i] > A[i + 1] && A[i] > A[i - 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    private Integer binarySearch(List<Integer> peaks) {
        int begin = 1, end = peaks.size();
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (canPutFlags(peaks, mid)) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (canPutFlags(peaks, end)) {
            return end;
        }
        if (canPutFlags(peaks, begin)) {
            return begin;
        }
        return 0;
    }

    public boolean canPutFlags(List<Integer> peaks, int flags) {
        if (peaks.size() == 0) {
            return false;
        }
        int lastIndex = peaks.get(0);
        int usedFlags = 1;
        for (int p = 1; p < peaks.size(); p++) {
            int pIndex = peaks.get(p);
            if (pIndex - lastIndex >= flags) {
                usedFlags++;
                lastIndex = pIndex;
            }
            if (usedFlags == flags) {
                return true;
            }
        }
        // ensure only one peek.
        return usedFlags == flags;
    }
}

Analysis

▶

example
example test

✔

Code: 03:32:59 UTC, java, verify, result: Passed

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

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    public int solution(int[] A) {
        // write your code in Java SE 8
        if (A == null || A.length == 0) {
            return 0;
        }
        // 1. find all peaks.
        List<Integer> peaks = getAllPeaks(A);
        // find max flags, range from 1 - k
        // 2. binary search.
        return binarySearch(peaks);
    }

    private List<Integer> getAllPeaks(int[] A) {
        List<Integer> peaks = new ArrayList();
        for (int i = 1; i < A.length - 1; i++) {
            if (A[i] > A[i + 1] && A[i] > A[i - 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    private Integer binarySearch(List<Integer> peaks) {
        int begin = 1, end = peaks.size();
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (canPutFlags(peaks, mid)) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (canPutFlags(peaks, end)) {
            return end;
        }
        if (canPutFlags(peaks, begin)) {
            return begin;
        }
        return 0;
    }

    public boolean canPutFlags(List<Integer> peaks, int flags) {
        if (peaks.size() == 0) {
            return false;
        }
        int lastIndex = peaks.get(0);
        int usedFlags = 1;
        for (int p = 1; p < peaks.size(); p++) {
            int pIndex = peaks.get(p);
            if (pIndex - lastIndex >= flags) {
                usedFlags++;
                lastIndex = pIndex;
            }
            if (usedFlags == flags) {
                return true;
            }
        }
        // ensure only one peek.
        return usedFlags == flags;
    }
}

Analysis

▶

example
example test

✔

Code: 03:33:03 UTC, java, final, score: 100

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

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {

    public int solution(int[] A) {
        // write your code in Java SE 8
        if (A == null || A.length == 0) {
            return 0;
        }
        // 1. find all peaks.
        List<Integer> peaks = getAllPeaks(A);
        // find max flags, range from 1 - k
        // 2. binary search.
        return binarySearch(peaks);
    }

    private List<Integer> getAllPeaks(int[] A) {
        List<Integer> peaks = new ArrayList();
        for (int i = 1; i < A.length - 1; i++) {
            if (A[i] > A[i + 1] && A[i] > A[i - 1]) {
                peaks.add(i);
            }
        }
        return peaks;
    }

    private Integer binarySearch(List<Integer> peaks) {
        int begin = 1, end = peaks.size();
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            if (canPutFlags(peaks, mid)) {
                begin = mid;
            } else {
                end = mid;
            }
        }
        if (canPutFlags(peaks, end)) {
            return end;
        }
        if (canPutFlags(peaks, begin)) {
            return begin;
        }
        return 0;
    }

    public boolean canPutFlags(List<Integer> peaks, int flags) {
        if (peaks.size() == 0) {
            return false;
        }
        int lastIndex = peaks.get(0);
        int usedFlags = 1;
        for (int p = 1; p < peaks.size(); p++) {
            int pIndex = peaks.get(p);
            if (pIndex - lastIndex >= flags) {
                usedFlags++;
                lastIndex = pIndex;
            }
            if (usedFlags == flags) {
                return true;
            }
        }
        // ensure only one peek.
        return usedFlags == flags;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example
example test

✔

▶

single
extreme min test

✔

▶

triple
three elements

✔

▶

extreme_without_peaks
test without peaks

✔

▶

simple1
first simple test

✔

▶

simple2
second simple test

✔

▶

medium_many_peaks
medium test with 100 peaks

✔

▶

medium_random
chaotic medium sequences, length = ~10,000

✔

▶

packed_peaks
possible to set floor(sqrt(N))+1 flags

✔

▶

large_random
chaotic large sequences, length = ~100,000

✔

▶

large_little_peaks
large test with 20-800 peaks

✔

▶

large_many_peaks
large test with 10,000 - 25,000 peaks

✔

▶

large_anti_slow
large test anti slow solutions

✔

▶

large_anti_slow2
large test anti slow solutions

✔

▶

extreme_max
extreme test, maximal number of elements

✔

▶

extreme_max2
extreme test, maximal number of elements

✔