# 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!

• 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

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:

##### 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.

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.

#### 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….
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:

('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.

These are all the combinations that are within our budget

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