Grokking LinkedIn Coding Interview

0% completed

​
Hidden Document
Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content Hidden Document Content

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

Why is this check done in the recursive helper function instead of in the count_change function? denominations list never changes, right?

n = len(denominations) if n == 0

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def countChange(self, denominations, total):
    
    def dp(index, acc, memo):
      if (index, acc) in memo:
        return memo[(index, acc)]

      if acc == total:
        return 1

      if acc > total or index == len(denominations):
        return 0

      with_item = dp(index, acc + denominations[index], memo) 
      without_item = dp(index + 1, acc, memo)

      result = with_item + without_item
      memo[(index, acc)] = result

      return result
    
    return dp(0, 0, {})
Online Courses

Online Courses

· 4 months ago

class Solution:
  def countChange_memo(self, denominations, total):
    n = len(denominations)

    memo = {}

    def change(idx, current_sum):
      print(idx, current_sum)
      if current_sum == total:
        return 1
      if idx == n or current_sum > total:
        return 0
      
      key = (idx, current_sum)
      if key in memo:
        return memo[key]

      count = change(idx + 1, current_sum)
      count += change(idx, current_sum + denominations[idx])

      memo[key] = count

      return count

    return change(0, 0)

  def countChange_2d_dp(self, denominations, total):
    n = len(denominations)

    # state
    dp =[[0] * (total + 1) for _ in range(n + 1)]

    # base case
    for i in range(n + 1):
      dp[i][total] = 1

    # recursion relation
    for