prudent_programmer
The trickiest part about this problem is that random has to be O(1). We can achieve this by using a list + dictionary to keep a track of the servers. The removal operation will be tricky since we have to swap it with the last element and then pop it to obtain constant time. I present my solution below in Python with test code.
Solution:
import random
class Pool:
def __init__(self):
self.servers = []
self.serverIndices = {}
def addServer(self, serverNumber):
if serverNumber not in self.serverIndices:
self.servers.append(serverNumber)
self.serverIndices[serverNumber] = len(self.servers)1
return True
return False
def deleteServer(self, serverNumber):
if serverNumber in self.serverIndices:
# Key trick is to swap with last element
# and then delete it
index = self.serverIndices[serverNumber]
lastNumber = self.servers[1]
self.servers[1] = serverNumber # Place it at last index
# Remove it from the list and the hashmap
self.servers.pop() # Remove the server
del self.serverIndices[serverNumber]
# Update the servers list and the hashmap
if index != len(self.servers):
self.servers[index] = lastNumber
self.serverIndices[lastNumber] = index
return True
return False
def getRandomServer(self):
return self.servers[random.randint(0, len(self.servers)1)]
def __repr__(self):
return 'Current pool: ' + str(self.servers)
Test Code:
# Test Code
p = Pool()
# Add servers
p.addServer(5)
p.addServer(3)
p.addServer(2)
p.addServer(10)
p.addServer(6)
# Print servers
print(p) # Current pool: [5, 3, 2, 10, 6]
# Get Random servers
print('Random server:', p.getRandomServer()) # Random server: 2
print('Random server:', p.getRandomServer()) # Random server: 5
print('Random server:', p.getRandomServer()) # Random server: 5
# Remove Servers
print(p.deleteServer(3)) # True
print(p.deleteServer(10)) # True
print(p.deleteServer(5)) # True
print(p.deleteServer(3)) # False
print(p.deleteServer(999)) # False
print(p) # Current pool: [2, 6]
# Get random servers
print('Random server:', p.getRandomServer()) # Random server: 6
print('Random server:', p.getRandomServer()) # Random server: 6

prudent_programmer
March 19, 2018 Elegant 4 line solution in Python (for small strings of course):
def sortStrings(strs, col):
data = [tuple(word.split()) for word in strs]
data = [(first_name, last_name, int(age)) for first_name, last_name, age in data]
result = sorted(data, key=lambda x: x[col1])
return result
Test Code:
strings = ['john doe 33', 'smith black 9', 'diana yale 12']
print(sortStrings(strings, 1)) # Order by first name
print(sortStrings(strings, 2)) # Order by last name
print(sortStrings(strings, 3)) # Order by age
'''
Output:
[('diana', 'yale', 12), ('john', 'doe', 33), ('smith', 'black', 9)]
[('smith', 'black', 9), ('john', 'doe', 33), ('diana', 'yale', 12)]
[('smith', 'black', 9), ('diana', 'yale', 12), ('john', 'doe', 33)]
'''
However, in a distributed setting, when we have large amounts of strings to process, we can divide up the column that we are trying to sort by and process per chunks. We would create multiple chunks and use a sorting algorithm such as quicksort or mergesort to combine the data into a sorted order.
 prudent_programmer March 19, 2018In case, some of you all want to test it, here are the helper functions I coded for my above solution:
class Node:
def __init__(self, value):
self.value = value
self.next = None
def insertAtBeggining(head, value):
if head is None:
head = Node(value)
else:
tempNode = Node(value)
tempNode.next = head
head = tempNode
return head
def reverseLL(head):
# Creates a new LL and returns the head
# instead of modifying it in place
stack = []
curr = head
while curr != None:
stack.append(curr.value)
curr = curr.next
newHead = curr = Node(None)
while len(stack):
elem = stack.pop()
if curr is None:
curr = Node(elem)
else:
curr.next = Node(elem)
curr = curr.next
return newHead.next
def getLengthofLL(head):
counter = 0
while head != None:
counter += 1
head = head.next
return counter
def constructLinkedList(word):
head = curr = Node(None)
for char in word:
if curr is None:
curr = Node(char)
else:
curr.next = Node(char)
curr = curr.next
return head.next
def printLL(head):
curr = head
while curr != None:
print(curr.value, end='>')
curr = curr.next
print()

prudent_programmer
March 19, 2018 Scan from end of the string and compare each character in the word. I assume that we are given a singly linked list and I also assume we are given helper functions such as reverseLinkedList(), insertAtBeginning, length(), etc. The idea is pretty straightforward, compare each character from end and if they are different break, else append the result. If there are no common characters which are suffixes, return the minimum length of the two linked lists. I present a solution in Python below. The time complexity is O(n) where n is the length of the longest suffix.
Solution:
def longestCommonSuffix(str1, str2):
suffix = None
str1rev, str2rev = reverseLL(str1), reverseLL(str2)
str1Len, str2Len = getLengthofLL(str1), getLengthofLL(str2)
while str1rev and str2rev:
if str1rev.value != str2rev.value:
break
suffix = insertAtBeggining(suffix, str1rev.value)
str1rev = str1rev.next
str2rev = str2rev.next
if not suffix:
if str1Len < str2Len:
return str1
else:
return str2
else:
return suffix
Test code:
# Test code
str1 = constructLinkedList('walking')
str2 = constructLinkedList('listening')
rev = longestCommonSuffix(str1, str2)
printLL(rev) # Outputs 'i>n>g>'
str3 = constructLinkedList('party')
str4 = constructLinkedList('partying')
rev = longestCommonSuffix(str3, str4) # Outputs 'p>a>r>t>y>'
printLL(rev)

prudent_programmer
March 19, 2018 This problem is essentially summing a subarray/part of an array of nums from 1..len(nums). To do this, the only tricky part is to find out the starting index to sum and the how many elements to do so. Luckily, we can easily do this using the triangular numbers formula and we are also given an n. This leads to a simple solution. I present my 4line solution in Python below.
Elegant Solution (Python):
def getNthRowSum(n):
n = n  1 # Since we offset by 0
if n == 0:
return 1 # First row
starting_ind = (n*(n+1)//2)+1 # Adding 1 since arrays/lists start at 0
return sum(range(starting_ind, starting_ind+n+1))
Test code:
for i in range(1, 7):
print('%dth row: Sum = %d' % (i, getNthRowSum(i)))
'''
Output:
1th row: Sum = 1
2th row: Sum = 5
3th row: Sum = 15
4th row: Sum = 34
5th row: Sum = 65
6th row: Sum = 111
'''

prudent_programmer
March 18, 2018 I present a simple solution in Python below. Using a doubleended queue for O(1) pop/append times.
Solution:
from collections import deque
class PeekIterator:
def __init__(self, nums):
self.result = deque(nums)
def peek(self):
return self.result[0]
def next(self):
return self.result.popleft()
def hasNext(self):
return len(self.result) > 0
Test code:
p = PeekIterator([2,3,6,7,10,12])
while p.hasNext():
print('Elem at top of stack = ', p.peek(), end=', ')
print('and now popping elem using next: ', p.next())
'''
Output:
Elem at top of stack = 2, and now popping elem using next: 2
Elem at top of stack = 3, and now popping elem using next: 3
Elem at top of stack = 6, and now popping elem using next: 6
Elem at top of stack = 7, and now popping elem using next: 7
Elem at top of stack = 10, and now popping elem using next: 10
Elem at top of stack = 12, and now popping elem using next: 12
'''

prudent_programmer
March 18, 2018 Assuming we have to implement next() and hasNext() methods (just like traditional iterators), I propose the following solution. I am using a deque since removing/adding elements to the front or back of the structure is O(1). I also assume in the implementation that the user specifies the limit or the first 'n' fibonacci numbers that he wishes to see.
Solution:
from collections import deque
class FibonacciIterator:
def __init__(self, limit):
self.results = deque([0, 1])
self.curPos = 0
self.limit = limit
def hasNext(self):
return self.curPos < self.limit
def next(self):
firstNum = self.results.popleft()
self.curPos += 1
self.results.append(self.results[0] + firstNum)
return firstNum
Test Code:
f = FibonacciIterator(15) # Want the first 15 fib numbers
while f.hasNext():
print(f.next(),end=', ')
print()
# Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,

prudent_programmer
March 18, 2018 A simple solution for this problem is to store and generate 5 random indices from 0  length of the array. Store these 5 indices, keep advancing the iterator, if you find that the iter position is equal to one of the indices, add that to the result. I present my solution below:
import random
def sample5Elements(nums, sampleSize=5):
randomIndices = set()
# Construct a set with random 5 indices
while len(randomIndices) != sampleSize:
randomIndex = random.randint(0, len(nums)  1)
if randomIndex not in randomIndices:
randomIndices.add(randomIndex)
counter = 0
res = []
# Obtain an iterator for the array
nums_it = iter(nums)
while counter < len(nums):
elem = next(nums_it)
if counter in randomIndices:
res.append(elem)
counter += 1
return res
nums = list(range(1, 21)) # Generate nums from 1  20
print('Random 5 elements:', sample5Elements(nums))
# Output: Random 5 elements: [1, 2, 6, 9, 11]

prudent_programmer
March 18, 2018 Simply iterate from 1 through n and n % i == 0, print the number. Elegant one liner in python below:
def getAllFactors(n):
return [i for i in range(1, n+1) if n % i == 0]
Test code:
print(getAllFactors(12)) # Prints [1, 2, 3, 4, 6, 12]

prudent_programmer
March 17, 2018 The idea is to use a hashtable or a set for this problem. When the store is called, we store all the numbers into the set. This gives us constant O(1) access time. When we are testing whether the target exists in the set, we simply compute its complement and check whether it exists in the set which amounts to O(n) time complexity. I present my solution in Python below:
Solution:
class StoreNums:
def __init__(self):
self.numSet = set()
# TC: O(1) since we are using a hashable set
def store(self, num):
if num in self.numSet:
return False
else:
self.numSet.add(num)
return True
# TC: O(n) where n = number of nums stored
def test(self, target):
for num in self.numSet:
complement = target  num
if complement in self.numSet:
return True
return False
Test code:
# Test code
s = StoreNums()
print(s.store(1)) # True
print(s.store(3)) # True
print(s.store(5)) # True
print(s.store(3)) # False
print(s.store(6)) # True
print(s.test(4)) # True
print(s.test(5)) # False
print(s.test(6)) # True

prudent_programmer
March 17, 2018 Since we know the maximum result can be three digits i.e 12 * 12 = 144, we can use the string formatting function when printing our output to correctly align the output. In this case, we have 3 digits as our max length, so we can format it in that particular way.
Solution:
def printMultiplicationTableFor12():
for row in range(1, 13):
for col in range(1, 13):
print('{:3} '.format(row * col),end='')
print()
Test code:
printMultiplicationTableFor12()
'''
Output:
1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 14 16 18 20 22 24
3 6 9 12 15 18 21 24 27 30 33 36
4 8 12 16 20 24 28 32 36 40 44 48
5 10 15 20 25 30 35 40 45 50 55 60
6 12 18 24 30 36 42 48 54 60 66 72
7 14 21 28 35 42 49 56 63 70 77 84
8 16 24 32 40 48 56 64 72 80 88 96
9 18 27 36 45 54 63 72 81 90 99 108
10 20 30 40 50 60 70 80 90 100 110 120
11 22 33 44 55 66 77 88 99 110 121 132
12 24 36 48 60 72 84 96 108 120 132 144
'''

prudent_programmer
March 17, 2018 A simple regex of the form \(?\d{3}\)?(\d{3})(\d{4}) will do for this problem. The idea is to compile or apply the regex to the text contained in various files from the directory. I present a simple solution in Python using regex below. I have used the verbose option to explain each symbol in my regex for clarity:
My solution:
import re
def findPhoneNumbers(text):
phoneNumberPattern = re.compile(r'''
\(? # The particular regex might optionally start with a (
(\d{3}) # Followed by the area code
\)? # Followed optionally by a parenthesis
 # Followed by a hyphen
(\d{3}) # Followed by three digits
 # And a hyphe
(\d{4}) # And last 4 digits
''', re.VERBOSE)
return phoneNumberPattern.findall(text)
Test code:
text = r'''
<p><b>This is a text string. Phone number is (111)1111111.
</b>This is a second phone number which follows a different format of 2222222222.</p>
<b>But if I have a phone number which is of the format 333.333.3333, then my regex shouldn't find it.
'''
print(findPhoneNumbers(text))
Output:
[('111', '111', '1111'), ('222', '222', '2222')]

prudent_programmer
March 17, 2018 Linked list is used in the case where you care about fast insertions and lookups are not performed that often. Due to insertions being constant time, the linked list does not need to resize as necessary but instead just append the node at the end or beginning of the linked list. This makes them a very flexible data structure.
On the other hand, an array is used when lookup via indexing is performed often. In this case, lookups give constant time but the downside is resizing or inserting elements into the array. Another advantage of arrays is that arrays offer is binary search for lookups in the case where the array is sorted. Unfortunately, with linked lists binary search can not be used.
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@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, rows1] or j in [0, cols1]:
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), (i1,j), (i,j+1), (i,j1)]
# 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']]

prudent_programmer
March 16, 2018 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 inplace.
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), (i1,j), (i,j+1), (i,j1)]
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']
]
'''

prudent_programmer
March 15, 2018 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>

prudent_programmer
March 14, 2018 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

prudent_programmer
March 13, 2018 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

prudent_programmer
March 12, 2018 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]

prudent_programmer
March 10, 2018 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

prudent_programmer
March 09, 2018 Kind of challenging to do this from scratch by writing algorithms, but using inbuilt 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 + maxheaps. 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 maxheaps
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']

prudent_programmer
March 09, 2018 import random
def simulateBiasedCoin(p):
if random.randint(1,100) < p*100:
return "Heads"
else:
return "Tails"
simulateBiasedCoin(0.67)

prudent_programmer
March 08, 2018 The outer loop runs for O(N1) where N is the length of your input string and the inner loop runs for O(13). So the total runtime is O(N1 * 13) => O(13N13) => 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 quickjived waltz.')
isPanagram('The quick fox.')
isPanagram('The five boxing wizards jump quickly.')
isPanagram('The five boxing wizards jump.')

prudent_programmer
March 08, 2018 Below I present the exhaustive search recursion solution and the much improved topbottom 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 TopDown 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)

prudent_programmer
March 06, 2018 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)]

prudent_programmer
March 06, 2018 A simple solution is to just keep a track of the counts of letters (az). 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 quickjived waltz.')
isPanagram('The quick fox.')
isPanagram('The five boxing wizards jump quickly.')
isPanagram('The five boxing wizards jump.')

prudent_programmer
March 06, 2018 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 topright 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 2d matrix as a 1d 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

prudent_programmer
March 06, 2018 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

prudent_programmer
March 05, 2018 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()

prudent_programmer
March 05, 2018 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

prudent_programmer
March 03, 2018 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

prudent_programmer
March 03, 2018 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)

prudent_programmer
March 01, 2018 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)))

prudent_programmer
March 01, 2018 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

prudent_programmer
March 01, 2018 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

prudent_programmer
February 23, 2018 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

prudent_programmer
February 23, 2018 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]

prudent_programmer
February 23, 2018 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, 2018Open Chat in New Window
@sbdul. Great approach. Using union find sounds cool! :)
 prudent_programmer March 19, 2018