DEV Community: Whiteboarding in Python

Sum of Three, Sum of Four, and Beyond? In Python!

Whiteboarding in Python — Thu, 25 Mar 2021 02:20:38 +0000

<< #21 Tree Practice | View Solution on GitHub

Actual pic of me after trying to solve this problem (Image: Bend Pet Express)

Today's problem has stumped many a programmer. A colleague of mine and I sat down with "Sum of Three", talked it out, and after more than an hour, finally finished a solution that was by no means elegant or optimal. I was joking with him that next we should try "Sum of Four", which I had totally made up. Turns out, it's real. After another long whiteboarding session, we came up with...a bunch of ideas and no solution.

We were so focused on finding an elegant solution that we missed being able to solve the problem at all. But here's an obvious solution: brute force. Brute force may be simple, and it certainly isn't optimal, but it gets the job done. And when you have no other solution, it helps to have at least one way to solve it.

(Image: KnowYourMeme)

Today, we're going to look at "Sum of Three" and "Sum of Four", and solve them using brute force. Then, you'll see how we can expand the brute force solution using recursion to allow for "Sum of K", which will work for 3, 4, or any amount of numbers we want to sum up. You'll see that having a brute force solution might not be scalable, but you can still build some powerful things.

Let's get started with the simpler problem, "Sum of Three". Here is the prompt:

# Given an array nums of n integers and a target,
# are there elements a, b, c in nums 
# such that a + b + c = target?

# Example:

# Input: 
# nums = [-1,0,1,2,-1,-4]
# target = 0

# Output: [[-1,-1,2],[-1,0,1]]

# Notice that the solution set must not contain duplicate triplets.

Were given a list of numbers, and we want to find every three numbers in the list that sum to zero, or whichever number is specified at the target. How would you go about solving this?

1. Approach

The brute force solution will involve iteration. Imagine we look at each number, and check it against every other number, and then check those two numbers against every other other number. What does this sound like? If you said a triple nested for loop, you're right (I'm sure there must also be a recursive way to do this part...let me know in the comments if you found it!).

But theres one other caveat, as listed in the prompt: Notice that the solution set must not contain duplicate triplets. How will we account for this? If you've been following this blog, you're probably thinking of using a set (more on this here). And yep, that's what we will be using. We'll codify each working triplet into a string and put it in the set to make sure we haven't included it already.

2. Setup

We're ready to start writing this bad boy. Our method sum_of_three will take in two arguments: the list nums and the target.

def sum_of_three(nums, target):

Next, we need to check for an edge case. What if nums has less than 3 numbers in it? Then we can't find a triplet. In this case, we'll return an empty list.

def sum_of_three(nums, target):
  if len(nums) < 3:
    return []

Finally, we need to initialize some variables that we'll be using. Firstly, the output list which will contain lists of triplets. We'll also start one of those triplet lists and call it current. Once we populate current with a working triplet, we can append it to output.

  output = []
  current = []

And, as discussed earlier, we'll need to make a set. Additionally, we'll want to sort the list to make sure we don't add the same triplet to the set, just in a different order (for instance, only one of [1, -2, 1] and [1, 1, -2] should be added).

  checked = set()
  nums.sort()

3. Iteration

We're ready to start our for loops. We're making three of them, and the most important part to consider is our indices' upper and lower bounds.

For the first loop, we'll start with the first number in the list and go until the 3rd from the last spot. Why? We need two additional numbers to check this with, and once we get to the 2nd or last index, there aren't enough numbers behind it to make a triplet.

  for i in range(len(nums) - 2):

As a review, range(start, end) accepts two arguments: a start (inclusive) and an end (exclusive). If the start argument is missing, it's assumed to be 0.

Okay, what will we do inside this first for loop? Here's the agenda:

Add the first number to current.
Subtract that number from the sum.
Check it with the other numbers.
Undo steps 1 and 2 so we can move on to the next number.

Let's write these in code. The first one is easy, simply append the number at index i to current.

    current.append(nums[i])

The next step is also pretty simple. You can subtract from the target, but I prefer making a new variable that makes it clear that we're changing it, called working_target.

    working_target = target - nums[i]

Step 3 is more complicated. "Check it with the other numbers" is my shorthand for doing the nested for loops. I'll comment it out for now.

Step 4 is simple. Remove the last element from current with current.pop(), and to move the target back, well, we don't need to do anything because it's going to be re-instantiated each iteration. Altogether, our loop looks like this so far:

  for i in range(len(nums) - 2):
    current.append(nums[i])
    working_target = target - nums[i]
    # do some for loops
    current.pop()

Great, we're ready to move onto loop #2.

What are our indices? We start at the index after i and go until the second-to-last spot in nums.

    for j in range(i + 1, len(nums) - 1):

Next, we follow our steps 1-4 again. That is, we append the number at j to current, subtract it from working_target, leave space for the next loop, and then undo steps 1 and 2.

    for j in range(i + 1, len(nums) - 1):
      working_target -= nums[j]
      current.append(nums[j])
      # do another for loop
      current.pop()
      working_target += nums[j]

Finally, we can write our innermost loop. The indices should be familiar by now, we start at j + 1 and go until the last index.

      for k in range(j + 1, len(nums)):

We can append the number at k to current, but when we subtract from the working_total, now we want to check if it equals zero. If the numbers all sum to the target, then target - a - b - c = 0 (if you remember back to algebra class).

      for k in range(j + 1, len(nums)):
        current.append(nums[k])
        if working_target - nums[k] == 0:

What goes in the if statement? Now it's time to use our set to determine if we've checked this triplet already.

We can't put lists into a set, so we have to codify our triplet into a string. The following code will make a string with &s in between the numbers, for example, [1, 1, -2] will get turned into 1&1&-2. You can use any character you want to deliniate the numbers, but you need something so 1, 11 isn't confused with 11, 1.

          # make code to put in duplicate set
          code = str(current[0])
          for n in range(1, len(current)):
            code += "&" + str(current[n])

Now we can check to see if the code is in the set. If not, we can add it to the set and add current to our final output. Remember to add a copy of current, and not just the reference. Otherwise, our triplet could change after we add it to output!

if code not in checked:
output.append(current.copy())
checked.add(code)

Lastly, we pop the third number off of current. Altogether, the final for loop:

      for k in range(j + 1, len(nums)):
        current.append(nums[k])
        if working_target - nums[k] == 0:
          # make code to put in duplicate set
          code = str(current[0])
          for n in range(1, len(current)):
            code += "&" + str(current[n])
          if code not in checked:
            output.append(current.copy())
            checked.add(code)
        current.pop()

4. Wrapping up Sum of Three

All that's left is to return our output list. Then, we're done! Here is the full method; be sure that your indentation matches exactly after all those for loops:

def sum_of_three(nums, target):
  if len(nums) < 3:
    return []
  output = []
  current = []
  checked = set()
  nums.sort()
  for i in range(len(nums) - 2):
    current.append(nums[i])
    working_target = target - nums[i]
    for j in range(i + 1, len(nums) - 1):
      working_target -= nums[j]
      current.append(nums[j])
      for k in range(j + 1, len(nums)):
        current.append(nums[k])
        if working_target - nums[k] == 0:
          # make code to put in duplicate set
          code = str(current[0])
          for n in range(1, len(current)):
            code += "&" + str(current[n])
          if code not in checked:
            output.append(current.copy())
            checked.add(code)
        current.pop()
      current.pop()
      working_target += nums[j]
    current.pop()
    working_target += nums[i]
  return output

Here is some sample driver code to test the method:

nums = [-1,0,1,2,-1,-4]
target = 0
print(sum_of_three(nums, target))

This will give us the final output of [[-1,-1,2],[-1,0,1]]. Notice how there are no duplicate triplets, even though there are two -1s to make the second triplet.

5. Step Up Complexity: Sum of Four

You were feeling pretty good, just finished Sum of Three. But can you next solve...sum of four?

Although it sounds more complex, conceptually, we can use the same brute force method. I know that our runtime will go from the terrible O(N³) to the even worse O(N⁴), but like I said earlier. It will still *run*.

How will we achieve this? We can simply adjust our code from sum_of_three by adding another loop. Each loop starts at the previous index + 1 and ends progressively closer to the end of the list. Here is what they will look like:

 for i in range(len(nums) - 3):
    for j in range(i + 1, len(nums) - 2):
      for k in range(j + 1, len(nums) - 1):
        for m in range(k + 1, len(nums)):

In each loop, we'll follow the same steps as before: appending to current, subtracting from the target, checking some stuff, and then undoing the previous actions. I'll save you some scrolling and post the method in full:

def sum_of_four(nums, target):
  if len(nums) < 4:
    return []
  output = []
  current = []
  nums.sort()
  checked = set()
  for i in range(len(nums) - 3):
    working_target = target - nums[i]
    current.append(nums[i])
    for j in range(i + 1, len(nums) - 2):
      working_target -= nums[j]
      current.append(nums[j])
      for k in range(j + 1, len(nums) - 1):
        working_target -= nums[k]
        current.append(nums[k])
        for m in range(k + 1, len(nums)):
          current.append(nums[m])
          if working_target - nums[m] == 0:
            # make code to put in duplicate set
            code = str(current[0])
            for n in range(1, len(current)):
              code += "&" + str(current[n])
            if code not in checked:
              output.append(current.copy())
              checked.add(code)
          current.pop()
        current.pop()
        working_target += nums[k]
      current.pop()
      working_target += nums[j]
    current.pop()
  return output

This exactly matches our method for "Sum of Three", just with an extra loop. We can run the following driver code:

nums = [1,0,-1,0,-2,2, 0]
target = 0
print(sum_of_four(nums, target))

And our result is [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]. It works!

6. Sum of Five...and Beyond?

You wrote "Sum of Three" and "Sum of Four"; you're feeling pretty confident. What if I told you next you need to solve...Sum of Five?

No problem, you say. Just add another for loop. But you might have noticed something. This looks a little repetitive:

for j in range(i + 1, len(nums) - 2):
  working_target -= nums[j]
  current.append(nums[j])
  for k in range(j + 1, len(nums) - 1):
    working_target -= nums[k]
    current.append(nums[k])
    for m in range(k + 1, len(nums)):
      current.append(nums[m])

And you're right. When we have repetitive code, a good practice is to write a method for it. So what if we wrote a recursive method to run each for loop? Then, we could tell it how many numbers we want to sum together, and it will know how many nested loops to construct.

We'll set up the method exactly we have as before, although this time, we take in an argument k of how many numbers (triplet, quadruplet, etc.) to sum.

def sum_of_k(nums, target, k):
  if len(nums) < k:
    return []
  output = []
  current = []
  nums.sort()
  checked = set()

Next, we'll make a recursive method called sum_helper() that accepts...pretty much every variable we have so far. Additionally, we need to know the previous index (for when we start the loop at i + 1), which starts at 0. This method will alter the arrays, so we just need to call it and then afterwards, return output.

  sum_helper(nums, target, k, output, checked, current, 0)
  return output

7. Iteration in the Recursive Method

Let's think about our approach for the recursive helper method. Each time, we're going to be subtracting from k. After all, "Sum of Four" is just "Sum of Three" with an extra number attached.

Our recursive method will need a base case. If k is zero, we don't have to do anything. In this case, we'll simply return out of the function.

  if k == 0:
    return

If k is greater than zero, we want to loop through nums. We'll start at the index prev and go until the end of the list - k + 1 (we get this by looking at the pattern in our previous solutions).

  for i in range(prev, len(nums) - k + 1):

What's next? Look at our list: we append the current number to current.

    current.append(nums[i])

You might think the next step is to subtract that number from the target, but we need to check something first. This for loop needs to be universal for every iteration of k, and we need to account for if this is the innermost loop.

If this is the case, we need to check if the target minus the number is zero. Then we do exactly what we did before (you could probably copy paste with minimal edits) by adding to the set and if unique, add to the output.

if k == 1 and target - nums[i] == 0:
  # make code to put in duplicate set
  code = str(current[0])
  for n in range(1, len(current)):
    code += "&" + str(current[n])
  if code not in checked:
    output.append(current.copy())
    checked.add(code)

Now we can subtract from the working target and write our recursive case. But wait, we can do this all in one step! Here is the recursive call:

sum_helper(nums, target - nums[i], k - 1, output, checked, current, i + 1)

So target moves, k goes down 1, and the current index + 1 becomes the previous index prev.

Finally, we have to undo our addition to current:

current.pop()

And that's it! Together, here are our methods:

def sum_of_k(nums, target, k):
  if len(nums) < k:
    return []
  output = []
  current = []
  nums.sort()
  checked = set()
  sum_helper(nums, target, k, output, checked, current, 0)
  return output

def sum_helper(nums, target, k, output, checked, current, prev):
  if k == 0:
    return
  for i in range(prev, len(nums) - k + 1):
    current.append(nums[i])
    if k == 1 and target - nums[i] == 0:
      # make code to put in duplicate set
      code = str(current[0])
      for n in range(1, len(current)):
        code += "&" + str(current[n])
      if code not in checked:
        output.append(current.copy())
        checked.add(code)
    sum_helper(nums, target - nums[i], k - 1, output, checked, current, i + 1)
    current.pop()

Our method is still pretty unwieldy, but we don't have to adjust it for every changing k. The following driver code will work whether k is 3, 4, or beyond!

nums = [-1,0,1,2,-1,-4, -2]
target = 0
k = 4
print(sum_of_k(nums, target, k))
# -> [[-2, -1, 1, 2], [-1, -1, 0, 2]]

Again, this is a brute force solution. The run time will be O(N^k), which is pretty bad if k is large. This problem could probably be solved more elegantly with linear algebra, so if some of you are particularly knowledgeable on that front and come up with something, let me know in the comments!

<< #21 Tree Practice | View Solution on GitHub

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Binary Tree Practice in Python: Mirror Tree

Whiteboarding in Python — Thu, 11 Mar 2021 00:07:15 +0000

<< #20 Breadth-First Search | View Solution on GitHub | #22 Sum of Three+ >>

(Image: FollowingNature on Flickr)

In the previous article, we discussed the differences between breadth- and depth-first search for trees and graph problems. Today, we're going to actually look at a sample problem, and given our new toolbox of search strategies, figure out the best way to implement a solution.

Here's the problem from LeetCode.

# Given the root of a binary tree, check whether it is 
# a mirror of itself (i.e., symmetric around its center).

Let's look at some examples.

(Image: LeetCode)

Giving the function the root of the above tree would yield True, since the values in the left half of the tree mirror the values in the right.

(Image: LeetCode)

In the above tree, the nodes with 3 are not organized to mirror each other. Passing the root would yield False.

1. Strategy

As with binary tree problems, the first thing we want to ask is if we should use breadth- or depth-first search. At first glance, you might think BFS would make sense, seeing that all the nodes are the same across the first two levels. But once we look at the third level with the nodes 3, 4, 4, 3, suddenly, it gets more complicated. Instead, what if we split the tree into two halves and ran a depth-first-search on each half? Let's look at the first example again:

If we were to look at the left half, depth-first-traversal would read the nodes in the order: 2, 3, 4. At the same time, we can travel down the right side of the tree and print the same 2, 3, 4. We then conclude the tree is symmetrical.

2. Setup

The first thing we'll need is our TreeNode class. As always, it will take data, the value we want to store on the node, and then a left and right pointer, which are initialized to None.

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

Next, we define our method, which takes in one value: the root node of the tree.

def is_mirror(root):
  pass

Remember how we said we would split the tree into two halves, and then check the nodes in each half? We'll do that by calling a recursive helper method, check_halves. This method takes a left and right node, which will be root.left and root.right to start.

def is_mirror(root):
  return check_halves(root.left, root.right)

3. Traversal

As with most tree traversals, we'll be using recursion. Start by defining our helper method that takes in a left and right tree.

def check_halves(left, right):

What is our base case? The simplest example would be a tree with only the root node, whose left and right halves are both None. In this case, we return True.

def check_halves(left, right):
  if not left and not right:
    return True

What's next? We want to check that there are both a left and right node, and that their values match. These can be put in the same if statement, but I'll separate them for clarity.

def check_halves(left, right):
  if not left and not right:
    return True
  if left and right:
    if left.data == right.data:

Next, we recurse! Here, we'll do a depth-first traversal on the left and right halves of the tree.

      left_half = check_halves(left.left, right.right) 
      right_half = check_halves(left.right, right.left)

Then, we check to see if they are both True. This can be achieved with an and statement.

      return left_half and right_half

Finally, we return the False if the previous if condition was not met. Altogether, our helper method looks like this:

def check_halves(left, right):
  if not left and not right:
    return True
  if left and right:
    if left.data == right.data:
      left_half = check_halves(left.left, right.right) 
      right_half = check_halves(left.right, right.left)
      return left_half and right_half
  return False

4. Test it Out

The following code will build the tree from the example.

tree1 = TreeNode(1)
tree1.left = TreeNode(2)
tree1.right = TreeNode(2)
tree1.left.left = TreeNode(3)
tree1.right.right = TreeNode(3)
tree1.left.right = TreeNode(4)
tree1.right.left = TreeNode(4)

Now we just have to call print(is_mirror(tree1)) and it will print True. Success!

Let's try a tree that isn't symmetrical, like the second example. The two nodes with the value 3 aren't positioned to mirror each other.

tree2 = TreeNode(1)
tree2.left = TreeNode(2)
tree2.right = TreeNode(2)
tree2.left.left = TreeNode(3)
tree2.right.left = TreeNode(3)

Printing is_mirror(tree2) should give us False. The same will work if we change any values in the first tree so that they don't match left and right.

That's it for this week, I hope this was a good lesson on how to use DFS concepts to solve a Binary Tree problem. In a future article, we'll take a look at a problem where a breadth first approach would work better.

<< #20 Breadth-First Search | View Solution on GitHub | #22 Sum of Three+ >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

More Python Binary Trees: What is Breadth vs Depth First Search?

Whiteboarding in Python — Tue, 23 Feb 2021 04:44:51 +0000

<< #19: JS Arrays | View Solution on GitHub | #21: Mirror Tree >>

IRL Breadth and Depth. (Images: 48days.com, deeperblue.com)

Christmas is over, but the classic data structure Binary Trees is forever. At least, technical hiring managers seem to think so. And when you're asked to solve a binary tree problem on an interview, the first thing your interviewer will want to know is this: breadth or depth first?

What's the difference?

Breadth First Search and Depth First Search, or BFS and DFS, are exactly as they sound--it's about the order of nodes we visit when traversing a tree. Depth first travels down the tree before traveling across, and breadth is just the opposite--start with the root and work down to its children, and then its children's children, and so on.

(Image: GeeksForGeeks)

For example, in the above tree, a BFS approach would yield 1, 2, 3, 4, 5.

For DFS, there are multiple possible outcomes depending on if we do a Pre-, Post-, or In- order traversal. For example, Pre-order would yield 1, 2, 4, 5, 3. We've covered these three traversals in this article.

Implementing Breadth First Search in Python

Let's look at how we would do a BFS in Python. Start by defining our TreeNode class, which simply needs a value, and a left and right pointer.

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

1. Strategy

Here's how we will approach traversing each node by level:

Find the full height of the tree from root to farthest leaf.
Loop over each level (ending with the height)
Traverse to each level and print all the nodes on that level.

2. Find the Height of the Tree

In order to traverse over each level, we need to know how many levels there are in the tree. We'll write a method to traverse the tree and find its height.

def height(node):

You guessed it--this is going to be a recursive method, as are most binary tree traversals. Let's think of our base case. The simplest case is if we're given a null root, in which case the height is 0. You might say a node with no children is the simplest case, but then we have to check for its children, which adds to the complexity.

def height(node):
  if not node:
    return 0

What next? We have the left and right halves of the tree to traverse. So we'll call the height() method on those halves and save them to two variables, l_height and r_height.

def height(node):
  if not node:
    return 0
  l_height = height(node.left) 
  r_height = height(node.right)

Which height do we return, left or right? Why, the higher one, of course! So we'll take the max() of both values, and return that. Don't forget to add 1 for the current node.

def height(node):
  if not node:
    return 0
  l_height = height(node.left) 
  r_height = height(node.right) 

  return max(l_height, r_height) + 1

3. Loop Over Each Level

Now that we have our height, we're ready to begin writing our breadth first traversal method. The only argument it takes is the root node.

def breadth_first(root):

Next, we get our height.

def breadth_first(root):
  h = height(root)

Finally, we loop over the height of the tree. For each height, we're going to call a helper function, print_level() which takes the root node and the level.

def breadth_first(root):
  h = height(root)
  for i in range(h):
    print_level(root, i)

4. Traverse the Tree

For each level, we're going to traverse down to the nodes at that level and print them. This will be achieved through our helper function. It takes in two arguments, the root node and the current level.

def print_level(root, level):

For this method, the level initially refers to the index i from the for loop. To traverse to the tree, we're going to recursively go down each level, subtracting from i each time until we hit level 0. This means we're at our level of interest, and we can print the nodes.

Again, our base case is if the root is null. This method only prints the tree, and doesn't return anything, so we'll simply return.

def print_level(root, level):
  if not root:
    return

Next, if our level is 0, i.e. the level we're interested in, we want to print the value at that node.

def print_level(root, level):
  if not root:
    return
  if level == 0:
    print(root.value)

Finally, if our level is greater than zero, that means we have to traverse down the tree. We call our recursive method on the left and right halves of the tree. Remember to subtract 1 from level in both function calls.

def print_level(root, level):
  if not root:
    return
  if level == 0:
    print(root.value)
  elif level > 0:
    print_level(root.left, level - 1)
    print_level(root.right, level - 1)

And that's it! It took three separate methods, but we're finally able to do a breadth-first traversal of the tree.

5. Test it Out

First, make a tree using our TreeNode class.

tree = TreeNode(1)

(Image: GeeksForGeeks)

Next, populate the rest of the tree. The following is to populate for the tree in the above image.

tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)

Finally, we run our method.

breadth_first(tree)

This should print out 1, 2, 3, 4, 5. We've successfully traversed the tree!

If you have any ideas for problems or data structures you want to see covered on here, let me know in the comments! Thanks for reading.

<< #19: JS Arrays | View Solution on GitHub | #21: Mirror Tree >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Javascript Fun(ctions)! Explore the 3 Hottest Array Methods: Map, Filter, and Reduce

Whiteboarding in Python — Tue, 09 Feb 2021 03:00:01 +0000

< #18 Webcrawling | View Solution on GitHub | #20 Binary Trees II >

(Image: codeanalogies.com)

Python will always be my first love, being the first programming language I ever learned (sorry, Java, not counting you). Its versatility and built-in librarys make for a wide range of applications, including data structures and algorithms. JavaScript on the other hand, being functional instead of object-oriented, is less so-equipped. However, being the de-facto language of the internet, its applications are widespread on the front end, including high-tech frameworks like React and Vue.

You might be wondering, what kind of questions might a company ask on a JavaScript technical interview? Functions! I know, shocker, the key to functional programming is functions. So today, we'll look at three built-in array methods and try to implement them on our own. By doing so, I hope this will help you get more familiar with using these hip "callback" things that tend to pop up everywhere in JavaScript coding.

1. `.map()`

The Array.map() function can be called on an array to, simpy put, take each item and replace it (or "map" it) with something else. This is commonly used in applications like React to turn raw data, like["milk", "eggs", "butter"] into something more html-friendly, such as list items:

[
    "<li>milk</li>", 
    "<li>eggs</li>", 
    "<li>butter</li>"
]

We could achieve this by calling .map(), which takes a callback function as an argument:

let groceries = ["milk", "eggs", "butter"];
let makeList = (item) => {
    return (
        `<li>${item}</li>`
    );
}

console.log(groceries.map(makeList));

More on the map function here. So how would we build it on our own?

We'll define our homegrown map funciton as myMap, and it will take two arguments, the array arr and the callback function cb.

function myMap(arr, cb) {

}

JavaScript utility methods usually return a new object instead of altering the original one. Here, we'll make a new empty array and push items onto it.

function myMap(arr, cb) {
    newArr = [];
}

What's next? We need to loop over our array. The syntax for a simple for loop traversing an array is probably familiar to you by now.

function myMap(arr, cb) {
  newArr = [];
  for (i = 0; i < arr.length; i++) {

  }
}

Remember the function of map. We want to get the item and call the function on it to get its new value. You can call the callback function simply by putting a pair of parentheses after it and passing in arguments, which is the value at index i.

  for (i = 0; i < arr.length; i++) {
    let newValue = cb(arr[i]);

  }

Once we get that new value, we want to push it onto our new array.

  for (i = 0; i < arr.length; i++) {
    let newValue = cb(arr[i]);
    newArr.push(newValue);
  }

Finally, we return our new array (outside of the loop).

function myMap(arr, cb) {
  newArr = [];
  for (i = 0; i < arr.length; i++) {
    let newValue = cb(arr[i]);
    newArr.push(newValue);
  }
  return newArr;
}

And we're done! To try it out, we can try making our grocery list again:

console.log(myMap(groceries, makeList));
// => [ '<li>milk</li>', '<li>eggs</li>', '<li>butter</li>' ]

2. `.filter()`

The Array.filter() method takes a callback which returns a boolean, and if that boolean is false, removes that item from the array. Essentially, it filters out unimportant elements based on the function's criteria.

For example, we might want to remove even numbers from a list. We have our list, nums, and a function isOdd that returns true if the given number is odd.

let nums = [1, 2, 3, 4, 5];
let isOdd = (num) => {
  return num % 2 === 1;
}

console.log(nums.filter(isOdd));

The result should give us the array with only the odd numbers: [1, 3, 5]. I'll link the filter documentation here. Now let's write it on our own.

Start by defining the function, which takes in an array and a callback function. Again, we'll make a new array, and then write a for loop to loop through the original array.

function myFilter(arr, cb) {
    let newArr = [];
    for (let i=0; i < arr.length; i++) {

    }
}

First, we get the value at that index. Then, we call our callback function and see if it returns true.

  for (let i=0; i < arr.length; i++) {
    let value = arr[i];
    if (cb(value)) {

    }
  }

If you're new to programming, you'll notice that if statements check for truthy or falsey values, so we can simply say if (cb(value)) instead of if (cb(value) === true).

Finally, we push the value onto the new array if the callback returns true. Don't forget to return the new array at the end of your function.

function myFilter(arr, cb) {
  let newArr = [];
  for (let i=0; i < arr.length; i++) {
    let value = arr[i];
    if (cb(value)) {
      newArr.push(value);
    }
  }
  return newArr;
}

We can try out our filter method by passing it the nums array and isOdd() function from earlier.

console.log(myFilter(arr3, isOdd));
// => [ 1, 3, 5 ]

There we go! It looks like our method successfully filtered out the even values.

3. `.reduce()`

This function might be one you didn't encounter in class (at least, not for me). Essentially, it takes all the elements in an array and reduces them down to one value. For example, let's say we want to multiply together all the numbers in our array.

function mult(prev, curr) {
  return prev * curr;
}

// let nums = [1, 2, 3, 4, 5];
console.log(nums.reduce(mult));

The console should print 120, which is the product of all those numbers. You'll notice that functions used by .reduce() usually take two arguments: a previous value prev and a current value curr. This effectively chains all the values together by calling the callback function repeatedly on the previous value. We'll stick to this basic functionality for now, but if you look at the documentation, .reduce() can take a couple other arguments.

Let's try it on our own. The function will take in an array and a callback, as usual.

function myReduce(arr, cb) {

}

Instead of returning an array, we'll return a single value. Let's call it final. What should the initial value be? If we're multiplying every number together, we could perhaps start with the first one, and multiply all the others to it.

function myReduce(arr, cb) {
  let final = arr[0];

}

Next, the for loop. Since we've already accounted for the first value, we'll start our loop at index 1.

for (let i = 1; i < arr.length; i++) {

}

Then, we'll reassign final to the result of the callback function. Remember, our callback takes in a previous and current value. The previous will be the final value we have so far, and the current value is the value at index i.

  for (let i = 1; i < arr.length; i++) {
    final = cb(final, arr[i]);
  }

Finally, we can return our final value. Altogether:

function myReduce(arr, cb) {
  let final = arr[0];
  for (let i = 1; i < arr.length; i++) {
    final = cb(final, arr[i]);
  }
  return final;
}

Let's try it out. Pass in the nums array and mult function, and we should get the same number as before, 120.

console.log(myReduce(nums, mult));
// => 120

And that's it, we've explored and implemented three JavaScript array methods. I hope this helped you gain a better understanding of callback functions, enough to ace that JavaScript interview. If you're hungry for more, check out these lessons on advanced JS topics. See you next time!

< #18 Webcrawling | View Solution on GitHub | #20 Binary Trees II >

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Web Crawling in Python: Dive Into Beautiful Soup

Whiteboarding in Python — Mon, 25 Jan 2021 23:43:06 +0000

< Week 17: Knapsack | View Solution on GitHub | Week 19: JS Array Functions >

(Image: Food.com)

What is Beautiful Soup? Something your mom makes for you on a cold January day? I hope so. Beautiful Soup is a webscraping Python library, and however difficult you thought webscraping would be, Beatiful Soup makes it so much easier. For instance, I used it on one project, when I had to scrape the Genius website, since their API doesn't actually provide song lyrics (I know right? You had one job, Genius).

Let's look at a sample technical interview question:

# Crawl a webpage and print the most common word with 
# the count of that word.

# Page to crawl:
# https://en.wikipedia.org/wiki/Apple_Inc.

# Only words from the section “history” should be accounted for.

# Example of the expected result
#     # of occurrences
# The 205

We're given Apple's Wikipedia page, and we want to find the most common word in the "history" section. So let's get started.

1. Setup and Installation

First we need to import Beautiful Soup. Install from the command line via pip3 install bs4 (or however you have pip configured). Check the documentation if you're having issues with installation.

Then, let's require our library at the top of the code. Here's everything we'll need:

from bs4 import BeautifulSoup, Tag
import requests

from collections import defaultdict

Next, we're ready to define our function.

def find_most_common():

2. Get the Page

Let's get our page and parse it with Beautiful soup. To get the page, we use the requests library:

  page = requests.get("https://en.wikipedia.org/wiki/Apple_Inc.")

Next, we parse the page text using Beautiful Soup.

  soup = BeautifulSoup(page.text, "html.parser")

How do we get just the history section? We have to take a look at the HTML of the page. There's a lot of random-looking gibberish, which I've tried to clean up:

<h2>
    <span class="mw-headline" id="History">History</span>
</h2>
<div ...>...</div>
<div ...>...</div>
<h3>
    <span ...></span>
    <span class="mw-headline" id="1976–1984:_Founding_and_incorporation">1976–1984: Founding and incorporation</span>
</h3>
.
.
.
<p>Apple Computer Company was founded on April 1, 1976, by <a href="/wiki/Steve_Jobs" title="Steve Jobs">Steve Jobs</a>...

For some reason, Wikipedia seems to have all their content in one div. This means that the "history" section is not its own div, but a header and some stuff inside a parent div, which contains all the sections. To get only the history section, the best we can do for now is to just grab that header and everything after it. We grab the <span> tag with ID "History", and then go to its parent, the <h2>. To get everything after it, we can use the BeautifulSoup notation, next_siblings. Altogether:

  history = soup.find(id="History").parent.next_siblings

3. Count the Words

Let's initialize a couple variables. We'll need the most common word and the number of times it appears. We'll also use a dictionary to store the count of each word. If you've been following this blog, you've probably guessed that we'll use a default dicitonary for this (if you don't remember, we can set the dictionary's default type to integers. That way, if we access a key that doesn't exist, the default value is already 0).

  max_count = 0
  max_word = ""
  dd = defaultdict(int)

Now, we're ready to crawl. Let's loop through history and look at each element, elem. However, Beautiful Soup sometimes returns something called a "Navigable String" instead of an element. We'll filter out everything that isn't an element using the isinstance() method from our library.

  for elem in history:
    if isinstance(elem, Tag):

Let's think of what happens next. We need to look at the text for each element in history, and count the instance of each word. However, remember, we need to stop when we're no longer in the history section. The next section is the same div, but starts with an <h2> tag. Then, we can end the function by printing the most common word and its count. I'll return max_count.

  for elem in history:
    if isinstance(elem, Tag):
      if elem.name == "h2":
        print(max_word, "is the most common, appearing", max_count, "times.")
        return max_count

But what if it's not the end of the section? We need to get the text by calling the BeautifulSoup get_text() method, and then split it into words by calling split() on each space.

      words = elem.get_text().split()

What's next? Loop through each word and update its count in the dictionary. Since we're using a default dictionary, we don't have to check to see if the word is already in there before adding 1 to it. Also, don't forget to update the max_word and max_count if we find a word that's more common than what we had previously.

      for word in words:
        dd[word] += 1
        if dd[word] > max_count:
          max_count = dd[word]
          max_word = word

And that's it! The code should work...unless Wikipedia changes the layout of their site. Let's add a final check at the end in case that happens. Altogether:

from bs4 import BeautifulSoup, Tag
import requests

from collections import defaultdict

def find_most_common():
  page = requests.get("https://en.wikipedia.org/wiki/Apple_Inc.")
  soup = BeautifulSoup(page.text, "html.parser")
  history = soup.find(id="History").parent.next_siblings
  max_count = 0
  max_word = ""
  dd = defaultdict(int)

  for elem in history:
    if isinstance(elem, Tag):
      if elem.name == "h2":
        print(max_word, "is the most common, appearing", max_count, "times.")
        return max_count
      words = elem.get_text().split()
      for word in words:
        dd[word] += 1
        if dd[word] > max_count:
          max_count = dd[word]
          max_word = word

  return "Error"

Try it out

This function prints the result, so we can simply run it with find_most_common(). Running the code gives us the result:

the is the most common, appearing 328 times.

And there you have it! Granted, this function only works for this specific page, at the time of writing this--the main problem with web crawling is that it can break if the website owner alters their content in the slightest fashion. We also didn't account for casing or punctuation, something you may want to try and implement on your own. Just a few things to think about. See you next time!

< Week 17: Knapsack | View Solution on GitHub | Week 19: JS Array Functions >

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Help Pierre the Py Pirate Solve this Knapsack Problem!

Whiteboarding in Python — Thu, 14 Jan 2021 07:41:21 +0000

<< Week 16: Find Substrings | View Solution on GitHub | Week 18: Webcrawling >>

There is no love like that between a pirate and his booty. (Image: ThoughtCo)

Remember when quarantine began, and all tech companies had to go remote? The joy we had during those first months...learning new pranks on Zoom! Students from my class will remember when I changed my inactive screen name to Pierre the Py Pirate (yes, Mac, it was me). There's nothing to break up a lecture on SQL models like a sudden "Ahoy!" from Pierre in the Zoom chat. We had a lot of fun in that class.

This is a problem I think Pierre would enjoy, as a pirate going about his pirate-y business. Let's take a look:

# A thief finds much more loot than he can fit in his knapsack.

Wait! Let me re-write this in terms Pierre would understand.

# Pierre the Py Pirate has plundered new booty! But alas, he
# can only fit a limited amount in the cargo hold of his ship.
# Help him to find the most valuable combination of items 
# assuming that any fraction of a loot item can be kept.

1. Setup

Let's say, for the problem, we're given two arrays: one which has the weight of each item, and one with each value. We're also given the capacity of the cargo hold. Simple enough; let's set up the method:

def knapsack(cap, values, weights):
    pass

2. Strategy

Think about how you would approach this problem if you were Pierre. Let's say he has found a diamond ring, which weighs little but is worth much, and a sack of flour, which weighs a lot, but isn't worth so much. He'd want to keep the ring first, and then keep whatever flour can fill the rest of the space. So we'll start by sorting the items by their value-per-weight, and then add the most valuable items first until our capacity is reached.

3. Make the Sorted List of Items

We'll start by making a new items list, where we'll put the sorted list of items. Then, we'll loop over the values list (or the weights list, since they're the same length). For each item, we'll store the value-per-item as vpw, and we'll also keep the weigth (more on this later).

def knapsack(cap, values, weights):
  items = []
  for i in range(len(values)):
    itemInfo = {
      'vpw': values[i]/weights[i],
      'weight': weights[i]
    }

Next, we have to add the item to the items list. However, we can't just tack it onto the end--this is a sorted list, sorted by the vpw. So, we'll traverse the items list, checking each vpw against the current item to see where we should put it.

First, if there are no items in the list, we have nothing to check it against, so we'll just add it.

    if len(items) == 0:
      items.append(itemInfo)

Next, we traverse the list. We don't know the exact number of times we'll need to move, just so long as the vpw of our current item is less than the one in the list, we need to move closer to the end. A while loop would work great.

    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1

Okay, now our index k should be pointing where the new item should go. We can use the Python insert() method to put it there.

    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1
      items.insert(k, itemInfo)

4. Add Items from the Sorted List to the "Knapsack"

Now it's time to fill up Pierre's cargo hold. As stated earlier, we're going to go through our list of items, conveniently sorted from most value-per-weight to least, and add each one until our capacity is filled up.

Let's make some new variables. total is what we're returning, the final value of Pierre's loot. Additionally, we'll make a cap_left variable to keep track of how much capacity is remaining after each item is added.

  total = 0
  cap_left = cap

Now, we'll loop through the items.

  for item in items:

For each item, we'll first check to see if it fits. If so, we add its value to total (the value can be found by multiplying the items weight by the vpw). Don't forget to subract the weight from cap_left!

if cap_left - item['weight'] >= 0 :
  total += item['weight'] * item['vpw']
  cap_left -= item['weight']

Let's say we've added a few items, and there's still room, but not enough to add the next whole item. The prompt says we can add a fraction of an item! To do this, we'll just check to see that there's some remaining capacity, and then calculate how much to add to total. There's some math involved; essentially we multiply the item's vpw by the remaining capacity. Then, after we've added it to the total, cap_left should be set to 0.

    elif cap_left > 0:
      total += item['vpw'] * cap_left
      cap_left = 0

All that's left is to return total! Altogether:

def knapsack(cap, values, weights):
  items = []
  for i in range(len(values)):
    itemInfo = {
      'vpw': values[i]/weights[i],
      'weight': weights[i]
    }
    if len(items) == 0:
      items.append(itemInfo)
    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1
      items.insert(k, itemInfo)
  total = 0
  cap_left = cap
  for item in items:
    if cap_left - item['weight'] >= 0 :
      total += item['weight'] * item['vpw']
      cap_left -= item['weight']
    elif cap_left > 0:
      total += item['vpw'] * cap_left
      cap_left = 0
  return total

5. Try it Out

Let's say Pierre has plundered three items, a barrel of rum, a sack of flour, and a roll of silk. He has room for 60 lbs in his ship.

cap = 60
values = [60, 100, 120]
weights = [20, 50, 30]

print(knapsack(cap, values, weights))

The silk has the highest VPW at 4 gold/lb, and next is rum at 3 and flour at 2. The silk gets added first, then the rum, and finally we have 10 lbs left to fit the flour. 10 lbs of flour is valued at 20 gold, so that makes for a return total of 200 gold pieces. Yarrr!

There are many ways of solving this problem. Let me know in the comments if you think you found a better way!

<< Week 16: Find Substrings | View Solution on GitHub | Week 18: Webcrawling >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

More Python Strings: Can You Solve This More Difficult String Problem?

Whiteboarding in Python — Thu, 07 Jan 2021 04:29:04 +0000

<< Week 15: Binary Trees | View Solution on GitHub | Week 17: Knapsack >>

(Image: TurboSquid.com)

This is a problem that pops up now and again on various daily-coding-challenge platforms, like this problem on HackerRank: given a string, find all the possible combinations of letters within that string. This is sometimes called "substrings," or if a series of lists is returned, "power sets." Let's look at one example:

# Given a string, return a sorted list of all 
# unique possible substrings.

For example, the string 'abc' would yield the list ['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c'].

Let's start with defining our method. It takes in a string, which we'll call word.

def find_substrings(word):

Next, let's think about our approach. We'll need a data structure to store all our new substrings. In the end, we'll have to return a list, but remember what it said in the prompt: unique substrings. So if we have the string 'aa', we don't want to add 'a' twice. What data structure does this sound like? If the word Set comes to mind, you're right! We've covered sets on this blog previously, but to recap, it's a data structure that stores a series of unique values.

To make a new set, we simply initiate the set object in Python.

def find_substrings(word):
  s = set()

Now we reach the next phase of the implementation. How are we going to add each substring? Let's say we have the string 'abc'. We can start with the first letter, 'a', and add it to the set. Next, we want to add the letter 'b', along with 'b' concatenated to everything previously in the set, namely 'a' to make 'ab'. The two rules in each iteration are:

Add the new letter. (e.g. 'b')
Add the new letter concatented with every previous substring (e.g. 'ab')

However, we can simplify this into one rule. If we add an empty string to the set, we only need #2, since #1 is covered by adding the new letter to an empty string. Altogether, these are the substrings that would be added for each iteration:

Iteration	Set Before Addition	Letter to Add	New Subsets
0	`{ '' }`	`a`	`'a'`
1	`{ '', 'a' }`	`b`	`'b'` `'ab'`
2	`{ '', 'a', 'b', 'ab' }`	`c`	`'c'` `'ac'` `'bc'` `'abc'`

Result: `{ '', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc' }`

Let's go about implementing this in code. As we established earlier, we need to start with an empty string in our set. Let's do that.

def find_substrings(word):
  s = set()
  s.add('')

Next, we need to define our iteration. We want to look at each letter in the string. Simple enough, we use a for loop.

  for letter in word:

Okay, so for each letter in the word, we need to loop through everything in the set and add new combos with that letter. However, if we try to change the set while we're looping through it, we'll get an error. So, we'll have to make a copy of it.

  for letter in word:
    new_set = s.copy()

Remember that we have to use the Python .copy() method, or else we'll just create a reference to the original set. This way, we have an unmodified copy to refer back to.

Next, we loop through the elements in the immutable copy. For each substring, we want to add the current letter, and then push it onto the set.

  for letter in word:
    new_set = s.copy()
    for substr in new_set:
      s.add(substr + letter)

Finally, we have our substrings. We just have to do some formatting to get it how the prompt wants it. First of all, we have this extra empty string element in the set. Let's remove that.

  s.remove('')

Simple. Next, as you remember, we want to return a list, not a set. How do we cast something to a list? We iterate over each of its contents and wrap it in some square brackets, like so:

  s = [letter for letter in s]

We can just reassign it to s, since we don't need that variable for anything else. Finally, we want to sort it. Simply call the .sort() method on our list.

s.sort()

And that's it, all that's left is to return s. Altogether:

def find_substrings(word):

  s = set()

  s.add('')

  for letter in word:

    new_set = s.copy()

    for substr in new_set:

      s.add(substr + letter)

  s.remove('')

  s = [letter for letter in s]

  s.sort()

  return s

Try it Out

Call the method find_substrings() on the string 'abc', and print the result. We should get:

['a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

Longer words will also work. 'abracadabra' will give us:

['a', 'aa', 'aaa', 'aaaa', 'aaaaa', 'aaaab'...

You get the idea. The point is that 'a' only appears once, and the list is sorted alphabetically.

(Binary) Christmas Trees! Learn the Three Simplest Tree Traversals in Python

Whiteboarding in Python — Tue, 22 Dec 2020 02:14:47 +0000

<< Week 14: Random Number | View Solution on GitHub | Week 16: Find Substrings >>

Someone on r/ProgrammingJokes thought they were really clever. (Image: Reddit)

I've been meaning to cover the topic of binary trees on here for some time, so I thought, why not make it festive? Okay, I know it's not everyone's favorite topic. It's one of those old programming concepts that is hotly debated in the developer community. Since it's rare that you'd actually come across them in industry, it's contested whether or not they should still be fair game in an interview.

We won't be inverting a binary tree today (*phew*), but we'll look at a couple traversal methods, and you'll find that binary trees aren't too terribly complicated to set up.

What is a Binary Tree, Anyway?

You may remember linked lists from when we covered them in a previous article. Each list is made up of a series of nodes pointing to other nodes. But what if a node could point to more than one node? Trees are exactly that, where each parent node can have multiple children. We call it a binary tree if the max number of children is 2: a left and a right child node.

(Image: GeeksForGeeks)

In the above example, the "root", meaning the topmost node, has a value of 1, and its children are the nodes 2 and 3, and so on. Nodes 3, 4, and 5 might be referred to as "leaves" because they have no child nodes.

How would we go about building a tree in Python? It will look similar to our linked list Node class. We'll call it TreeNode.

class TreeNode:
    pass

Next, let's define the __init__() method. As always, it takes in self, and we'll also pass in the value to be stored on the node.

class TreeNode:
  def __init__(self, value):

We'll set the value of the node, and then we'll define a left and right pointer, which we'll set as None to start.

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

And...that's it! What, did you think a tree would be more complicated? For a binary tree, the only difference from a linked list is that instead of next, we have left and right.

Let's build the tree from the diagram earlier. The top node has a value of 1, and then we just keep setting its left and right nodes until we have the tree we want.

tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)

Traversing the Tree

So you've built the tree, and now you're asking, "How do I see the tree I just built?" You can't just print the whole tree in one command, but we can traverse over each node. But what in what order should we print each node?

The three easiest traversals to implement are Pre-Order, Post-Order, and In-Order. You'll also hear the terms breadth-first and depth-first search, but the implementation of these is more complicated, so we'll cover them in a future article. So what are the three listed above? Let's look at our tree again.

(Image: GeeksForGeeks)

Pre-Order visits a parent node before its children. Pre-order of the above tree would result 1, 2, 4, 5, 3.

Post-Order visits a node's children first, and then the parent. Post-order would result in 4, 5, 2, 3, 1.

In-Order visits each node from left to right. In-order traversal of the the above tree would give us 4, 2, 5, 1, 3

Let's write the traversal methods for our binary tree. Start by defining the pre_order() method, which can go outside the TreeNode class. Our method takes one argument, the highest parent, a.k.a. the root node.

def pre_order(node):
    pass

Next, we want to check that the node exists. You could argue that we could instead check if its children exist before visiting them, but we would have to write two if statements, and this way we only need to write one.

def pre_order(node):
  if node:
    pass

To write the traversal is simple. Pre-order visits the parent and then each child, so we're going to "visit" the parent by printing it, and then "traverse" to the children by calling the method recursively on each child.

# prints the parent before each child
def pre_order(node):
  if node:
    print(node.value)
    pre_order(node.left)
    pre_order(node.right)

Simple, right? You can test it out with the tree we built earlier.

pre_order(tree)

And the results:

Excellent. Next, let's do post-order. You may think that we have to write a whole new method, but actually, we just need to change one line. Instead of "visiting" the node and then "traversing" the children, we just "traverse" the children first, and then "visit" the parent node. What do I mean by this? Simply move the print statement to the last line! Remember to change the name of all your function calls to post_order().

# prints children and then parent
def post_order(node):
  if node:
    post_order(node.left)
    post_order(node.right)
    print(node.value)

Printing the result should give us the following:

Where each child node is visited before its parent.

Last, we need to write the In-Order traversal. How do you traverse the left node, and then visit the parent, and then traverse the right? Again, we just move the print statement!

# prints left child, parent, then right child
def in_order(node):
  if node:
    in_order(node.left)
    print(node.value)
    in_order(node.right)

Now if we print the tree, the nodes are printed "in order."

And there you have it, the three simplest ways to traverse a binary tree. Have a happy holiday, however you celebrate (socially distanced of course). I hope this helped you learn more about the binary trees!

<< Week 14: Random Number | View Solution on GitHub | Week 16: Find Substrings >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

More Python Practice: Find the Random Number (ft. Sets!)

Whiteboarding in Python — Thu, 17 Dec 2020 19:13:09 +0000

<< Week 13: Diving Board | View Solution on Github | Week 15: Binary Trees >>

Cloudflare in San Francisco uses lava lamps as a random number generator to encrypt requests (Source: Fast Company)

Random numbers, the spice of life. Or, at least in the coding world, they are. The Bored API uses random numbers to find an activity to alleviate your boredom, and games like Minecraft use them to spawn random terrain (check out my simple 2D Javascript Minecraft spin-off here). And there are more practical uses, like encryption at CloudFlare, which uses a wall of lava lamps as a random number generator to encrypt web requests.

So let's talk about using random numbers in Python. Here is a sample interview question.

# Given an integer n and a list of integers, 
# write a function that randomly generates a number 
# from 0 to n-1 that isn't in the list.

There are two things we'll need if we're going to generate a random integer. One is the Python random library, and we'll also need the math library to round down our random number to an integer.

import random
import math

Next, as always, we define our method. It takes in a number and a list of integers, which we'll call nums.

def get_rand(n, nums):
    pass

Solution 1: Reroll

Let's talk strategy. The first one we'll discuss is a "galaxy brain" sort of idea that perhaps first comes to mind: find a random number in the given range, and then if it's in the list, simply run the random number generator again until we find one that's valid.

We'll start by getting a random number between 0 and n. The random object has a method called random() which returns a random (decimal) number between 0 and 1. To get a numbet between 0 and n, we multiply it by n, and then we round down using math.floor()

  rand_num = math.floor(random.random() * n)

You might start by getting the random number, but there's something else we can use to make the (pretty terrible) runtime a bit better. Let's look at something used in many programming languages called a set.

Set - A data type that stores unique values in no particular order.

A visualization of the Set datatype.

I like to think of sets as a cloud: a bunch of numbers floating around, but there's no order to them. What's important is that no number appears twice. If you try to add 3 to a set, and it's already in there, it won't get added again. What's useful for us is that checking to see if the set contains a certain number takes constant O(1) time. This is better than the O(N) time we'd get if we had to loop through a list every time.

How do we implement a set in Python? Start by calling the set class with its constructor, set().

  s = set()

Next, we add the numbers from the list into the set.

for num in nums:
    s.add(num)

Now we check to see if the random number we made is in the set. If not, we want to find a new random number. This can be achieved with a while loop that runs if the random number is in the set. For fun, you can put a print statement to see how many times the method has to find a new number before it finds one that is valid.

  while rand_num in s:
    print("reroll")
    rand_num = math.floor(random.random()*n)

And finally, we return the resulting random number once the while loop has been exited. Altogether:

def get_rand(n, nums):
  rand_num = math.floor(random.random()*n)
  s = set()
  for num in nums:
    s.add(num)
  while rand_num in s:
    print("reroll")
    rand_num = math.floor(random.random()*n)
  return rand_num

If we try it out by printing get_rand(5, [0, 1, 2, 3]), we should get 4, which is the only number left that is less than 5, and that isn't in the list.

As I mentioned earlier, the runtime for this solution is not terribly efficient. Potentially, the algorithm could keep picking random numbers into eternity if it doesn't find the right one--which is exactly what happens if there are no numbers that meet the criteria. Why don't you try printing the result of get_rand(5, [0, 1, 2, 3, 4]), where the list contains all the numbers that are less than 5. Does it look like this?

reroll
reroll
reroll  
reroll
reroll
reroll
reroll
...

The algorithm keeps rerolling to eternity since there are no possible numbers to choose from. Let's think of a different solution that will both address this edge case and eliminate infinite runtime.

Solution 2: List of Possible Numbers

Sometimes, we approach these programming questions as though we're solving a math program, and we forget: we're developers. We build things. So one approach is to always ask, "Can I build the thing I need to solve this problem?"

Imagine instead of having to check each time if our random number was in the list, we already had of list of valid numbers to choose from. Then, we would just pick a random number in the list. This would also solve our edge case, because we would know that this list of possible numbers is empty, we should return None.

The first part of our method will remain the same: we take the numbers from the nums list and put them in a set. Then, we want to make an empty list that will contain all the possible numbers to choose from.

def get_rand2(n, nums):
  s = set()
  for num in nums:
    s.add(num)
  poss_nums = []

How do we find the valid numbers? We simply loop through every integer from 0 to n, and if it's not in the set, we add it to the list.

  for num in range(n):
    if num not in s:
      poss_nums.append(num)

If we were to run our call from earlier, get_rand(5, [0, 1, 2, 3]), we would get a list of poss_nums containing only the number 4.

Next, we check for our edge case. Simply check if the list is empty, and if so, return None.

  if not len(poss_nums):
    return None

What's left? To pick our random number, of course! Using the random.random() function, we multiply it by the length of the list to pick a random index, and then we'll return the number at that index.

  rand_i = math.floor(random.random()*len(poss_nums))
  return poss_nums[rand_i]

That's it! The method looks like this in total:

def get_rand2(n, nums):
  s = set()
  for num in nums:
    s.add(num)
  poss_nums = []
  for num in range(n):
    if num not in s:
      poss_nums.append(num)
  if not len(poss_nums):
    return None
  rand_i = math.floor(random.random()*len(poss_nums))
  return poss_nums[rand_i]

Now, if we try running get_rand(5, [0, 1, 2, 3, 4]) and print the result, we should get None because there are no numbers that meet the criteria. Hooray! No more infinite loops.

That's all for this week. If you like this content, please let me know in the comments what you would like to see next!

<< Week 13: Diving Board | View Solution on Github | Week 15: Binary Trees >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Dive into Python with this Diving Board Problem (ft. Recursion)!

Whiteboarding in Python — Mon, 07 Dec 2020 22:11:45 +0000

<< Week 12: Robot | View Solution on GitHub | Week 14: Random Number >>

Like a pro. (Image: Mandatory.com)

I'm going to say one word: Recursion. What is your initial reaction? Fear? Excitement? Back in my CS days at uni, they made sure to take caution introducing this subject: "It's so unintuitive!"

In all honesty, though, recursion is just another way to solve iterative problems. We got our for loops, for 10 times do X. But in recursion, X is to call the same method again. And instead of calling it 10 times, we call it until the conditions are met. What are the conditions? That's for us to determine. Let's look at this sample interview question.

# A diving board must be built to a certain length,
# made up only of the given pieces of wood

# Given a list of numbers (the lengths of wood)
# and a number k, return whether any two numbers 
# from the list add up to k.

# For example, given [10, 15, 3, 7] and k of 17, return 
# True, since 10 + 7 is 17.

First, let's take a step back and think how we might solve this iteratively. A "brute force" solution, if you will. We'll simply create a nested for loop where we check every single number against every other number in the list to see if they add to k.

Start with a method add_to_k() that takes in two parameters, our numbers list, and the sum k.

def add_to_k(numbers, k):
  pass

Our first for loop will run up through the end of the list minus 1, since by the time we get to the last element, there's nothing behind it to compare it with.

def add_to_k(numbers, k):
  for i in range(len(numbers) - 1):
    ...

We'll keep track of the first number we find and call it current. Next, we want to look at all the numbers in the list behind it. This can be achieved with the nested for loop as shown.

def add_to_k(numbers, k):
  for i in range(len(numbers) - 1):
    current = numbers[i]
    for j in range(i + 1, len(numbers)):
        ...

Finally, if the sum of the two numbers is equal to k, we return True. If we loop through the entire list without finding a match, we return False. Altogether:

def add_to_k(numbers, k):
  for i in range(len(numbers) - 1):
    current = numbers[i]
    for j in range(i + 1, len(numbers)):
      # print("checking", current, "+", numbers[j])
      if current + numbers[j] == k:
        return True
  return False

Let's try running the solution.

num_list = [10, 15, 3, 7]
k = 10

print(add_to_k(num_list, k))
# -> True

Great. This solution does the trick, but how would we go about solving it recursively?

Writing the Recursive Solution

The method will start the same, taking in the same numbers and k parameters as before.

def add_to_k_recursive(numbers, k):
  pass

Now, we need to determine our base case(s). With recursion, the best thing to ask is, "What is the simplest case?" Put on your lazy engineer hat; if you had to solve this problem looking at a bunch of different lists, which one would you want to solve? Perhaps a list that only has one item, in which case, the answer must always be false. This is our primary base case. I'm making the length less than 2, since an empty list would also fall into this category.

def add_to_k_recursive(numbers, k):
  if (len(numbers) < 2):
    return False

What's next? We have one more base case to write. If a list must be at least 2 long, the easiest case would be...if the list were only 2 long! Then we would simply add the two numbers and see if they equal k. In the case that we don't know the length of the list, let's default to checking the first and last number.

def add_to_k_recursive(numbers, k):
  if (len(numbers) < 2):
    return False
  elif numbers[0] + numbers[-1] == k:
    return True

Now all we have to do is make our recursive case, i.e., the one where we call our method again.

Let's think about it. Our list is [10, 15, 3, 7], and we're looking for numbers that sum to 10. Obviously, the length is longer than 2, so we skip the first if statement. In the elif, we see that the first and last numbers, 10 and 7, add to 17, which is not 10. So now what?

We'll have to call add_to_k_recursive() on a smaller list so that the first and last numbers are different. There are two lists we can check:

Everything but the first value.
Everything but the last value.

These are, in python:

numbers[1:]
numbers[:-1]

So, we'll call our method twice, once for each of the two smaller lists. What do we return? Remember that in Python, or will return the first True value. So, we return one method call or the other.

def add_to_k_recursive(numbers, k):
  if (len(numbers) < 2):
    return False
  elif numbers[0] + numbers[-1] == k:
    return True
  else:
    return add_to_k_recursive(numbers[:-1], k) or add_to_k_recursive(numbers[1:], k)

Testing it Out

Running the same code as before should give us the same output of True.

num_list = [10, 15, 3, 7]
k = 10

print(add_to_k_recursive(num_list, k))

However, let's look at what's going on under the hood.

We start with the list [10, 15, 3, 7]. As stated before, the first and last numbers don't add to 10. So, we call the function again on the smaller lists, [10, 15, 3] and [15, 3, 7].

Each of those lists will get broken down again, so the second list will get split into [15, 3] and [3, 7], the last one returning True. So, True gets returned up the chain of command through the initial instance of our method.

I hope this helped clear up your understanding of recursion. We didn't make the run time any better, since we still have to look at every number about two times, or O(N²) complexity. However, you might look at this solution and find it more elegant. Regardless, recursion is a good trick to have in your bag, especially if you see the words "check all possible combinations" looming in an interview question.

<< Week 12: Robot | View Solution on GitHub | Week 14: Random Number >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Robot Vacuum in Python: Bring Him Home!

Whiteboarding in Python — Wed, 02 Dec 2020 00:33:20 +0000

<< Week 11: Merge Sort | View Solution on Github | Week 13: Diving Board >>

My ride is here. (Image: Catcheckup.com)

I'm sure you remember when Roombas first came out, and how they were all the rage. Where are they now? Is our humble explorer still roaming the endless carpet of a McMansion bedroom suite that it hasn't left since 2007?

This sample interview question has to do with exactly that. Let's take a look.

# Given a string representing the sequence of moves a 
# robot vacuum makes, return whether or not it will 
# return to its original position. 
#
# The string will only contain L, R, U, and D characters, 
# representing left, right, up, and down respectively.

Does it sound complicated? Don't worry, we're going to break it down step by step.

Let's start with defining the method. It takes in one parameter, a string which we'll call direction.

def return_home(directions):
    pass

Next, you might have guessed it--some math is involved. Let's think back to primary school and the cartesian coordinate system. Our humble robot explorer starts at the origin and travels a few directions, say one foot right and two up. It would be at the position (1, 2).

How would we move it back home? We would move it two feet down in the minus Y-direction and one left, in the minus X-direction. But it doesn't matter which of those actions we take first. As long as we move -1 X and -2 Y, our humble robot explorer will return to its home at (0, 0).

So, we can keep track of the robot's X and Y coordinates, adding or subtracting 1 based on each direction we get, and if by the end of the directions string, we have an X and Y coordinate of (0, 0), the robot has returned home. Hooray!

The first thing we'll do is define those x and y coordinates. They both start at 0.

def return_home(directions):
  x = 0
  y = 0

Next, we want to iterate over each letter in the string. A for loop should work. I'm calling each letter a direction.

for direction in directions:

Now, let's make a simple if statement for each one. We've established that "R" (right) is in the positive X-direction, and "L" (left) is the negative X-direction, so we'll add or subtract 1 to x accordingly.

  for direction in directions:
    if direction == "R":
      x += 1
    elif direction == "L":
      x -= 1

The Y-direction is fairly the same, we add 1 for "U" (up), and subtract 1 for "D" (down).

  for direction in directions:
    if direction == "R":
      x += 1
    elif direction == "L":
      x -= 1
    elif direction == "U":
      y += 1
    elif direction == "D":
      y -= 1

Once we have looped through each direction in the string, we're ready to check if our robot has returned home. Simply return whether or not x and y are equal to zero. Be sure that this goes outside the for loop. Altogether:

def return_home(directions):
  x = 0
  y = 0
  for direction in directions:
    if direction == "R":
      x += 1
    elif direction == "L":
      x -= 1
    elif direction == "U":
      y += 1
    elif direction == "D":
      y -= 1
  return x == 0 and y == 0

Testing it out

Let's try the example from earlier, one right and two up.

print(return_home("RUU"))
# -> False

But, if we go two down and one left, we should get True.

print(return_home("RUULDD")
# -> True

You can try out an impressively long string of letters to see if the robot can make it back from the other side of the McMansion lawyer foyer.

print(return_home("LRULLRRDDRUDLLLURRLRULLRRDDRUDLLLURR"))
# -> True

That's it for this week, please follow the blog if you're interested in more Python practice. Also, I would like to hear from you! Let me know in the comments if there are any topics you'd like us to cover.

<< Week 11: Merge Sort | View Solution on Github | Week 13: Diving Board >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

Merge Sort: When You're Too Much of a Nerd to Use .sort()

Whiteboarding in Python — Mon, 23 Nov 2020 20:24:45 +0000

<< Week 10: Urlify | View Solution on GitHub | Week 12: Robot Vacuum >>

It's the age old question. "I have a list of things and I want to sort them. What do?"

(Image: BBC)

Well, clearly, the most intuitive answer is to take the list, divide it in half, and in half and in half until you have a bunch of lists 1 length long, and then put each pair back together in the right order, and then put the little sorted pairs together in bigger sorted pairs, and then again until you have a full list, but sorted. Is that what you were thinking?

Looks something like this. (Source: Wikipedia)

Okay, so maybe it's not the most intuitive solution, but I'll spare you the tedious hand holding of walking through inferior search algorithms like bubble sort and bogo sort (*shudder*) before explaining merge sort. What you need to know is that merge sort has a pretty good runtime compared to other algorithms, which, as you may have guessed from the whole "split in half" thing, is O(N log N).

Let's get started. Make the merge_sort(), which takes in a list. We'll call it nums for our purposes, but this same method would work for a list of any sortable types, such as strings.

def merge_sort(nums):
    pass

The first step is to divide the list in half. Use integer division to make sure we get a whole number index (in case the list is odd). Then we'll make two smaller lists, left and right, using python's handy sub-list notation. Wait, what if the list is 0 or 1 long? Then we can't split it in half. This is why we wrap our entire method in an if statement, ensuring it only operates if the list is greater than 1.

def merge_sort(nums): 
  if len(nums) >1: 
    mid = len(nums)//2
    left = nums[:mid] 
    right = nums[mid:]

What do we do next? Simple! Sort the two halves by calling merge_sort() on them.

def merge_sort(nums): 
  if len(nums) >1: 
    mid = len(nums)//2
    left = nums[:mid] 
    right = nums[mid:]
    merge_sort(left) 
    merge_sort(right)

But wait, we're not done. So far, we've split the list into halves repeatedly until we have a bunch of little lists length one. For example, if we had the list [4, 2, 1, 3], it would get split into [4, 2] and [1, 3], and then into [4], [2], [1], and [3], lists each of length 1.

What's next? I'll give you a hint, it's in the name of the method...rhymes with blurge....right! We merge the halves together.

Things get a little tricky here. We need to keep track of a few indices, which we'll call i, j, and k. Here is what they represent:

i is an index in the left list.
j is an index in the right list.
k is the index in the original list, nums where we want to put each number when we're done.

To start, we'll make all of them zero.

i = j = k = 0

Next, we're going to traverse both the left and right lists, comparing each item. We only need to go through once because left and right are already sorted. We just need to merge them.

If the number in left is smaller, we put it back in nums at spot k, and advance our left index j. If the number in right is smaller (or equal), we put it in nums instead, and advance our right index, j. Finally, we advance k now that we have added a new number to nums.

while i < len(left) and j < len(right): 
    if left[i] < right[j]: 
        nums[k] = left[i] 
        i+=1
    else: 
        nums[k] = right[j] 
        j+=1
    k+=1

There's one more thing we need to do. We said while i < len(left) and j < len(right), meaning as soon as one of those conditions is met, the loop will break. So let's say we reached the end of left, but we still have more indices to go in right? We just have to make another while loop that accounts for this, looping through the rest of right and adding its numbers into the nums list. We do the same for any numbers left in left (ha, left, get it? I'll stop now).

while j < len(right): 
    nums[k] = right[j] 
    j+=1
    k+=1

while i < len(left): 
    nums[k] = left[i] 
    i+=1
    k+=1

That's it! To recap the merge, we started with [4], [2], [1], and [3]. These get merged to [2, 4] and [1, 3], and then finally they come together to make [1, 2, 3, 4].

Here is the full code. Notice that the bulk of the method lies within that first if statement.

def merge_sort(nums): 
  if len(nums) > 1: 
    mid = len(nums)//2
    left = nums[:mid] 
    right = nums[mid:]
    merge_sort(left) 
    merge_sort(right) 

    i = j = k = 0

    while i < len(left) and j < len(right): 
        if left[i] < right[j]: 
            nums[k] = left[i] 
            i+=1
        else: 
            nums[k] = right[j] 
            j+=1
        k+=1

    while i < len(left): 
        nums[k] = left[i] 
        i+=1
        k+=1

    while j < len(right): 
        nums[k] = right[j] 
        j+=1
        k+=1

Testing it out

Let's sort some numbers. Make a list of numbers, and call merge_sort() on them. Notice how we print the result after the method call, since it alters the original list nums instead of returning anything.

nums = [5, 2, 3, 6, 84, 9, 8]
merge_sort(nums)
print(nums)

This should give you the sorted list, [2, 3, 5, 6, 8, 9, 84]. As mentioned before, this will also work with strings. Giving the list ['banana', 'apple', 'grape', 'orange'] will sort alphabetically to ['apple', 'banana', 'grape', 'orange'].

I hope this gave you some clarity on how merge sort works. Python's .sort() method is similar to merge sort and is another "divide and conquer" algorithm, and has about the same time complexity. So, there's not really a reason you would have to implement merge sort...unless you're asked to do so on an technical interview. I hope this helped to prepare you for that!

<< Week 10: Urlify | View Solution on GitHub | Week 12: Robot Vacuum >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly. This blog is not associated with GA.

DEV Community: Whiteboarding in Python

Sum of Three, Sum of Four, and Beyond? In Python!

1. Approach

2. Setup

3. Iteration

4. Wrapping up Sum of Three

5. Step Up Complexity: Sum of Four

6. Sum of Five...and Beyond?

7. Iteration in the Recursive Method

Binary Tree Practice in Python: Mirror Tree

1. Strategy

2. Setup

3. Traversal

4. Test it Out

More Python Binary Trees: What is Breadth vs Depth First Search?

What's the difference?

Implementing Breadth First Search in Python

1. Strategy

2. Find the Height of the Tree

3. Loop Over Each Level

4. Traverse the Tree

5. Test it Out

Javascript Fun(ctions)! Explore the 3 Hottest Array Methods: Map, Filter, and Reduce

1. .map()

2. .filter()

3. .reduce()

Web Crawling in Python: Dive Into Beautiful Soup

1. Setup and Installation

2. Get the Page

3. Count the Words

Try it out

Help Pierre the Py Pirate Solve this Knapsack Problem!

1. Setup

2. Strategy

3. Make the Sorted List of Items

4. Add Items from the Sorted List to the "Knapsack"

5. Try it Out

More Python Strings: Can You Solve This *More* Difficult String Problem?

Result: { '', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc' }

Try it Out

Further Reading: Optimization

(Binary) Christmas Trees! Learn the Three Simplest Tree Traversals in Python

What is a Binary Tree, Anyway?

Traversing the Tree

More Python Practice: Find the Random Number (ft. Sets!)

Solution 1: Reroll

Solution 2: List of Possible Numbers

Dive into Python with this Diving Board Problem (ft. Recursion)!

Writing the Recursive Solution

Testing it Out

Robot Vacuum in Python: Bring Him Home!

Testing it out

Merge Sort: When You're Too Much of a Nerd to Use .sort()

Testing it out

1. `.map()`

2. `.filter()`

3. `.reduce()`

More Python Strings: Can You Solve This More Difficult String Problem?

Result: `{ '', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc' }`