2 votes 2 votes 1. What is equivalence relation? 2. How can u represent equivalence. relation with a data structure? 3. Which data structure? how efficient? How can u test for. equivalence efficiently? Interview Questions data-structures + – Rajesh Pradhan asked Feb 22, 2016 Rajesh Pradhan 1.5k views answer comment Share Follow See 1 comment See all 1 1 comment reply Arjun commented Mar 17, 2016 reply Follow Share no answer :O 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Can't we use directed graphs for representing equivalence relations? SnehaK answered Mar 21, 2016 SnehaK comment Share Follow See all 19 Comments See all 19 19 Comments reply Show 16 previous comments Arjun commented Mar 21, 2016 reply Follow Share In a graph representation each element of the set will be a vertex and each equivalent class correspond to a strongly connected component rt? Usually for interviews questions go like this - they tell us answer and take our feedback too :) 0 votes 0 votes abhilashpanicker29 commented Mar 21, 2016 reply Follow Share Again, to make it clear, 1. If we are already given that the input relation is equivalence relation, then the strongly connected component would give the correct partition.. we can find using DFS numbering method - i think it has complexity O(V+E) for adjacency lists, and O(V2) for adjacency matrix, in any case less efficient than the disjoint set DS. 2. but for general case of a relation, this might not be true.. Strongly connected component need not necessarily imply partitions i think.. Take this graph for example.. 1 votes 1 votes Arjun commented Mar 21, 2016 reply Follow Share yes, I meant the first case.. 1 votes 1 votes Please log in or register to add a comment.