Codility – Page 7

Solution to Genomic-Range-Query by codility

21 Jan

Question: http://codility.com/demo/take-sample-test/genomic_range_query Question Name: GenomicRangeQuery This is a typical case that uses more space for less time.

def solution(S, P, Q):

result = []

DNA_len = len(S)

mapping = {"A":1, "C":2, "G":3, "T":4}

# next_nucl is used to store the position information

# next_nucl[0] is about the "A" nucleotides, [1] about "C"

# [2] about "G", and [3] about "T"

# next_nucl[i][j] = k means: for the corresponding nucleotides i,

# at position j, the next corresponding nucleotides appears

# at position k (including j)

# k == -1 means: the next corresponding nucleotides does not exist

next_nucl = [[-1]*DNA_len, [-1]*DNA_len, [-1]*DNA_len, [-1]*DNA_len]

# Scan the whole DNA sequence, and retrieve the position information

next_nucl[mapping[S[-1]] - 1][-1] = DNA_len-1

for index in range(DNA_len-2,-1,-1):

next_nucl[0][index] = next_nucl[0][index+1]

next_nucl[1][index] = next_nucl[1][index+1]

next_nucl[2][index] = next_nucl[2][index+1]

next_nucl[3][index] = next_nucl[3][index+1]

next_nucl[mapping[S[index]] - 1][index] = index

for index in range(0,len(P)):

if next_nucl[0][P[index]] != -1 and next_nucl[0][P[index]] <= Q[index]:

result.append(1)

elif next_nucl[1][P[index]] != -1 and next_nucl[1][P[index]] <= Q[index]:

result.append(2)

elif next_nucl[2][P[index]] != -1 and next_nucl[2][P[index]] <= Q[index]:

result.append(3)

else:

result.append(4)

return result

Solution to Passing-Cars by codility

20 Jan

Question: http://codility.com/demo/take-sample-test/passing_cars Question Name: PassingCars

def solution(A):

west = 0 # The number of west-driving cars so far

passing = 0 # The number of passing

for index in xrange(len(A)-1,-1,-1):

# Travel the list from the end to the beginning

if A[index] == 0: # A east-driving car

passing += west

if passing > 1000000000:

return -1

else: # A west-driving car

west += 1

return passing

Solution to Max-Counters by codility

19 Jan

Question: http://codility.com/demo/take-sample-test/max_counters Question Name: MaxCounters A straightforward solution is easy as following. But the expected worst-case time complexity cannot be guaranteed.

def solution(N, A):

result = [0]*N

for command in A:

if 1 <= command <= N:

result[command-1] += 1

else:

result[:] = [max(result)]*N

return result

We could use lazy-write to improve the performance. When receiving the max_counter command, we record the current-max value, … Read More »

Solution to Frog-River-One by codility

19 Jan

Question: https://codility.com/demo/take-sample-test/frog_river_one Question Name: FrogRiverOne If coding with C, bitmap is preferred to store which positions are covered.

def solution(X, A):

covered_time = [-1]*X # Record the time, each position is covered

uncovered = X # Record the number of uncovered position

for index in range(0,len(A)):

if covered_time[A[index]-1] != -1:

# This position is already covered

continue

else:

# This position is to be covered

covered_time[A[index]-1] = index

uncovered -= 1

if uncovered == 0:

# All positions are covered

return index

# Finally, some positions are not covered

return -1

Solution to Perm-Check by codility

19 Jan

Question: http://codility.com/demo/take-sample-test/perm_check Question Name: PermCheck This question is a simple variant of the counting question. The Python solution is:

def solution(A):

counter = [0]*len(A)

limit = len(A)

for element in A:

if not 1 <= element <= limit:

return 0

else:

if counter[element-1] != 0:

return 0

else:

counter[element-1] = 1

return 1

The Java solution is:

class Solution {

public static int solution(int[] A) {

int[] counter = new int [A.length];

for(int i= 0; i< A.length; i++){

if (A[i] < 1 || A[i] > A.length) {

// Out of range

return 0;

}

else if(counter[A[i]-1] == 1) {

// met before

return 0;

}

else {

// first time meet

counter[A[i]-1] = 1;

}

return 1;

}

Solution to Tape-Equilibrium by codility

16 Jan

Question: http://codility.com/demo/take-sample-test/tape_equilibrium Question Name: TapeEquilibrium The variable of head stores the sum of the heading part of the tape. And the variable of tail stores the sum of tailing part. Then, we move the index from 2nd position to the … Read More »

Solution to Perm-Missing-Elem by codility

16 Jan

Question: http://codility.com/demo/take-sample-test/perm_missing_elem Question Name: PermMissingElem or PermMissingElement The main challenge of this question is the XOR operations: X^X=0, and 0^X=X. Logically, the addition and subtraction operations also are able to do this work. But taking the overflow in computer into … Read More »

Solution to Frog-Jmp by codility

15 Jan

Question: https://codility.com/demo/take-sample-test/frog_jmp Question Name: FrogJmp This is a very easy question. If with C, one statement is enought. UPDATE on 2017/11/29: Codility changed Python from 2.X to 3.X. So the integer division needs to be updated to “//” from “/”. … Read More »

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...