Oursky interview

answer1.py

"""
list to Set: O(n)
Check if b in a: O(len(b))

so the the time complexity will be O(2n + len(b)) : O(n)

"""
class Solution:
  def isSubset(self, a, b):
    return set(b).issubset(set(a))
    
print(Solution().isSubset(['A', 'B', 'C', 'D', 'E'], ['A', 'E', 'D']))
print(Solution().isSubset(['A','B','C','D','E'], ['A','D','Z']))

answer2.py

"""
  get(): O(1)
  it's an access to a hash table(dict in python)

  put(): O(n) 
  O(1) while current size of the cache is smaller than the capacity of the cache
  worest case is O(n) since it have to calculate the score for all data (n)
"""
import time
import math

class Cache:
  def __init__(self, maxSize):
    self.maxSize = maxSize
    self.size = 0
    self.data = {}
    self.lastAccessTime = {}
    self.weight = {}
  
  def get(self, key):
    self.lastAccessTime[key] = time.time()
    return self.data[key] if key in self.data else -1

  def getLeastScoreKey(self):
    scores = {} 
    currentTime = time.time()
    for key in self.data.keys():
      lastAccessTime = self.lastAccessTime[key]
      weight = self.weight[key]

      if(currentTime != lastAccessTime):
        scores[key] = (weight/math.log(currentTime - lastAccessTime))
      else:
        scores[key] = weight/-100
    return min(scores, key=scores.get)

  def put(self, key, value, weight):
    if(self.size < self.maxSize):
      self.size += 1
    else:
      leastScoreKey = self.getLeastScoreKey()
      del self.data[leastScoreKey]
      del self.weight[leastScoreKey]
      del self.lastAccessTime[leastScoreKey]
    self.data[key] = value
    self.weight[key] = weight
    self.lastAccessTime[key] = time.time()

cache = Cache(3)
cache.put('go', 1, 1)
cache.put('goagain', 2, 100)
cache.put('goagain2', 3, 100)
print(cache.get('go'))
cache.put('goagain3', 4, 100)
print(cache.get('go'), cache.get('goagain'), cache.get('goagain2'), cache.get('goagain3'))

answer3.md

Even though each function in arr is a closure but all of them are refering to the same reference of i. So whenever i increment, it also affect all elements in arr.

To fix it simply change var i = 0 to let i = 0. since the keyword let works in block scope instead of functional scope in the var keyword. So each i generated in the for loop have their own context.

answer4.py

"""
Time Complexity: Sorting O(nlogn) + Single pass iteration O(n)
Space: New sorted nums O(n) + Constant O(1)
"""
class Solution:
  def nextFibonacci(self, nums):
    sortedNums = list.copy(nums) 
    sortedNums.sort()

    res = []
    f2 = f1 = 1
    while(sortedNums):
      f0 = f1 + f2
      if(f0 > sortedNums[0]):
        idx = nums.index(sortedNums.pop(0))
        res.insert(idx, f0)
      f2 = f1
      f1 = f0
    return res

print(Solution().nextFibonacci([1,22,9]))