Google Interview Question
Software Engineer / DevelopersCountry: -
what benefit does a hashmap add as compared to just a list of Node objects and the Node class contains the list of adjacent Nodes.
The question says "Define a class to represent a graph...that supports addEdge(Node n1, Node n2)". That seems to indicate the Node class has already been defined elsewhere and that we aren't supposed to modify it. We should build another class to store the edge relationships instead. That's why I am using a HashMap.
Otherwise, if we just need to support these 2 operations, I agree having a single Node class to contain the adjacent Nodes might be easier. But if we were to start implementing other methods such as removeNode(Node n), then the HashMap approach would be better again.
I agree with Sunny here. Otherwise why would other people mention adjacency matrices or lists of tuples? The nice thing about a hashtable solution is you can still get a list of edges for a node in constant time. The adjacency matrix could become quite large and the list of tuples need to be iterated over or binary searched upon if they are sorted in some way.
I'm not sure if I got this question right.
In case we don't need to delete nodes from graph we can use a classic graph representation, such as adjacency list or adjacency matrix.
If we implement adjacency list with std::vector it will take amortized constant time to add a new node or edge. Also there is no trouble to distinguish an edge n1->n2 from n2->n1.
Assume we have a matrix .. ( adjacency matrix ) adj[3][3] (assuming we have only 3 vertices)..
while adding an edge just mention the source and destination as node1 and node2 ..
i.e
addEdge(Node n1,Node n2)
{
...
...
adj[n1][n2]=1;
...
..
}
here we can see that we have edge from some vertex to other only if there is '1' ... similarly
here there wont be edge from n2 to n1
The graph can be represented as an adjancency matrix or list of nodes with list of tuples for directed edges.
In an adjancency matrix representation, the edge direction can be stored by having 1
for adj[i][j] = 1 such tht i->j is a directed edge.
In the tuple representation, <i, j>, where i->j is a directed edge.
Here is my solution that uses multi-structured linked list to solve the problem:
"I know its a bit complicated, but when you will run the code, you will know that it works". :)
The solution might seem a bit complicated because I have modified the problem to also hold relations to other node data such as distance between two nodes, to make the problem more challenging.
Each node contains its ID and a link to another structure called Link. This "structure", Link is a linked list where each node of this link list tells what other nodes this node is connected to.
Link contains two fields. One field points to the actual structure (Relation) where all the data is kept such as what is the distance to the other node and what node it is connected to.
The other field just points to the next structure.
The header file goes as follows:
#include <stdio.h>
#include <stdlib.h>
#ifndef __GRAPHNODES
#define __GRAPHNODES
struct nodeRelation;
struct linkStructure;
struct nodeStructure;
typedef struct nodeRelation
{
int distance;
struct nodeStructure *peer;
} Relation;
typedef struct linkStructure
{
struct nodeRelation *edge;
struct linkStructure *next;
} Link;
typedef struct nodeStructure
{
int id;
struct linkStructure *relations;
} Node;
Node* createNode(int givenID)
{
Node *temp = (Node*) malloc (sizeof(Node*));
temp->id = givenID;
temp->relations = NULL;
}
void addEdge(Node *src, Node *dest, int givenDistance)
{
Link *newLink = (Link*) malloc (sizeof(Link*));
Relation *newRel = (Relation*) malloc (sizeof(Relation*));
newRel->distance = givenDistance;
newRel->peer = dest;
newLink->edge = newRel;
newLink->next = NULL;
if (src->relations == NULL)
{
src->relations = newLink;
}
else
{
Link *temp = src->relations;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newLink;
}
}
void printRelations(Node *myNode)
{
printf("Node ID: %d.\n\n", myNode->id);
printf("Node Relations are: \n\n");
Link *temp = myNode->relations;
if (temp != NULL)
{
do
{
printf("Related To: %d\n", temp->edge->peer->id);
printf("Distance: %d\n\n", temp->edge->distance);
temp = temp->next;
} while (temp != NULL);
}
else
{
printf("No Relations Found.\n\n");
}
printf("-------------------------------------\n\n");
}
#endif
And the main file goes as follows:
#include "graphNodes.h"
int main()
{
Node *one = createNode(1);
Node *two = createNode(2);
Node *three = createNode(3);
Node *four = createNode(4);
Node *five = createNode(5);
addEdge(one, two, 10);
addEdge(one, four, 20);
addEdge(one, five, 30);
addEdge(two, one, 15);
addEdge(two, five, 30);
addEdge(three, five, 50);
printRelations(one);
printRelations(two);
printRelations(three);
printRelations(four);
printRelations(five);
return 0;
}
"How do you differentiate between an edge n1->n2 and n2->n1"
This depends on the type of graph - is it directed or not. If it's a directed graph then something similar to list of adjacent nodes for each node will do. Otherwise, you can use adjacency matrix, implemented as a sparce array to preserve the space to be allocated for the lower part of the main diagonal of the NxN matrix, where N is the count of vertices.
I would use a HashMap<Node, List<Node>> to store the nodes as keys and the list of adjacent nodes as values. That way both operations take O(1). The adjacency matrix approach isn't optimal for supporting these 2 operations, because you would need to expand the matrix (a 2-dimensional array) with each additional node.
- Sunny June 27, 2013