Memoization in python - detailed explanation with video


  • 0

    VIDEO EXPLANATION

    This is deeply explained in this youtube video, but you can find the summary below

    Trivial, Broute-force solution

    • In __init__ constructor - do nothing special, just store nums in self.nums
    • In pick() - do 3 things:
      1. get the count of elements which match target
      2. find the random integer in the range(count), from 0 to count, not including count
      3. return the index of randomth occurrence of target in the array

    Sightly optimized solution with memoization

    if pick() is called multiple times with same values of target, then we don't need to re-calculate count each time. It's better to store it in a hash entry hash[target] after we did it first time, and on any following call to pick() - just return hash[target] if it's present.

    Solution

    from random import randrange
    class Solution(object):
    
        def __init__(self, nums):
            """
            :type nums: List[int]
            :type numsSize: int
            """
            self.memoCounts = {}
            self.nums = nums
    
        def getCount(self, target):
            # O(n)
            if target in self.memoCounts:
                return self.memoCounts[target]
                
            count = 0
            for el in self.nums:
                if el == target:
                    count += 1
            self.memoCounts[target] = count
            return count
            
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            count = self.getCount(target)
            randIndex = randrange(count) # [0...count)
            targetIndex = 0
    
            for i in xrange(len(self.nums)):
                if self.nums[i] == target:
                    if targetIndex == randIndex:
                        return i
                    targetIndex += 1
            
            return "bla"
    

    FINAL THOUGHTS

    I hope that the video was not too boring and long, but I made it to explain the whole process of solving this task as if you were coding on a whiteboard. This can be helpful for those who goes to onsite interviews soon. Anyways, please, leave comments here or below the video if you have them - I'll answer and improve! Good luck!


  • 0

    @3v3rgr33n Are you using random sampling? I think you are not. I don't know if using random sampling is necessary in this question.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.