Amazon Interview Question
InternsCountry: United States
Interview Type: Phone Interview
Elements can be expressed by an array for union find operartions
0 1 2 3 4 5 6 7 8 9 <- Connected to
------------------------
0 1 2 3 4 5 6 7 8 9 <— Element
Step 1: (1,2)
0 1 1 3 4 5 6 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9
Step 2: (2,3)
0 1 1 1 4 5 6 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9
Step 3: (5,6)
0 1 1 1 4 5 5 7 8 9
------------------------
0 1 2 3 4 5 6 7 8 9
Step 4: (2,9)
0 1 1 1 4 5 5 7 8 1
------------------------
0 1 2 3 4 5 6 7 8 9
Now go through all the array and print out connected components
0: 0
1: 1 2 3 9
4: 4
5:5 6
6:
7: 7
8: 8
9:
Isnt this n*logn worst case? Let's say you have 8 elements and you have pairs (0,1) (2,3) (4,5) (6,7) (1,2) (5,6) (3,5). Then your algorithm would have to perform nlogn in the worst case, althought depending on the order the pairs are processed, it could also end up being linear. So the order of the pairs matter, but the worst case complexity is still nlogn. A fine algorithm but slower than some of the ones presented here.
union-find + sort
O(log*(number_of_elements) * number_of_edges + number_of_elements * log(number_of_elements))
It should be either {1,2,3} and {5,6} if we are not considering the second occurance. else it should {1,2,3,9} and {5,6} ..??
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
My solution is not linear...I know that. However, I do not need to create a graph and perform DFS. Simply sort pairs based on smallest value in pair.
(2,3), (5, 1) => (5, 1), (2, 3) because 1 is the smallest value in (5, 1) and is smaller than 2 (the smallest value in (2, 3)).
Now, simply iterate through pairs and determine if consecutive pairs are in the same group (if they contain one of the same numbers). The code is shown below:
public class Pair implements Comparable<Pair> {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public boolean contains(int num) {
return this.x == num || this.y == num;
}
@Override
public int compareTo (Pair other) {
return new Integer(Math.min(x, y)).compareTo(Math.min(other.x, other.y));
}
}
//In some other class
public List<Set<Integer>> computeGroups(List<Pair> pairs) {
List<Set<Integer>> groups = new ArrayList<Set<Integer>>();
Collections.sort(pairs);
Pair pair = pairs.get(0);
Set<Integer> group = new HashSet<Integer>();
group.add(pair.x);
group.add(pair.y);
for(int i = 1; i < pairs.size(); i++) {
if(!pairs.get(i).contains(pair.x) && !pairs.get(i).contains(pair.y)) {
groups.add(group);
group = new HashSet<Integer>();
}
pair = pairs.get(i);
group.add(pairs.get(i).x);
group.add(pairs.get(i).y);
}
groups.add(group);
return groups;
}
A very simple code which uses only a string and trivial delimiters.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
class List {
String list;
List() {
list="";
}
boolean last(int a) {
return list.contains(a+";");
}
void append(int b, int a) {
int i;
list = list.substring(0,(i=list.indexOf(a+";"))+1)+","+b+list.substring(i+1);
}
void add(int a, int b) {
list+=a+","+b+";";
}
void printGroup() {
char c;
for(int i=0; i<list.length();i++)
System.out.print((c=list.charAt(i))==';'?"\n":c);
}
}
public class Group {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
List list=new List();
for(int i=1;i<=n; i++) {
int a = s.nextInt(), b=s.nextInt();
if(list.last(a))
list.append(b,a);
else list.add(a,b);
}
list.printGroup();
}
}
How about build a map<integer, list<integer>>, and then put all the pairs in it. For (2,3), (2,9), it will be {2: [3, 9]}.
And then pop every key from the map, and then concat the corresponding value as well as corresponding value of the value recursively, until there is no corresponding value. Then we get a group.
Repeat above steps until there is no pair left in the map, and then we get all the groups.
var data = [[1,2], [2,3], [5,6], [2,9]];
function func (data) {
var ht = {};
for (var i=0; i<data.length; i++) {
var point = data[i];
if (ht[point[0]] === undefined) {
ht[point[0]] = [];
}
ht[point[0]].push(point[1]);
}
// ht will be something like
// [1] => [2]
// [2] => [3, 9]
// [5] => [6]
var result = [];
var index = 0;
for (var u in ht) {
result.push([parseInt(u)]);
var v_collection = ht[u];
for (var j=0; j<v_collection.length; j++) {
result[index].push(v_collection[j]);
var v = v_collection[j];
if (ht[v] !== undefined) {
result[index] = result[index].concat(ht[v]);
delete ht[v];
}
}
index +=1
}
return result;
}
func(data);
One way you can do this is make nodes for each number, then add connections in code.
- Skor January 16, 2015Put all of these nodes into a List (L)
Now, run DFS on one node- All nodes in the visited list of this DFS will be part of a set (group), Now, remove all the nodes in the visited list from L. With whatever node is left in L,run DFS and repeat the same process until L is empty.