Oursky PT 2020 (Yong En)

answer1.js

function questionOne(first_arr, second_arr) {
  var first_set = new Set(first_arr);
  var second_set = new Set(second_arr);

  var is_subset = true;
  second_set.forEach(val => {
    if (!first_set.has(val)) {
      is_subset = !is_subset;
    };
  });

  return is_subset;
}


//TIME COMPLEXITY
//It is O(n). Assuming both first and second array are n size:
//Converting the two arrays into their respective sets is actually an iteration operation = 2n
//Checking that every unique value in second array is contained in first array is about iterating through the second set ~= n
//(strictly speaking, less than or equal to n as they contain the unique numbers in the original array).
//Total number of operations is ~3n, which is O(n) as it is a linear multiple of n. 

answer2.js

//ASSUMPTIONS
// Limit is in terms of number of key-value pairs that can be contained
const limit = 5;

//CODE

//CACHE
//cache uses map object which holds key-value pairs. time cache is also the same data structure, 
//used to store the last accessed/added time of the key value pair
var cache = new Map();
var time_cache = new Map();

//FUNCTION THAT FINDS THE LEAST SCORED KEY IN THE CACHE GIVEN CURRENT TIME 
function findLeastScore(time) {
  var score = Infinity;
  var lowest_key;

  cache.forEach((val, key) => {
    const {value, weight} = val;
    const last_access_time = time_cache.get(key);
    var this_score;
    
    if (time != last_access_time) {
      this_score = weight / Math.log(time - last_access_time);
    } else {
      this_score = weight / -100;
    };

    if (this_score < score) {
      score = this_score;
      lowest_key = key;
    };

  })

  return lowest_key;
}


//GET FUNCTION TO RETRIEVE VALUE GIVEN KEY
function get(key) {
  const time = Math.floor(Date.now()/1000);
  if (time_cache.has(key)) {
    time_cache.set(key, time);
  };

  return cache.has(key) ? cache.get(key).value : -1;
}

//PUT FUNCTION TO ADD/OVERWRITE VALUE GIVEN KEY. ITS WEIGHT IS ALSO STORED HERE WHICH WILL BE USED TO COMPUTE ITS 'SCORE'
function put(key, value, weight) {
  const payload = {value, weight};
  const time = Math.floor(Date.now()/1000);
  
  if (!cache.has(key) && cache.size === limit) {
    const lowest_key = findLeastScore(time);
    cache.delete(lowest_key);
    time_cache.delete(lowest_key);
  }; 

  time_cache.set(key, time);
  cache.set(key, payload);
}


//COMPUTATIONAL COMPLEXITY 
//get(key): O(1) complexity. The number of operations is fixed regardless of the existing size of cache. 
//put(key, value, weight): O(n). It has O(1) complexity when the cache has not reached its capacity/when the key-value pair to be 
//added already exist in the cache. However, when either of these conditions are not met, the lowest scored key has to be removed
//to make way for the new key-value pair. The function iterates through the cache to calculate the score for each key, causing it
//to incur n number of operations, with n being the limit of the cache - hence O(n) comeplxity.



//*Some helper functions to test out the cache in an interactive console like REPL

// function makeid(length) {
//    var result           = '';
//    var characters       = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
//    var charactersLength = characters.length;
//    for ( var i = 0; i < length; i++ ) {
//       result += characters.charAt(Math.floor(Math.random() * charactersLength));
//    }
//    return result;
// }

// function getRandomArbitrary(min, max) {
//   return Math.floor(Math.random() * (max - min) + min);
// }

// put(makeid(5),getRandomArbitrary(1, 100),getRandomArbitrary(1000, 10000))

answer3.js

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

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

//The way to correct it is just to change 'var' to 'let'. The reason is because 'var' is function scoped, whereas 'let' is block scoped. 
//The given original function is actually equivalent to:

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

//which means, there is only one, same variable i in the whole scope, and all the anonymous functions inserted into the array were bound 
//to the same variable (which hence takes on the same value that was assigned in the last loop iteration).

//However, when using 'let', since it is block scoped, that means every time the loop runs, the variable i is actually declared as if it 
//is a new variable (ie. variable i is not being overwritten by the declaration that happens in the next loop). As such, each anonymous function 
//inserted into the array is bound to its own variable, which takes on the correct value assigned to it in its own loop.