Yahoo Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Step 1: Create a graph based on equalities. When two element are equal, add a link between them in the graph.
Step 2: Label the graph connected component (using bfs or dfs) in linear time.
Step 3: For each inequalty check whether there is a link between the two side in the graph. If there is, return No
Step 4: return yes.
Use a UnionFind datastructure to construct a set of unions with the equalities.
Then use the UnionFind to ensure that the inequalities are all valid.
Runtime complexity of O(e + i) where e = equalities and i = inequalities.
Memory complexity = O(n) where n is the number of distinct object names.
static class MapUnionFind<T>{
HashMap<T,T> map;
MapUnionFind(){
map = new HashMap<T,T>();
}
private void union(T obj1, T obj2){
T rootObj1 = find(obj1);
T rootObj2 = find(obj2);
if(depth(obj1) > depth(obj2) ){
map.put(rootObj2, rootObj1);
}
else{
map.put(rootObj1, rootObj2);
}
}
private int depth(T obj){
int count = 0;
while( (obj = map.get(obj) ) != null){
count++;
}
return count;
}
private int find(T obj){
T parent = map.get(obj);
if(parent == null){
return obj;
}
parent = find(parent);
map.put(obj, parent);
return parent;
}
}
public static boolean isConsistent(Equality[] eArr, Inequality[] iArr){
UnionFind<String> uf = new UnionFind<String>();
for(Equality e : eArr){
String[] names = separate(e);
uf.union(names[0], names[1];
}
for(Inequality i : iArr){
String[] names = separate(i);
String root1 = uf.find(names[0]);
String root2 = uf.find(names[1]);
if(root1.equals(root2)){
return false;
}
}
return true;
}
Again, would help if I proofed my code. The using static function should be written as follows (and actually use a MapUnionFind):
public static boolean isConsistent(Equality[] eArr, Inequality[] iArr){
MapUnionFind<String> uf = new MapUnionFind<String>();
for(Equality e : eArr){
String[] names = separate(e);
uf.union(names[0], names[1];
}
for(Inequality i : iArr){
String[] names = separate(i);
String root1 = uf.find(names[0]);
String root2 = uf.find(names[1]);
if(root1.equals(root2)){
return false;
}
}
return true;
}
Is there transitive existed? I mean if A, B are in equal, B, C in unequal. Can we get A is not equal to C?
my solution is:
1.build a 2 dimension array to represent the relation between any two letters
2.full the matrix to satisfy equal array.(n^2)
3.full the matrix to satisfy unequal array.(n^2)
4.use the matrix to get answer
Are they given in the order that A=B, then C=A is not possible? Do i know the total number of elements from before/can i have a list of them? please clarify
- mariushtcwild October 26, 2014