Skip to content

Instantly share code, notes, and snippets.

@1st
Last active May 19, 2022 19:58
Show Gist options
  • Save 1st/5278729 to your computer and use it in GitHub Desktop.
Save 1st/5278729 to your computer and use it in GitHub Desktop.
My answers for tests on http://codility.com that I passed for company http://toptal.com I use Python language to solve problems.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Test that I passed on codility.com for TopTal company
#
# Task #1
def binary_gap(N):
'''
A binary gap within a positive integer N is any maximal
sequence of consecutive zeros that is surrounded by ones
at both ends in the binary representation of N.
Args:
- N: integer within the range [1..2,147,483,647]
'''
bin_representation = bin(N)[2:]
max_gap = 0
gap_counter = 0
gap_started = False
for symbol in bin_representation:
if symbol == '1':
if gap_counter > max_gap:
max_gap = gap_counter
gap_counter = 0
gap_started = True
elif gap_started:
gap_counter += 1
return max_gap
print binary_gap(1041)
# Task #2
def count_div(A, B, K):
'''
Returns the number of integers within the range [A..B] that are divisible by K.
Used generators to save memory on large amounts of data.
Args:
- A: is an integer within the range [0..2,000,000,000]
- B: is an integer within the range [0..2,000,000,000] and A <= B
- K: is an integer within the range [1..2,000,000,000]
'''
divs_count = 0
for x in xrange(A, B + 1):
if (x % K) == 0:
divs_count += 1
return divs_count
print count_div(1, 200000000, 1000)
# Task #3
def triangle(A):
'''
Calculate triangel of integers, where sentense of numbers P, Q, R
correspond to next rules:
- P + Q > R
- Q + R > P
- R + P > Q
Args:
- A: list of integers, where we will search triangle
Return: 1 - if triangle exists, and 0 - otherwise
'''
A = tuple(enumerate(A))
for p, P in A:
for q, Q in A[p + 1:]:
for r, R in A[q + 1:]:
if (P + Q > R) and (Q + R > P) and (R + P > Q):
return 1
return 0
print triangle([10, 2, 5, 1, 8, 20])
@Odame
Copy link

Odame commented Feb 7, 2019

Alternate solution to Task #1

import re

def gap(number):
    binary_number = bin(number)[2:]
    zeros = re.findall(r'0+', binary_number)
    if binary_number[0] != '1':
        zeros = zeros[1:]
    if binary_number[-1] != '1':
        zeros = zeros[:-1:]
    if not zeros:
        return 0
    return len(max(zeros))

Copy link

ghost commented Aug 21, 2019

Solution for task 2: O(1)

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
// write your code in JavaScript (Node.js 8.9.4)

return Math.floor(B / K) - Math.floor((A - 1) / K)

}

@jonathonnordquist
Copy link

jonathonnordquist commented May 28, 2020

For number one Ruby two liner that took me far longer than it should have because I'm weak with regex:

def solution(n)
  split = n.to_s(2).scan(/(?=(10+1))/)
  split.any? ? split.flatten.sort.first.length - 2 : 0
end

@haveaguess
Copy link

Here is one-liner for the problem 1:

import re
def gap(number):
    return len(max(re.findall(r'0+',bin(number)[2:]),default=[]))

Doesn't this incorrectly return 5 for '11100000'?

len(max(re.findall(r'0+', '11100000'),default=[]))
5

@tik9
Copy link

tik9 commented Sep 21, 2020

Doesn't this incorrectly return 5 for '11100000'?

@haveaguess, you are correct, the oneliner with re for problem 1 does not work for edge cases. You need the checking for the one's as in the post written by Odame.

@p0rsche
Copy link

p0rsche commented Sep 25, 2020

binary gap

import re

def solution(n):
    bin_n = bin(n)[2:]
    gap = re.findall(r'(?=(10+1))', bin_n)
    return 0 if len(gap) == 0 else len(max(gap,key=len))-2

@aameerhamza1801
Copy link

Are you sure this was the toptal test and not you just practising the lessons. Mine was much more harder than this with optimal solutions involving dynamic programming.

@fatihtepekoy
Copy link

for task 3 another java imp

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

    Arrays.sort(A);
    for (int i = 0; i < A.length-2; i++) {
      long i1 = A[i];
      long i2 = A[i+1];
      long i3 = A[i+2];
      if((i1+i2>i3 && i2+i3>i1 && i3+i1>i2))
        return 1;

    }

    return 0;
  }
}

@106AbdulBasit
Copy link

These are the training question company asked the same questions which are provided in the traininng course of the codility website
my code for big binary gap

def DecimalToBinary(num):
S = bin(num).replace("0b", "")
res = [int(x) for x in str(S)]
print(res)
if res.count(1) < 2 or res.count(0) < 1:
print("its has no binary gap")
else:
positionof1 = [i for i,x in enumerate(res) if x==1]
print(positionof1)
differnce = [abs(j-i) for i,j in zip(positionof1, positionof1[1:])]
differnce[:] = [differnce - 1 for differnce in differnce]
differnce.sort()
print(differnce[-1])

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment