class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next Draw It out! To solve the linked list problems, the most important thing is to draw the linked list and the procedure out.
2021-04-15
Hash Table The Hash table data structure stores elements in key-value pairs where Key - unique integer that is used for indexing the values Value - data that are associated with keys.
2021-04-08
TL;DR Merge sort use Divide and Conquer strategy Repeatedly divides the array into two subarrays until subarrays of size 1 Merge two sorted array to achieve a bigger sorted array Time complexity is $O(n \log n)$ Space complexity is $O(n)$ (non-inplace) How Merge Sort Works?
2021-04-06
TL;DR Divide and Conquer (D&C) Partition the array with the selected pivot: [elements <= pivot, pivot, elements > pivot]. Recursively apply quick sort on left and right sub-arrays. Average time complexity: $O(n \log n)$ 💡 Idea Pick a pivot Partition the array into two sub-arrays Elements less thant the pivot go to the left sub-array Elements greater thant the pivot go to the right sub-array Call quick sort recursively on the two sub-arrays Concat left sub-array, pivot, and right sub-array Implementation Quick sort can be implemented using Divide and Conquer (D&C).
2021-04-06
TL;DR Key idea: repeatedly selecting the smallest remaining item Time complexity: $O(n^2)$ Idea The idea of selection sort is pretty simple: First, find the smallest item in the array and exchange it with the first entry Then, find the next smallest item and exchange it with the sec- ond entry.
2021-04-06
Every recursive function has two parts base case: the function does not call itself again, so it will not go into an infinite loop recursive case: the function calls itself Sometimes recursion could be also re-written using loops.
2021-04-06
TL;DR Array Linked List Store in memory Elements are stored in contiguous locations in memory. Elements can be stored anywhere in memory Size Fixed, must be specified at the time of initialization Changeable, can grow/shrink by insertion/deletion Access element Random access
2021-04-05
Binary search only works when your list is in sorted order. Code def binary_search(list, item): # keep track of low and high low = 0 high = len(list) - 1 while low <= high: # when we haven't narrowed down to one element mid = (low + high) // 2 # index of the middle element guess = list[mid] # value of the middle element if guess == item: return mid elif guess > item: # Guess is too high, # we narrow our search on the "left" part high = mid - 1 else: # Guess is too low, # we narrow our search on the "right" part low = mid + 1 # If we have anrrowed down to one element but still can not find the item # => Item is not in the list return -1 Complexity Time complexity: $O(\log n)$ Binary Vs Linear Search Average Case Binary Search Worst Case Binary Search Best Case
2021-04-04
Definition In general, a better algorithm means a FASTER algorithm. In other words, it costs less runtime or it has lower time complexity. Big O notation is one of the most fundamental tools to analyze the cost of an algorithm.
2021-04-04