prudent_programmer
BAN USER@sbdul Thank you so much.Nice catch. I didn't consider the edge cases and consider if the islands are stringed together or if they lie near the boundaries. I fixed my code and use DFS for searching through the grid and remove the islands as necessary. I have attached the rewritten code in Python below.
Solution:
def removeIslands(islandsMatrix):
rows, cols = len(islandsMatrix), len(islandsMatrix[0])
def dfs(i, j):
# Check if the coordinate is a boundary
if i in [0, rows-1] or j in [0, cols-1]:
return True
# Check if the coordinate is invalid
if i < 0 or i >= rows \
or j < 0 or j >= cols \
or islandsMatrix[i][j] != '1':
return False
islandsMatrix[i][j] = '#' # Use '#' for marking
coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
# If you find that all four sides are surrounded by water
# then remove the islands by setting it to 0
if not any(dfs(x, y) for x,y in coordinates):
islandsMatrix[i][j] = '0'
else: # Else, set it to 1
islandsMatrix[i][j] = '1'
for i, row in enumerate(islandsMatrix):
for j, sq in enumerate(row):
dfs(i, j)
return islandsMatrix
Test code:
from pprint import pprint
islands1 = [
['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '1', '1', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(islands1))
print('--'* 20)
island2 = [
['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '1', '1', '0', '1', '1'],
['1', '0', '1', '0', '0', '0', '1'],
['1', '1', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']
]
pprint(removeIslands(island2))
Output:
[['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']]
----------------------------------------
[['1', '1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1', '1'],
['1', '0', '0', '0', '0', '0', '1'],
['1', '1', '0', '0', '0', '1', '1'],
['1', '1', '1', '1', '1', '1', '1']]
For this problem, I am assuming we can modify the original matrix. In that case, scan through the islands matrix, and if we find an island that is surrounded by islands, remove it by setting it to 0. I present my solution in Python below. TC:- O(n*m) where n and m represents the number of rows and cols. SC:- O(1) since we are modifying the matrix in-place.
My solution:
def removeIslands(islandsMatrix):
rows, cols = len(islandsMatrix), len(islandsMatrix[0])
def isCoordinateWater(i, j):
return 0 <= i < rows and 0 <= j < cols and islandsMatrix[i][j] == '0'
for i, row in enumerate(islandsMatrix):
for j, sq in enumerate(row):
if sq == '1':
coordinates = [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
if all([isCoordinateWater(x, y) for x, y in coordinates]):
islandsMatrix[i][j] = '0'
return islandsMatrix
Test Code:
islands = [
['1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '1', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '1', '1', '1', '1', '1']
]
from pprint import pprint
pprint(removeIslands(islands))
'''
Output:
[
['1', '1', '1', '1', '1', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '0', '0', '0', '0', '1'],
['1', '1', '1', '1', '1', '1']
]
'''
Maintain a variable for totalSum and another variable for carry. Add the value based on the head of the linked lists. Keep iterating while there is another node in the linked list or there is a carry. TC:- O(n+m) where n and m are the size of the linked lists. SC:- O(n+m) since we are constructing a new linked list and returning it. My solution in Python:
def addTwoNums(head1, head2):
carry = 0
curr = dummy = Node(None)
while head1 or head2 or carry:
totalSum = 0
if head1:
totalSum += head1.value
head1 = head1.next
if head2:
totalSum += head2.value
head2 = head2.next
totalSum += carry
carry = totalSum // 10
curr.next = Node(totalSum % 10)
curr = curr.next
return dummy.next
Test code:
# Test code
class Node:
def __init__(self, value):
self.value = value
self.next = None
def printList(head):
while head != None:
print(head.value, end='->')
head = head.next
num1 = Node(4)
num1.next = Node(5)
num1.next.next = Node(6)
num2 = Node(7)
num2.next = Node(8)
num2.next.next = Node(9)
result = addTwoNums(num1, num2)
printList(num1)
print('\n+')
printList(num2)
print('\n' + ('-'*10))
printList(result)
num1 = Node(4)
num1.next = Node(5)
num2 = Node(1)
num2.next = Node(2)
num2.next.next = Node(3)
result = addTwoNums(num1, num2)
print('\n\n')
printList(num1)
print('\n+')
printList(num2)
print('\n' + ('-'*10))
printList(result)
Output:
4->5->6->
+
7->8->9->
----------
1->4->6->1->
4->5->
+
1->2->3->
----------
5->7->3->
Based on your question, the problem is asking us to find the celebrity given the person list and the person number. So, this can be done in O(N+N) = O(N) time where N = number of rows/cols. If this was problem was finding the celebrity given the matrix, then it would be a different problem. I present a solution in Python below.
I assume I am given an adjacency matrix. My solution in Python:
def determineCelebrity(peopleList, person):
# Scan the adjacency matrix
actualPersonIndex = person - 1
# Scan the cols and make sure everyone knows the person
for i in range(len(peopleList)):
if i != actualPersonIndex and peopleList[i][actualPersonIndex] != 1:
return False
# Make sure the celebrity knows no one else in the party
return all(x == 0 for x in peopleList[actualPersonIndex])
Test code:
celebrityMatrix = \
[
[0, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 1, 0, 1, 0, 1],
[0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 0]
]
print(determineCelebrity(celebrityMatrix, 5)) # False
print(determineCelebrity(celebrityMatrix, 2)) # True
print(determineCelebrity(celebrityMatrix, 3)) # False
Maintain two pointers, start and end and sequentially go through the string comparing characters. If you notice a special character, then increment start pointer or decrement end pointer. Posting my solution in Python below.
Solution:
from string import punctuation
def isPalindrome(inputStr):
inputStr = inputStr.lower()
start, end = 0, len(inputStr) - 1
while start <= end:
if inputStr[start] in punctuation:
start += 1
continue
if inputStr[end] in punctuation:
end -= 1
continue
if inputStr[start] != inputStr[end]:
return False
start += 1
end -= 1
return True
print(isPalindrome('L*&EVe)))l')) # True
This popular problem is known as the Josephus Problem. If the problem asked us to find the last person standing, it could in fact be solved in constant O(1) time using a mathematical formula. However, since the problem asks us for the last TWO people remaining, we have to capture the intermediate results. To perform this, I construct a circular linked list which represents the circle in which the criminals stand and then simulate the killing.
Finally, I capture intermediate results in a stack and then to pop the last two results to obtain the last two men standing alive. The time complexity of this algorithm would be O(N) where N = the number of criminals. The space complexity would O(N/2) roughly since we capture the results of approximately half of the criminals using the stack.
Solution code in Python below :
class Node:
def __init__(self, data):
self.data = data
self.next = None
def josephusCircle(n):
# Simple Cases
if n == 1: return [1]
if n == 2: return [1, 2]
# Create circular linked list
# for n >= 3
head = Node(1)
curr = head
for i in range(2, n+1):
newCriminalNode = Node(i)
curr.next = newCriminalNode
curr = newCriminalNode
curr.next = head
# Go through the circular linked list
# and kill every other criminal by setting
# criminal.next to be criminal.next.next
curr = head
resultStack = []
while curr.next != curr:
resultStack.append(curr.data)
curr.next = curr.next.next
curr = curr.next
lastCriminal = resultStack.pop()
penultimateCriminal = resultStack.pop()
return [penultimateCriminal, lastCriminal]
Test code:
print(josephusCircle(5)) # [5,3]
print(josephusCircle(6)) # [1, 5]
print(josephusCircle(7)) # [3,7]
print(josephusCircle(10)) # [9, 5]
As @NoOne pointed out, the problem is extremely trivial if we take the assumption that we use the int() function. However, if we are not allowed to do so, then we have to add strings and use subtraction to get the integer value for each character in the string (this is similar to the atoi function approach). I have outlined both solutions below. I am making an assumption that we can still use string functions (since that's our input) and I use one another iterable function.
Simple solution (using int)
def addNumbersUsingSumFunction(numericStrings):
return str(sum(int(numString) for numString in numericStrings))
Adding Strings Solution (without using int())
import itertools
def addNumbers(numericStrings):
reversedNums = [list(number)[::-1] for number in numericStrings]
result = ''
carry = 0
for ind, digits in enumerate(itertools.zip_longest(*reversedNums, fillvalue='0')):
innerSum = carry
for digit in digits:
innerSum += ord(digit) - ord('0')
carry = innerSum // 10
result += str(innerSum % 10)
if carry:
result += str(carry)
return result[::-1]
Test Code:
print(addNumbersUsingSumFunction(['199', '1', '1'])) # 201
print(addNumbersUsingSumFunction(['999', '99', '9'])) #1107
print(addNumbersUsingSumFunction(['333', '333', '334'])) #1000
print(addNumbers(['199', '1', '1'])) # 201
print(addNumbers(['999', '99', '9'])) #1107
print(addNumbers(['333', '333', '334'])) #1000
Kind of challenging to do this from scratch by writing algorithms, but using in-built libraries, we can come up with elegant code that gets the job done! :) For this problem, we need to use a mix of dictionaries/hashmaps + combinations generator + max-heaps. If we were doing this from scratch, obviously, this would amount to a lot of code! Therefore, I have outlined an elegant solution below.
Elegant solution in Python below:
import itertools
from collections import defaultdict
import heapq
class Product:
def __init__(self, aisleId, productId, price):
self.aisleId = aisleId
self.productId = productId
self.price = price
def getKHighestPrices(products, k):
# Structure of the data structure will be as follows:
# Aisle IDs: [Prices]
aisleMap = defaultdict(list)
for product in products:
aisleMap[product.aisleId].append(product.price)
heap = []
for combination in itertools.product(*aisleMap.values()):
# The negation is for max-heaps
heapq.heappush(heap, (-sum(combination), combination))
result = []
while k > 0:
priceList = heapq.heappop(heap)[1]
formattedStringPriceList = ','.join([('$%s' % price) for price in sorted(priceList,reverse=True)])
result.append(formattedStringPriceList)
k = k - 1
return result
Test code:
# Aisle 1 Products
p11 = Product(1,100,4)
p12 = Product(1,101,2)
p13 = Product(1,102,5)
# Aisle 2 Products
p21 = Product(2, 200, 1)
p22 = Product(2, 201, 6)
totalProducts = [p11, p12, p13, p21, p22]
print(getKHighestPrices(totalProducts, 2)) #['$6,$5', '$6,$4']
print(getKHighestPrices(totalProducts, 5)) #['$6,$5', '$6,$4', '$6,$2', '$5,$1', '$4,$1']
import random
def simulateBiasedCoin(p):
if random.randint(1,100) < p*100:
return "Heads"
else:
return "Tails"
simulateBiasedCoin(0.67)
The outer loop runs for O(N-1) where N is the length of your input string and the inner loop runs for O(13). So the total runtime is O(N-1 * 13) => O(13N-13) => O(N). Therefore, I think the time complexity would be Linear time.
Since you are using a temporary buffer, charArray, to modify and keep track of the changes, I think that the space complexity would be O(N) also.
Question unclear. Please clarify and provide an example.
- prudent_programmer March 08, 2018from string import ascii_lowercase, punctuation
from collections import defaultdict
def isPanagram(sentence):
sentence = sentence.lower()
letterCount = defaultdict(int)
for letter in ascii_lowercase:
letterCount[letter] = 0
for letter in sentence:
if letter in punctuation:
continue # Skip special characters / punctuation marks
letterCount[letter] += 1
missingLetters = [letter for letter, count in letterCount.items() if count == 0]
if len(missingLetters) == 0:
print('The sentence is a panagram!')
else:
print('The sentence is not a panagram and is missing the letters: ', missingLetters)
isPanagram('Fox nymphs grab quick-jived waltz.')
isPanagram('The quick fox.')
isPanagram('The five boxing wizards jump quickly.')
isPanagram('The five boxing wizards jump.')
Below I present the exhaustive search recursion solution and the much improved top-bottom solution using memoization.
Exhaustive Search using Recursion
# Recursion. Time Complx:- 2^(n+m)
def printPath(matrix):
def isSafe(i, j, prevValue):
return 0 <= i < len(matrix) and \
0 <= j < len(matrix[0]) \
and matrix[i][j] != prevValue
def findHelper(i, j, prevValue, path):
if i == len(matrix) - 1 and j == len(matrix[0]) - 1 \
and prevValue != matrix[i][j]:
path.append(str((i, j)))
return True
if isSafe(i, j, prevValue):
path.append(str((i, j)) + '-> ')
if findHelper(i, j+1, matrix[i][j], path):
return True
if findHelper(i+1, j, matrix[i][j], path):
return True
path.pop()
return False
return False
path = []
res = findHelper(0, 0, -1, path)
if len(path) == 0:
print('No path found from source to destination')
else:
print('Path found and the path is %s' % (''.join(path)))
Recursion + Memoization (Aka Top-Down Approach)
# Recursion + Memoization. Takes O(n+m).
# Use dictionary to store all the path's values
def printPathWithMemoization(matrix):
pathMemo = {}
def isSafe(i, j, prevValue):
return 0 <= i < len(matrix) and 0 <= j < len(matrix[0]) \
and matrix[i][j] != prevValue
def findHelper(i, j, prevValue, path):
if (i, j) in pathMemo:
return pathMemo[(i, j)]
if i == len(matrix) - 1 and j == len(matrix[0]) - 1 \
and prevValue != matrix[i][j]:
path.append(str((i, j)))
pathMemo[(i, j)] = True
return True
if isSafe(i, j, prevValue):
path.append(str((i, j)) + '-> ')
if findHelper(i, j+1, matrix[i][j], path):
pathMemo[(i, j)] = True
return True
if findHelper(i+1, j, matrix[i][j], path):
pathMemo[(i, j)] = True
return True
path.pop()
pathMemo[(i, j)] = False
return False
return False
path = []
res = findHelper(0, 0, -1, path)
if len(path) == 0:
print('No path found from source to destination')
else:
print('Path found and the path is %s' % (''.join(path)))
Test code:
matrix = \
[
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
matrix2 = \
[
[1, 0, 0],
[0, 1, 1],
[0, 0, 0],
]
matrix3 = \
[
[1, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 1, 0]
]
from pprint import pprint
pprint(matrix)
printPath(matrix)
printPathWithMemoization(matrix)
printPath(matrix2)
printPathWithMemoization(matrix2)
printPath(matrix3)
printPathWithMemoization(matrix3)
Elegant Python Solution:
from collections import Counter
def stringCounts(words):
for word in words:
c = Counter(word)
# First sort by counts, then by alphabet
orderedLetters = sorted(c.items(), key=lambda elem:(-elem[1],elem[0]))
print('%s: %s' % (word, orderedLetters))
stringCounts(['hello', 'world'])
# Output:
# hello: [('l', 2), ('e', 1), ('h', 1), ('o', 1)]
# world: [('d', 1), ('l', 1), ('o', 1), ('r', 1), ('w', 1)]
A simple solution is to just keep a track of the counts of letters (a-z). If any of the counts are 0, then it is not a panagram, else it is.
Simple to understand Python solution below:
from string import ascii_lowercase, punctuation
from collections import defaultdict
def isPanagram(sentence):
sentence = sentence.lower()
letterCount = defaultdict(int)
for letter in ascii_lowercase:
letterCount[letter] = 0
for letter in sentence:
if letter in punctuation:
continue # Skip special characters / punctuation marks
letterCount[letter] += 1
missingLetters = [letter for letter, count in letterCount.items() if count == 0]
if len(missingLetters) == 0:
print('The sentence is a panagram!')
else:
print('The sentence is not a panagram and is missing the letters: ', missingLetters)
isPanagram('Fox nymphs grab quick-jived waltz.')
isPanagram('The quick fox.')
isPanagram('The five boxing wizards jump quickly.')
isPanagram('The five boxing wizards jump.')
There are surprisingly 4 solutions to this problem! We can start with the brute force and improve from O(n^2) -> O(nlogn) -> O(n) -> O(lgn). I have outlined the 4 solutions below with explanations.
PS:- I would appreciate if you can plz upvote :P, I put in some effort to clearly explain the solution. :P
Python solution:
# Brute Force - Look at each element one by one
# O(n^2) solution
def searchVersion1(matrix, target):
for i, row in enumerate(matrix):
for j, sq in enumerate(row):
if sq == target:
return True
return False
# Since each row is sorted, perform binary search
# Since there are n rows, the runtime is O(n*lgn)
def searchVersion2(matrix, target):
def binarySearchHelper(row, target, low, high):
while low <= high:
mid = (low + high) // 2
if row[mid] == target:
return True
elif row[mid] < target:
low = mid + 1
elif row[mid] > target:
high = mid - 1
return False
for i, row in enumerate(matrix):
if binarySearchHelper(row, target, 0, len(row)-1):
return True
return False
# O(n) solution
# We can start from top-right corner of the matrix
# and move up to bottom right. If current element < target, move down
# else if element > target, move left. If we go out of bounds, we can
# return False since the element is not found.
def searchVersion3(matrix, target):
x, y = 0, len(matrix[0])-1
while 0 <= x < len(matrix) and 0 <= y < len(matrix[0]):
currentElement = matrix[x][y]
if currentElement == target:
return True
elif currentElement < target:
x += 1 # Move down
elif currentElement > target:
y -= 1 # Move left
return False
# O(lgn) solution
# Treat the 2-d matrix as a 1-d sorted array
# and just map the indices using math while applying binary search.
def searchVersion4(matrix, target):
rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1
while low <= high:
mid = (low + high) // 2
curRow = mid // cols
curCol = mid % cols
currentElement = matrix[curRow][curCol]
if currentElement == target:
return True
elif currentElement < target:
low = mid + 1
else:
high = mid - 1
return False
matrix = \
[
[1 , 3, 5, 7, 9] ,
[11,13,15,16,20],
[21,22,23,24,25],
[30,32,35,40,45],
]
print(searchVersion1(matrix, 23)) # True
print(searchVersion1(matrix, 28)) # False
print(searchVersion1(matrix, 5)) # True
print(searchVersion1(matrix, 10))# False
print('#' * 20)
print(searchVersion2(matrix, 23))# True
print(searchVersion2(matrix, 28))# False
print(searchVersion2(matrix, 5))# True
print(searchVersion2(matrix, 10))# False
print('#' * 20)
print(searchVersion3(matrix, 23))# True
print(searchVersion3(matrix, 28))# False
print(searchVersion3(matrix, 5))# True
print(searchVersion3(matrix, 10))# False
print('#' * 20)
print(searchVersion4(matrix, 23))# True
print(searchVersion4(matrix, 28))# False
print(searchVersion4(matrix, 5))# True
print(searchVersion4(matrix, 10))# False
Question is not clear. Can you please rephrase the question and edit the question. When n > 0, doesn't it imply that it can be greater than 4?? One more doubt I have is given example for n=5
1,11,111,1111,11111,12341 , the numbers 222, 2222, 333, 3333, .... are also valid right?
The easiest way would be to use the library function replace() function but since the question specifically asks not to use any library functions, the alternative way is to use three pointers, prev, curr, and next. If the three pointers match any one of the special characters below, then use the pop() function to modify the string in place.
If you're using python, another quick way to do this would be to use the python's slicing to find the strings and replace it with the appropriate character to be replaced. I present both solutions below.
Solution:
def decodeString(encodedStr):
curr = 0
encodedStr = list(encodedStr)
specialCharacters = \
{
'%20':' ',
'%3A':'?',
'%3D':':'
}
while curr < len(encodedStr) - 2:
specialCharacter = ''.join(encodedStr[curr:curr+3])
if specialCharacter in specialCharacters:
encodedStr.pop(curr+2)
encodedStr.pop(curr+1)
# Replace by the appropriate decoded character
encodedStr[curr] = specialCharacters[specialCharacter]
else:
curr += 1
return ''.join(encodedStr)
def decodeUsingThreePointers(encodedStr):
prev, curr, next = 0, 1, 2
encodedStr = list(encodedStr)
while prev < len(encodedStr) - 2:
if encodedStr[prev] == '%' and encodedStr[curr] == '2' and encodedStr[next] == '0':
encodedStr.pop(next)
encodedStr.pop(curr)
encodedStr[prev] = ' '
elif encodedStr[prev] == '%' and encodedStr[curr] == '3' and encodedStr[next] == 'A':
encodedStr.pop(next)
encodedStr.pop(curr)
encodedStr[prev] = '?'
elif encodedStr[prev] == '%' and encodedStr[curr] == '3' and encodedStr[next] == 'D':
encodedStr.pop(next)
encodedStr.pop(curr)
encodedStr[prev] = ':'
else:
prev += 1
curr += 1
next += 1
return ''.join(encodedStr)
print(decodeUsingThreePointers('kitten%20pic.jpg')) # kitten pic.jpg
print(decodeUsingThreePointers('dog%3Aimg.jpg')) #dog?img.jpg
print(decodeUsingThreePointers('lion%3Dbook.txt')) #lion:book.txt
print(decodeString('kitten%20pic.jpg')) #kitten pic.jpg
print(decodeString('dog%3Aimg.jpg')) #dog?img.jpg
print(decodeString('lion%3Dbook.txt')) #lion:book.txt
This question is based on thread scheduling. Normally, if you were designing a thread scheduler and had access to the internals, you would change the priority of each thread such that Thread 1 would have the highest priority, Thread 2 would have a lower priority and Thread 3 would have the lowest priority. And if the scheduler dispatched the threads according to the priorities, then T1, T2, T3 would be executed in that order.
However, in most systems, since you can only treat the Thread Scheduler as a black box, you can only use the join() method to control the execution of the threads. One simple way would be to have thread1 call join() and when it finishes, thread2 calls join() and so forth. In essence, calling join() will make the other thread wait. I have implemented my solution in Python below.
My solution:
import threading
import time
def worker():
print(threading.currentThread().getName(), 'Starting')
time.sleep(2)
print(threading.currentThread().getName(), 'Exiting')
t1 = threading.Thread(name='Thread 1', target=worker)
t2 = threading.Thread(name='Thread 2', target=worker)
t3 = threading.Thread(name='Thread 3', target=worker)
t1.start()
t1.join()
t2.start()
t2.join()
t3.start()
t3.join()
Same idea as dictionary but in addition to the key, record the time it was inserted. You can do this by either using a python tuple or using a separate list which keeps track of the times it inserted. I used the latter approach. I present my solution below.
Solution:
class HistoricalDict:
def __init__(self):
self._d = {}
def set(self, time, key, value):
if key not in self._d:
self._d[key] = [[value], [time]]
else:
self._d[key][0].append(value)
self._d[key][1].append(time)
def get(self, key, time):
valueList = self._d[key][0][::-1]
timeList = self._d[key][1][::-1]
if time < timeList[-1]: # HistoricalDict has not been created
return None
else:
# Scan from latest creation date
for ind, tempTime in enumerate(timeList):
if time >= tempTime:
return valueList[ind]
return None
def printHistorialDict(self):
print(self._d)
hdict = HistoricalDict()
hdict.set(2, 'foo', 1)
hdict.set(4, 'foo', 2)
hdict.printHistorialDict() # {'foo': [[1, 2], [2, 4]]}
print(hdict.get('foo', 5)) # 2
print(hdict.get('foo', 4)) # 2
print(hdict.get('foo', 3)) # 1
print(hdict.get('foo', 2)) # 1
print(hdict.get('foo', 1)) # None
print(hdict.get('foo', 0)) # None
I present my solution to this problem below. I assume that backslash+b represents backspace and backslash+c represents the caps lock. The hardest part about this problem is a shit ton of edge cases. I use python's pop() function to modify the list in place since the problem states to solve it in O(1) SC.
Other than that, the main idea is to keep track of two pointers, current and next. If it is backspace, carefully remove the escape characters and the previous character to be deleted. If it is caps lock, carefully remove the escape characters and modify the next+1 pointer to be uppercase.
Solution:
def isValid(inputString):
# There can't be a single backslash character as the string
if len(inputString) == 1 and inputString[0] == '\\':
return False
# Backspace can't occur at beginning of a string
if len(inputString) >= 2 and inputString[0] == '\\' and inputString[1] == 'b':
return False
# You can't have just a caps lock character in your string
if len(inputString) == 2 and inputString[0] == '\\' and inputString[1] == 'c':
return False
# Can't have just a caps lock string at the end
if len(inputString) >= 2 and inputString[-2] == '\\' and inputString[-1] == 'c':
return False
for i in range(len(inputString)-3):
temp = inputString[i:i+4]
# Caps lock can't be immediately followed by backspace
if temp[0:2] == r'\c' and temp[2:4] == r'\b':
return False
return True
def compareStrings(specialString, secondString):
specialString = list(specialString)
if not isValid(specialString):
print('*** Invalid input string. Characters are not properly escaped! ***')
return False
curr = 0
next = 1
while curr < len(specialString) - 1:
if specialString[curr] == '\\' and specialString[next] == 'c':
specialString[next+1] = specialString[next+1].upper()
specialString.pop(next)
specialString.pop(curr)
if specialString[curr] == '\\' and specialString[next] == 'b':
specialString.pop(next)
specialString.pop(curr)
curr = curr - 1
specialString.pop(curr)
else:
curr = curr + 1
next = curr + 1
return ''.join(specialString) == secondString
print(compareStrings('abc\\b', 'ab')) # True
print(compareStrings('abc\\bxy\cz', 'abxyZ')) # True
print(compareStrings('a\\ba', 'a')) # True
print(compareStrings('a\\b\cb', 'B')) # True
print(compareStrings('abc\ca', 'abcA')) # True
print(compareStrings('a\\b', '')) # True
print(compareStrings('\cz', 'Z')) # True
Problem not clear. Can you please give an example and clarify the problem a bit more. Thanks
- prudent_programmer March 02, 2018Can you please give an example and clarify the problem a bit more. Thanks
- prudent_programmer March 01, 2018Can you please give an example and clarify the problem a bit more. Thanks
- prudent_programmer March 01, 2018Another way is stating this problem is to say whether two strings are permutations of each other. I present two solutions. One using sorting which takes O(nlogn) where n = the number of characters/letters in the given word. Other approach is to use a hash table and maintain counts of letters. If the counts match, then the target string can be formed by swapping the characters in the original string.
Elegant solutions in python:
# O(nlogn) time for sort
def canBeSwappedUsingSort(originalString, targetString):
return sorted(originalString) == sorted(targetString)
# O(n) time
def canBeSwappedUsingHash(originalString, targetString):
from collections import Counter
return Counter(originalString) == Counter(targetString)
Can you please give an example and clarify the problem a bit more. Thanks
- prudent_programmer March 01, 2018I present two solutions. One iterative using explicit stack and other recursive using implicit stack.
def prefixToPostfixIterative(expression):
myStack = []
operators = set(['+','-','*','/'])
# Scan each letter from last
for ind, letter in reversed(list(enumerate(expression))):
# If expression is operand, push it to stack
if letter not in operators:
myStack.append(letter)
else:
firstExp = myStack.pop()
secondExp = myStack.pop()
result = firstExp + secondExp + letter
# Append it as operand + operand + operator
myStack.append(result)
return myStack.pop()
def prefixToPostfixRecursive(expression):
operators = set(['+', '-', '*', '/'])
# Pass index by reference by using a list
# This is the python workaround of passing int by reference
def helper(expr, index):
if index[0] == len(expr):
return
curr_char = expr[index[0]]
# If expression is operand, return it
if curr_char not in operators:
return curr_char
else:
index[0] += 1
left = helper(expr, index)
index[0] += 1
right = helper(expr, index)
# Append it as operand + operand + operator
return left + right + curr_char
cur_index = [0]
return helper(expression, cur_index)
prefixStringTestCases = ['+*AB/CD', '++A*BCD', '+-435', '+++ABCD']
for test_case in prefixStringTestCases:
print('-' * 50)
print('Prefix to Postfix final expr(Iterative): %s -> %s' % (test_case, prefixToPostfixIterative(test_case)))
print('Prefix to Postfix final expr(Recursive): %s -> %s' % (test_case, prefixToPostfixRecursive(test_case)))
Maintain two pointers previous and next and adjust those pointers accordingly depending on
whether the count % k == 0.
def removeKthNode(head, k):
if k == 1:
print 'Emptying entire list and returning None Pointer'
head = None
return head
counter = 1
prev = None
curr = head
while curr != None:
prev = curr
curr = curr.next
counter += 1
if counter % k == 0:
if prev:
prev.next = curr.next
return head
Simple Python solution
def minLevelSum(root):
q = Queue()
q.put(root)
minSum = float('inf')
curLevel, minLevel = 0, 0
while q.qsize():
tempList = []
for _ in range(0, q.qsize()):
curr = q.get()
tempList.append(curr.data)
if curr.left: q.put(curr.left)
if curr.right: q.put(curr.right)
if sum(tempList) < minSum:
minSum = sum(tempList)
minLevel = curLevel
curLevel += 1
return minLevel
This problem is also known as zigzag or spiral order traversal of a tree. You can simply do a BFS / level order traversal and reverse the level list depending on the level of the tree. I present a python solution down below which also returns Lists of Lists.
from queue import Queue
def zigzagPrintTree(root):
q = Queue()
q.put(root)
curLevel = 0
res = []
while q.qsize():
tempList = []
for _ in range(0, q.qsize()):
curr = q.get()
tempList.append(curr.data)
if curr.left: q.put(curr.left)
if curr.right: q.put(curr.right)
if curLevel % 2 == 0:
res.append(tempList)
else:
res.append(tempList[::-1])
curLevel += 1
return res
Is there a typo? What's an arrow?? Do you mean area??? Please clarify
- prudent_programmer February 23, 2018Without dictionary lookup, wouldn't it be impossible for this problem because we have no way of knowing whether the underscores separate a word or simply letters in a word.
For example, how would we know that "are" and "widely" are two different words? Does three underscores denote separation between two words and single underscore denote separation between two letters in a word? Anyone have thoughts on this?
Elegant Python Solution :)
def reverseAfterMiddle(nums):
mid = len(nums) // 2
return nums[mid+1:][::-1] + nums[0:mid]
print(reverseAfterMiddle([1,2,3,4,'&',12,13,14,15])) # prints [15, 14, 13, 12, 1, 2, 3, 4]
print(reverseAfterMiddle([33,34,'&',55,63])) # prints [64, 55, 33, 34]
Like other comments, please clarify the problem and provide additional details. Thank you.
- prudent_programmer February 23, 2018No approximate algorithms required here. You just do an exhaustive search using DFS+Recursion to find the combination that sums up to target sum.
def combinationSum(nums, target):
nums.sort() # Sort the numbers so that you know when to stop (with respect to target)
res = []
def combinationHelper(nums, tempResult=[], sumSoFar=0, target=target, start=0):
if sumSoFar > target:
return
if sumSoFar == target:
res.append(tempResult[:])
return
for index in range(start, len(nums)):
tempResult.append(nums[index])
combinationHelper(nums, tempResult, sumSoFar+nums[index], target, index)
tempResult.pop()
combinationHelper(nums)
return res
You can definitely speed this up though using DP.
- prudent_programmer February 23, 2018
Repcarlawbartlett, Accountant at ASU
Managed a small team managing toy elephants for the underprivileged. A real dynamo when it comes to managing vashikaran mantra ...
Rep
This looks awfully suspicious and looks like a homework problem. Coming from a .edu account also raises more suspicions. Reading a .csv file...hmmmm.........Anyone have any thoughts on this?
- prudent_programmer March 16, 2018