prudent_programmer
This sounds awfully lot like a homework problem.
 prudent_programmer May 16, 2018A very large value is typically used for Hashcodes to avoid collisions. Simply put, a larger range provides more values, thereby preventing collisions.
 prudent_programmer May 16, 2018I present two solutions to the above problem.
Appr 1: We can essentially scan through the entire array and perform a linear search. But this would take O(n) time complexity and O(1) SC.
Appr 2: Since the number is sorted, we can do a modified binary search and reduce search space at every step. This would take O(logn) and O(1) SC.
I present both solutions in Python below:
def findFirstOccLinear(nums, target):
for ind, num in enumerate(nums):
if num == target:
return ind
return 1
def findFirstOccurenceBS(nums, target):
index = 1
l, r = 0, len(nums)  1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
index = mid
r = mid  1
elif nums[mid] > target:
r = mid  1
else:
l = mid + 1
return index

prudent_programmer
May 12, 2018 The guy probably failed his interview which is why he probably has quit()? :P
 prudent_programmer May 12, 2018Awesome suggestions! Thank you!
 prudent_programmer April 17, 2018First Approach: Perform a dfs or bfs on the tree and retrieve the results. Check whether all of them are the same element. Second approach: As you are traversing, use a set or hash map to make sure they are all the same elements and if they are different return False.
Simple solution in Python outlining the first approach:
def preOrderRecursive(root):
res = []
def helper(root, res):
if not root:
return
res.append(root.val)
for child in root.children:
helper(child, res)
helper(root, res)
return res
def isUnivalTree(root):
result = preOrderRecursive(root)
return all(result[0] == x for x in result[1:])
Test code:
class Node:
def __init__(self, val):
self.val = val
self.children = []
'''
Construct the following tree:
1
/  \
1 2 1
/\ \
1 3 1
'''
root = Node(1)
root.children = [Node(1), Node(2), Node(1)]
root.children[1].children = [Node(1), Node(3)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: False
'''
Construct the following tree:
1
/  \
1 1 1
/\ \
1 1 1
'''
root = Node(1)
root.children = [Node(1), Node(1), Node(1)]
root.children[1].children = [Node(1), Node(1)]
root.children[2].children = [Node(1)]
print(isUnivalTree(root)) # Output: True

prudent_programmer
April 04, 2018 Very similar to binary tree traversal but use an array of children as opposed to left and right. Complete solution in Python:
Recursive Solution in Python:
def preOrderRecursive(root):
res = []
def helper(root, res):
if not root:
return
res.append(root.val)
for child in root.children:
helper(child, res)
helper(root, res)
return res
Iterative Solution in Python:
def preOrderIterative(root):
st = []
st.append(root)
res = []
while len(st):
curr = st.pop()
res.append(curr.val)
for child in reversed(curr.children):
st.append(child)
return res
Test Code:
class Node:
def __init__(self, val):
self.val = val
self.children = []
'''
Construct the following tree:
1
/  \
2 3 6
/\ \
4 5 7
'''
root = Node(1)
root.children = [Node(2), Node(3), Node(6)]
root.children[1].children = [Node(4), Node(5)]
root.children[2].children = [Node(7)]
print(preOrderRecursive(root)) # Output: [1, 2, 3, 4, 5, 6, 7]
print(preOrderIterative(root)) # Output: [1, 2, 3, 4, 5, 6, 7]

prudent_programmer
April 02, 2018 Use two pointers which are kth distance apart and move the pointers sequentially. When the later pointer reaches the end of the list, the earlier pointer will be the kth element from end.
Concise code in Python:
def kthFromEnd(head, k):
slow = fast = head
for _ in range(k):
fast = fast.next
if not fast:
return None
while fast:
slow = slow.next
fast = fast.next
return slow
Test code:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Construct 5>6>7>8
head = Node(5)
head.next = Node(6)
head.next.next = Node(7)
head.next.next.next = Node(8)
print(kthFromEnd(head, 2).data) # Output: 7
print(kthFromEnd(head, 1).data) # Output: 8

prudent_programmer
March 31, 2018 @Silvimasss, checking whether they are digits is not enough since ip addresses always fall between ranges 0  255. So, you have to check that as well.
Elegant solution in Python:
def isValidIP(ip):
parts = ip.split('.')
if len(parts) != 4:
return False
if any(part.isalpha() for part in parts):
return False
return all(0 <= int(part) <= 255 for part in parts)
Test code:
valid, invalid = [], []
ip_addresses = ["192.100.0.1", "10.0.0.1", "aa.bb.cc.dd", "10.0", "999.10.10.1"]
for ip_addr in ip_addresses:
valid.append(ip_addr) if isValidIP(ip_addr) else invalid.append(ip_addr)
print 'Valid IPs = ', valid
print 'Invalid IPs = ', invalid
'''
OUTPUT:
Valid IPs = ['192.100.0.1', '10.0.0.1']
Invalid IPs = ['aa.bb.cc.dd', '10.0', '999.10.10.1']
'''

prudent_programmer
March 29, 2018 Use two pointers, one for iterating through the array and another one for maintaining the last seen zero index. Every time you see a nonzero index, swap it with the previous seen zero index. Simple solution in Python
Solution:
def moveZeroes(arr):
i, j = 0, 0
while i < len(arr):
if arr[i] != 0:
arr[i], arr[j] = arr[j], arr[i]
j += 1
i += 1
return arr
Test code:
print(moveZeroes([0, 3, 1, 0, 2, 6, 7, 0])) # Output: [3, 1, 2, 6, 7, 0, 0, 0]
print(moveZeroes([0,0,1,0,0])) # Output: [1, 0, 0, 0, 0]
print(moveZeroes([0,3])) # Output: [3, 3]

prudent_programmer
March 28, 2018 UIThread > This is the singular main thread which runs when Android first launches and triggers Application.onStart().
Services are processes which run on the main thread by default, but they can be pushed to the background. If intensive services run on the main thread, they can be Blocking (usually networking operations and such). So, in that case, it is much better to put networking operations on the background thread and use that instead of using the main or the UIThread.
Here is also a recursion version of the same idea in Python.
Solution (Recursive):
def printFunctionRecursive(functions):
def recursiveHelper(functions, indendationLevel = 1, hasSubFunction = False):
if '>' not in functions:
print(' ' * indendationLevel + functions + ' start')
if not hasSubFunction: # Single function
print(' ' * indendationLevel + functions + ' end')
else:
stackTrace = functions.split('>')
for sub_funcs in stackTrace:
indendationLevel += 2
recursiveHelper(sub_funcs, indendationLevel, True)
print(' ' * indendationLevel + sub_funcs + ' end')
for stackTrace in functions:
recursiveHelper(stackTrace)
Test code:
printFunctionRecursive(['main>foo>bar', 'main2'])
'''
Output:
main start
main end
foo start
foo end
bar start
bar end
main2 start
main2 end

prudent_programmer
March 28, 2018 @Raju. I think it's the number of characters in the original input string.
 prudent_programmer March 28, 2018Use a stack or recursion to keep track of the function calls. This is very similar to printing the directory structure of a folder. I assume we are given a string which represents the function and I assume we are also given a marker which denotes whether this function calls other functions or is just a standalone function. For the sake of assumption, I assume '>' is the marker which denotes that this function will call other functions. I present my solution in Python below using an explicit stack.
Solution:
def printFunction(functions):
functionStack = []
for function in functions:
if '>' in function:
callStack = function.split('>')
indentLevel = 0
# Push the functions to stack
for f in callStack:
functionStack.append((indentLevel, f))
print('%s %s start' % (' ' * indentLevel, f))
indentLevel += 2
# Pop the functions off the stack
while len(functionStack):
functionInfo = functionStack.pop()
print('%s %s end' % (' ' * functionInfo[0], functionInfo[1]))
else:
print('%s start' % function)
print('%s end' % function)
Test code:
printFunction(['main>foo>bar', 'main2'])
'''
Output:
main start
foo start
bar start
bar end
foo end
main end
main2 start
main2 end
'''

prudent_programmer
March 28, 2018 You can probably start out with the smallest flow [s1, s2] from the coffee machine. You would then compare the differences of [c1,c2] with [s1, s2], [m1, m2], [l1, l2]. Then, you could see that if the differences were negative i.e l1 > c1 or l2 > c2, it might overflow, so you wouldn't choose that particular intake flow. Like this, you can calibrate and choose the particular range (small, medium, or large) and still filling the cup.
 prudent_programmer March 28, 2018@Mehdi. Haha true. I think he just gets the interview questions from various companies and posts them. I don't think he physically attends that many interviews or I might be wrong. Or he might be the interviewer himself and might share the questions. :P :D
 prudent_programmer March 27, 2018Usually the OTP code is sent to the phone and a corresponding screen on the web is displayed verifying the user to enter the OTP code. If the OTP codes match, then the user is able to set his/her password and can proceed to use the email address.
 prudent_programmer March 26, 2018Ensure that the password has alphanumeric characters with upper case and lower case and some special characters. In addition, I would also make it nonpasteable. After the user clicks "Sign Up" or "Login" then encrypt the given password on serverside via SHA1/SHA2 or some other encryption method. Then, you can decrypt on the receiving end and retrieve the user's profile and so forth.
If the user has forgotten the password, then the recovery procedure is "Forgot Password", which then usually sends a temporary secured password to email or phone. And then you would direct the user towards that flow.
You can "Find Accounts" apparently, if you have forgotten your fb email address and then from there proceed with the security code and other things.
 prudent_programmer March 26, 2018@Andy. Excellent catch man! Thank you for pointing that out. :)
 prudent_programmer March 26, 2018The tricky part of this problem is to make random() O(1). To achieve this, use a set/hashmap to achieve O(1) insertions/deletions. To obtain O(1) for random, use an auxiliary list and return a random index from the list. Another tricky part is to keep the list in sync with the hashmap/set. To achieve this swap the quote with the last element and then remove the element when you select the random() quote.
I have provided a toy example which represents this idea:
Solution in Python Below:
from random import randint
class QuoteManager:
def __init__(self):
self.quoteToIndicesMap = {}
self.quotes = []
def add(self, quote):
if quote not in self.quoteToIndicesMap:
# Add it
self.quotes.append(quote)
self.quoteToIndicesMap[quote] = len(self.quotes)  1 # index
return True
return False # Already there return False
def random(self):
if len(self.quotes) == 0:
print('All quotes are exhausted!')
return 'INVALID!!'
# Key trick is to swap with last element
# and then delete it
# Swap it with last position
lastQuote = self.quotes[1]
randomIndex = randint(0, len(self.quotes)  1)
self.quotes[randomIndex], self.quotes[1] = self.quotes[1], self.quotes[randomIndex]
# Delete it from list and the hashmap
quoteToPop = self.quotes.pop()
self.quoteToIndicesMap[lastQuote] = randomIndex
del self.quoteToIndicesMap[quoteToPop]
# Return the random quote
return quoteToPop
Test code:
# Test code
q = QuoteManager()
print(q.add('Quote 1')) # True
print(q.add('Quote 2')) # True
print(q.add('Quote 3')) # True
print(q.add('Quote 4')) # True
print(q.add('Quote 1')) # False
print(q.random()) # Quote 2
print(q.random()) # Quote 4
print(q.random()) # Quote 3
print(q.random()) # Quote 1
print(q.random()) # All quotes are exhausted! INVALID!

prudent_programmer
March 26, 2018 Evaluate the product of the list and keep popping it off until the list is not empty.
Solution in Python:
class CartesianIterator:
def __init__(self, sets):
self.result = [[]]
for pool in sets:
self.result = [x + [y] for x in self.result for y in pool]
def hasNext(self):
return len(self.result) != 0
def next(self):
return self.result.pop(0)
Test Code:
Test code
# Example 1
c = CartesianIterator([[1,2,3], [4,5]])
while c.hasNext():
print(c.next(), end=', ')
print()
# Example 2
c = CartesianIterator([['a','b','c'], ['p', 'q'], ['r', 's']])
while c.hasNext():
print(c.next(), end=', ')
print()
Output:
[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5],
['a', 'p', 'r'], ['a', 'p', 's'], ['a', 'q', 'r'], ['a', 'q', 's'], ['b', 'p', 'r'], ['b', 'p', 's'], ['b', 'q', 'r'], ['b', 'q', 's'], ['c', 'p', 'r'], ['c', 'p', 's'], ['c', 'q', 'r'], ['c', 'q', 's'],

prudent_programmer
March 23, 2018 Given a current sim location, I would radially start exploring the presence of another sim. This means first looking at radius increments of 1,2,3, etc... (i.e look 1unit right / 1 unit left, then 2 units right / 2 units left, etc..) until another sim is found. Once we know the direction in which the other sim is found, we can start moving in that direction by calling moveLeft() or moveRight(). This way, eventually, both sims will collide. I have outlined a simple solution in Python below:
Solution:
def collide():
# Mark current location
currSim.markPosition()
# Radially search for another marked location
# (this indicates the presence of another sim)
isRight = True
increment = 1
while True:
rightLocation = currentLocation + increment
leftLocation = currentLocation  increment
if isCurrentLocationMarked(rightLocation):
break
elif isCurrentLocationMarked(leftLocation):
isRight = False
break
increment += 1
# If another sim is towards right
# move right
if isRight:
currSim.moveRight()
currSim.markPosition()
else: # else move left
currSim.moveLeft()
currSim.markPosition()

prudent_programmer
March 22, 2018 Use a priority queue and insert elements into the queue as you go along and call next. Posting my solution below in Python:
from queue import PriorityQueue
class SuperIterator:
def __init__(self, iterators):
self.sortedQueue = PriorityQueue()
for iterator in iterators:
self.sortedQueue.put((next(iterator), iterator))
def hasNext(self):
return self.sortedQueue.qsize() != 0
def next(self):
value, iterator = self.sortedQueue.get()
try:
next_value = next(iterator)
self.sortedQueue.put((next_value, iterator))
except StopIteration:
pass
return value
Test code:
# Test code
# Example 1
list1 = [1, 4, 5,20]
list2 = [2,10,12,50]
s = SuperIterator([iter(list1), iter(list2)])
while s.hasNext():
print(s.next(), end=', ')
print()
# Output: 1, 2, 4, 5, 10, 12, 20, 50,
# Example 2
list1 = [12,14,16]
list2 = [4,7,9,50,100]
list3 = [6,8,10,13]
s = SuperIterator([iter(list1), iter(list2), iter(list3)])
while s.hasNext():
print(s.next(), end=', ')
print()
# Output: 4, 6, 7, 8, 9, 10, 12, 13, 14, 16, 50, 100,

prudent_programmer
March 22, 2018 Fairly straightforward problem. The only clarification we might need is if to include the second LL's element in the last interleaving (i.e whether to include 40) but going by your example, it doesn't seem to be the case. This solution is expressed in Python below.
Solution:
def interleaveLL(head1, head2):
dummy = curr = Node(None)
while head1 != None:
# Append head1 and move its pointer forwards
curr.next = head1
curr = curr.next
head1 = head1.next
if head1 is None:
break # If end of head then break
# Append head2 and move its pointer forwards
curr.next = head2
curr = curr.next
head2 = head2.next
return dummy.next
Test code:
def printLL(head):
curr = head
while curr:
print(curr.data, end='>')
curr = curr.next
print()
class Node:
def __init__(self, data):
self.data = data
self.next = None
head1 = Node(1)
head1.next = Node(2)
head1.next.next = Node(3)
head1.next.next.next = Node(4)
head2 = Node(10)
head2.next = Node(20)
head2.next.next = Node(30)
head2.next.next.next = Node(40)
head2.next.next.next.next = Node(50)
head2.next.next.next.next.next = Node(60)
printLL(interleaveLL(head1, head2))
'''
Output:
1>10>2>20>3>30>4>
'''

prudent_programmer
March 22, 2018 Use two stacks, one for operands and one of operators. Whenever you notice parenthesis, take special action. Solution in Python below:
def evaluateInfix(expr):
def helper(operator, x, y):
if operator == '+': return x + y
if operator == '': return x  y
if operator == '/': return y // x
if operator == '*': return x * y
operandStack = [] # for numbers
operatorStack = [] # for arithmetic operators and parens.
operators = {
'/': 1,
'*': 1,
'+': 2,
'': 2
}
for token in expr:
if token.isdigit():
operandStack.append(token)
elif token == '(':
operatorStack.append(token)
elif token == ')':
while operatorStack[1] != '(':
operandStack.append()
elif token == ')':
while operatorStack[1] != '(':
result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
operandStack.append(result)
operatorStack.pop()
elif token in operators:
while len(operatorStack) and operators[operatorStack[1]] <= operators[token]:
result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
operandStack.append(result)
operatorStack.append(token)
while len(operatorStack):
result = helper(operatorStack.pop(), int(operandStack.pop()), int(operandStack.pop()))
operandStack.append(result)
return operandStack.pop()
Test Code:
print(evaluateInfix('2 + 3 * 5')) # 17
print(evaluateInfix('4 * 5 / 2')) # 10

prudent_programmer
March 22, 2018 @sbdul. Great approach. Using union find sounds cool! :)
 prudent_programmer March 19, 2018The 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 Open Chat in New Window
Outlining a simple twopass approach with dictionary/hashmap. TC: O(n) and SC: O(n) where n = number of elements.
Solution in Python:
Test code:
 prudent_programmer May 19, 2018