ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
I have implemented 5 different functions which I list here and I want to calculate the time and space complexity together with the worst case complexities. Can anyone calculate the complexities for me and give me a short description of the calculation. Truth is I am not that familiar with complexity computation and any help here will be really welcomed.
Thank you.
Code:
def question1(s,t):
if not s or not isinstance(s, str):
return False
if not t or not isinstance(t,str):
return False
try:
if s.index(t) >= 0:
return True
except:
perms = [''.join(p) for p in permutations(t)]
try:
if perms.index(t) >= 0:
return True
except ValueError:
return False
Code:
def addBoundaries(chars):
if not chars or len(chars) == 0:
return list("||")
chars2 = [None] * ((len(chars)*2)+1)
for i in range(0, len(chars2)-1,2):
chars2[i] = '|'
chars2[i+1] = chars[int(i/2)]
chars2[len(chars2) - 1] = '|'
return chars2
def removeBoundaries(ss):
if not ss or len(ss) < 3:
return list("")
cs2 = [None] * int((len(ss) -1) / 2)
for i in range(0, len(cs2), 1):
cs2[i] = ss[(i*2)+1]
return cs2
def findLongestPalindrome(s):
if not isinstance(s, str):
return "Error: parameter not a string"
if(len(s) == 0):
return ""
boundaries = addBoundaries(list(s))
p = [None] * len(boundaries)
c = 0
r = 0
m = 0
n = 0
for i in range(1, len(boundaries), 1):
if i > r:
p[i] = 0
m = i - 1
n = i + 1
else:
i2 = c * 2 - i
if not p[i2] is None:
if p[i2] < r - i - 1:
p[i] = p[i2]
m = -1
else:
p[i] = r - i
n = r + 1
m = i * 2 - n
while (m >= 0 and n < len(boundaries) and boundaries[m]
== boundaries[n]):
p[i]+= 1
m -= 1
n += 1
if not p[i] is None:
if i + p[i] > r:
c = i
r = i + p[i]
length = 0
c = 0
for i in range(1,len(boundaries),1):
if not p[i] is None:
if length < p[i]:
length = p[i]
c = i
ss = boundaries[c-length:c+length+1]
return removeBoundaries(ss)
def question2(s):
if not isinstance(s, str):
return "Error: parameter not a string"
strList = findLongestPalindrome(s)
string = ""
for item in strList:
string += item
return string
Code:
def getMinimumSpanningTree(G):
"""
Return the minimum spanning tree of an undirected graph G.
G should be represented in such a way that iter(G) lists its
vertices, iter(G[u]) lists the neighbors of u, G[u][v] gives the
length of edge u,v, and G[u][v] should always equal G[v][u].
The tree is returned as a list of edges.
"""
# Kruskal's algorithm: sort edges by weight, and add them one at a time.
# We use Kruskal's algorithm, first because it is very simple to
# implement once UnionFind exists, and second, because the only slow
# part (the sort) is sped up by being built in to Python.
if not isUndirected(G):
return "Graph is undirected"
for u in G:
for v in G[u]:
if G[u][v] != G[v][u]:
return "MinimumSpanningTree: asymmetric weights"
subtrees = UnionFind()
tree = []
for W,u,v in sorted((G[u][v],u,v) for u in G for v in G[u]):
if subtrees[u] != subtrees[v]:
tree.append((u,v))
subtrees.union(u,v)
return tree
def toGraph(G, vertices):
graph = {}
for item in vertices:
a,b = item
graph[a] = []
graph[b] = []
for item in vertices:
a,b = item
vertex1 = G[a]
vertex2 = G[b]
graph[b].append({a:vertex1[b]})
graph[a].append({b:vertex2[a]})
return graph
def question3(G):
if not isinstance(G, dict):
return "Error G not a dictionary"
if len(G) < 2:
return ""
mst = getMinimumSpanningTree(G)
return toGraph(G, mst)
Code:
def getParent(T, n):
for x in range(0, len(T), 1):
for y in range(0, len(T[x]), 1):
if T[x][y] == 1 and y == n:
return x
def getChildren(T, item, children):
for x in range(0, len(T[item]), 1):
if T[item][x] == 1:
children.append(x)
getChildren(T, x, children)
return children
def question4(T, r, n1, n2):
if not isinstance(T, list):
return "Error Tree not in a list"
if not isinstance(r, int):
return "Error root not an integer"
if not isinstance(n1, int):
return "Node 1 not an integer"
if not isinstance(n2, int):
return "Node 2 not an integer"
n1Children = getChildren(T, n1, [])
try:
if n1Children.index(n2)>= 0:
return getParent(n1)
except ValueError:
pass
n2Children = getChildren(T, n2, [])
try:
if n2Children.index(n1) >= 0:
return getParent(n2)
except ValueError:
pass
item = n1
while getParent(T, item) != r:
try:
items = []
item = getParent(T, item)
children = getChildren(T, item, items)
if children.index(n2):
return item
except ValueError:
pass
return r
Code:
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
def getNext(self):
return self.next
def getLength(self):
if self.next is None:
return 1
else:
length = 1
while not self.next is None:
self = self.getNext()
length += 1
return length
def getData(self):
return self.data
def getDataFromLast(self, index):
length = self.getLength()
if index > length:
return "Error index out of bounds"
for i in range(0, length - index, 1):
self = self.next
return self.data
def question5(ll, index):
if not isinstance(ll, Node):
return "Input not a linked list"
if not isinstance(index, int):
return "Index not an integer"
return ll.getDataFromLast(index)
Code:
Question 1
Given two strings s and t, determine whether some anagram of t is a substring of s. For example: if s = "apple" and t = "pa", then the function returns True. Your function definition should look like: question1(s, t) and return a boolean True or False.
Question 2
Given a string a, find the longest palindromic substring contained in a. Your function definition should look like question2(a), and return a string.
Question 3
Given an undirected graph G, find the minimum spanning tree within G. A minimum spanning tree connects all vertices in a graph with the smallest possible total weight of edges. Your function should take in and return an adjacency list structured like this:
{'A': [('B', 2)],
'B': [('A', 2), ('C', 5)],
'C': [('B', 5)]}
Vertices are represented as unique strings. The function definition should be question3(G)
Question 4
Find the least common ancestor between two nodes on a binary search tree. The least common ancestor is the farthest node from the root that is an ancestor of both nodes. For example, the root is a common ancestor of all nodes on the tree, but if both nodes are descendents of the root's left child, then that left child might be the lowest common ancestor. You can assume that both nodes are in the tree, and the tree itself adheres to all BST properties. The function definition should look like question4(T, r, n1, n2), where T is the tree represented as a matrix, where the index of the list is equal to the integer stored in that node and a 1 represents a child node, r is a non-negative integer representing the root, and n1 and n2 are non-negative integers representing the two nodes in no particular order. For example, one test case might be
question4([[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 0, 0]],
3,
1,
4)
and the answer would be 3.
Question 5
Find the element in a singly linked list that's m elements from the end. For example, if a linked list has 5 elements, the 3rd element from the end is the 3rd element. The function definition should look like question5(ll, m), where ll is the first node of a linked list and m is the "mth number from the end". You should copy/paste the Node class below to use as a representation of a node in the linked list. Return the value of the node at that position.
I had a go myself and I tried to compute the time and space complexities. I list them below. Please let me know if they are correct. I am sorry but at this time I am not available to include detailed explanation of the computation.
Quote:
Question1
time = O(len(s)) where s is the number of the subsequent permutation strings
space = O(len(s)) where s is the number of the subsequent permutation strings
Question2
time = O(n^2) where n is the number of loops that are executed in the palindrome string
space = O (1)
Question3
time = O(n*log(n)) because we sort the indices
space = I still havent done it
Question4
time = O(n^2) where n is the number of nodes in the tree
space = O(n^2)
Question5
time = O(n^2) where n is the number of linked lists. We need to get the length first and then get the index so we loop twice.
space = O(n) where n is the number of linked lists.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.