LeetCode: Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4after calling your function.

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

class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # boundary condition - avoid null nodes and tail node
        if node and node.next is not None:
            node.val = node.next.val        # overwrite the current node with the next node
            node.next = node.next.next      # link the node next to the next to next node

LeetCode: Ransom Note

Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        #/////////////////////////////////////////////////
        # Using an extra hash/dict: O(n) space, O(n) time
        #/////////////////////////////////////////////////
        magazineDict = {}
        for elem in magazine:
            if elem in magazineDict:
                magazineDict[elem] += 1
            else:
                magazineDict[elem] = 1
            
        canbeconstructed = True    
        for item in ransomNote:
            if item not in magazineDict:
                canbeconstructed = False
                break
            else:
                if magazineDict[item] == 0:
                    canbeconstructed = False
                    break
                else:
                    magazineDict[item] -= 1
            
            
        return canbeconstructed
        

LeetCode: Sum of Left Leaves
Find the sum of all left leaves in a given binary tree.

  3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. 

Return 24.

#Two key points to note here: Left branch and Leaf nodes

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.sumLeft = 0 # declare a global variable to account for the sum of left branches
        
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.findLeftSum(root)
        #print 'sum: ', self.sumLeft
        return self.sumLeft

        
    def findLeftSum(self, node, dir=None):
        #////////////////////////////////
        # do it using in-order traversal
        #////////////////////////////////
        if node is None:
            return 0

        # Only sum those node vals when the dir = 0 (signifying left branch) and
        # it has no more child nodes
        if dir == 0 and node.left is None and node.right is None:
            self.sumLeft += node.val
            
        # When left node is pushed to the stack, pass it's identifier direction as 0
        self.findLeftSum(node.left, 0)
        #print 'node val: ', node.val
        self.findLeftSum(node.right, 1)

Fibonacci series - Find the fibonacci number of a given integer 'n'

#!/usr/bin/python

import sys

#/////////////////////////////////////////////////////////////////

# Recursive version - revisits the same computation multiple times

#/////////////////////////////////////////////////////////////////

def fibRecurse(n):

    # Some boundary conditions

    if n < 0:

        print('Cannot find Fibonacci of -ve numbers. Returning -1')

        return -1

    if n == 0:

        return 0

    if n == 1 or n == 2:

        return 1

    return (fibRecurse(n - 2) + fibRecurse(n - 1))

#/////////////////////////////////////////////////////////////////

# Iterative version - optimal computation. Works on accumulation

#                     and moving forward

#/////////////////////////////////////////////////////////////////

def fibIterative(n):

    # Some boundary conditions

    if n < 0:

        print('Cannot find Fibonacci of -ve numbers. Returning -1')

        return -1

    if n == 0:

        return 0

    if n == 1 or n == 2:

        return 1

    a = 1 # (n-1)th element

    b = 1 # (n-2)th element

    for i in xrange(3, n+1):

        c = a + b

        b = a

        a = c

    return a

if __name__ == "__main__":

    if len(sys.argv) == 2:

        n = int(sys.argv[1])

    else:

        print 'Usage - requires 1 arguement (n): progName n'

        exit(0)

    result = fibRecurse(n)

    print("fibonacci -recursive of: ", n, " is: ", result)

    result = fibIterative(n)

    print("fibonacci -iterative of: ", n, " is: ", result)

LeetCode: Invert Binary Tree

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

In the above tree, the output will be a list = [4,7,2,9,6,3,1]

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        #print 'root val: ', root.val
        mirrorList = []
        if not root:
            return mirrorList
            
        # do a BFS. Use a Queue - FIFO to traverse the original list
        from collections import deque
        Q = deque()
        Q.append(root)
        mirrorList.append(root.val)
        while len(Q) != 0:
            node = Q.popleft()
            
            #//////////////////////////////////////
            # now turn the direction first
            # This is the most important step
            # to mirror the tree
            #//////////////////////////////////////
            temp = node.left
            node.left = node.right
            node.right = temp
            
            
            # then append the turned node to the mirrored List and the Q
            if node.left is not None:
                mirrorList.append(node.left.val)
                Q.append(node.left)
            else:
                mirrorList.append(None)
                
            if node.right is not None:
                mirrorList.append(node.right.val)
                Q.append(node.right)
            else:
                mirrorList.append(None)
                
        
        #Trim the null's from the end, since mirrorList can get some extra nulls at it's end
        for item in mirrorList[::-1]:
            if item == None:
                mirrorList.pop()
            else:
                break
        return mirrorList

LeetCode: Two sum: Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        arrH = {}
        for i in xrange(len(nums)):
            arrH[nums[i]] = i
            
        for j in xrange(len(nums)):
            diff = target - nums[j]
            print 'diff: ', diff
            if diff in arrH and j != arrH[diff]:
                print j, arrH[diff]
                return [j, arrH[diff]]

LeetCode: Find the maximum depth of a Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        '''
        #///////////////////////////
        # recursive implementation
        # Complexity: O(n) - since it has to visit all the nodes
        #///////////////////////////
        if not root:
            return 0
            
        leftHeight = self.maxDepth(root.left)
        rightHeight = self.maxDepth(root.right)
        
        if leftHeight > rightHeight:
            return leftHeight + 1
        else:
            return rightHeight + 1