Interview03_Dictionaries_and_Hashmaps

## Interview Preparation Kit
## Dictionaries and Hashmaps




##  Hash Tables: Ransom Note
def checkMagazine(magazine, note):
    if len(magazine) < len(note):
        return print('No')

    # to build a dictionary for magazine
    magazine_dict = {}
    for word in magazine:
        if word in magazine_dict:
            magazine_dict[word] += 1
        else:
            magazine_dict[word] = 1

    # unable to build note if the word from note is not in magazine_dict
    # or if there are insufficient words in the magazine_dict
    for word in note:
        if word not in magazine_dict.keys() or magazine_dict[word] == 0 :
            return print('No')
        else:
            magazine_dict[word] -= 1
    print('Yes')

if __name__ == '__main__':
    mn = input().split()
    m = int(mn[0])
    n = int(mn[1])
    magazine = input().rstrip().split()
    note = input().rstrip().split()

    checkMagazine(magazine, note)




## Two Strings
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the twoStrings function below.
# Option 1
def twoStrings(s1, s2):
    return 'YES' if any([i in s2 for i in s1]) else 'NO'

# Option 2
def twoStrings(s1, s2): 
    result = 'NO'
    a = set(list(s1)) 
    b = set(list(s2)) 
    c = a.intersection(b) 
    if (len(c) != 0): 
        result = 'YES' 
    return result

# Option 3
def twoStrings(s1, s2):
    s1 = set(s1)
    s2 = set(s2)
    for ele in s1:
        if ele in s2:
            return 'YES'
    return 'NO'

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input())
    for q_itr in range(q):
        s1 = input()
        s2 = input()
        result = twoStrings(s1, s2)
        fptr.write(result + '\n')
    fptr.close()




## Sherlock and Anagrams
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the sherlockAndAnagrams function below.
# Option 1
from collections import Counter
def sherlockAndAnagrams(s):
    anagrams = 0 
    for i in range(1, len(s)): 
        substrings = [] 
        for l in range(len(s)+1-i): 
            substrings.append(s[l:l+i]) 
        letters_in_sub = list(map(lambda x: Counter(x), substrings)) 
        for ele in letters_in_sub: 
            if letters_in_sub.count(ele)>1: 
                anagrams += (letters_in_sub.count(ele)-1)/2 
    return int(anagrams)

# Option 2
def sherlockAndAnagrams(s):
    dic = {}
    anagrams = 0
    for k in range(1, len(s)):
        for i in range(len(s)-k+1):
            j = i+k
            strr = ''.join(sorted(s[i:j]))
            dic[strr] = dic.get(strr,0)+1
    for v in dic.values():
        if v>1:
            anagrams += (v*(v-1))//2
    return anagrams

# Option 3
def sherlockAndAnagrams(s):
    anagrams = 0
    sub_str_dict = {}
    for pos, char in enumerate(s):
        for idx in range(pos + 1, len(s) + 1):
            ordered_sub_str = ''.join(sorted(s[pos:idx]))
            if ordered_sub_str in sub_str_dict:
                anagrams += sub_str_dict[ordered_sub_str]
                sub_str_dict[ordered_sub_str] += 1
            else:
                sub_str_dict[ordered_sub_str] = 1
    return anagrams

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input())
    for q_itr in range(q):
        s = input()
        result = sherlockAndAnagrams(s)
        fptr.write(str(result) + '\n')
    fptr.close()




## Count Triplets
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the countTriplets function below.
# Option 1
from collections import defaultdict
def countTriplets(arr, r):    #(array, ratio)
    c = 0   #count
    triplets = defaultdict(lambda: defaultdict(lambda: 0))
    for num in arr:
        if num in triplets:
            c += triplets[num][2]
            triplets[num*r][2] += triplets[num][1]
        triplets[num*r][1] += 1
    return c

# Option 2
from collections import Counter
def countTriplets(arr, r):
    second = Counter()
    third = Counter()
    c = 0   #count
    for num in arr:
        if num in third:
            c += third[num]
        if num in second:
            third[num*r] += second[num]
        second[num*r] += 1
    return c

# Option 3
from collections import defaultdict
def countTriplets(arr, r):
    second = defaultdict(int)
    third = defaultdict(int)
    c = 0   #count
    for num in arr:
        c += third[num]
        third[num*r] += second[num]
        second[num*r] += 1
    return c

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    nr = input().rstrip().split()
    n = int(nr[0])
    r = int(nr[1])
    arr = list(map(int, input().rstrip().split()))
    ans = countTriplets(arr, r)
    fptr.write(str(ans) + '\n')
    fptr.close()




## Frequency Queries
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the freqQuery function below.
# Option 1
from collections import Counter
def freqQuery(queries):
    result=[]
    n = len(queries)
    f = Counter()
    ff = Counter()
    for i in range(n):
        o,e = queries[i]
        if o==1:
            ff[f[e]]-=1
            f[e]+=1
            ff[f[e]]+=1
        elif o==2:
            ff[f[e]]-=1
            f[e]-=1
            ff[f[e]]+=1
            if f[e]<=0:
                del f[e]
        else:
            if ff[e]>0:
                result.append(1)
            else:
                result.append(0)
    return result

# Option 2
def freqQuery(queries):
    result=[]
    n = len(queries)
    f = {}
    ff = {}
    for i in range(n):
       o, e = queries[i]
       if (o==1):
           if e not in f:
               f[e]=0
           ff[f[e]]=ff.setdefault(f[e],0)-1
           f[e]=f.setdefault(e,0)+1
           ff[f[e]]=ff.setdefault(f[e],0)+1
       elif (o==2):
           if e in f:
               ff[f[e]]=ff.setdefault(f[e],0)-1
               f[e]=f.setdefault(e,0)-1
               ff[f[e]]=ff.setdefault(f[e],0)+1
               if f[e]<=0:
                   del f[e]
       else:
           if e in ff:
               if ff[e]:
                   result.append(1)
               else:
                   result.append(0)
           else:
               result.append(0)
    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input().strip())
    queries = []
    for _ in range(q):
        queries.append(list(map(int, input().rstrip().split())))
    ans = freqQuery(queries)
    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')
    fptr.close()




## end ##