<jupyter_start><jupyter_text>**Amazon Fresh Promotion**<jupyter_code>def fresh_promotion(codeList,shoppingCart):

    if not codeList: return 1 
    if not shoppingCart: return 0

    i = 0
    j = 0

    while i<len(codeList) and j+len(codeList[i])<=len(shoppingCart):

          match = True
          
          for k in range(len(codeList[i])):
              #print(codeList[i][k],shoppingCart[j+k])
              if codeList[i][k]!='anything' and codeList[i][k]!=shoppingCart[j+k]:
                  match = False
                  break

          if match:
            j+=len(codeList[i])
            i+=1
          else:
            j+=1
    #print(i)
    return 1 if i==len(codeList) else 0 
codeList = [['apple', 'apple'], ['banana', 'anything', 'banana']] 
shoppingCart = ['orange', 'apple', 'apple', 'banana', 'orange', 'banana']

codeList1 = [['apple', 'apple'], ['apple', 'apple', 'banana']] 
shoppingCart1 = ['apple', 'apple', 'apple', 'banana']
fresh_promotion(codeList1,shoppingCart1)<jupyter_output>apple apple
apple apple<jupyter_text>**Substrings of size K with K distinct chars**<jupyter_code># Time Complexity: O(n)
# Space Complexity: O(1)
def unique_character_strings(s,k):
    if not s: return []

    res = set()
    start = 0
    dic = {}

    for end, char in enumerate(s):

        if char in dic and dic[char]>=start:
          start=dic[char]+1

        dic[char] = end

        if end-start+1==k:
          res.add(s[start:start+k])
          start+=1


    return res
s = "awaglknagawunagwkwagl"
k = 4
s1 = "abcabc"
k1 = 3
s2 = "awaglk" 
k2 = 4
unique_character_strings(s2,k2)
unique_character_strings(s1,k1)
unique_character_strings(s,k)<jupyter_output><empty_output><jupyter_text>**Substrings of size K with K-1 distinct characters**<jupyter_code># Time Complexity: O(n)
# Space Complexity: O(1)
def unique_character_strings1(s,k):
    if not s: return []

    res = set()
    start = 0
    dic = {}

    for end, char in enumerate(s):

        if char in dic and dic[char][0]>=start and dic[char][1]==2:
          start=dic[char][0]+1
          dic[char][1]-=1

        if char not in dic:
          dic[char] = []
          dic[char].append(end)
          dic[char].append(0)
        
        dic[char][0] = end
        dic[char][1]+=1

        if end-start+1==k:
          match = False
          for key in dic:
            if dic[key][1]==2:
              match = True
          if match:
            res.add(s[start:start+k])
          dic[s[start]][1]-=1
          start+=1


    return res
s = "awaglknagawunagwkwagl"
k = 4
s1 = "abcabc"
k1 = 3
s2 = "awaglk" 
k2 = 4
unique_character_strings1(s,k)
unique_character_strings1(s1,k1)
unique_character_strings1(s2,k2)<jupyter_output><empty_output><jupyter_text>**Favorite Genre**<jupyter_code>def favoriteGenre(userSongs,songGenres):

      if not userSongs: return {} 
      res = {}

      if not songGenres:
        for user in userSongs:
          res[user] = []
        return res
      
      reversegenre = {}

      for genre in songGenres:
          for song in songGenres[genre]:
              reversegenre[song] = genre

      for user in userSongs:
          dic = {}
          for song in userSongs[user]:
            genre = reversegenre[song]
            if genre not in dic:
              dic[genre] = 0
            dic[genre]+=1

          m = sorted(dic.values(),reverse=True)[0]
          res[user] = []
          for genre in dic:
            if dic[genre]==m:
              res[user].append(genre)


      return res       
userSongs = {  
   "David": ["song1", "song2", "song3", "song4", "song8"],
   "Emma":  ["song5", "song6", "song7"]
}
songGenres = {  
   "Rock":    ["song1", "song3"],
   "Dubstep": ["song7"],
   "Techno":  ["song2", "song4"],
   "Pop":     ["song5", "song6"],
   "Jazz":    ["song8", "song9"]
}

userSongs1 = {  
   "David": ["song1", "song2"],
   "Emma":  ["song3", "song4"]
}
songGenres2 = {}
favoriteGenre(userSongs,songGenres)<jupyter_output><empty_output><jupyter_text>**Optimization**<jupyter_code># Time Complexity: O(n^2)
# Space Complexity: O(n) #Excluding output
def findTarget1(l1,l2,target):
    import heapq
    mini = float('inf')
    h = []
    for i in range(len(l1)):
        for j in range(len(l2)):
            s = l1[i][1]+l2[j][1]
            if s<=target:
                heapq.heappush(h,(abs(target-s),l1[i][0],l2[j][0]))
                
    
    if len(h)>0:
        mini = h[0][0]
        res = []
        while h and h[0][0]==mini:
            a,b,c = heapq.heappop(h)
            res.append([b,c])
            
        return res
    
    return []
# Time Complexity: O(nlogn)
# Space Complexity: O(1) #excluding solution

def findTarget2(l1,l2,target):

    if not l1 or not l2: return []
    diff = float('inf')

    l1.sort(key = lambda k: k[1])
    l2.sort(key = lambda k: k[1]) 
    
    size1 = len(l1)
    size2 = len(l2)
    res = []
    i = 0
    j = size2-1
    while i<size1 and j>=0:
          s = l1[i][1]+l2[j][1]
          if target - s == diff:
              res.append([l1[i][0],l2[j][0]])
          elif target-s<diff and target>=s:
              res = []
              res.append([l1[i][0],l2[j][0]])
              diff = target-s
                
    
          if target<s:
            j-=1
          else:
            i+=1
    return res
a = [[1, 2], [2, 4], [3, 6]]
b = [[1, 2]]
target = 7
a1 = [[1, 3], [2, 5], [3, 7], [4, 10]]
b1 = [[1, 2], [2, 3], [3, 4], [4, 5]]
target1 = 10

a2 = [[1, 8], [2, 7], [3, 14]]
b2 = [[1, 5], [2, 10], [3, 14]]
target2 = 20

a3 = [[1, 8], [2, 15], [3, 9]]
b3 = [[1, 8], [2, 11], [3, 12]]
target3 = 20
findTarget(a2,b2,target2)
findTarget1(a2,b2,target2)<jupyter_output><empty_output><jupyter_text>**Missing Dice Rolls**<jupyter_code>def missing_dice_rolls(arr,f,m):

    if not arr: return 0
    total = sum(arr)
    count = len(arr)+f
    target = m*count - total

    if target>6*count:
      return [0]

    nums = [1,2,3,4,5,6]
    res = []
    def backtracking(nums,curr,total,f,target,match):

      if total<target and len(curr)<f and not match:

        for i in range(len(nums)):
            curr.append(nums[i])
            total+=nums[i]

            if total==target and len(curr)==f:
                res.append(curr[:])
                match = True
                break
            elif total<target and len(curr)<f and not match:
                match = backtracking(nums,curr,total,f,target,match)

            total-=curr.pop()
      if match:
        return True
      return False


    if backtracking(nums,[],0,f,target,False):
      return res
    return [0]
A = [3, 2, 4, 3] 
F = 2 
M = 4

A1 = [1,5,6] 
F1 = 4
M1 = 3

A2 = [1, 2, 3, 4] 
F2 = 4 
M2 = 6
print(missing_dice_rolls(A,F,M))
print(missing_dice_rolls(A1,F1,M1))
print(missing_dice_rolls(A2,F2,M2))<jupyter_output>[[6, 6]]
[[1, 1, 1, 6]]
[0]<jupyter_text>**Largest Item Associations**<jupyter_code>from collections import deque
import heapq
def dfs(curr_ver,graph,visited):

    stack = deque()
    stack.append(curr_ver)
    res = []
    visited.add(curr_ver)
    while stack:

        node = stack.pop()
        heapq.heappush(res,node)

        for ver in graph[node]:
            if ver not in visited:
              visited.add(ver)
              stack.append(ver)

    return res,visited


def largest_item_associations(arr):

    if not arr: return []

    graph = {}
    edges = set()
    for i,edge in enumerate(arr):
        edge1 = edge[0]
        edge2 = edge[1]

        if edge1 not in graph:
          graph[edge1] = []
          edges.add(edge1)
        if edge2 not in graph:
          graph[edge2] = []
          edges.add(edge2)

        graph[edge1].append(edge2)
        graph[edge2].append(edge1)
      
    visited = set()
    out = []

    for node in graph:
        if node not in visited: 
            res,visited = dfs(node,graph,visited)
        
        if not out:
          out.append(res[:])
        elif len(out[0])<len(res):
            out.pop()
            out.append(res[:])
        elif len(out[0])==len(res) and " ".join(out[0])>" ".join(res):
            out.pop()
            out.append(res[:])
    return out
arr1 = [['Item1', 'Item2'], ['Item3', 'Item4'], ['Item4', 'Item5']]
arr2 = [['Item1', 'Item2'], ['Item2', 'Item3'], ['Item5', 'Item6']]
arr3 = [['Item1', 'Item2'], ['Item2', 'Item3'], ['Item4', 'Item5'], ['Item5', 'Item6']]
print(largest_item_associations(arr1))
print(largest_item_associations(arr2))
print(largest_item_associations(arr3))<jupyter_output>[['Item3', 'Item4', 'Item5']]
[['Item1', 'Item2', 'Item3']]
[['Item1', 'Item2', 'Item3']]<jupyter_text>**Minimum cost to repair all edges**<jupyter_code>def minimumCost(N,edges,edgesToRepair):
    
    if N<1 or (not edges and not edgesToRepair) or not edgesToRepair: return -1
    
    df = {i:i for i in range(1,N+1)}
    edges_to_be_repaired = set([(i,j) for i,j,k in edgesToRepair])
    edgesToRepair.sort(key = lambda x:x[-1])
    res = 0

    def find(node):
        if df[node]!=node:
            df[node] = find(df[node])
        return df[node]

    for node1,node2 in edges:
        if (node1,node2) not in edges_to_be_repaired and not (node2,node1) in edges_to_be_repaired:
          x = find(node1)
          y = find(node2)
          edges_to_be_repaired.add((node1,node2))
          if x!=y:
              df[x] = y  
    
    for node1,node2,cost in edgesToRepair:
        x = find(node1)
        y = find(node2)
        if x!=y:
            
            res+=cost
            df[x] = y
            
    return res if len(set([find(i) for i in df]))==1 else -1
n = 6
edges = [[1, 2], [2, 3], [4, 5], [3, 5], [1, 6], [2, 4]]
edgesToRepair = [[1, 6, 410], [2, 4, 800]]

n1 = 5
edges1 = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]]
edgesToRepair1 = [[1, 2, 12], [3, 4, 30], [1, 5, 8]]

n2 = 6
edges2 = [[1, 2], [2, 3], [4, 5], [5, 6], [1, 5], [2, 4], [3, 4]]
edgesToRepair2 = [[1, 5, 110], [2, 4, 84], [3, 4, 79]]
print(minimumCost(n,edges,edgesToRepair))
print(minimumCost(n1,edges1,edgesToRepair1))
print(minimumCost(n2,edges2,edgesToRepair2))<jupyter_output>410
20
79<jupyter_text>**Truck Box**<jupyter_code>def get_max_unit(num,boxes,unitSize,unitsPerBox,truckSize):
    
    if not truckSize or not boxes or not num or not unitsPerBox or not unitSize: return 0
    import heapq

    h = []

    for i,box in enumerate(boxes):
        heapq.heappush(h,(-unitsPerBox[i],box))

    res = 0
    while truckSize>0 and h:

        a,b = heapq.heappop(h)
        res+=(-a)
        b-=1
        truckSize-=1
        if b:
          heapq.heappush(h,(a,b)) 

    return res
print(get_max_unit(3, [1,2,3], 3, [3,2,1], 3))
print(get_max_unit(3, [2,5,3], 3, [3,2,1], 50))<jupyter_output>7
19
{'fraction_non_alphanumeric': 0.16559200074759367, 'fraction_numerical': 0.04289318755256518, 'mean_word_length': 2.344375, 'pattern_counts': {'":': 9, '<': 44, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '562763', 'license': 'Unlicense', 'n_tokens_mistral': 4339, 'n_tokens_neox': 4088, 'n_words': 936, 'path': 'Amazon_OA.ipynb', 'repo_name': 'manashpratim/Algorithms-and-Data-Structures', 'size': '10701'}