# Basics

### 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]]
# 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
[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.
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
[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.
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