# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---
from platform import python_version
from typing import List
from collections import defaultdict
print(python_version())

# 1.  We have two SORTED arrays of integers: A and B. A has empty slots at the end of it. It has exactly as many empty slots as there are elements in B. Your goal is to merge the elements from B into A so that array A contains all of the elements in sorted order. Optimize for speed and memory usage. 
#  
# Input: 
# A = [1, 2, 3, _, _, _, _ ] 
# B = [2, 4, 6, 100] 
#  
# Expected output: 
# A = [1, 2, 2, 3, 4, 6, 100] 
#
def merge(A: List, B: List) ->List:
    
    pointerA = 0
    for index in range(len(A)):
        if A[index] != None:
            pointerA = index
            
    pointerB, newIndex = len(B)-1, len(A)-1
    
    print(pointerA, A[pointerA])
    
    while pointerA >=0 and pointerB >= 0:
        if A[pointerA] > B[pointerB]:
            A[newIndex] = A[pointerA]
            newIndex -= 1
            pointerA -= 1
            
        else:
            #print(B[pointerB], pointerA[newIndex])
            A[newIndex] = B[pointerB]
            newIndex -= 1
            pointerB -= 1
            
    while pointerA >= 0:
        A[newIndex] = A[pointerA]
        pointerA -= 1
        newIndex -= 1
        
    while pointerB >= 0:
        A[newIndex] = B[pointerA]
        pointerB -= 1
        newIndex -= 1
        
    return A

merge([1, 3, 5, None, None, None, None], [2, 4, 6, 100])

# 2.  We have a list of various types of tasks to perform. Task types are identified with an identifier: task of type A, task of type B, task of type C, etc. Each task takes 1 time slot to execute, and once we have executed a task we need cooldown (parameter) time slots to recover before we can execute another task of the same type. However, we can execute tasks of other types in the meantime. The recovery interval is the same for all task types. We do not reorder the tasks: always execute in order in which we received them on input. 
#  
# Given a list of input tasks to run, and the cooldown interval, output the minimum number of time slots required to run them. 
#  
# Example 1: 
# Tasks: A, B, B, A 
# Recovery interval (cooldown): 2 
# Output: 7        
# (order is A _ _ A B _ A) 
#
# Example 2:
# Tasks: A, A, B, A, B
# Recovery interval (cooldown): 2
# Output: 8
# (order is A_ _ A B _ A B)
#
def insert(tasks: List, cooldown: int) -> int:
    if cooldown <= 0:
        return len(tasks)
    index, lookup, result = 0, defaultdict(int), 0
    
    while (index < len(tasks)):
        curr = tasks[index]
        if curr in lookup:
            prev = lookup[curr] 
        else:
            prev = -1
        
        if prev == -1 or result - prev > cooldown:
            lookup[curr]= result
            index += 1
        else:
            result += cooldown-(result-prev)+1
            lookup[curr]= result
            index += 1
            
        result += 1
            
    return result

insert(['A', 'A', 'B', 'A'], 2)
insert(['A', 'A', 'B', 'A', 'B'], 2)