My Attempts at Various Programming Interview Questions

task1.py

# Interview: "https://www.youtube.com/watch?v=10WnvBk9sZc"

"""
Take two strings
Begin at index 0 on string one
Iterate over one of the strings until you find a character in both strings
Append it to subsequence and cut off remainder in other string

Error:
* Iterating over first string selects longest substring from first string
- Fix: Find the character which appears in both strings at the lowest index
       in either stirng. then iterate over that string first.

Optional Optimisations
* shared_chars is calculated in first_shared_character_compare but abandoned
  and then redetermined in find longest_subsequence. Wasted Work.
* 

"""

def first_shared_character_compare(s1: str, s2: str) -> int:
    """Finds in which string the first character which exists in both strings
    exists.

    Returns
    -------
    * 0 when no characters are shared between the two strings
    * 1 when the first shared character appears earliest in s1
    * 2 when the first shared character appears earliest in s2

    """
    char_to_index_tuples  = lambda X: (s1.find(X), s2.find(X)) # X is char
    
    shared_chars = map(char_to_index_tuples, filter(s2.__contains__, s1))
    shared_chars = sorted(shared_chars, key=sum) # sort by smallest total

    if len(shared_chars) == 0: return 0 # no shared characters
    else:
        s1_shared_char_index, s2_shared_char_index = shared_chars[0]

        if s1_shared_char_index <= s2_shared_char_index: return +1
        else:                                            return -1

def longest_subsequence(s1: str, s2: str) -> str:
    substring = '' # initial return value is an empty string
    comparison_eval = first_shared_character_compare(s1, s2)

    if   comparison_eval > 0: s1, s2 = s1, s2
    elif comparison_eval < 0: s1, s2 = s2, s1
    else: return substring # no shared chars
    
    for s1_index, char in enumerate(s1, start=0):
        index_of_char_in_s2 = s2.find(char)

        if index_of_char_in_s2 != -1:
            substring += char # add found char

            if index_of_char_in_s2 == len(s2)-1:
                break # end when s2 completed
            
            s2 = s2[index_of_char_in_s2+1:]

    return substring

if __name__ == '__main__':
    def test_all(method, tests):
        for s1, s2, result in tests:
            m_result = method(s1, s2)
            
            if m_result != result:
                print(f'Test Failed "{s1}" + "{s2}" => "{m_result}", Not "{result}"')
            else: print(f'Test Passed "{s1}", "{s2}" => "{result}"')

    test_all(longest_subsequence, [
        ("ABAZDC", "BACBAD",  "ABAD"),
        ("AGGTAB", "GXTXAYB", "GTAB"),
        ("aaaa",   "aa",      "aa"),
        ("",       "",        ""),
        ("ABBA",   "ABCABA",  "ABBA")
    ])

task2.py

# Interview: https://www.youtube.com/watch?v=GJdiM-muYqc

"""
Iterate over string
if char not in list: Store iterated character in list
else: char already exists, return character

"""

def first_repeating_char(string):
    iterated = []

    for char in string:
        if char not in iterated:
            iterated.append(char) # remember
        else: return char # 2nd discovery

    return None # no repeated characters

for string in ("ABCA", "ABBA", "BCABA", "ABC"):
    print("{0} => {1}".format(string, first_repeating_char(string)))

task3.py

# Interview: https://www.youtube.com/watch?v=XKu_SEDAykw

"""
Iterate over list in 2 dimensions
ensure diagonal line in [][] is skipped
check if they add to give desired num
if true: return pass
else: return fail

"""

#region sorted solutions
def sum_exists__mine(nums, sum):
    for X, numX in enumerate(nums, start=0):
        for Y, numY in enumerate(nums, start=0):
            if X != Y and numX + numY == sum:
                return True # sum pair found

    return False # nums exhausted, failed.

def sum_exists__other_guys(nums, sum):
    start, end = 0, len(nums)-1

    while start != end:
        x = nums[start] + nums[end]

        if   x > sum: end   -= 1
        elif x < sum: start += 1
        else: return True # x == sum

    return False # sum not found
#endregion

if __name__ == "__main__":
    def test(collections, desired_sum, method):
        for passed, collection in collections:
            result = method(collection, desired_sum)

            if result == passed:
                print(f"Method Passed Attempt {{{collection}, {desired_sum}}}")
            elif result: # result true, passed isn't
                print(f"Method Gave Pass For {{{collection}, {desired_sum}}} When It Should've Failed")
            else: # passed true, result isn't
                print(f"Method Failed For {{{collection}, {desired_sum}}} When It Should've Passed")
    
    desired_sum = 8

    tests = (
        (False, [1, 2, 3, 9]),
        (True,  [1, 2, 4, 4]),
        (True,  [2, 3, 5, 9]),
        (True,  [1, 4, 4, 9]),
        (False, [1, 1, 1, 1])
    )

    methods = (
        ("Mine", sum_exists__mine),
        ("Other Guys", sum_exists__other_guys)
    )

    for msg, method in methods:
        print('='*13, f"Attempting Test {msg}", '='*13)
        test(tests, desired_sum, method)
        print("\n") # leave 2 line breaks

task4.py

# Interview: https://www.youtube.com/watch?v=uQdy914JRKQ

from typing import List

def add_to_list(nums: List[str], value: int, BASE: int=10):
    index = len(nums) - 1 # begin at smallest value

    while value != 0: # until value exhausted
        if index < 0:
            """When Index Value Negative, Expand Into
            Higher Base 10 Values By Inserting Number
            to Start of the Numbers List at index=0"""
            power_one_remainder = value % BASE
            # value at smallest power of the base
            
            nums.insert(0, power_one_remainder) # add to start of nums
            value = (value - power_one_remainder) // BASE # no loss
            # then shorten value by the factor of the base after remainder
        else:
            index_value = nums[index] # get num at index
            incremented_value = index_value + value # add

            if incremented_value >= 10:
                incremented_base_remainder = incremented_value % BASE
                nums[index] = incremented_base_remainder # add less than base remainder
                value = int((incremented_value-incremented_base_remainder) // BASE)
            else:
                nums[index] += value # add value
                value = 0 # addition value exhausted

            index -= 1 # move to bigger base index

    return nums

if __name__ == '__main__':
    char_map_base_10 = list(map(str, range(0, 10)))
    num_list_to_num = lambda list: int("".join(map(lambda X: char_map_base_10[X], list)))

    def test(tests, method):
        for array, add_value, result in tests:
            method_result = method(array.copy(), add_value)
            method_result = num_list_to_num(method_result)

            if result == method_result:
                print("Test Passed: {0} + {1} = {2}".format(
                    num_list_to_num(array), add_value, method_result
                ))
            else:
                print("Test Failed: {0} + {1} = {2}, Not {3}".format(
                    num_list_to_num(array), add_value, method_result, result
                ))
    
    tests = (
        ([9, 9, 9, 9, 9],  +1, 100000),
        ([0, 0, 0, 0, 1],  +1, 2),
        ([1, 2, 3, 4, 0],  +5, 12345),
        ([0, 0, 0, 0, 0], +10, 10),
        ([0, 2, 0, 0, 0], +27, 2027),
    )

    test(tests, add_to_list)

task5.py

# Interview: https://www.youtube.com/watch?v=qli-JCrSwuk&list=PLBZBJbE_rGRVnpitdvpdY9952IsKMDuev&index=2&t=0s

"""Enumerate over message. Add one for every character in message.
Add one for every character + the next character which as an int is within range.
"""

# char_map = dict(zip("ABCDEFGHIJKLMNOPQRSTUVWXYZ ", map(str, range(1, 27)))) # value -> key

def num_ways(encrypted_msg, char_range=range(1, 27)):
    counter = 0 # len(encrypted_msg) if char_range spans at least 1-9. For now leave as 0.
    max_char_range_length = len(str(max(char_range.start, char_range.stop))) # assumed +ve values

    check_additional_values_in_range = lambda index, X: index+X < len(encrypted_msg) and int(encrypted_msg[index+X]) in char_range 
    
    for msg_index, char in enumerate(encrypted_msg, 0):
        for index_increment in range(0, max_char_range_length):
            if check_additional_values_in_range(msg_index, index_increment):
                counter += 1 # append when all continuous values are within range

    return counter

if __name__ == '__main__':
    def test(tests, method):
        for encrypted, expected_result in tests:
            result = method(encrypted)

            if result == expected_result:
                print("Test Passed: {0} => {1}".format(
                    repr(encrypted), result
                ))
            else:
                print("Test Failed: Method Gave {0} => {1}, Not {2}".format(
                    repr(encrypted), result, expected_result
                ))

    tests = (
        ('12345', 9),
        ('', 0),
        ('5', 1),
        ('123', 5)
    )

    test(tests, num_ways)

task6.py

# Interview: https://www.youtube.com/watch?v=qRNB8CV3_LU&index=12&list=PLBZBJbE_rGRVnpitdvpdY9952IsKMDuev

def longest_char_subsequence(string):
    counters = {}

    for X, char in enumerate(string, 0):
        counter = 1

        while X+counter < len(string) and string[X+counter] == char:
            counter += 1 # add until string exhausted or char changed

        counters[char] = max(counter, counters.get(char, 0))
 
    biggest = max(counters.values())

    for key, value in counters.items():
        if value == biggest: return {key:value}


print(longest_char_subsequence('AABCDDBBBEA'))