sleebapaul
BAN USERTime complexity: O(n) where n is the length of aString
def repeatingStringCheck(aString, bString):
try:
n = aString.index(bString[0])
except ValueError:
return False
while len(aString) < len(bString) + n:
aString += aString
return bString in aString
q = list(range(n))
for any n. The above code code works well for only n=3.
- sleebapaul January 31, 2020N: Number of the show - rating pairs
Time complexity: O(NlogN)
Space complexity: O(N)
def findTopTen(aListOfShows):
if aListOfShows is None: return None
if len(aListOfShows) == 0: return aListOfShows
if len(aListOfShows) == 1: return aListOfShows
sortedList = sorted(aListOfShows, key=lambda x: x[1], reverse=True)
i = 0
seen = set()
res = []
while i < len(sortedList):
show, rate = sortedList[i]
if show not in seen:
seen.add(show)
res.append(sortedList[i])
i+=1
return res
Time complexity: log(N), If insertion to BST is not counted otherwise O(N)
class Node():
def __init__(self, show, rate):
self.show = show
self.rate = rate
self.left = None
self.right = None
class BST():
def __init__(self):
self.root = None
def createBST(self, show, rate):
if self.root is None:
self.root = Node(show, rate)
return
else:
current = self.root
while True:
if current.show == show:
if current.rate < rate:
current.rate = rate
break
if rate < current.rate:
if current.left:
current = current.left
else:
current.left = Node(show, rate)
break
elif rate > current.rate:
if current.right:
current = current.right
else:
current.right = Node(show, rate)
break
return
def inOrderTraversal(self, limit):
res = []
def traverse(root, res):
if root:
traverse(root.right, res)
res.append([root.show, root.rate])
traverse(root.left, res)
return
traverse(self.root, res)
return res[:limit]
values = [("abc", 13), ("xyz", 19), ("efr", 89), ("afaf", 23), ("abc", 7), ("afeogh", 5)]
bst = BST()
for val in values:
show, rate = val
bst.createBST(show, rate)
print(bst.inOrderTraversal(3))
Complexity - O(mn)
M: Number of vertical lines
N: Number of horizontal lines
class Line():
def __init__(self, y1, y2, x1, x2, direction):
self.y1 = y1
self.y2 = y2
self.x1 = x1
self.x2 = x2
self.direction = direction
def getLength(self):
return int(((self.x1 - self.x2)**2 + (self.y1 - self.y2)**2)**0.5)
def matchLinePairs(linePairOne, linePairTwo):
lineOne, lineTwo = linePairOne
lineThree, lineFour = linePairTwo
if lineOne.getLength() == lineThree.getLength():
if (lineOne.x1, lineOne.y1) == (lineThree.x1, lineThree.y1) or (lineOne.x1, lineOne.y1) == (lineThree.x2, lineThree.y2):
return True
return False
def numberOfSquares(aListOfVertLines, aListOfHorLines):
horPairs = []
verPairs = []
for i in range(len(aListOfHorLines)):
line1 = aListOfHorLines[i]
for j in range(i, len(aListOfHorLines)):
line2 = aListOfHorLines[j]
if line1.getLength() == line2.getLength():
if line1.y1 == line2.y1 and line1.y2 == line2.y2:
horPairs.append((line1, line2))
for i in range(len(aListOfVertLines)):
line1 = aListOfVertLines[i]
for j in range(i, len(aListOfVertLines)):
line2 = aListOfHorLines[j]
if line1.getLength() == line2.getLength():
if line1.x1 == line2.x1 and line1.x2 == line2.x2:
verPairs.append((line1, line2))
numSquares = 0
for horLinePair in horPairs:
for verLinePair in verPairs:
if matchLinePairs(horLinePair, verLinePair):
numSquares+=1
return numSquares
Time complexity: O(NlogN)
- sleebapaul February 01, 2020