## Common Python Interview Questions - Part 1

January 21 2022

The goal of this series is to go through some of the algorithmic Python questions that get asked in interviews. It will be a practical hands-on approach with an emphasis on the code. The idea is to get a good developer brushed up quickly on these types of questions, rather than explain the theory behind them. Unlike an algorithm class in a CS curriculum, this is a code-first approach.

I haven't decided yet on how many parts in that series I would do, but each tutorial will handle 3 questions - and we will move progressively in difficulty.

I tried to balance simplicity (simple is better than complex after all!), code readability, and performance over magic 1-line solutions or even clever recursive ones. There is probably a better solution for these problems somewhere, I simply choose a good solution that I can easily explain.

## Fizzbuzz

Fizzbuzz is perhaps the simplest question out there. It essentially tests whether the candidate knows basic programming skills. To solve it, you need to know looping, the modulo operator, and simple list manipulation.

Here is the text of the question.

"*Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.*

Here is the code.

```
def fizzbuzz(n):
result = []
for i in range (1, n+1):
if i % 3 == 0 and i % 5 == 0:
result.append("FizzBuzz")
elif i % 3 == 0:
result.append("Fizz")
elif i % 5 == 0:
result.append("Buzz")
else:
result.append(i)
return result
print(fizzbuzz(100))
"""
[1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', ..., 97, 98, 'Fizz', 'Buzz']
"""
```

The trick here is knowing the special "%" symbol (modulo operator). This symbol returns the remainder of a division. For example 5 % 2 is equal 1. In other words, if we are dividing 5 apples among 2 people equally, each person would get 2 apples and 1 apple would remain. The modulo operator tells us the remainder of a division.

**Additional related questions:**

- What is 8 % 3? The Answer is 2 (we are dividing 8 apples among 3 people)
- What is 3 % 8? The Answer is 3 (we are dividing 3 apples among 8 people, since none of them can get a whole apple 3 apples would remain)

## TwoSum

The Two Sum problem is more advanced. The goal is to test whether the candidate recognizes the difference in performance between brute force looping solutions vs. taking advantage of Python's dictionaries. Dictionaries in Python take more space (memory) but offer very quick lookup. This is because a Python dictionary is a hash table.

This is a code-first tutorial, so I encourage you to research what is a hash table on your own if you never heard the term before and are curious. For all practical purposes, knowing that a dictionary is a hash table, and offers a very quick lookup is sufficient for most interviews.

Here is the text of the question.

"Given an array of integers (nums) and an integer (target), return the *i*ndices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the *same* element twice.

You can return the answer in any order."

Here is the code.

```
def two_sum(nums, target):
solution_dict = {}
for i in range(len(nums)):
x = nums[i]
match = target - x
if match in solution_dict:
return ([solution_dict[match], i])
else:
solution_dict[x] = i
return None
print (two_sum([1, 2, 3], 4))
# answer is [0,2]
# 0 is the index of 1, and 2 is the index of 3 and 1 + 3 = 4
```

Here is what we are doing.

- We initialize an empty dictionary that will hold our solution.
- We iterate through the array. The solution is asking for indices, so we want "i" and "range(len(array))", instead of the pythonic "for item in array".
- The question is essentially asking given that target = x + y, is x and y in the array?

We can change that around to say given that y = target - x, is y in the array? (the code has y as "match" for clarity).

4. Now - since we agreed to we going to take advantage of Python dictionaries for fast lookup. We want to construct our dictionary in that step. This the "solution_dict[x] = i" line

Our dictionary for an array of [1,2,3] would be, {1:0, 2:1, 3:2} - where the key is the number, and the value is the index of that number.

5. Lastly, instead of constructing our dictionary with all our numbers, then see where is our match. We can terminate the function when the match is found, and return the indices of the two numbers

Consider the simple case of the example array [1,2,3] - When our dictionary is at {1:0, 2:1} point, x would be 3, and y (match) would be 1 (4-3). If our y is in the dictionary, then we are done. We return the index of x (via accessing the current iteration of the loop), and the index of y (via dictionary lookup).

**Additional related questions:**

- A variation is to ask to return the numbers instead of the indices of the numbers. For that, we need to change how we constructed our dictionary, and return x instead of i.

```
if match in solution_dict:
return ([solution_dict[match], x]) #returned x, not i
else:
sol_dict[x] = x #constructed our dictionary as {1:1, 2:2}
```

## Remove Characters

The last question of this series is very similar to the previous question. The basic idea involves exploiting dictionaries for quick lookup instead of multiple loops. This is a common pattern for interview questions. Where looping over a list is a possible solution, but using a dictionary is preferred for performance.

Using the O notations, iterating over a list of n size is O(n) - in other words, as the list gets bigger, so would the time it takes to go through it. However, finding if an item is in a dictionary or not is O(1) - in other words, no matter how big the dictionary gets, it takes the same amount of time.

So, if you are in an interview and using a nested loop - and then get nudged to think of a better solution, immediately think about constructing a dictionary.

If you want to see the O notations for Python operations between lists and dictionaries, this is an excellent read

Here is the question text.

"An array of characters (arr) and a string (B) is given. Write a function to return the string B with all the characters from the array removed.

print (removeChars(['h', 'e', 'w', 'o'], 'hello world')) # => "ll rld" "

Here is the code.

```
def removeChars(arr, string):
lookup_dictionary = {}
for letter in arr:
lookup_dictionary[letter] = True
result = ''
for c in string:
if c not in lookup_dictionary:
result += c
return result
print (removeChars(['h', 'e', 'w', 'o'], 'hello world')) # => "ll rld"
```

Here is what we are doing,

- First, we initialize an empty dictionary that we will use for quick lookup
- Then, we construct that dictionary. For our example array ["h", "e", "w", "o"], our dictionary would look like this

{"h": True, "e": True, "w": True, "o": True}

3. Then, we build our result by looping through the string given and if we can't find the character (c) in our dictionary - we add it to the result.

That's it.

**Additional related questions:**

This is not strictly related since it has to do with how the Django ORM works rather than a general Python algorithm but in the same theme of optimizing how to find things.

- How would you improve this Django query:

```
entry = Entry.objects.get(pk=123)
if entry in some_queryset:
print("Entry contained in QuerySet")
```

This look up, would brute force the queryset looking for the entry. Not great.

An improvement would be using the exists() expression. Which optimizes the query for finding our entry, using more or less the same principles discussed above.

```
entry = Entry.objects.get(pk=123)
if some_queryset.filter(pk=entry.pk).exists():
print("Entry contained in queryset")
```

## Conclusion

We went through three common problems in technical interviews, FizzBuzz, Two Sum, and Removing Characters. The essential skill here is knowing the performance of looking up values via looping vs. using a dictionary.

Copyright © HTMX-Django 2022.

Built by Jonathan Adly. Contact for opportunities.