Understanding Data Structures with Grokking Algorithms!

Binary search

The search problem: to find element x in given list i, should i start from the beginning or start near the middle and split each step up?

def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
mid = int((low + high)/2)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1)) # => None

Running times

Whenever the maximum amount of guesses is equal to the size of the list, we generally define this to be linear time.

Lists + Arrays

Think of your computer as a giant set of drawers with each drawer having an address.

Insertion

Generally, with lists, insertion is quite easy. You just simply change the address the previous element points to.

Deletion

Again, lists are better. You simply just change what the previous element points to while with arrays, everything needs to be moved up when you delete the element.

Arrays vs lists?

Arrays are generally used more because they can allow for random access. We generally have 2 types of access: random access and sequential [one by one] access. Linked lists can only do sequential access while random allows you to jump directly to your desired element.

Selection sort

Let’s say that I’m sorting music

def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
>>> print selectionSort([5, 3, 6, 2, 10])
[2, 3, 5, 6, 10]

Recursion

It’s where a function calls itself.

def look_for_key(box):
for item in box:
if item.is_a_box():
look_for_key(item)
elif item.is_a_key():
print “found the key!”
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
  1. Use something known as tail recursion. (only supports some languages)

Divide and Conquer

Divide and Conquer is generally used in situations where you need to solve a problem that can’t be solved with the existing algorithms you’ve learned.

  1. Figure out how to reduce your problem and get to the base case.

Quicksort

Quicksort is generally known as a sorting algorithm. It’s a lot faster than selection sort and is generally used. It uses a recursive algorithm structure for fast + proper sorting.

  1. From there, you bin the smaller + larger elements into 2 separate arrays. (This overall process is known as partitioning.)
  2. You then run this recursively until you get sorted arrays and then you can simply concatenate everything and you now have your output.
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
print(pivot)
print(less)
print(greater)
print("-"*20)
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))

Hash tables

The goal with hash tables mainly is to be able to retrieve information about an item instantaneously. Something that’s running time is O(1).

  1. Hash functions map different strings to different indexes.
  2. Hash functions know how big your array already is and can only return valid indexes.

Graphs + Breadth-first search

Breadth-first search allows you to find the shortest distance between 2 values.

  1. Solve the problem using breadth-first search
  1. What is the shortest path from node A to node B?

Linear programming

Linear programming can be used to maximize something given the time constraints.

Queues

The way we’d organize through different hierarchies (levels) of nodes is through queues. They’re similar to stacks but you can only perform 2 operations: enqueue and dequeue.

graph = {}
graph[“you”] = [“alice”, “bob”, “claire”]
graph[“bob”] = [“anuj”, “peggy”]
graph[“alice”] = [“peggy”]
graph[“claire”] = [“thom”, “jonny”]
graph[“anuj”] = []
graph[“peggy”] = []
graph[“thom”] = []
graph[“jonny”] = []
# A use case of this for "mango" sellers

from collections import deque
search_queue = deque()
search_queue += graph[“you”]

def person_is_seller(name):
return name[-1] == ‘m’

while search_queue:
person = search_queue.popleft()
if person_is_seller(person):
print person + “ is a mango seller!”
return True
else:
search_queue += graph[person]
return False
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
while search_queue:
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print person + “ is a mango seller!”
return True
else:
search_queue += graph[person]
searched.append(person)
return False

Dijkstra’s Algorithm

4 main steps:

  1. Update the costs of the neighbours of the node.
  2. Repeat this until you’ve done this for every node in the graph.
  3. Calculate the final path
def find_lowest_cost_node(costs):
lowest_cost = float(“inf”)
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node

node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if costs[n] > new_cost: #we want to reduce + lower the cost
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)

Greedy algorithms

It’s pretty straightforward: at each step, you pick the locally optimal solution, and in the end, you’re left with the globally optimal solution.

The Set-covering problem

  1. Repeat until all the states are covered.
  1. How close they are to the optimal solution
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
arr = [1, 2, 2, 3, 3, 3]
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
final_stations = set()
while states_needed:
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
covered = states_needed & states_for_station # this is a set intersection
if len(covered) > len(states_covered): #check whether this station covers more states then the current station, best_station
best_station = station #update if condition is met
states_covered = covered
states_needed -= states_covered #update because the station has covered those states
final_stations.add(best_station)
print(final_stations)

Dynamic programming

We talked about in the previous chapter (greedy algorithms) that sometimes, we can only come up with an approximate solution. But is it even possible to find + calculate the optimal solution? That’s where dynamic programming comes in.

The knapsack problem

  1. The values in the cells are usually what you’re trying to optimize. For the knapsack problem, the values were the value of the goods.
  2. Each cell is a subproblem, so think about how you can divide your problem into subproblems. That will help you figure out what the axes are.

Longest common subsequence

Suppose Alex accidentally searched for fosh. Which word did he mean: fish or fort?

  1. Have you ever used diff (like git diff)? Diff tells you the differences between two files, and it uses dynamic programming to do so.
  2. We talked about string similarity. Levenshtein distance measures how similar two strings are, and it uses dynamic programming. Levenshtein distance is used for everything from spell-checking to figuring out whether a user is uploading copyrighted data.

k-Nearest Neighbors

Generally, the main intuition behind KNNs is finding the closest neighbour of a point when graphed out.

  1. Features that don’t have a bias (for example, if you ask the users to only rate comedy movies, that doesn’t tell you whether they like action movies)

Binary trees

The main intuition behind binary search trees is mainly that whenever you do binary search, you have to add and then sort the array. That’s inefficient.

Inverted indexes

Let’s say that we have 3 web pages with this content:

From there, let’s build a hash table from that:

Fourier transform

Fourier transform is essentially this algorithm that: given a smoothie, the Fourier transform will tell you the ingredients in that smoothie. Or given a song, the transform can separate it into individual frequencies.

Parallel algorithms

The main focus of parallel algorithms is to take advantage of the multiple cores in a computer.

  1. Load distribution amongst processors — if you have 10 tasks to do, you’d probably give each core 5 tasks. What’s the problem? The first core is given the easy tasks whereas the other core gets all the hard tasks. Now a core stays idle while it could be used to work.

MapReduce

A special type of parallel algorithm used is MapReduce that’s becoming increasingly famous, known as distributed algorithms. MapReduce is essentially a popular distributed algorithm to manage workloads amongst hundreds of cores.

>>> arr1 = [1, 2, 3, 4, 5]
>>> reduce(lambda x,y: x+y, arr1)
15

Bloom filters + HyperLogLog

The main problem is that you want to go through a large list to figure out whether an element is in a large set.

SHA Algorithms

SHA (Secure hash algorithms) convert input to a hash for that string. Note: hashes are just a short string in this context where the goal is string→string.

Diffie-Hellman key exchange

The DH key exchange solves a problem that’s lurking for quite some time now: How do you encrypt a message so it can only be read by the person you sent the message to?

  1. The encrypted messages are extremely hard to decode.

--

--

solving self-driving cars. srianumakonda.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store