Part B References

• Part B theory slides by Luca Bianco

• Problem Solving with Algorithms and Data Structures using Python online book by Brad Miller and David Ranum

• Theory exercises (complexity, tree visits, graph visits) - by Alberto Montresor

LeetCode for Part B

In general: https://leetcode.com/problemset/all/ (sort by easy difficulty)

LeetCode LinkedLists

• Merge Two Sorted Lists

• Remove Duplicates from Sorted List

• Intersection of Two Linked Lists

• Linked List Cycle NOTE: a solution which occupies \(O(n)\) memory is easy - the follow up question requires \(O(1)\) memory, for that you will probably need to look at the solution

• Palindrome Linked List

• Merge In Between Linked Lists

• Odd Even Linked List

• Split Linked List in Parts

• Partition List

• Reverse Linked List II

• Remove Duplicates from Sorted List II

• Copy List with Random Pointer

LeetCode Queues

• Number of Recent Calls notice you only need to return number of calls occurred during last 3000 ms, so please try avoiding storing all previous calls history

• Design Front Middle Back Queue

LeetCode Trees

NOTE 1: on LeetCode root usually can also be None

NOTE 2: on LeetCode self is reserved for the test runner, ignore it

NOTE 3: if you try the algorithms on your computer, you will want to add these __str__ and __repr__ methods to TreeNode:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __str__(self):

        """ Returns a pretty string of the tree """
        def str_branches(node, branches):
            """ Returns a string with the tree pretty printed.

                branches: a list of characters representing the parent branches. Characters can be either ` ` or '│'
            """
            strings = [str(node.val)]

            i = 0
            if node.left != None or node.right != None:
                for current in [node.left, node.right]:
                    if i == 0:
                        joint = '├'
                    else:
                        joint = '└'

                    strings.append('\n')
                    for b in branches:
                        strings.append(b)
                    strings.append(joint)
                    if i == 0:
                        branches.append('│')
                    else:
                        branches.append(' ')

                    if current != None:
                        strings.append(str_branches(current, branches))
                    branches.pop()
                    i += 1
            return "".join(strings)

        return str_branches(self, [])

    def __repr__(self):
        return self.__str__()

NOTE 4: testcases are expressed as a list, which doesn’t tell much how the tree is structured. To see a visualization of the tree, when you get an error you can copy paste the ‘Input’ testcase into this tab and turn on the Tree Visualizer selector:

Trees exercises on LeetCode (sort by easy difficulty), for example:

• Merge Two Binary Trees

• Sum range of BST

• Invert Binary Tree

• Minimum Depth of Binary Tree

• Symmetric Tree

• Minimum Depth of Binary Tree HINT: when you need to calculate a min of two numbers but one of them may be undefined, you can initialize them to math.inf

• Increasing Order Search Tree

• Binary Tree Level Order Traversal HINT: use a queue, for more info see here

• Average of Levels in Binary Tree HINT: use a queue, for more info see here

• Cousins in Binary Tree NOTE: nodes have all distinct values, a queue visit might help

• Find Mode in Binary Search Tree - you don’t need to bother about the follow up question

• Path Sum DO NOT store in memory all possible paths to then calculate the sum of each, that would be a waste of space.

• Second Minimum Node In a Binary Tree

• Lowest Common Ancestor of a Binary Search Tree

• Balanced Binary Tree

• Binary Tree Tilt

LeetCode Graphs

• Keys and rooms

Geeks for geeks

NOTE: required outputs are a bit strange, often times they ask you to print stuff while in fact you just need to return some data.

Geeks for geeks Queues

• Interleave the first half of the queue with second half to implement it, use Queue object from python module queue

• Sorting a Queue without extra space remember to use only the allowed operations !

Geeks for geeks Graphs

NOTE: if they require you to produce stuff like matrices they are shown as a line of numbers but you have to return the actual Python matrix

DO NOT print anything

• Distance of nearest cell having 1 in a binary matrix - HINT: basically it’s a BFS on a matrix

• Rotten Oranges - HINT: basically it’s a BFS on a matrix