# Codility linked list

Recently, during interview to some company, I got tested by Codility service. And here is my performance results. Generally this is copy&paste from their email. Hope this can be helpful for others who want to see what this tests are.

This is overal performance table:

 Task name Correctness Performance Task score 1 PtrListLen 100 not assessed 100 2 BugfixingLeaderSorted 100 not assessed 100 3 DeepestPit 55 66 60 4 CountMultiplicativePairs 80 87 83 Total 84 N/A 343 / 400

Danh mục bài viết

## PtrListLen – problem description

A pointer is called a linked list if:

· it is an empty pointer (it is then called a terminator or an empty list); or

· it points to a structure (called a node or the head) that contains a value and a linked list (called the tail).

The length of a list is defined as the total number of nodes it contains. In particular, an empty list has length 0.

For example, consider the following linked list:

A -> B -> C -> D ->

This list contains four nodes: A, B, C and D. Node D is the last node and its tail is the terminator. The length of this list is 4.

Assume that the following declarations are given:

classIntList(object):
value=0
next=None

Write a function:

def solution(L)

that, given a non-empty linked list L consisting of N nodes, returns its length.

For example, given list L shown in the example above, the function should return 4.

Assume that:

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

· list L does not have a cycle (each non-empty pointer points to a different structure).

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

Copyright 20092015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

### Tests

Score: 100 of 100

Estimated time complexity: None

 Test name Running time Result exampleexample, length=4 0.060s OK extreme_single_doublelength=1 0.044s OK three_elemslength=3 0.044s OK twenty_elementslength=20 0.044s OK mediumlength=93 0.044s OK medium2length=999 0.044s OK 1k_elementslength=1,000 0.044s OK quite_longlength=4,000 0.052s OK longlength=5,000 0.056s OK

### Solution (language: Python)

# you can use print for debugging purposes, e.g.
# print “this is a debug message”
def solution(L):
# write your code in Python 2.7
count = 0
while L:
count = count + 1
L = L.next
return count

## BugfixingLeaderSorted – problem description

A non-empty zero-indexed array A consisting of N integers and sorted in a non-decreasing order is given. The leader of this array is the value that occurs in more than half of the elements of A.

You are given an implementation of a function:

def solution(A)

that, given a non-empty zero-indexed array A consisting of N integers, sorted in a non-decreasing order, returns the leader of array A. The function should return 1 if array A does not contain a leader.

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

A = 2
A = 2
A = 2
A = 2
A = 2
A = 3
A = 4
A = 4
A = 4
A = 6

the function should return 1, because the value that occurs most frequently in the array, 2, occurs five times, and 5 is not more than half of 10.

Given array A consisting of five elements such that:

A = 1
A = 1
A = 1
A = 1
A = 50

the function should return 1.

Unfortunately, despite the fact that the function may return expected result for the example input, there is a bug in the implementation, which may produce incorrect results for other inputs. Find the bug and correct it. You should modify at most three lines of code.

Assume that:

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

· each element of array A is an integer within the range [0..2,147,483,647];

· array A is sorted in non-decreasing order.

Complexity:

· expected worst-case time complexity is O(N);

· expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 20092015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

### Tests

Score: 100 of 100

Estimated time complexity: None

 Test name Running time Result example1first example test 0.044s OK example2second example test 0.044s OK simple1values from a continuous range 0.044s OK simple20s/1s only 0.044s OK singleone element 0.044s OK two_valuestwo different values 0.044s OK extreme_big_valuesmin/max values only 0.044s OK medium_1small sequence repeated many times 0.044s OK medium_2no leader and small sequence with values from a continuous range 0.044s OK cyclic_sequenceno leader and small sequence repeated many times 0.044s OK medium_randomrandom sequences 0.044s OK largetwo different values, length = ~100,000 0.104s OK large_rangevalues from a continuous range, length = ~100,000 0.108s OK

### Solution (language: Python)

def solution(A):
n = len(A)
L = [-1] + A
count = 0
pos = (n + 1) // 2
candidate = L[pos]
for i in xrange(1, n + 1):
if (L[i] == candidate):
count = count + 1
if (2*count > n):
return candidate
return -1

## DeepestPit – problem description

A non-empty zero-indexed array A consisting of N integers is given. A pit in this array is any triplet of integers (P, Q, R) such that:

· 0 P < Q < R < N;

· sequence [A[P], A[P+1], …, A[Q]] is strictly decreasing,
i.e. A[P] > A[P+1] > … > A[Q];

· sequence A[Q], A[Q+1], …, A[R] is strictly increasing,
i.e. A[Q] < A[Q+1] < … < A[R].

The depth of a pit (P, Q, R) is the number min{A[P] A[Q], A[R] A[Q]}.

For example, consider array A consisting of 10 elements such that:

A = 0
A = 1
A = 3
A = -2
A = 0
A = 1
A = 0
A = -3
A = 2
A = 3

Triplet (2, 3, 4) is one of pits in this array, because sequence [A, A] is strictly decreasing (3 > 2) and sequence [A, A] is strictly increasing (2 < 0). Its depth is min{A A, A A} = 2. Triplet (2, 3, 5) is another pit with depth 3. Triplet (5, 7, 8) is yet another pit with depth 4. There is no pit in this array deeper (i.e. having depth greater) than 4.

Write a function:

def solution(A)

that, given a non-empty zero-indexed array A consisting of N integers, returns the depth of the deepest pit in array A. The function should return 1 if there are no pits in array A.

For example, consider array A consisting of 10 elements such that:

A = 0
A = 1
A = 3
A = -2
A = 0
A = 1
A = 0
A = -3
A = 2
A = 3

the function should return 4, as explained above.

Assume that:

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

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

Complexity:

· expected worst-case time complexity is O(N);

· expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 20092015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

### Tests

Score: 60 of 100

 Test name Running time Result exampleexample test 0.044s OK extreme_no_pitsmall test cases 0.044s WRONG ANSWERgot -1 expected 1 extreme_depth 0.044s WRONG ANSWERgot -1 expected 200000000 simple1no pit 0.044s WRONG ANSWERgot -1 expected 1 simple2one pit 0.044s WRONG ANSWERgot -1 expected 50 useruser-defined test case 0.044s OK simple3`vulcano’ shape 0.044s OK retriesretries 0.044s OK medium1medium correctness test 0.104s OK medium_pitmedium test one pit 0.044s OK large_pit_1large test one pit 1 0.148s WRONG ANSWERgot 43265 expected 43287 large_pit_2large test one pit 2 0.152s WRONG ANSWERgot 432950 expected 433170 big_pit_1big test one pit 1 0.120s OK big_pit_2big test one pit 1 0.132s OK big3_1large random test 0.424s OK big3_2big random test 1.336s OK

### Solution (language: Python)

# you can use print for debugging purposes, e.g.
# print “this is a debug message”
def solution(A):
deepest = 0
pit = lambda p, q, r: min(A[p] – A[q], A[r] – A[q])
p = 0
r = -1
q = -1
l = len(A)
for i in xrange(0, l):
if q<0 and A[i]>=A[i-1]:
q = i -1
if (q>=0 and r<0) and (A[i]<=A[i-1] or i+1==l):
r = i-1
deepest = max(deepest, pit(p, q, r))
p = i-1
q = -1
r = -1
return deepest if deepest else -1

## CountMultiplicativePairs – problem description

Zero-indexed arrays A and B consisting of N non-negative integers are given. Together, they represent N real numbers, denoted as C, …, C[N1]. Elements of A represent the integer parts and the corresponding elements of B (divided by 1,000,000) represent the fractional parts of the elements of C. More formally, A[I] and B[I] represent C[I] = A[I] + B[I] / 1,000,000.

For example, consider the following arrays A and B:

A = 0 B = 500,000
A = 1 B = 500,000
A = 2 B = 0
A = 2 B = 0
A = 3 B = 0
A = 5 B = 20,000

They represent the following real numbers:

C = 0.5
C = 1.5
C = 2.0
C = 2.0
C = 3.0
C = 5.02

A pair of indices (P, Q) is multiplicative if 0 P < Q < N and C[P] * C[Q] C[P] + C[Q].

The above arrays yield the following multiplicative pairs:

· (1, 4), because 1.5 * 3.0 = 4.5 4.5 = 1.5 + 3.0,

· (1, 5), because 1.5 * 5.02 = 7.53 6.52 = 1.5 + 5.02,

· (2, 3), because 2.0 * 2.0 = 4.0 4.0 = 2.0 + 2.0,

· (2, 4) and (3, 4), because 2.0 * 3.0 = 6.0 5.0 = 2.0 + 3.0.

· (2, 5) and (3, 5), because 2.0 * 5.02 = 10.04 7.02 = 2.0 + 5.02.

· (4, 5), because 3.0 * 5.02 = 15.06 8.02 = 3.0 + 5.02.

Write a function:

def solution(A, B)

that, given zero-indexed arrays A and B, each containing N non-negative integers, returns the number of multiplicative pairs of indices.

If the number of multiplicative pairs is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given:

A = 0 B = 500,000
A = 1 B = 500,000
A = 2 B = 0
A = 2 B = 0
A = 3 B = 0
A = 5 B = 20,000

the function should return 8, as explained above.

Assume that:

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

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

· each element of array B is an integer within the range [0..999,999];

· real numbers created from arrays are sorted in non-decreasing order.

Complexity:

· expected worst-case time complexity is O(N);

· expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 20092015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

### Tests

Score: 83 of 100

Estimated time complexity: O(N)

 Test name Running time Result exampleexample test 0.044s OK simple_diagonalsimple test with A = B 0.052s OK simple_equalitysimple test with multiple equalities to be counted 0.052s OK mulitple_zerosmany zeros 0.052s WRONG ANSWERgot 1 expected 2 extreme_emptyempty sequence + [1.5, 3.01] 0.044s WRONG ANSWERgot -1 expected 0 extreme_singlesingleton sequence + [1.4, 3.5] 0.044s OK doubles2-element sequences, precise calculation 0.040s OK precision_smallprecise calculation, N = 400 0.044s OK geometric_smallgeometric sequence, N = 111 0.044s OK arithmetic_smallarithmetic sequence, N = ~300 0.044s OK random_smallrandom sequence, N = ~600 0.044s OK geometric_mediumgeometric sequence, N = ~9,000 0.064s OK random_mediumrandom sequence, N = ~10,000 0.064s OK arithmetic_mediumarithmetic sequence, N = 20,000 0.088s OK geometric_largegeometric sequence, N = ~60,000 0.188s OK arithmetic_largearithmetic sequence, N = 90,000 0.244s OK random_largerandom sequence, N = 100,000 0.272s OK extreme_largebig numbers, N = 100,000 0.280s OK extreme_zerosalmost all zeros, N <= 100,000 0.224s WRONG ANSWERgot 0 expected 1000000000

### Solution (language: Python)

def solution(A, B):
# write your code in Python 2.7
if not len(A) or not len(B) or len(A) != len(B):
return -1
# make C and filter all values <= 1
C = [A[i]+float(B[i])/1000000 for i in range(len(A)) if A[i]+float(B[i])/1000000 > 1]
C.sort()
result = 0
p = 0 # position
l = len(C) – 1
while l > p:
res = C[l] / (C[l] – 1)
while (p < l and C[p] < res):
p = p + 1
if p == l:
break
result = result + (l-p)
if result > 1000000000:
return 1000000000
l = l-1
return result

Bài viết được chia sẻ bởi kinhnghiem.com