CareerCup

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.

class Node {
	private Object nodeData;
	public Node(Object nodeData) {
		this.nodeData = nodeData;
	}
}

class GraphRepresentation {
	private HashMap<Node, LinkedList<Node>> nodes = new HashMap<Node, LinkedList<Node>>();

	public void addEdge(Node n1, Node n2) {
		nodes.get(n1).add(n2);
		nodes.get(n2).add(n1);
	}

	public void addNode(Object nodeData) {
		nodes.put(new Node(nodeData), new LinkedList<Node>());
	}
}

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

Store nodes in a list.
Store edges in a list of tuples.
Example, <n1,n2> represents an edge n1->n2. In a list the lookup will be O(n).

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.

take a map and linked list , map will store node_value and corresponding linked_list start address.
Linked list will keep information about those nodes with whom that node is connected.

I did research on Graphics. If you have some computer graphics background, you can tell clearly he was expecting the answer: helf-edge structure, which is some basis knowledge in this field.