3
$\begingroup$

I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):

Given a list of Persons, and two arbitrary Persons out of that list, we need to find the minimum nth-degree relationship between them.

Here are the definitions of Person and a "relationship":

  • A Person is defined as having 2 properties: Name and Age:

    class Person
    {
        public string Name { get; set; }
        public int Age { get; set; }
    }
    
  • A relationship between two Persons is defined as follows:

    1. Two Persons are considered to be in a 1st-degree relationship if they have either the same name or the same age.
    2. Two Persons are considered to be in a nth-degree relationship if they have n people of 1st-degree connecting them.

Example input:

Given the following list of Persons:

persons = [{ Name = "John", Age = 60 }, { Name = "John", Age = 50 }, { Name = "Ted", Age = 50 }]

Then:

  1. The two Johns have a 1st degree relationship (because they have the same name).
  2. The second John and Ted have a 1st degree relationship (because they have the same age).
  3. Hence, the first John and Ted have a 2nd degree relationship (because the second John connects them).

Now, I understand that it's a simple Dijkstra's algorithm question, but what I don't know is how should we build the graph of Persons?

I'm looking for an algorithm, but preferably code, that can build the graph in a time complexity which is better than $O(|V|^2)$.
If you think this question can be solved without building a graph (e.g., using BFS as mentioned in the comments), please let me know how can this be done, but I still want to know how to build the graph.

$\endgroup$
  • $\begingroup$ I don't know if I understand the question, but if you want to find the distance between two vertices $v$ and $u$ (say distance $d$) and create an edge with label $d$ between $v$ and $u$, check out power graphs and transitive closures. $\endgroup$ – Pål GD Sep 29 at 14:31
  • $\begingroup$ @PålGD, if there are specifics you're not sure about my question, I'd be glad to clarify. I googled the terms you mentioned; I'm not sure how can they help in building the graph, but it seems that using them would be an overshoot for this interview question. $\endgroup$ – HelterSkelter Sep 29 at 16:19
  • $\begingroup$ I'm not entirely comfortable with 2. of "relationship". I'd prefer each is in 1st degree relationship with a person in n-1st degree relationship with the other. (consider Ike(5), Ike(6), Ike(7), Sue(6), Sue(7), Sue(8)). What is the problem with the graph? Adjacent is equivalent to either the same name or the same age. $\endgroup$ – greybeard Sep 29 at 16:44
  • $\begingroup$ Do you want to answer the question for a single pair, or for all pairs? If all you want to find is the distance between a single pair of people, it seems that you can just do a single breadth-first search. An advantage of BFS is that you do not need to build the actual graph and leave the structure implicit. If you want a table of all pairs of distances, this output already has size $\Omega(|V|^2)$, so you might as well construct the entire graph. $\endgroup$ – Discrete lizard Sep 30 at 15:48
  • $\begingroup$ @Discrete lizard, you actually touch two goals of my question: I want to (1) answer it for (any) single pair, but I also want to (2) learn how to build the graph. As for (1), I encourage you to make it an answer, because I'm not sure how that BFS solution would go. As for (2), I want to build the graph in a better time complexity than O(|V|^2). $\endgroup$ – HelterSkelter Sep 30 at 16:40
4
$\begingroup$

I assume you want to build the graph of all people, with edges between each pair of people at degree 1. Once you have this graph, it is straightforward to calculate the distance ("degree") between any two people using standard algorithms.

It's easy to build that graph in adjacency list format; or to store it implicitly and generate the adjacency lists on demand.

Store a hash table that maps from name to a list of all people with that name; and another hash table that maps from age to a list of all people with that age. Now, given one person, you can use the hash tables to quickly find all other people who have a first-degree relationship with that person, i.e., who are adjacent in the graph. This lets you build an adjacency list representation of the graph in $O(|V|+|E|)$ time, i.e., linear time rather than quadratic time.

Then, once you have this graph, you can compute distances using BFS in this graph. Note that you can construct the graph on-the-fly as you execute the BFS algorithm; you don't need to build the entire graph in advance.


Footnote: I'm treating hash table lookups as $O(1)$ time. This is a reasonable modelling assumption for practical work. For theoretical work, you can ensure that lookups take $O(1)$ expected time if you use an appropriate hash function, which is nearly as good for most practical purposes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm not clear about how should we get the path using both tables. I guess we should accommodate Guido van Rossum's way for running with two graphs? but how? you can see my current clearly unsuccessful attempt here. I'm also not clear about how can we generate the lists on demand while still keeping the complexity as suggested, but let me first understand the path calculation. $\endgroup$ – HelterSkelter Oct 1 at 22:36
  • $\begingroup$ @HelterSkelter, That's not in the question. You asked how to compute the graph, not how to find paths. I notice now that you haven't defined what graph you want or what you mean by "the graph". Since you know that you can use Dijkstra's to compute the distance between nodes, I assumed you wanted the graph with edges showing first-degree relationships. But, OK, I edited my answer to add that information as well. In the future, please make sure you include a careful specification of exactly what problem you want solved in the question from the start. $\endgroup$ – D.W. Oct 1 at 22:55
  • $\begingroup$ I asked about calculating the path in my last comment because If what you suggest is using two graphs (two hash tables), I don't know how to use Dijkstra for this. But I think this is not what you suggest; you have in mind a graph that is somehow built by combining the two hash tables? You assumed correctly what I mean by "the graph", but still, I'm not clear about how it should be built. It would be of much help if you could add an example displaying two example hash tables and the graph created based upon them. $\endgroup$ – HelterSkelter Oct 1 at 23:17
  • 1
    $\begingroup$ @HelterSkelter please don't put important parts of your question into the comments. As I've mentioned before, we want questions to be self-contained, so people don't have to read the comments to understand what you're asking. Comments exist to help you improve your question, not to provide additional information or requirements not found in the question. BFS is better than Dijkstra's algorithm, and I describe how to build the graph in my answer and how to use it to compute distances. I'm not going to create an example - maybe you'll need to spend some time on this yourself. $\endgroup$ – D.W. Oct 1 at 23:24
  • $\begingroup$ Your solution, which I can see its cleverness, is not something I can Google with something like "BFS over two hash tables" or "... two graphs" or "adjacency list from two hash tables", so unfortunately, without a bit more info about how to build the adjacency list out of the two hash tables, I'm left in the dark. Thank you, though, I appreciate your time and efforts. $\endgroup$ – HelterSkelter Oct 1 at 23:56
1
$\begingroup$

Since your only parameters are name and age, you can make two lists, sort them, and then construct a graph using adjacency list:

$n \gets$ size of the set $\mathbf{persons}$;
$V \gets \{\ \}$; // set of vertices
$\mathit{adj} \gets [\ ]$; // adjacency list
for $i = 1 \to n$ do

$\mathbf{persons}[i].\mathit{id} \gets i$;
$\mathit{adj}[i] \gets [\ ]$; //adjacency list of vertex $v_i$

endfor

$A \gets$ $\mathbf{persons}$ sorted by $\mathit{name}$;
$B \gets$ $\mathbf{persons}$ sorted by $\mathit{age}$;

for $i = 2 \to n$ do

if $A_i.\mathit{name} == A_{i-1}.\mathit{name}$ then
$Q \gets \{(i-1)\}$;
$j \gets i$;
while $A_j.\mathit{name} == A_{i-1}.\mathit{name}$ do
$Q \gets Q \cup \{j\}$;
$j \gets j+1$;
endwhile
add_clique($Q$); // this function runs in $|Q|$ and adds edges between all pairs in $Q$
$i \gets j$;
endif

endfor

for $i = 2 \to n$ do

if $B_i.\mathit{age} == B_{i-1}.\mathit{age}$ then
$Q \gets \{(i-1)\}$;
$j \gets i$;
while $B_j.\mathit{name} == B_{i-1}.\mathit{name}$ do
$Q \gets Q \cup \{j\}$;
$j \gets j+1$;
endwhile
add_clique($Q$);
$i \gets j$;
endif

endfor

The above operations take $O(n \log n)$ time to sort, and $O(n)$ time to create an adjacency list, which is less than $O(n^2)$ unless the number of edges are $O(n^2)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain how can the two sorted lists are then used to find the shortest path between two given persons? your solution is similar to D.W as it separates persons to two data structures, but what I still not get is how to use them to get the path. $\endgroup$ – HelterSkelter Oct 4 at 5:24
  • $\begingroup$ This algorithm builds a graph in $O(n + n \log n)$ time, as you asked in the question. After the graph is obtained, Dijkstra's algorithm can be applied to find shortest path in the graph in $O(n + n \log n)$. $\endgroup$ – padawan Oct 4 at 20:07
  • $\begingroup$ I may be blind, but where is The graph? I see two separate graphs (i.e., two separate lists whose items are connected by edges). Are they supposed to be merged somehow? if so, how? $\endgroup$ – HelterSkelter Oct 4 at 20:27
  • $\begingroup$ @HelterSkelter I made some modifications to improve readability and introduced a variable named id to make it easier to identify the vertices. $\endgroup$ – padawan Oct 4 at 20:54
  • 1
    $\begingroup$ @padawan you can't! That's the point. The best you can do is $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges. $\endgroup$ – D.W. Oct 5 at 17:22
0
$\begingroup$

If there are no other constraints, it's easy to represent the graph using an adjacency matrix. You can construct a matrix where an entry A[3,2] will represent the relationship between persons[3] and persons[2]. So if you want to represent the edge between two "John"s, your entry A[0,1] would be equal to 1. You can iterate through each of the elements of persons and fill the matrix this way. Note that this makes adding a vertex $O(|V|^2)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ shouldn't there be a better solution than O(|V|^2)? $\endgroup$ – HelterSkelter Sep 29 at 17:51
  • $\begingroup$ @HelterSkelter not with a representation using $\Theta(|V|^2)$ space. $\endgroup$ – greybeard Oct 2 at 7:43
  • $\begingroup$ this makes adding a vertex $O(|V|^2)$ I don't see that - adding all vertices should take that long. $\endgroup$ – greybeard Oct 2 at 7:47
  • $\begingroup$ @greybeard, sure, that's what I was implying. D.W. answer does that, but unfortunately I can't figure how to build the adjacency list out of the two hash tables it suggests. It would be great if you can shed some light on it. $\endgroup$ – HelterSkelter Oct 2 at 8:15
  • $\begingroup$ @greybeard, this is as far as I've got. I tried to accommodate Guido van Rossum's algorithm for iterating two hash tables instead of one, so that instead of just iterating upon graph as he does, we need to have an outer graphByName and an inner graphByAge. It doesn't work, and I don't know how to fix it, and it all boils down to me not understanding how to build the adjacency list out of the two hash tables. Any additional help would be great. $\endgroup$ – HelterSkelter Oct 2 at 9:41
0
$\begingroup$

This will be more of a programming/coding companion to D.W.'s answer than a self-contained answer to how should we build the graph of Persons?

You seem to have narrow concept of graph and building a/the graph that I don't seem to share.

I see nodes: Persons and edges: equality of one of a specified set of properties of Person - that's my graph, even before I think of representation.

Different algorithms on graphs need different operations supported - examples:

  • predicate adjacent: given two nodes, are they?
    this can be answered for two nodes in the presentation presented in the question
  • iterating ("outgoing", if directed) edges of a node
    as edges in this problem don't carry information, this is equivalent to iterating directly connected node - I'd skip modelling edges and support the latter.
    How depends on implementation/run-time environment. Alienated by C#, I have to consult docs.microsoft.com to find System.Collections.Generic.IEnumerable<Person> should fit the bill.
    If I assigned to every Person a separate collection of its namesakes and peers, that is bound to require $\Theta(n^2)$ space - not following this train of thought.
    I can build collections of namesakes and collections of peers as I add Persons to the graph (which is what I take D.W. to suggest). To get suitable enumerators without explicitly specifying additional parameters, a C# Person/Node should be a class nested in Graph. The IEnumerable<Person> implementation would yield return each namesake and each peer, skipping the object which was used to invoke it.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ concept of … to share consider to elaborate in the question! $\endgroup$ – greybeard Oct 3 at 10:45
  • $\begingroup$ Thank you. Do you have an idea on how to build the adjacency list out of the two hash tables D.W suggested? $\endgroup$ – HelterSkelter Oct 3 at 16:24
  • $\begingroup$ I don't see a need for an adjacency list. If I wanted it and had the IEnumerable<Person> from above answer, I'd get Persons from it one by one and add them to a list. What do you want an adjacency list for? $\endgroup$ – greybeard Oct 3 at 16:28
  • $\begingroup$ I'm referring it because that's what D.W suggested: "It's easy to build that graph in adjacency list format". But I don't get how it should be built. BTW, if it'd be better for you, I can convert my C# to python. $\endgroup$ – HelterSkelter Oct 3 at 16:33
  • $\begingroup$ [an adjacency list is] what D.W suggested not exactly: he mentioned it as one possibility, to go on and sketch how to store it implicitly and generate the [node] adjacency lists on demand. using two dicts (Python naming). Much the same as sketched above for IEnumarables/generator iterators: for any given person, take the union of its namesakes and peers and take out the person itself. For the graph adjacency list, repeat for all persons. $\endgroup$ – greybeard Oct 3 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.