1

I was recently asked this in an interview for a SDE role.

Suppose you have a list of User objects

class User {
    String userId;
    String email;
    String ip_addr;
} 

where userId field is unique among all users, while ip_addr and email are not necessarily so.

and you know some users have more than one user account (if any two User objects share a common email OR an ip_addr, you classify them as belonging to the same user).

you are required to write a function, whose signature is given as:

List<List<User>> findDups(User[] userList) {
    // code here
}

[EDIT] so for example, if there are 7 users, only 2 of which are unique, the function can return something like the following (not necessarily in this specific order):

{
    {user1, ip1, email1}, 
    {user5, ip5, email1}, 
    {user24, ip5, email2}
},

{
    {user2, ip2, email2},
    {user7, ip2, email7},
    {user8, ip2, email0},
    {user19, ip19, email7}
}

here, in this first group, the first user (user1) is the same user as the second one (user5) as they share the same email address. We also know that the third user (user24) is also the same user as it shares the same ip address (ip5) as the second user in the list. [/END EDIT]

what data structure would you use and what would be the time complexity of the proposed solution?

I tried to use disjoint set union (quick union), which would give me linear complexity, however the interviewer constantly tried to steer me away from that and said just the Collection API would be enough (Using Lists and Sets and maps).

What would be your approach and solution and the corresponding time complexity?

Gokay
  • 758
  • 5
  • 9
  • Could you clarify this a bit? What exactly is that method supposed to return? (I dont get the list of list part - you are not asking to identify all those entries that have an email or ip_addr in common)? – GhostCat Mar 24 '17 at 07:26

0 Answers0