SIgnal Classification - Women Technologists Codesprint - Hackerrank

signal_classification.py

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'classifySignals' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER_ARRAY freq_standard
#  2. INTEGER_ARRAY freq_signals
#

"""
2020 Feb 29 Sat  00:18:15 - Arjun Adhikari
Returns the closest value to target from (val1, val2).  
"""
def getClosest(val1, val2, target):

    if (target - val1 >= val2 - target):
        return val2
    else:
        return val1


def binarySearch(frequencies, end, key):

    """
    2020 Feb 29 Sat  00:19:08 - Arjun Adhikari
    Corner Search  
    """
    if (key <= frequencies[0]):
        return frequencies[0]
    if (key >= frequencies[end - 1]):
        return frequencies[end - 1]


    """
    2020 Feb 29 Sat  00:19:21 - Arjun Adhikari
    Binary Search Algorithm; returns the element or the closest element.  
    """
    i = 0
    j = end-1
    mid = 0

    while i < j:
        mid = int((i+j)/2)
        if frequencies[mid] == key:
            return frequencies[mid]
        elif (key < frequencies[mid]):

            """
            2020 Feb 29 Sat  00:19:58 - Arjun Adhikari
            If key is greater than previous to mid, return closest of two.  
            """
            if (mid > 0 and key > frequencies[mid - 1]):
                return getClosest(frequencies[mid - 1], frequencies[mid], key)

            j = mid

        else:
            """
            2020 Feb 29 Sat  00:20:57 - Arjun Adhikari
            If key is less than next element to mid, return closest of two.  
            """
            if (mid < end - 1 and key < frequencies[mid + 1]):
                return getClosest(frequencies[mid], frequencies[mid + 1], key)

            i = mid + 1

    return frequencies[mid]


def classifySignals(freq_standard, freq_signals):

    """
    2020 Feb 29 Sat  00:22:15 - Arjun Adhikari
    Sort the array.  
    """
    sorted_freq_standard = sorted(freq_standard)
    len_freq_standard = len(sorted_freq_standard)

    """
    2020 Feb 29 Sat  00:22:23 - Arjun Adhikari
    For storing the closest position.  
    """
    ans = []

    """
    2020 Feb 29 Sat  00:22:39 - Arjun Adhikari
    Hashing the initial position of the frequency standards.  
    """
    old_position = {}
    for i, signal in enumerate(freq_standard):
        old_position[signal] = i

    """
    2020 Feb 29 Sat  00:23:10 - Arjun Adhikari
    Gets the closest frequency type and maps with initial position of the frequency standards.  
    """
    for signal in freq_signals:
        element = binarySearch(sorted_freq_standard, len_freq_standard, signal)
        ans.append(old_position[element] + 1)

    return ans

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    q = int(first_multiple_input[1])

    f = list(map(int, input().rstrip().split()))

    F = list(map(int, input().rstrip().split()))

    ans = classifySignals(f, F)

    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')

    fptr.close()