##Khandane algo.

# Write an efficient program to find the sum of contiguous subarray

# within a one-dimensional array of numbers that has the largest sum.

arr = [-6, 4, -2, 3, -2, 4]

max_so_far = arr[0]
max_ending_here = arr[0]

for i in range(0,len(arr)):
max_ending_here = max(arr[i],max_ending_here+arr[i])
max_so_far = max(max_so_far,max_ending_here)

print(max_so_far)

#alternate:

maxhere,maxsofar = 0,float("-inf")

for i in range(len(arr)):
maxhere = maxhere + arr[i]
maxsofar = max(maxsofar,maxhere)

if maxhere <0:
maxhere = 0

print(maxsofar)

#kth largest elsement:

def kthlargestelement(arr,l,r,k):
if (k > 0 and k <= r-l+1):
pos = partition(arr,l,r)

if pos-l == k-1:
return arr[pos]

if (pos-l > k-1):

return kthlargestelement(arr,l,pos-1,k)

return kthlargestelement(arr,pos+1 , r , k-pos+l-1)

def partition(arr,l,r):
x = arr[r]
i=l
for j in range(l,r):
if arr[j] >= x:
arr[i],arr[j] = arr[j],arr[i]
i = i+1
arr[i],arr[r] = arr[r],arr[i]
return i
if __name__ == "__main__":

arr = [1, 3, 5, 7, 4, 19, 12]

n = len(arr)
k = 3
for k in range(1,k+1):
print("K'th smallest element is",
kthlargestelement(arr, 0, n - 1, k))

##reverse a int
n=123
rev = 0

while n!=0:
a = n%10
rev = rev*10 + a
n = n//10

print(rev)

#reverse string

s = ["h","e","l","l","o"]
str = ""
for i in s:
str = i+str
print(f"reverse string {str}")

#Alternative which return list of strings

left = 0
right = len(s)-1

while right >= left:

s[left],s[right] = s[right],s[left]
 left = left +1
right = right -1
print(f"list of reverse strings: {s}")

#string is palindrome or not

s = "momo"

def reverse(s):
str = ""
for i in s:
str = i+str
return s

if reverse(s) == s:
print("yes")
else:
print("no")

#duplicate char in string:

check_string = "hello"

count = {}
for s in check_string:
if s in count:
count[s] += 1
else:
count[s] = 1

for key in count:

if count[key] > 1:
print(f"duplicate: {key, count[key]}")

#TWO SUMS
nums = [2,3,4]
target = 6
ans = []

for i in range(len(nums)):
x = target - nums[i]
if x in nums:
x_index = nums.index(x)
if i != x_index:
 ans.append(i)
ans.append(x_index)
print(f"Two sum:{ans}")
break
else:
i = i+1

#Given a list of words, can you find out the frequency of each word?
from collections import Counter as c
from typing import Counter

lst = ['w','t','t']

lst1 = c(lst)
print(lst1)
for k,v in lst1.items():
print(f"for key {k} : {v} no of occurance")

#Given a list of numbers [1,2,3,4,5,6,7,8,9], print all the pairs for which the
summation of index positions is equal to 10

array = [1,2,3,4,5,6,7,8,9]
sum_of_index = 10
for i in range(int(sum_of_index/2)):
print(i)
if i < len(array) and sum_of_index-i-1 < len(array):
print((array[i], array[sum_of_index-i-1]))

#Find the Difference

s = "aa"
t="a"
len_s =len(s)
len_t =len(t)
s = c(s)
t = c(t)

if len_s > len_t:

for i in (s-t):
print(i)
else:
for i in (t-s):
print(i)
print("-"*10)
#Find the highest occuring number in the list, in case of tie return both
numbers.

lst = [2,4,3,5,2,6,3]

list_count= Counter(lst)
max_value = max(list_count.values())
print(list_count)
for k,v in list_count.items():
if v == max_value:
print(k)

print("-"*10)

#Given Two Arrays. Identify the common elements or not common element within them
A= [3, 2, 1]
B=[1, 4, 2]

A =Counter(A)
B= Counter(B)

#common

K = [k for k,v in A.items() if k in B]

print(K)

# not common
K = [k for k,v in A.items() if k not in B]
print(K)

print('-'*20)

#Given a string s, find the length of the longest substring without repeating
characters.

s = 'abcabcbc'

res = 0
word = ''

for i in s:
if i not in word:
word = word+i
 if len(word) > res:
res = len(word)

else:
word = word[word.find(i): ] + i
print
print(res)

#Closest Sum

MAX_VAL = 1000000000

#Prints the pair with sum closest to x

def printClosest(arr, n, x):

# To store indexes of result pair

res_l, res_r = 0, 0

#Initialize left and right indexes

# and difference between
# pair sum and x
l, r, diff = 0, n-1, MAX_VAL

# While there are elements between l and r

while r > l:
# Check if this pair is closer than the
# closest pair so far
if abs(arr[l] + arr[r] - x) < diff:
res_l = l
res_r = r
diff = abs(arr[l] + arr[r] - x)

if arr[l] + arr[r] > x:

# If this pair has more sum, move to
# smaller values.
r -= 1
else:
# Move to larger values
l += 1

print('The closest pair is {} and {}'

 .format(arr[res_l], arr[res_r]))

# Driver code to test above

if __name__ == "__main__":
arr = [10, 22, 28, 29, 30, 40]
n = len(arr)
x=54
printClosest(arr, n, x)

#find closest 2 numbers to the target

nums = [100, 999, 2, 3, 8, 9, 21, 33]

target = 4
d={}
for k,v in enumerate(nums):
m = abs(target - v)
d[m] = v
print(d)
print(f"Closest Sum: {sorted(value for key, value in d.items())[:2]}")

# Replace a Char in string with a Diff Char

#Given an array nums containing n distinct numbers in the range [0, n],
# return the only number in the range that is missing from the array.

nums = [3,0,1]

n = len(nums)
print(f"here: {n * (n+1) / 2 - sum(nums)}")

#2nd method
s = 0
s1 = 0
for i in range(len(nums)+1):
s = s+i

for i in nums:
s1 = s1 + i
print(s-s1)

print('-'*20)
#Given a string s, find the first non-repeating character in it and return its
index.
# If it does not exist, return -1.

s = "aab"

raw = {}
rep = {}

for i in range(len(s)):
if s[i] not in rep:
if s[i] not in raw:
raw[s[i]] = i
else:
raw.pop(s[i])
rep[s[i]] = 1
print(raw)
if len(raw) > 0:
print(min(raw.values()))
else:
print(-1)

#Given a string paragraph and a string array of the banned words banned, return
the most frequent word that is not banned.
# It is guaranteed there is at least one word that is not banned, and that the
answer is unique.
import re

paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]

paragraph=re.split('\W+',paragraph.lower())

words=Counter(paragraph)
for word in words.most_common():
if word[0] not in banned:
print(word[0])
break

# stack = []
# for char in s:
# if char in "({[":
# stack.append(char)
# elif char in ")}]":
# if stack == []:
# return False
# else:
# token = stack.pop(-1)
# if token == "(" and char != ")":
# return False
# elif token == "{" and char != "}":
# return False
# elif token == "[" and char != "]":
# return False

# return True if len(stack) == 0 else False

#Given two sorted arrays nums1 and nums2 of size m and n respectively, return the
median of the two sorted arrays.
#Using merge_sort
nums1 = [1,3]
nums2 = [2]
store = []
i = j = 0
k = len(nums1)
l = len(nums2)

while i < k and j < l:

if nums1[i] > nums2[j]:
store.append(nums2[j])
j = j+1
else:
store.append(nums1[i])
i = i+1

while i < k:
store.append(nums1[i])
i = i+1

while j < l:
store.append(nums2[j])
j = j+1

ln = len(store)
if ln%2 !=0:
print(int(store[ln//2])/1.0)

else:
print(int(store[ln//2]) + int(store[ln-1//2]))/2.0

#Add two number list

# resultlist = curr = ListNode() #we need two varibles because if only

one variable is used we might loose reference to the head

# # carry = 0
# # while l1 or l2 or carry: # not none
# # if l1 is not None:
# # carry += l1.val
# # l1 = l1.next #increase value of l1
# # if l2 is not None:
# # carry+= l2.val
# # l2 = l2.next
# # curr.next = ListNode(carry%10) #retur remainder of division
# # curr = curr.next
# # carry = carry//10 #returns floor value of division

# # return resultlist.next

#Merge two Array Linklist

# dummy = ListNode(0)
# cur = dummy
# while l1 and l2:
# if l1.val <= l2.val:
# cur.next = l1
# l1 = l1.next
# else:
# cur.next = l2
# l2 = l2.next
# cur = cur.next
# cur.next = l1 or l2
# return dummy.next

#Return the maximum profit you can achieve from this transaction. If you cannot
achieve any profit, return 0.
prices = [7,1,5,3,6,4]

n=len(prices)
for i in range(n-1):
prices[i]=prices[i+1]-prices[i]
print(prices)

# kadane Algo
MaxSum=0
Sum=0
for i in range(n-1):
Sum+=prices[i]
MaxSum=max(MaxSum,Sum)
if Sum<0:
Sum=0

if MaxSum<=0:
print("0")

print(MaxSum)

#Your task is to find the smallest possible length of a (contiguous) subarray of

nums, that has the same degree as nums.
nums = [1,2,2,3,1]

freq = Counter(nums)

degree = max(freq.values())
print(degree)
if degree == 1:
print('1')
solution = [n for n in freq if freq[n] == degree]
print(solution)

minlen = 50000 #constraint

for n in solution:
left = nums.index(n)

right = len(nums) - nums[::-1].index(n)

minlen = min(minlen, right-left)
print(minlen)
#Given a string s, return true if the s can be palindrome after deleting at most
one character from it.

s = "aba"
if s == s[::-1]:
print('True')

begin = 0
end = len(s) - 1

while begin < end:

if s[begin] == s[end]:
begin +=1
end -=1

else:
left_removal = s[begin+1:end+1]
right_removal = s[begin:end]

if left_removal == left_removal[::-1] or right_removal ==

right_removal[::-1]:
print('True')
else:
print('false')
print('True')

#Given a string s, return the longest palindromic substring in s.

s = "babad"

def helper(s, l, r) :
while l >= 0 and r < len(s) and s[l] == s[r] :
l -= 1
r += 1
return s[l+1:r]

ans = ''
for i in range(len(s)):

temp = helper(s, i, i)
if len(temp) > len(ans):
ans = temp
temp = helper(s, i, i+1)
if len(temp) > len(ans):
ans = temp
print(f"palindromic:{ans}")

#Write a function to find the longest common prefix string amongst an array of
strings.
#If there is no common prefix, return an empty string "".
# Input: strs = ["flower","flow","flight"]
# Output: "fl"

strs = ["flower","flow","flight"]
letters = list(zip(*strs)) # here we bring sequence of our strings to the
following format: [('f', 'f', 'f'), ...] - for sequence ["football", "fight",
"four"]
longest = [] # variable for the future result
for el in letters:
if len(set(el)) == 1: # if the length of a set is 1, then we admit that all
letters are the same
longest.append(el[0]) # use list, not string cause string will be
recreated again ang again and algorithm will take O(n*n) instead of O(n)
else: # if our letters are not equal, we are breaking from "for loop"
break
print(''.join(longest)) if longest else print('') # if longest is not empty - we
join it and return otherwise we return ""

# res = ""
# for i in range(len(min(strs))):
# for s in strs:
# if s[i] != strs[0][i]:
# print(res)
# break
# res += strs[0][i]
# print(res)

#Remove Duplicates from Sorted Array

nums = [1,1,2]

l = r = 1

for r in range(1, len(nums)):

if nums[r-1] != nums[r]:
nums[l] = nums[r]
l += 1
r += 1
print(l)
print(nums)

#Remove Element
nums = [3,2,2,3]
val = 3

for i in range(nums.count(val)): # loop how many val is in the list

nums.remove(val) # remove each val one by one
print(len(nums)) # return len of nums
print(nums)

#Find First and Last Position of Element in Sorted Array

nums = [5,7,7,8,8,10]
target = 8
l = 0
r = len(nums)-1

while(l<=r):

if nums[l] == nums[r] == target:

#print([l,r])
print([l,r])
break

if nums[l] != target:
l +=1
if nums[r] != target:
r -=1
#if not found
#print([-1,-1])

#Search Insert Position

nums = [1,3,5,6]
target = 5

left = 0
right = len(nums)-1
while left <= right:
pivot = left + (right - left)//2
if nums[pivot]==target:
 print(pivot)
break
elif nums[pivot] > target and nums[pivot-1]< target:
print(pivot)
break
elif nums[pivot] > target:
right = pivot-1
else:
left = pivot+1
#print(right+1)

arr = [4,3,1,2,3,4,5,7,5,3,2,4]
N = 4
newarr = []

for i in range(len(arr)-1):
if(arr[i]+1 == arr[i+1]):
newarr += [arr[i]]
if(len(newarr) == N):
break
else:
newarr = []

print(newarr)

#find mejority

def findMajority(arr, size):

m = {}
for i in range(size):
if arr[i] in m:
m[arr[i]] += 1
else:
m[arr[i]] = 1

print(m)
count = 0
for key in m:

if m[key] > size / 2:

count = 1
print("Majority found :",key)
break
if(count == 0):
print("No Majority element")
# Driver code
arr = [2, 2, 2, 2, 5, 5, 2, 3, 3]
n = len(arr)

# Function calling
findMajority(arr, n)

#Merge Sorted Lists

def merge_lists(list1, list2):

merged = []
n = 0
m = 0

while n < len(list1) and m < len(list2):

if list1[n] < list2[m]:
merged.append(list1[n])
n += 1
else:
merged.append(list2[m])
m += 1
(merged)
merged += list1[n:] + list2[m:]
print(merged)

# Driver code
list1 = [1,2,5]
list2 = [2,4,6]

# Function calling
merge_lists(list1, list2)

#Find the missing number

def missing_number(nums):
n = len(nums)
total = n*(n+1)/2

sum_nums = sum(nums)

if total == sum_nums:
return 0
else:
 return (total - sum_nums)

# Driver code
nums = [0,1,2,4,5]

# Function calling
print(missing_number(nums))

#first occurance of repeating letter

def find_repeat(w):
if len(w) == 0:
return None
if w[0] in w[1:]:
return w[0]
find_repeat(w[1:])

# Driver code
input = "interviewquery"
# Function calling
print(find_repeat(input))

#String Mapping

def str_map(string1, string2):

#if not same length then return false
if len(string1) != len(string2):
return False

m = dict()#create dictionary
for c1, c2 in zip(string1, string2):
if c1 not in m.keys():
m[c1] = c2
elif m[c1] != c2:
return False

for c1, c2 in zip(string2, string1):

if c1 not in m.keys():
m[c1] = c2
elif m[c1] != c2:
return False

return True

# Driver code
string1 = 'qwe'
string2 = 'asd'
# Function calling
print(str_map(string1, string2))

#shift string

def can_shift(a, b):

# Necessary condition has to be met

if len(a) != len(b):
return False

# Start from different position to check

for i in range(len(a)):
mut_a = a[i:] + a[:i]
if mut_a == b:
return True

return False

# Driver code
a = 'abcde'
b = 'cdeab'
# Function calling
print(can_shift(a, b))

def palindrome(input):
dict = {}
for i in input:
if i in dict:
dict[i]+= 1
else:
dict[i] = 1

flag = 0
for i in dict.values():
if i%2 != 0:
flag += 1

if flag > 1:
return False
 return True

# Driver code
str = 'carerac'
# Function calling
print(palindrome(str))

#Array Partition
# Input: nums = [1,4,3,2]
# Output: 4
# Explanation: All possible pairings (ignoring the ordering of elements) are:
# 1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
# 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
# 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
# So the maximum possible sum is 4.

nums = [1,4,3,2]
print(sum(sorted(nums)[::2]))

#Two Sum II - Input array is sorted

numbers = [2,7,11,15]
target = 9

l = 0
r = len(numbers)-1

while l < r:
if numbers[l]+numbers[r] == target:
print(l+1,r+1)
break
if numbers[l] + numbers[r] < target:
l = l+1
else:
r=r-1

#Remove Element
# Input: nums = [0,1,2,2,3,0,4,2], val = 2
# Output: 5, nums = [0,1,4,0,3,_,_,_]

nums = [0,1,2,2,3,0,4,2]
val = 2

k = 0
for i in range(len(nums)):
 if nums[i] != val:
nums[k] = nums[i]
k+=1
print(k)

#Max Consecutive Ones

# Input: nums = [1,1,0,1,1,1]
# Output: 3
nums = [1,1,0,1,1,1]
max_count = 0
count = 0

for num in nums:

if num == 1:
count +=1
max_count = max(count,max_count)
else:
count = 0
print(max_count)

# Input: s = "00110011"
# Output: 6
# Explanation: There are 6 substrings that have equal number of consecutive 1's
and 0's: "0011", "01", "1100", "10", "0011", and "01".
# Notice that some of these substrings repeat and are counted the number of times
they occur.
# Also, "00110011" is not a valid substring because all the 0's (and 1's) are not
grouped together.
s = "00110011"
acc = 1
occ=[]
res=0
for i in range(1,len(s)):
if s[i] == s[i-1]:
acc += 1
else:
occ.append(acc)
acc = 1
occ.append(acc)
print(occ)

for i in range(1,len(occ)):
res += min(occ[i],occ[i-1])
print(res)
#Given a string s, reverse only all the vowels in the string and return it.
s = "hello"

vow = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']

s = list(s)
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

if s[left] not in vow:

left +=1
if s[right] not in vow:
right -=1
print(''.join(s))

arr = [2,4,5,0,0,1,3,4,0,0,6]

temp_num = []
temp_zero = []
inti = 0

for i in range(len(arr)):
if arr[i] == 0:
temp_zero.append(arr[i])
inti +=1
else:
temp_num.append(arr[i])
inti +=1

for i in range(len(temp_num)):
temp_zero.append(temp_num[i])

print(temp_zero)

from collections import Counter as c

string = "I am back."

temp = c(string)
print(temp)

prices = [ 10.0 , 5.0 , 20.0]

budget=35
# total = 0
# item = 0
# for i in sorted(prices):
# total += i
# while total <= budget:

# print(total)
# item +=1
# break
# print(item)

item_cnt = 0
total = 0
print(enumerate(prices))
for i , v in enumerate(prices):
print(i)
print(v)
if total < budget and budget > v:
total += v
item_cnt += 1
print(item_cnt)

print("67")

str1="Firstly Firstly this is the first string"

str2= "Next is the second string"

count = {}

# insert words of string A to hash

for word in str1.split():
print(count.get(word, 0))
count[word] = count.get(word, 0) + 1

# insert words of string B to hash

for word in str2.split():
count[word] = count.get(word, 0) + 1
 # return required list of words
print([word for word in count if count[word] == 1])

input = [1,3,4,2,1,4,1]

list1 = Counter(input)
maxv = max(list1.values())
print({k:maxv-v for k,v in list1.items() if v < maxv})

word1= "Mmississippi"
c = 's'

count1 = {}

for i in word1:
if i in count1:
count1[i] += 1
else:
count1[i] = 1

print([v for k,v in count1.items() if k==c])

input_lst=[1,None,2,3,None,None,5,None]
left = 0

for i in range(len(input_lst)):
if input_lst[i] is None:
input_lst[i] = input_lst[left-1]
left+=1
else:
left+=1

print(input_lst)

#String is made of a-j and 0-9 where alphabets marks the opening and numbers as
closing

def solution(string):

ref =
{'0':'a','1':'b','2':'c','3':'d','4':'e','5':'f','6':'g','7':'h','8':'i','9':'j'}
 stk = []
cnt = 0
for i in string:
if i in ref and ref[i] in stk:
stk.pop(stk.index(ref[i]))
elif i in ref and ref[i] not in stk:
cnt+=1
else:
stk.append(i)

return len(stk) + cnt

# Driver code
string = 'ab00a'
# Function calling
print(solution(string))

def subString(string):
n = len(string)
return n*(n+1)/2

#a,b,c,ab,bc,abc (not ac becasue ac is not sub sequecne set of string)

string = 'abc'
print(subString(string))

def count(s,c):
count1 = {}

for i in s:
if i in count1:
count1[i] += 1
else:
count1[i] = 1
if c in count1:
for k,v in count1.items():
if k==c:
return v
else:
pass
else:
return 0
word= "Mississippi"
c= "s"
print(count(word,c))

def return_missing_balanced_numbers(input):
my_dict = {}
for i in input:
if i in my_dict:
my_dict[i] += 1
else:
my_dict[i] = 1
return {a:max(my_dict.values())-b for (a,b) in my_dict.items() if b!=
max(my_dict.values())}

lst = [1,2,[3,4, [5],[6,7,[8,[9]]]]]

def flatten_list(ip_list, op_list=[]):

for i in ip_list:
if isinstance(i, list):
flatten_list(i, op_list)
else:
op_list.append(i)
return op_list

ip_list = [1,2,[3,4, [5],[6,7,[8,[9]]]]]

print(flatten_list(ip_list))

def remove_dupes(ip_list):
op_dict={}
op_list=[]
for i in ip_list:
if i not in op_dict.keys():
op_dict[i] = 1
op_list.append(i)
return op_list

ip_list=[1,1,1,2,2]
print(remove_dupes(ip_list))
def nth_lowest(inp,n):
return sorted(inp.items(), key=lambda x: (-x[1], x[0]))[n - 1][0]

ip_list={'peter': 40,'mike': 90, 'sam': 60,'wohn': 90, 'jimmy': 32}

print(nth_lowest(ip_list,3))

from heapq import heappush

import collections

dic = collections.defaultdict(list)
h =[]
def calc(names ,n ) :
for k ,v in names.items() :
dic[v].append(k)
if v not in h :
heappush(h , v )

if n <= 0 or n > len(h) :

return 'error'
res = sorted(dic[h[-n]])
return res[0]
print(calc(ip_list,1))

def monotonic(arr):
inc=0
dec=0
for i in range(1,len(arr)):
if arr[i-1]< arr[i]:
inc += 1
elif arr[i-1]> arr[i]:
dec += 1
else:
inc += 1
dec += 1
if inc + 1 ==len(arr) or dec +1 ==len(arr):
return('Monotonic')
else:
return('Non-Monotonic')
lst = [7,9,5,2]
print(monotonic(lst))

def avgWordLength(words):
sum = 0
for i in range(len(words)):
sum += len(words[i])

return sum / len(words)

word = ["mango", "apple", "pineapple", "it", "pizza","corn"]

print(avgWordLength(word))

#find s in missisipi - print the index

string = "missisipi"

print([idx for idx, letter in enumerate(string) if letter == "s" ])

# for idx, letter in enumerate(string):
# if letter == "i":
# print(f"the index of i is: ", idx)

def return_mismatched_words(str1, str2):

# Write your code here
list1=str1.split()
list2=str2.split()

ctr_dict1=Counter(list1)
ctr_dict2=Counter(list2)

print(ctr_dict1)
print(ctr_dict2)

res=list((Counter(ctr_dict1) - Counter(ctr_dict2)).elements()) +
list((Counter(ctr_dict2) - Counter(ctr_dict1)).elements())
return res

lst = [None]
target = 30
srtl = sorted(lst)
sum = 0
count = 0
for i in range(len(srtl)):
sum += srtl[i]
if sum <= target:
count +=1
print(count)

array=[['D'],['A','B'],['A','C'],['C','A']]
def find_followers(arr):
dict = {}
for i in arr:
if i[0] not in dict:
dict[i[0]] = len(i)-1
else:
dict[i[0]] += len(i)-1
return dict

print(find_followers(array))

def validate(ip):
valid_digit=set('0123456789')
a=ip.split('.')
if len(a)!=4:
return False
for x in a:
if not x.isdigit():
return False
i=int(x)
if i < 0 or i> 255:
return False
return True

print(validate('127.0.0.0'))