Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Is your solution scalable ???? Adjacency Matrix is NOT recommended when large number of nodes are under consideration... One of aspects which any interviewer would be targeting.
@Bevan: Why can't you store the adjacency matrix in a distributed way? One thing that comes to mind is use a distributed hash table with (i,j) (row/column/vertex numbers) as the key and 0 or 1 (denoting adjacency) as the value.
BFS can probably be parallelized too...
Use BFS.
Consider people as nodes. And their friendship as an edges between the nodes.
To improvise on the algorithm, run BFS from Both ends, and some kind of book keeping, like a Hashmap to keep track to visited nodes. ( Proof given by eugene in some previous post, If needed I will explain.)
Thanks Bevan .. BFS meaning - Breadth First Search right ? Which Data Structure should I use to first store these values ? I was thinking to first get all the distinct values and then create a two dimensional array of those values eg : In the list above I have 7 distinct values so I create an array of arr[7][7] ? Which data structure is ideal to store Matrix ? Any pseudocode will be really helpful...I need to create a working version
Yes. It is Breadth First Search.
Well, IF and only IF the problem has a size 7(or some small number), please feel free to go ahead with this 2D Structure.
But in practicality, this is never the case. You will be required to create adjacency list exactly as mentioned in the question.
Since you want a working code quickly, (there can multiple ways to implement this. I find this to be the simplest)
class Person
{
String name;
List<Person> friendsList;
}
some Global HashMap to get a quick handle of any Person..
now just scan the people.
look at their friend list. Use the Hashmap created above to get a reference to the friend, add it to their corresponding friendsList..
Now you have your graph.. Just run a BFS(Lookup Wikipedia) ...
Thats all you need to do...
The level at which meet is your degree of connection.
Thanks again Bevan..The problem is we have to find a degree of connection if the two people are not directly friends. The question states an example :
"John has a 2nd degree connection to June since June has a 1st degree connection to Jim" --> They first find out Jim and then since is Jim is common between John and June they made is second degree ..this is where I am getting lost ...
Thanks Kai..for your help but this logic is going in infinite loop :
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication1
{
public class node
{
public int nodeValue;
public int degree;
public node(int nodeValue, int degree)
{
this.nodeValue = nodeValue;
this.degree = degree;
}
}
class Program
{
public Boolean[,] adjMatrix;
static void Main(string[] args)
{
Program p = new Program();
p.Initialize();
}
/* parse the strings & represent them in a Graph structure.. i'm using matrix representation here
* node-> person
* edges-> relationship (i.e. connected or not )
* In the above example
* John, Jane, Jill, Jim, Jeb, June,Jason represented by vertices
* 0, 1, 2, 3, 4, 5, 6
*
* I'm using String[] array for convinience to represent the connections as below
* each index referring to each person as above, and each string value representing the connections to the persons.
*/
public void Initialize()
{
string[] connections = { "1:2:4:3",
"0:6:5",
"0:3",
"0:2:5",
"5:0",
"3:1:4",
"1"
};
int totalNodes = connections.Length;
adjMatrix = new Boolean[totalNodes, totalNodes];
//initially there are no connections among the nodes..
for (int i = 0; i < totalNodes; i++)
{
for (int j = 0; j < totalNodes; j++)
{
adjMatrix[i, j] = false;
}
}
//setting up the connections
// from the problem statement, its indicated that it's an undirected graph
// ( this can be seen from the connections that are made in the graph )
for (int i = 0; i < totalNodes; i++)
{
string[] str = connections[i].Split(':');
foreach (string st in str)
{
int j = Convert.ToInt32(st);
adjMatrix[i, j] = true;
}
}
int node1, node2;
// eg: You would like to know the connection degree b/w John & June
// so node1-> 0, node2-> 5
node1 = 0;
node2 = 5;
//use Breadth First Search to get the degreee of connection
BFS(node1, node2, totalNodes);
}
public void BFS(int source, int target, int totalNodes)
{
int degree=0;
Boolean found=false;
Boolean[] color = new Boolean[totalNodes];
for(int i=0;i<totalNodes;i++)
color[i]=false;
Queue<node> q = new Queue<node>();
q.Enqueue(new node(source,0));
//Deque<node> q= new ArrayDeque<node>();
//q.add(new node(source,0));
node tempNode = new node(0,0) ;
while(q.Count != 0 && !found)
{
tempNode = (node) q.Peek();
if(tempNode.nodeValue == target){
found=true;
degree = tempNode.degree;
break;
}
if(color[tempNode.nodeValue]){
continue;
}
color[tempNode.nodeValue]=true;
for(int i=0;i<totalNodes;i++){
if(adjMatrix[tempNode.nodeValue,i])
{
q.Enqueue(new node(i,tempNode.degree+1));
}
}
}
if(found){
Console.WriteLine("Degree -> "+degree);
}
else
Console.WriteLine(" Not Connected ");
}
}
}
Kai's program is excellent. One thing to note is it will detect 2nd degree connnection between John and June by 1) John is friend with Jane and Jane is friend with June. The explaination given in problem is still valid but if you run Kai's program, this is how it will determine the 2nd degree connection
As I said BFS is the solution to the problem.. so i thought y not code it and present it to you
instead of a pseudo code.. once you understand BFS, its simple to understand all the code..
- Kai March 20, 2013