Python Fundamentals and Preparation

A repository curated for learning the fundamentals of Python, as well as all of the solutions to every Python interview question I have done so far.

Algorithms and Data Structures for Beginners

Arrays

RAM

Ram is measured in bytes. Byte is 8 bits. A bit is the position that can store a digit, the restriction is that it can be a zero or a one. RAM stores the values, but every value is stored at a distint location called an address. Arrays are going to be contiguous, meaning that the values stored in RAM are going to be next to eachother. THe address will increment by 4 because intergers are 4 bytes. However, if we store ASCII values, they will increment by 1, because it is 1 byte. Increment the address by the size of the value.

Static Arrays

Static arrays are fixed size arrays. Python doesnt offer static, it has dynamic arrays as default. Inserting at the end is efficient, but adding at the front or the middle, is not efficient at all. We must shift all of the values to the right. If we add a the front, this is a O(n) time complexity because we are shifting all of the elements to the right.

Operation	Time Complexity
r/w i-th element	O(1)
Insert/Remove end	O(1)
Insert middle	O(n)
Remove middle	O(n)

Dynamic Arrays

Dynamic arrays resize themselves when more space is requested, for example if we wish to add to the end middle or beginning of the array, but we do not have enough space in the current array.

Operation	Time Complexity
r/w i-th element	O(1)
Insert/Remove end	O(1)
Insert middle	O(n)
Remove middle	O(n)

Stacks

The stack is nothing but an array. LIFO - last in, first out data structure.

Operation	Time Complexity
Push	O(1)
Pop	O(1)
Peek/Top	O(1)

Linked Lists

Singly Linked Lists

A linked list is made up of a chain of nodes. These nodes contain a value and pointer to the next node. A chain of nodes is called a singly linked list becaue every next pointer points to the address of the next node.

Operation	Time Complexity
r/w i-th element	O(n)
Insert/Remove end	O(1)
Insert/Remove middle	O(n)/O(1)

Doubly Linked Lists

Exact same as singly linked lists but, now a node also stores a refrence to the previous node aswell as the next node.

Operation	Time Complexity
r/w i-th element	O(n)
Insert/Remove end	O(1)
Insert/Remove middle	O(n)/O(1)

Queues

Queues are similar to stacks. FIFO - first in, first out data structure. Supports two operations, enqueue and dequeue. Elements are added from the end and removed from the front.

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)

Recursion

Factorial

A factorial, would be a good introduction to recursion. This is called a one-branch recursion. To notice a recursion problem, we have to find if there are sub-problems. The equation for a factorial is as follows: n! = n * (n - 1)!.
There is no benefit to using recursion for a factorial problem. However it gives you a good visualization of how recursion works. Here is the code solution for a factorial and the decision tree:

def factorial(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return 1

    # Recursive case: n! = n * (n - 1)!
    return n * factorial(n - 1)
    
5!	
  \		24	->	120	
   4!		|-
     \		6
      3!	|-
        \	2
	 2!	|-
	   \	1
	    1!

Recursion is not recommended because we are using O(n) memory, and we can do this in constant memory using a while loop like so:

int res = 1

while n < 1:
    res = res * n
    n -= 1
	
return res

Fibonacci

This is an example of two-branch recursion. Here is the implementation:

def fibonacci(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return n

    # Recursive case: fib(n) = fib(n - 1) + fib(n - 1)
    return fibonacci(n - 1) + fibonacci(n - 2)

Sorting

Insertion Sort

def insertionSort(arr):
	# Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        j = i - 1
        while j >= 0 and arr[j + 1] < arr[j]:
            # arr[j] and arr[j + 1] are out of order so swap them 
            tmp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = tmp
            j -= 1
    return arr

Merge Sort

def mergeSort(arr, s, e):
    if e - s + 1 <= 1:
        return arr

    # The middle index of the array
    m = (s + e) // 2

    # Sort the left half
    mergeSort(arr, s, m)

    # Sort the right half
    mergeSort(arr, m + 1, e)

    # Merge sorted halfs
    merge(arr, s, m, e)
    
    return arr

# Merge in-place
def merge(arr, s, m, e):
    # Copy the sorted left & right halfs to temp arrays
    L = arr[s: m + 1]
    R = arr[m + 1: e + 1]

    i = 0 # index for L
    j = 0 # index for R
    k = s # index for arr

    # Merge the two sorted halfs into the original array
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # One of the halfs will have elements remaining
    while i < len(L):
        arr[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        arr[k] = R[j]
        j += 1
        k += 1

Quick Sort

def quickSort(arr, s, e):
    if e - s + 1 <= 1:
        return

    pivot = arr[e]
    left = s # pointer for left side

    # Partition: elements smaller than pivot on left side
    for i in range(s, e):
        if arr[i] < pivot:
            tmp = arr[left]
            arr[left] = arr[i]
            arr[i] = tmp
            left += 1

    # Move pivot in-between left & right sides
    arr[e] = arr[left]
    arr[left] = pivot
    
    # Quick sort left side
    quickSort(arr, s, left - 1)

    # Quick sort right side
    quickSort(arr, left + 1, e)

    return arr

Bucket Sort

def bucketSort(arr):
    # Assuming arr only contains 0, 1 or 2
    counts = [0, 0, 0]

    # Count the quantity of each val in arr
    for n in arr:
        counts[n] += 1
    
    # Fill each bucket in the original array
    i = 0
    for n in range(len(counts)):
        for j in range(counts[n]):
            arr[i] = n
            i += 1
    return arr

Binary Search

Search Array

arr = [1, 3, 3, 4, 5, 6, 7, 8]

def binarySearch(arr, target):
    L, R = 0, len(arr) - 1

    while L <= R:
        M = (L + R) // 2

        if target > arr[M]:
            L = M + 1
        elif target < arr[M]:
            R = M - 1
        else:
            return M
    return -1

Search Range

# low = 1, high = 100

# Binary search on some range of values
def binarySearch(low, high):

    while low <= high:
        mid = (low + high) // 2

        if isCorrect(mid) > 0:
            high = mid - 1
        elif isCorrect(mid) < 0:
            low = mid + 1
        else:
            return mid
    return -1

# Return 1 if n is too big, -1 if too small, 0 if correct
def isCorrect(n):
    if n > 10:
        return 1
    elif n < 10:
        return -1
    else:
        return 0

Advanced Algorithms

Advanced Arrays

Kadane's Algorithm

...

Python Basics

Variables

Dynamically Typed

Python variables are dynamically typed. This means that the interpreter assigns variables a type at runtime based on the variable's value at the time. None is equivalent to null, there is no value when a variable is set to None.

n = 0
print('n =', n)
>>> n = 0

n = "abc"
print('n =', n)
>>> n = abc

n = 4
n = None
print("n =", n)
>>> n = None

Multiple Assignments

Use this shorthand notation to assign multiple variables, it makes the look code cleaner.

n, m = 0, "abc"
n, m, z = 0.125, "abc", False

Incrementing

There is no ++ incrementing in Python!

n = n + 1 # good
n += 1    # good
n++       # bad

If you wish to know more about Pythons built-in types, visit the documentation page here

Math

Division

Division is python is decimal by default. Notice that we can use a double slash to round down. Division with negative numbers will result in rounding down, whereas in most languages it will be rounded closer to zero. If you want to round closer to zero, use decimal division and then convert the value to an integer

print(5 / 2)
>>> 2.5

print(5 // 2)
>>> 2

# Careful here with negative division
print(-3 // 2)
>>> -2

# Workaround to round closer to zero
print(int(-3 / 2))
>>> -1

Modulo

Modding is similar to most languages, expect when we are modding negative values. To be consistent with other languages modulo, use a module.

print(10 % 3)
>>> 1

print(-10 % 3)
>>> 2

# To be consistent with other languages modulo
import math
from multiprocessing import heap
print(math.fmod(-10, 3))
>>> -1

More Math

Useful Functions

print(math.floor(3 / 2))
>>> 1

print(math.ceil(3 / 2))
>>> 2

print(math.sqrt(2))
>>> 1.4142135623730951

print(math.pow(2, 3))
>>> 8

+/- Infinity

First two functions create max/min integers. Python numbers are infinite, so they never overflow. However, they will always be less that infinity!

float("inf")
float("-inf")

print(math.pow(2, 200))
>>> 1.6069380442589903e+60

print(math.pow(2, 200) < float("inf"))
>>> True

If Statements

If-statements do not need parentheses or curly braces.

n = 1
if n > 2:
    n -= 1
elif n == 2:
    n *= 2
else:
    n += 2

Parentheses are only needed for multi-line conditions.

n, m = 1, 2
if ((n > 2 and 
    n != m) or n == m):
    n += 1

Loops

Remember that loops are inclusive, if you range(5) it will print from 0 to 5.

While Loops

n = 0
while n < 5:
    print(n)
    n += 1
>>> 0 1 2 3 4

For Loop

Looping from `i = 0` to `i = 4`

for i in range(5):
    print(i)
>>> 0 1 2 3 4

Looping from `i = 2` to `i = 5`

for i in range(2, 6):
    print(i)
>>> 2 3 4 5

Looping from `i = 5` to `i = 2`

for i in range(5, 1, -1):
    print(i)
>>> 5 4 3 2

If you wish you wish to know more about Pythons control flow, visit the documentation page here

Elements of Programming Interviews in Python

Arrays

Array problems often have simple brute force solutions that use O(n) space, but there are subtler solutions that use the array itself to reduce space complexity to O(1). Filling an array from the front is slow, so see if it's possible to write values from the back. Instead of deleting an entry (which requires moving all entries to its left), consider overwriting it. When dealing with integers encoded by an array consider processing the digits from the backof the array. Alternately, reverse the array so the least-significant digit is the first entry. Be comfortable with writing code that operates on subarrays It's incredibly easy to make off-by-l errors when operating on arrays-reading past the last element of an array is a comrnon error which has catastrophic consequences. Don't worry about preserving the integrity of the array (sortedness, keeping equal entries together, etc.) until it is time to return. An array can serve as a good data structure when you know the distribution of the elements inadvance. For example, a Boolean array of length W is a good choice for representing a subset of {0, 1, ..., W - 1}. (When using a Boolean array to represent a subset of {1,2,3, ...,n|, allocate an array of size n+1 to simplify indexing). When operating on 2D arrays, use parallel logic for rows and for columns. Sometimes it's easier to simulate the specification, than to analytically solve for the result. For example, rather than writing a formula for the i-th entry in the spiral order for an n x n matrix, just compute the output from the beginning.

Arrays Syntax

Instantiation

list = [1, 2, 3, 4, 5]

print(list)
>>> [1, 2, 3, 4, 5]

# Initialize a list of size n with default value of 1
n = 5
list = [1] * n

print(list)
>>> [1, 1, 1, 1, 1]

print(len(list))
>>> 5

list = [i for i in range(5)]

print(list)
>>> [0, 1, 2, 3, 4]

Indexing

list[0] = 0
list[3] = 0
print(list)
>>> [0, 2, 3, 0, 5]

# Careful: -1 is not out of bounds, it's the last value
list = [1, 2, 3]

print(list[-1])
>>> 3

print(arr[-2])
>>> 2

Slicing

If we have A = [1, 6, 3, 4, 5, 2, 77], these are the following slicing operations we can perform.

A[2:4] is [3, 4]
A[2:] is [3, 4, 5, 2, 77]
A[:4] is [1, 6, 3, 4]
A[:-1] is [1, 6, 3, 4, 5, 2]
A[-3:] is [5, 2, 7]
A[-3:-1] is [5, 2]
A[1:5:2] is [6, 4]
A[5:1:-2] is [2, 4]
A[::-1] is [7, 2, 5, 4, 3, 6, 1] (reverses list)

Slicing can also be used to rotate a list A[k:l] + A[:k] rotates A by k to the left. It can also be used to create a copy: B = A[:] does a (shallow) copy of A into B.

arr = [1, 2, 3, 4]
print(arr[1:3])
>>> [2, 3]

# Similar to for-loop ranges, last index is non-inclusive, but no out of bounds error
print(arr[0:4])
>>> [1, 2, 3, 4]

print(arr[0:10])
>>> [1, 2, 3, 4]

Basic Operations

len(list)
list.append(42)
list.remove(42)
list.insert(3, 28)
list.reverse()
list.sort()
list.sort(reverse=True)

list = ["bob", "alice", "jane", "doe"]
list.sort()

print(list)
>>> ["alice", "bob", "doe", "jane"]

# Custom sort (by length of string)
list.sort(key=lambda x: len(x))

print(list)
>>> ["bob", "doe", "jane", "alice"]

Looping Through Array

nums = [1, 2, 3]

# Using index
for i in range(len(nums)):
    print(nums[i])
>>> 1 2 3

# Without index
for n in nums:
    print(n)
>>> 1 2 3

# With index and value
for i, n in enumerate(nums):
    print(i, n)
>>> 0 1
>>> 1 2
>>> 2 3

# Loop through multiple arrays simultaneously with unpacking
nums1 = [1, 3, 5]
nums2 = [2, 4, 6]
for n1, n2 in zip(nums1, nums2):
    print(n1, n2)
>>> 1 2
>>> 3 4
>>> 5 6

2-D Lists

list = [[0] * 4 for i in range(4)]

print(list)
print(arr[0][0], arr[3][3])
>>> [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

# This won't work as you expect it to
arr = [[0] * 4] * 4

Value Exists

a in list

Copying (Shallow & Deep)

listB = listA

This will make listB point to listA. They will have the same values.

Shallow Copy

A shallow copy creates a new object which stores the reference of the original elements.
So, a shallow copy doesn't create a copy of nested objects, instead it just copies the reference of nested objects. This means, a copy process does not recurse or create copies of nested objects itself.

import copy

old_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
new_list = copy.copy(old_list)

print("Old list:", old_list)
print("New list:", new_list)

Changes in the old_list, will appear in the new_list. Changes in the new_list will not appear in the old_list.

Deep Copy

A deep copy creates a new object and recursively adds the copies of nested objects present in the original elements.

import copy

old_list = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
new_list = copy.deepcopy(old_list)

print("Old list:", old_list)
print("New list:", new_list)

In the above program, we use deepcopy() function to create copy which looks similar. However, if you make changes to any nested objects in original object old_list, you’ll see no changes to the copy new_list.

Key Methods

min(A),
max(A),
binary search for sorted lists (bisect.bisect(A,6), bisect.bisect-left(A,6), and bisect.bisect_right(A,6)),
A.reverse() (in-place)
reversed(A) (returns an iterator),
A.sort() (in-place),
sorted(A) (returns a copy),
del A[i] (deletes the i-th element), `and
del A[i: j]` (removes the slice)

List Comprehension

Python provides a feature called list comprehension that is a succinct way to create lists. A list comprehension consists of:

an input sequence
an iterator over the input sequence
a logical condition over the iterator (this is optional)
an expression that yields the elements of the derived list.

[x**2 for x in range(6)] yields [0, 1, 4, 9, 16, 25]
[x**2 for x in range(6) if x%2 == 0] yields [0, 4, 16]

List comprehension supports multiple levels of looping. This can be used to create the product of sets, e.g., if A = [1, 3, 5] and B = ['d', 'b'], then [(x, y) for x in A for y in B] creates [(1, 'a'), (1, 'b'), (3, 'a'), (3, 'b'), (5, 'a'), (5, 'b')].

It can also be used to convert a 2D list to a 1D list, e.g., if M = [['a', 'b', 'c'], ['d', 'e','f']], x for row in M for x in row creates ['a', 'b', 'c', 'd', 'e', 'f '].

Two levels of looping also allow for iterating over each entry in a 2D list, e.g., lf A = [[1, 2, 3] , [4, 5, 6]] then [[x**2 for x in row] for row in M] yields [[1, 4, 9], [16, 25, 36]].

As a general rule, it is best to avoid more than two nested comprehensions, and use conventional nested for loops-the indentation makes it easier to read the program.

Arrays Problems

Problem	LeetCode	Solution	Completed	Notes	Video Walkthrough
5.1	75. Sort Colors 🟡	Code	✔️	PARTITION/PIVOT POINT ➡️ Instantiate a left and right pointer and a pivot point i. While i <= r, if nums[i] is zero do a swap with the left and the pivot point, if nums[i] is 2 do a swap with the right and pivot point, but do not increment the pivot point (that is why we decrement the pivot point in the if statment). Simply put we are breaking up the array into 3 section, 0, 1 and 2. Time Complexity: O(n) Space Complexity: O(1)
5.2			☐
5.3			☐
5.4	55. Jump Game		☐
5.5	26. Remove Duplicates from Sorted Array		☐
5.6	121. Best Time to Buy and Sell Stock 🟢	Code	✔️	Use a sliding window technique, have a left and right pointer beginning next to eachother. Window size depends on if right is less than left. Keep track of the maximum profit. Time Complexity: O(n) Space Complexity: O(1)	Video
5.7	123. Best Time to Buy and Sell Stock III		☐
5.8	280. Wiggle Sort		☐
5.9	204. Count Primes note: book asks to return a list of the primes		☐
5.10			☐
5.11	31. Next Permutation		☐
5.12			☐
5.13			☐
5.14	384. Shuffle an Array		☐
5.15			☐
5.16			☐
5.17	36. Valid Sudoku		☐
5.18	54. Spiral Matrix 🟡	Code	🟥	X ➡️ Not solved, but it is in the hackathon time frame.
5.19	48. Rotate Image		☐
5.20	118. Pascal's Triangle		☐
BLIND	11. Container With Most Water 🟡	Code	✔️
BLIND	15. 3Sum 🟡	Code	✔️
NC.io	27. Remove Element 🟢	Code	✔️	Max Time Complexity: // Space Complexity: //
BLIND	33. Search in Rotated Sorted Array 🟡	Code	✔️
BLIND	53. Maximum Subarray 🟢	Code	✔️	Max Time Complexity: O(n) Space Complexity: O(1)
BLIND	125. Valid Palindrome 🟢	Code	✔️	Use left and right pointer technique. Update left and right until each one points at an alphanum. A global while loop is needed to ensure that the two pointers do not cross. Then compare left and right, continue until left >= right. There are upper and lower case letters, therefore use a .lower() method to take care of that. There are two more solutions to this problem in the code. Make sure to make your own alphanum function, or write an algorithm using built-in methods. Time Complexity: O(n) Space Complexity: O(1)	Video
BLIND	152. Maximum Product Subarray 🟡	Code	✔️
BLIND	153. Find Minimum in Rotated Sorted Array 🟡	Code	✔️
NC.io (1)	217. Contains Duplicate 🟢	Code	✔️	Use a set() data structure to solve this problem. It is a built-in data type in Python used to store collections of data. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (2)	242. Valid Anagram 🟢	Code	✔️	Use the hashmap data structure to count each character in both strings, then compare the lengths of each element, or just compare the hashmaps. One liner solution is to sort the strings and compare, or use a Counter() and then compare. Go to the code to view the time and space complexities.	Video
NC.io (3)	1. Two Sum 🟢	Code	✔️	Use a hashmap data structure to keep track of the value and indice. Calculate the complement and check if it exists in the hashmap. Time Complexity: O(m*n) Space Complexity: O(n)	Video
NC.io (4)	49. Group Anagrams 🟡	Code	✔️	Create a HashMap, the key will be a list that holds the count of each letter, and the value will be a list of strings that have the same amount of letters. Return the values of the resulting HashMap at the end. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (5)	347. Top K Frequent Elements 🟡	Code	✔️	Create a count HashMap to count the frequency of every number. Create an array that holds arrays, the index will be the frequency of integer and the value at that index is a list that holds all the integers with that shared frequency. Once those have been populated loop through the frequency array, then loop through the other array and append it to the resulting array. Check if the length of the resulting array is k, if it is, return result. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (6)	238. Product of Array Except Self 🟡	Code	✔️	ARRAY ➡️ Instantiate a result array with 1s, it will be the length of the given array. Start from the beginning of res and calculate the prefix (set to 1), set the res with the calculated prefix (prefix multiplied by nums[i]). Start from the end of res and calculate the postfix (set to 1, calculated by postfix multiplied by nums[i]), the res will be given as res multiplied by the postfix. Return the res array. Time Complexity: O(n) Space Complexity: O(1) if output array doesn't count as memory	Video
NC.io (7)	36. Valid Sudoku 🟡	Code	✔️	HashSet Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (8)	659. Encode and Decode Strings 🟡	Code	✔️	Add the length of the string and a delimeter after it before every string. Then decode it by getting the getting the length, stopping the index count at the delimeter. The string will be index + 1 and index + 1 + length. Time Complexity: O(n) Space Complexity: O(1)	Video
NC.io (9)	128. Longest Consecutive Sequence 🟡	Code	✔️	Add all the nums in a set. Check if num is the start of a sequence, if it is, increment that value and continue checking if it exists in the set, if it does, increment the length value by one. Then once there are no more values that can be found, take the max of the length and the longest. Time Complexity: O(n) Space Complexity: O(n)	Video

Strings

Strings Syntax

Strings Problems

Problem	LeetCode	Solution	Completed	Notes
6.1	8. String to Integer (atoi) (Medium) 🟡	Code	🟥	X ➡️ Not solved, but it is in the hackathon time frame.
6.2		Code	☐
6.3	171. Excel Sheet Column Number	Code	☐
6.4		Code	☐
6.5	125. Valid Palindrome (Easy) 🟢	Code	✔️	Use left and right pointers. Update left and right until each one points at an alphanum. Then compare left and right, continue until left >= right. Don’t distinguish between upper and lowercase. Make own alphanum function
6.6	186. Reverse Words in a String II	Code	☐
6.7	17. Letter Combinations of a Phone Number	Code	☐
6.8	38. Count and Say	Code	☐
6.9	13. Roman to Integer	Code	☐
6.10	93. Restore IP Addresses	Code	☐
6.11		Code	☐
6.12	443. String Compression	Code	☐
6.13	28. Implement strStr()	Code	☐
BLIND	3. Longest Substring Without Repeating Characters (Medium) 🟡	Code	✔️	Use the sliding window technique, if we see the same character twice within the current window, shift the start position
BLIND	5. Longest Palindromic Substring (Medium) 🟡	Code	✔️
BLIND	76. Minimum Window Substring (Hard) 🔴	Code	✔️
BLIND	424. Longest Repeating Character Replacement (Medium) 🟡	Code	✔️
BLIND	647. Palindromic Substrings (Medium) 🟡	Code	✔️
BLIND	0. Encode and Decode Strings (Unknown) ⚫	Code	☐

Linked Lists

Linked Lists Implementations

In a Singly Linked List implementation, each node only points to one other node ahead of it. Below is the implementation of a linked list:

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

# Implementation for Singly Linked List
class LinkedList:
    def __init__(self):
        # Initialize the list with a 'dummy' node which makes removing a node from the beginning of list easier.
        self.head = ListNode(-1)
        self.tail = self.head
    
    def insertEnd(self, val):
        self.tail.next = ListNode(val)
        self.tail = self.tail.next

    def remove(self, index):
        i = 0
        curr = self.head
        while i < index and curr:
            i += 1
            curr = curr.next
        
        # Remove the node ahead of curr
        if curr and curr.next:
            if curr.next == self.tail:
                self.tail = curr
            curr.next = curr.next.next

    def print(self):
        curr = self.head.next
        while curr:
            print(curr.val, " -> ", end="")
            curr = curr.next
        print()

In a Doubly Linked List implementation, each node points to the next node and the previous node. Below is the implementation of a duobly linked list:

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

# Implementation for Doubly Linked List
class LinkedList:
    def __init__(self):
        # Init the list with 'dummy' head and tail nodes which makes 
        # edge cases for insert & remove easier.
        self.head = ListNode(-1)
        self.tail = ListNode(-1)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def insertFront(self, val):
        newNode = ListNode(val)
        newNode.prev = self.head
        newNode.next = self.head.next

        self.head.next.prev = newNode
        self.head.next = newNode

    def insertEnd(self, val):
        newNode = ListNode(val)
        newNode.next = self.tail
        newNode.prev = self.tail.prev

        self.tail.prev.next = newNode
        self.tail.prev = newNode

    # Remove first node after dummy head (assume it exists)
    def removeFront(self):
        self.head.next.next.prev = self.head
        self.head.next = self.head.next.next

    # Remove last node before dummy tail (assume it exists)
    def removeEnd(self):
        self.tail.prev.prev.next = self.tail
        self.tail.prev = self.tail.prev.prev

    def print(self):
        curr = self.head.next
        while curr != self.tail:
            print(curr.val, " -> ")
            curr = curr.next
        print()

Linked Lists Problems

Problem	LeetCode	Solution	Completed	Notes	Video Walkthrough
7.1	21. Merge Two Sorted Lists (Easy) 🟢	Code	✔️	Instantiate a dummy and a tail node that will hold dummy node at the start. Use a while loop that will continue as long as there is at least one of list1 or list2. Compare the values of list1 and list2 and append them respectively to the tail.next. Once the while loop ends, create an if statement check to see if there are still any nodes in the lists. If there is, append them to the tail.next at the end. Finally, return the dummy.next node. Time Complexity: O(n + m) Space Complexity: O(1)	Video
7.2	206. Reverse Linked List (Easy) 🟢	Code	✔️	Use the two pointer technique. Instantiate a previous and current pointer to None and head respectively. Start a while loop which continues while we have a current. Add current.next to a temp variable. Then set current.next to the previous node. Set the previous node to the current node and then set the current node to the temp variable. The temp saves the next value, we do the direction change and then shift our previous and current pointers. Once out of the while loop, we can return the previous node and the linked list is changed directionally. Time Complexity: O(n) Space Complexity: O(1)	Video
7.3	142. Linked List Cycle II (Medium) 🟡	Code	✔️	SET ➡️ You can use a set to keep track of nodes that we have gone through, however this takes up extra memory and is not the most optimal solution. Time Complexity: O(n) Space Complexity: O(n) HARE AND TORTOISE ➡️ Create a slow and fast pointer, the slow pointer increments by one and the fast pointer increments by two. Once the two pointers are the same, create a third pointer that starts at head. Take the new pointer and the old fast pointer and increment them by one until they are the same. Once they are the same, return the node. Time Complexity: O(n) Space Complexity: O(1)
7.4	160. Intersection of Two Linked Lists (Easy)	Code	☐
7.5	(Easy)	Code	☐
7.6	237. Delete Node in a Linked List (Easy)	Code	☐
7.7	19. Remove Nth Node From End of List (Medium) 🟡	Code	✔️
7.8	83. Remove Duplicates from Sorted List (Easy)	Code	☐
7.9	61. Rotate List (Easy)	Code	☐
7.10	328. Odd Even Linked List (Easy)	Code	☐
7.11	234. Palindrome Linked List (Easy)	Code	☐
7.12	86. Partition List (Easy)	Code	☐
7.13	2. Add Two Numbers (Easy)	Code	☐
BLIND	141. Linked List Cycle (Easy) 🟢	Code	✔️	SET ➡️ You can use a set to keep track of nodes that we have gone through, however this takes up extra memory and is not the most optimal solution. Time Complexity: O(n) Space Complexity: O(n) HARE AND TORTOISE ➡️ Create a slow and fast pointer, the slow pointer increments by one and the fast pointer increments by two. Once the two pointers are the same, return True. Time Complexity: O(n) Space Complexity: O(1)
BLIND	23. Merge k Sorted Lists (Hard) 🔴	Code	☐	Skipped
BLIND	143. Reorder List (Medium) 🟡	Code	✔️

Stacks and Queues

Stack Implementation

# Implementing a stack is trivial using a dynamic array
class Stack:
    def __init__(self):
        self.stack = []

    def push(self, n):
        self.stack.append(n)

    def pop(self):
        return self.stack.pop()

Queue Implementation

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class Queue:
    # Implementing this with dummy nodes would be easier!
    def __init__(self):
        self.left = self.right = None
    
    def enqueue(self, val):
        newNode = ListNode(val)

        # Queue is non-empty
        if self.right:
            self.right.next = newNode
            self.right = self.right.next
        # Queue is empty
        else:
            self.left = self.right = newNode

    def dequeue(self):
        # Queue is empty
        if not self.left:
            return None
        
        # Remove left node and return value
        val = self.left.val
        self.left = self.left.next
        if not self.left:
            self.right = None
        return val

    def print(self):
        cur = self.left
        while cur:
            print(cur.val, ' -> ', end ="")
            cur = cur.next
        print() # new line

Stacks and Queues Problems

Problem	LeetCode	Solution	Completed	Notes	Video Walkthrough
8.6	102. Binary Tree Level Order Traversal (Medium) 🟡	Code	✔️	BFS ➡️ Instantiate a queue, this can be done using the collections library or by simply using .pop(0) to remove from the front. While we have a full queue, we want to for loop in the range of the length of the queue, so that we visit all of the nodes on that level. We pop from the front, add the value to the list and add the left and right child nodes to the queue. After the for loop, if the level array is not empty, we append it to the result array. The while loop restarts, and continues as long as the child nodes get added. Return the result array Time Complexity: O(n) Space Complexity: O(n)
NC.io (1)	20. Valid Parentheses 🟢	Code	✔️	Push opening brace on stack, pop if matching close brace by checking the hashmap, at the end if the stack is empty, return true. Use hashmap for the closed to open parentheses. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (2)	155. Min Stack 🟡	Code	✔️	Use two stacks one to store the values, the other one to store the minimum value at every new value added. Time Complexity: O(1) Space Complexity: O(n)	Video
NC.io (3)	150. Evaluate Reverse Polish Notation 🟡	Code	✔️	Push to stack, double pop when an operator is reached. Subtraction is reversed, aswell as division. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (4)	22. Generate Parentheses 🟡	Code	✔️	Only add open parentheses if open < n. Only add closing p i closed < open. Base Case: valid IIF open == closed == n. .join() = The join in Python takes all the elements of an iterable and joins them into a single string. It will return the joined string. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (5)	739. Daily Temperatures 🟡	Code	✔️	Create a stack that holds a pair (temp, index), we want to iterate through the temperature array, looping through the temperature and index, using the enumerate() method. While loop, conditions, stack non-empty and current temp greater than temp on top of stack: if true pop and add days to res array. Time Complexity: O(n) Space Complexity: O(n)	Video
NC.io (6)	853. Car Fleet 🟡	Code	✔️	Calculate time it takes to reach the target and add to stack. Check the top two values, if top is less/equal to the one below, pop the top off because that is a collision. Returning length of stack. Time Complexity: O(nlogn) Space Complexity: O(n)	Video
NC.io (7)	84. Largest Rectangle in Histogram 🔴	Code	✔️	Time Complexity: O(n) Space Complexity: O(1)	Video

Binary Trees

Binary Trees Syntax

Binary Trees Problems

Problem	LeetCode	Solution	Completed	Notes
9.1	110. Balanced Binary Tree (Easy) 🟢	Code	✔️	RECURSIVE DFS ➡️ Create a recursive DFS function. The base case will be when the node is null, you will return [True, 0] because it has a height of zero and it is balanced, therfore True. Then we will check the left and right child nodes, by calling the DFS function again. This will return the tuple. When we have the left and right tuple, we can check that it is balanced. To be balanced left and right must both be True, and the height must be less than or equal to one. We return a tuple [balanced, 1 + max(left, right)]. After creating the function, we call the DFS function on the root and return the boolean at position 0. Simply put we are recursively traversing to the bottom of the tree to its last nodes and then traversing back up, returning the height and the boolean. Time Complexity: O(n) Space Complexity: O(n)

Heaps

Heaps Syntax

Heaps Problems

Searching

Searching Syntax

Searching Problems

Problem	LeetCode	Solution	Completed	Notes
11.4	69. Sqrt(x) (Easy) 🟢	Code	✔️	BINARY SEARCH ➡️ Use a binary searchy, find the mid point, square it and compare it to the k. Time Complexity: O(log(n)) Space Complexity: O(1)
11.8	215. Kth Largest Element in an Array (Medium) 🟡	Code	☐	➡️ Time Complexity: O(n) Space Complexity: O(n)

Hash Tables

Hash Tables Syntax

Hash Tables Problems

Problem	LeetCode	Solution	Completed	Notes
12.2	383. Ransom Note (Easy) 🟢	Code	✔️	HASH TABLE ➡️ First solution using two hashtables Time Complexity: O(n + m) Space Complexity: O(n + m) HASH TABLE ➡️ Second solution using one hashtable and updating frequencies Time Complexity: O(n) Space Complexity: O(n)
12.X	69. Sqrt(x) (Easy) 🟢	Code	✔️	➡️ Time Complexity: O(n) Space Complexity: O(n)

Primitive Types

Be very comfortable with the bitwise operators, particularly XOR. Understand how to use masks and create them in an machine independent way, Know fast ways to clear the lowermost set bit (and by extension, set the lowermost 0, get its index, etc.) Understand signedness and its implications to shifting. Consider using a cache to accelerate operations by using it to brute-force small inputs. Be aware that commutativity and associativity can be used to perform operations in parallel and reorder operations.

Primitive Types Syntax

Bitwise operations:

Operator 	Example 	Meaning
&		a & b		Bitwise AND (equiv to product)
|		a | b		Bitwise OR
^		a ^ b		Bitwise XOR (exclusive OR)
~		~a		Bitwise NOT (only unary operator)
<<		a << n		Bitwise left shift
>>		a >> n		Bitwise right shift

All binary bitwise operators have a corresponding compound operator that performs an augmented assignment:

Operator	Example		Equivalent to
&=		a &= b		a = a & b
|=		a |= b		a = a | b
^=		a ^= b		a = a ^ b
<<=		a <<= n		a = a << n
>>=		a >>= n		a = a >> n

Primitive Types Problems

Problem	LeetCode	Solution	Completed	Notes
4.1	() ⚫ (Unknown)	Code
4.7	50. Pow(x, n) (Medium) 🟡	Code	🟥	RECURSION ➡️ Not solved, but it is in the hackathon time frame. Did not solve it using bitwise operators. No clue how. Information is not all included in this question

Name		Name	Last commit message	Last commit date
Latest commit History 2 Commits
Elements of Programming Interviews in Python/Arrays		Elements of Programming Interviews in Python/Arrays
LeetCode		LeetCode
Scratch Code/Arrays		Scratch Code/Arrays
.gitattributes		.gitattributes
README.md		README.md

Completed	Problem	Solution	Notes	Video Walkthrough
❌	707. Design Linked List 🟡	Add Code		Add Video
❌	1472. Design Browser History 🟡	Add Code		Add Video

Completed	Problem	Solution	Notes	Video Walkthrough
❌	225. Implement Stack using Queues 🟢	Add Code		Video
❌	1700. Number of Students Unable to Eat Lunch 🟢	Add Code		Add Video

Completed	Problem	Solution	Video Walkthrough
❌	374. Guess Number Higher or Lower 🟢	Add Code	Video
❌	278. First Bad Version 🟢	Add Code	Add Video
❌	875. Koko Eating Bananas 🟡	Add Code	Video

Completed	Problem	Solution	Notes	Video Walkthrough
✔️	26. Remove Duplicates from Sorted Array 🟢	Add Code		Video
✔️	27. Remove Element 🟢	Add Code		Video

Completed	Problem	Solution	Notes	Video Walkthrough
✔️	21. Merge Two Sorted Lists 🟢	Add Code		Video
✔️	206. Reverse Linked List 🟢	Add Code		Video

Completed	Problem	Solution	Notes	Video Walkthrough
❌	70. Climbing Stairs 🟢	Add Code		Video
❌	509. Fibonacci Number 🟢	Add Code		Video

Completed	Problem	Solution	Notes	Video Walkthrough
❌	912. Sort an Array 🟡	Add Code		Video
❌	23. Merge k Sorted Lists 🔴	Add Code		Video

Completed	Problem	Solution	Notes	Video Walkthrough
❌	74. Search a 2D Matrix 🟡	Add Code		Video
❌	704. Binary Search 🟢	Add Code		Video

Completed	Problem	Solution	Video Walkthrough
❌	53. Maximum Subarray 🟡	Code	Video
❌	918. Maximum Sum Circular Subarray 🟡	Code	Video
❌	978. Longest Turbulent Subarray 🟡	Code	Video

MikeyLuo/Python-Preparation

Folders and files

Latest commit

History

Repository files navigation

Python Fundamentals and Preparation

Table of Contents

Algorithms and Data Structures for Beginners

Arrays

RAM

Static Arrays

Suggested Problems

Dynamic Arrays

Suggested Problems

Stacks

Suggested Problems

Linked Lists

Singly Linked Lists

Suggested Problems

Doubly Linked Lists

Suggested Problems

Queues

Suggested Problems

Recursion

Factorial

Suggested Problems

Fibonacci

Suggested Problems

Sorting

Insertion Sort

Suggested Problems

Merge Sort

Suggested Problems

Quick Sort

Suggested Problems

Bucket Sort

Suggested Problems

Binary Search

Search Array

Suggested Problems

Search Range

Suggested Problems

Advanced Algorithms

Advanced Arrays

Kadane's Algorithm

Suggested Problems

Python Basics

Variables

Dynamically Typed

Multiple Assignments

Incrementing

Math

Division

Modulo

More Math

Useful Functions

+/- Infinity

If Statements

Loops

While Loops

For Loop

Looping from i = 0 to i = 4

Looping from i = 2 to i = 5

Looping from i = 5 to i = 2

Elements of Programming Interviews in Python

Arrays

Arrays Syntax

Instantiation

Indexing

Slicing

Basic Operations

Looping Through Array

2-D Lists

Value Exists

Copying (Shallow & Deep)

Shallow Copy

Deep Copy

Key Methods

List Comprehension

Arrays Problems

Looping from `i = 0` to `i = 4`

Looping from `i = 2` to `i = 5`

Looping from `i = 5` to `i = 2`

Packages