Interview Cake Course

Glossary

Asymptotic analysis (Big O)

Asymptotic analysis expresses runtime and space time in terms of how quickly they grow relative to the input as the input grows arbitrarily large.

• how quickly they grow…
  • Exact runtime can only be measured by benchmarking. Many factors of an actual computer implementation govern this result (cache, CPU instructions, CPU speed, etc.)
• …relative to the input…
  • Instead of measuring in seconds, we use the size of the input. The input can be just a number or the size of the input object.
• …as the input grows arbitrarily large
  • The algorithm may have distinct steps that have different runtimes. The overall runtime may have multiple terms, but the only term that matters is the one that grows the fastest as the input increases.

Develop a habit of thinking about asymptotic performance while you code, both in time and space. Use it as a tool to identify places for optimization. Constants may not matter in big O notation, but they can be important in practice. If you can make an algorithm run even 2x faster on average, that is 2x more work you can do.

Develop the skill to see time and space optimizations, as well as the wisdom to judge if those optimizations are worthwhile. Balance performance, maintainability, and readability.

Data Structures

Logarithms

Arrays

Readings

Merging meeting times

Write a function merge_ranges() that takes a list of multiple meeting time ranges and returns a list of condensed ranges.

For example, given:

[(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]

your function would return:

[(0, 1), (3, 8), (9, 12)]

Do not assume the meetings are in order. The meeting times are coming from multiple teams.

Write a solution that’s efficient even when we can’t put a nice upper bound on the numbers representing our time ranges. Here we’ve simplified our times down to the number of 30-minute slots past 9:00 am. But we want the function to work even for very large numbers, like Unix timestamps. In any case, the spirit of the challenge is to merge meetings where start_time and end_time don’t have an upper bound.

My Solution:

from collections import namedtuple

Meeting = namedtuple('Meeting', ['start', 'finish'])

def merge_ranges(meetings):

    # Merge meeting ranges
    if len(meetings) <= 1:
        return meetings

    meetings.sort()

    merged = [Meeting(*meetings[0])]
    for meet in meetings:
        meet = Meeting(*meet)
        if meet.start <= merged[-1].finish:
            finish = meet.finish
            if merged[-1].finish >= meet.finish:
                finish = merged[-1].finish

            merged[-1] = Meeting(merged[-1].start, finish)
        else:
            merged.append(meet)

    return merged

Book solution:

First, we sort our input list of meetings by start time so any meetings that might need to be merged are now next to each other.

Then we walk through our sorted meetings from left to right. At each step, either:

1. We can merge the current meeting with the previous one, so we do.
2. We can’t merge the current meeting with the previous one, so we know the previous meeting can’t be merged with any future meetings and we throw the current meeting into merged_meetings.

def merge_ranges(meetings):

  # Sort by start time
  sorted_meetings = sorted(meetings)

  # Initialize merged_meetings with the earliest meeting
  merged_meetings = [sorted_meetings[0]]

  for current_meeting_start, current_meeting_end in sorted_meetings[1:]:
      last_merged_meeting_start, last_merged_meeting_end = merged_meetings[-1]

      # If the current meeting overlaps with the last merged meeting, use the
      # later end time of the two
      if (current_meeting_start <= last_merged_meeting_end):
          merged_meetings[-1] = (last_merged_meeting_start,
                                  max(last_merged_meeting_end,
                                      current_meeting_end))
      else:
          # Add the current meeting since it doesn't overlap
          merged_meetings.append((current_meeting_start, current_meeting_end))

  return merged_meetings

Complexity: O(nlgn) time and O(n) space.

Even though we only walk through our list of meetings once to merge them, we sort all the meetings first, giving us a runtime of O(nlgn). It’s worth noting that if our input were sorted, we could skip the sort and do this in O(n) time!

We create a new list of merged meeting times. In the worst case, none of the meetings overlap, giving us a list identical to the input list. Thus we have a worst-case space cost of O(n).

Bonus:

1. What if we did have an upper bound on the input values? Could we improve our runtime? Would it cost us memory?
2. Could we do this “in place” on the input list and save some space? What are the pros and cons of doing this in place?

What We Learned:

This one arguably uses a greedy approach as well, except this time we had to sort the list first.

How did we figure that out?

We started off trying to solve the problem in one pass, and we noticed that it wouldn’t work. We then noticed the reason it wouldn’t work: to see if a given meeting can be merged, we have to look at all the other meetings! That’s because the order of the meetings is random.

That’s what got us thinking: what if the list were sorted? We saw that then a greedy approach would work. We had to spend O(nlgn) time on sorting the list, but it was better than our initial brute force approach, which cost us O(n^2) time!

Reverse string in-place

Write a function that takes a list of characters and reverses the letters in place.

Why a list of characters instead of a string?

The goal of this question is to practice manipulating strings in place. Since we’re modifying the input, we need a mutable type like a list, instead of Python 3.6’s immutable strings.

My solution:

def reverse(list_of_chars):
    chars = list_of_chars
    half = len(chars) // 2
    for i in range(half):
        right = - (i + 1)
        chars[i], chars[right] = chars[right], chars[i]

Solution:

In general, an in-place algorithm will require swapping elements.

We swap the first and last characters, then the second and second-to-last characters, and so on until we reach the middle.

def reverse(list_of_chars):

  left_index  = 0
  right_index = len(list_of_chars) - 1

  while left_index < right_index:
      # Swap characters
      list_of_chars[left_index], list_of_chars[right_index] = \
          list_of_chars[right_index], list_of_chars[left_index]
      # Move towards middle
      left_index  += 1
      right_index -= 1

Complexity: O(n) time and O(1) space.

Reverse words

Your team is scrambling to decipher a recent message, worried it’s a plot to break into a major European National Cake Vault. The message has been mostly deciphered, but all the words are backward! Your colleagues have handed off the last step to you.

Write a function reverse_words() that takes a message as a list of characters and reverses the order of the words in place.

For example:

message = [ 'c', 'a', 'k', 'e', ' ',
            'p', 'o', 'u', 'n', 'd', ' ',
            's', 't', 'e', 'a', 'l' ]

reverse_words(message)

# Prints: 'steal pound cake'
print(''.join(message))

When writing your function, assume the message contains only letters and spaces, and all words are separated by one space.

My solution (doesn’t work):

Although I had the right idea, this doesn’t work. I’m not quite sure why this doesn’t work, but I assume it’s because slicing copies data. I would’ve thought that assigning the slice would overwrite, but I guess not. I’ll have to investigate.

def reverse_words(message):
    message = message[::-1]
    msg = message
    i, n = 0, len(msg)

    while i < n:
        space = find(' ', msg, i)
        space_not_found = space == -1
        if space_not_found:
            break

        msg[i:space] = msg[i:space:-1]
        i = space + 1

    msg[i:n] = msg[i:n:-1]


def find(ch, arr, start=0):
    for i, item in enumerate(arr[start:], start=start):
        if item == ch:
            return i
    return -1

Solution:

We’ll write a helper function reverse_characters() that reverses all the characters between a left_index and right_index. We use it to:

1. Reverse all the characters in the entire message, giving us the correct word order but with each word backward.
2. Reverse the characters in each individual word.

def reverse_words(message):
  # First we reverse all the characters in the entire message
  reverse_characters(message, 0, len(message)-1)

  # This gives us the right word order
  # but with each word backward

  # Now we'll make the words forward again
  # by reversing each word's characters

  # We hold the index of the *start* of the current word
  # as we look for the *end* of the current word
  current_word_start_index = 0

  for i in range(len(message) + 1):
      # Found the end of the current word!
      if (i == len(message)) or (message[i] == ' '):
          reverse_characters(message, current_word_start_index, i - 1)
          # If we haven't exhausted the message our
          # next word's start is one character ahead
          current_word_start_index = i + 1


def reverse_characters(message, left_index, right_index):
    # Walk towards the middle, from both sides
    while left_index < right_index:
        # Swap the left char and right char
        message[left_index], message[right_index] = \
            message[right_index], message[left_index]
        left_index  += 1
        right_index -= 1

Complexity: O(n) time and O(1) space!

Bonus: How would you handle punctuation?

What We Learned:

The naive solution of reversing the words one at a time had a worst-case O(n^2) runtime. That’s because swapping words with different lengths required “scooting over” all the other characters to make room.

To get around this “scooting over” issue, we reversed all the characters in the message first. This put all the words in the correct spots, but with the characters in each word backward. So to get the final answer, we reversed the characters in each word. This all takes two passes through the message, so O(n) time total.

This might seem like a blind insight, but we derived it by using a clear strategy:

Solve a simpler version of the problem (in this case, reversing the characters instead of the words), and see if that gets us closer to a solution for the original problem.

We talk about this strategy in the “get unstuck” section of our coding interview tips.

Merge sorted arrays

Python has heapq.merge() that will merge multiple, sorted iterables into a single sorted iterator over all values.

def merge_lists(my_list, alices_list):
    i = j = 0
    left, right = my_list, alices_list
    nl, nr = len(left), len(right)
    result = []
    while i < nl and j < nr:
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        elif left[i] == right[j]:
            result.append(left[i])
            result.append(right[j])
            i += 1
            j += 1
        else:
            result.append(right[j])
            j += 1
    longer = left[i:] or right[j:]
    result += longer

    return result

Hashing and hash tables

Inflight entertainment

Users on longer flights like to start a second movie right when their first one ends, but they complain that the plane usually lands before they can see the ending. So you’re building a feature for choosing two movies whose total runtimes will equal the exact flight length.

Write a function that takes an integer flight_length (in minutes) and a list of integers movie_lengths (in minutes) and returns a boolean indicating whether there are two numbers in movie_lengths whose sum equals flight_length.

When building your function:

• Assume your users will watch exactly two movies
• Don’t make your users watch the same movie twice
• Optimize for runtime over memory

My Solution:

def can_two_movies_fill_flight(movie_lengths, flight_length):
    movie_ix = {length: ix for ix, length in enumerate(movie_lengths)}

    for i, length in enumerate(movie_lengths):
        complement = flight_length - length
        if complement not in movie_ix:
            continue

        ix = movie_ix[complement]
        if i != ix:
            return True
    return False

Solution:

We make one pass through movie_lengths, treating each item as the first_movie_length. At each iteration, we:

1. See if there’s a matching_second_movie_length we’ve seen already (stored in our movie_lengths_seen set) that is equal to flight_length - first_movie_length. If there is, we short-circuit and return True.
2. Keep our movie_lengths_seen set up to date by throwing in the current first_movie_length.

def can_two_movies_fill_flight(movie_lengths, flight_length):
# Movie lengths we've seen so far
movie_lengths_seen = set()

for first_movie_length in movie_lengths:
    matching_second_movie_length = flight_length - first_movie_length
    if matching_second_movie_length in movie_lengths_seen:
        return True
    movie_lengths_seen.add(first_movie_length)

# We never found a match, so return False
return False

We know users won’t watch the same movie twice because we check movie_lengths_seen for matching_second_movie_length before we’ve put first_movie_length in it!

Complexity: O(n) time, and O(n) space. Note while optimizing runtime we added a bit of space cost.

Bonus:

• What if we wanted the movie lengths to sum to something close to the flight length (say, within 20 minutes)?
• What if we wanted to fill the flight length as nicely as possible with any number of movies (not just 2)?
• What if we knew that movie_lengths was sorted? Could we save some space and/or time?

What We Learned:

The trick was to use a set to access our movies by length, in O(1) time.

Using hash-based data structures, like dictionaries or sets, is so common in coding challenge solutions, it should always be your first thought. Always ask yourself, right from the start: “Can I save time by using a dictionary?”

Permutation palindrome

Write an efficient function that checks whether any permutation of an input string is a palindrome.

You can assume the input string only contains lowercase letters.

Examples:

“civic” should return True “ivicc” should return True “civil” should return False “livci” should return False

“But ‘ivicc’ isn’t a palindrome!”

If you had this thought, read the question again carefully. We’re asking if any permutation of the string is a palindrome. Spend some extra time ensuring you fully understand the question before starting. Jumping in with a flawed understanding of the problem doesn’t look good in an interview.

My solution:

def has_palindrome_permutation(the_string):
    counts = Counter(the_string)
    seen_odd = False
    for ch, count in counts.items():
        is_odd = count % 2
        if is_odd and seen_odd:
            return False
        elif is_odd and not seen_odd:
            seen_odd = True

    return True

Solution:

The brute force solution would generate all permutations of the input string and check each one if it’s a palindrome. This leads to an O(n! * n) runtime.

After looking at palindromes, another definition could be that if at most one character has an odd number of counts, it is a palindrome. We could count all characters and then run through all counts to see if only one character has an odd count.

However, notice that we only need to keep track of whether character has an odd or even count, not the actual count. We can use a set to keep track of characters that have an odd count. If the character is not in the set, this means the count is even. If the character is in the set, the count is odd.

def has_palindrome_permutation(the_string):
    odd_counts = set()
    for ch in the_string:
        if ch in odd_counts:
            odd_counts.remove(ch)
        else:
            odd_counts.add(ch)

    return len(odd_counts) <= 1

Complexity:

O(n) time, since we’re making one iteration through the nn characters in the string.

Our unpaired_characters set is the only thing taking up non-constant space. We could say our space cost is O(n) as well, since the set of unique characters is less than or equal to nn. But we can also look at it this way: there are only so many different characters. How many? The ASCII character set has just 128 different characters (standard english letters and punctuation), while Unicode has 110,000 (supporting several languages and some icons/symbols). We might want to treat our number of possible characters in our character set as another variable kk and say our space complexity is O(k). Or we might want to just treat it as a constant, and say our space complexity is O(1).

What We Learned:

One of the tricks was to use a dictionary or set.

This is the most common way to get from a brute force approach to something more efficient. Especially for easier problems.

I even know interviewers who just want to hear you say “dictionary”, and once they hear that they’ll say, “Great, let’s move on.”

So always ask yourself, right from the start: “Can I save time by using a dictionary?”

Want more examples of dictionaries unlocking the optimal answer for a coding interview question? Check out these other questions.

Greedy algorithms

Choose the best option at each step. Keep in mind this picks the locally best option, not the globally best option.

Types of problems:

• Some coin counting problems
  • US coinage
  • not all denominations will produce a globally optimal solution
• Scheduling as many overlapping meetings as possible
  • choose the meeting that ends the earliest
• minimum spanning tree
  • pick the cheapest route to a new vertex

Proving that a greedy algorithm produces a globally optimal answer is usually tough. Try to prove that each step always produces the most optimal answer or create a test suite that tries to cover as many cases as possible.

Apple stocks

Write an efficient function that takes stock_prices and returns the best profit I could have made from one purchase and one sale of one share of Apple stock yesterday.

For example:

stock_prices = [10, 7, 5, 8, 11, 9]

get_max_profit(stock_prices)
# Returns 6 (buying for $5 and selling for $11)

No “shorting”—you need to buy before you can sell. Also, you can’t buy and sell in the same time step—at least 1 minute has to pass.

Solution:

We’ll greedily walk through the list to track the max profit and lowest price so far.

For every price, we check if:

• we can get a better profit by buying at min_price and selling at the current_price
• we have a new min_price

To start, we initialize:

• min_price as the first price of the day
• max_profit as the first profit we could get

We decided to return a negative profit if the price decreases all day and we can’t make any money. We could have raised an exception instead, but returning the negative profit is cleaner, makes our function less opinionated, and ensures we don’t lose information.

def get_max_profit(stock_prices):
  n = len(stock_prices)
  if n < 2:
      raise ValueError

  min_price = stock_prices[0]
  max_profit = stock_prices[1] - stock_prices[0]
  for ix in range(1, n):
      curr_price = stock_prices[ix]
      profit = curr_price - min_price
      max_profit = max(max_profit, profit)
      min_price = min(min_price, curr_price)

  return max_profit

Complexity: O(n) time and O(1) space. We only loop through the list once.

What We Learned:

This one’s a good example of the greedy approach in action. Greedy approaches are great because they’re fast (usually just one pass through the input). But they don’t work for every problem.

How do you know if a problem will lend itself to a greedy approach? Best bet is to try it out and see if it works. Trying out a greedy approach should be one of the first ways you try to break down a new question.

To try it on a new problem, start by asking yourself:

“Suppose we could come up with the answer in one pass through the input, by simply updating the ‘best answer so far’ as we went. What additional values would we need to keep updated as we looked at each item in our input, in order to be able to update the ‘best answer so far’ in constant time?”

In this case:

The “best answer so far” is, of course, the max profit that we can get based on the prices we’ve seen so far.

The “additional value” is the minimum price we’ve seen so far. If we keep that updated, we can use it to calculate the new max profit so far in constant time.

The max profit is the larger of:

• The previous max profit
• The max profit we can get by selling now (the current price minus the minimum price seen so far)

Try applying this greedy methodology to future questions.

Highest product of 3

Given a list of integers, find the highest product you can get from three of the integers.

The input list_of_ints will always have at least three integers.

My Solution:

from functools import reduce
from operator import mul

def highest_product_of_3(list_of_ints):
    # Complexity is O(n lg n) time and O(1) space.  The inner loop does a
    # constant amount of work for each iteration of the outer loop.

    n = len(list_of_ints)
    if n < 3:
        raise ValueError

    list_of_ints.sort()

    threes = list_of_ints[:3]
    max_product = reduce(mul, threes)
    for i in range(3, n):
        tmp = list_of_ints[i]
        maybe_threes = threes[:]
        for i in range(3):
            tmp, maybe_threes[i] = maybe_threes[i], tmp
            new_product = reduce(mul, maybe_threes)
            if new_product > max_product:
                max_product = new_product
                threes = maybe_threes[:]
            tmp, maybe_threes[i] = maybe_threes[i], tmp

    return max_product

Solution:

We use a greedy approach to solve the problem in one pass. At each iteration we keep track of:

• highest_product_of_3
• highest_product_of_2
• highest
• lowest_product_of_2
• lowest

When we reach the end, the highest_product_of_3 is our answer. We maintain the others because they’re necessary for keeping the highest_product_of_3 up to date as we walk through the list. At each iteration, the highest_product_of_3 is the highest of:

1. the current highest_product_of_3
2. current * highest_product_of_2
3. current * lowest_product_of_2 (if current and lowest_product_of_2 are both low negative numbers, this product is a high positive number).

def highest_product_of_3(list_of_ints):
    # Complexity is O(n) time and O(1) space.

    if len(list_of_ints) < 3:
        raise ValueError('Less than 3 items!')

    # We're going to start at the 3rd item (at index 2)
    # so pre-populate highests and lowests based on the first 2 items.
    # We could also start these as None and check below if they're set
    # but this is arguably cleaner
    highest = max(list_of_ints[0], list_of_ints[1])
    lowest  = min(list_of_ints[0], list_of_ints[1])
    highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
    lowest_product_of_2  = list_of_ints[0] * list_of_ints[1]

    # Except this one--we pre-populate it for the first *3* items.
    # This means in our first pass it'll check against itself, which is fine.
    highest_product_of_3 = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]

    # Walk through items, starting at index 2
    for i in range(2, len(list_of_ints)):
        current = list_of_ints[i]

        # Do we have a new highest product of 3?
        # It's either the current highest,
        # or the current times the highest product of two
        # or the current times the lowest product of two
        highest_product_of_3 = max(highest_product_of_3,
                                   current * highest_product_of_2,
                                   current * lowest_product_of_2)

        # Do we have a new highest product of two?
        highest_product_of_2 = max(highest_product_of_2,
                                   current * highest,
                                   current * lowest)

        # Do we have a new lowest product of two?
        lowest_product_of_2 = min(lowest_product_of_2,
                                  current * highest,
                                  current * lowest)

        # Do we have a new highest?
        highest = max(highest, current)

        # Do we have a new lowest?
        lowest = min(lowest, current)

    return highest_product_of_3

Bonus:

• What if we wanted the highest product of 4 items?
• What if we wanted the highest product of kk items?
• If our highest product is really big, it could overflow. ↴ How should we protect against this?

What We Learned:

Greedy algorithms in action again!

That’s not a coincidence—to illustrate how one pattern can be used to break down several different questions, we’re showing this one pattern in action on several different questions.

Usually it takes seeing an algorithmic idea from a few different angles for it to really make intuitive sense.

Our goal here is to teach you the right way of thinking to be able to break down problems you haven’t seen before. Greedy algorithm design is a big part of that way of thinking.

For this one, we built up our greedy algorithm exactly the same way we did for the Apple stocks question. By asking ourselves:

“Suppose we could come up with the answer in one pass through the input, by simply updating the ‘best answer so far’ as we went. What additional values would we need to keep updated as we looked at each item in our set, in order to be able to update the ‘best answer so far’ in constant time?”

For the Apple stocks question, the only “additional value” we needed was the min price so far.

For this one, we needed four things in order to calculate the new highest_product_of_3 at each step:

• highest_product_of_2
• highest
• lowest_product_of_2
• lowest

Product of other numbers

You have a list of integers, and for each index you want to find the product of every integer except the integer at that index.

Write a function get_products_of_all_ints_except_at_index() that takes a list of integers and returns a list of the products.

For example, given:

[1, 7, 3, 4]

your function would return:

[84, 12, 28, 21]

by calculating:

[7 * 3 * 4,  1 * 3 * 4,  1 * 7 * 4,  1 * 7 * 3]

Here’s the catch: You can’t use division in your solution!

My solution:

def get_products_of_all_ints_except_at_index(int_list):
    n = len(int_list)
    if n < 2:
        raise ValueError

    products = []
    partial_product = 1
    for num in int_list:
        products.append(partial_product)
        partial_product *= num

    partial_product = 1
    for i in reversed(range(n)):
        products[i] *= partial_product
        partial_product *= int_list[i]

    return products

Solution:

To find the products of all the integers except the integer at each index, we’ll go through our list greedily twice. First, we get the products of all the integers before each index, and then we go backwards to get the products of all the integers after each index.

When we multiply all the products before and after each index, we get our answer—the products of all the integers except the integer at each index!

def get_products_of_all_ints_except_at_index(int_list):
    # O(n) time and O(n)O(n) space. We make two passes through our input a
    # list, and the list we build always has the same length as the input list.

    if len(int_list) < 2:
        raise IndexError('Getting the product of numbers at other '
                         'indices requires at least 2 numbers')

    # We make a list with the length of the input list to
    # hold our products
    products_of_all_ints_except_at_index = [None] * len(int_list)

    # For each integer, we find the product of all the integers
    # before it, storing the total product so far each time
    product_so_far = 1
    for i in range(len(int_list)):
        products_of_all_ints_except_at_index[i] = product_so_far
        product_so_far *= int_list[i]

    # For each integer, we find the product of all the integers
    # after it. since each index in products already has the
    # product of all the integers before it, now we're storing
    # the total product of all other integers
    product_so_far = 1
    for i in range(len(int_list) - 1, -1, -1):
        products_of_all_ints_except_at_index[i] *= product_so_far
        product_so_far *= int_list[i]

    return products_of_all_ints_except_at_index

Bonus:

What if you could use division? Careful—watch out for zeroes!

What We Learned:

Another question using a greedy approach. The tricky thing about this one: we couldn’t actually solve it in one pass. But we could solve it in two passes!

This approach probably wouldn’t have been obvious if we had started off trying to use a greedy approach.

Instead, we started off by coming up with a slow (but correct) brute force solution and trying to improve from there. We looked at what our solution actually calculated, step by step, and found some repeat work. Our final answer came from brainstorming ways to avoid doing that repeat work.

So that’s a pattern that can be applied to other problems:

Start with a brute force solution, look for repeat work in that solution, and modify it to only do that work once.

In-place shuffle

Write a function for doing an in-place shuffle of a list.

The shuffle must be “uniform,” meaning each item in the original list must have the same probability of ending up in each spot in the final list.

Assume that you have a function get_random(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.

My Solution:

import random
def get_random(floor, ceiling):
    return random.randrange(floor, ceiling + 1)

def shuffle(the_list):
    # O(n) time and O(1) space
    n = len(the_list)
    for i in range(n):
        other = get_random(i, n-1)
        the_list[i], the_list[other] = the_list[other], the_list[i]

Solution:

The key insight is that once a value has been chosen at random, it can no longer be used in the shuffle. This is called the Fisher-Yates shuffle or Knuth shuffle.

It’s easy to over-count some permutations. Consider an example with three values. If we’d left all values in the shuffle for each position in the array, we would get 3*3*3=3^3=27 possibilities.

But there are only 3*2*1=3!=6 unique permutations. The over-counting would be ok if the two counts were evenly divisible. However, since 27%6 != 0, some permutations will have a higher chance of being picked. Therefore, the shuffle wouldn’t have a uniform distribution.

import random
def get_random(floor, ceiling):
    return random.randrange(floor, ceiling + 1)

def shuffle(the_list):
    # If it's 1 or 0 items, just return
    if len(the_list) <= 1:
        return the_list

    last_index_in_the_list = len(the_list) - 1

    # Walk through from beginning to end
    for index_we_are_choosing_for in range(0, len(the_list) - 1):

        # Choose a random not-yet-placed item to place there
        # (could also be the item currently in that spot)
        # Must be an item AFTER the current item, because the stuff
        # before has all already been placed
        random_choice_index = get_random(index_we_are_choosing_for,
                                         last_index_in_the_list)

        # Place our random choice in the spot by swapping
        if random_choice_index != index_we_are_choosing_for:
            the_list[index_we_are_choosing_for],
            the_list[random_choice_index] = (
                the_list[random_choice_index],
                the_list[index_we_are_choosing_for])

Binary search

def binary_search(arr, x):
    # arr must be sorted. O(lg(n)) time and O(1) space.
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        elif arr[mid] == x:
            return mid
        else:
            hi = mid - 1
    return -1

Find rotation point

I opened up a dictionary to a page in the middle and started flipping through, looking for words I didn’t know. I put each word I didn’t know at increasing indices in a huge list I created in memory. When I reached the end of the dictionary, I started from the beginning and did the same thing until I reached the page I started at.

Now I have a list of words that are mostly alphabetical, except they start somewhere in the middle of the alphabet, reach the end, and then start from the beginning of the alphabet. In other words, this is an alphabetically ordered list that has been “rotated.”

Write a function for finding the index of the “rotation point,” which is where I started working from the beginning of the dictionary. This list is huge (there are lots of words I don’t know) so we want to be efficient here.

To keep things simple, you can assume all words are lowercase.

My solution:

It’s messy and hard to explain.

def find_rotation_point(words):
    lo, hi = 0, len(words) - 1
    mid = lo + (hi - lo) // 2
    while not (words[lo] <= words[mid] <= words[hi]):
        if words[lo] == words[mid]:
            lo = mid + 1
        else:
            lo = mid

        mid = lo + (hi - lo) // 2

    return lo

Solution:

The list is mostly ordered. We should exploit that fact.

The rotation point is to our left if the current item is less than the first item. Else it’s to our right.

This is a modified version of binary search. At each iteration, we go right if the item we’re looking at is greater than the first item and we go left if the item we’re looking at is less than the first item.

We keep track of the lower and upper bounds on the rotation point, calling them lo and hi (initially we called them “floor” and “ceiling,” but because we didn’t imply the type in the name we got confused and created bugs). When lo and hi are directly next to each other, we know the floor is the last item we added before starting from the beginning of the dictionary, and the ceiling is the first item we added after.

def find_rotation_point(words):
    first_word = words[0]
    lo, hi = 0, len(words) - 1
    while lo < hi:
        guess_index = lo + (hi - lo) // 2

        # If guess comes after first word or is the first word
        if words[guess_index] >= first_word:
            # Go right
            lo = guess_index
        else:
            # Go left
            hi = guess_index

        # If floor and ceiling have converged
        if lo + 1 == hi:
            # Between floor and ceiling is where we flipped to the beginning
            # so ceiling is alphabetically first
            return hi

Complexity:

Each time we go through the while loop, we cut our range of indices in half, just like binary search. So we have O(lg(n)) loop iterations.

In each loop iteration, we do some arithmetic and a string comparison. The arithmetic is constant time, but the string comparison requires looking at characters in both words—every character in the worst case. Here, we’ll assume our word lengths are bounded by some constant so we’ll say the string comparison takes constant time.

The longest word in English is pneumonoultramicroscopicsilicovolcanoconiosis, a medical term. It’s 45 letters long.

Putting everything together, we do O(lg(n)) iterations, and each iteration is O(1) time. So our time complexity is O(lg(n)).

Some languages—like German, Russian, and Dutch—can have arbitrarily long words, so we might want to factor the length of the words into our runtime. We could say the length of the words is ℓ, each string comparison takes O(ℓ) time, and the whole algorithm takes O(ℓ∗lg(n)) time.

We use O(1) space to store the first word and the floor and ceiling indices.

Bonus:

This function assumes that the list is rotated. If it isn’t, what index will it return? How can we fix our function to return 0 for an unrotated list?

What We Learned:

The answer was a modified version of binary search.

This is a great example of the difference between “knowing” something and knowing something. You might have seen binary search before, but that doesn’t help you much unless you’ve learned the lessons of binary search.

Binary search teaches us that when a list is sorted or mostly sorted:

• The value at a given index tells us a lot about what’s to the left and what’s to the right.
• We don’t have to look at every item in the list. By inspecting the middle item, we can “rule out” half of the list.
• We can use this approach over and over, cutting the problem in half until we have the answer. This is sometimes called “divide and conquer.”

So whenever you know a list is sorted or almost sorted, think about these lessons from binary search and see if they apply.

Trees and graphs

Balanced binary tree

Write a function to see if a binary tree is “superbalanced” (a new tree property we just made up).

A tree is “superbalanced” if the difference between the depths of any two leaf nodes is no greater than one.

Breakdown:

Sometimes it’s good to start by rephrasing or “simplifying” the problem.

The requirement of “the difference between the depths of any two leaf nodes is no greater than 1” implies that we’ll have to compare the depths of all possible pairs of leaves. That’d be expensive—if there are nn leaves, there are O(n^2) possible pairs of leaves.

But we can simplify this requirement to require less work. For example, we could equivalently say:

• “The difference between the min leaf depth and the max leaf depth is 1 or less”
• “There are at most two distinct leaf depths, and they are at most 1 apart”

If you’re having trouble with a recursive approach, try using an iterative one.

To get to our leaves and measure their depths, we’ll have to traverse the tree somehow. What methods do we know for traversing a tree?

Depth-first and breadth-first are common ways to traverse a tree. Which one should we use here?

The worst-case time and space costs of both are the same—you could make a case for either.

But one characteristic of our algorithm is that it could short-circuit and return False as soon as it finds two leaves with depths more than 1 apart. So maybe we should use a traversal that will hit leaves as quickly as possible…

Depth-first traversal will generally hit leaves before breadth-first, so let’s go with that. How could we write a depth-first walk that also keeps track of our depth?

My solution:

I came up with a solution that was almost like the actual answer except I tried only keeping track of the smallest leaf height seen so far and comparing it every time we came across a leaf. It doesn’t work. The solution below is my version of the actual solution.

def is_balanced(tree_root):
    if not tree_root:
        return True

    stack = [(tree_root, 0)]
    depths = []
    while stack:
        node, depth = stack.pop()
        is_leaf = (not node.left) and (not node.right)
        if is_leaf:
            if depth not in depths:
                depths.append(depth)

                too_many_depths = len(depths) > 2
                not_balanced = (
                    len(depths) == 2 and
                    abs(depths[0] - depths[1]) > 1)
                if too_many_depths or not_balanced:
                    return False

        if node.left:
            stack.append((node.left, depth+1))

        if node.right:
            stack.append((node.right, depth+1))

    return True

Solution:

We do a depth-first walk through our tree, keeping track of the depth as we go. When we find a leaf, we add its depth to a list of depths if we haven’t seen that depth already.

Each time we hit a leaf with a new depth, there are two ways that our tree might now be unbalanced:

1. There are more than 2 different leaf depths
2. There are exactly 2 leaf depths and they are more than 1 apart.

Why are we doing a depth-first walk and not a breadth-first one? You could make a case for either. We chose depth-first because it reaches leaves faster, which allows us to short-circuit earlier in some cases.

def is_balanced(tree_root):

    # A tree with no nodes is superbalanced, since there are no leaves!
    if tree_root is None:
        return True

    # We short-circuit as soon as we find more than 2
    depths = []

    # We'll treat this list as a stack that will store tuples of (node, depth)
    nodes = []
    nodes.append((tree_root, 0))

    while len(nodes):
        # Pop a node and its depth from the top of our stack
        node, depth = nodes.pop()

        # Case: we found a leaf
        if (not node.left) and (not node.right):
            # We only care if it's a new depth
            if depth not in depths:
                depths.append(depth)

                # Two ways we might now have an unbalanced tree:
                #   1) more than 2 different leaf depths
                #   2) 2 leaf depths that are more than 1 apart
                if ((len(depths) > 2) or
                        (len(depths) == 2 and abs(depths[0] - depths[1]) > 1)):
                    return False
        else:
            # Case: this isn't a leaf - keep stepping down
            if node.left:
                nodes.append((node.left, depth + 1))
            if node.right:
                nodes.append((node.right, depth + 1))

    return True

Complexity:

O(n) time and O(n) space.

For time, the worst case is the tree is balanced and we have to iterate over all n nodes to make sure.

For the space cost, we have two data structures to watch: depths and nodes.

depths will never hold more than three elements, so we can write that off as O(1).

Because we’re doing a depth first search, nodes will hold at most d nodes where d is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is O(d).

But we can also relate d to n. In a balanced tree, d is O(log 2(n)). And the more unbalanced the tree gets, the closer d gets to n.

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to nodes at each step. When the traversal hits the rightmost node, nodes will hold half of the n total nodes in the tree. Half n is O(n), so our worst case space cost is O(n).

What We Learned:

This is an intro to some tree basics. If this is new to you, don’t worry—it can take a few questions for this stuff to come together. We have a few more coming up.

Particular things to note:

Focus on depth-first vs breadth-first traversal. You should be very comfortable with the differences between the two and the strengths and weaknesses of each.

You should also be very comfortable coding each of them up.

One tip: Remember that breadth-first uses a queue and depth-first uses a stack (could be the call stack or an actual stack object). That’s not just a clue about implementation, it also helps with figuring out the differences in behavior. Those differences come from whether we visit nodes in the order we see them (first in, first out) or we visit the last-seen node first (last in, first out).

BST checker

Write a function to check that a binary tree is a valid binary search tree.

Breakdown:

One way to break the problem down is to come up with a way to confirm that a single node is in a valid place relative to its ancestors. Then if every node passes this test, our whole tree is a valid BST.

What makes a given node “correct” relative to its ancestors in a BST? Two things:

• if a node is in the ancestor’s left subtree, then it must be less than the ancestor, and
• if a node is in the ancestor’s right subtree, then it must be greater than the ancestor.

So we could do a walk through our binary tree, keeping track of the ancestors for each node and whether the node should be greater than or less than each of them. If each of these greater-than or less-than relationships holds true for each node, our BST is valid.

The simplest ways to traverse the tree are depth-first and breadth-first. They have the same time cost (they each visit each node once). Depth-first traversal of a tree uses memory proportional to the depth of the tree, while breadth-first traversal uses memory proportional to the breadth of the tree (how many nodes there are on the “level” that has the most nodes).

Because the tree’s breadth can as much as double each time it gets one level deeper, depth-first traversal is likely to be more space-efficient than breadth-first traversal, though they are strictly both O(n) additional space in the worst case. The space savings are obvious if we know our binary tree is balanced—its depth will be O(lg(n)) and its breadth will be O(n).

But we’re not just storing the nodes themselves in memory, we’re also storing the value from each ancestor and whether it should be less than or greater than the given node. Each node has O(n) ancestors O(lg(n)) for a balanced binary tree), so that gives us O(n^2) additional memory cost (O(n*lg(n)) for a balanced binary tree). We can do better.

Let’s look at the inequalities we’d need to store for a given node:

A binary tree with a root node of 50. To the left of the root is a node containing 30, whose left child contains 20, whose left child (highlighted in blue) contains 10. Notice that we would end up testing that the blue node is <20, <30, and <50. Of course, <30 and <50 are implied by <20. So instead of storing each ancestor, we can just keep track of a lower_bound and upper_bound that our node’s value must fit inside.

Solution:

We do a depth-first walk through the tree, testing each node for validity as we go. If a node appears in the left subtree of an ancestor, it must be less than that ancestor. If a node appears in the right subtree of an ancestor, it must be greater than that ancestor.

Instead of keeping track of every ancestor to check these inequalities, we just check the largest number it must be greater than (its lower_bound) and the smallest number it must be less than (its upper_bound).

def is_binary_search_tree(root):

    # Start at the root, with an arbitrarily low lower bound
    # and an arbitrarily high upper bound
    node_and_bounds_stack = [(root, -float('inf'), float('inf'))]

    # Depth-first traversal
    while len(node_and_bounds_stack):
        node, lower_bound, upper_bound = node_and_bounds_stack.pop()

        # If this node is invalid, we return false right away
        if (node.value <= lower_bound) or (node.value >= upper_bound):
            return False

        if node.left:
            # This node must be less than the current node
            node_and_bounds_stack.append((node.left, lower_bound, node.value))
        if node.right:
            # This node must be greater than the current node
            node_and_bounds_stack.append((node.right, node.value, upper_bound))

    # If none of the nodes were invalid, return true
    # (at this point we have checked all nodes)
    return True

Instead of allocating a stack ourselves, we could write a recursive function that uses the call stack. This would work, but it would be vulnerable to stack overflow. However, the code does end up quite a bit cleaner:

def is_binary_search_tree(root):
    return is_bst(root)

def is_bst(node, lo=-float('inf'), hi=float('inf')):
    if not node:
        return True

    if node.value >= hi or node.value <= lo:
        return False

    return (is_bst(node.left, lo, node.value)
        and is_bst(node.right, node.value, hi))

Checking if an in-order traversal of the tree is sorted is a great answer too, especially if you’re able to implement it without storing a full list of nodes.

Complexity:

O(n) time and O(n) space.

The time cost is easy: for valid binary search trees, we’ll have to check all n nodes.

Space is a little more complicated. Because we’re doing a depth first search, node_and_bounds_stack will hold at most d nodes where d is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is O(d).

But we can also relate d to n. In a balanced tree, d is lg(n). ​ n. And the more unbalanced the tree gets, the closer d gets to n.

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to the stack at each step. When the traversal hits the rightmost node, the stack will hold half of the n total nodes in the tree. Half n is O(n), so our worst case space cost is O(n).

Bonus:

What if the input tree has duplicate values?

What if -float('inf') or float('inf') appear in the input tree?

What We Learned:

We could think of this as a greedy approach. We start off by trying to solve the problem in just one walk through the tree. So we ask ourselves what values we need to track in order to do that. Which leads us to our stack that tracks upper and lower bounds.

We could also think of this as a sort of “divide and conquer” approach. The idea in general behind divide and conquer is to break the problem down into two or more subproblems, solve them, and then use that solution to solve the original problem.

In this case, we’re dividing the problem into subproblems by saying, “This tree is a valid binary search tree if the left subtree is valid and the right subtree is valid.” This is more apparent in the recursive formulation of the answer above.

Of course, it’s just fine that our approach could be thought of as greedy or could be thought of as divide and conquer. It can be both. The point here isn’t to create strict categorizations so we can debate whether or not something “counts” as divide and conquer.

Instead, the point is to recognize the underlying patterns behind algorithms, so we can get better at thinking through problems.

Sometimes we’ll have to kinda smoosh together two or more different patterns to get our answer.

Graph coloring

Given an undirected graph with maximum degree D, find a graph coloring using at most D+1 colors.

Breakdown:

Let’s take a step back. Is it always possible to find a legal coloring with D+1 colors?

Let’s think about it. Each node has at most D neighbors, and we have D+1 colors. So, if we look at any node, there’s always at least one color that’s not taken by its neighbors.

So yes—D+1 is always enough colors for a legal coloring.

Still not convinced? We can prove this more formally using induction.

Okay, so there is always a legal coloring. Now, how can we find it?

A brute force approach would be to try every possible combination of colors until we find a legal coloring. Our steps would be:

1. For each possible graph coloring,
2. If the coloring is legal, then return it
3. Otherwise, move on to the next coloring

For example, imagine a graph of 12 nodes with a maximum degree of 3. We can use 3+1 colors. We can try every possible combination of 4 colors over 12 nodes.

This would work. But what’s the complexity?

Here we’d try 4^12 combinations (every combination of 4 colors for 12 nodes). In general, we’ll have to check O(D^N)) colorings. And that’s not all —- each time we try a coloring, we have to check all M edges to see if the vertices at both ends have different colors. So, our runtime is O(M*D^N). That’s exponential time since N is in an exponent.

Since this algorithm is so inefficient, it’s probably not what the interviewer is looking for. With practice, it gets easier to quickly judge if an approach will be inefficient. Still, sometimes it’s a good idea in an interview to briefly explain inefficient ideas and why you think they’re inefficient. It shows rigorous thinking.

How can we color the graph more efficiently?

Well, we’re wasting a lot of time trying color combinations that don’t work. If the first 2 nodes are neighbors, we shouldn’t try any combinations where the first 2 colors are the same.

Instead of assigning all the colors at once, what if we colored the nodes one by one?

We could assign a color to the first node, then find a legal color for the second node, then for the third node, and keep going node by node.

def color_graph(graph, colors):
    for node in graph:
        # Get the node's neighbors' colors, as a set so we
        # can check if a color is illegal in constant time
        illegal_colors = set([
            neighbor.color
            for neighbor in node.neighbors
            if neighbor.color
        ])
        legal_colors = [
            color
            for color in colors
            if color not in illegal_colors
        ]

        # Assign the first legal color
        node.color = legal_colors[0]

Is it possible we’ll back ourselves into a corner somehow and run out of colors for some nodes?

Let’s think back to our earlier argument about whether a coloring always exists:

Each node has at most D neighbors, and we have D+1 colors. So, if we look at any node, there’s always at least one color that’s not taken by its neighbors.

That reasoning works here, too! So no–we’ll never back ourselves into a corner.

Ok, what’s our runtime?

We’re iterating through each node in the graph, so the loop body executes NN times. In each iteration of the loop:

1. We look at the current node’s neighbors to figure out what colors are already taken. That’s O(D), since any given node can have up to D neighbors.
2. Then, we look at all the colors (there O(D) of them) to see which ones are available.
3. Finally, we pick the first color that’s free and assign it to the node (O(1)).

So our runtime is N∗(D+D+1), which is O(N*D).

Can we tighten our analysis a bit here? Take a look at step 1, where we collect the neighbors’ colors:

We said looking at each node’s neighbors was O(D) since each node can have at most D neighbors… but each node might have way fewer neighbors than that.

Can we say anything about the total number of neighbors we’ll look at across all of the loop iterations? How many neighbors are there in the entire graph?

Each edge creates two neighbors: one for each node on either end. So when our code looks at every neighbor for every node, it looks at 2*M neighbors in all. With O(M) neighbors, collecting all the colors over the entire for loop takes O(M) time.

Using this tighter analysis, we’ve taken our runtime from N∗(D+D+1) down to N∗(D+1)+M. That’s O((N∗D)+M) time.

Of course, that complexity doesn’t look any faster, at least not asymptotically. But in the underlying expression, we’ve gotten rid of one of the two N∗D factors.

Can we get rid of the other one to bring our complexity down to linear time?

The remaining N∗D factor comes from step 2: looking at every color for every node to populate legal_colors.

Do we have to look at every color for every node?

When we’re coloring a node, we just need one color that hasn’t been taken by any of the node’s neighbors. We can stop looking at colors as soon as we find one:

def color_graph(graph, colors):
    for node in graph:
        # Get the node's neighbors' colors, as a set so we
        # can check if a color is illegal in constant time
        illegal_colors = set([
            neighbor.color
            for neighbor in node.neighbors
            if neighbor.color
        ])

        # Assign the first legal color
        for color in colors:
            if color not in illegal_colors:
                node.color = color
                break

Okay, now what’s the time cost of assigning the first legal color to every node (the whole last block)?

We’ll try at most len(illegal_colors) + 1 colors in total. That’s how many we’d need if we happen to test all the colors in illegal_colors first, before finally testing the one legal color last.

Remember the “+1” we get from testing the one legal color last! It’s going to be important in a second.

How many colors are in illegal_colors? It’s at most the number of neighbors, if each neighbor has a different color.

Let’s use that trick of looking at all of the loop iterations together. In total, over the course of the entire loop, how many neighbors are there?

Well, each of our M edges adds two neighbors to the graph: one for each node on either end. So that’s 2∗M neighbors in total. Which means 2∗M illegal colors in total.

But remember: we said we’d try as many as len(illegal_colors) + 1 colors per node. We still have to factor in that “+1”! Across all N of our nodes, that’s an additional N colors. So we try 2∗M+N colors in total across all of our nodes.

That’s O(M+N) time for assigning the first legal color to every node. Add that to the O(M) for finding all the illegal colors, and we get O(M+N) time in total for our graph coloring function.

Is this the fastest runtime we can get? We’ll have to look at every node (O(N)) and every edge (O(M)) at least once, so yeah, we can’t get any better than O(N+M).

How about our space cost?

The only data structure we allocate with non-constant space is the set of illegal colors. What’s the most space that ever takes up?

In the worst case, the neighbors of the node with the maximum degree will all have different colors, so our space cost is O(D).

Before we’re done, what about edge cases?

For graph problems in general, edge cases are:

• nodes with no edges
• cycles
• loops

What if there are nodes with no edges? Will our function still color every node?

Yup, no problem. Isolated nodes tend to cause problems when we’re traversing a graph (starting from one node and “walking along” edges to other nodes, like we do in a depth-first or breadth-first search). We’re not doing that here—instead, we’re iterating over a list of all the nodes.

What if the graph has a cycle? Will our function still work?

Yes, it will. Cycles also tend to cause problems with graph traversal, because we can end up in infinite loops (going around and around the cycle). But we’re not actually traversing our graph here.

What if the graph has a loop?

That’s a problem. A node with a loop is adjacent to itself, so it can’t have the same color as . . . itself. So it’s impossible to “legally color” a node with a loop. So we should throw an error.

How can we detect loops?

We know a node has a loop if the node is in its own set of neighbors.

Solution:

We go through the nodes in one pass, assigning each node the first legal color we find.

How can we be sure we’ll always have at least one legal color for every node? In a graph with maximum degree D, each node has at most D neighbors. That means there are at most D colors taken by a node’s neighbors. And we have D+1 colors, so there’s always at least one color left to use.

When we color each node, we’re careful to stop iterating over colors as soon as we find a legal color.

class GraphNode:

    def __init__(self, label):
        self.label = label
        self.neighbors = set()
        self.color = None

def color_graph(graph, colors):
    for node in graph:
        loop_detected = node in node.neighbors
        if loop_detected:
            raise Exception(f'Loop detected at {node}')

        illegal_colors = set(neighbor.color
            for neighbor in node.neighbors
            if neighbor.color)

        for color in colors:
            if color not in illegal_colors:
                node.color = color
                break

Complexity:

O(N+M) time where N is the number of nodes and M is the number of edges.

The runtime might not look linear because we have outer and inner loops. The trick is to look at each step and think of things in terms of the total number of edges (M) wherever we can:

• We check if each node appears in its own set of neighbors. Checking if something is in a set is O(1), so doing it for all N nodes is O(N).
• When we get the illegal colors for each node, we iterate through that node’s neighbors. So in total, we cross each of the graphs M edges twice: once for the node on either end of each edge. O(M) time.
• When we assign a color to each node, we’re careful to stop checking colors as soon as we find one that works. In the worst case, we’ll have to check one more color than the total number of neighbors. Again, each edge in the graph adds two neighbors—one for the node on either end—so there are 2*M neighbors. So, in total, we’ll have to try O(N+M) colors.

Putting all the steps together, our complexity is O(N+M).

What about space complexity? The only thing we’re storing is the illegal_colors set. In the worst case, all the neighbors of a node with the maximum degree (D) have different colors, so our set takes up O(D) space.

Bonus:

• Our solution runs in O(N+M) time but takes O(D) space. Can we get down to O(1) space?
• Our solution finds a legal coloring, but there are usually many legal colorings. What if we wanted to optimize a coloring to use as few colors as possible?

What We Learned:

We used a greedy approach to build up a correct solution in one pass through the nodes.

This brought us close to the optimal runtime, but we also had to take that last step of iterating over the colors only until we find a legal color. Sometimes stopping a loop like that is just a premature optimization that doesn’t bring down the final runtime, but here it actually made our runtime linear!

Find Repeat, space edition BEAST MODE

In Find a duplicate, Space Edition™, we were given a list of integers where:

1. the integers are in the range 1..n
2. the list has a length of n+1

These properties mean the list must have at least 1 duplicate. Our challenge was to find a duplicate number without modifying the input and optimizing for space. We used a divide and conquer approach, iteratively cutting the list in half to find a duplicate integer in O(nlgn) time and O(1) space (sort of a modified binary search).

But we can actually do better. We can find a duplicate integer in O(n) time while keeping our space cost at O(1).

This is a tricky one to derive (unless you have a strong background in graph theory), so we’ll get you started:

Imagine each item in the list as a node in a linked list. In any linked list, each node has a value and a “next” pointer. In this case:

• The value is the integer from the list.
• The “next” pointer points to the value-eth node in the list (numbered starting from 1). For example, if our value was 3, the “next” node would be the third node.

Notice we’re using “positions” and not “indices”. For this problem, we’ll use the word “position” to mean something like “index,” but different: indices start at 0, while positions start at 1. More rigorously: position = index + 1.

Using this, find a duplicate integer in O(n) time while keeping our space cost at O(1). Just like before, don’t modify the input.

Drawing pictures will help a lot with this one. Grab some paper and pencil (or a whiteboard, if you have one).

My Solution:

def find_duplicate(int_list):
    # Use slow-fast pointers to find loop
    start, ix_start = int_list[-1], len(int_list)-1
    finish, ix_finish = int_list[start-1], start-1

    while ix_start != ix_finish:
        start, ix_start = int_list[start-1], start-1
        finish, ix_finish = int_list[finish-1], finish-1
        finish, ix_finish = int_list[finish-1], finish-1

    # find length of loop
    length = 1
    finish, ix_finish = int_list[finish-1], finish-1
    while ix_start != ix_finish:
        finish, ix_finish = int_list[finish-1], finish-1
        length += 1

    # advance two pointers that are a loop length apart
    start, ix_start = int_list[-1], len(int_list)-1
    finish, ix_finish = start, ix_start
    for _ in range(length):
        finish, ix_finish = int_list[finish-1], finish-1

    # when the pointers meet, the node *position* is the duplicate value
    while ix_start != ix_finish:
        start, ix_start = int_list[start-1], start-1
        finish, ix_finish = int_list[finish-1], finish-1

    # return node position, not the value
    return ix_start + 1

Solution:

We treat the input list as a linked list like we described at the top in the problem.

To find a duplicate integer:

• We know the position of a node with multiple incoming pointers is a duplicate in our list because the nodes that pointed to it must have the same value.
• We find a node with multiple incoming pointers by finding the first node in a cycle.
• We find the first node in a cycle by finding the length of the cycle and advancing two pointers: one starting at the head of the linked list, and the other starting ahead as many steps as there are nodes in the cycle. The pointers will meet at the first node in the cycle.
• We find the length of a cycle by remembering a position inside the cycle and counting the number of steps it takes to get back to that position.
• We get inside a cycle by starting at the head and walking nn steps. We know the head of the list is at position n+1.

We want to think of our list as a linked list but we don’t want to actually use up all that space, so we traverse our list as if it were a linked list by converting positions to indices.

def find_duplicate(int_list):
    """Book solution, cleaned up and slightly refactored."""
    n = len(int_list) - 1

    # find loop.  Iterating n steps guarantees we're in the loop.
    position_in_loop = n + 1
    for _ in range(n):
        position_in_loop = int_list[position_in_loop-1]

    # find length of loop
    length = 1
    curr_position = int_list[position_in_loop-1]
    while curr_position != position_in_loop:
        curr_position = int_list[curr_position-1]
        length += 1

    # advance two pointers that are a loop length apart
    start = finish = n + 1
    for _ in range(length):
        finish = int_list[finish-1]

    # when the pointers meet, the node *position* is the duplicate value
    while start != finish:
        start = int_list[start-1]
        finish = int_list[finish-1]

    # return node position, not the value
    return start

Complexity:

O(n) time and O(1) space.

Our space cost is O(1) because all of our additional variables are integers, which each take constant space.

For our runtime, we iterate over the array a constant number of times, and each iteration takes O(n) time in its worst case. So we traverse the linked list more than once, but it’s still a constant number of times—about 3.

Bonus:

There another approach using randomized algorithms that is O(n) time and O(1) space. Can you come up with that one? (Hint: You’ll want to focus on the median.)

What We Learned:

This one’s pretty crazy. It’s hard to imagine an interviewer expecting you to get all the way through this question without help.

But just because it takes a few hints to get to the answer doesn’t mean a question is “too hard.” Some interviewers expect they’ll have to offer a few hints.

So if you get a hint in an interview, just relax and listen. The most impressive thing you can do is drop what you’re doing, fully understand the hint, and then run with it.

DP and recursion

Recursive string permutation

Write a recursive function for generating all permutations of an input string. Return them as a set.

Don’t worry about time or space complexity—if we wanted efficiency we’d write an iterative version.

To start, assume every character in the input string is unique.

Your function can have loops—it just needs to also be recursive.

My solution:

from itertools import permutations

def get_permutations(string):
    return set(''.join(perm) for perm in permutations(string))

Solution:

def get_permutations(string):
    if len(string) <= 1:
        return set([string])

    trimmed = string[:-1]
    last = string[-1]

    prev_perms = get_permutations(trimmed)

    perms = set()
    for perm in prev_perms:
        for i in range(len(trimmed) + 1):
            new_perm = perm[:i] + last + perm[i:]
            perms.add(new_perm)

    return perms

def get_permutations(string):
    if len(string) <= 1:
        return set([string])

    old_perms = []
    perms = [string[0]]
    for i in range(1, len(string)):
        old_perms, perms = perms, old_perms
        while old_perms:
            new_perm = list(old_perms.pop())
            new_perm.append(string[i])

            perms.append(''.join(new_perm))
            for j in reversed(range(1, len(new_perm))):
                new_perm[j], new_perm[j-1] = new_perm[j-1], new_perm[j]
                perms.append(''.join(new_perm))

    return set(perms)

Making change

Your quirky boss collects rare, old coins. They found out you’re a programmer and asked you to solve something they’ve been wondering for a long time.

Write a function that, given:

• an amount of money
• a list of coin denominations

computes the number of ways to make the amount of money with coins of the available denominations.

For example, when amount=4 and denominations=[1,2,3], there are four unique combinations to get 4.

Breakdown:

We need to find some way to break this problem down into subproblems.

Here’s one way: for each denomination, we can use it once, or twice, or…as many times as it takes to reach or overshoot the amount with coins of that denomination alone.

For each of those choices of how many times to include coins of each denomination, we’re left with the subproblem of seeing how many ways we can get the remaining amount from the remaining denominations.

A strictly top-down approach will duplicate some work. Using memoization, we can make the top-down approach O(n*m) and O(n*m) space.

Instead, we can use a bottom-up approach by looking at smaller amounts and fewer denominations.

If we only had 1-cent coins, how many ways can we use those coins to make some amount? What happens when we add 3-cent coins? How do we reuse our answer for 1-cent coins?

Let’s suppose we’re partway through already (this is a classic dynamic programming approach). Say we’re trying to calculate ways_of_doing_n_cents_1_2[5]. Because we’re going bottom-up, we know we already have:

1. ways_of_doing_n_cents_1_2 for amounts less than 5
2. a fully-populated ways_of_doing_n_cents_1

So how many new ways should we add to ways_of_doing_n_cents_1[5] to get ways_of_doing_n_cents_1_2[5]?

Well, if there are any new ways to get 5¢ now that we have 2¢ coins, those new ways must involve at least one 2¢ coin. So if we presuppose that we’ll use one 2¢ coin, that leaves us with 5-2=35−2=3 left to come up with. We already know how many ways we can get 3¢ with 1¢ and 2¢ coins: ways_of_doing_n_cents_1_2[3], which is 22.

Why don’t we also need to check ways_of_doing_n_cents_1_2[5 - 2 - 2] (two 2¢ coins)? Because we already checked ways_of_doing_n_cents_1_2[1] when calculating ways_of_doing_n_cents_1_2[3]. We’d be counting some arrangements multiple times. In other words, ways_of_doing_n_cents_1_2[k] already includes the full count of possibilities for getting k, including possibilities that use 2¢ any number of times. We’re only interested in how many more possibilities we might get when we go from k to k+2 and thus have the ability to add one more 2¢ coin to each of the possibilities we have for k.

Solution:

We use a bottom-up algorithm to build up a table ways_of_doing_n_cents such that ways_of_doing_n_cents[k] is how many ways we can get to k cents using our denominations. We start with the base case that there’s one way to create the amount zero, and progressively add each of our denominations.

The number of new ways we can make a higher_amount when we account for a new coin is simply ways_of_doing_n_cents[higher_amount - coin], where we know that value already includes combinations involving coin (because we went bottom-up, we know smaller values have already been calculated).

# variable names have been modified, but same implementation as original.
def change_possibilities(amount, denominations):

    n_combos = [1] + [0] * amount

    for coin in denominations:
        for smaller_amount in range(coin, amount+1):
            diff = smaller_amount - coin
            n_combos[smaller_amount] += n_combos[diff]

    return n_combos[amount]

Complexity:

O(n*m) time and O(n) additional space, where n is the amount of money and m is the number of potential denominations.

What We Learned:

This question is in a broad class called “dynamic programming.” We have a bunch more dynamic programming questions we’ll go over later.

Dynamic programming is kind of like the next step up from greedy. You’re taking that idea of “keeping track of what we need in order to update the best answer so far,” and applying it to situations where the new best answer so far might not just have to do with the previous answer, but some other earlier answer as well.

So as you can see in this problem, we kept track of all of our previous answers to smaller versions of the problem (called “subproblems”) in a big list called ways_of_doing_n_cents.

Again, same idea of keeping track of what we need in order to update the answer as we go, like we did when storing the max product of 2, min product of 2, etc in the highest product of 3 question. Except now the thing we need to keep track of is all our previous answers, which we’re keeping in a list.

We built that list bottom-up, but we also talked about how we could do it top-down and memoize. Going bottom-up is cleaner and usually more efficient, but often it’s easier to think of the top-down version first and try to adapt from there.

Dynamic programming is a weak point for lots of candidates. If this one was tricky for you, don’t fret. We have more coming later.

The cake thief

While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.

Each type of cake has a weight and a value, stored in a tuple with two indices:

• An integer representing the weight of the cake in kilograms
• An integer representing the monetary value of the cake in British shillings

You brought a duffel bag that can hold limited weight, and you want to make off with the most valuable haul possible.

Write a function max_duffel_bag_value() that takes a list of cake type tuples and a weight capacity, and returns the maximum monetary value the duffel bag can hold.

For example:

cake_tuples = [(7, 160), (3, 90), (2, 15)]
capacity    = 20

# Returns 555 (6 of the middle type of cake and 1 of the last type of cake)
max_duffel_bag_value(cake_tuples, capacity)

Weights and values may be any non-negative integer. Yes, it’s weird to think about cakes that weigh nothing or duffel bags that can’t hold anything. But we’re not just super mastermind criminals—we’re also meticulous about keeping our algorithms flexible and comprehensive.

Breakdown:

What about edge cases?

Remember, weights and values can be any non-negative integer. What about zeroes? How can we handle duffel bags that can’t hold anything and cakes that weigh nothing?

Well, if our duffel bag can’t hold anything, we can just return 0. And if a cake weighs 0 kg, we return infinity. Right?

Not that simple!

What if our duffel bag holds 0 kg, and we have a cake that weighs 0 kg. What do we return?

And what if we have a cake that weighs 0 kg, but its value is also 0. If we have other cakes with positive weights and values, what do we return?

If a cake’s weight and value are both 0, it’s reasonable to not have that cake affect what we return at all.

If we have a cake that weighs 0 kg and has a positive value, it’s reasonable to return infinity, even if the capacity is 0.

For returning infinity, we have several choices. We could return:

• Python 3.6’s float('inf').
• Return a custom response, like the string 'infinity'.
• Raise an exception indicating the answer is infinity.

What are the advantages and disadvantages of each option?

For the first option the advantage is we get the behavior of infinity. Compared to any other integer, float('inf') will be greater. And it’s a number, which can be an advantage or disadvantage—we might want our result to always be the same type, but without manually checking we won’t know if we mean an actual value or the special case of infinity.

For the second option the advantage is we can create a custom behavior that we—or our function’s users—could know to expect. The disadvantage is we’d have to explicitly check for that behavior, otherwise we might end up trying to parse the string “infinity” as an integer, which could give us an error or (perhaps worse) a random number. In a production system, a function that sometimes returns an integer and sometimes returns a string would probably be seen as sloppy.

The third option is a good choice if we decide infinity is usually an “unacceptable” answer. For example, we might decide an infinite answer means we’ve probably entered our inputs wrong. Then, if we really wanted to “accept” an infinite answer, we could always “catch” this exception when we call our function.

Any option could be reasonable. We’ll go with the first one here.

Solution:

This is a classic computer science puzzle called “the unbounded knapsack problem.”

We use a bottom-up approach to find the max value at our duffel bag’s weight_capacity by finding the max value at every capacity from 0 to weight_capacity.

We allocate a list max_values_at_capacities where the indices are capacities and each value is the max value at that capacity.

For each capacity, we want to know the max monetary value we can carry. To figure that out, we go through each cake, checking to see if we should take that cake.

The best monetary value we can get if we take a given cake is simply:

1. that cake’s value, plus
2. the best monetary value we can carry in our remaining duffel bag capacity after taking the cake—which we’ll already have stored in max_values_at_capacities

To handle weights and values of zero, we return infinity only if a cake weighs nothing and has a positive value.

from collections import namedtuple

Cake = namedtuple('Cake', ['weight', 'value'])

def max_duffel_bag_value(cake_tuples, weight_capacity):
    cake_tuples = [Cake(w, v) for w, v in cake_tuples]
    max_capacity = weight_capacity + 1
    max_values = [0] * max_capacity

    for curr_capacity in range(max_capacity):
        curr_max_value = 0
        for cake in cake_tuples:
            weightless = not cake.weight
            if weightless and cake.value:
                return float('inf')

            if cake.weight <= curr_capacity:
                max_value_with_cake = (
                    cake.value + max_values[curr_capacity - cake.weight])

                curr_max_value = max(max_value_with_cake, curr_max_value)

        max_values[curr_capacity] = curr_max_value

    return max_values[weight_capacity]

Complexity:

O(n∗k) time, and O(k) space, where n is number of types of cake and k is the capacity of the duffel bag. We loop through each cake (n cakes) for every capacity (k capacities), so our runtime is O(n∗k), and maintaining the list of k+1 capacities gives us the O(k) space.

Congratulations! Because of dynamic programming, you have successfully stolen the Queen’s cakes and made it big.

Keep in mind: in some cases, it might not be worth using our optimal dynamic programming solution. It’s a pretty slow algorithm—without any context (not knowing how many cake types we have, what our weight capacity is, or just how they compare) it’s easy to see O(n*k) growing out of control quickly if n or k is large.

If we cared about time, like if there was an alarm in the vault and we had to move quickly, it might be worth using a faster algorithm that gives us a good answer, even if it’s not always the optimal answer. Some of our first ideas in the breakdown were to look at cake values or value/weight ratios. Those algorithms would probably be faster, taking O(n*lg(n)) time (we’d have to start by sorting the input).

Sometimes an efficient, good answer might be more practical than an inefficient, optimal answer.

Bonus:

• We know the max value we can carry, but which cakes should we take, and how many? Try adjusting your answer to return this information as well.
• What if we check to see if all the cake weights have a common denominator? Can we improve our algorithm?
• A cake that’s both heavier and worth less than another cake would never be in the optimal solution. This idea is called dominance relations. Can you apply this idea to save some time? Hint: dominance relations can apply to sets of cakes, not just individual cakes.
• What if we had a tuple for every individual cake instead of types of cakes? So now there’s not an unlimited supply of a type of cake—there’s exactly one of each. This is a similar but harder problem, known as the 0/1 Knapsack problem.

What We Learned:

This question is our spin on the famous “unbounded knapsack problem”—a classic dynamic programming question.

If you’re struggling with dynamic programming, we have reference pages for the two main dynamic programming strategies: memoization and going bottom-up.

Stacks and queues

Largest stack

You want to be able to access the largest element in a stack.

Use your Stack class to implement a new class MaxStack with a method get_max() that returns the largest element in the stack. get_max() should not remove the item.

Your stacks will contain only integers.

Solution:

class Stack(object):

    def __init__(self):
        """Initialize an empty stack"""
        self.items = []

    def push(self, item):
        """Push a new item onto the stack"""
        self.items.append(item)

    def pop(self):
        """Remove and return the last item"""
        # If the stack is empty, return None
        # (it would also be reasonable to throw an exception)
        if not self.items:
            return None

        return self.items.pop()

    def peek(self):
        """Return the last item without removing it"""
        if not self.items:
            return None
        return self.items[-1]


class MaxStack(object):
    def __init__(self):
        self._stack = Stack()
        self._max_stack = Stack()

    def push(self, item):
        self._stack.push(item)
        if (self._max_stack.peek() is None
            or item >= self._max_stack.peek():

            self._max_stack.push(item)

    def pop(self):
        item = self._stack.pop()
        if item == self._max_stack.peek():
            self._max_stack.pop()
        return item

    def get_max(self):
        if self._max_stack.peek() is None:
            raise ValueError('Stack is empty')

        return self._max_stack.peek()

Here’s a way to do it without the extra stack. Whenever we encounter a value that is greater than the max, we store the value as the max value, but push 2*value - old_max onto the stack. When we pop, we do the inverse. Therefore, we never store the maximum value in the stack; it’s always stored in the _max attribute:

class MaxStack(object):
    def __init__(self):
        self._stack = Stack()
        self._max = None

    def push(self, item):
        if self._stack.peek() is None:
            self._max = item

        if item > self._max:
            self._stack.push(2 * item - self._max)
            self._max = item
        else:
            self._stack.push(item)


    def pop(self):
        if self._stack.peek() is None:
            raise ValueError('Stack is empty')

        item = self._stack.pop()
        if item > self._max:
            self._max, item = 2*self._max - item, self._max

        return item

    def get_max(self):
        if self._stack.peek() is None:
            raise ValueError('Stack is empty')

        return self._max

Bracket Validator

Let’s say:

• '(', '{', '[' are called “openers.”
• ')', '}', ']' are called “closers.”

Write an efficient function that tells us whether or not an input string’s openers and closers are properly nested.

Examples:

• “{ ( ) }” should return True
• “{ [ ( ] ) }” should return False
• “{ [ }” should return False

My solution:

def is_valid(code):
    stack = []
    delimiters = '(){}[]'
    open_delimiters = delimiters[::2]
    closed_delimiters = delimiters[1::2]
    for ch in code:
        if ch in open_delimiters:
            stack.append(ch)
            continue
        elif ch not in closed_delimiters:
            continue

        if not stack:
            return False

        pair = stack.pop() + ch
        if pair not in delimiters:
            return False



    return not stack

Solution:

We iterate through our string, making sure that:

• each closer corresponds to the most recently seen, unclosed opener
• every opener and closer is in a pair

We use a stack to keep track of the most recently seen, unclosed opener. And if the stack is ever empty when we come to a closer, we know that closer doesn’t have an opener.

So as we iterate:

• If we see an opener, we push it onto the stack.
• If we see a closer, we check to see if it is the closer for the opener at the top of the stack. If it is, we pop from the stack. If it isn’t, or if the stack is empty, we return False.

If we finish iterating and our stack is empty, we know every opener was properly closed.

def is_valid(code):
    openers_to_closers = {
        '(' : ')',
        '{' : '}',
        '[' : ']',
    }
    openers = set(openers_to_closers.keys())
    closers = set(openers_to_closers.values())

    openers_stack = []
    for char in code:
        if char in openers:
            openers_stack.append(char)
        elif char in closers:
            if not openers_stack:
                return False
            else:
                last_unclosed_opener = openers_stack.pop()
                # If this closer doesn't correspond to the most recently
                # seen unclosed opener, short-circuit, returning False
                if not openers_to_closers[last_unclosed_opener] == char:
                    return False

    return openers_stack == []

Complexity:

O(n) time (one iteration through the string), and O(n) space (in the worst case, all of our characters are openers, so we push them all onto the stack).

Bonus:

In Ruby, sometimes expressions are surrounded by vertical bars, “|like this|”. Extend your validator to validate vertical bars. Careful: there’s no difference between the “opener” and “closer” in this case—they’re the same character!

What We Learned:

The trick was to use a stack.

It might have been difficult to have that insight, because you might not use stacks that much.

Two common uses for stacks are:

• parsing (like in this problem)
• tree or graph traversal (like depth-first traversal)

So remember, if you’re doing either of those things, try using a stack!

Linked lists

Delete node

Delete a node from a singly-linked list, given only a variable pointing to that node.

My solution:

In contrast to the book solution, I detect that we are at the end of the list, not just at the last node.

def delete_node(node_to_delete):

    if (not node_to_delete) or (not node_to_delete.next):
        raise Exception('Undeletable node')

    next_node = node_to_delete.next
    node_to_delete.value = next_node.value
    node_to_delete.next = next_node.next

Solution:

We take value and next from the input node’s next node and copy them into the input node. Now the input node’s previous node effectively skips the input node’s old value!

In some languages, like C, we’d have to manually delete the node we copied from, since we won’t be using that node anymore. Here, we’ll let Python’s garbage collector take care of it.

def delete_node(node_to_delete):
    # Get the input node's next node, the one we want to skip to
    next_node = node_to_delete.next

    if next_node:
        # Replace the input node's value and pointer with the next
        # node's value and pointer. The previous node now effectively
        # skips over the input node
        node_to_delete.value = next_node.value
        node_to_delete.next  = next_node.next
    else:
        # Eep, we're trying to delete the last node!
        raise Exception("Can't delete the last node with this technique!")

But be careful—there are some potential problems with this implementation:

First, it doesn’t work for deleting the last node in the list. We could change the node we’re deleting to have a value of None, but the second-to-last node’s next pointer would still point to a node, even though it should be None. This could work—we could treat this last, “deleted” node with value None as a “dead node” or a “sentinel node,” and adjust any node traversing code to stop traversing when it hits such a node. The trade-off there is we couldn’t have non-dead nodes with values set to None. Instead we chose to throw an exception in this case.

Second, this technique can cause some unexpected side-effects. For example, let’s say we call:

a = LinkedListNode(3)
b = LinkedListNode(8)
c = LinkedListNode(2)

a.next = b
b.next = c

delete_node(b)

There are two potential side-effects:

• Any references to the input node have now effectively been reassigned to its next node. In our example, we “deleted” the node assigned to the variable b, but in actuality we just gave it a new value (2) and a new next! If we had another pointer to b somewhere else in our code and we were assuming it still had its old value (8), that could cause bugs.
• If there are pointers to the input node’s original next node, those pointers now point to a “dangling” node (a node that’s no longer reachable by walking down our list). In our example above, c is now dangling. If we changed c, we’d never encounter that new value by walking down our list from the head to the tail.

Complexity:

O(1) time and O(1) space.

What We Learned:

My favorite part of this problem is how imperfect the solution is. Because it modifies the list “in place” it can cause other parts of the surrounding system to break. This is called a “side effect.”

In-place operations like this can save time and/or space, but they’re risky. If you ever make in-place modifications in an interview, make sure you tell your interviewer that in a real system you’d carefully check for side effects in the rest of the code base.

Does this linked list have a cycle?

Write a function contains_cycle() that takes the first node in a singly-linked list and returns a boolean indicating whether the list contains a cycle.

My solution:

def contains_cycle(first_node):
    if not first_node:
        return False

    slow = fast = first_node

    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True


    return False

Solution:

def contains_cycle(first_node):
    slow = fast = first_node

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True

    return False

Complexity:

O(n) time and O(1) space.

The runtime analysis is a little tricky. The worst case is when we do have a cycle, so we don’t return until fast_runner equals slow_runner. But how long will that take?

First, we notice that when both runners are circling around the cycle, fast_runner can never skip over slow_runner. Why is this true?

Suppose fast_runner had just skipped over slow_runner. fast_runner would only be 1 node ahead of slow_runner, since their speeds differ by only 1.

If it had, what would the step right before this “skipping step” look like? fast_runner would be 2 nodes back, and slow_runner would be 1 node back. But wait, that means they would be at the same node! So fast_runner didn’t skip over slow_runner! (This is a proof by contradiction.)

Since fast_runner can’t skip over slow_runner, at most slow_runner will run around the cycle once and fast_runner will run around twice. This gives us a runtime of O(n).

For space, we store two variables no matter how long the linked list is, which gives us a space cost of O(1).

Bonus:

• How would you detect the first node in the cycle? Define the first node of the cycle as the one closest to the head of the list.
• Would the program always work if the fast runner moves three steps every time the slow runner moves one step?
• What if instead of a simple linked list, you had a structure where each node could have several “next” nodes? This data structure is called a “directed graph.” How would you test if your directed graph had a cycle?

What We Learned:

Some people have trouble coming up with the “two runners” approach. That’s expected—it’s somewhat of a blind insight. Even great candidates might need a few hints to get all the way there. And that’s fine.

Remember that the coding interview is a dialogue, and sometimes your interviewer expects she’ll have to offer some hints along the way.

One of the most impressive things you can do as a candidate is listen to a hint, fully understand it, and take it to its next logical step. Interview Cake gives you lots of opportunities to practice this. Don’t be shy about showing lots of hints on our exercises—that’s what they’re there for!

Reverse a linked list

Write a function for reversing a linked list. Do it in place.

Your function will have one input: the head of the list.

Your function should return the new head of the list.

My solution:

def reverse(head_of_list):
    new_head = None
    tmp = head_of_list
    while head_of_list:
        tmp = head_of_list.next
        head_of_list.next = new_head
        new_head = head_of_list
        head_of_list = tmp
    return new_head

A nifty solution I saw:

def reverse(head_of_list):
    new_head = None
    while head_of_list:
        head_of_list.next, new_head, head_of_list = (
            new_head, head_of_list, head_of_list.next
        )
    return new_head

Solution:

In one pass from head to tail of our input list, we point each node’s next pointer to the previous item.

The order of operations is important here! We’re careful to copy current_node.next into next before setting current_node.next to previous_node. Otherwise “stepping forward” at the end could actually mean stepping back to previous_node!

def reverse(head_of_list):
    current_node = head_of_list
    previous_node = next_node = None

    while current_node:
        next_node = current_node.next

        current_node.next = previous_node

        # Step forward in the list
        previous_node = current_node
        current_node = next_node

    return previous_node

We return previous_node because when we exit the list, current_node is None. Which means that the last node we visited—previous_node—was the tail of the original list, and thus the head of our reversed list.

Complexity:

O(n) time and O(1) space. We pass over the list only once, and maintain a constant number of variables in memory.

Bonus:

This in-place reversal destroys the input linked list. What if we wanted to keep a copy of the original linked list? Write a function for reversing a linked list out-of-place.

What We Learned:

It’s one of those problems where, even once you know the procedure, it’s hard to write a bug-free solution. Drawing it out helps a lot. Write out a sample linked list and walk through your code by hand, step by step, running each operation on your sample input to see if the final output is what you expect. This is a great strategy for any coding interview question.

kth to last node in singly linked list

Write a function kth_to_last_node() that takes an integer k and the head_node of a singly-linked list, and returns the kth to last node in the list.

My solution:

def kth_to_last_node(k, head):
    if k <= 0:
        raise Exception('k not big enough.')

    total = 0
    curr = head
    while curr:
        total += 1
        curr = curr.next

    steps = total - k
    if steps < 0:
        raise Exception('Not enough nodes.')

    curr = head
    for _ in range(steps):
        curr = curr.next

    return curr

Solution:

We can think of this two ways.

First approach: use the length of the list.

1. walk down the whole list, counting nodes, to get the total list_length.
2. subtract k from the list_length to get the distance from the head node to the target node (the kth to last node).
3. walk that distance from the head to arrive at the target node.

This is basically my solution. However, I think it will fail if head is None. The while loop assumes that current_node is a node, but if current_node is None, it won’t be able to access next. My solution doesn’t have that problem and will raise the exception at the next check.

def kth_to_last_node(k, head):
    if k < 1:
        raise ValueError(
            'Impossible to find less than first to last node: %s' % k
        )

    # Step 1: get the length of the list
    # Start at 1, not 0
    # else we'd fail to count the head node!
    list_length = 1
    current_node = head

    # Traverse the whole list,
    # counting all the nodes
    while current_node.next:
        current_node = current_node.next
        list_length += 1

    # If k is greater than the length of the list, there can't
    # be a kth-to-last node, so we'll return an error!
    if k > list_length:
        raise ValueError(
            'k is larger than the length of the linked list: %s' % k
        )

    # Step 2: walk to the target node
    # Calculate how far to go, from the head,
    # to get to the kth to last node
    how_far_to_go = list_length - k
    current_node = head
    for i in range(how_far_to_go):
        current_node = current_node.next

    return current_node

Second approach: maintain a k-wide “stick” in one walk down the list.

1. Walk one pointer k nodes from the head. Call it right_node.
2. Put another pointer at the head. Call it left_node.
3. Walk both pointers, at the same speed, towards the tail. This keeps a distance of k between them.
4. When right_node hits the tail, left_node is on the target (since it’s k nodes from the end of the list).

def kth_to_last_node(k, head):
    if k < 1:
        raise ValueError(
            'Impossible to find less than first to last node: %s' % k
        )

    left_node  = right_node = head
    # Move right_node to the kth node
    for _ in range(k - 1):
        # But along the way, if a right_node doesn't have a next,
        # then k is greater than the length of the list and there
        # can't be a kth-to-last node! we'll raise an error
        if not right_node.next:
            raise ValueError(
                'k is larger than the length of the linked list: %s' % k
            )
        right_node = right_node.next

    # Starting with left_node on the head,
    # move left_node and right_node down the list,
    # maintaining a distance of k between them,
    # until right_node hits the end of the list
    while right_node.next:
        left_node  = left_node.next
        right_node = right_node.next

    # Since left_node is k nodes behind right_node,
    # left_node is now the kth to last node!
    return left_node

In either approach, make sure to check if k is greater than the length of the linked list! That’s bad input, and we’ll want to raise an error.

Complexity:

Both approaches use O(n) time and O(1) space.

But the second approach is fewer steps since it gets the answer “in one pass,” right? Wrong.

In the first approach, we walk one pointer from head to tail (to get the list’s length), then walk another pointer from the head node to the target node (the kth to last node).

In the second approach, right_node also walks all the way from head to tail, and left_node also walks from the head to the target node.

So in both cases, we have two pointers taking the same steps through our list. The only difference is the order in which the steps are taken. The number of steps is the same either way.

However, the second approach might still be slightly faster, due to some caching and other optimizations that modern processors and memory have.

Let’s focus on caching. Usually when we grab some data from memory (for example, info about a linked list node), we also store that data in a small cache right on the processor. If we need to use that same data again soon after, we can quickly grab it from the cache. But if we don’t use that data for a while, we’re likely to replace it with other stuff we’ve used more recently (this is called a “least recently used” replacement policy).

Both of our algorithms access a lot of nodes in our list twice, so they could exploit this caching. But notice that in our second algorithm there’s a much shorter time between the first and second times that we access a given node (this is sometimes called “temporal locality of reference”). Thus it seems more likely that our second algorithm will save time by using the processor’s cache! But this assumes our processor’s cache uses something like a “least recently used” replacement policy—it might use something else. Ultimately the best way to really know which algorithm is faster is to implement both and time them on a few different inputs!

Bonus:

Can we do better? What if we expect nn to be huge and k to be pretty small? In this case, our target node will be close to the end of the list…so it seems a waste that we have to walk all the way from the beginning twice.

Can we trim down the number of steps in the “second trip”? One pointer will certainly have to travel all the way from head to tail in the list to get the total length…but can we store some “checkpoints” as we go so that the second pointer doesn’t have to start all the way at the beginning? Can we store these “checkpoints” in constant space? Note: this approach only saves time if we know that our target node is towards the end of the list (in other words, n is much larger than k).

What We Learned:

We listed two good solutions. One seemed to solve the problem in one pass, while the other took two passes. But the single-pass approach didn’t take half as many steps, it just took the same steps in a different order.

So don’t be fooled: “one pass” isn’t always fewer steps than “two passes.” Always ask yourself, “Have I actually changed the number of steps?”

Miscellaneous

Rectangular love

My solution:

from collections import namedtuple

Endpoints = namedtuple('Endpoints', ['left', 'right'])
class Endpoints:
    def __init__(self, left, length):
        self.left = left
        self.right = left + length

    def __lt__(self, other):
        return self.left < other.left

    def contains(self, other):
        return self.left <= other.left <= other.right <= self.right

def get_endpoints(rect, coord):
    if coord == 'x':
        return Endpoints(rect.left_x, rect.width)

    return Endpoints(rect.bottom_y, rect.height)

Rect = namedtuple('Rect', ['left_x', 'bottom_y', 'width', 'height'])
defaults = [None] * 4

def find_rectangular_overlap(rect1, rect2):
    rect1, rect2 = Rect(**rect1), Rect(**rect2)
    x1, y1 = get_endpoints(rect1, 'x'), get_endpoints(rect1, 'y')
    x2, y2 = get_endpoints(rect2, 'x'), get_endpoints(rect2, 'y')

    x = sorted([x1, x2])
    y = sorted([y1, y2])
    rect = Rect(*defaults)

    if rect1 == rect2:
        rect = rect1

    elif x[0].contains(x[1]) and y[0].contains(y[1]):
        rect = rect1 if x[1].left == rect1.left_x else rect2

    elif x[0].right > x[1].left and y[0].right > y[1].left:
        rect = Rect(
            x[1].left,
            x[0].right - x[1].left,
            y[1].left,
            y[0].right - y[1].left
        )

    return rect._asdict()

Solution:

We divide the problem into two halves:

1. The intersection along the x-axis
2. The intersection along the y-axis

Both problems are basically the same as finding the intersection of two “ranges” on a 1-dimensional number line.

So we write a helper function find_range_overlap() that can be used to find both the x overlap and the y overlap, and we use it to build the rectangular overlap:

def find_range_overlap(point1, length1, point2, length2):
    # Find the highest start point and lowest end point.
    # The highest ("rightmost" or "upmost") start point is
    # the start point of the overlap.
    # The lowest end point is the end point of the overlap.
    highest_start_point = max(point1, point2)
    lowest_end_point = min(point1 + length1, point2 + length2)

    # Return null overlap if there is no overlap
    if highest_start_point >= lowest_end_point:
        return (None, None)

    # Compute the overlap length
    overlap_length = lowest_end_point - highest_start_point

    return (highest_start_point, overlap_length)


def find_rectangular_overlap(rect1, rect2):
    # Get the x and y overlap points and lengths
    x_overlap_point, overlap_width  = find_range_overlap(rect1['left_x'],
                                                         rect1['width'],
                                                         rect2['left_x'],
                                                         rect2['width'])
    y_overlap_point, overlap_height = find_range_overlap(rect1['bottom_y'],
                                                         rect1['height'],
                                                         rect2['bottom_y'],
                                                         rect2['height'])

    # Return null rectangle if there is no overlap
    if not overlap_width or not overlap_height:
        return {
            'left_x'   : None,
            'bottom_y' : None,
            'width'    : None,
            'height'   : None,
        }

    return {
        'left_x'   : x_overlap_point,
        'bottom_y' : y_overlap_point,
        'width'    : overlap_width,
        'height'   : overlap_height,
    }

My translation of the book solution:

from collections import namedtuple
from itertools import chain

class Endpoints(namedtuple('Endpoints', ['left', 'length'])):
    __slots__ = ()
    @property
    def right(self):
        return self.left + self.length

Rect = namedtuple('Rect', ['left_x', 'bottom_y', 'width', 'height'])
class Rect(Rect):
    __slots__ = ()
    @classmethod
    def empty(cls):
        n = len(super()._fields)
        return cls(*chain(None for _ in range(n)))

def find_range_overlap(point1, point2):
    hi_start = max(point1, point2)
    lo_end = min(point1, point2, key=lambda x: x.right)

    if hi_start.left >= lo_end.right:
        return (None,) * 2

    return hi_start.left, lo_end.right - hi_start.left

def find_rectangular_overlap(rect1, rect2):
    rect1, rect2 = Rect(**rect1), Rect(**rect2)
    x_overlap = find_range_overlap(
        Endpoints(rect1.left_x, rect1.width),
        Endpoints(rect2.left_x, rect2.width),)

    y_overlap = find_range_overlap(
        Endpoints(rect1.bottom_y, rect1.height),
        Endpoints(rect2.bottom_y, rect2.height),)

    rect = Rect.empty()

    if not any(x_overlap) or not any(y_overlap):
        pass
    else:
        rect = Rect(*chain(*zip(x_overlap, y_overlap)))

    return rect._asdict()

Complexity:

O(1) time and O(1) space.

Bonus:

What if we had a list of rectangles and wanted to find all the rectangular overlaps between all possible pairs of two rectangles within the list? Note that we’d be returning a list of rectangles.

What if we had a list of rectangles and wanted to find the overlap between all of them, if there was one? Note that we’d be returning a single rectangle.

What We Learned:

This is an interesting one because the hard part isn’t the time or space optimization—it’s getting something that works and is readable.

For problems like this, I often see candidates who can describe the strategy at a high level but trip over themselves when they get into the details.

Don’t let it happen to you. To keep your thoughts clear and avoid bugs, take time to:

• Think up and draw out all the possible cases. Like we did with the ways ranges can overlap.
• Use very specific and descriptive variable names.