haydum
BAN USER
Comments (2)
Followers (1)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Create a graph of connections between elements (undirected) and a set containing every single element (etc. unvisited(1,2,3,9,5,6)) . Start from any element in the unvisited set and make a dfs or bfs on the graph. Delete the element from the set when it's visited. And as long as there are still elements at the end of each bfs/dfs, continue the above algorithm. Each separate dfs/bfs gives you the different connections
import collections
def findComponents(connections):
unvisited = set()
graph = collections.defaultdict(list)
for x, y in connections:
graph[x].append(y)
graph[y].append(x) # Graph is undirected
unvisited.add(x)
unvisited.add(y)
components = [[]]
stack = collections.deque()
stack.append(unvisited.pop())
while len(stack) != 0:
node = stack.pop()
components[1].append(node)
print node, unvisited
for nbr in graph[node]:
if nbr in unvisited:
stack.append(nbr)
unvisited.remove(nbr)
if len(stack) == 0:
if len(unvisited) == 0:
return components
else:
components.append([])
stack.append(unvisited.pop())
connections = [(1,2), (2,3), (5,6), (2,9)]
components = findComponents(connections)
print components

haydum
January 17, 2015 Page:
1
Repmarthahiggs71, Intern at Achieve Internet
Hi, I am Martha from Toledo, OH. Working with Top NYC consulting engineers by helping them design controls projects. Have ...
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Find the number of all subsets first; 2^n where n is the size of the array. Then think in binary: start from zero to 2^n1 and check for the bit positions. 2^n1 has n 1's in binary. Loop from 0 to 2^n1, print the numbers in the array when there is a 1 in the counter at this position of the array where the sum of them is zero:
n = 6 (size of the array)
2^n = 64 (size of all possible subsets)
loop from zero to 2^n1
start = 000000
end = 111111
Example: When counter is 33
array : 8, 3, 5, 1,4,8
counter: 1 0 0 0 0 1 (33)
counter: 0 1 1 0 0 1 (25)
Time complexity is: O(2^n)
Space complexity: O(n)
Python solution is here:
 haydum January 17, 2015