<jupyter_start><jupyter_text>Microsoft Codility Demo<jupyter_code>def solution(A):
    array = sorted(A)
    print(array)
    
    i = 0
    while i < len(array) - 1:
        if array[i] <= 0:
            i += 1
            continue
            
        if array[i+1] - array[i] > 1:
            return array[i] + 1
        
        i += 1
        
    if array[-1] <= 0:
        return 1
    
    else:
        return array[-1] + 1
    
a = [1,3,6,4,1,2]
solution(a)<jupyter_output>[1, 1, 2, 3, 4, 6]<jupyter_text>Math  67 Add Binary (Facebook 45->56, Google 2->0, Amazon 3, ByteDance 2)  Another in 2. BS<jupyter_code>class Solution:
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        
        def convert(num):
            res = 0

            for exp, n in enumerate(num[::-1]):
                if n == '1':
                    res += pow(2, exp)
           
            return res
        
        x = convert(a)
        y = convert(b)
            
        res = x + y
        
        return bin(res).replace("0b", "")
    
    # "{0:#b}".format(my_int)
    # int('11111111', 2)
int('11111', 2)
bin(11111)
ord('0')
ord('1')<jupyter_output><empty_output><jupyter_text>Decimal to Binary<jupyter_code>import math
def dec_to_bin(n):
    # array to store 
    # binary number 

    size = 0
    while math.pow(2, size) <= n:
        size += 1

    binaryNum = [0] * size
  
    # counter for binary array 
    i = -1
    while n > 0:  
  
        # storing remainder 
        # in binary array 
        binaryNum[i] = n % 2
        n = n // 2
        i -= 1
  
    # printing binary array 
    # in reverse order 
    return binaryNum

dec_to_bin(1000)
math.floor(-345.5)

int(-3.6)

round(-3.6)

divmod(351, 10) # (a // b, a % b)

math.log10(19876)
import math
def vertical_print(a):
    if a == 0:
        return

    n = math.floor(math.log10(a))

    while n>=0:
        d,m = divmod(a, 10**n)

        a = m
        n-=1
        
    return a
        

vertical_print(1234)<jupyter_output><empty_output><jupyter_text>191 Number of 1 Bits (Facebook 5->2, Apple 2->0)<jupyter_code>class Solution: 
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        bits = 0
        mask = 1
        for i in range(32):
            if n & mask != 0:
                bits += 1
                
            mask <<= 1
            
        return bits
class Solution:
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        bits = 0
        for i in range(32):
            if n & 1 != 0:
                bits += 1
                
            n >>= 1
            
        return bits
mask = 1
for i in range(2):
    mask <<= 1
    
mask
bin(mask)

public int hammingWeight(int n) {
    int bits = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}<jupyter_output><empty_output><jupyter_text>190 Reverse Bits (Apple 3->4) As easy as it sounds, the above intuition could lead to quite some variants of implementation. For instance, to retrieve the right-most bit in an integer n, one could either apply the modulo operation (i.e. n % 2) or the bit AND operation (i.e. n & 1).<jupyter_code>class Solution:
    # param n, an integer
    # return an integer
    def reverseBits(self, n):    
        ret = 0
        power = 31
        while n:
            ret += (n & 1) << power

            n >>= 1
            power -= 1
        return ret
n = 110
n >>= 1
n<jupyter_output><empty_output><jupyter_text>401 Binary Watch (Apple 2->3 ,google)<jupyter_code>class Solution(object):
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        ans = []
        
        def bitCount(n):            
            count = 0
            while n > 0:
                if n % 2 == 1:
                    count += 1
                n = n >> 1
            
            return count
        
        def convert(H, M):
            # convert to string time 0 <= H < 12 
            if M < 10:
                return str(H) + ':' + '0' + str(M)
            
            else:
                return str(H) + ':' + str(M)
            
            # return str(H) + ":" + ("0" if M < 10 else "") + str(M)
        
        for H in range(0, 12):
            for M in range(0, 60):
                if bitCount(H) + bitCount(M) == num:
                    ans.append(convert(H, M))
        return ans<jupyter_output><empty_output><jupyter_text>393 UTF-8 Validation (Facebook 2, Amazon2)1.   List item2.   List item<jupyter_code>class Solution(object):
    def validUtf8(self, data):
        """
        :type data: List[int]
        :rtype: bool
        """
        # Number of bytes in the current UTF-8 character
        n_bytes = 0

        # Mask to check if the most significant bit (8th bit from the left) is set or not
        mask1 = 1 << 7

        # Mask to check if the second most significant bit is set or not
        mask2 = 1 << 6
        for num in data:

            # Get the number of set most significant bits in the byte if
            # this is the starting byte of an UTF-8 character.
            mask = 1 << 7
            if n_bytes == 0:
                while mask & num:
                    n_bytes += 1
                    mask = mask >> 1

                # 1 byte characters
                if n_bytes == 0:
                    continue

                # Invalid scenarios according to the rules of the problem.
                if n_bytes == 1 or n_bytes > 4:
                    return False
            else:

                # If this byte is a part of an existing UTF-8 character, then we
                # simply have to look at the two most significant bits and we make
                # use of the masks we defined before.
                if not (num & mask1 and not (num & mask2)):
                    return False
            n_bytes -= 1
        return n_bytes == 0<jupyter_output><empty_output><jupyter_text>(5) 7. Reverse Integer (Int. Math) (Amazon 9, Google 6, Apple 5, Facebook 5, Microsoft 2, )时间复杂度: O(lgx)  O(1)<jupyter_code>class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -self.reverse(-x)
        
        res = 0
        while x:
            res = res * 10 + x % 10
            x //= 10
            
        return res if res <= 2**31 - 1 else 0
a = Solution()
a.reverse(-23)
0x7fffffff
2**31 -1 
'2' == '2'
26 % 26<jupyter_output><empty_output><jupyter_text>9 Palindrome Number (Amazon 4->0, Google 4, Apple 2->0, Microsoft 4, Facebook 2)<jupyter_code>class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
    
        return x == self.reverse(x)


    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        res = 0
        while x:
            res = res * 10 + x % 10
            x //= 10

        return res if res <= 2**31 - 1 else 0<jupyter_output><empty_output><jupyter_text>202 Happy Number (Int, Set) (Amazon 4->3, Google 4->0, Apple 5, Bytedance 2)O(N)  O(N)<jupyter_code>class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set([n])
        
        while n != 1:            
            x = 0
            while n:
                x += (n % 10)**2
                n //= 10
                
            if x in seen:
                return False
            
            seen.add(x)
            n = x

        return True
class Solution:
    def isHappy(self, n):
        seen = set()
        while n not in seen:
            seen.add(n)
            n = sum([int(x) **2 for x in str(n)])
            
            if n == 1:
                return True
            
        return False<jupyter_output><empty_output><jupyter_text>*866* Prime Palindrome (Amazon 9 ->10)<jupyter_code>class Solution():
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n % d for d in range(2, int(n**.5) + 1))

        def reverse(x):
            ans = 0
            while x:
                ans = 10 * ans + x % 10
                x /= 10
            return ans

        while True:
            if N == reverse(N) and is_prime(N):
                return N
            N += 1
            
            if 10**7 < N < 10**8:
                N = 10**8
int(6**.5)<jupyter_output><empty_output><jupyter_text>204 Count Primes (Microsoft 4->2, Amazon 4->5, Google 2, Apple 2)<jupyter_code>class Solution:
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        # Sieve of Eratosthenes 
        
        isPrime = [True] * n
    
        for i in range(2, n):
            if i*i < n and isPrime[i*i]:
                for j in range(i*i, n, i):
                    isPrime[j] = False
                
        count = 0
        for i in range(2, n):
            if isPrime[i]:
                count += 1
                
        return count
                
import math
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0

        # Sieve of Eratosthenes 
        sieve = [True] * n
        sieve[0] = False
        sieve[1] = False
        
        for i in range(2, int(math.sqrt(n))+1):
            k = i * 2
            while k < n:
                sieve[k] = False
                k += i
                
        return sum(sieve)
import math
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """     
        def isPrime(n):
            for i in range(2, int(math.sqrt(n))+1):
                if n % i == 0:
                    return False

            return True
        
        count = 0
        for i in range(2, n):
            if isPrime(i):
                count += 1
                
        return count
import math
def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
        
    return True

isPrime(8)
for n in range(2, 10):
    for x in range(2, n):
        if n % x == 0:
            print(n, 'equals', x, '*', n//x)
            break
    else:
        # loop fell through without finding a factor
        print(n, 'is a prime number')
# Python program to check if the input number is prime or not

num = 407

# take input from the user
# num = int(input("Enter a number: "))
def prime_numer(num):
    # prime numbers are greater than 1
    if num > 1:
       # check for factors
        for i in range(2,num):
            if (num % i) == 0:
                print(num,"is not a prime number")
                print(i,"times",num//i,"is",num)
                break
        else:
            print(num,"is a prime number")


    # if input number is less than
    # or equal to 1, it is not prime
    else:
        print(num,"is not a prime number")<jupyter_output><empty_output><jupyter_text>390 Elimination Game ( Quora 2)<jupyter_code>class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        step = 1
        head = 1
        left = True
        
        while n > 1:
            if left or n % 2:
                head += step
            
            n //= 2
            step *= 2
            left = not left
        
        return head<jupyter_output><empty_output><jupyter_text>29 Divide Two Integers (Facebook 17->33, Amazon 3->5, Microsoft Onsite->0)<jupyter_code># 不能乘除，所以我们改用位运算，运用二分的思想，beats 100%
# 因为最坏的情况就是最大的数除以1，即2**31 / 1, 所以时间复杂度就是O(1)，如果assuming n is the number of bits， 那就是O(lgN)

# O(1)
# O(1)
class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        positive = (dividend > 0) is (divisor > 0)
        
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        
        while dividend >= divisor:
            tmp, cnt = divisor, 1
            while dividend >= tmp:
                tmp <<= 1 # *2
                cnt <<= 1 # *2
            dividend -= tmp >> 1 
            res += cnt >> 1
            
        res = res if positive else -res
        if res >= 2**31 - 1:
            return 2**31 - 1
        elif res <= -(2**31):
            return -(2**31)
        else:
            return res
s = Solution()
s.divide(10, 2)
dividend = 10
tmp = 12
dividend = dividend - tmp >> 1
dividend
bin(256)<jupyter_output><empty_output><jupyter_text>681 Next Closest Time (String. Math) (Google 17->0, Amazon 4)O(1)<jupyter_code>class Solution:
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """
        
        cur = 60 * int(time[:2]) + int(time[3:])
#         print('cur=', cur)
        allowed = {int(x) for x in time if x != ':'}
#         print('allowed=', allowed)
        while True:
            cur = (cur + 1) % (24 * 60)
#             print('cur=', cur)
            if all(digit in allowed
                    for block in divmod(cur, 60)
                    for digit in divmod(block, 10)):
                return "{:02d}:{:02d}".format(*divmod(cur, 60))
s = Solution()
time = "19:34"
s.nextClosestTime(time)
divmod(120, 60)<jupyter_output><empty_output><jupyter_text>65 Valid Number (Facebook 14->15, Amazon 3->0, Google 2->0) (Hard)<jupyter_code>class Solution():
    def isNumber(self, s):
        """
        :type s: str
        :rtype: bool
        """
        try:
            float(s)
            return True
        except:
            return False  
a = 2
print(a)
a += 3
print(a)
a = [1,2]
print(a)<jupyter_output>2
5
[1, 2]<jupyter_text>General  String. O(N) O(1). (String) List. O(N) O(N)  412 Fizz Buzz (Microsoft 3->5, Amazon 2->0, Apple 2)O(N)<jupyter_code>class Solution(object):
    def fizzBuzz(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        
        
        res = []
        for i in range(1, n+1):
            if not i % 3 and not i % 5:
                res.append('FizzBuzz')    
                
            elif not i % 3:
                res.append('Fizz')
                
            elif not i % 5:
                res.append('Buzz')
                
            else:
                res.append(str(i))
                
        return res<jupyter_output><empty_output><jupyter_text>263 Ugly Number<jupyter_code>class Solution(object):
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0:
            return False
        
        if num == 1:
            return True

        while num % 2 == 0:
            num //= 2 
            
        while num % 3 == 0:
            num //= 3
            
        while num % 5 == 0:
            num //= 5
            
        return num == 1<jupyter_output><empty_output><jupyter_text>264 Ugly Number II (Amazon 4->2)<jupyter_code>class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [1]
        if n == 1:
            return nums[-1]
        
        i2 = i3 = i5 = 0

        while True:
            ugly = min(nums[i2] * 2, nums[i3] * 3, nums[i5] * 5)
            nums.append(ugly)
            
            if len(nums) == n:
                return nums[-1]

            if ugly == nums[i2] * 2: 
                i2 += 1
            if ugly == nums[i3] * 3:
                i3 += 1
            if ugly == nums[i5] * 5:
                i5 += 1
from heapq import heappop, heappush
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = []
        seen = {1}
        heap = []
        heappush(heap, 1)
        
        for i in range(1, 1691):
            cur = heappop(heap)
            nums.append(cur)
            for i in (2,3,5):
                new = cur * i
                                                
                if new not in seen:
                    seen.add(new)
                    heappush(heap, new)
                    
        return nums[n-1]<jupyter_output><empty_output><jupyter_text>796 Rotate String (Apple 2->0, Amazon 2, Microsoft 2)<jupyter_code>class Solution(object):
    def rotateString(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: bool
        """
        return len(A) == len(B) and B in A + A<jupyter_output><empty_output><jupyter_text>8 String to Integer(atoi) (String. Math) (Facebook 6->20, Microsoft 5->6, Amazon 5->9, Google 3, Apple 5)O(N)  O(1)  指针是否为空指针以及字符串是否为空字符串；  字符串对于正负号的处理；  输入值是否为合法值，即小于等于'9'，大于等于'0'；  int为32位，需要判断是否溢出；  使用错误标志，区分合法值0和非法值0。<jupyter_code>int('')
class Solution:
    # param str, a string
    # return an integer
    def myAtoi(self, s: str) -> int:
        """
        :type str: str
        :rtype: int
        """
        s = s.strip()
        
        if not s:
            return 0
        
        num = ''
        if s[0] in '+-':
            num += s[0]
            s = s[1:]
            
        i = 0
        while i < len(s) and s[i].isdigit():
            num += s[i]
            i+=1
                

        if not num:
            return 0
                
        try: 
            res = int(num)
            if res > 2**31 - 1:
                return 2**31 - 1 
            elif res < -2**31:
                return -2**31
            else:
                return res
        
        except:
            return 0
int('-2')
def test(x):
    try:
        n = int(x)
        return n

    except:
        return 0

test('a')
ch = '3'
ch.isdigit()<jupyter_output><empty_output><jupyter_text>Replace Blank  剑指Offer. URL. change spance with %20<jupyter_code>class Solution:
    def url(self, string: str, length: int):
        if not string:
            return ''
        
        string = string.strip()
        
        # for i in range(length):
        #     if string[i] == ' ':
        #         space += 1
        space = string.count(' ')
                
        index = length + space * 2 - 1
        for i in range(length-1, -1, -1):
            if string[i] == ' ':
                string[index] = '0'
                string[index-1] = '2'
                string[index-2] = '%'
                index -= 3
                
            else:
                string[index] = string[i]
                index -= 1<jupyter_output><empty_output><jupyter_text>724 Find Pivot Index (Facebook 3->7, Google 2->0, Amazon 2->0, Microsoft 2->0, Apple 3)<jupyter_code>class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        
        suma = sum(nums)
        left_sum = 0
        for i in range(len(nums)):
            left_sum += nums[i-1] if i >= 1 else 0
            right_sum = suma - left_sum - nums[i]
            
            if left_sum == right_sum:
                return i
            
        return -1
class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        suma = sum(nums)
        leftsum = 0
        for i, x in enumerate(nums):
            if leftsum == (suma - leftsum - x):
                return i
            leftsum += x
        return -1<jupyter_output><empty_output><jupyter_text>14 Longest Common Prefix (Amazon 6-.5, Google 5->2, Microsoft 3, Apple 4->7, Facebook 9)<jupyter_code>class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''

        for i in range(len(strs[0])):
            for string in strs[1:]:
                if i >= len(string) or strs[0][i] != string[i]:
                    return strs[0][:i]

        return strs[0]<jupyter_output><empty_output><jupyter_text>134 Gas Station (List) (Amazon 6->5, Microsoft 5->3, Facebook 3, Google 2, Apple 3)  Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]  Output: 3  Explanation:  Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4  Travel to station 4. Your tank = 4 - 1 + 5 = 8  Travel to station 0. Your tank = 8 - 2 + 1 = 7  Travel to station 1. Your tank = 7 - 3 + 2 = 6  Travel to station 2. Your tank = 6 - 4 + 3 = 5  Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.   Therefore, return 3 as the starting index.<jupyter_code>class Solution:
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """        
        if sum(gas) - sum(cost) < 0:
            return -1
        
        tank = 0
        res = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0: 
                tank = 0
                res = i + 1
        return res<jupyter_output><empty_output><jupyter_text>1094 Car Pooling  trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off.   Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.   Input: trips = [[2,1,5],[3,3,7]], capacity = 4  Output: false<jupyter_code>class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        timestamp = []
        for trip in trips:
            timestamp.append([trip[1], trip[0]])
            timestamp.append([trip[2], -trip[0]])

        timestamp.sort()
        
        used_capacity = 0
        for time, passenger_change in timestamp:
            used_capacity += passenger_change
            if used_capacity > capacity:
                return False

        return True<jupyter_output><empty_output><jupyter_text>575 Distribute Candies   Input: candyType = [1,1,2,2,3,3]  Output: 3  Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.<jupyter_code>class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        # We start by sorting candyType.
        candyType.sort()
        # The first candy is always unique.
        unique_candies = 1
        # For each candy, starting from the *second* candy...
        for i in range(1, len(candyType)):
            # This candy is unique if it is different to the one
            # immediately before it.
            if candyType[i] != candyType[i - 1]:
                unique_candies += 1
            # Optimization: We should terminate the loop if unique_candies
            # is now at the maxium she can eat.
            if unique_candies == len(candyType) // 2:
                break
        # Like before, the answer is the minimum out of the number of unique candies, and 
        # half the length of the candyType array.
        return min(unique_candies, len(candyType) // 2)<jupyter_output><empty_output><jupyter_text>859 Buddy Strings (Microsoft Onsite,Facebook 2)<jupyter_code>class Solution:
    def buddyStrings(self, A: str, B: str) -> bool:
        if len(A) != len(B): 
            return False
        
        # 兩個字串相等, 且字串中有重複的字元(swap後字串不變)
        if A == B and len(set(A)) < len(A): 
            return True
        
        # ["abcd", "badc"], #false
        # dif = [('a', 'b'), ('b', 'a'), ('c', 'd'), ('d', 'c')]
        # 唯一一組, 且swap後吻合 -> True
        dif = [(a, b) for a, b in zip(A, B) if a != b]
        #print(dif)
        return len(dif) == 2 and dif[0] == dif[1][::-1]<jupyter_output><empty_output><jupyter_text>836 Rectangle Overlap (Apple 4->0, Microsoft 5, Amazon 3->0)<jupyter_code>class Solution:
    def isRectangleOverlap(self, rec1, rec2):
        """
        :type rec1: List[int]
        :type rec2: List[int]
        :rtype: bool
        """
        
        x1,y1,x2,y2 = 0,1,2,3
        
        return ( 
            rec1[x1] < rec2[x2] and # rec1 is to left of rec2
            rec1[y1] < rec2[y2] and # rec1 is above rec2
            rec2[x1] < rec1[x2] and # rec2 is to the left of rec1
            rec2[y1] < rec1[y2]     # rec2 is above rec1
        )<jupyter_output><empty_output><jupyter_text>169 Majority Element (Amazon 6->4, Google 3, Microsoft 3->2, Apple 2->0)  The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.<jupyter_code>class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        majority = None
        for num in nums:
            if count == 0:
                majority = num
                count += 1
                
            elif num == majority:
                count += 1
            else:
                count -= 1
        return majority
class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate = self.getCandidate(nums)
        return candidate if self.validate(nums, candidate) else -1

    def getCandidate(self, nums):
        count = 0
        for num in nums:
            if count == 0:
                majority = num
                
            if num == majority:
                count += 1
            else:
                count -= 1
        return majority

    def validate(self, nums, majority):
        count = 0
        for n in nums:
            if n == majority:
                count += 1

        return count > len(nums) // 2<jupyter_output><empty_output><jupyter_text>229 Majority Element II (List) (Microsoft 2->0, Amazon 2, Google 2)  Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.<jupyter_code>class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        
        count1 = 0
        count2 = 0
        candidate1 = None
        candidate2 = None
        for n in nums:
            if n == candidate1:
                count1 += 1

            elif n == candidate2:
                count2 += 1
            
            elif count1 == 0:
                candidate1 = n 
                count1 += 1

            elif count2 == 0:
                candidate2 = n 
                count2 += 1
        
            else:
                count1 -= 1
                count2 -= 1

        return [n for n in (candidate1, candidate2)
                        if nums.count(n) > len(nums) // 3]
class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        
        count1 = 0
        count2 = 0
        candidate1 = 0
        candidate2 = 1
        for n in nums:
            if n == candidate1:
                count1 += 1
#                 print('case1 count1=', count1)
            elif n == candidate2:
                count2 += 1
#                 print('case2 count2=', count2)
            elif count1 == 0:
                candidate1 = n 
                count1 = 1
#                 print('case3 candidate1=', candidate1)
#                 print('case3 count1=', count1)
            elif count2 == 0:
                candidate2 = n 
                count2 = 1
#                 print('case4 candidate2=', candidate2)
#                 print('case4 count2=', count2)
            else:
                count1 -= 1
                count2 -= 1
#                 print('x')
#         print(candidate1,candidate2)
        return [n for n in (candidate1, candidate2)
                        if nums.count(n) > len(nums) // 3]
s = Solution()
nums = [1,1,1,3,3,2,2,2]
s.majorityElement(nums)<jupyter_output><empty_output><jupyter_text>277 Find the Celebrity (Microsoft Onsite 3->4, Facebbook 5->3, Amazon 5, Apple 3)<jupyter_code>class Solution:
    def findCelebrity(self, n: int) -> int:
        self.n = n
        celebrity_candidate = 0
        for i in range(1, n):
            if knows(celebrity_candidate, i):
                celebrity_candidate = i
                
        if self.is_celebrity(celebrity_candidate):
            return celebrity_candidate
        return -1

    def is_celebrity(self, i):
        for j in range(self.n):
            if i == j: continue
            if knows(i, j) or not knows(j, i):
                return False
        return True
# O(N) 
# O(1)
class Solution:
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        celebrity = 0
        for i in range(1, n):
            if knows(celebrity, i):
				#说明当前的这个celebrity肯定不是名人，因为他认识别的人
                celebrity = i
		# 到这里的 celebrity，必定不认识 [celebrity + 1, n - 1]的所有人
        for i in range(celebrity):
            if knows(celebrity, i): # 为了确保celebrity 不认识 [0, celebrity - 1]
                return -1
        
        for i in range(n):
            if not knows(i, celebrity): # 为了确保 每个人都认识 celebrity
                return -1
        return celebrity
class Solution():
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        
        # if celebrity > candidate, candidate must change to the celebrity, cause (knows(candidate, celebrity) == True)
        # if candidate == celebrity: candidate won't change, cause celebrity knows nobody.
        # after the loop, candidate is the only one can be the celebrity
        for i in range(1, n):
            if knows(res, i):
                res = i
                
        # check people < candidate
        for i in range(res):
            if knows(res, i) or not(knows(i, res)):
                return -1
        
        # check if people > candidate are all knows the candidate
        for i in range(res+1, n):
            if not knows(i, res):
                return -1
            
        return res<jupyter_output><empty_output><jupyter_text>722 Remove Comments (List[str]) (Microsoft 5->7, Google 4)<jupyter_code>class Solution(object):
    def removeComments(self, source):
        """
        :type source: List[str]
        :rtype: List[str]
        """
        in_block = False
        ans = []
        for line in source:
            if not in_block:
                newline = []

            i = 0
            while i < len(line):
                if line[i:i+2] == '//' and not in_block:
                    break
                
                elif line[i:i+2] == '/*' and not in_block:
                    in_block = True
                    i += 2
                elif line[i:i+2] == '*/' and in_block:
                    in_block = False
                    i += 2
                
                elif in_block:             
                    i += 1
                else:
                    newline.append(line[i])
                    i += 1
                
            if newline and not in_block:
                ans.append("".join(newline))

        return ans
s = ' // jsjjs  '
s.strip()<jupyter_output><empty_output><jupyter_text>468 Validate IP Address (Facebook 3, Microsoft 2)<jupyter_code>class Solution:
    def validate_IPv4(self, IP: str) -> str:
        nums = IP.split('.')
        for num in nums:
            # Validate integer in range (0, 255):
            # 1. length of chunk is between 1 and 3
            if len(num) == 0 or len(num) > 3:
                return "Neither"
            # 2. no extra leading zeros
            # 3. only digits are allowed
            # 4. less than 255
            if num[0] == '0' and len(num) != 1 or not num.isdigit() or int(num) > 255:
                return "Neither"
        return "IPv4"
    
    def validate_IPv6(self, IP: str) -> str:
        nums = IP.split(':')
        hexdigits = '0123456789abcdefABCDEF'
        for num in nums:
            # Validate hexadecimal in range (0, 2**16):
            # 1. at least one and not more than 4 hexdigits in one chunk
            # 2. only hexdigits are allowed: 0-9, a-f, A-F
            if len(num) == 0 or len(num) > 4:
                return "Neither" 
            
            for c in num:
                if c not in hexdigits:
                    return "Neither"
        return "IPv6"
        
    def validIPAddress(self, IP: str) -> str:
        if IP.count('.') == 3:
            return self.validate_IPv4(IP)
        elif IP.count(':') == 7:
            return self.validate_IPv6(IP)
        else:
            return "Neither"<jupyter_output><empty_output><jupyter_text>161 One Edit Distance (Amazon 3->2, Facebook 3, Apple 2)  Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.  A string s is said to be one distance apart from a string t if you can:Insert exactly one character into s to get t.  Delete exactly one character from s to get t.  Replace exactly one character of s with a different character to get t.<jupyter_code>class Solution:
    def isOneEditDistance(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if s == t:
            return False 
        
        if abs(len(s) - len(t)) > 1:
            return False
        
        for i in range(min(len(s), len(t))):
            if s[i] != t[i]:
                if len(s) == len(t):
                    s = s[:i] + t[i] + s[i+1:] # replacement
                    
                elif len(s) < len(t):
                    s = s[:i] + t[i] + s[i:]   # insertion
                    
                else:
                    s = s[:i] + s[i+1:]        # deletion
                    
                break
                
        # 后面两个是为了 checking edge case for s ="a", t = ""
        return s == t or s == t[:-1] or s[:-1] == t 

bin(3)<jupyter_output><empty_output><jupyter_text>443 String Compression (String List) (Microsoft Onsite 6->7, Apple 6,Amazon 4, Facebook 3, Google 2)  Input: chars = ["a","a","b","b","c","c","c"]  Output: Return 6, and the first 6 characters of the input array should  be: ["a","2","b","2","c","3"]  Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".<jupyter_code># O(N)  
# O(1)
class Solution:
    def compress(self, strs):
        """
        :type chars: List[str]
        :rtype: int
        """
        
        count = 1

        for i in range(len(strs)-1, -1, -1):
            if i > 0 and strs[i] == strs[i-1]:
                count += 1
                
            else:
                if count == 1:
                    continue
                else:
                    end = i + count
                    strs[i: end] = [strs[i]] + list(str(count))   
                    count = 1

        return len(strs)

class Solution:
    def compress(self, strs):
        """
        :type chars: List[str]
        :rtype: int
        """
        
        count = 1

        for i in range(len(strs)-1, -1, -1):
            if i > 0 and strs[i] == strs[i-1]:
                count += 1
                
            elif count != 1:
                end = i + count
                strs[i: end] = [strs[i]] + list(str(count))
                count = 1

        return len(strs)
class Solution:
    def compress(self, chars):
        """
        List[stri]
        int
        """
        
        if not chars:
            return []
        
        if len(chars) == 1:
            return len(chars)
        
        l = 0
        r = 0
        
        count = 0
        while r < len(chars):                               
            if chars[l] == chars[r]:
                r += 1
                count += 1
                
                if r == len(chars) and count > 1:
                    replace = list(str(count))
                    chars[l + 1:] = replace
   
            else:
                if count == 1:
                    l = r              
                    count = 0
                    
                else:
                    replace = list(str(count))                    
                    chars[l + 1 : r] = replace
                    r = l + len(replace) + 1
                    l = r
                    count = 0

        return len(chars)
l = 0
r = 3
s = ['a', 'a', 'a', 'b']

s[l+1:r] = '2'

r = l + 2
l = r

l 
r

s[1:1]
class Solution:
    def compress(self, chars):
        if len(chars) <= 1:
            return len(chars)
        
#         count = 1
#         start = 0
#         for i in range(len(chars)-1):
#             if chars[i] == chars[i+1]:
#                 count += 1
                
#             if chars[i] != chars[i+1]:
#                 chars[start+1: i+1] = [str(count)]
#                 count = 1
#                 start = i + 1
        
#             if i == len(chars)-2:
#                 chars[start+1:] = [str(count)]
                
#         return len(chars)
        
        count = 0
        l = 0
        r = 0
        while r <= len(chars) - 1:
            if chars[l] == chars[r]:
                count += 1
                r += 1
                print('on', l, r)
                if r >= len(chars):
                    tmp = []
                    for c in str(count):
                        tmp.append(c)
                        
                    print('tmp2', tmp)
                    
                    chars[l+1:r] = tmp
                    
            else:
                if count == 1:
                    count = 0
                    l = r
                    print('one')
                
                else:
                    tmp = []
                    for c in str(count):
                        tmp.append(c)
                    
                    print('tmp1', tmp)
                    chars[l+1:r] = tmp 
                    count = 0
                    l = r
                    print('l', l)
                    print('r', r)
                        
        return chars
s = Solution()
s.compress(["a","a","b","b","c","c","c"])
["a","a","b","b","c","c","c"] -> ["2", "a", "2", "b", "3", "c"]
# create a nenw string to return
class Solution:
    def compress(self, strs: List[str]) -> int:
        if not strs:
            return ""
        
        res = []
        prechar = ""
        count = 0
        for s in strs:
            if s == prechar:
                count+=1
                
            else:
                if prechar != "":
                    res.append(prechar)
                    res.append(str(count))
                    
                prechar = s
                count = 1
                
        res.append(prechar)
        res.append(str(count))
                    
        print(res)
        return len(res)<jupyter_output><empty_output><jupyter_text>68 Text Justification (Google 8->4, Microsoft 4->2, Amazon 3->6, ByteDance 3) (Hard)  Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16  Output:[     "This    is    an",     "example  of text",     "justification.  "  ]<jupyter_code>from collections import deque
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
                
        queue = deque(words)
        ans = []
        
        while queue:
            
            res = []
            length = 0
            
            while queue and (length + len(queue[0]) + 1) <= maxWidth + 1:
                res.append(queue.popleft())
                length += len(res[-1]) + 1    
            length -= 1
            
            if queue:
                string = ""
                total_space = maxWidth - length
                divisor = len(res) - 1
                
                if divisor == 0:
                    string += res[0]
                    string += " " * total_space
            
                else:
                    space = total_space // divisor
                    extra = total_space % divisor

                    for word in res:
                        string += word
                        string += " " * (space + 1)
                        if extra:
                            string += " " 
                            extra -= 1
                    string = string.rstrip()
            
            else:
                string = ""
                for word in res:
                    string += word
                    string += " "
                string = string.rstrip()
                string += " " * (maxWidth - len(string))
                
                ans.append(string)
            
        return ans
class Solution:
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        
        n = len(words)
        if n == 0:
            return []
        
        res = []
        cur, num_letters = [], 0
        
        for w in words:
            if len(cur) + len(w) + num_letters > maxWidth:
                if len(cur) == 1:
                    res.append(cur[0] + ' '*(maxWidth - num_letters))
                else:
                    num_space = maxWidth - num_letters
                    gap, remain_gap = divmod(num_space, len(cur) - 1)
                    for i in range(remain_gap):
                        cur[i] += ' '
                    res.append((' '*gap).join(cur))
                cur, num_letters = [], 0
                
            cur += [w]
            num_letters += len(w)
            
        res.append(' '.join(cur) + ' '*(maxWidth - num_letters - len(cur) + 1))
        return res<jupyter_output><empty_output><jupyter_text>239 Sliding Window Maximum (List, Queue) (Amazon Onsite 21->32, Facebook 6->5, Google 5->4, Microsoft Onsite 1, 5->2, ByteDance 7)<jupyter_code>class Solution():
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []

        if k == 1:
            return nums
        
        res = [max(nums[:k])]
        
        for i in range(k, len(nums)):
            if nums[i] >= res[-1]:
                res.append(nums[i])
            else:
                if nums[i - k] < res[-1]:
                    res.append(res[-1])
                    
                elif nums[i - k] == res[-1]:
                    res.append(max(nums[i-k+1:i+1]))
                    
        return res<jupyter_output><empty_output><jupyter_text>use heap to get max?<jupyter_code># O(N)  
# O(N)
class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []

        queue = []
        res = []

        for i in range(k):
            while queue:
                if nums[i] > nums[queue[-1]]:
                    queue.pop()
                else:
                    break
            queue.append(i)

        for i in range(k, len(nums)):
            res.append(nums[queue[0]])
            if queue[0] < i - k + 1:
                queue.pop(0)

            while queue:
                if nums[i] > nums[queue[-1]]:
                    queue.pop()
                else:
                    break
            queue.append(i)

        res.append(nums[queue[0]])
        return res
from collections import deque
class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """       
        # base cases
        n = len(nums)
        if n * k == 0:
            return []
        if k == 1:
            return nums
        
        def clean_deque(i):
            # remove indexes of elements not from sliding window
            if deq and deq[0] == i - k:
                deq.pop(0)
                
            # remove from deq indexes of all elements 
            # which are smaller than current element nums[i]
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()
        
        # init deque and output
        deq = []
        max_idx = 0
        for i in range(k):
            clean_deque(i)
            deq.append(i)
            # compute max in nums[:k]
            if nums[i] > nums[max_idx]:
                max_idx = i
                
        output = [nums[max_idx]]
        
        # build output
        for i in range(k, n):
            clean_deque(i)          
            deq.append(i)
            output.append(nums[deq[0]])
        return output<jupyter_output><empty_output><jupyter_text>Average of n elements in array<jupyter_code>class Main:
    def average(self, array, n):
        if not isinstance(array, list) or not isinstance(n, int):
            raise Exception("Invalid inputs")

        if len(array) < n:
            raise Exception("The length of array is smaller than n")

        if not array:
            return []

        res = []
        subarray = array[:n]
        sums = sum(subarray)
        res.append(sums//n)
        i = n
        while i < len(array):
            sums += array[i]
            sums -= array[i-n]
            res.append(sums//n)
            
            i += 1

        return res

s = Main()
array = [2,4,6,8]
n = 2
s.average(array, n)<jupyter_output><empty_output><jupyter_text>38 Count and Say (Amazon 4, Facebook 3-.4, Google 3->2, Microsoft 2->3, Apple 2)   Input: n = 4  Output: "1211"  Explanation:  countAndSay(1) = "1"  countAndSay(2) = say "1" = one 1 = "11"  countAndSay(3) = say "11" = two 1's = "21"  countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"<jupyter_code>class Solution:
    def countAndSay(self, n: int) -> str:
        number = '1'
        new_str = ''
        
        for num in range(1, n):
            count = 1
            index = 0
            while index < len(number)-1:
                if number[index+1] == number[index]:
                    count+=1
                else:
                    new_str += str(count) + number[index]
                    count=1
                index += 1
            new_str += str(count) + number[index]
            number = new_str
            new_str = ''
            
        return number<jupyter_output><empty_output><jupyter_text>163 Missing Ranges (List) (Google 6 Phone->3, Facebook 7, Amazon 2, ByteDance 2)   Input: nums = [0,1,3,50,75], lower = 0, upper = 99Output: ["2","4->49","51->74","76->99"]  Explanation: The ranges are:  [2,2] --> "2"  [4,49] --> "4->49"  [51,74] --> "51->74"  [76,99] --> "76->99"<jupyter_code># O(N)  
# O(1)
class Solution:
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        
        result = []
        nums.insert(0, lower -1)
        pre = nums[0]
        nums.append(upper + 1)
        
        for n in nums[1:]:
            if n - pre == 2:
                result.append(str(n - 1))
#                 print('result1=', result)
            elif n - pre > 2:
                result.append(str(pre + 1) + "->" + str(n - 1))
#                 print('result2=', result)
            pre = n
#             print('pre=', pre)
#             print()
        return result
s = Solution()
nums = [0, 1, 3, 50, 75]
s.findMissingRanges(nums, 0, 99)<jupyter_output><empty_output><jupyter_text>442 Find All Duplicates in an Array (Facebook 6, Amazon 4, Microsoft 3)  Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.<jupyter_code>class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();

        for (int num : nums) {
            if (nums[Math.abs(num) - 1] < 0) { // seen before
                ans.add(Math.abs(num));
            }
            nums[Math.abs(num) - 1] *= -1;
        }

        return ans;
    }
}<jupyter_output><empty_output><jupyter_text>843 Guess the Word (Google 23->29)<jupyter_code># """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
# class Master:
#     def guess(self, word: str) -> int:

import random
class Solution:
    def findSecretWord(self, wordlist, master):
        """
        :type wordlist: List[Str]
        :type master: Master
        :rtype: None
        """
        
        new_wordlist = wordlist
        while True:
            test_word = random.choice(new_wordlist)
            matches = master.guess(test_word)

            if matches == 6:
                return

            wordlist = new_wordlist
            new_wordlist = []
            for word in wordlist:
                dist = 0
                for i in range(6):
                    if word[i] == test_word[i]:
                        dist += 1

                if matches == dist:
                    new_wordlist.append(word)<jupyter_output><empty_output><jupyter_text>157 Read N Characters Given Read4<jupyter_code>class Solution:
    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Number of characters to read (int)
        :rtype: The number of actual characters read (int)
        """
        copied_chars = 0
        read_chars = 4
        buf4 = [''] * 4
        
        while copied_chars < n and read_chars == 4:
            read_chars = read4(buf4)
            
            for i in range(read_chars):
                if copied_chars == n:
                    return copied_chars
                buf[copied_chars] = buf4[i]
                copied_chars += 1
        
        return copied_chars<jupyter_output><empty_output><jupyter_text>158 Read N Characters Given Read4 II - Call multiple times (String List) (Facebook 15->18, Google 6->0) (Hard)<jupyter_code>class Solution:
    head, tail, buffer = 0, 0, [''] * 4 ## 定义全局变量

    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        i = 0
        while i < n:
            if self.head == self.tail: ## read4 的缓存区为空的时候
                self.head = 0
                self.tail = read4(self.buffer) ## 开始进缓存区
                if self.tail == 0:
                    break
            while i < n and self.head < self.tail:
                buf[i] = self.buffer[self.head] ## 读出缓存区的变量
                i += 1
                self.head += 1
        return i
buf = ['a','b','c']
buf[0] = ''
buf<jupyter_output><empty_output><jupyter_text>1268 Search Suggestions System (Amazon OA 29->5)<jupyter_code>class Solution:
    def suggestedProducts(self, products, searchWord):
        """
        :type products: List[str]
        :type searchWord: str
        :rtype: List[List[str]]
        """
        res = []
        products.sort()
        
        for i in range(1, len(searchWord)+1):  
            tmp = []
            for j in range(len(products)):
                if len(tmp) == 3:
                    break
                    
                if searchWord[:i] == products[j][:i]:
                    tmp.append(products[j])
                
            res.append(tmp)
            
        return res
class Solution:
    def suggestedProducts(self, products, searchWord):
        """
        :type products: List[str]
        :type searchWord: str
        :rtype: List[List[str]]
        """
        ans, res = [], []
        products.sort()
        
        for i in range(1, len(searchWord)+1):
            to_search = searchWord[:i]
            
            j = 0
            while j < len(products):
                if len(ans) == 3:
                        break
                
                if to_search == products[j][:i]:
                    ans.append(''.join(products[j]))
                    
                j += 1
                
            res.append(ans)
            ans = []
            
        return res
# Buggy with large input 
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        
                    
        dic = {}
        
        for word in products:
            t = dic
            for c in word:
                if c not in t:
                    t[c] = {}
                    
                t = t[c]
                
            t['#'] = {}
            
        # print(dic)
        def dfs(start, t, word):
            if start == '#':
                tmp.append(word)
                return

            # print(t)
            # print(start)
            t = t.get(start)

            for nxt in t:
                dfs(nxt, t, word + start)   
            
        res = []
        
        for i in range(len(searchWord)):
            tmp = []
            word = ''
            t = dic
            for c in searchWord[:i]:
                if c not in t:
                    break
                
                word += c
                t = t[c]
            
            if searchWord[i] in t:
                start = searchWord[i]
                dfs(start, t, word)

            tmp.sort()
            if len(tmp) >= 3:
                tmp = tmp[:3]

            res.append(tmp)
            
        return res<jupyter_output><empty_output><jupyter_text>482 License Key Formatting (String. List) (Google OA 16)<jupyter_code>class Solution:
    def licenseKeyFormatting(self, S, K):
        """
        :type S: str
        :type K: int
        :rtype: str
        """
        S = S.replace("-", "").upper()[::-1]
        return '-'.join(S[i:i+K] for i in range(0, len(S), K))[::-1]
'-'.join(['w9e3','23f5'])[::-1]<jupyter_output><empty_output><jupyter_text>Max Possible Value (Microsoft OA)<jupyter_code>def solution(n): 
    string = list(str(n))
    
    if string[0] == '-':
        for i in range(1, len(string)+1):
            if i == len(string):
                string.insert(i, '5')
                break
            
            if '5' < string[i]:
                string.insert(i, '5')
                break
        
    else:
        for i in range(len(string)+1):   
            if i == len(string):
                string.insert(i, '5')
                break
                
            
            if '5' > string[i]:
                string.insert(i, '5')
                break
            
    return int(''.join(string))
            
a = 268
b = 670
c = 0
d = -999
e = 945
f = -945
g = -123 # -123 returns -5123 while it should return -1235
        
solution(123)
n = -9
list(str(n))
# O(k), k = number of digits
def solution(num):
    if num < 0:
        return neg(num)
    else:
        return pos(num)

def pos(num):
    n = len(str(num))
    res = 0
    
    while num >= 0:
        val = num//10**(n-1)
        num %= 10**(n-1)
        if val < 5:
            res += (5*10**n)+val*(10**(n-1))+num
            return res
        else:
            res += val*10**n
            n -= 1
            
def neg(num):
    num = abs(num)
    n = len(str(num))
    res = 0
    
    while num >= 0:
        val = num//10**(n-1)
        num %= 10**(n-1)
        if val > 5:
            res += (5*10**n)+val*(10**(n-1))+num
            return -res
        else:
            res += val*10**n
            n -= 1
print(solution(-99))
def maxPossibleValue(N):
    s = str(N)
    if N >= 0:
        i = 0
        for d in s:
            if d >= '5':
                i += 1
            else:
                break
        ans = int(s[:i] + '5' + s[i:])
    else:
        i, s = 0, s[1:]
        for d in s:
            if d <= '5':
                i += 1
            else:
                break
        ans = -int(s[:i] + '5' + s[i:])
    return ans
            

N = 268
print(maxPossibleValue(N))

N = 670
print(maxPossibleValue(N))

N = 0
print(maxPossibleValue(N))

N = -999
print(maxPossibleValue(N))
def insert_five(num):
    num_str = str(num) if num >= 0 else str(-num)
    i = 0

    if num >= 0:
        while i < len(num_str) and num_str[i] >= '5':
            i += 1
    else:
        while i < len(num_str) and num_str[i] <= '5':
            i += 1

    max_string = (num_str[:i] + '5' + num_str[i:])

    return max_string if num >= 0 else '-' + max_string<jupyter_output><empty_output><jupyter_text>1647 Minimum Deletions to Make Character Frequencies Unique (Microsoft OA 2021)<jupyter_code>from collections import Counter
class Solution:
    def minDeletions(self, s: str) -> int:
        
        res = 0
        count = Counter(s)
        array = list(count.items())
        
        formated = list(map(list, array))
        formated.sort(key=lambda x: -x[1])
        
        for i in range(1, len(formated)):
            if formated[i][1] >= formated[i-1][1]:
                expected = max(formated[i-1][1] - 1, 0)
                res += formated[i][1] - expected
                formated[i][1] = expected
                
        return res
from collections import Counter

# buggy
def solution(s):
    dic = Counter(s)
    
    array = list(dic.values())
    array.sort()
    print(array)
    
    count = 0
    for i in range(len(array)-2, -1, -1):
        print('i', i)
        if array[i] == array[i + 1]:
            array[i] -= 1
            count += 1
            
            if array[i] == 1:
                count += sum(array[:i])
                break
                
    return count
                
solution("aabbffddeaee")<jupyter_output><empty_output><jupyter_text>Find N Unique Integers Sum up to Zero (Microsoft OA)<jupyter_code>class Solution:
    def sumZero(self, n):
        array = list(range(-(n // 2), (n // 2) + 1))

        if n % 2 == 0:
            array.pop(n // 2)
        return array
    
obj = Solution()
obj.sumZero(4)<jupyter_output><empty_output><jupyter_text>Day of Week (Microsoft OA)<jupyter_code>def solution(s, n):
    array = ["Mon", "Tue", "Web", "Thu", "Fri", "Sat", "Sun"]
    index = array.index(s)
    
    if n >= 7:
        n %= 7
    
    if index + n >= 7:
        return array[index + n - 7]
    
    else:
        return array[index + n]
    
solution("Sat", 23)<jupyter_output><empty_output><jupyter_text>Max Inserts to Obtain String Without 3 Consecutive 'a' (Microsoft OA)<jupyter_code>def solution(string):
    if not len(string):
        return 2
    
#     result = 0    
    if string[0] == "a": 
        res = 0
        a = 1
        
    else:
        res = 2
        a = 0
    
    for i in range(1, len(string) + 1):
        if i == len(string):
            res += 2 - a
            break
        
        if string[i] == "a":
            a += 1
        else:
            res += 2 - a
            a = 0
            
        if a >= 3:
            return -1
        
    return res


a = "aabab" #3
b = "dog" #8
c = "aa" #0
d = "baaaa" #-1
solution(d)
def consecutive(string):
    count = 0
    prea = False
    for ss in string:
        if ss == "a":
            if prea == False:
                count += 1
                prea = True
                
        if ss != "a":
            if prea == False:
                count += 2
            else:
                prea = True
                
    if string[-1] != "a":
        count+= 2
        
    return count

a = "aabab"
b = "dog"
c = "aa"
d = "baaaa"
print(consecutive(d))<jupyter_output>3<jupyter_text>Fair Indexes (Microsoft OA)<jupyter_code>def solution(A, B):
    res = 0
    
    sumA = sum(A)
    sumB = sum(B)
    
    tmpA = 0
    tmpB = 0
    
    for i in range(len(A)-1):
        tmpA += A[i]
        tmpB += B[i]
        
        if sumA == 2 * tmpA and sumB == 2 * tmpB and tmpA == tmpB:
            res += 1
            
    return res

A1 = [4,-1,0,3]; B1 = [-2, 5, 0 ,3] #2
A2 = [2,-2,-3,3]; B2 = [0,0,4,-4] #1
A3 = [4,-1,0,3]; B3 = [-2,6,0,4] #0
A4 = [3,2,6]; B4 = [4,1,6] #0
A5 = [1,4,2,-2,5]; B5 = [7,-2,-2,2,5] #2

solution(A4, B4)
def solution(A, B):
    res = 0
    sum_leftA = 0
    sum_leftB = 0
    sum_rightA = sum(A)
    sum_rightB = sum(B)
    
    print(sum_rightA)
    print(sum_rightB)
    
#     if sum_rightA == sum_rightB:
#         res += 1
        
    for i in range(1, len(A)):
        sum_leftA += A[i - 1]
        sum_leftB += B[i - 1]
        
        print(sum_leftA, sum_leftB)
        
        sum_rightA -= A[i-1]
        sum_rightB -= B[i-1]
        
        print(sum_rightA, sum_rightB)
        
        if sum_leftA == sum_leftB == sum_rightA == sum_rightB:
            res += 1
            
#     sum_leftA += A[-2]
#     sum_leftB += B[-2]
    
#     if sum_leftA == sum_leftB:
#         res += 1
            
    return res

A1 = [4,-1,0,3]; B1 = [-2, 5, 0 ,3] #2
A2 = [2,-2,-3,3]; B2 = [0,0,4,-4] #1
A3 = [4,-1,0,3]; B3 = [-2,6,0,4] #0
A4 = [3,2,6]; B4 = [4,1,6] #0
A5 = [1,4,2,-2,5]; B5 = [7,-2,-2,2,5] #2

solution(A5, B5)<jupyter_output>10
10
1 7
9 3
5 5
5 5
7 3
3 7
5 5
5 5<jupyter_text>String Without 3 Identical Consecutive Letters (Microsoft OA)<jupyter_code>from itertools import groupby
def stringWithout3Identical(S):
    """
    input: str
    output: str
    """
    
    ans = ''
    for c, g in groupby(S):
        length = len(list(g))
        
        if length > 2:
            ans += c * 2
            
        else:
            ans += c * length

    return ans
    
S = 'eedaaad'
# S = ['e', 'e', 'd', 'a', 'a', 'a', 'd']
stringWithout3Identical(S)

S = 'xxxtxxx'
stringWithout3Identical(S)

S = 'uuuuxaaaaxuuu'
stringWithout3Identical(S)
def filter_string(s: str) -> str:

    news = s[0:2]
    for i in range(2, len(s)):
        if s[i] == s[i - 1] and s[i] == s[i - 2]:
            continue
            
        news += s[i]
    return news<jupyter_output><empty_output><jupyter_text>Lexicographically Smallest String (Microsoft OA)<jupyter_code>def smallest_string(s: str) -> str:
    for i in range(len(s) - 1):
        if s[i] > s[i + 1]:
            break

    return s[:i] + s[i + 1:]
def lexiSmallestString(string):
    # loop through one letter after another
    for index, letter in enumerate(string[:-1]):
        if letter > string[index+1]:
            # rebuild string without z if letter is greater than next
            result_string = string[:index] + string[index+1:]
            # print ("letter", letter)
            # print ("result string", result_string)
            return result_string
        else:
            # else remove last character
            result_string = string[:index+1]
            # print ("result string", result_string)
            
lexiSmallestString("abczd")
lexiSmallestString("abcde")
def solution(s):
    for i in range(len(s)-1):
        if s[i] > s[i+1]:
            s = s.replace(s[i], '')
            
            break
    
    return s

a = 'abczd'
solution(a)
s = 'abc'
s.replace('c', '')
s
def containsSubstring(src, key):
    res = []
    for word in src:
        if key in word:
            res.append(word)
    return res

src = {"minecraftgame", "intelligent", "innercrafttalent", "knife", "scissor", "stonecrafter"}
key = "craft"
containsSubstring(src, key)<jupyter_output><empty_output><jupyter_text>Light Buld Switcher (Microsoft OA)<jupyter_code>public int getShiningCounts(int[] arr) {
	int ans = 0, sum = 0, target = 0;
		
	for(int i = 1; i<= arr.length; i++) {
		sum += arr[i-1];
		target += i ; //Sum from 1 to i
		if(sum == target) ans++;
	}
		
	return ans;
}
def solution(s):
    ans = 0
    sums = 0
    target = 0
    for i in range(1, len(s)+1):
        sums += s[i-1]
        target += i
        
        if sums == target:
            ans += 1
            
    return ans

a = [2, 1, 3, 5, 4]
solution(a)<jupyter_output><empty_output><jupyter_text>Second Max (Google Phone)<jupyter_code>def secondMax(nums):
    def compare(a,b):
        return max(a,b)
    
    first = compare(nums[0], nums[1])
    if first == nums[0]:
        second = nums[1]
    else:
        second = nums[0]
            
    for i in range(2, len(nums)):
        if compare(first, nums[i]) > first:
            second = first
            first = nums[i]
                
        elif compare(first, nums[i]) > nums[i]:
            if compare(second, nums[i]) > second: 
                second = nums[i]
                
    return second
nums = [10, 8, 15, 12, 6, 20, 20, 1]
secondMax(nums)
(10, 8)
(10, 15) - (15, 10)
(15, 12)
(15, 20) - (20, 15)<jupyter_output><empty_output><jupyter_text>(String) Matrix. O(N^2) O(N^2)  6 ZigZag Conversion (Amazon 2, Apple)<jupyter_code>class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); i++)
            rows.add(new StringBuilder());

        int curRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows.get(curRow).append(c);
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        StringBuilder ret = new StringBuilder();
        for (StringBuilder row : rows) ret.append(row);
        return ret.toString();
    }
}<jupyter_output><empty_output><jupyter_text>419 Battleships in a Board (Facebbook 90->3, Microsoft ->0, Amazon 3, Google 2,)  Input: board =   [["X",".",".","X"],  [".",".",".","X"],  [".",".",".","X"]]  Output: 2<jupyter_code>class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        ans = 0
        
        directions = [(0, -1), (-1, 0)]
        
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'X':
                    
                    tmp = 1
                    
                    for di, dj in directions:
                        x = i + di
                        y = j + dj
                        
                        if 0 <= x < len(board) and 0 <= y < len(board[0]):
                            if board[x][y] == 'X':
                                tmp -= 1
                                break   
                    ans += tmp
        return ans
class Solution:
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        ans = 0
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'X':
                    if i == 0 or board[i-1][j] == '.':
                        if j == 0 or board[i][j-1] == '.': 
                            ans += 1
        return ans<jupyter_output><empty_output><jupyter_text>463 Island Perimeter (Facebook 11->5, Google 2->0 )<jupyter_code>class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows = len(grid)
        cols = len(grid[0])
        
        result = 0
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for i in range(rows):
            for j in range(cols):
                if grid[r][c] == 1:
                    tmp = 4
                    for di, dj in directions:
                        x = i + di
                        y = j + dj
                        
                        if 0 <= x < rows and 0 <= y < cols:
                            if grid[x][y] == 1:
                                tmp -= 1

                    result += tmp
                    
        return result
class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows = len(grid)
        cols = len(grid[0])
        
        result = 0
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    if r == 0:
                        up = 0
                    else:
                        up = grid[r-1][c]
                    if c == 0:
                        left = 0
                    else:
                        left = grid[r][c-1]
                    if r == rows-1:
                        down = 0
                    else:
                        down = grid[r+1][c]
                    if c == cols-1:
                        right = 0
                    else:
                        right = grid[r][c+1]
                        
                    result += 4-(up+left+right+down)
                
        return result<jupyter_output><empty_output><jupyter_text>289 Game of Life (Matrix) (Amazon 10->4, Google 2->0 Phone, Microsoft 3)  Any live cell with fewer than two live neighbors dies as if caused by under-population.  Any live cell with two or three live neighbors lives on to the next generation.  Any live cell with more than three live neighbors dies, as if by over-population.  Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.<jupyter_code># O(n^2)
# O(1)
class Solution:
    def gameOfLife(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        # Neighbors array to find 8 neighboring cells for a given cell
        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        m = len(board)
        n = len(board[0])

        # Iterate through board cell by cell.
        for i in range(m):
            for j in range(n):

                # For each cell count the number of live neighbors.
                live_neighbors = 0
                for di, dj in neighbors:

                    # row and column of the neighboring cell
                    x = i + di
                    y = j + dj

                    # Check the validity of the neighboring cell and if it was originally a live cell.
                    if 0 <= x < m and 0 <= y < n and abs(board[x][y]) == 1:
                        live_neighbors += 1

                # Rule 1 or Rule 3
                if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    # -1 signifies the cell is now dead but originally was live.
                    board[i][j] = -1
                # Rule 4
                elif board[i][j] == 0 and live_neighbors == 3:
                    # 2 signifies the cell is now live but was originally dead.
                    board[i][j] = 2

        # Get the final representation for the newly updated board.
        for i in range(m):
            for j in range(n):
                if board[i][j] > 0:
                    board[i][j] = 1
                else:
                    board[i][j] = 0
a = [1,2]
del a[0]
a
class Solution:
    def gameOfLife(self, board):
        """
        Do not return anything, modify board in-place instead.
        """
        # Neighbors array to find 8 neighboring cells for a given cell
        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

        dp = []
        for n in board:
            dp.append(n.copy())
        
        rows = len(board)
        cols = len(board[0])

        # Iterate through board cell by cell.
        for row in range(rows):
            for col in range(cols):

                # For each cell count the number of live neighbors.
                live_neighbors = 0
                for neighbor in neighbors:

                    # row and column of the neighboring cell
                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # Check the validity of the neighboring cell and if it was originally a live cell.
                    if (r < rows and r >= 0) and (c < cols and c >= 0) and dp[r][c] == 1:
                        live_neighbors += 1

                # Rule 1 or Rule 3
                if dp[row][col] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    # -1 signifies the cell is now dead but originally was live.
                    board[row][col] = 0
                # Rule 4
                if dp[row][col] == 0 and live_neighbors == 3:
                    # 2 signifies the cell is now live but was originally dead.
                    board[row][col] = 1
class Solution:
    def gameOfLife(self, board):
        """
        :type board: List[List[int]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        
        for i in range(len(board)):
            for j in range(len(board[i])):
                live=0
                try:
                    l_1=board[i-1][j-1]
                    if l_1>0 and i>0 and j>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_2=board[i-1][j]
                    if l_2>0 and i>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_3=board[i-1][j+1]
                    if l_3>0 and i>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_4=board[i][j-1]
                    if l_4>0 and j>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_5=board[i][j+1]
                    if l_5>0:
                        live+=1
                except IndexError:
                    pass
                try:
                    l_6=board[i+1][j-1]
                    if l_6>0 and j>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_7=board[i+1][j]
                    if l_7>0:
                        live+=1
                except IndexError:
                    pass
                
                try:
                    l_8=board[i+1][j+1]
                    if l_8>0:
                        live+=1
                except IndexError:
                    pass  
                
                if board[i][j]>0:
                    if live<2 or live>3:
                        board[i][j]=2
                    elif live==2 or live==3:
                        board[i][j]=1
                else:
                    if live==3:
                        board[i][j]=-1
                        
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j]==2:
                    board[i][j]=0
                if board[i][j]==-1:
                    board[i][j]=1<jupyter_output><empty_output><jupyter_text>36 Valid Sudoku (String Matrix) (Uber 7, Microsoft 7->0, Amazon 5->9, Apple 7->6, Google 3->2, Facebook 4)O(m*n)  O(1)<jupyter_code>class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        for row in board:
            row_hash = set()
            for c in row:
                if c != "." and c in row_hash:
                    return False
                row_hash.add(c)

        for col in zip(*board):
            col_hash = set()
            for c in col:
                if c != "." and c in col_hash:
                    return False
                col_hash.add(c)

        # check for panel
        for i in (0, 3, 6):
            for j in (0, 3, 6):
                panel_hash = set()
                for x in range(i, i + 3):
                    for y in range(j, j + 3):
                        c = board[x][y]
                        if c != "." and c in panel_hash:
                            return False
                        panel_hash.add(c)

        return True
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        return  self.is_row_valid(board) and \
                self.is_col_valid(board) and \
                self.is_square_valid(board)
    
    def is_row_valid(self, board):
        for row in board:
            if not self.is_unit_valid(row):
                return False
        return True

    def is_col_valid(self, board):
        for col in zip(*board):
            if not self.is_unit_valid(col):
                return False
        return True

    def is_square_valid(self, board):
        for i in (0, 3, 6):
            for j in (0, 3, 6):
                square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
#                 print(square)
#                 print()
                if not self.is_unit_valid(square):
                    return False
        return True

    def is_unit_valid(self, unit):
        unit = [i for i in unit if i != '.']
        return len(set(unit)) == len(unit)
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        def is_row_valid(board):
            for row in board:
                if not is_unit_valid(row):
                    return False
            return True

        def is_col_valid(board):
            for col in zip(*board):
                if not is_unit_valid(col):
                    return False
            return True

        def is_square_valid(board):
            for i in (0, 3, 6):
                for j in (0, 3, 6):
                    square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
    #                 print(square)
    #                 print()
                    if not is_unit_valid(square):
                        return False
            return True

        def is_unit_valid(unit):
            unit = [i for i in unit if i != '.']
            return len(set(unit)) == len(unit)

        
        return (is_row_valid(board) and
                is_col_valid(board) and
                is_square_valid(board))
s = set()
s.add(1)
s
board = [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
s = Solution()
s.isValidSudoku(board)
class Solution:
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    num = int(num)
                    box_index = (i // 3 ) * 3 + j // 3
                    
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False         
        return True
matrix = [['a'] * 4 for j in range(3)]
matrix
[[1] for i in range(9) for i in range(9)]<jupyter_output><empty_output><jupyter_text>794 Valid Tic-Tac-Toe State	(String Matrix) (Microsoft Onsite 4->0)O(m*n)  O(1)  To find the validity of a given board, we could first think about the cases where the board is invalidSince X starts first, x_count >= o_count. So if o_count > x_count, we can return FalseSince the players take turns, we could also return False if x_count-o_count>1After the corner cases, this is the algorithm used:If player O has a winning condition, also check the following:a) If player X also has a winning condition, return Falseb) If x_count != o_count , return False (Since player O always plays second, it has to meet this condition always)If player X has a winning condition, check the following:a) If x_count != o_count + 1, return False (Since player X plays the first move, if player X wins, the player X's count would be 1 more than player O)<jupyter_code>class Solution:    
    def validTicTacToe(self, board):
        """
        :type board: List[str]
        :rtype: bool
        """    
        X, O = 0, 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "X":
                    X += 1
                elif  board[i][j] == "O":
                    O += 1
        
        def win(board, player):
            """
            Check if the given player has a win position.
            Return True if there is a win position. Else return False.
            """
        
            #Check the rows
            for i in range(len(board)):
                if board[i][0] == board[i][1] == board[i][2] == player:
                    return True                        

            #Check the columns
            for i in range(len(board)):
                if board[0][i] == board[1][i] == board[2][i] == player:
                    return True 

            #Check the diagonals
            if board[0][0] == board[1][1] == board[2][2]  == player or \
                   board[0][2] == board[1][1] == board[2][0] == player:
                return True

            return False
        
        if X == O:
            if win(board, 'O') and win(board, 'X'):
                return False
            
            if win(board, 'X'):
                return False
            
            if win(board, 'O'):
                return True
        
            return True
        
        elif X == O + 1:
            if win(board, 'O') and win(board, 'X'):
                return False
            
            if win(board, 'X'):
                return True
            
            if win(board, 'O'):
                return False
            
            return True
        
        else:
            return False
class Solution:    
    def validTicTacToe(self, board):
        """
        :type board: List[str]
        :rtype: bool
        """    
        X, O = 0, 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == "X":
                    X += 1
                elif  board[i][j] == "O":
                    O += 1

        if O not in {X-1, X}: 
            return False
        
        def win(board, player):
            """
            Check if the given player has a win position.
            Return True if there is a win position. Else return False.
            """
        
            #Check the rows
            for i in range(len(board)):
                if board[i][0] == board[i][1] == board[i][2] == player:
                    return True                        

            #Check the columns
            for i in range(len(board)):
                if board[0][i] == board[1][i] == board[2][i] == player:
                    return True 

            #Check the diagonals
            if board[0][0] == board[1][1] == board[2][2]  == player or \
                   board[0][2] == board[1][1] == board[2][0] == player:
                return True

            return False
        
        if win(board, 'O'):
            if win(board, 'X'):
                return False
            return O == X  
        
        if win(board, 'X') and X != O + 1:
            return False
        
        return True<jupyter_output><empty_output><jupyter_text>54 Spiral Matrix (Matrix) (Amazon OA 19->8, Microsoft 8->17, Google 5->4, Apple 5->6, Facebook 7, ByteDance 3)  Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]  Output: [1,2,3,6,9,8,7,4,5]O(m*n)  O(1)<jupyter_code>class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
    
        m = len(matrix)
        n = len(matrix[0])
        
        res = []
               
        maxUp = maxLeft = 0
        maxRight = n - 1
        maxDown = m - 1
        direction = 0
        
        while len(res) < m * n:
            if direction == 0: #go right
                for i in range(maxLeft, maxRight+1):
                    res.append(matrix[maxUp][i])
                    
                maxUp += 1
            elif direction == 1: # go down
                for i in range(maxUp, maxDown+1):
                    res.append(matrix[i][maxRight])
                    
                maxRight -= 1
            elif direction == 2: # go left
                for i in range(maxRight, maxLeft - 1, -1):
                    res.append(matrix[maxDown][i])
                maxDown -= 1
            else: #go up
                for i in range(maxDown, maxUp - 1, -1):
                    res.append(matrix[i][maxLeft])
                maxLeft += 1
                
            direction = (direction + 1 ) % 4

        return res
class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        
        return list(matrix.pop(0)) + self.spiralOrder(list(zip(*matrix))[::-1])
s = Solution()
matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

print(matrix and matrix.pop(0))

matrix2 = list(zip(*matrix))[::-1]
print('matrix2 =', matrix2)
print(matrix2 and matrix2.pop(0))


matrix3 = list(zip(*matrix2))[::-1]
print('matrix3 =', matrix3)
print(matrix3 and matrix3.pop(0))

matrix4 = list(zip(*matrix3))[::-1]
print('matrix4 =', matrix4)
print(matrix4 and matrix4.pop(0))

matrix5 = list(zip(*matrix4))[::-1]
print('matrix5 =', matrix5)
print(matrix5 and matrix5.pop(0))

matrix6 = list(zip(*matrix5))[::-1]
print('matrix6 =', matrix6)
print(matrix5 and matrix6.pop(0))

# s.spiralOrder(matrix)

1 and 32
l1 = [1,2,3]
l1 += [3]
l1<jupyter_output><empty_output><jupyter_text>59 Spiral Matrix II (Microsoft Onsite -> 7, Amazon 3->0)   Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.Input: n = 3  Output: [[1,2,3],[8,9,4],[7,6,5]]<jupyter_code>class Solution:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        l = n * n + 1
        while l > 1:
            l, r = l - len(res), l
            res = [list(range(l, r))] + list(zip(*res[::-1]))
        return res
class Solution():
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if not n:
            return
        
        
        cur = 0
        matrix = [[0 for i in range(n)] for j in range(n)]
        maxUp = maxLeft = 0 
        maxDown = maxRight = n - 1
        direction = 0
        
        while True:
            if cur == n * n:
                return matrix
            
            if direction == 0: #go right
                for i in range(maxLeft, maxRight+1):
                    cur += 1
                    matrix[maxUp][i] = cur
                maxUp += 1
            elif direction == 1: # go down
                for i in range(maxUp, maxDown+1):
                    cur += 1
                    matrix[i][maxRight] = cur
                maxRight -= 1
            elif direction == 2: # go left
                for i in range(maxRight, maxLeft - 1, -1):
                    cur += 1 
                    matrix[maxDown][i] = cur
                maxDown -= 1
            else: #go up
                for i in range(maxDown, maxUp - 1, -1):
                    cur += 1
                    matrix[i][maxLeft] = cur
                maxLeft +=1       
            
            direction = (direction + 1) % 4<jupyter_output><empty_output><jupyter_text>48 Rotate Image (Matrix) (Amazon 9->8, Microsoft Onsite 8->6, Facebook 4,Apple 8)  Input: matrix =   [[1,2,3],  [4,5,6],  [7,8,9]]  Output:   [[7,4,1],  [8,5,2],  [9,6,3]]  O(row*col)  O(1)<jupyter_code>class Solution:
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)        
        # transpose matrix
        for i in range(n):
            for j in range(i, n):
                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i] 
        
        # reverse each row
        for i in range(n):
            matrix[i].reverse()
class Solution:
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = zip(*matrix[::-1])
        
s = Solution()
matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
# matrix[:]
# s.rotate(matrix)
# matrix
x = zip(*matrix[::-1])
for i in x:
    print(i)
list(zip(*matrix[::-1]))<jupyter_output><empty_output><jupyter_text>867 Transpose Matrix (Microsoft Onsite ->2, Apple 3). Input: matrix =   [[1,2,3],  [4,5,6],  [7,8,9]]. Output:  [[1,4,7],  [2,5,8],  [3,6,9]]<jupyter_code>class Solution():
    def transpose(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        m, n = len(A), len(A[0])
        ans = [[0] * m for _ in range(n)]
        
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                ans[c][r] = val
        return ans
class Solution:
    def transpose(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        
        A[:] = zip(*A)
        return A<jupyter_output><empty_output><jupyter_text>73 Set Matrix Zeroes (Matrix) (Amazon 7->2, Microsoft Onsite 5->4, Facebook 5, Apple 3)  Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.时间复杂度: O(m * n)  空间复杂度: O(1)<jupyter_code>import math
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    for k in range(row):
                        if matrix[k][j] != 0:
                            matrix[k][j] = math.inf
                            
                    for k in range(col):
                        if matrix[i][k] != 0:
                            matrix[i][k] = math.inf
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == math.inf:
                    matrix[i][j] = 0 
class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        is_col = False
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            # Since first cell for both first row and first column is the same i.e. matrix[0][0]
            # We can use an additional variable for either the first row/column.
            # For this solution we are using an additional variable for the first column
            # and using matrix[0][0] for the first row.
            if matrix[i][0] == 0:
                is_col = True
            for j in range(1, n):
                # If an element is zero, we set the first element of the corresponding row and column to 0
                if matrix[i][j]  == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        # Iterate over the array once again and using the first row and first column, update the elements.
        for i in range(1, m):
            for j in range(1, n):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0

        # See if the first row needs to be set to zero as well
        if matrix[0][0] == 0:
            for j in range(n):
                matrix[0][j] = 0

        # See if the first column needs to be set to zero as well        
        if is_col:
            for i in range(m):
                matrix[i][0] = 0<jupyter_output><empty_output><jupyter_text>311 Sparse Matrix Multiplication (Matrix) (Facebook 5->6, Microsoft Onsite->0, Apple 4->3 , Amazon 2)O(m*n)  O(m*n)<jupyter_code>class Solution:
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
            
        rowA = len(A)
#         print('mA=', mA)
        colA = len(A[0])
#         print('nA=', nA)
        colB = len(B[0])
#         print('nB=', nB)
        res = [[0]*colB for n in range(rowA)]
#         print('res=', res)

        for i in range(rowA):
            for j in range(colA):
                if A[i][j]:
                    for k in range(colB):
                        res[i][k] += A[i][j]*B[j][k]
        return res
class Solution(object):
    def multiply(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        
        rowA = len(A)
#         print('mA=', mA)
        colA = len(A[0])
#         print('nA=', nA)
        colB = len(B[0])
#         print('nB=', nB)
        res = [[0]*colB for n in range(rowA)]
#         print('res=', res)
        
        for i in range(rowA):
            for k in range(colB):
                for j in range(colA):
                    if A[i][j]:
                        res[i][k] += A[i][j] * B[j][k]    
        return res
def matrixmult (A, B):
    rows_A = len(A)
    cols_A = len(A[0])
    rows_B = len(B)
    cols_B = len(B[0])

    if cols_A != rows_B:
      print("Cannot multiply the two matrices. Incorrect dimensions.")
      return

    # Create the result matrix
    # Dimensions would be rows_A x cols_B
    C = [[0 for row in range(cols_B)] for col in range(rows_A)]

    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                C[i][j] += A[i][k] * B[k][j]
    return C
s = Solution()
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

A[1][0]

s.multiply(A,B)
import numpy as np
x = np.array(A)
y = np.array(B)
z = x @ y<jupyter_output><empty_output><jupyter_text>498 Diagonal Traverse (Facebook 11->4, Google 2->0, Amazon 2)  ![diag1-grid.jpeg](data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wBDAAMCAgICAgMCAgIDAwMDBAYEBAQEBAgGBgUGCQgKCgkICQkKDA8MCgsOCwkJDRENDg8QEBEQCgwSExIQEw8QEBD/2wBDAQMDAwQDBAgEBAgQCwkLEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBD/wAARCAFOAU4DASIAAhEBAxEB/8QAHQABAQABBQEBAAAAAAAAAAAAAAgCAwUGBwkEAf/EAEkQAAEDAwIDAwkGBQMACQQDAAECAwQABREGBwgSIQkiMRMUGTJBUXaWtDhSVFZx0TY3QmHSFRYjGCQzQ2hygZGxYmam5Jek1f/EABoBAQACAwEAAAAAAAAAAAAAAAADBAECBgX/xAAxEQACAQIDBwMEAgIDAQAAAAAAAQIDBBEhMQUSQUJRYWJxscETMoHwBtGRoRUWI1L/2gAMAwEAAhEDEQA/APVOlKUApSlAKUpQClKUApSlAKUpQClKUApSlAKUpQCuL7mauvOhNDXXVentDXXWFxgNoVHslrU2mTLUpaU4QXCEjAUVE/dScAnpWuxrXR991BetBWjWEBzUNojNO3CFFlNrlwEPhQacW2c8pPKSOYewZGCM7TtlpG4be6MtWhp2sL7qtdsY8iq73t5DsyT3icuKSlIOM4HTOAASfGspYgz19u3oza/TEbVmuZki3wpM2HbkhuK5Ic84kupbbRyNJUo4UrrgdACa5klxC/VUDivkVbWFoKVoSsFSVgKGRzAgg/qCAR/cVwC7Xfd60buWK02vStkkbeyLXMeu12euS0zWJqVtBltDIbIIIK+nNhQ5iVIKEpcYJ6A7MpWlHfTIbC0+BrVrAFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAVwDcjcjUuiNS6Kslk2wvmpoep7quBcbjAcYS1aGgw44HnQ4tJIygezGAoAlZQhe+63j6gv2jdQ2fQOqIlm1E7DfiQbi4wJSYEtTeW1ra5hzFPMlXKT7QcEdDlp9q8pscG16lujd0uceM01NnNRfNkSXgkBbqWgpQbCiCeUEgZxWUD9asNlF3m6jtlqhsXK5oZbmzGmEpekpaCg0HFgZWEhagMk4BIFb203yJGR3vfWEWKiKjlTWvRgVpPx25CeVYyK1aVgHWlttsLZaFrPV2rtzLrMsky4PX+RIv8poR7LH8khKmWlJQnkYT5MkJOcZwOuSefWe82rUFriXqyXKLcIE5lEiNKiupdaeaUMpWhaSQpJBBBBwaXmz2vUFqmWS9W+POgXBhyLKjSGw4080tJStC0nopJBIIPiDXXmtNZ6h221DofTOmdqrvfrTfribXKlWsx2o1jjIjuLS4tK1pwkeTSAAAnlCgDz8iF51B2hStJiQ3ITzIORWrWAKUpQClKUApSlAKUpQClKUApSlAKUpQClKUApSlAKUpQCvyhrzr4TOEzbrf/AG6veu9d6p1+1cmtX3y2JTbNVy4rAYYlrDQDQUUp5UkJwnAwkdPEkD0UyPfTI99Sr6N3Yf8AN+6nztM/eno3dh/zfup87TP3oCqsj30yPfUq+jd2H/N+6nztM/eno3diPzfup87TP3oCqsj30yPfUq+jd2H/ADfup87TP3p6N3Yf837qfO0z96AqrI99Mj31Kvo3dh/zfup87TP3rY9YcAexukrM5eGZO9t9LfTzW06vlPPnp7EFYJH6Z/SsNqKxZtCEqklCOrLGyPfXA71vLpixbt2PZuZbb6u8X61y7qxKZtT7kFtthbaVJckBPIknynvwnCQopK2wrzH1Rt1opd8Fm0ratxba75UMeb3XWtyfkqcJwkcqVt8hOR3cH9a7I4I+D7aTffZuVr3U931zAmjUt2gNt2rVMuM15Bl/lbyjmPeCAlJPt5QT1yTBRuadeTUOB6W0Nj3OzKcJ3OCctFji8uOWXHqXvpLbfRugp9/n6IsEa2Oaqurl6uymskyZi0JSpw5JxkIHQYA64Aya5k22hHeAGT41K47NzYZIwnV26YH9tbTP3r99G7sP+b91PnaZ+9WWzyyqsj30yPfUq+jd2H/N+6nztM/eno3diPzfup87TP3rAKqyPfTI99Sr6N3Yf837qfO0z96ejd2H/N+6nztM/egKqyPfWnIZRIbKFHoaln0buw/5v3U+dpn709G7sP8Am/dT52mfvQHeFls2vbHr7UN3u2sodw0tcI0Nuz2du2+SdtzyPKeXUp/nPlQ5lB6pGMYGAOvNIcyNOitTIr7bzLyQttxtYUlaT4EEdCP71Jsjs79hWpjUNi/7lz3SoKdYka1mlko9oc5VA4I6YBB610xwb8JOx2/+1E7cF6Fq3R7f+47nbo1q07qudHitMR3A22SkrVzOFIHOoYCj15R4V5Nrtmhf3lW0tk5KllKaw3FL/wCMccXJLOSSajkm08iSVNxipPj+4no/ke+mR76lX0buw/5v3U+dpn709G7sP+b91PnaZ+9esRlVZHvpke+pV9G7sP8Am/dT52mfvT0buxH5v3U+dpn70BVWR76ZHvqVfRu7D/m/dT52mfvT0buw/wCb91PnaZ+9AVVke+mR76lX0buw/wCb91PnaZ+9bHrDgD2N0lZnLwzJ3tvpb6ea2nV8p589PYgrBI/TP6VhtRWLNoQlUkoR1ZY2R76ZFeReqNutFLvgs2lbVuLbXfKhjze661uT8lThOEjlStvkJyO7g/rXdvAVuFuvbG29Hw7Nb5+iEX/UqLndpt0eXPZfZlttRkJSpKi4A2gjvK6jJKk8gDkVvXhdSlGnwPS2hsi42XThO5wTnoscXlxyy49T0IpWjFkJkNBxPtFa1THlilKUApSlAKUpQClKUB+HwqVezd/kPf8A4/1J9YqqqPhUq9m7/Ie//H+pPrFUBVdKUoBSlKAUpSgFdXbmbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFNzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICuQbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kkwSk6j3Ifl/C7+x6dGjC0gri4WLf2x6+UvHoub0Orm+Fq1WzXGg9SsSn7k9a5cidqGfLXzPT5XKHGXSCemHU+HXpjxOSeBdln9mB/4wvn1FV/Ugdln9mB/wCML59RW1OjCljuLUr3d9Xvd368sd1YL8tv5/xgiv6UpUpUFKUoBSlKAVt1wuDodFutwC5Sx1P9LSfvH9qXC4Oh0W63ALlLHU/0tJ+8f2rXt9vagNFKSVuLPM44r1lq95rj76+udu3M9lbKm4Qg8K1ZcvWnTfGo+aWlNeeCViMVSW/PXgvl9vcW+3tQGilJK3FnmccV6y1e81JXZZ/Zgf8AjC+fUVX9SB2Wf2YH/jC+fUV0tjY22zLaFpaQUKcVgkv3NvVt5t5vMhlJze9LUr+lKVbNRSlKAUpSgFdXbmbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFNzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICuQbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kkwSk6j3Ifl/C7+x6dGjC0gri4WLf2x6+UvHoub0Orm+Fq1WzXGg9SsSn7k9a5cidqGfLXzPT5XKHGXSCemHU+HXpjxOSejez7YQ/pnUCHBkf71v/wBaur0qD+z0/hvUHxrf/rV1YtaUKO9uLDFf0Vry+r3259eWO7kvy2/n/GCKktVuhbL2/WWrtXbl3WZZJs96/wAiRf5TQj2WP5JCVMsqCE8jCfJkhJzjOB1yTz+z3m1agtcS9WS5RbhAnMokRpUV1LrTzShlK0LSSFJIIIIODWN1s9r1BZ5dkvVvjzoFwjriyo0hsONPNLSUrQtJ6KSQSCD4g119rTWeodttQ6H0zpnaq7360364m1ypVrMdqNY4yI7i0uLStacJHk0gAAJ5QoA8/IhbUqnaFK0mJDchPMg5FatYApSlAKUpQClKUB+HwqVezd/kPf8A4/1J9YqqqPhUq9m7/Ie//H+pPrFUBVdKUoBXzXG4wLRAk3W6TGYkOG0p+Q+8sIbabSMqUpR6AAAkmvprz44tNnONzix3ivWz1juzWi9kbaqOHrm4nyKbllpK15QFeVlkKUQEjkZynqeYZoDsDhl7Ruw8TnENfdlNLbbLhWi1wps+FqJV58qZzTDzbaVebeQT5MLDnMP+VWAB456d7bmbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFeS3Zv6C3R0jxD6im6ChMuvuQLlpqBOmDkQkiS15SXydcobSyfeOdSQObqK9ids9s7PtrZ3IkR52fdJ7nnN1usnvSJ0g9StZOTjJOE5wAfaSSYJSdR7kPy/hd/Y9OjShaQVxcLFv7Y9fKXj0XN6DbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kknmNKVLGKgt2OhQrVp15upUeLYqQOyz+zA/wDGF8+oqv6kDss/swP/ABhfPqK2Iyv6UpQCpF4ru0p2Z4XtRuaBVaLlrDV7DaXJNutzqGWIfMAUpffVnlWUkEJShZwRnGRVdVHm33ZxaQ0fxRTuJu/7gydVzJkybck2q52lsoZlvnKHEOhf/dAkJBQT4HORmgOtdlu2X2i1/qiHpnc3bm5aBTcHksM3JNzRcobS1HALyvJNLbT4d4IUB7cDJq+ZV18v5OLZ1ofefQFpcScoQgjIWSPHp4VE/aV7abDaiXo7cfeF5uJA0m+8ZrUBA/1O/qWlPm9qZIwolawVE57iAT3ebnTXu0sWSxtzp164WFmzTJFsjOv29rPLDJbBDAJA6NghHgPV8BXH319c7duZ7K2VNwhB4Vqy5etOm+NR80tKa88ErEYqkt+evBfL7e5yW329qA0UpJW4s8zjivWWr3mvqpSulsbG22ZbQtLSChTisEl+5t6tvNvN5kMpOb3paipA7LP7MD/xhfPqKr+pA7LP7MD/AMYXz6irZqV/SlKAVJvFx2jW0XCle06Ik2a46t1ephMhy1wHUMtRUK6o8u+rPIVDqEpQs46kAEZrKp0uHBrw66Y3tuPFtfYtyXqKGJF1muzZXnMNCgzgvhlSFKCm0J7nIRjAwDQHUHDP2s20m+2tIG3mstFz9AXq7uiPbnHrgidBfeJwlovhDakLUeict8pPTmBxmmdzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICvN3fa26T49OKrTOtdhbPNkWa1RWIy7yiC5Dcu8pt4rDuFpS4hhkFIU8sA+KQM4r1B2w2ys+2dkXDivOT7rOX5xdbrIPNInSD6y1KOTjJPKnPQH2kkmCUnUe5D8v4Xf2PSo0oWkFcXCxb+2PXyl49Fzeh+7Z7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xpSpYxUFux0KNatOvN1KjxbFQf2en8N6g+Nb/wDWrq8Kg/s9P4b1B8a3/wCtXVijzen9ET4F3I9RP6VhIYTIbKFeBrNHqJ/SsqhMnBbLZdfWPX2obtd9Yw7hpa4Robdns7ds8k9bnkeU8upT/OfKhzmQeqRjGBgDrzOHMjz4rUyI+28y8gLbcbWFJWk+BBHQj+9JkOLPjuxJjCHmXkKbcbWnKVpIwQR7QQcV1bZHNnuG2FofZ21uxdMW+9S3LRpq3BLqxIkBKnlo8phWFHvHK1DJIA6kCs6g7ZpWKVJUMpOayrAFKUoBSlKA/D4VKvZu/wAh7/8AH+pPrFVVR8KlXs3f5D3/AOP9SfWKoCq6UpQCurN0Nzbu1dU7X7YMNXDWM9oredV1j2eOR1kPnwBwe6jxJI6HICstzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICt+232xtG29ifhQ3nbhdbgoyLpdZJzInyDnK1qPUDJOE5wAfaSSYJSdR7kPy/hd/Y9OjRhaQVxcLFv7Y9fKXj0XN6Hln2bGsb3qrj21LGucj/qto05eYUOOjo202iZHTkD7ysZUfEn+2BXr/XmXwDcHXEdsrxeap3Q3N26/wBG0xcrdd2Is7/V4Ejyjj0tpxoeTZfW4MpQo5KQBjrg16aVLGKgt2OhQq1Z15upUeLYpSlbEYqQOyz+zA/8YXz6iq/qQOyz+zA/8YXz6igK/pSlAK6m4ieIjRPD3oiVqrVU8pWCGIsZhIcky5Kh/wAcdhv/ALx5fsHgkZUrAHXse5XF5C/MLajystScnGMNj3n2Z91eQPEjww9ppvzvG9uQ7thPtzFomOHTDULV1qYNsZS5ltxtQmBQeVhKludFFXuASlPH319c7duJ7K2VNwhB4Vqy5etOm+NR80tKa88ErEYqkt+evBfL7e5UuxnCxuTv3ubbuKfi8jqiG3r850ZoArKmbQgkKQ/Kz67xISopIyVAFeMJbTddeK3/AEae2S/Me6v/APLDH/8Ao16z8Pdo19YNjdCWTdN2a7rCDYIbF8XNnCZIVNS0kOlx8LWHVc2crClZ8cmulsbG22ZbQtLSChTgsEl+5t6tvNvN5kMpOb3panYVKUq2aipA7LP7MD/xhfPqKr+pA7LP7MD/AMYXz6igK/pSlAKnvcvfTRm6DEvY3am6QdR3/UxmWOWryi240FtKVolFbnTmWhKXByoJIIOeuArme5m5l4avLe121zLU/Wc9vmddV3o9njnxkPnqM4PdR4kkdDkBUU8SnZ88SFs3BsO9/C7ui9M1HZ2udyJOloiyEzFZLrzCljyK0ulR523SPcVLBwIJSdR7kPy/hd/Y9OjRhaQVxcLFv7Y9fKXj0XN6HVvaG7OvcGa9p90tkdwb3ZL0wXbUtuPJLTZU0lLnlG2k9Etq9RTZykgIBz1J9QdjddT9ztm9E7iXWEYk3UdihXKSwUcvI66ylShj2dSelebll4BeNriu3EsmrOOLWzUGx2TDaoaZUNctxnmBU0w1AHm7XPgBTmebw6KIGPU+z2m3WC0wrHaIqI0G3x24sZlHqttISEpSP7AACpYxUFux0KFatOvN1KjxbPspSlbEYqD+z0/hvUHxrf8A61dXhUH9np/DeoPjW/8A1q6mo83p/Rh8C7keon9KyrFHqJ/SsqhMiuD3LcXSjm57G0kiDdDfzaFX5h9VqeVDDAdDSsSuXyaXAop7uR6w9vStLeW9bt2HTEOZs3pSyX+8Lu0FqVHutwXEbbgqfQJDiVJQrJDZV/5RlQCykNq5Uhz/AFNpIVhCwO8EqJAPtAOBn9cVlA+qE0W2+q+bNfTWmw35JsIznFalYYFKUoBSlKA/D4VKvZu/yHv/AMf6k+sVVVHwqVezd/kPf/j/AFJ9YqgKrrq7czcy8NXlva7a5lqfrOe3zOuq70ezxz4yHz1GcHuo8SSOhyApuZuZeGry3tdtcy1P1nPb5nXVd6PZ458ZD56jOD3UeJJHQ5AVyDbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kkmCUnUe5D8v4Xf2PTo0YWkFcXCxb+2PXyl49Fzeg2z2zs+2tnciRHnZ90nuec3W6ye9InSD1K1k5OMk4TnAB9pJJ5jSlSxioLdjoUK1adebqVHi2KUpWxGKUpQCpA7LP7MD/AMYXz6iq/qQOyz+zA/8AGF8+ooCv6264XB0Oi3W4BcpY6n+lpP3j+1LhcHQ6LdbgFyljqf6Wk/eP7Vr2+3tQGilJK3FnmccV6y1e81x99fXO3bmeytlTcIQeFasuXrTpvjUfNLSmvPBKxGKpLfnrwXy+3uLfb2oDRSklbizzOOK9Zavea+qlK6WxsbbZltC0tIKFOKwSX7m3q28283mQyk5velqKUpVs1FKUoBUgdln9mB/4wvn1FV/Ugdln9mB/4wvn1FAV/XV25m5l4avLe121zLU/Wc9vmddV3o9njnxkPnqM4PdR4kkdDkBTczcy8NXlva7a5lqfrOe3zOuq70ezxz4yHz1GcHuo8SSOhyArkG2e2dn21s7kSI87Puk9zzm63WT3pE6QepWsnJxknCc4APtJJMEpOo9yH5fwu/senRowtIK4uFi39sevlLx6Lm9BtntnZ9tbO5EiPOz7pPc85ut1k96ROkHqVrJycZJwnOAD7SSTzGlKljFQW7HQoVq0683UqPFsUpStiMUpSgFQf2en8N6g+Nb/APWrq8Kg/s9P4b1B8a3/AOtXU1Hm9P6MPgXcj1E/pXH4+t9G37UF70FZ9Y293UVmjtOXGDElNrlwEvhXklrbOeQnlJHMPdkYIzsO4m5GpdEaj0TZLJthfNTQ9TXRcC43GA4wlq0NBhxwPOhxaSRlA9mMBQBKyhC+QNafsgvM3UtrtUKPc7ohhqdNaYSl6ShnmDSXFgZWEBagnJOASBUWBk2rbbSU/QWjrVoifq6+aqctjPklXa9OodmSTzE5cUlKQcZwOnQADJxmuXsRWo+eQYzWTTfIkZHX31qUbApSlYApSlAKUpQH4fCoK4MdwdRwNnbptltvA861heNb6kkB91B82tcQzlpMp04weoISnrkjwPRKr1Pga83OE7gv2i4htqpeqdxrlq5ydZ9TXqxR/ML67Fb82jy1pb5kI7pXykAqwMhI91aVIyksIvD94Fm1qUqMnUqx3mtFwx79l046aF57Z7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xqQPRZ8MH4vcD5qkU9Fnwwfi9wPmqRWYxUFux0Iq1adebqVHi2V/SpA9Fnwwfi9wPmqRT0WfDB+L3A+apFbEZX9KkD0WfDB+L3A+apFPRZ8MH4vcD5qkUBX9KkD0WfDB+L3A+apFPRZ8MH4vcD5qkUBX9Rp2ZTk+JwxeZR4riZEzVd8eaWtBCQ150U+UyfEZSofqDRzsyuGKJPYjwv8AfMyQlaVrae1VK8kEg5PPykHB9wINcK2C2C2w43tsGdyNyI1/srVlu9x09ZLJp69PQbfb7fGe5GUJZR3S5y4514HNgdAAAOPvr6527cz2VsqbhCDwrVly9adN8aj5paU154JWIxVJb89eC+X29y9rfb2oDRSklbizzOOK9Zavea+qpA9Fnwwfi9wPmqRT0WfDB+L3A+apFdLY2Ntsy2haWkFCnFYJL9zb1bebebzIZSc3vS1K/pUgeiz4YPxe4HzVIp6LPhg/F7gfNUirZqV/SpA9Fnwwfi9wPmqRT0WfDB+L3A+apFAV/SpA9Fnwwfi9wPmqRT0WfDB+L3A+apFAV/XnpwDbg6jgcOre2W28DzrWF41RfJAfdQfNrXEMopMp04weoISnrkjwPRKm4PANw6wNRxdt9smda3jWErldeEjVUpUS1xsjL0kpIPgeiAQTke9IVsnCNwjbOcUmziNwNwG9RwZcG9XKyxYtlvT0KM3Gjvcrf/Gnpz48VdM4FQSk6j3Ifl/C7+x6dGjC0gri4WLf2x6+UvHoub0L12z2zs+2tnciRHnZ90nuec3W6ye9InSD1K1k5OMk4TnAB9pJJ5jUgeiz4YPxe4HzVIp6LPhg/F7gfNUipYxUFux0KFatOvN1KjxbK/pUgeiz4YPxe4HzVIp6LPhg/F7gfNUitiMr+lSB6LPhg/F7gfNUinos+GD8XuB81SKAr+lSB6LPhg/F7gfNUinos+GD8XuB81SKAr+vPTgohaju+1uu7Xoq/wAezX6RqfUrFvuL0bzlEOSqU55N1TWRzcpIVgn3ePgewHOzK4Yok9iPC/3zMkJWla2ntVSvJBIOTz8pBwfcCDXG+A9mwPnWl+01paDYGbrri8KVChc3kmwy6GE45iT1S0FEDA5lL5QkEJHm7P2zSvr6tZ20XJUlhOaw3FPFf+afGSWcsFhHJN4vA3nTcYqUuP7iWfp9m7pscG16iubdzuUeM21MnNxhHTJeCQFuhoKUEBRBPKCQM4FbzFioio5U1kw2hKEqCRkitWvTxNBSlKwBSlKAUpSgFKUoD8PhUq9m7/Ie/wDx/qT6xVVUfCpV7N3+Q9/+P9SfWKoCq6UpQClKUApSlAK264XB0Oi3W4BcpY6n+lpP3j+1LhcHQ6LdbgFyljqf6Wk/eP7Vr2+3tQGilJK3FnmccV6y1e81x99fXO3bmeytlTcIQeFasuXrTpvjUfNLSmvPBKxGKpLfnrwXy+3uLfb2oDRSklbizzOOK9Zaveakrss/swP/ABhfPqKr+pA7LP7MD/xhfPqK6WxsbbZltC0tIKFOKwSX7m3q28283mQyk5velqV/SlKtmopSlAKUpQCurtzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICm5m5l4avLe121zLU/Wc9vmddV3o9njnxkPnqM4PdR4kkdDkBXINs9s7PtrZ3IkR52fdJ7nnN1usnvSJ0g9StZOTjJOE5wAfaSSYJSdR7kPy/hd/Y9OjRhaQVxcLFv7Y9fKXj0XN6DbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kkmceyz+zA/8AGF8+oqv6kDss/swP/GF8+oqWMVBbsdChWrTrzdSo8Wyv6UpWxGKUpQClKUArbrhcHQ6LdbgFyljqf6Wk/eP7UuFwdDot1uAXKWOp/paT94/tWvb7e1AaKUkrcWeZxxXrLV7zXH319c7duZ7K2VNwhB4Vqy5etOm+NR80tKa88ErEYqkt+evBfL7e4t9vagNFKSVuLPM44r1lq95qGez0/hvUHxrf/rV1eFQf2en8N6g+Nb/9auur2XY22zLZWlpBQpwWCS9f9t6tvNvN5lepJzlvS1LuR6if0rKsUeon9KyqUClKUApSlAKUpQClKUB+HwqVezd/kPf/AI/1J9YqqqPhUq9m7/Ie/wDx/qT6xVAVXSlKAUpUf9pDxWSNgtq29CaEkrc3E1+FW2ztR+8/FZWeRySEjrzd4Ib6dVq/+k0BsF17ULSKuKyBw16L25/3DClXtiwvamTfAy2iSpXK7yRwwvyiW1ZTnyieYg+AwTZ1wuDodFutwC5Sx1P9LSfvH9q8beHLgf1fs9xF6U1lvRqeNZIdmulqMMK/7e636S2hxEFgEkrDSlguu4x3FAeClI9mbfb2oDRSklbizzOOK9Zavea4++vrnbtzPZWypuEIPCtWXL1p03xqPmlpTXnglYjFUlvz14L5fb3Fvt7UBopSStxZ5nHFestXvNfVSldLY2Ntsy2haWkFCnFYJL9zb1bebebzIZSc3vS1FSB2Wf2YH/jC+fUVX9SB2Wf2YH/jC+fUVbNSv6UpQCo742+0Ph8HWsNPaOa2r/3jJvducuLq/wDXf9P81SHORCcebu8/NhRzkYx7c1YleL3G3uVtpP7TGBM3ZKZeiNE/6dDu0ZyJ522420yZC2vI4IXzrcCSCMHPXABwB2b6c7/wu/8A5t/+hV56t3hvF4atOidroLUjWd/gMzXeZXlI9jjuoSovPqxgkBXdTjJODjqEqj60b38CO7tkiwNreFvQGmbjf7oiy2256x0TZIMTyizjyrZSXPKEexJAyfEHHKbt2r2s0/tXp/8A0u1Eyp0oh243F1I8tMex6x9yR1CUjoke8kkwSk6j3Ifl/C7+x6dGlC0gri4WLf2x6+UvHoub0NTbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kknmNKVLGKgt2OhQrVp15upUeLYqQOyz+zA/8YXz6iq/qQOyz+zA/wDGF8+orYjK/pSlAKnPiy46NnuEiLFg6s88vmp7i0XodhtpR5ctZIDry1EJZbJBAJyo4PKk4OKMrw4gbnbXa37STVu7HENeo7Wj9KXa5ykt3BsvNrEDLMRhDICis86UKSgDJI8PGgK52V7ZXajcPWcPSW422ly0KzcpCY0W6JuibjGQpRwkv4aaU0kkgZAWBnrgZIvubc1OKRDtRS9IeSFBYOUNoP8AUT/8VB2t7pwU8eUPTO6O4Vg1Jpa2Wu7jT1kud/ci2aNqBxxQ/wCBCkOLeebSUEDBbwVLGcg4vSx2SBYLczbre0lDbLaW04GO6kYAHuAAwBXH31/c7duZ7K2VNxhB4Vqy5etOm+NR80tKa88ErEYqkt+evBfL7e5rW+3tQGilJK3FnmccV6y1e819VKV0tjY22zLaFpaQUKcVgkv3NvVt5t5vMhlJze9LUVB/Z6fw3qD41v8A9aurwqD+z0/hvUHxrf8A61dejR5vT+jR8C7keon9KyrFHqJ/SsqhMilKUApSlAKUpQClKUB+HwqVezd/kPf/AI/1J9YqqqPhUq9m7/Ie/wDx/qT6xVAVXSlKA+a4zUW23yri4hS0RWVvKSnxISkkgf8AtXjttduZatebuap7RXikjTIWlbI+IuhLa42hzzuSkqS0xFaUoeVUykE59TyqlqUocisev11l+W5rRFZQ+8+gpcStIUhCCMEqB6Hp7K4jceHvY2/Wi1WPVGz2iL7DsjPkLczctPRJLUJsgAoYQ42UtI7qe6gAdB7q4++vrnbtzPZWypuEIPCtWXL1p03xqPmlpTXnglYjFUlvz14L5fb3PF7d/ja03uTxm6L32b/3c5oLR06BJi2qYywmY0lshUkoaS8Wuda8nJcyQEgkBIA9pNid6dLcQm19n3Z0ZAusK0XoOmOzdGm25KfJuKbPOltbiR1ScYUemK89d1uz43AunHhZtc6J4fdNo2aZuVrcmMRjao9vLCEIEnmgFxKlDmCsp8keb3GvTTTGk9LaIskfTWjNNWqwWiJzeb2+1w24sZnmJJ5GmwEpySScDxJrpbGxttmW0LS0goU4rBJfuberbzbzeZDKTm96WputKUq2aipA7LP7MD/xhfPqKr+pA7LP7MD/AMYXz6igK/pSlAK88twNg+EPcviBlan27gjXW5epbnMZlxrvJL9jhSm8h991lxsB5bQbWA0CtAKTzJJCQa83M3MvDV5b2u2uZan6znt8zrqu9Hs8c+Mh89RnB7qPEkjocgKibia7PTiNibgWHe3hi3Qfm6js7YdcizZiIkhE0kl1+OtQ8kpLpJ50OkdOhUsHAglJ1HuQ/L+F39j06NGFpBXFwsW/tj18pePRc3odbdqnw07b7KbNbaX3SiFs3ti6uWh9xCy23IaUwt0rSwDyNhC20hPIBhKgCT0NeiPB3qq/624XNsNU6ofcfuk/TcRcl5wkqdUE8ocJPiVBIVn+9QJbuBHjs4s9dWK98beuGrbp2xqIVEEqCuStrmBUhhm3jzdClgYLqlcwGOisYr1OsFitOl7Hb9N2KE3Et1rjNw4jDYwlpptIShI/QAVLGKgt2OhQrVp15upUeLZ99KUrYjFSB2Wf2YH/AIwvn1FV/Ugdln9mB/4wvn1FAV/SlKAV4y7I8Eb2vOL7VepN6ocSFo1jXN2iW2FcV+TOpJwfecSw0gnLjSEguOEZB5Cjr3+X2JuFwdDot1uAXKWOp/paT94/tUQ8dvA9vVvDqzTO82we5UiLqnSbWGLVLnKjNpdCyvziI4BytvKJwsLwFBKcqGMHj7++udu3M9lbKm4Qg8K1ZcvWnTfGo+aWlNeeCViMVSW/PXgvl9vc6k7Y/aXRekNqNsdSadhpt0i1XRywxYcU+RitxFMKdw3HThtvlUygApSOhAPgKufg61XfdccLe2GqdTPuP3OfpyIqS85nmdUlPIFnPiVBIVn+9efw4HO0F4ttXWIcZOuGrTpmwOHAVKt7j6myRz+QYgDyRcUBjyjpBA9/qn1Q0tpqzaM03a9JadhpiWuzRGoMNhPg2y2kJSP/AGArpbGxttmW0LS0goU4rBJfuberbzbzeZDKTm96WpulKUq2aioP7PT+G9QfGt/+tXV4VB/Z6fw3qD41v/1q6mo83p/Rh8C7keon9KyrFHqJ/SsqhMilKUApSlAKUpQClKUB+HwqVezd/kPf/j/Un1iqqo+FSf2cspqNsTeg6ceW3D1G0n/zGYrH/wAVDcXFK0purXkoxWGb0zeC/wBvAyk5PBFY1t1wuDodFutwC5Sx1P8AS0n7x/alwuDodFutwC5Sx1P9LSfvH9q17fb2oDRSklbizzOOK9Zavea5W+vrnbtzPZWypuEIPCtWXL1p03xqPmlpTXnglPGKpLfnrwXy+3uLfb2oDRSklbizzOOK9Zavea+qlK6WxsbbZltC0tIKFOKwSX7m3q28283mQyk5velqKUpVs1FKUoBUgdln9mB/4wvn1FV/Ugdln9mB/wCML59RQFf11duZuZeGry3tdtcy1P1nPb5nXVd6PZ458ZD56jOD3UeJJHQ5AU3M3MvDV5b2u2uZan6znt8zrqu9Hs8c+Mh89RnB7qPEkjocgK5BtntnZ9tbO5EiPOz7pPc85ut1k96ROkHqVrJycZJwnOAD7SSTBKTqPch+X8Lv7Hp0aMLSCuLhYt/bHr5S8ei5vQbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xpSpYxUFux0KFatOvN1KjxbFKUrYjFKUoBUgdln9mB/4wvn1FV/Ugdln9mB/4wvn1FAV/W3XC4Oh0W63ALlLHU/0tJ+8f2pcLg6HRbrcAuUsdT/S0n7x/ate329qA0UpJW4s8zjivWWr3muPvr6527cz2VsqbhCDwrVly9adN8aj5paU154JWIxVJb89eC+X29xb7e1AaKUkrcWeZxxXrLV7zX1UpXS2NjbbMtoWlpBQpxWCS/c29W3m3m8yGUnN70tRSlKtmopSlAKg/s9P4b1B8a3/61dXhUH9np/DeoPjW/wD1q6mo83p/Rh8C7keon9KyrFHqJ/SsqhMilKUApSlAKUpQClKUB+HwqMuBNqdF2QmJU2pKZGuNSy45Hisf6i43n/0U0oVSO8t63bsWmIczZvStkv14XdoLMpi63BcRtuCp9AkOJUlCskNlX/lGVALKQ2qHeEjg/wBtOITZV+5bkaj125/ouqb3aIcKFqeTHhtMszF8pSwk+TSs8x5lJSnmPUjJJPGfzz+MXX8w2R/xNvX+jGcoucsG3uxe9glis3JReOOSXEsWteNvU+o1iegmnRMbbIkWxbZcPMt9au8s/wBwetb3Ugeiz4YPxe4HzVIp6LPhg/F7gfNUivW/jWw/+ubNp7NVWVVQWClJRT/xCMVrni8ZNtuUm8zStV+tNzwwxK/pUgeiz4YPxe4HzVIp6LPhg/F7gfNUivdIiv6VIHos+GD8XuB81SKeiz4YPxe4HzVIoCv6VIHos+GD8XuB81SKeiz4YPxe4HzVIoCv689OAbcHUcDh1b2y23gedawvGqL5ID7qD5ta4hlFJlOnGD1BCU9ckeB6JU3B4BuHWBqOLtvtkzrW8awlcrrwkaqlKiWuNkZeklJB8D0QCCcj3pCtk4RuEbZzik2cRuBuA3qODLg3q5WWLFst6ehRm40d7lb/AONPTnx4q6ZwKglJ1HuQ/L+F39j06NGFpBXFwsW/tj18pePRc3oXrtntnZ9tbO5EiPOz7pPc85ut1k96ROkHqVrJycZJwnOAD7SSTzGpA9Fnwwfi9wPmqRT0WfDB+L3A+apFSxioLdjoUK1adebqVHi2V/SpA9Fnwwfi9wPmqRT0WfDB+L3A+apFbEZX9KkD0WfDB+L3A+apFPRZ8MH4vcD5qkUBX9KkD0WfDB+L3A+apFPRZ8MH4vcD5qkUBX9Rp2ZTk+JwxeZR4riZEzVd8eaWtBCQ150U+UyfEZSofqDRzsyuGKJPYjwv98zJCVpWtp7VUryQSDk8/KQcH3Ag1wrYLYLbDje2wZ3I3IjX+ytWW73HT1ksmnr09Bt9vt8Z7kZQllHdLnLjnXgc2B0AAA4++vrnbtzPZWypuEIPCtWXL1p03xqPmlpTXnglYjFUlvz14L5fb3L2t9vagNFKSVuLPM44r1lq95r6qkD0WfDB+L3A+apFPRZ8MH4vcD5qkV0tjY22zLaFpaQUKcVgkv3NvVt5t5vMhlJze9LUr+lSB6LPhg/F7gfNUinos+GD8XuB81SKtmpX9KkD0WfDB+L3A+apFPRZ8MH4vcD5qkUBX9KkD0WfDB+L3A+apFbHrDs2eGXSVmcvDNk3Zvpb6ea2nUbzz56exBUCR+mf0rDaisWbQhKpJQjqy26g/s9P4b1B8a3/AOtXUy6o2P2iXfBZtK6G1jbXfKhjze66pnPyVOE4SOVJb5Ccju4P61RnZwWqNZtI3yFCSpLSNY3pASpZVgNyPJJ6nJPdbGSSSSSc1izuYXEpqnwR6O0dkXOzKdOdzgnPRY4vLjllx6l+I9RP6VlWLf8A2af0rKtjzBSlKAUpSgFKUoBXHY+t9G37UF70FZ9Y293UVmjtOXGDElNrlwEvhXklrbOeQnlJHMPdkYIzsW5G5GpdEal0VZLJthfNTQ9T3VcC43GA4wlq0NBhxwPOhxaSRlA9mMBQBKyhC9/a0/ZBeZupbXaoUe53RDDU6a0wlL0lDPMGkuLAysIC1BOScAkCs4A2nbfSU/QWjbVoifq6+aqctjPklXa9OodmSTknLikpSDjOB06AAZOM10T2bgCdhr8keA19qQf/ANw1VDbYSgBQ64qWOzd/kPf/AI/1J9YqjYKrpSlYApSlAKUpQCurtzNzLw1eW9rtrmWp+s57fM66rvR7PHPjIfPUZwe6jxJI6HICm5m5l4avLe121zLU/Wc9vmddV3o9njnxkPnqM4PdR4kkdDkBXINs9s7PtrZ3IkR52fdJ7nnN1usnvSJ0g9StZOTjJOE5wAfaSSYJSdR7kPy/hd/Y9OjRhaQVxcLFv7Y9fKXj0XN6DbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kkmceyz+zA/wDGF8+oqv6kDss/swP/ABhfPqKljFQW7HQoVq0683UqPFsr+lKVsRilKUApSlAK264XB0Oi3W4BcpY6n+lpP3j+1LhcHQ6LdbgFyljqf6Wk/eP7Vr2+3tQGilJK3FnmccV6y1e81x99fXO3bmeytlTcIQeFasuXrTpvjUfNLSmvPBKxGKpLfnrwXy+3uLfb2oDRSklbizzOOK9Zaveakrss/swP/GF8+oqv6kDss/swP/GF8+orpbGxttmW0LS0goU4rBJfuberbzbzeZDKTm96WpX9KUq2ailKUApSlAK6u3M3MvDV5b2u2uZan6znt8zrqu9Hs8c+Mh89RnB7qPEkjocgKbmbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFcg2z2zs+2tnciRHnZ90nuec3W6ye9InSD1K1k5OMk4TnAB9pJJglJ1HuQ/L+F39j06NGFpBXFwsW/tj18pePRc3odXN8LVqtmuNB6lYlP3J61y5E7UM+WvmenyuUOMukE9MOp8OvTHick9I9np/DeoPjW//AFq6vCoP7PT+G9QfGt/+tXVi1owpb24tV/RWvL6vfbn15Y7uS/Lb+f8AGCLuR6if0rKsUeon9KyrBVFKUoBSlKAVx7WrGoL7o/UFo0FqaHZ9ROQ3osK4OsCUiBLU3lta2gocxTzJVyk+0HBHQ6GrtzNDaEvOmdParv7UC46wuBtdkjqbWtUuSGy4UDlSQnCUnvKwnqBnJFfBpDbLRm3tx1BO0Np+NbF6ruzl7u6mSo+czFoQlThyTjIQO6MAEkgdTWUsQbxYWruLLBtmo7m3c7kxGbamTm4wjpkvBIC3Q0CoICjk8oJAzgVvEWKiKjlTWbbSUdeUc3trUpiD8PhUq9m7/Ie//H+pPrFVVR8KlXs3f5D3/wCP9SfWKrAKrpSlAK8xtc9tT/svW2oNHf8ARq88/wBCusu2ec/7y8n5byLym+fk8xPLnlzjJxnGT416c11bd+GThfkvTb7fOHva5551TkuZLlaSt61rUSVOOOLU1kknJKicnqTQHn76c7/wu/8A5t/+hVn2LiTvO7e3mi1bX6faj6z11Y4t5dirkecx9PR320rLj7vIkLKQoco5QVdDy9QlXm+NpLNxscVL83aDaXS+l9s9PSFwrZHtVkj29i5NtLwuXILCE8zZX1JVk8vK2kZUcet20202m9o9NoslkbD0p4JXOnLQA5KcAxk49VA8EoHRI/vkmCUnUe5D8v4Xf2PTo0oWkFcXCxb+2PXyl49FzehrbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xpSpYxUFux0KFatOvN1KjxbFSB2Wf2YH/jC+fUVX9SB2Wf2YH/jC+fUVsRlf0pSgFSDxa9pVtFwtalVt+iw3DWWrmmkvSrfBkIjsQgoZSl99QVyrIIISlCiAQTjIzX1eP2urVB4T+0unb08R2k5kvQN/uUu4Wm+mCuXHZceb/4nQEg5cZOUlABWOigD0oCheHztftpN3NZ27Q24Ggp+38y7vpjQ5q7mifA8qo4Qh13ybSm+Y4APIU5PUgdauufcHPKC320ByU4Mk/0tJ+8a8+t8dDbL8fW5Og909Ew7nctIafS9GfuUS2yIEvU8kuILcKOHUNu+RaKVl2SoJS2CQlWedSPQezWtu1QWmAhPleRPlVA5yrHsJ9g9lcffX1xt25nsrZU3GEHhWrLl606b41HzS0przwSsRiqS3568F8vt7mrb7e1AaKUkrcWeZxxXrLV7zX1UpXS2NjbbMtoWlpBQpxWCS/c29W3m3m8yGUnN70tRUgdln9mB/wCML59RVf1IHZZ/Zgf+ML59RVs1K/pSlAKj7ix7THZ3hh1K7t/Gsk/Wur4yErl2+BIRHjwioZSh+QoK5VkEHlShZA9blyM1+sqCSUjJA6D+9eNXZ0x7Jq3tDtb3XcZLU3UDKr5Mt4nDnUJwlgLUkKz/AMiEFePaBnHh0Arnhf7VfZ/iC1fC281RpWdoHUd0X5K3plTUTIMp0+DQkBDZS4fYFNgE9ArJANG7mbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFeffao6L2mt29ek90Xp8S1zbTAW7fU28hEydKS4hUJvu4/5MBwlRPMEhJ6DBF8cLVu089szprXdqbW9O1pbIt8uU593yz8p95sLJU57UgqISPAD+5JMEpOo9yGnF/C7+x6VGlC0gri4WLf2x6+UvHoub0OWbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xpSpYxUFux0KNatOvN1KjxbFQf2en8N6g+Nb/9aurwqD+z0/hvUHxrf/rV1Yo83p/RE+BdyPUT+lZVij1E/pWVQmRSlKAUpSgOF7t6+0xtfoyRrnVkK5SYVveZbCbdbHZ0jyjziWkcjbaSoZUtI5ugGeprk9tUhbCVpUohaQoc6SlWD7wcEH+x619biedBTnGa61u923ctG71jtdp0pZJG3si1THrtdnrktM1ialbQZQhkNkEEFfTmwocxKkFCUuZWeQOzKVpR30yGwtPga1awD8PhUq9m7/Ie/wDx/qT6xVVUfCpV7N3+Q9/+P9SfWKoCq6UpQCpO4/eJbR21O0t90a/dXP8AUrxG8zmCKvDjEd0dWwQch11PMlIGCElSyQAM9wbmbmXhq8t7XbXMtT9Zz2+Z11Xej2eOfGQ+eozg91HiSR0OQFRr2gfBZvJuHt7ojR+xWj39YT2bnLu+prnIucOK/KlKbShDi1SXkFQ7zvKlPNygnrkkmCUnUe5D8v4Xf2PTo0YWkFcXCxb+2PXyl49Fzeh3z2dGkRa+G+y65lWqNBmazBuTbDDYSmNABKYjCfeA2Ob+6nFHpnFVFXFNptLuaI2v0jo96ImK7ZbJCgusJKSG3G2UpUnKSQcKB6gkH31yupYxUFux0KFWrOvN1KjxbFKUrYjFSB2Wf2YH/jC+fUVX9SB2Wf2YH/jC+fUUBX9KUoBXlDp/ZrXvHtxX6h11v1LnNbXafvlwsunLI7MXHbuCori0FqOhJB5AG1LedR3iocgJwSj1NuFwdDot1uAXKWOp/paT94/tUF8Y/BnxV6i3bsW+/DNul/17TzAbgWN+S3DNucI/5VRipPkHEunKlpdwT4EqSEpTx9/fXO3bmeytlTcIQeFasuXrTpvjUfNLSmvPBKxGKpLfnrwXy+3udW9qdpK58Od42h3d2f1vddNy7SHbJb7XCkeSiwkMpSsKYaThKUqHccSQQsBAPQYr0g2Q11N3O2e0XuJcoRiS9R2OHcpDBSU+TcdaSpQwfDqT0rzOi8BfHjxabhWTUHGhrBi12SzENrQqXBck+Q5srbjMW8eQQpeAC4ogjoe9jFerNhsds0zY7fpyyxUxrfa4rUOKynwbabSEoSP0AFdLY2Ntsy2haWkFCnFYJL9zb1bebebzIZSc3vS1PvpSlWzUVIHZZ/Zgf+ML59RVf1IHZZ/Zgf8AjC+fUUBX9KUoBXmfxKcGO3us+LOzay2I3IftWtb5Ncm3W122Z5BuPJbSSuQmW0vnjKPKorbQlS+iiOUkA2/uZuZeGry3tdtcy1P1nPb5nXVd6PZ458ZD56jOD3UeJJHQ5AVDXEfwFcWemN17PvnwtbjOXm725oL82ky2IktiWpJ8u4jy+I7rbpKipLis97B5gARBKTqPch+X8Lv7Hp0qMLSCuLhYt/bF8fKXj0XN6ExdozsHqfZlWkrzuduZ/uTWeqn5shyFFWtUODEb5BkLdHlX3VrWSp1fLzYxy9K9h+GXS8jRXDvttpSWlaXrXpe2x3Av1goR0ZB6DrUHbVdn5xQ79bx2nerjy1fHktWbyS2rK3JjuvyPJq5kMqTEAjMM83VXkySrqCBnmr07QhDaEttpCUpASlIGAAPZUsYqC3Y6FCrVnXm6lR4tmVKUrYjFQf2en8N6g+Nb/wDWrq8Kg/s9P4b1B8a3/wCtXU1Hm9P6MPgXcj1E/pWVYo9RP6VlUJkUpSgFKUoBWk/HbkJ5VjIrVpQHWlttsLZaFrPV2rtzLrMsky4PX+RIv8poR7LH8khKmWlJQnkYT5MkJOcZwOuSefWe82rUFriXqyXKLcIE5lEiNKiupdaeaUMpWhaSQpJBBBBwaXmz2vUFqmWS9W+POgXBhyLKjSGw4080tJStC0nopJBIIPiDXXmtNZ6h221DofTOmdqrvfrTfribXKlWsx2o1jjIjuLS4tK1pwkeTSAAAnlCgDz8iF51B2efCpV7N3+Q9/8Aj/Un1iqqZmQ3IRzIORUs9m7/ACHv/wAf6k+sVWAVXXV25m5l4avLe121zLU/Wc9vmddV3o9njnxkPnqM4PdR4kkdDkBTczcy8NXlva7a5lqfrOe3zOuq70ezxz4yHz1GcHuo8SSOhyArkG2e2dn21s7kSI87Puk9zzm63WT3pE6QepWsnJxknCc4APtJJMEpOo9yH5fwu/senRowtIK4uFi39sevlLx6Lm9BtntnZ9tbO5EiPOz7pPc85ut1k96ROkHqVrJycZJwnOAD7SSTzGlKljFQW7HQoVq0683UqPFsUpStiMUpSgFSB2Wf2YH/AIwvn1FV/Uddl3KajcMKg6ceW1pe2k/+YyOn/wAVDcXFK0purXkoxWGb0zeC/wBvAyk5PBFi1t1wuDodFutwC5Sx1P8AS0n7x/alwuDodFutwC5Sx1P9LSfvH9q17fb2oDRSklbizzOOK9Zavea5W+vrnbtzPZWypuEIPCtWXL1p03xqPmlpTXnglPGKpLfnrwXy+3uLfb2oDRSklbizzOOK9Zavea+qlK6WxsbbZltC0tIKFOKwSX7m3q28283mQyk5velqKUpVs1FKUoBUgdln9mB/4wvn1FV/Ugdln9mB/wCML59RQFf11duZuZeGry3tdtcy1P1nPb5nXVd6PZ458ZD56jOD3UeJJHQ5AU3M3MvDV5b2u2uZan6znt8zrqu9Hs8c+Mh89RnB7qPEkjocgK5BtntnZ9tbO5EiPOz7pPc85ut1k96ROkHqVrJycZJwnOAD7SSTBKTqPch+X8Lv7Hp0aMLSCuLhYt/bHr5S8ei5vQbZ7Z2fbWzuRIjzs+6T3PObrdZPekTpB6laycnGScJzgA+0kk8xpSpYxUFux0KFatOvN1KjxbFKUrYjFKUoBUH9np/DeoPjW/8A1q6vCoP7PT+G9QfGt/8ArV1NR5vT+jD4F3I9RP6VlWKPUT+lZVCZFKUoBSlKAUpSgFaUhhMhsoV4GtWlAcEs1l17Y9e6hu131jDuGlrhGht2ezt2zyT1udR5Ty6lP858qHMoPVIxjAwB1kHgs3F1BG2ZuW2+2cNM3Vt81rqOUiQ4nMW2Q1TVJ87dV4EZB5U9cke3oFXlMhxZ8Z2JMYQ8y8hTbja05StJGCCPaCDioqunZwbVWSNGtOjr1ru3woiChtqLqR+OgAqKiSlrlBJKj1Iz7PACsShKqt2Lw7li2q0qM3UqR3sNFwx79u3HTQqvbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kknmNQf6PTTf5w3G+bpv+dPR6ab/OG43zdN/wA6ljbqC3YtYEVavOvN1KjxbLwpUH+j003+cNxvm6b/AJ09Hppv84bjfN03/OtvpeSIsS8KVB/o9NN/nDcb5um/509Hppv84bjfN03/ADp9LyQxLwpUH+j003+cNxvm6b/nT0emm/zhuN83Tf8AOn0vJDEvCod7OhqdF4aIaVNqSmRqi+y45Hiseerbz/6KaUK+H0emm/zhuN83Tf8AOuGz+BnVtl1Zp/RlvveuJO3jFvluPyV66mMLhSfKIUhDUZpKW++VuKJ8VErUpSSkBfF/zz+JXX8w2T/xFtcqjGcoucsHJ7sXvYJYrNyUc8ckmWbW4jb1PqOOJ6D6dExtsiRbFtlw8y31q7yz/cHrW91BbHZ96ZfbDiNYbjYP/wB3zf8AOtT0emm/zhuN83Tf869b+N/x7/rmzaezVXdVQWG9JRT/AMQjFa54vGTbblJvMjrVvrTc8MMS8KVB/o9NN/nDcb5um/509Hppv84bjfN03/Ove+l5IixLwpUH+j003+cNxvm6b/nT0emm/wA4bjfN03/On0vJDEvClQf6PTTf5w3G+bpv+dPR6ab/ADhuN83Tf86fS8kMS8K89OAbcHUcDh1b2y23gedawvGqL5ID7qD5ta4hlFJlOnGD1BCU9ckeB6JUhcFG1t31HddFWvdnWki/2Zll6429jXEpcmGh7m8kpxvnJRzcpIyPd7xn6rJ2dVjtVriWiRrvcOWYjfkg8nULkUqGSeqWAhJ6k4Ksqx0yQBUdShKSwjJItWtalRk6lWO81ouGPfsunHTQtDbPbOz7a2dyJEedn3Se55zdbrJ70idIPUrWTk4yThOcAH2kknmNQf6PTTf5w3G+bpv+dPR6ab/OG43zdN/zraNuoLdi1gRVq8683UqPFsvClQf6PTTf5w3G+bpv+dPR6ab/ADhuN83Tf862+l5IixLwpUH+j003+cNxvm6b/nT0emm/zhuN83Tf86fS8kMS8KVB/o9NN/nDcb5um/509Hppv84bjfN03/On0vJDEvCoP7PT+G9QfGt/+tXT0emm/wA4bjfN03/Ou6uHrh6gbHwFWKxLuDkNyY9OWqdJVIeU86eZxRcV3lZVlRKiTknrW0YqCbbWgxxKER6if0rKsUDCQD7qyqubClKUApSlAKUpQClKUAr8KUnqUg1+0oDHkR90U5EfdFZUoDHkR90U5EfdFZUoDHkR90U5EfdFZUoDHkR90U5EfdFZUoDHkR90VpPxGH08q0D/ANq16UB1nbrVb9l4WstXau3Kuk2yTLg9f35F/ktCPZY/kkBTLSkoTyMJ8mSEnOM4HXJPPrPdbPqC1xL1ZLhEuECcyiRGlRXUutPNKGUrQtJIUkgggg4Nft5s9r1BaplkvVvjzoFwYciyo0hsONPNLSUrQtJ6KSQSCD4g115rTWeodttQ6H0zpnaq7360364m1ypVrMdqNY4yI7i0uLStacJHk0gAAJ5QoA8/Ihe2oOzuRH3RTkR90VgxIbkJ5kHIrVrUGPIj7opyI+6KypQGPIj7orgO5G4mo9Eal0VZLJtde9TQ9T3VcC43GA4wlq0NBhxwPOhxaSRlA9mMBQBKyhC9+1vH1BftG6hs+gdURLNqJ2G/Eg3FxgSkwJam8trW1zDmKeZKuUn2g4I6HLT7V5TY4Nr1LdG7pc48ZpqbOai+bIkvBIC3UtBSg2FEE8oJAzisoBnT9jTd5uorXaYUe5XNDLc6Y0wlL0lLQUGg4sDKwkLUBknAJAre22EJSOZIJ/SsYsVEVHKmtejYMeRH3RTkR90VlSsAx5EfdFORH3RWVKAx5EfdFORH3RWVKAx5EfdFORH3RWVKAx5EfdFAhI8EisqUApSlAKUpQClKUApSlAKUpQClKUApSlAKUpQClKUApSlAKUpQCtKQwmQ2UK8DWrSgOC2Wy6+sevtQ3a76xh3DS1wjQ27PZ27Z5J63PI8p5dSn+c+VDnMg9UjGMDAHXmcOZHnxWpkR9t5l5AW242sKStJ8CCOhH96TIcWfHdiTGEPMvIU242tOUrSRggj2gg4rq1yyQuG3Z5dr2d2snXq36YjgW7TVoeSJEgKdHlORbyu8oc61nJJOCBk4FZ1B2zXAr1vLpiw7t2LZuZbb8u8X+1y7rHlNWp9cFtthbaVJXICeRJPlPfhOEhRSVthWruLctz3NKRpG0kWwG/mfBU+xflupYEMvI86HM1khwNlWDg+B6ZxXJXENXPvBIC0ApCsdQCRkZ/8AQf8AsKYA47pLbbR2gp9/n6I0/Htjmqrq5ersprJMmYtCUqcOScZCB0GAOuAMmuYttJR15Rze2sYrHm7QRnOK1qNgUpSsAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBWKkhSSk+2sqUB8zUJtsqPjzVqtsNtZ5BjNalKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgFKUoBSlKAUpSgP//Z)<jupyter_code>class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        
        m = len(matrix)
        n = len(matrix[0])
        
        res = []
        even_odd = 0
        for j in range(n):
            i = 0
            
            tmp = []
            while i < m and j >= 0:
                tmp.append(matrix[i][j])                
                i += 1
                j -= 1
                
            if even_odd % 2:
                res.extend(tmp)
                
            else:
                res.extend(tmp[::-1])
                
            even_odd += 1
            
        for i in range(1, m):
            j = n - 1
            
            tmp = []
            while i < m and j >= 0:
                tmp.append(matrix[i][j])
                i += 1
                j -= 1
                
            if even_odd % 2:
                res.extend(tmp)
                
            else:
                res.extend(tmp[::-1])
                
            even_odd += 1
            
        return res<jupyter_output><empty_output><jupyter_text>391 Perfect Rectangle (Apple 2->4)<jupyter_code>class Solution(object):
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        if not rectangles:
            return False
        
        hs = set()
        area = 0
        for rec in rectangles:
            bottom_left = (rec[0], rec[1])
            top_right = (rec[2], rec[3])
            top_left = (rec[0], rec[3])
            bottom_right = (rec[2], rec[1])
            
            area += (rec[2] - rec[0]) * (rec[3] - rec[1])
            for i in [top_left, top_right, bottom_left, bottom_right]:
                if i not in hs:
                    hs.add(i)
                else:
                    hs.remove(i)
                    
        if len(hs) != 4:
            return False
        
        hs = sorted(hs)
        first = hs.pop(0)
        last = hs.pop()
        return area == (last[0] - first[0]) * (last[1] - first[1])<jupyter_output><empty_output><jupyter_text>Find artifacts （IMC Codility)<jupyter_code>from collections import Counter
def solution(N, artifacts, searched):
    # write your code in Python
    if not isinstance(N, int) or not isinstance(artifacts, str) or not isinstance(searched, str):
        raise Exception('Invalid inputs')
    
    matrix = [['.' for row in range(N)] for col in range(N)]
    count = Counter()
    artifacts = artifacts.split(',')
    
    for index, pair in enumerate(artifacts):
        top_left, right_down = pair.split()
        piece_num = chr(index + 1)
        
        top_left_x, top_left_y = convert_num(top_left[:-1]), convert_alpha(top_left[-1])
        right_down_x, right_down_y = convert_num(right_down[:-1]), convert_alpha(right_down[-1])
        
        for x in range(top_left_x, right_down_x+1):
            for y in range(top_left_y, right_down_y+1):
                matrix[x][y] = piece_num
        
        count[piece_num] = (right_down_y - top_left_y + 1) * (right_down_x - top_left_x + 1)

    visited = set()
    res = [0, 0]
    for pair in searched.split():
        x = convert_num(pair[:-1])
        y = convert_alpha(pair[-1])
        
        if matrix[x][y] == '.':
            matrix[x][y] == 'O'
            
        else:
            piece_num = matrix[x][y]
            matrix[x][y] = 'X'
            count[piece_num] -= 1
            if count[piece_num] != 0:
                visited.add(piece_num)
            else:
                res[0] += 1
                visited.discard(piece_num)
    
    res[1] = len(visited)
    return res

def convert_alpha(alpha):
    return ord(alpha) - 65
    
def convert_num(num):
    return int(num) - 1
a = 'a'
b = "a"
a == b<jupyter_output><empty_output><jupyter_text>Robinhood<jupyter_code>logs = [["58523", "user_1", "resource_1"],
["62314", "user_2", "resource_2"],
["54001", "user_1", "resource_3"],
["200", "user_6", "resource_5"],
["215", "user_6", "resource_4"],
["54060", "user_2", "resource_3"],
["53760", "user_3", "resource_3"],
["58522", "user_22", "resource_1"],
["53651", "user_5", "resource_3"],
["2", "user_6", "resource_1"],
["100", "user_6", "resource_6"],
["400", "user_7", "resource_2"],
["100", "user_8", "resource_6"],
["54359", "user_1", "resource_3"],
]
def build_transition_graph(logs):

    user_dict = {}
    res_dict = {}
    # Sort the logs by usr and then by ts. use int() since it is string and sorting wont work well with string
    logs.sort(key=lambda x: (x[1], int(x[0])))

    # Fill in the user dict, adding start and end for transitions
    for ts, usr, res in logs:
        if usr not in user_dict:
            user_dict[usr] = ['START']
        user_dict[usr].append(res)

    for usr in user_dict:
        user_dict[usr].append('END')

    # Iterate through the user dict and set counts per transition, keeping track of total users per resource
    for usr in user_dict:
        for i in range(1, len(user_dict[usr])):
            prev_res, cur_res = user_dict[usr][i-1], user_dict[usr][i]
            if prev_res not in res_dict:
                res_dict[prev_res] = {'total': 0}
            if cur_res not in res_dict[prev_res]:
                res_dict[prev_res][cur_res] = 0

            res_dict[prev_res][cur_res] += 1
            res_dict[prev_res]['total'] += 1
    
    for pair in res_dict.items():
        print(pair)

    # Fill the transition graph with resources and their probabilities
    transition_graph = {}
    for res in res_dict:
        transition_graph[res] = {}
        for nex_res in res_dict[res]:
            if nex_res == 'total':
                continue
            prob = res_dict[res][nex_res]/res_dict[res]['total']
            transition_graph[res][nex_res] = prob
    return transition_graph

build_transition_graph(logs)
from collections import defaultdict, Counter
all_courses = [
    ["Logic", "COBOL"],
    ["Data Structures", "Algorithms"],
    ["Creative Writing", "Data Structures"],
    ["Algorithms", "COBOL"],
    ["Intro to Computer Science", "Data Structures"],
    ["Logic", "Compilers"],
    ["Data Structures", "Logic"],
    ["Graphics", "Networking"],
    ["Networking", "Algorithms"],
    ["Creative Writing", "System Administration"],
    ["Databases", "System Administration"],
    ["Creative Writing", "Databases"],
    ["Intro to Computer Science", "Graphics"]
]

def findMidInPath(graph, cur, nodes, midNode):
    new = nodes + [cur]
    if cur not in graph or len(graph[cur]) == 0:
        print(new)
        mid = new[(len(new)-1)//2]
        midNode.add(mid)
        return

    for n in graph[cur]:
        findMidInPath(graph, n, new, midNode)

def findMidClasses(all_courses):
    # build the graph
    graph = defaultdict(list)
    indegree = Counter()
    all = set()
    for c in all_courses:
        graph[c[0]].append(c[1])
        all.add(c[0])
        all.add(c[1])
        indegree[c[1]] += 1

    for key in indegree:
        all.remove(key)

    # print(graph)
    # print(indegree)
    print(all)

    midNode = set()
    for root in all:
        nodes = []
        findMidInPath(graph, root, nodes, midNode)

    return midNode

findMidClasses(all_courses)
class Question:
    """
    /*
    Our goal is to build a simplified version of a real Robinhood system that reads a customer's trades from a stream, maintains what they own, and rectifies running out of cash (through a process called a "margin call", which we'll define later). We’re looking for clean code, good naming, testing, etc. We're not particularly looking for the most performant solution.

    **Step 1 (tests 1-4): Parse trades and build a customer portfolio**

    Your input will be a list of trades, each of which is itself a list of strings in the form [timestamp, symbol, B/S (for buy/sell), quantity, price], e.g.

    [["1", "AAPL", "B", "10", "10"], ["3", "GOOG", "B", "20", "5"], ["10", "AAPL", "S", "5", "15"]]

    is equivalent to buying 10 shares (i.e. units) of AAPL for 5 each at timestamp 3, and selling 5 shares of AAPL for $15 at timestamp 10.

    **Input assumptions:**

    - The input is sorted by timestamp
    - All numerical values are nonnegative integers
    - Trades will always be valid (i.e. a customer will never sell more of a stock than they own).

    From the provided list of trades, our goal is to maintain the customer's resulting portfolio (meaning everything they own), **assuming they begin with $1000**. For instance, in the above example, the customer would end up with $875, 5 shares of AAPL, and 20 shares of GOOG. You should return a list representing this portfolio, formatting each individual position as a list of strings in the form [symbol, quantity], using 'CASH' as the symbol for cash and sorting the remaining stocks alphabetically based on symbol. For instance, the above portfolio would be represented as

    [["CASH", "875"], ["AAPL", "5"], ["GOOG", "20"]]

    **Step 2 (tests 5-7): Margin calls**

    If the customer ever ends up with a negative amount of cash **after a buy**, they then enter a process known as a **margin call** to correct the situation. In this process, we forcefully sell stocks in the customer's portfolio (sometimes including the shares we just bought) until their cash becomes non-negative again.

    We sell shares from the most expensive to least expensive shares (based on each symbol's most-recently-traded price) with ties broken by preferring the alphabetically earliest symbol. Assume we're able to sell any number of shares in a symbol at that symbol's most-recently-traded price.

    For example, for this input:

`
    [["1", "AAPL", "B", "10", "100"],
    ["2", "AAPL", "S", "2", "80"],
    ["3", "GOOG", "B", "15", "20"]]

`

    The customer would be left with 8 AAPL shares, 15 GOOG shares, and 80 a share) to cover the deficit. Afterwards, they would have 6 shares of AAPL, 15 shares of GOOG, and a cash balance of $20.

    The expected output would be

    [["CASH", "20"], ["AAPL", "6"], ["GOOG", "15"]]

    **Step 3/Extension 1 (tests 8-10): Collateral**

    Certain stocks have special classifications, and require the customer to also own another "collateral" stock, meaning it cannot be sold during the margin call process. Our goal is to handle a simplified version of this phenomenon.

    Formally, we'll consider stocks with symbols ending in "O" to be special, with the remainder of the symbol identifying its collateral stock. For example, AAPLO is special, and its collateral stock is AAPL. **At all times**, the customer must hold at least as many shares of the collateral stock as they do the special stock; e.g. they must own at least as many shares of AAPL as they do of AAPLO.

    As a result, the margin call process will now sell the most valuable **non-collateral** share until the balance is positive again. Note that if this sells a special stock, some of the collateral stock may be freed up to be sold.

    For example, if the customer purchases 5 shares of AAPL for 75 each, then finally 5 shares of AAPLO for 125, but their shares of AAPL can no longer be used to cover the deficit (since they've become collateral for AAPLO). As a result, 2 shares of GOOG would be sold back (again at 25, 5 AAPL, 5 AAPLO, and 3 GOOG. Thus, with an input of

    [["1", "AAPL", "B", "5", "100"], ["2", "GOOG", "B", "5", "75"], ["3", "AAPLO", "B", "5", "50"]]

    the corresponding output would be

    [["CASH", "25"], ["AAPL", "5"], ["AAPLO", "5"], ["GOOG", "3"]
    */

    """
from typing import *
from collections import Counter
import heapq

class Main:
    def __init__(self):
        self.balance = Counter()
        self.priceMap = dict()
        
    def getPortfolio(self, records: List[List[str]]) -> List[List[str]]:
        self.balance["CASH"] = 1000
        for record in records:
            self.trade(record)

        return self.generateOutput()

    def trade(self, record): 
        stock = record[1]
        action = record[2]
        quantity = int(record[3])
        price = int(record[4])
        total = quantity * price

        if action == "B":
            self.balance[stock] += quantity
            self.balance["CASH"] -= total

        elif action == "S":
            self.balance[stock] -= quantity
            self.balance["CASH"] += total 

        self.priceMap[stock] = price
        if self.balance[stock] == 0:
            self.priceMap.pop(stock)
            
    def generateOutput(self):
        res = []
        for key in self.balance:
            if key != "CASH" and self.balance[key] != 0:
                res.append([key, str(self.balance[key])])

        res.sort()

        res.insert(0, ["CASH", str(self.balance["CASH"])])
                                   
        return res

    def getPortFolioWithMarginCall(self, records):
        self.balance["CASH"] = 1000
        for record in records:
            self.trade(record)

            if self.balance["CASH"] < 0:
                self.marginCall()

        return self.generateOutput()

    def marginCall(self):
        cash = self.balance["CASH"]
        heap = []
        for stock, price in self.priceMap.items():
            heapq.heappush(heap, (-price, stock))

        while cash < 0:
            nprice, stock = heapq.heappop(heap)
            price = -nprice
            quantity = self.balance[stock]

            while quantity > 0 and cash < 0:
                cash += price
                quantity -= 1

            self.balance[stock] = quantity

            if quantity == 0:
                self.priceMap.pop(stock)

        self.balance["CASH"] = cash

        
m = Main()
records = [["1", "AAPL", "B", "10", "10"], ["3", "GOOG", "B", "20", "5"], ["10", "AAPL", "S", "5", "15"]]
records2 = [["1", "AAPL", "B", "10", "100"], ["2", "AAPL", "S", "2", "80"], ["3", "GOOG", "B", "15", "20"]]

m.getPortFolioWithMarginCall(records2)
# symbol, side, quantity, id
from collections import defaultdict
class Util:
    def getUnMatches(self, house, street):
        houseMap = self.getMap(house)
        streetMap = self.getMap(street)

        print(houseMap)
        print(streetMap)

        self.removeMatches(houseMap, streetMap, "exact")
        
        unmatched = []
        for value in houseMap.values():
            unmatched.extend(value)

        for value in streetMap.values():
            unmatched.extend(value)

        return unmatched

    def getMap(self, array):
        map = defaultdict(list)
        for trade in array:
            items = trade.split(',')
            symbol = items[0]
            quantity = items[2]
            key = symbol + " " + quantity
            map[key].append(trade)

        return map

    def removeMatches(self, houseMap, streetMap, typing):
        # houseMapKeys = list(houseMap.keys()) #["symbol, side, quantity, id"]
        # houseMapKeys.sort()

        for key in sorted(houseMap.keys()):
            if key in streetMap:
                hRemove = []
                sRemove = []

                hTrades = houseMap[key]
                sTrades = streetMap[key]

                hTrades.sort()
                sTrades.sort()

                for i in range(len(hTrades)):
                    hTrade = hTrades[i]
                    for j in range(len(sTrades)):
                        if j in sRemove:
                            continue

                        sTrade = sTrades[j]
                        if typing == "exact":
                            if hTrade == sTrade:
                                hRemove.append(i)
                                sRemove.append(j)
                                break

                houseMap[key] = self.getRemainList(hTrades, hRemove)
                streetMap[key] = self.getRemainList(sTrades, sRemove)

    def remove(self, house, street):
        house_remove = []
        street_remove = []

        house.sort()
        street.sort()

        i = 0
        j = 0
        while i < len(house) and j < len(street):
            if house[i] == street[j]:
                house_remove.append(i)
                street_remove.append(j)

                i += 1
                j += 1

            elif house[i] < street[j]:
                i += 1
            elif house[i] > street[j]:
                j += 1

        return [self.getRemainList(house, house_remove), self.getRemainList(street, street_remove)]


    def getRemainList(self, original, remove):
        remain = list(original)
        for i in remove:
            remain.pop(i)
        return remain 

house_trades = [ "AAPL,B,0100,ABC123", "AAPL,B,0100,ABC123", "GOOG,S,0050,CDC333" ]
street_trades = [ " FB,B,0100,GBGGGG", "AAPL,B,0100,ABC123" ]

u = Util()
u.getUnMatches(house_trades, street_trades)
def removeMatches(self, houseMap, streetMap, typing):
        # houseMapKeys = list(houseMap.keys()) #["symbol, side, quantity, id"]
        # houseMapKeys.sort()

        for key in sorted(houseMap.keys()):
            if key in streetMap:
                hRemove = []
                sRemove = []

                hTrades = houseMap[key]
                sTrades = streetMap[key]

                hTrades.sort()
                sTrades.sort()

                for i in range(len(hTrades)):
                    hTrade = hTrades[i]
                    for j in range(len(sTrades)):
                        if j in sRemove:
                            continue

                        sTrade = sTrades[j]
                        if typing == "exact":
                            if hTrade == sTrade:
                                hRemove.append(i)
                                sRemove.append(j)
                                break

                houseMap[key] = self.getRemainList(hTrades, hRemove)
                streetMap[key] = self.getRemainList(sTrades, sRemove)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10667381399088716, 'fraction_numerical': 0.050352416206074745, 'mean_word_length': 1.922887994918484, 'pattern_counts': {'":': 15, '<': 399, '<?xml version=': 0, '>': 530, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 5, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '74', 'dir': 'jupyter-structured-clean-dedup', 'id': '222587', 'license': 'MIT', 'n_tokens_mistral': 57597, 'n_tokens_neox': 53198, 'n_words': 10305, 'path': '1. Math & String & List & Matrix.ipynb', 'repo_name': 'zhutianwei/Essential-Python-Data-Structure', 'size': '138047'}