# 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 * 104`

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

`0 <= 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