Array
Missing element from a duplicated array
#Find the missing element from the given 2 arrays, second array is duplicate.
#array 1: [1,2,3,4,5,6,7]
#array2: [1,3,4,5,6,7] missing is 2
# Can I assume missing element is always from the second array?
# assume only element is missing and its always present in the first array, if not present can i just return NULL element or something
# So to confirm my fucntion takes two arrays of integers ?? as inputs and returns missing element or NULL
# it does not matter its integer array or any other type of array
# Appears from the input that array is sorted ? is it so?
a1 = [1,2,3,4,5,6,7] a2 = [1,3,4,5,6,7]
# special cases -
# first element could be missing or last element, no element missing
# compare the length of two arrays, check for empty array
def find_missing_element(a1, a2):
missing_element = None
l1 = len(a1)
l2 = len(a2) # o(1) stil
if a1 is None or a2 is None:
return None
if l1 == 0 or l2 == 0:
return None
if (l1-l2) != 1:
return None
sum_1 = 0
for i in range(0, l1):
sum_1 += a1[i]
sum_2 = 0
for i in range(0, l2):
sum_2 += a2[i]
missing_element = sum_1 - sum_2
return missing_element
missing_element = find_missing_element(a1, a2)
print (missing_element)
# Improvements need process whole array to find out the sum - not efficient, if more elements are missing then it becomes hard to reuse the code
def find_missing_element(a1, a2):
l1 = len(a1)
l2 = len(a2) # o(1) stil
if a1 is None or a2 is None:
return None
if l1 == 0 or l2 == 0:
return None
if (l1-l2) != 1:
return None
for i in range(0, l1):
if a1[i] != a2[i]:
return a1[i]
# o(n)
missing_element = find_missing_element(a1, a2)
print (missing_element)
# improvements - Binary search
def find_missing_element(a1, a2): # this is o(logn) - binray search one l1 = len(a1) l2 = len(a2) # o(1) stil lo = 0 hi = l1 - 1 while (lo < hi): mid = (lo + hi) // 2 if a1[mid] == a2[mid]: lo = mid else: hi = mid if lo == hi - 1: break return a1[hi] missing_element = find_missing_element(a1, a2) print (missing_element)
|
Write a program to display numbers having sum of left side numbers equal to right side numbers.
# {1,0,-11,1,12}=>0 {Left side number 1+0=1, Right side number -11+1+12=1}
s = [1, 0, -12, 1, 12]
l = len(s)
for i in range(1, l):
j = 0
left_sum = 0
right_sum = 0
while (j < i+1):
left_sum += s[j]
j = j + 1
while (j < l):
right_sum += s[j]
j = j + 1
if left_sum == right_sum:
print (s[0:i+1], s[i+1:l])
for i in range(1, l):
j = 0
left_sum = 0
right_sum = 0
for item in s[0:i+1]:
left_sum += item
for item in s[i+1:l]:
right_sum += item
if left_sum == right_sum:
print (s[0:i+1], s[i+1:l]) |
Write a program to display numbers having sum of left side numbers equal to right side numbers.
# {1,0,-11,1,12}=>0 {Left side number 1+0=1, Right side number -11+1+12=1}
# What should I do if entire list sum becomes zero which equals to [] can output be like [-5, 0, -12, 1, 12, 5, -1] []
s = [1, 0, -12, 1, 12]
l = len(s)
sum = 0
i = 0
while (i < len(s)):
sum += s[i]
i = i + 1
print ("total = ", sum)
left_sum = 0
right_sum = sum
for i in range(0, l):
left_sum += s[i]
right_sum -= s[i]
if left_sum == right_sum:
print (s[0:i+1], s[i+1:l]) |
Two sum problem
#Given an array of integers, return indices of the two numbers such that they add up to a specific target.
#You may assume that each input would have exactly one solution, and you may not use the same element twice.
list = [1, 2, 4, 6, 0, -1]
target = -1
def two_sum(list, target):
for i in range(0, len(list)):
j=i+1
for j in range(0, len(list)):
if list[i] + list[j] == target:
print i,j,list[i],list[j]
return i,j
(start, end) = two_sum(list, target)
print start, end
nums = [2, 1, 11, 15, 5, 4] sum = 9 d = {} for i in range(0, len(nums)): c = sum - nums[i] if c in d: print ("output is ", c, nums[i]) print ("index", i, d[c]) d[nums[i]] = i print (d)
#Another tech is binary search for compliment
|
Given a binary array {0,1,1,0,0,1,0,0,1} , sort the array in a way that all zeros come to the left and all the one's come to the right side of the array.
def solve(arr):
left=0
right=len(arr)-1
while left<right:
while left<right and arr[left]==0:
left+=1
while left<right and arr[right]==1:
right-=1
arr[left],arr[right]=arr[right],arr[left]
left+=1
right-=1
return arr XXXXXXXXXXXXXX for x in a: if x == 1: a.remove(1) a.append(1)
print (a) |
Sum of two arrays and merging
a = [1,2,3,4,8,9]
b = [4,8,9,4]
s = []
m = len(a)
n = len(b)
i = j = 0
while (i < m) and (j < n):
sum = a[i] + b[j]
while (sum > 0):
rem = sum % 10
sum = sum//10
s.append(rem)
i = i + 1
j = j + 1
while i < m:
s.append(a[i])
i = i + 1
while j < n:
s.append(b[j])
j = j + 1
print (s) |
Python slice
list = ["1", "2", "3", "4","5","6"]
print list[0:2]
print list[1:3]
print list[1:4]
print list[::-1] #reverse
print list[3:]
print list[:4]
print list[4:6]
print list[0::2] #odd number
print list[1::2] #even number
print list[-4:-1] #3,4,5
print list[-4:-2] #3,4 |
Smallest unique integer in an array
arr=[1, 2, 3, 1, 0, 1, 0]
seenonce = set()
seenmultiple = set()
for i in range(0,len(arr)):
if arr[i] in seenmultiple:
#print "seenmultiple", arr[i]
continue
if arr[i] in seenonce:
#print "remove and add", arr[i]
seenonce.remove(arr[i])
seenmultiple.add(arr[i])
else:
#print "add", arr[i]
seenonce.add(arr[i])
if seenonce is None:
print ("empty so return")
lowest = next(iter(seenonce))
print (lowest)
print (seenonce)
for item in seenonce:
if item < lowest:
lowest = item
print (lowest) |
Smallest unique integer in an array
arr=[1, 2, 3, 1, 0, 1, 0]
import collections
# iterating over list is o(n) and adding to set/dict is o(1)
# incase of collision worst case may be o(n)
c_dict = collections.Counter(arr)
new_list = []
#iterating each and every element o(n)
for key in c_dict:
#take unique nhbgvfc
if c_dict[key] == 1:
new_list.append(key)
new_list.sort() #merge sort on(logn)
print (new_list[0])
# Time complexity o(n) + o(n) + o(mlogm)
# So toal o(nlogn)
# space complexity - new_dict + new_list => worst case could be o(n) + o(m) |
Find the first and last occurrences of a number in a sorted array
a = [1,2,3,4,5,6,6,6,7]
x = 6 Output = 5 and 7
# find the first and last occurrences of a number in a sorted array
# Function for finding first and last # occurrence of an elements def findFirstAndLast(arr, n, x) : first = -1 last = -1 for i in range(0,n) : if (x != arr[i]) : continue if (first == -1) : first = i last = i if (first != -1) : print( "First Occurrence = " , first, " \nLast Occurrence = " , last) else : print("Not Found")
|
Maximum product of an array
# there could be -ve numbers
def maxProduct(arr, n):
# if size is less than 3, no triplet exists
if n < 3:
return -1
# Sort the array in ascending order
arr.sort()
# Return the maximum of product of last
# three elements and product of first
# two elements and last element
return max(arr[0] * arr[1] * arr[n - 1],
arr[n - 1] * arr[n - 2] * arr[n - 3]) |
Reverse an array by n items
#Reverse an array n = [1,4,2,0]
l = 0 r = len(n) - 1
while (l < r): n[l],n[r] = n[r],n[l] l = l + 1 r = r -1 print n ==== n = [1,4,2,0,8,9] x = 3 l = 0 r = 3 - 1
while (l < r): n[l],n[r] = n[r],n[l] l = l + 1 r = r -1 print n === n = [1,4,2,0,8,9] x = 3 # last 3 l = len(n) - x r = len(n) - 1
while (l < r): n[l],n[r] = n[r],n[l] l = l + 1 r = r -1 print n =================== arr = [1,2,3,4,5,6,8]
rev = []
l=len(arr)
for i in range (0,l):
rev.append(arr[l-1])
l = l - 1
print (rev)
#Reverse an array by n items
n = 5
for i in range(0, n):
ele = arr.pop(n-1)
print ("fsd", i, ele)
arr.insert(i, ele)
print (arr)
#Reverse an array by n items using extra array arr = [1,2,3,4,5,6,8] rev = [] n = 3 i = n while (i > 0): rev.append(arr[i-1]) i = i - 1
while (n < len(arr)): rev.append(arr[n]) n = n + 1 print (rev)
|
Minimum delta of two arrays
a = [2,3,1,6,9]
b = [11,3,5,8]
#find the minimum delta of two arrays
#smallest diff btn a-b or b-a
a.sort()
b.sort()
print (a)
print (b)
l = len(a) - 1
delta = max ((a[l] - b[0]), (b[0] - a[l]))
print (delta) |
Maximum number of consecutive 1s
a = [1,0,0,0,1,1,0,1,1,1,1]
#output shall be 4 because 1 repeated twice consecutively
#maximum number of consecutive 1's
max_count = 0
count = 0
for num in a:
if num == 1:
count += 1
if max_count < count:
max_count = count
else:
count = 0
print (max_count) |
Merge two sorted arrays
a = [0, 1,1,3,4]
b = [1,4,6,7,8,8]
c = []
i = j = k = 0
n = len(a)
m = len(b)
while ((i<n) and (j<m)):
print (i,j)
if a[i] <= b[j]:
c.append(a[i])
i = i + 1
else:
c.append(b[j])
j = j + 1
while (i<n):
c.append(a[i])
i = i + 1
while (j<m):
c.append(b[j])
j = j + 1
print (c) |
Write a code to return a value 'True' if the number '1' throughout the array appears consecutively. Ex: S = {1,1,1,0,0,3,4}.
#Else, return 'False' if the array does not have the given number (char = '1' in this case) in the consecutive order. Ex: S = {1,1,0,0,1,3,4}
# arary ?, +1 and -1, start and end (rotate), int or decimal or long, chars, what is the numbr is there only once, what if that number does not exist
S1 = [1,1,1,0,0,3,4], [9,1,1,9,1], [1,1,1,0,0,1], [9,9,1,1,1], [9,9,1,1,1,0,0,0]
S = [9,9,1,1,1,0,0,0]
key = 1
found = False
could_be_invalid = False
if len(S) <=0:
print "False"
if len(S) == 1 and S[0] == key:
print "True"
if len(S) > 1 and S[0] == key and S[1] != key:
print "False"
for num in S:
if num==key:
found=True
if found == True and key != num:
could_be_invalid = True
if could_be_invalid == True and key==num:
found = False
print (found) |
Rotate array by x numbers
a = [1,2,3,4,5]
#expcted [4,5,1,2,3]
r = 5
i = 0
while (i < r):
x = a.pop()
a.insert(0, x)
i = i + 1
print (a)
Compute array intersection
#Each element in the result must be unique. The result can be in any order.
#nums1 = [1,2,2,1], nums2 = [2,2]
#nums1 = [4,9,5], nums2 = [9,4,9,8,4]
class Solution:
def set_intersection(self, set1, set2):
return [x for x in set1 if x in set2]
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
set1 = set(nums1)
set2 = set(nums2)
if len(set1) < len(set2):
return self.set_intersection(set1, set2)
else:
return self.set_intersection(set2, set1)
n1 = [4,8,4,5,4,5]
n2 = [5,3,4,5,4,5]
set1 = set(n1)
set2 = set(n2)
out = []
for x in set1:
if x in set2:
out.append(x)
print (out) |
Subsets array using pattern
#you have to come up with a program that will give all possible subsets of the array #based on the pattern. Pattern restrictions were the string array should start with 1 and #end with 1. So there will be many sub arrays like from index 0 to 3 and 0 to 4 and #index 7 to 9
arr = [1,0,0,1,1,0,0,1,0,1,0,0,0,1]
for i in range(0, len(arr)):
if arr[i] == 1:
for j in range(i+1, len(arr)):
if arr[j] == 1:
print (arr[i:j+1]) |
Find the second largest
n = [10,2,3,4,8,3,3,9]
first = -234
sl = -234
for item in n:
if item > first:
sl = first
first = item
if item > sl and item != first:
sl = item
print (sl) |
Strings
Count of each words
str = ["ambika", "ambika", "goat", "dog", "doga", "sheep"]
dict = {}
for item in str:
if item in dict:
dict[item] += 1
else:
dict[item] = 1
for key in dict:
print dict[key], key |
Anagram of strings
def anagram(s1, s2):
s1 = s1.replace(' ','').lower()
s2 = s2.replace(' ','').lower()
if len(s1) != len(s2):
return False
#if sorted(s1) == sorted(s2):
# return True
d = {}
for letter in s1:
if letter in d:
d[letter] += 1
else:
d[letter] = 1
for letter in s2:
if letter in d:
d[letter] -= 1
else:
d[letter] = 1
for counter in d:
if d[counter] != 0:
return False
return True
s1="clint eastwood"
s2="old west action"
print anagram(s1, s2) |
Print even length words in a string
str = "Amb bhat abhi baleg"
strWords = str.split(" ")
for word in strWords:
#print word
if len(word) % 2 != 0:
print "Even word - ", word |
Remove duplicates
str = ['a','a','b','c','g','g','h','g']
if str is "" or str is None:
print ("invalid")
if len(str) <= 0:
print ("invalid")
if len(str) == 1:
print ("no duplicates")
str.sort()
l = len(str)
i = 1
while (i < l):
if str[i] == str[i-1]:
str.remove(str[i])
l = l - 1
else:
i = i + 1
print (str) |
My Class example
class MyClass:
def __init__(self, car=9):
self.car = car
def func(self, car=0):
print car
print self.car
def main():
obj = MyClass()
obj.func(788)
if __name__=="__main__":
main()
|
Palindrome
#str = "A man, a plan, a canal: Panama"
str = "race a car"
str="mvdflk"
import re
if not str.strip():
print "emepty"
str = re.sub(r"[^a-zA-Z0-9]+",' ',str)
str=str.replace(" ","").lower()
print str
rev = str[::-1]
if str == rev:
print "PALINDROME", str
else:
print "Not palindrome - ", rev |
Regular expression
import re
str = "Ambika Bhat Ambika"
str1 = re.search("^Ambika.*Ambika$",str)
print str1
try:
txt = "ss rain in Spain"
x = re.search("^The.*Spain$", txt)
print x.start()
except:
print "exception" |
Remove ith cchar in a string
str = "geeks for geeks"
new_str = " "
#remove 2nd char
for i in range(0, len(str)):
if i!=2:
new_str = new_str + str[i]
print new_str
#----
g = "geoks gee"
l = list(g)
l.pop(1)
s = ''.join(l)
print s |
str = "geeks for geeks"
new_str = " "
#remove 2nd char
for i in range(0, len(str)):
if i!=2:
new_str = new_str + str[i]
print new_str
#----
g = "geoks gee"
l = list(g)
l.pop(1)
s = ''.join(l)
print s |
Reverse each word in a given string
str = "hello how are you all"
# reverse list of words
# suppose we have list of elements list = [1,2,3,4],
# list[0]=1, list[1]=2 and index -1 represents
# the last element list[-1]=4 ( equivalent to list[3]=4 )
# So, inputWords[-1::-1] here we have three arguments
# first is -1 that means start from last element
# second argument is empty that means move to end of list
# third arguments is difference of steps
str_list = str.split(" ")
rev = " "
inputwords = " "
inputwords = str_list[-1::-1]
#join concatenates iterable items in the list, also separator can be added
rev = ','.join(inputwords)
print str_list
print inputwords
print rev |
check for substring
str = "Ambika Bhat Balegadde Sirsi #$$"
sub_str = "#$$"
if str.find(sub_str) == -1:
print "No"
else:
print "Yes"
|
Maximum occurred char
# HO HELLO
# H appeared 2 and its 1st occurrence
import collections
def check_max_occurrences(str):
str_dict = collections.Counter(str)
max = 0
str_len = len(str)
out = ""
for char in str:
if str_dict[char] > max:
max = str_dict[char]
out = char
return out
str = "HO HELLO"
char = check_max_occurrences(str)
print (char) |
Remove uncommon char
s1 = "string"
s2 = "strong"
out = ""
for c in s1:
for c1 in s2:
if c==c1:
out += c1
print (out) |
import collections
s1 = "string"
s2 = "strong"
d = {}
d = collections.Counter(s1)
for c in s2:
if c in d:
d[c] -= 1
else:
d[c] = 1
out = []
for c in s1:
if d[c] != 1:
out.append(c)
' '.join(out)
print (out)
# o(n) + o(m) + o(n) Time
# o(n) for dict and o(m) for list I should reduce one for loop check below
|
To print common chars
s1 = "string"
s2 = "strong"
d={}
for c in s1:
if c in d:
d[c] += 1
else:
d[c] = 1
print (d)
for c2 in s2:
if c2 in d:
print (c2) |
Compress / decompress problem
#wwwgetzz ==> w3getz2
#speace remove
def is_letter(char):
if (char >= 'a' and char <= 'z') or (char >= 'A' and char <= 'Z'):
return True
return False
s = "www getzzii "
s = s.replace(" ","")
#s = " ".join(s.split())
import collections
d = collections.Counter(s)
out = " "
for key in d:
out += key
if d[key] > 1:
out += str(d[key])
print (out)
new_out = " "
last_char = " "
for char in out:
if is_letter(char):
new_out += char
lastchar = char
else:
num = ord(char) - ord('0')
print (num)
while (num > 0):
new_out += lastchar
num = num - 1
print (new_out) |
Reversing string
s = "ambika"
# Python hack print (s[::-1]) # For loop
rev =""
for i in range(len(s)-1,-1,-1):
rev += s[i] # While loop
rev = ""
i = len(s) - 1
while i >= 0:
rev += s[i]
i = i - 1
print (rev) |
Reversing the order of words in a sentence
s = "ambika hello hi"
a = s.split(" ")
l = 0
r = len(a) - 1
while (l<r):
a[l],a[r] = a[r],a[l]
l = l + 1
r = r - 1
print (a) ss = " ".join(a) |
Reversing from given index
a = "ambikabhat"
n = 4
rev = ""
len = len(a)
i = n - 1
while (i>=0):
rev += a[i]
i = i - 1
i = n
while (i<len):
rev += a[i]
i = i + 1
print(rev) |
Sum of only numbers in a string
import re
str1 = "ab10rt200r1"
s = re.findall('\d+',str1)
sum = 0
for item in s:
sum = sum + int(item)
print ("sum=",sum) |
temp = "0"
sum = 0
str1 = "ab10rt200r1"
for char in str1:
if (char.isdigit()):
temp = temp + char
else:
sum = sum + int(temp)
temp = "0"
sum = sum + int(temp)
print (sum) |
Print the middle char of the string
str2 = "amazon"
str_len = len(str2)
mid = str_len//2
if (str_len % 2 == 0):
#even length
print ("even", str2[mid-1:mid])
else:
# odd length
print (str2[mid]) |
Find the maximum consecutive occurrence of a character in a given string.
#For example for the given input string of "Amazon is a great company as it haas AtoooZzz" and the output should be "o"
#s = "Amazon is a great company as it haas AtoooZzz"
s = "nnnnd oo"
s = s.replace(" ", "")
if s == "" or s == " ":
print ("empty")
if len(s) == 1:
print ("fjshd", s[0])
print (s)
max_count = 0
cur_count = 1
max_char = s[0]
for i in range(0,len(s)-1):
if s[i] == s[i+1]:
cur_count += 1
if cur_count > max_count:
max_count = cur_count
max_char = s[i]
else:
cur_count = 1
print (max_char) |
String to palindrome conversion keeping original string intact
str = "zxy"
def convert_to_palindrome(str):
l = len(str)
pali = " "
start = 0
# Find how many times first char has repeated
start = 1
rev = str[start:l]
rev = rev[::-1]
pali = rev + str
return pali
pali = convert_to_palindrome(str)
print (pali) === s = "BABABAA" cnt = 0 flag = 0 while(len(s) > 0): # if string becomes palindrome then break if(ispalindrome(s)): flag = 1 break else: cnt += 1 # erase the last element of the string s = s[:-1] # print the number of insertion at front if(flag): print(cnt)
|
Hashmap
Sets
Verify if S2 = {5,8,2} is a subset of S1 = {1,5,4,6,8,2} and S3 = {5,8,2,7} is not a subset of S1.
# all elements in a given subset is part of another set or not
# set - unordered, but unique
# only integers? if yes -ve numbers ?
# string, chars, unicode?
# empty sets
# True or False
# S2 and S3 are two different inputs ?
S2 = {5,8}
S1 = {1,5,4,6,8,2}
S3 = {5,8,2,7}
def findSubset(S1, S2, S3):
for item in S2:
if item not in S1:
print ("False")
print ("True")
for item in S3:
if item not in S1:
print ("False")
findSubset(S1, S2, S3) |
Matrix
Merge two dimensional array into a string or single list
li = [[0,1,2],[3,4,5],[6,7,8]]
li1 = []
for row in li:
for col in row:
li1.append(col)
print (li1)
li2 = [ col for row in li for col in row]
print (li2) |
# sum up all elements in the matrix
a = [[1, 2, 3],
[5, 6, 7],
[8, 9, 10]]
sum = 0
for i in range(0,len(a)):
for j in range(0,len(a)):
print (a[i][j])
sum = sum + a[i][j]
print (sum) |
Linkedlist
Mathematical
Clock angle problem
time = "3.15"
hr = 360/12
min = 360/60
h = int(time.split(".")[0])
m = int(time.split(".")[1])
#how did 0.5 came
#60 mins 30 (==> 360/60 * 5) degreee
#1 mins ?
h_angle = h * hr + (m * 0.5)
m_angle = m * min
print(h_angle)
print(m_angle) |
Function for nth Fibonacci number
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==1:
return 0
# Second Fibonacci number is 1
elif n==2:
return 1
else:
return Fibonacci(n-1)+Fibonacci(n-2) |
X to the power y
x = 2
y = 4
mul = 1
while (y > 0):
mul = mul * x
y = y - 1
print (mul) |
Mul withut using *
x = 0
y = -4
mul = 0
if x == 0 or y == 0:
mul = 0
for i in range(0, abs(y)):
mul = mul + abs(x)
if (x < 0 and y < 0) or (x > 0 and y > 0):
mul = mul
else:
mul = -mul
print (mul) |
Sum of n numbers
def sum(n):
s = 0
for i in range((n+1)):
s += i
return s
def sum1(n):
return (n*(n+1))/2
print sum(10)
print sum1(10)
|
Triangle *
n = m = 5
for i in range(0, n):
for j in range(0, m):
print ("*", end=" ")
print ("\r")
m = m - 1
n = 5
for i in range(0, n):
for j in range(0, i+1):
print ("*", end=" ")
print ("\r") |
Comments
Post a Comment