.answers[1-3].md

Answers for the developer pre-test

answer1.py

def is_subset(arr1, arr2):
    """
    Verifies if arr2 is in arr1.
    Runs a single for loop that checks both from the back [0] and the front [len(arr2) -1]
    Best case is O(1) where arr2[0] is not in arr1 OR arr2[len(arr2) - 1] is not in arr2
    Worst case is O(n2/2) (n2 = len(arr2)) when is indeed a subset.
    """
    front_idx = len(arr2) - 1
    for back_idx, letter in enumerate(arr2):
        if back_idx > front_idx:
            break
        #O(1) + O(1) = O(2) = O(1)
        if letter not in arr1 or arr2[front_idx] not in arr1:
            return False
        
        front_idx = front_idx - 1

    return True


def main():
    arr1 = input()
    arr2 = input()
    issubset = is_subset(arr1, arr2)
    print(f'Is subset: {issubset}')

if __name__ == '__main__':
    main()

answer2.py

from datetime import datetime
import math
from numbers import Number

"""
A Wrapper for the cache map values.\n
Holds the value, the weight and the last access time of the value from the CacheMap
"""
class ValueHolder:

    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.last_access_time = datetime.now()


    def calc_score(self):
        """
        Returns the value's score based on the weight, the current_time and the last_access_time.
        """
        current_time = datetime.now()

        if current_time != self.last_access_time:
            diff = current_time - self.last_access_time
            return self.weight / math.log(diff.microseconds)
        else:
            return self.weight / -100


    def __repr__(self):
        return "{} with weight={}".format(self.value, self.weight)



class CacheMap:
    """
    CacheMap that holds values like a Python dict but with a weight.
    Internally uses a dict that inserts/removes ValueHolder objects.\n
    Attributes:
        cache_size (int): The initial size of the cache.
    """
    def __init__(self, cache_size):
        self.cache_size = cache_size
        self._internaldict_ = dict()


    def values(self):
        return [holder.value for holder in self._internaldict_.values()]


    def keys(self):
        return self._internaldict_.keys()
    

    def items(self):
        return self._internaldict_.items()
    

    def get(self, key):
        """
        Returns the key if exist and updates is last_access_time.\n
        Average time: O(1)
        Worst time: O(n)
        See https://wiki.python.org/moin/TimeComplexity#dict
        \nThrows KeyError if the key is not in the CacheMap
        """
        if key not in self._internaldict_:
            raise KeyError(f'[{key}] is not in the CacheMap')

        holder = self._internaldict_[key]
        holder.last_access_time = datetime.now()
        return holder.value
            

    def put(self, key, value, weight):
        """
        Inserts a new key with its value and weight.\n
        When the cache_size is reached, the least scored item is removed in favor of the new item.\n
        If the cache_size is reached but the key exist, the key is just replaced.\n
        Average: O(1). \n
        Worst: O(n) [generate all scores] + O(n) [worst case for deletion] + O(n) [set item on dict] = O(n)\n
        See https://wiki.python.org/moin/TimeComplexity#dict
        Throws ValueError if the weight is not a number.
        """
        if not isinstance(weight, Number):
            raise ValueError("The weight must be a number")

        if key not in self._internaldict_ and len(self._internaldict_) == self.cache_size:
            self._invalidate_least_scored_key()
        
        self._internaldict_[key] = ValueHolder(value, weight)
    

    def _invalidate_least_scored_key(self):
        # Get the scores as a dictionary of score:key of the internaldict items for easier deletion.
        scores = { holder.calc_score(): key for key, holder in self._internaldict_.items() }

        least_scored = min(scores.keys())
        least_scored_key = scores[least_scored]
        
        del self._internaldict_[least_scored_key]


def main():
    #Start a cache map with a size of 4
    cs = CacheMap(4)
    #Adding 4 values
    cs.put('peru', 10, 20)
    cs.put('venezuela', 3, 45)
    cs.put('colombia', 2, 3)
    cs.put('argentina', 12, 30)

    print('Values before cache reach')
    for key, value in cs.items():
        print(f'key={key}, value={value}')

    cs.put('caracas', 12, 30)
    print('Values after cache reach: ')
    for key, value in cs.items():
        print(f'key={key}, value={value}')

    #Accesing the value with `get` function
    print(cs.get('peru'))


if __name__ == '__main__':
    main()

answer3.md

This function:

function createArrayOfFunctions(y) {
    var arr = [];
    for(var i = 0; i<y; i++) {
        arr[i] = function(x) { return x + i; }
    }
    return arr;
}

Will succesfully generate y functions that will return the sum of x + i. But if we run the createArrayOfFunctions with y = 5 and run the created functions with x = 1 they will all return 6 instead of 1, 2, 3, 4 and 5 respectively. The bug is caused because the variable i is scoped for the whole loop. So when the created functions access it, they will access the last value that i hold, which was 6 in our case. The fix is quite simple: changing var with let for the i variable. This will create a variable i for each iteration of the loop. Here is the function fixed:

function createArrayOfFunctions(y) {
    var arr = [];
    for(let i = 0; i<y; i++) {
        arr[i] = function(x) { return x + i; }
    }
    return arr;
}