Basics
This page deals with Basic Python Questions
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.
Answer
# 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"))
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
Answer
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)
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]]
Answer
# Ref: https://stackoverflow.com/questions/58415182/function-that-find-combination-of-values-that-sums-to-a-given-number
def a(lst, target):
final_list = [] # list to store all the valid results
def _a(idx, li):
if target == sum(li): final_list.append(li)
elif target < sum(li): return
for u in range(idx, len(lst)):
_a(u , li + [lst[u]]) # recursive call
return final_list
return _a(0, []) # initial call
a([2,3,5],8)ython
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
Answer
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
buy = j
sell = max(li[i+1:])
print(j, max(li[i+1:]))
except:
print("end")
print(buy, sell, diff)
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
Answer
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'))
Given two sorted lists, write a function to merge them into one sorted list.
What’s the time complexity?
Answer
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)
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’] ]
Answer
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)
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.
Answer
nums = [0,1,2,4,5]
for i in range(0,len(nums)+1):
try:
if(nums[i+1]-nums[i]>1):
print("Missing nums --> ", i+1)
except:
pass
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)]
Answer
# 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))
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)]Answer
# 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)
a = [2,3,4,6, 6, 2,2] answer --> 2
Answer
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))
Implement an iterator function which takes three iterators as the input and sorts them.
Answer
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)
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
Answer
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
Explain Python recursion with an example.
Answer
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.
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 * 1041 <= nums[i] <= 10000 <= k <= 106
Answer
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
Last modified 3d ago