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
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 permutationss = ['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 elementss = "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?
- Using loops
- Recursion
- 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!