Must-Know Methods for Python Coding Interviews


Author :: Kevin Vecmanis


As a self-taught developer, you end up going through (and failing) a lot of coding interviews before you’re able to get a grasp of what’s required to be successful. There is no substite for practice, but in this post I walk through a collection of recipes I have made that address common themes I’ve noticed in interviews. Enjoy!



In this article you will learn:
  • When to properly apply combinations, permutations, and cartesian product
  • How to leverage itertools to make your life easier
  • How to leverage the collections library to make your life easier


Table of Contents

Once you write enough coding interviews you start to realize that there are underlying patterns involved when it comes to what is being asked of you. In my experience, screen-based coding interviews tend to involve problems that can be broken down succinctly into one or two sub-problems. These sub-problems almost always involve:

  • Iterating
  • Filtering / Comparing / Sorting
  • Finding combinations or permutations

This means that, for Python interviews, the itertools library and collection library are you best friend. In coding interviews the problem will typically be veiled so that it’s not immediately obvious what methods you should use. The break-through moment in coding interviews typically comes once you can strip that veil away and categorize into one of the basic groupings I just described.

In this post I want to walk through a collection of methods I have found really useful in cracking the “sub-problems” that invariably arise in the Python coding interview.



Finding Sandwich Variations with Cartesian Product

This is an actual question I had in an interview. I wasn’t told to use cartesian product, but this is a classic cartesian product-style question. The question came in this format:

  • You run a restaurant that serves sandwiches.
  • You currently offer different types of bread, meat, veggies, and sauces as toppings.
  • You don’t currently offer different sizes of sandwich, but you’re interested in knowing how many more options are available to your customers by introducing three size: small, medium, and large.
Analysis

This can actually be executed with a single line function using cartesian product. Let’s walk through how this is done.

  • You need to find the number of sandwich options before and after you introduce different sizes. The following method will take a list of lists (any number of lists) and generate the cartesian product of those lists (AKA, all of our possible sandwich types).

Let’s see how it work:

import itertools as it

def cartesian_product(somelists):
    '''
    Calculate the cartesian product of any number of lists. 
    'somelists' needs to be a list of lists
    '''
    return [element for element in it.product(*somelists)]
Usage:
if __name__=='__main__':
    bread = ['Gluten Free', 'Whole Wheat', 'White']
    meat = ['Chicken', 'Beef', 'Salami']
    veggies = ['Lettuce', 'Pickles', 'Green Peppers']
    sauces = ['Mustard', 'Hot sauce', 'Mayo']

    ingredients = [bread, meat, veggies, sauces]
    sandwich_variations = cartesian_product(ingredients)
    print('Number of variations: '+str(len(sanwich_variations), end = '\n')

    for variant in sandwich_variations:
        print(variant)
You end up getting an output like…
Number of variations: 81

('Gluten Free', 'Chicken', 'Lettuce', 'Mustard')
('Gluten Free', 'Chicken', 'Lettuce', 'Hot sauce')
('Gluten Free', 'Chicken', 'Lettuce', 'Mayo')
('Gluten Free', 'Chicken', 'Pickles', 'Mustard')
('Gluten Free', 'Chicken', 'Pickles', 'Hot sauce')
('Gluten Free', 'Chicken', 'Pickles', 'Mayo')
('Gluten Free', 'Chicken', 'Green Peppers', 'Mustard')
('Gluten Free', 'Chicken', 'Green Peppers', 'Hot sauce')
('Gluten Free', 'Chicken', 'Green Peppers', 'Mayo')
('Gluten Free', 'Beef', 'Lettuce', 'Mustard')
('Gluten Free', 'Beef', 'Lettuce', 'Hot sauce')
('Gluten Free', 'Beef', 'Lettuce', 'Mayo')
('Gluten Free', 'Beef', 'Pickles', 'Mustard')
('Gluten Free', 'Beef', 'Pickles', 'Hot sauce')
('Gluten Free', 'Beef', 'Pickles', 'Mayo')
('Gluten Free', 'Beef', 'Green Peppers', 'Mustard')
('Gluten Free', 'Beef', 'Green Peppers', 'Hot sauce')
('Gluten Free', 'Beef', 'Green Peppers', 'Mayo')
('Gluten Free', 'Salami', 'Lettuce', 'Mustard')
('Gluten Free', 'Salami', 'Lettuce', 'Hot sauce')
('Gluten Free', 'Salami', 'Lettuce', 'Mayo')
('Gluten Free', 'Salami', 'Pickles', 'Mustard')
('Gluten Free', 'Salami', 'Pickles', 'Hot sauce')
('Gluten Free', 'Salami', 'Pickles', 'Mayo')
('Gluten Free', 'Salami', 'Green Peppers', 'Mustard')
('Gluten Free', 'Salami', 'Green Peppers', 'Hot sauce')
('Gluten Free', 'Salami', 'Green Peppers', 'Mayo')
('Whole Wheat', 'Chicken', 'Lettuce', 'Mustard')
('Whole Wheat', 'Chicken', 'Lettuce', 'Hot sauce')
('Whole Wheat', 'Chicken', 'Lettuce', 'Mayo')
.
.
.
.
.
.

Not bad for a one line method!

Now, if we add another list called `sizes’ we can see how many more possible variations this adds.

if __name__=='__main__':
    bread = ['Gluten Free', 'Whole Wheat', 'White']
    meat = ['Chicken', 'Beef', 'Salami']
    veggies = ['Lettuce', 'Pickles', 'Green Peppers']
    sauces = ['Mustard', 'Hot sauce', 'Mayo']
    sizes = ['Small', 'Medium', 'Large']

    ingredients = [bread, meat, veggies, sauces, sizes]
    sandwich_variations = cartesian_product(ingredients)
    print('Number of variations: '+str(len(sandwich_variations)), end = '\n')

    for variant in sandwich_variations:
        print(variant)
Number of variations: 243

('Gluten Free', 'Chicken', 'Lettuce', 'Mustard', 'Small')
('Gluten Free', 'Chicken', 'Lettuce', 'Mustard', 'Medium')
('Gluten Free', 'Chicken', 'Lettuce', 'Mustard', 'Large')
('Gluten Free', 'Chicken', 'Lettuce', 'Hot sauce', 'Small')
('Gluten Free', 'Chicken', 'Lettuce', 'Hot sauce', 'Medium')
('Gluten Free', 'Chicken', 'Lettuce', 'Hot sauce', 'Large')
('Gluten Free', 'Chicken', 'Lettuce', 'Mayo', 'Small')
('Gluten Free', 'Chicken', 'Lettuce', 'Mayo', 'Medium')
('Gluten Free', 'Chicken', 'Lettuce', 'Mayo', 'Large')
('Gluten Free', 'Chicken', 'Pickles', 'Mustard', 'Small')
.
.
.
.
.

We can see that our new total is 243 sandwich combinations, versus 81. Our answer is just the difference between the two. Cartesian Product is applied effectively in situations like this where the number of options is implicit in the number of lists being passed. Here, for example, we have give lists of options so our function will generate lists of 5 things (one from each list).

Another situation where you would use cartesian product is if you want to produce unique sequences of length N from a finite set of elements. I had an interview once that required me (as a sub-step) to produce all the binary numbers that were 8 digits long. This is one pythonic way of doing that with itertools.product.

def get_binary_elements(n):
    '''
    Get all binary values of length n.
    '''
    return [''.join(x) for x in list(it.product('01',repeat=n))]



Explanation

  • list(it.product('01',repeat=n)) product a list of lists, with individual elements in the list as either '0' or '1'.
  • ''.join(x) for x combines the elements in list x into one string.
  • This is done for every list.

    Usage….
# Print all binary numbers of length 8
for element in get_binary_elements(8):
    print(element)
00000000
00000001
00000010
00000011
00000100
00000101
00000110
00000111
00001000
00001001
00001010
.
.
.
.
.
.
11111000
11111001
11111010
11111011
11111100
11111101
11111110
11111111



Greatest hockey players of all time with permutations <a name=’hockey></a>

Consider the situation you and a group of friends are sitting around on a Saturday night watching hockey. You get into a debate about who the top 5 hockey players in history are. Permuations are relevant in situations where order matters.

Suppose you’re debating the order of the following 5 players, in terms of where they rank as the greatest of all time:

  • Wayne Gretzky
  • Alexander Ovechkin
  • Bobby Orr
  • Sidney Crosby
  • Mario Lemieux

One way to get the number of ways these names can be ranked is:

# Print all binary numbers of length 8
players = ['Wayne Gretzky', 'Alexander Ovechkin', 'Bobby Orr', 'Sidney Crosby', 'Mario Lemieux']

# There will 5x4x3x2x1 = 120 ways these players can be ranked!
for elem in list(it.permutations(players)):
    print(elem)
('Wayne Gretzky', 'Alexander Ovechkin', 'Bobby Orr', 'Sidney Crosby', 'Mario Lemieux')
('Wayne Gretzky', 'Alexander Ovechkin', 'Bobby Orr', 'Mario Lemieux', 'Sidney Crosby')
('Wayne Gretzky', 'Alexander Ovechkin', 'Sidney Crosby', 'Bobby Orr', 'Mario Lemieux')
('Wayne Gretzky', 'Alexander Ovechkin', 'Sidney Crosby', 'Mario Lemieux', 'Bobby Orr')
('Wayne Gretzky', 'Alexander Ovechkin', 'Mario Lemieux', 'Bobby Orr', 'Sidney Crosby')
('Wayne Gretzky', 'Alexander Ovechkin', 'Mario Lemieux', 'Sidney Crosby', 'Bobby Orr')
('Wayne Gretzky', 'Bobby Orr', 'Alexander Ovechkin', 'Sidney Crosby', 'Mario Lemieux')
('Wayne Gretzky', 'Bobby Orr', 'Alexander Ovechkin', 'Mario Lemieux', 'Sidney Crosby')
.
.
.
.
.
.
('Mario Lemieux', 'Bobby Orr', 'Alexander Ovechkin', 'Sidney Crosby', 'Wayne Gretzky')
('Mario Lemieux', 'Bobby Orr', 'Sidney Crosby', 'Wayne Gretzky', 'Alexander Ovechkin')
('Mario Lemieux', 'Bobby Orr', 'Sidney Crosby', 'Alexander Ovechkin', 'Wayne Gretzky')
('Mario Lemieux', 'Sidney Crosby', 'Wayne Gretzky', 'Alexander Ovechkin', 'Bobby Orr')
('Mario Lemieux', 'Sidney Crosby', 'Wayne Gretzky', 'Bobby Orr', 'Alexander Ovechkin')
('Mario Lemieux', 'Sidney Crosby', 'Alexander Ovechkin', 'Wayne Gretzky', 'Bobby Orr')
('Mario Lemieux', 'Sidney Crosby', 'Alexander Ovechkin', 'Bobby Orr', 'Wayne Gretzky')
('Mario Lemieux', 'Sidney Crosby', 'Bobby Orr', 'Wayne Gretzky', 'Alexander Ovechkin')
('Mario Lemieux', 'Sidney Crosby', 'Bobby Orr', 'Alexander Ovechkin', 'Wayne Gretzky')



Choosing Groceries with Combinations

Consider a situation where you’re at the grocery store and you’ve packed your cart full of awesome food. You get to the cash and realize you don’t have enough in your budget to buy everything in the cart! So you have some tough choices to make. On top of this, they’ve run out of bags and you decide that you can only carry 3 items in your cart. You’ve got some tough choices…

You decide that you want to look at this two ways:

  1. The healthiest 3 items that are within the budget.
  2. The tastiest 3 items that are within the budget.

Our budget is $15

To set this problem up I’m going to create a namedtuple class so that it’s more readable.

from collections import namedtuple
import itertools as it

# Declare namedtuple class with price, healthiness, and taste as attributes.
Food = namedtuple('Food' ,['name', 'price', 'healthiness', 'taste'])

# These are the items in our grocery cart!
pizza = Food('Pizza',6.99, 1, 10)
carrots = Food('Carrots', 2.99, 9, 3)
chips = Food('Chips', 4.99, 2, 9)
bananas = Food('Bananas', 0.99, 8, 7)
watermelon = Food('Watermelon', 6.99, 9, 9)
chicken = Food('Chicken', 10.99, 7, 7)
rice = Food('Rice', 5.29, 5, 5)
avocados = Food('Avocados', 1.99, 8, 7)

# We want to find all combinations of 3 from this list that are within budget.
cart = [pizza, carrots, chips, bananas, watermelon, chicken, rice, avocados]

on_budget=[]
# For all combinations of 3 in the cart...
for combo in list(it.combinations(cart, 3)):
    # If the total of the 3 items is less than our budget, add them to on_budget list.
    if sum([x.price for x in combo]) <=15:
        on_budget.append(combo)
        
for elem in on_budget:
    print([x.name for x in elem])

These are all the combinations that are within our budget

['Pizza', 'Carrots', 'Chips']
['Pizza', 'Carrots', 'Bananas']
['Pizza', 'Carrots', 'Avocados']
['Pizza', 'Chips', 'Bananas']
['Pizza', 'Chips', 'Avocados']
['Pizza', 'Bananas', 'Watermelon']
['Pizza', 'Bananas', 'Rice']
['Pizza', 'Bananas', 'Avocados']
['Pizza', 'Rice', 'Avocados']
['Carrots', 'Chips', 'Bananas']
['Carrots', 'Chips', 'Watermelon']
['Carrots', 'Chips', 'Rice']
['Carrots', 'Chips', 'Avocados']
['Carrots', 'Bananas', 'Watermelon']
['Carrots', 'Bananas', 'Chicken']
['Carrots', 'Bananas', 'Rice']
['Carrots', 'Bananas', 'Avocados']
['Carrots', 'Watermelon', 'Avocados']
['Carrots', 'Rice', 'Avocados']
['Chips', 'Bananas', 'Watermelon']
['Chips', 'Bananas', 'Rice']
['Chips', 'Bananas', 'Avocados']
['Chips', 'Watermelon', 'Avocados']
['Chips', 'Rice', 'Avocados']
['Bananas', 'Watermelon', 'Rice']
['Bananas', 'Watermelon', 'Avocados']
['Bananas', 'Chicken', 'Avocados']
['Bananas', 'Rice', 'Avocados']
['Watermelon', 'Rice', 'Avocados']

Kevin Vecmanis