CareerCup

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

Can this be done in merge find...

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.

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

Actually there is even a better method...

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

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

Do we have any correct solution for this question?

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.

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