Interview Tips: Python

If you are preparing for coding interviews, then you must have comes across two set of problems very frequently…

• Given a set or list of items find a sub set that matches some criteria: Combinations
• Given a set or list of items find different arrangements of the items: Permutations

https://calcworkshop.com/functions-statistics/permutations-combinations/

Many of us seen this in our high school and no way of escaping it, right?

And till data I confuse with these terms! Nevertheless in interviews we need solve the given problem one way or other as quick as possible, right?

Sample problems

Permutations

Problem: How do you find all the permutations of a string?

Input: (‘A’, ‘B’, ‘C’)

Output: (‘B’, ‘C’, ‘A’) (‘B’, ‘A’, ‘C’) (‘C’, ‘B’, ‘A’) (‘C’, ‘A’, ‘B’) (‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’)

Combinations

Problem: Given a list of integers S and a target number k, write a function that returns a subset of S that adds up to k. If such a subset cannot be made, then return null.

Input: [12, 1, 61, 5, 9, 2], k= 24

Output: [12, 9, 2, 1]

Solutions

Permutations:

Using in-build Python APIs

from itertools import permutations
s = ['A','B','C']
print(f"Permutations of {s} is")
for p in permutations(s):
    print(p, end=" ")
#ouput
Permuation of ['A', 'B', 'C'] is
('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')

Combinations

Using in-build Python APIs

from itertools import combinations
# unlike permutation API, combination API needs one extra param for number of items to consider while combining elements
s = "ABC"
print(f"Combination of {s} is")
for i in range(len(s)+1): # +1 if we wanted to add entire sequence
    for c in combinations(s,i):
        print(c, end=" ")
print(" ")
# output
# Combination of ABC is
# () ('A',) ('B',) ('C',) ('A', 'B') ('A', 'C') ('B', 'C') ('A', 'B', 'C')

def find_numbers(l, total):
    for i in range(len(l)+1): # +1 if we wanted to add entire sequence
        for c in combinations(l, i):
            if sum(c) == total:
                print(c)

find_numbers([12, 1, 61, 5, 9, 2], 24)
#output
#(12, 1, 9, 2)

Okay…How about other approaches for these problems, instead of using in-build calls?

1. Using loops
2. Recursion
3. Backtracking : Recursion + Loop

Check out these reference links for implementation:

• https://www.geeksforgeeks.org/combinations-in-python-without-using-itertools/
• https://www.geeksforgeeks.org/generate-all-the-permutation-of-a-list-in-python/

Happy coding!