Test results - Codility

Tasks Details

easy

1. MaxProfit

Given a log of stock prices compute the maximum possible earning.

Task Score

66%

Correctness

100%

Performance

25%

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

def solution(A)

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

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

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

Solution

Programming language used Python

Total time used 13 minutes

Effective time used 13 minutes

Notes

not defined yet

Task timeline

Code: 13:59:31 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// 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
    }
}

Code: 13:59:41 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    pass

Code: 14:03:19 UTC, py, autosave

show code in pop-up

1 2 3 4 5

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):

Code: 14:03:43 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, num in enumerate(A):
        print(i, num)

Code: 14:03:53 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, num in enumerate(A):
        for

Code: 14:04:10 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, num in enumerate(A):
        for j,

Code: 14:04:20 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, num in enumerate(A):
        for

Code: 14:04:36 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i,  in enumerate(A):
        for

Code: 14:04:51 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for

Code: 14:05:06 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for j in range(i+1)

Code: 14:05:17 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for j in

Code: 14:06:55 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for j in A[]

Code: 14:07:06 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for j in A[i+1:]:
            print(j)

Code: 14:07:19 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i:]:
            print(j)

Code: 14:07:50 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            print(q)

Code: 14:08:04 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        print("num")
        print(i)
        for q in A[i+1:]:
            print(q)

Code: 14:08:04 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        print("num")
        print(i)
        for q in A[i+1:]:
            print(q)

Analysis

expand all Example tests

▶

example
example, length=6

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 14:08:28 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
     
        print(i)
        for q in A[i+1:]:
            print(q)

Code: 14:08:39 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):

        for q in A[i+1:]:
            print(q)

Code: 14:09:39 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            print(q)

Code: 14:09:43 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            print(q)

Analysis

expand all Example tests

▶

example
example, length=6

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.040 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 14:09:56 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:

Code: 14:10:13 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, p - q)

Code: 14:10:20 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, p - q)
    print(max_num)

Analysis

expand all Example tests

▶

example
example, length=6

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 14:10:49 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num,  - q)
    print(max_num)

Code: 14:10:56 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)
    print(max_num)

Analysis

expand all Example tests

▶

example
example, length=6

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 14:11:10 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)
    print(max_num)

Code: 14:11:19 UTC, py, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            print(q-p)
            max_num = max(max_num, q - p)
    print(max_num)

Analysis

expand all Example tests

▶

example
example, length=6

✘

RUNTIME ERROR
tested program terminated with exit code 1

0.036 s

RUNTIME ERROR, tested program terminated with exit code 1

stderr:

Invalid result type, int expected, <class 'NoneType'> found.

stdout:

Code: 14:11:33 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = -1

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)
    print(max_num)

Code: 14:11:49 UTC, py, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = 0

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)
    print(max_num)

    return max_num

Code: 14:11:54 UTC, py, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = 0

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)

    return max_num

Analysis

expand all Example tests

▶

example
example, length=6

✔

0.036 s

Code: 14:12:01 UTC, py, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = 0

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)

    return max_num

Analysis

expand all Example tests

▶

example
example, length=6

✔

0.036 s

Code: 14:12:04 UTC, py, final, score: 66

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    max_num = 0

    for i, p in enumerate(A):
        for q in A[i+1:]:
            max_num = max(max_num, q - p)

    return max_num

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N**2)

expand all Example tests

▶

example
example, length=6

✔

0.036 s

expand all Correctness tests

▶

simple_1
V-pattern sequence, length=7

✔

0.040 s

▶

simple_desc
descending and ascending sequence, length=5

✔

0.036 s

▶

simple_empty
empty and [0,200000] sequence

✔

0.036 s

▶

two_hills
two increasing subsequences

✔

0.036 s

▶

max_profit_after_max_and_before_min
max profit is after global maximum and before global minimum

✔

0.036 s

expand all Performance tests

▶

medium_1
large value (99) followed by short V-pattern (values from [1..5]) repeated 100 times

✔

0.124 s

▶

large_1
large value (99) followed by short pattern (values from [1..6]) repeated 10K times

✘

TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.

6.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.

▶

large_2
chaotic sequence of 200K values from [100K..120K], then 200K values from [0..100K]

✘

TIMEOUT ERROR
Killed. Hard limit reached: 8.000 sec.

8.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 8.000 sec.

▶

large_3
chaotic sequence of 200K values from [1..200K]

✘

TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.

7.000 s

TIMEOUT ERROR, Killed. Hard limit reached: 7.000 sec.