HackerRank: [Python Question] GET STORAGE | Python-3 Solution by APDaga

I came across a Python 3 practice question by HackerRank. 

Here, I am providing my solution to the problem "Get Storage" with the intention to help you learn and understand Python 3 in a better way.

Please make use of my blog posts for learning purposes only and feel free to ask your questions in the comment box below in case of any doubt.

Click Here to check out all other HackerRank solutions.

Recommended Python Courses:
1. Udemy: Top Python Courses
2. Udemy: 2021 Complete Python Bootcamp From Zero to Hero in Python
3. Udemy: Learn Python Programming Masterclass
4. Coursera: Python for Everybody
5. LinkedIn: Become a Python Developer
6. edX: Programming for Everybody (Getting Started with Python)
7. edureka: Python Programming Certification Training
8. Eduonix: Mighty Python Bundle

---

Python Problem Description:

There are a number of computers which are connected to each other. Each computer has a storage capacity which can be used to store data. When a computer is connected to another, they form a set of computers

and the storage capacity of the set is the sum of the storage capacities of the computers in the set.

You are given the set of connections between the computers by the arrays connections_from and connections_to (The connections are bi-directional). The initial storage capacities are denoted by

storage[storage[0],...,storage[connections_nodes-1]]. Also, you are given a threshold of storage capacity. After every connection, you are required to find the number of sets of computers which have storage capacity

less than or equal to threshold.

Note: Initially there are no connections between the computers and each computer can be considered as a set with 1 computer.

For example

• connections_nodes = 3. storage = {2, 3, 6}, connections_from = {0, 0, 2}, connections_to = {1, 2, 1}, threshold = 6.
  
  
• After 1st connection {0, 1}: {5, 6} (2 values are less than or equal to 6)
  
  
• After 2nd connection {0, 2}: {11} (no value is less than or equal to 6)
  
  
• After 3rd connection {2, 1}: {11} (no value is less than or equal to 6)

Return an array containing the answer after each connection.

---

Function Description:

Complete the function getStorage in the editor below. The function must return a vector. get_storage has the following parameter(s):

• connections_nodes: an integer denoting the number of computers
  
  
• connections_from: an array of integers denoting the ith connection
  
  
• connections_to: an array of integers denoting the ith connection
  
  
• storage: an array of integers denoting the initial storage capacities
  
  
• threshold: an integer

---

Constraints:

• 1 ≤ connections_nodes ≤ 105
• 1 ≤ connections_edges ≤ min( (connections_nodes) * (connections_nodes-1)/2, 105)
• 0 ≤ connections_fromi, connections_toi < connections_nodes
• 1 ≤ storage i ≤ 104
• 1 ≤ threshold ≤ 109
• The graph does not contain a self-loop or multiple edges between two nodes.
  
  

---

Input Format For Testing:

• The first line contains 2 space-separated integers, connections_nodes and connections_edges, denoting the number of computers and number of connections respectively.
  
  
• Each line i of the connections_edges subsequent lines (where 0 ≤ i < connections_edges) contains 2 space-separated integers describing connections_from i and connections_to i.
  
  
• The next line contains an integer, connections_nodes, denoting the number of elements in storage.
  
  
• Each line i of the connections_nodes subsequent lines (where 0 ≤ i < connections_nodes) contains an integer storage i.
  
  
• The last line contains the integer threshold.

---

Sample Case 0:

Sample Input For Testing:

5 3
0 1
1 4
0 4
5
1
2
3
4
5
4

---

Sample Output:

3
2
2

Explanation:

• Initial storage capacities: {1, 2, 3, 4, 5}
  
  
• After 1st connection {0, 1}: {3, 3, 4, 5} (3 values are less than or equal to 4)
  
  
• After 2nd connection {1, 4}: {3, 4, 8} (2 value is less than or equal to 4)
  
  
• After 3rd connection {0, 4}: {3, 4, 8} (2 value is less than or equal to 4)

---

Sample Case 1:

Sample Input For Testing:

3 2
0 1
1 2
3
1
2
3
4

Sample Output:

2
0

Explanation:

• Initial storage capacities: {1, 2, 3}
  
  
• After 1st connection {0, 1}: {3, 3} (2 values are less than or equal to 4)
  
  
• After 2nd connection {1, 2}: {6} (no value is less than or equal to 4)

---

###############Write your solution below##################
def get_storage(connection_nodes, connection_edges, connections_from, connections_to, storage, threshold):
# Complete the getStorage, append your answers to 'ans' list
# ans[i] = answer to i-th query for connections_from[i] and connections_to[i]
ans = []

# Task-3: Write your code here
return ans

# Task-1: Prepare your input Params
ans = get_storage(connection_nodes, connection_edges, connections_from, connections_to, storage, threshold)
for _ in range(0,len(ans)):
print(ans[_])

Task Weightage:

Sr No.  Task                                                                 Weightage
1.	Preparation of Input param for function 				 30%
2.	Algorithm design (Pseudo code, Time Complexity, Memory Complexity )	 40%
3.	Completion of function(Coding) 					 30%

Note: You can choose any language for coding Java, c++, python, go.

Try to code on your local machine and final script update here.

---

Python 3 Solution:

# nodes = 5
# num_edges = 3
# edges = [(0, 1), (1, 4), (0, 4)]
# storages = [1, 2, 3, 4, 5]
# threshold = 4

nodes = int(input("Enter no. of nodes: "))
num_edges = int(input("Enter no. of edges: "))

edges = []
for i in range(num_edges):
    edges.append(tuple(map(int, input("edge "+str(i+1)+" = ").split(" "))))
 
storages = []
for i in range(nodes):
    storages.append(int(input("Storage "+str(i)+" = ")))
    
threshold = int(input("Enter the threshold: "))


# connection_map = [[0] * nodes for n in range(nodes)]
# print(connection_map)

class Graph:

    # init function to declare class variables
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]

    def DFSUtil(self, temp, v, visited):

        # Mark the current vertex as visited
        visited[v] = True

        # Store the vertex to list
        temp.append(v)

        # Repeat for all vertices adjacent
        # to this vertex v
        for i in self.adj[v]:
            if visited[i] == False:
                # Update the list
                temp = self.DFSUtil(temp, i, visited)
        return temp

    # method to add an undirected edge
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)

    # Method to retrieve connected components
    # in an undirected graph
    def connectedComponents(self):
        visited = []
        cc = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                cc.append(self.DFSUtil(temp, v, visited))
        return cc
        
# Driver Code
if __name__ == "__main__":
    # Create a graph given in the above diagram
    # 5 vertices numbered from 0 to 4
    g = Graph(nodes)
    for edge in edges:
        from_node, to_node = edge
        g.addEdge(from_node, to_node)

        cc = g.connectedComponents()

        print("\nFollowing are connected components")
        print(cc)

        new_storages = []

        for connected_component in cc:
            if len(connected_component) == 1:
                new_storages.append(storages[connected_component[0]])
            else:
                storage = 0
                for i in connected_component:
                    storage = storage + storages[i]
                new_storages.append(storage)

        count = 0
        for storage in new_storages:
            if storage <= threshold:
                count = count + 1
        print("Set of Computer having storage less than of equal to threshold:")
        print(count)

---

Output:

[Case-0] Output:

# Following are connected components
# [[0, 1], [2], [3], [4]]
# Set of Computer having storage less than of equal to threshold:
# 3

# Following are connected components
# [[0, 1, 4], [2], [3]]
# Set of Computer having storage less than of equal to threshold:
# 2

# Following are connected components
# [[0, 1, 4], [2], [3]]
# Set of Computer having storage less than of equal to threshold:
# 2
# > 

[Case-1] Output:

# Enter no. of nodes: 3
# Enter no. of edges: 2
# edge 1 = 0 1
# edge 2 = 1 2
# Storage 0 = 1
# Storage 1 = 2
# Storage 2 = 3
# Enter the threshold: 4

# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

# Following are connected components
# [[0, 1], [2]]
# Set of Computer having storage less than of equal to threshold:
# 2

# Following are connected components
# [[0, 1, 2]]
# Set of Computer having storage less than of equal to threshold:
# 0
# > 

--------------------------------------------------------------------------------

Click here to see solutions for all Machine Learning Coursera Assignments.

&

Click here to see more codes for Raspberry Pi 3 and similar Family.

&

Click here to see more codes for NodeMCU ESP8266 and similar Family.

&

Click here to see more codes for Arduino Mega (ATMega 2560) and similar Family.

Feel free to ask doubts in the comment section. I will try my best to answer it.

If you find this helpful by any means, like, comment and share the post.

This is the simplest way to encourage me to keep doing such work.

Thanks & Regards,

-Akshay P Daga