Strings Manipulation
1. Reverse Integer
# Given an integer, return the integer with reversed digits.
# Note: The integer could be either positive or negative.
#--------------------------------------------------------------------
# Name: Reverse Integer
# Purpose: Multiple solutions for reversing an Integer
# such that -123 -> -321 and 543 -> 345
#
# Author: jlai
#
# Created: 24/09/2020
# Copyright: (c) jlai 2020
# Licence: <your licence>
#--------------------------------------------------------------------
def solution(n):
return int(f"{str(n)[::-1]}") if n>0 else int(f"-{str(abs(n))[::-1]}")
def solution1(x):
string = str(x)
if string[0] == '-':
return int('-'+string[:0:-1])
else:
return int(string[::-1])
def solution1a(x):
string = str(x)
return int('-'+string[:0:-1]) if string[0] == '-' else int(string[::-1])
def solution2(n):
n1 = int(n)
if n1 <0:
neg = True
else:
neg = False
n1 = abs(n1)
ns = str(n1)
ns = ns[::-1]
# ns = ''.join(list(ns).reverse())
if neg:
return f"-{ns}"
else:
return ns
def solution3(n):
neg = False
if n[0]=="-":
neg = True
n = n[1:]
n = n[::-1]
if neg:
n = "-"+n
return n
# recursive
def solution4(n):
ns = str(n)
#print(ns)
if len(ns)==1:
return ns
if ns[0]=="-":
return "-"+ solution4(ns[2:]) + ns[1]
else:
return solution4(ns[1:]) + ns[0]
print(solution1(-321))
print(solution1(543))
2. Average Words Length
# For a given sentence, return the average word length.
# Note: Remember to remove punctuation first.
sentence1 = "Hi all, my name is Tom...I am originally from Australia."
sentence2 = "I need to work very hard to learn more about algorithms in Python!"
def solution(sentence):
for p in "!?',;.":
sentence = sentence.replace(p, '')
words = sentence.split()
return round(sum(len(word) for word in words)/len(words),2)
print(solution(sentence1))
print(solution(sentence2))
Object Oriented Python version:
import re
class Sentence:
sentence = ""
def __init__(self):
self.sentence = self.loadSentence()
def loadSentence(self):
while True:
sentence = input("Enter your sentence: ")
sentence = self.strip1(sentence)
print(f"You entered: {sentence}({len(sentence)})")
if len(sentence) > 0:
break
else:
print(f"Try again! <{self.sentence}> not appropriate: ")
return sentence
def strip1(self, sentence):
'''
The [] create a list of chars. The ^ negates the list. A-Za-z are the English alphabet and is space. For any one or more of these (that is, anything that is not A-Z, a-z, or space,) replace with the empty string.
'''
return re.sub(r'[^A-Za-z0-9 ]+', ' ', sentence).replace(" ", " ")
def getAverageWordLength(self):
print(f"get Average Word Length of: {self.sentence}")
l = (self.sentence).split()
n = len(l)
print(l, n)
t = 0
for word in l:
t += len(word.strip())
return t/n
def getSentence(self):
return self.sentence
s = Sentence()
print(s.getSentence())
print(s.getAverageWordLength())
3. Add Strings
# Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
# You must not use any built-in BigInteger library or convert the inputs to integer directly.
#Notes:
#Both num1 and num2 contains only digits 0-9.
#Both num1 and num2 does not contain any leading zero.
num1 = '364'
num2 = '1836'
# Approach 1:
def solution(num1,num2):
eval(num1) + eval(num2)
return str(eval(num1) + eval(num2))
print(solution(num1,num2))
#Approach2
#Given a string of length one, the ord() function returns an integer representing the Unicode code point of the character
#when the argument is a unicode object, or the value of the byte when the argument is an 8-bit string.
def solution(num1, num2):
n1, n2 = 0, 0
m1, m2 = 10**(len(num1)-1), 10**(len(num2)-1)
for i in num1:
n1 += (ord(i) - ord("0")) * m1
m1 = m1//10
for i in num2:
n2 += (ord(i) - ord("0")) * m2
m2 = m2//10
return str(n1 + n2)
print(solution(num1, num2))# Approach 3
nums = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
numDict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4,
'5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
num1 = '364'
num2 = '1836'
n1 = 0
n2 = 0
x = 0
# first num using array
for n in num1[::-1]:
for i in range(10):
nx = (i * 10**x) if n == nums[i] else 0
n1 += nx
x += 1
# second num using dictionary
x = 0
for n in num2[::-1]:
n2 += numDict[n]*10**x
x += 1
print(n1, n2, n1+n2)
4. First Unique Character
# Given a string, find the first non-repeating character in it and return its index.
# If it doesn't exist, return -1. # Note: all the input strings are already lowercase.
#Approach 1
def solution(s):
frequency = {}
for i in s:
if i not in frequency:
frequency[i] = 1
else:
frequency[i] +=1
for i in range(len(s)):
if frequency[s[i]] == 1:
return i
return -1
print(solution('alphabet'))
print(solution('barbados'))
print(solution('crunchy'))
print('###')
#Approach 2
import collections
def solution(s):
# build hash map : character and how often it appears
count = collections.Counter(s) # <-- gives back a dictionary with words occurrence count
#Counter({'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1})
# find the index
for idx, ch in enumerate(s):
if count[ch] == 1:
return idx
return -1
print(solution('alphabet'))
print(solution('barbados'))
print(solution('crunchy'))
5. Valid Palindrome
# Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
# The string will only contain lowercase characters a-z.
s = 'radkar'
def solution(s):
for i in range(len(s)):
t = s[:i] + s[i+1:]
if t == t[::-1]: return True
return s == s[::-1]
solution(s)
Arrays
6. Monotonic Array
This is another very frequently asked problem and the solution provided above is pretty elegant as it can be written as a one-liner. An array is monotonic if and only if it is monotone increasing, or monotone decreasing and in order to assess it, the algorithm above takes advantage of the all() function that returns Trueif all items in an iterable are true, otherwise it returns False. If the iterable object is empty, the all() function also returns True.
# Given an array of integers, determine whether the array is monotonic or not.
A = [6, 5, 4, 4]
B = [1,1,1,3,3,4,3,2,4,2]
C = [1,1,2,3,7]
def solution(nums):
return (all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1)) or
all(nums[i] >= nums[i + 1] for i in range(len(nums) - 1)))
print(solution(A))
print(solution(B))
print(solution(C))
7. Move Zeroes
#Given an array nums, write a function to move all zeroes to the end of it while maintaining the relative order of
#the non-zero elements.
array1 = [0,1,0,3,12]
array2 = [1,7,0,0,8,0,10,12,0,4]
def solution(nums):
for i in nums:
if 0 in nums:
nums.remove(0)
nums.append(0)
return nums
solution(array1)
solution(array2)
8. Fill The Blanks
# Given an array containing None values fill in the None values with most recent
# non None value in the array
array1 = [1,None,2,3,None,None,5,None]
def solution(array):
valid = 0
res = []
for i in nums:
if i is not None:
res.append(i)
valid = i
else:
res.append(valid)
return res
solution(array1)
9. Matched & Mismatched Words
#Given two sentences, return an array that has the words that appear in one sentence and not
#the other and an array with the words in common.
sentence1 = 'We are really pleased to meet you in our city'
sentence2 = 'The city was hit by a really heavy storm'
def solution(sentence1, sentence2):
set1 = set(sentence1.split())
set2 = set(sentence2.split())
return sorted(list(set1^set2)), sorted(list(set1&set2)) # ^ A.symmetric_difference(B), & A.intersection(B)
print(solution(sentence1, sentence2))
10. Prime Numbers Array
# Given k numbers which are less than n, return the set of prime number among them
# Note: The task is to write a program to print all Prime numbers in an Interval.
# Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
n = 35
def solution(n):
prime_nums = []
for num in range(n):
if num > 1: # all prime numbers are greater than 1
for i in range(2, num):
if (num % i) == 0: # if the modulus == 0 is means that the number can be divided by a number preceding it
break
else:
prime_nums.append(num)
return prime_nums
solution(n)
