Yahoo Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

They may or may not be in order. No we do not know the total number of elements.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can this be done in merge find...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

entire set is consistent in constant time ?? how is this possible.. this is takin linear time

Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually there is even a better method...

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0

Great solution. But is the map.put(obj, parent); in find() really necessary?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do we have any correct solution for this question?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Iterate through the equalities set. Add each element to hashmap1 <elem, dummy>
2. Iterate through the inequalities set. If both the elements are present in the hashmap1, return false.
In short, A = B = C is consistent. A != B != C is not consistent.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do we have correct O(n) solution for this?

Comment hidden because of low score. Click to expand.
0

The disjoint set solution is a correct solution. It takes O(N) amortized time to create the set and O(1) amortized time to test each inequality.

The BFS/DFS based solution is also a correct solution. But It is O(N) to test each inequality.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.