IQs

BFS.py

"""
Graph is represented as an adjacency list
"""
def BFS(self,root):
  visited = [False]*(len(self.nodes))
  queue = []
  queue.append(root)
  visited[root] = True
  
  while queue:
    v = queue.pop(0)
    print(v)
    for u in self.nodes[v].neighbors:
      if not visited[u]:
        queue.append(u)
        visited[u] =True
      
  

BoyerMooreMajorityVote.py

"""
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.
"""
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counter = 0
        major = nums[0]
        for k in nums:
            if counter == 0:
                major = k
                counter =1
            elif major == k:
                counter += 1
            else:
                counter -= 1
        return major

CoinChange.py

#You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount.

def change(self, amount, coins):
    """
    :type amount: int
    :type coins: List[int]
    :rtype: int
    """
    NWays = [ 0 for k in range(amount+1) ]
    NWays[0] =1
    for i in range(1,amount+1):
        for c in coins:
            if i >= c:
                NWays[i] += NWays[i -c] 
    return NWays[amount]

CoinChange2.py

"""
You are given coins of different denominations and a total amount of money amount. 
Write a function to compute the fewest number of coins that you need to make up that amount. 
If that amount of money cannot be made up by any combination of the coins, return -1.
"""
def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [0]*(amount +1)
    dp[0] = 0
        
    for i in range(1,amount+1):
        dp[i] = min([ dp[i-c] for c in coins if i >= c  ], default = float('inf')) + 1
    return -1 if dp[amount] == float('inf') else dp[amount]

EditDistance.py

    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        
        ed = [  [0 for _ in range(n2+1)] for __ in range(n1+1)  ]
        
        for k1 in range(n1+1):
            for k2 in range(n2+1):
                res = 0
                if k1 == 0:
                    res = k2
                elif k2 == 0:
                    res = k1
                elif word1[k1-1] == word2[k2-1]:
                    res =  ed[k1-1][k2-1]
                else:
                    res = 1 + min(   ed[k1-1][k2], ed[k1][k2-1], ed[k1-1][k2-1])
                ed[k1][k2] = res
        return ed[n1][n2]

EratostenesSieve.py

def sieve(n):
    isPrime = [True for i in range(n+1)]
    isPrime[0:2] =[False , False]
    for i in range(int(n**0.5)+1):
        if isPrime[i]:
            for j in range(i*i , n+1, i):
                isPrime[j] = False
    return [i for i,k in enumerate(isPrime) if k]

sieve(1000)

fibonacci.py

def fib(n):
    prev, curr = 0, 1
    for i in range(n):
        prev, curr = curr, prev+ curr
    return curr

fib(900)

FizzBuzz.py

"""
Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.    
"""
def fizzBuzz(self, n: int) -> List[str]:
    divisors = {3 : "Fizz", 5 : "Buzz"}
    ans = []
        
    for i in range(1,n+1):
        num_str = "".join([ v for k,v in divisors.items() if i%k ==0 ])
        if num_str == "":
            num_str = str(i)
        ans.append(num_str)
     return ans

FloydCycle.py

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None:
            return None
        
        slow = head
        fast = head
        while True:
            if fast.next != None and fast.next.next != None:
                    fast = fast.next.next
                    slow = slow.next
                    if slow == fast:
                        break
            else:
                return None
        ptr1 = head
        ptr2 = slow
        while True:
            if ptr1 == ptr2:
                return ptr1
            ptr1 = ptr1.next
            ptr2 = ptr2.next

GenerateParanthesis.py

"""
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. 
"""
    def generateParenthesis(self, n: int) -> List[str]:
        res =[]
        def backtrack(s, l, r):
            if len(s) == 2*n:
                res.append(s)
                return
            if l < n:
                backtrack(s+"(",l+1,r)
            if r<l:
                backtrack(s+")",l,r+1)
        backtrack("",0,0)
        return res
        

jump.py

"""
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.


"""
def canJump(self, nums: List[int]) -> bool:
    n = len(nums)
    lastKnownGood = n-1
    for k in  range(n-2,-1,-1):
        if lastKnownGood - k <= nums[k]:
            lastKnownGood = k
    return lastKnownGood ==0

MaxContiguousSubarray.py

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxSum=nums[0]
        maxEndingAt =nums[0]
        for k in nums[1:]:
            maxEndingAt = max(k,maxEndingAt+k)
            maxSum = max(maxSum,maxEndingAt)
        return maxSum

ReversePolish.py

  """
  Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

    Division between two integers should truncate toward zero.
    The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
  """  
  def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        oper = {  '+' : lambda x , y: x+y
                    ,'-' : lambda x , y: x-y
                    ,'*' : lambda x , y: x*y
                    ,'/' : lambda x , y: (x//y +1) if x*y <= 0 and x%y != 0 else x//y
               }
        for t in tokens:
            if t not in oper:
                stack.append(int(t))
            else:
                r , l = stack.pop() , stack.pop()
                stack.append( oper[t](l,r)  )
        return stack.pop()