tech test

codility.py

# CyclicRotationSTART
# Rotate an array to the right by a given number of steps.
# https://github.com/Mickey0521/Codility-Python/blob/master/CyclicRotation.py
# https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/
def solution(A, K):
    N = len(A)
    # Calculate the effective number of rotations K by taking the modulus of K
    # with the length of the array N. This is because rotating an array of length N by N positions is equivalent to not rotating it at all.
    K = K % N  # Handle cases where K > N
    return A[-K:] + A[:-K]
  
  
  ########### 
  # odd occurrence
  # https://github.com/Mickey0521/Codility-Python/blob/master/OddOccurrencesInArray.py
  # https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/
  # use the exclusive OR ie the XOR operation to find the unpaired element in the array:
  """
  The XOR operation (^) has the following properties:

    a ^ a = 0 (any number XOR itself is 0)
    a ^ 0 = a (any number XOR 0 is itself)
    a ^ b ^ a = b (associative property)

Using these properties, we can find the unpaired element in the array by XORing 
all the elements together. The paired elements will cancel each other out, 
leaving only the unpaired

  """
  def solution(A):
    result = 0
    for num in A:
        result ^= num
    return result
  
  
  ### binarygap
  # https://github.com/Mickey0521/Codility-Python/blob/master/BinaryGap.py
  # https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
  # temp & 1 performs a bitwise AND operation between temp and 1, which effectively checks the least significant bit (LSB) of temp. If the LSB is 1, the result is 1; otherwise, it's 0.
  # temp >> 1 shifts the bits of temp to the right by 1, effectively dividing temp by 2. This allows us to process the next bit in the next iteration.
  def solution(N):
    # Initialize variables to track the current gap and the maximum gap
    current_gap = 0
    max_gap = 0
    
    # Flag to indicate whether we've seen the first 1
    start_counting = False

    temp = N
    
    # Loop until we've processed all bits of N
    while temp > 0: 
        # Check if the current bit is 1
        if (temp & 1 == 1): 
            # If we haven't started counting yet, set the flag
            if (start_counting == False):
                start_counting = True
            # If we have started counting, update the max gap and reset the current gap
            elif (start_counting == True):
                max_gap = max(max_gap, current_gap)
                current_gap = 0
        
        # If the current bit is 0 and we've started counting, increment the current gap
        elif (temp & 1 == 0):
            if(start_counting == True):
                current_gap += 1
        
        # Shift the bits of temp to the right by 1 (essentially dividing by 2)
        temp = temp >> 1
    
    # Return the maximum gap found
    return max_gap
  
  ########################             
            Time Complexity
  ######
  #
  # https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/
  # https://github.com/Mickey0521/Codility-Python/blob/master/FrogJmp.py
  # uses the ceiling division formula to calculate the minimal number of jumps. 
  # Add D - 1 to the distance to ensure that the frog will cover the entire distance, even if it's not a multiple of D.
  # Divide the result by D using integer division (//) to get the minimal number of jumps.
  # The + D - 1 part is used to perform ceiling division, which ensures that we get the smallest integer greater than or equal 
  #
  def solution(X, Y, D):
    return (Y - X + D - 1) // D
  
  # approach 2
 import math

def solution(X, Y, D):
    return math.ceil((Y - X) / D)
  
  ## PermMissingElem
  # https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/
  # https://github.com/Mickey0521/Codility-Python/blob/master/PermMissingElem.py
  def solution(A):
    # Calculate the length of the array A
    N = len(A)
    
    # Calculate the expected sum of numbers from 1 to N + 1
    # This is done using the formula for the sum of an arithmetic series
    expected_sum = (N + 1) * (N + 2) // 2
    
    # Calculate the actual sum of the numbers in the array A
    actual_sum = sum(A)
    
    # The missing number is the difference between the expected sum and the actual sum
    return expected_sum - actual_sum
  
  ## TapeEquilibrium
  #
  # https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
  # https://github.com/Mickey0521/Codility-Python/blob/master/TapeEquilibrium.py
  # A = [1, 2, 3, 3, 4]
def solution(A):
    # Calculate the total sum of the array
    total_sum = sum(A)
    
    # Initialize the minimum difference and the sum of the first part
    min_diff = float('inf')
    left_sum = 0
    
    # Iterate over the array, adding each element to the sum of the first part and calculating the difference between the two parts.
    # Iterate over the array
    for i in range(len(A) - 1):
        # Add the current element to the sum of the first part
        left_sum += A[i]
        
        # Calculate the difference between the two parts
        diff = abs(left_sum - (total_sum - left_sum))
        
        # Update the minimum difference
        min_diff = min(min_diff, diff)
    
    # Return the minimum difference
    return min_diff

  
##  FrogRiverOne
# https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/
# https://github.com/Mickey0521/Codility-Python/blob/master/FrogRiverOne.py
# This solution works by iterating over the array A and removing positions from 
# the set of needed positions as they are covered. When the set of needed positions
# is empty, it means that all positions have been covered, and the function returns the time. If 
#
# 
def solution(X, A):
    # Create a set to store the positions that need to be covered
    needed_positions = set(range(1, X + 1))
    
    # Iterate over the array A
    for index, position in enumerate(A):
        # If the position is in the set of needed positions, remove it
        if position in needed_positions:
            needed_positions.remove(position)
        
        # If all positions have been covered, return the time
        if not needed_positions:
            return index
    
    # If the loop finishes without covering all positions, return -1
    return -1
  #
  # Percheck  
  # https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/
  # https://github.com/Mickey0521/Codility-Python/blob/master/PermCheck.py
  """
  This solution works by creating two sets: one containing all elements from 1 to N (where N is the length of the array A), 
  and another containing all elements from the array A. If the two sets are equal, 
  it means that the array A is a permutation, and the function returns 1. Otherwise,
  it returns 0.
  """
  def solution(A):
    # Create a set containing all elements from 1 to N
    expected_set = set(range(1, len(A) + 1))
    
    # Create a set from the array A
    actual_set = set(A)
    
    # If the two sets are equal, return 1; otherwise, return 0
    return 1 if expected_set == actual_set else 0
  
  
  ### pending lesson 4 MaxCounters & MissingInteger
  
  #
  ###  lesson 5
   # pending
   # CountDiv, MinAvgTwoSlice
  # Passinng cars
  #https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/
  # https://github.com/Mickey0521/Codility-Python/blob/master/PassingCars.py
  
  def solution(A):
    # Initialize the count of passing cars and the count of eastbound cars
    passing_cars = 0
    eastbound_cars = 0
    
    # Iterate over the array A
    for car in A:
        # If the car is eastbound, increment the count of eastbound cars
        if car == 0:
            eastbound_cars += 1
        # If the car is westbound, increment the count of passing cars by the count of eastbound cars
        else:
            passing_cars += eastbound_cars
            # If the count of passing cars exceeds 1,000,000,000, return -1
            if passing_cars > 1000000000:
                return -1
    
    # Return the count of passing cars
    return passing_cars
  
  ### lesson 6
  # pending:
  # 
  # distinc, triangle, maxproductofthree
  # https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/
  # https://github.com/Mickey0521/Codility-Python/blob/master/NumberOfDiscIntersections_v2.py
  def solution(A):
    points = []
    for i, radius in enumerate(A):
        points.append((i - radius, 1))
        points.append((i + radius, 2))

    points.sort()

    intersecting_pairs = 0
    active_discs = 0

    for _, point_type in points:
        if point_type == 1:
            intersecting_pairs += active_discs
            active_discs += 1
        else:
            active_discs -= 1

        if intersecting_pairs > 10000000:
            return -1

    return intersecting_pairs
    
  ## Lesson 7 - Stacks and Queues
  # pending
  # fish, nesting , stonewall
  # https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/
  # https://github.com/Mickey0521/Codility-Python/blob/master/Brackets_v2.py
  # 
 #S = "{[()()]}"
#
def solution(S):
    stack = []
    bracket_map = {")": "(", "}": "{", "]": "["}

    for char in S:
        print('char', char)
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map:
            if not stack or stack.pop() != bracket_map[char]:
                return 0

    return 1 if not stack else 0
    
print(solution(S))
    
 ## lesson 8 - leader
#pending: equileader
# denominator
# https://app.codility.com/programmers/lessons/8-leader/dominator/
# https://github.com/Mickey0521/Codility-Python/blob/master/Dominator.py
# example array A = [3, 4, 3, 2, 3, -1, 3, 3] 
def solution(A):
    # Create a dictionary to store the count of each number
    count_dict = {}

    # Iterate through the array and count the occurrences of each number
    for num in A:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1

    # Find the number with the maximum count
    max_count = 0
    dominator = None
    for num, count in count_dict.items():
        if count > max_count:
            max_count = count
            dominator = num

    # Check if the dominator occurs more than half of the time
    # 1. Check if the array is empty
    if not A:
        return -1

    # Check if the dominator occurs more than half of the time
    if max_count > len(A) / 2:
        # Return the index of the dominator
        return A.index(dominator)
    else:
        # Return -1 if there is no dominator
        return -1
      
def solution(A):
    my_dictionary = {}

    for item in A:
        if item in my_dictionary:
            my_dictionary[item] += 1
        else:
            my_dictionary[item] = 1

    for index in range(len(A)):
        if my_dictionary[A[index]] > len(A) / 2:
            return index

    return -1