# Basics

There are some common programming techniques that you must be familiar with if you want to be comfortable enough to solve Python questions live during an interview. Here we have summarized a few of such techniques but do hone your skills using platforms like Leet code to ensure that you perform well during interviews.

We have collated some resources from the internet as a starting point to help you prepare on this:

### Questions

[SNAPCHAT] Palindrome Checker

Given a string, determine whether any permutation of it is a palindrome.

For example, carerac should return true, since it can be rearranged to form racecar, which is a palindrome. sunset should return false, since there’s no rearrangement that can form a palindrome.

``````# A string can be a palindrome only if it has even pair of characters and at max 1 odd character
def palindrome(x):
char_dict = {}
for i in x:
# we will check if the element exists else we will add it to the dictionary
try:
char_dict[i] = char_dict[i] + 1
except:
char_dict.update({i:1})
# next we will create a list of element counts and use list comprehension
# to check if odd element count is 1 and rest all even
check = list(char_dict.values())
if (len([temp for temp in check if temp%2==1]) == 1 and len([temp for temp in check if temp%2==0]) > 1):
return "palindrome"
else:
return "not palindrome"

print(palindrome("carerac"))
print(palindrome("abc"))``````
Pattern Generation

Write a function to generate this pattern: 1 2 3 4 5 6

Now change the code to output 1 1 2 1 2 3

``````def pyramid(n):
counter = 1
max = 1
while(max<n):
for i in range(max, max+counter): # for the second pattern change max to 1
print(i, end=" ")
max=max+1
counter=counter+1
print(" ")

pyramid(6)``````
[UBER] Sum to N

Given a list of positive integers, find all combinations that equal the value N.

Example:

integers = [2,3,5], target = 8,

output = [[2,2,2,2],[2,3,3],[3,5]]

We will solve it in 2 ways, one using itertools the other one using recursion:

``````def combinationSum(candidates, target):
def traverse(candid, arr, sm):                  # arr : an array that contains the accused combination; sm : is the sum of all elements of arr
if sm == target: ans.append(arr)            # If sum is equal to target then add it to the final list
if sm >= target: return                     # If sum is greater than target then no need to move further.
for i in range(len(candid)):                # we will traverse each element from the array.
traverse(candid[i:], arr + [candid[i]], sm+candid[i])   #most important, splice the array including the current index, splicing in order to handle the duplicates.
traverse(candidates,[], 0)
return ans

combinationSum([2, 3, 5], 8)``````
``````import itertools
integers = [2,3,5]
target = 8
final = []
# output = [[2,2,2,2],[2,3,3],[3,5]]

max = target//min(integers)
for i in range(1,max+1):
a = list(itertools.combinations_with_replacement(integers,i))
for k in a:

if sum(list(k)) == target:
final.append(k)

print(final)``````
[STARBUCKS] Max Profit

Given a list of stock prices in ascending order by datetime, write a function that outputs the max profit by buying and selling at a specific interval.

Example:

stock_prices = [10,5,20,32,25,12]

buy –> 5 sell –> 32

``````li = [10,5,20,32,25,12]
diff = 0
for i,j in enumerate(li):
try:
if(diff<(max(li[i+1:])-j)):
diff = max(li[i+1:])-j
sell = max(li[i+1:])
print(j, max(li[i+1:]))
except:
print("end")

[IBM] Isomorphic string check

Write a function which will check if each character of string1 can be mapped to a unique character of string2.

Example: string1 = ‘donut’ string2 = ‘fatty’

string_map(string1, string2) == False # as n and u both get mapped to t

string1 = ‘enemy’ string2 = ‘enemy’

string_map(string1, string2) == True # as e’s get mapped to e even though there is two e

string1 = ‘enemy’ string2 = ‘yneme’

string_map(string1, string2) == False # as e’s dont get mapped uniquely

``````def string_map(string1, string2):
if(string1==string2):
status = True
elif(len(string1)!=len(string2)):
status = False
else:
tempstore = {}
for i,j in enumerate(string1):
if(j in tempstore):
if(tempstore[j] != string2[i]):
status = False
break
elif(string2[i] in tempstore.values()):
status = False
break
else:
tempstore[j] = string2[i]
status = True
return status

print(string_map('enemy', 'enemy'))
print(string_map('enemy', 'yneme'))
print(string_map('cat', 'ftt'))
print(string_map('ctt', 'fat'))
print(string_map('cat', 'fat'))``````
[WORKDAY] Sorted String merge

Given two sorted lists, write a function to merge them into one sorted list.

What’s the time complexity?

``````def mergeArrays(arr1, arr2):

n1 = len(arr1)
n2 = len(arr2)
arr3 = [None] * (n1 + n2)
i = 0
j = 0
k = 0
# Traverse both array
while i < n1 and j < n2:
# Check if current element of first array is smaller than current element of second array.
# If yes, store first array element and increment first array index. Otherwise do same with second array

if arr1[i] < arr2[j]:
arr3[k] = arr1[i]
k = k + 1
i = i + 1
else:
arr3[k] = arr2[j]
k = k + 1
j = j + 1

# Store remaining elements
# of first array
while i < n1:
arr3[k] = arr1[i];
k = k + 1
i = i + 1

# Store remaining elements
# of second array
while j < n2:
arr3[k] = arr2[j];
k = k + 1
j = j + 1
print("Array after merging")
for i in range(n1 + n2):
print(str(arr3[i]), end = " ")

arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
mergeArrays(arr1, arr2)

# Next coming to the time complexity it is linear as the execution time of the algorithm grows in direct proportion to the size of the data set it is processing.
# For merging two arrays, we are always going to iterate through both of them no matter what,
# so the number of iterations will always be m+n and the time complexity being O(m+n) where m = len(arr1) and n = len(arr2)``````
[POSTMATES] Weekly Aggregation

Given a list of timestamps in sequential order, return a list of lists grouped by week (7 days) using the first timestamp as the starting point.

Example:

ts = [ ‘2019-01-01’, ‘2019-01-02’, ‘2019-01-08’, ‘2019-02-01’, ‘2019-02-02’, ‘2019-02-05’, ]

output = [ [‘2019-01-01’, ‘2019-01-02’], [‘2019-01-08’], [‘2019-02-01’, ‘2019-02-02’], [‘2019-02-05’] ]

``````ts = [
'2019-01-01',
'2019-01-02',
'2019-01-08',
'2019-02-01',
'2019-02-02',
'2019-02-05',
]

from datetime import datetime as dt
from itertools import groupby

first = dt.strptime(inp[0], "%Y-%m-%d")
out = []

for k, g in groupby(ts, key=lambda d: (dt.strptime(d, "%Y-%m-%d") - first).days // 7 ):
out.append(list(g))

print(out)``````
[MICROSOFT] Find the missing number

You have an array of integers of length n spanning 0 to n with one missing. Write a function that returns the missing number in the array

Example:

nums = [0,1,2,4,5] missingNumber(nums) -> 3

Complexity of O(N) required.

``````def missingNumber(nums):

diff = 0
miss_num = []
for i, j in enumerate(nums):
try:
t_diff = nums[i+1]-nums[i]
if t_diff>0:
for k in range(i+1,i+t_diff):
# print(k)
miss_num.append(k)
except:
pass
return miss_num

nums = [0,1,2,5,6]
missingNumber(nums)``````
[SQUARE] Book Combinations

You have store credit of N dollars. However, you don’t want to walk a long distance with heavy books, but you want to spend all of your store credit.

Let’s say we have a list of books in the format of tuples where the first value is the price and the second value is the weight of the book -> (price,weight).

Write a function optimal_books to retrieve the combination allows you to spend all of your store credit while getting at least two books at the lowest weight.

Note: you should spend all your credit and getting at least 2 books, If no such condition satisfied just return empty list.

Example:

``````N = 18
books = [(17,8), (9,4), (18,5), (11,9), (1,2), (13,7), (7,5), (3,6), (10,8)]

def optimal_books(N, books) -> [(17,8),(1,2)]``````

``````# Let's take this step by step
import itertools

def optimal_books(N, books):
print("(Price,Weight) details of books: ",books)
print("Store Credit: ",N)
final_books = [] # empty list to store the final books
# sorting the books by weight as we need the lightest books
sorted_books = sorted(books, key = lambda x:x[1])
price = [i[0] for i in sorted_books] #list of prices sorted by weight

for i in range(2,len(price)+1):
templist = (list(itertools.combinations(price,i))) # generating all combinations of price
res = [sum(j) for j in templist] # summing individual combination to get total price of each combination
if N in res: # if the result matches traceback traceback and append the combination
tempbooks = (templist[res.index(N)])
for k in tempbooks:
final_books.append(sorted_books[price.index(k)])
break

return final_books

N = 18
books = [(17,8), (9,4), (18,5), (11,9), (1,2), (13,7), (7,5), (3,6), (10,8)]
print("Best Combination: ",optimal_books(N,books))``````
[WISH] Intersecting Lines

Say you are given a list of tuples where the first element is the slope of a line and the second element is the y-intercept of a line.

Write a function find_intersecting to find which lines, if any, intersect with any of the others in the given x_range.

Example

`tuple_list = [(2, 3), (-3, 5), (4, 6), (5, 7)] x_range = (0, 1)`

Output

`def find_intersecting(tuple_list, x_range) -> [(2,3), (-3,5)]`

``````# for 2 lines to intersect the formulas used here are:
# y = mx + c
# x = (c2-c1)/(m1-m2)
# https://www.cuemath.com/geometry/intersection-of-two-lines/ Check this link for details of the formula

def intersectinglines(tuple_list,x_range):
output=[]
for i in range(len(tuple_list)):
for j in range(i+1,len(tuple_list)):

x = (tuple_list[j][1]-tuple_list[i][1])/(tuple_list[i][0]-tuple_list[j][0])
y = tuple_list[j][1]*x+tuple_list[j][0]

if x>=x_range[0] and x<=x_range[1]:
output.extend([tuple_list[i],tuple_list[j]])
return output

tuple_list = [(2, 3), (-3, 5), (4, 6), (5, 7)]
x_range = (0, 1)

intersectinglines(tuple_list, x_range)``````
Find the majority element in a list.

a = [2,3,4,6, 6, 2,2] answer --> 2

``````a = [2,3,4,6, 6, 2,2]

def major_ele(x):
counter_dict = {}
for i in a:
if i not in counter_dict:
counter_dict.update({i:1})
else:
counter_dict[i] =  counter_dict[i] + 1
for i,j in counter_dict.items():
if j == max(list(counter_dict.values())):
return i

print(major_ele(a))``````
[INTUIT] Iterator

Implement an iterator function which takes three iterators as the input and sorts them.

2 Solutions are provided below:

``````import heapq

def sorted_merge(*iterators):
# Use heapq.merge to merge and sort the input iterators
sorted_iterator = heapq.merge(*iterators)

# Return the sorted iterator
return sorted_iterator

# Example usage:
if __name__ == "__main__":
# Create three sorted iterators (lists in this case)
iterator1 = iter([1, 3, 5, 7])
iterator2 = iter([2, 4, 6, 8])
iterator3 = iter([0, 9, 10])

# Merge and sort the iterators
sorted_iterator = sorted_merge(iterator1, iterator2, iterator3)

# Iterate through the sorted values
for value in sorted_iterator:
print(value)
``````
``````def sort_iterators(it1, it2, it3):
"""Sorts three iterators.

Args:
it1: The first iterator.
it2: The second iterator.
it3: The third iterator.

Returns:
An iterator that yields the sorted elements of the three iterators.
"""
# Create a list to store the elements of the three iterators.
elements = []

# Iterate over the three iterators and add the elements to the list.
for element in it1:
elements.append(element)
for element in it2:
elements.append(element)
for element in it3:
elements.append(element)

# Sort the list.
elements.sort()

# Create an iterator that yields the elements of the sorted list.
return iter(elements)``````
[SPLUNK] Last Page Number

We're given a string of integers that represent page numbers.

Write a function to return the last page number in the string. If the string of integers is not in correct page order, return the last number in order.

``````input = '12345'
output = 5

input = '12345678910111213'
output = 13

input = '1235678'
output = 3``````

``````def get_last_page(int_string):
print(int_string)
count = 0
counter2 = 0
for i in int_string:
count = count+1+counter2//10
counter2 = counter2+1
if(str(counter2)==int_string[count-1:count+counter2//10]):
pass
else:
return counter2-1``````
Python Recursion

Explain Python recursion with an example.

Recursion is a programming technique that allows a function to call itself. This can be useful for solving problems that involve self-similar structures, such as trees and graphs.

``````def factorial(n): # 6! = 6*3*2*1
if(n==0 or n==1): # define the base case
return 1
return factorial(n-1)*n # recursively call the func

factorial(6)``````

This function works by calling itself recursively to calculate the factorial. The base cases are when n is 0 or 1, in which case the function simply returns n.

Recursion can be a powerful tool, but it is important to use it carefully. If a recursive function is not designed carefully, it can easily lead to stack overflows.

[INTUIT] Subarray Product Less Than K

This was asked in INTUIT Sr. Data Scientist initial round using Glider

Given an array of integers `nums` and an integer `k`, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than `k`.

Example 1:

``````Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.``````

Example 2:

``````Input: nums = [1,2,3], k = 0
Output: 0``````

Constraints:

• `1 <= nums.length <= 3 * 104`

• `1 <= nums[i] <= 1000`

• `0 <= k <= 106`

You are not only required to solve the problem in a limited time frame (~30mins) but the ask is also to ensure that the all test-cases pass and at least one of them fails if the code does not meet the required time complexity even if you get the required answer.

``````class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], max_product: int) -> int:
result = 0
for i in range(1, len(nums)):
for j, l in enumerate(nums):
temp = nums[j:j+i]
res = 1
for m in temp:
res = m*res
if(res<max_product and len(temp)==i):
result +=1
return result``````

The above code fails some test cases as it has O(n^3) complexity. There is the two-pointer or inchworm approach given below which solves the problem along with taking care of the complexity. Click on the Leetcode link above and check the discussions if you want to understand it better:

``````class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], max_product: int) -> int:
left = 0
result = 0
product = 1

for right in range(len(nums)):
product *= nums[right]

if product >= max_product:
while product >= max_product and left <= right:
product /= nums[left]
left += 1

result += right - left + 1

return result``````

Reverse Vowels in a String

Given a string `s`, reverse only all the vowels in the string and return it.

The vowels are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`, and they can appear in both lower and upper cases, more than once.

Example 1:

``````Input: s = "hello"
Output: "holle"``````

Example 2:

``````Input: s = "leetcode"
Output: "leotcede"``````

This can be solved using the 2-pointer approach:

``````class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vow = "aeiouAEIOU"
left = 0
right = len(s)-1
while left < right:
if s[left] in vow and s[right] in vow:

s[left], s[right] = s[right], s[left]

left += 1; right -= 1

elif s[left] not in vow:
left += 1

elif s[right] not in vow:
right -= 1
return ''.join(s)``````
Swap numbers

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example:

``````Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]``````

``````class Solution:
def moveZeroes(self, nums: list) -> None:
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0 and nums[slow] == 0:
nums[slow], nums[fast] = nums[fast], nums[slow]

# wait while we find a non-zero element to
# swap with you
if nums[slow] != 0:
slow += 1``````

Algorithm complexity: Time complexity: O(n). Our fast pointer does not visit the same spot twice. Space complexity: O(1). All operations are made in-place

[SALESFORCE] Interpolation

``````x = [25, 50, 100]
y = [5.0, 4.0, 3.0]

def interporlate(n):
if(n in x):
return y[x.index(n)]
elif(n > x[-1]):
x_t = x[-1]-x[-2]
y_t = y[-1]-y[-2]
return y[-1] + (y_t / x_t * (n-x[-1]))
elif(n < x[0]):
x_t = x[0]-x[1]
y_t = y[0]-y[1]
return y[0] + (y_t / x_t * (n-x[0]))
else:
for i,j in enumerate(x):
if n<j:
break
x_t = x[i-1]-x[i]
y_t = y[i-1]-y[i]
return y[i-1] + (y_t / x_t * (n-x[i-1]))

print(interporlate(50))
print(interporlate(150))
print(interporlate(25))
print(interporlate(75))``````
[SALESFORCE] Prison Problem

``````def prison(size, x, y):
x_t = list(range(0,6,1))
y_t = list(range(0,6,1))
x_t = [a for a in x_t if a not in x]
y_t = [a for a in y_t if a not in y]

# accounting for the outer walls, we will add 0 as starting
# and add +1 to all others
x_t = list(map(lambda t: t + 1, x_t))
y_t = list(map(lambda t: t + 1, y_t))
x_t.insert(0,0)
y_t.insert(0,0)

max_x = 1
max_y = 1

for i,j in enumerate(x_t):
try:
if(max_x< x_t[i+1]-j):
max_x = x_t[i+1] -j
except:
pass

for i,j in enumerate(y_t):
try:
if(max_y< y_t[i+1]-j):
max_y = y_t[i+1] -j
except:
pass

return "Max cell size: ", max_x*max_y

prison(5, [3, 2], [0, 1, 3])``````

Last updated