## Expedia Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Two points here:

1. you are trying to return min of something, I can see one of the element, don't know what's second

2. most probably will go into an infinite loop (will leave it to you to find why)

You are right about the infinite loop. Edited the code to handle it. But I didn't understand your first point. I am returning the min elem in the list (the list of all possible depths from A to B).

ok...got it. i didn'tha quite understand earlier what you were trying to minimizing with that min statement

*************************************************************************

Just want to clarify what need to find out is whether any given two people are in a friend chain or not. A friend chain means either one is a friend of the other or one is a friend of a friend of ... of the other.

@Learner, yes it is.

@fz, That is what it does. If 2 people are in a friend chain it will return the distance between them in the chain(0 for direct friends, 1 for one mutual friend in the middle,..). If they don't happen to be friends, they algorithm will return infinity(since the distance between them is infinite).

This can be done using either DFS or BFS. However, the BFS would provide the shortest path, assuming the edges are all equally weighted (i.e., they are all one).

Here are 2 solutions. The first one is simple BFS and the second one uses bi-directional BFS with set intersection at each distance level.

```
// Using BFS
// O(x^d) where x = average number of friends and d = distance between nodes
public boolean isRelated1(Node node0, Node node1) {
if (node0 == node1) {
return false;
}
int iterations = 0;
HashSet<Node> visitedSet = new HashSet<Node>();
ArrayDeque<Node> queue = new ArrayDeque<Node>();
queue.add(node0);
while (queue.size() > 0) {
++iterations;
Node node = queue.remove();
if (node == node1) {
System.out.println("iterations=" + iterations);
return true;
}
visitedSet.add(node);
for (Node friend : node.friendList) {
if (!visitedSet.contains(friend)) {
queue.add(friend);
}
}
}
System.out.println("iterations=" + iterations);
return false;
}
// Using bidirectional BFS + set intersection.
// Perform BFS starting from each node. At each distance level, perform an intersection of each visited set.
// ~O(x^(d/2) + x^(d/2)) where x = average number of friends and d = distance between nodes
public boolean isRelated2(Node node0, Node node1) {
if (node0 == node1) {
return false;
}
int iterations = 0;
HashSet<Node> visitedSet0 = new HashSet<Node>();
HashSet<Node> visitedSet1 = new HashSet<Node>();
ArrayDeque<Node> queue0 = new ArrayDeque<Node>();
ArrayDeque<Node> queue1 = new ArrayDeque<Node>();
queue0.add(node0);
queue1.add(node1);
int depthTillNextIteration0 = 1;
int depthTillNextIteration1 = 1;
while (queue0.size() > 0 && queue1.size() > 0) {
while (depthTillNextIteration0 > 0) {
++iterations;
Node node00 = queue0.remove();
visitedSet0.add(node00);
for (Node friend : node00.friendList) {
if (!visitedSet0.contains(friend)) {
queue0.add(friend);
}
}
--depthTillNextIteration0;
}
while (depthTillNextIteration1 > 0) {
++iterations;
Node node11 = queue1.remove();
visitedSet1.add(node11);
for (Node friend : node11.friendList) {
if (!visitedSet1.contains(friend)) {
queue1.add(friend);
}
}
--depthTillNextIteration1;
}
depthTillNextIteration0 = queue0.size();
depthTillNextIteration1 = queue1.size();
iterations += visitedSet0.size();
if (intersects(visitedSet0, visitedSet1)) {
System.out.println("iterations=" + iterations);
return true;
}
}
System.out.println("iterations=" + iterations);
return false;
}
public boolean intersects(HashSet<Node> set0, HashSet<Node> set1) {
for (Node node : set0) {
if (set1.contains(node)) {
return true;
}
}
return false;
}
```

By the way, the second solution was inspired by the post here:

www .careercup. com/question?id=14087784

package com.test.graph.algo;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.List;

import java.util.Queue;

/*

* Expedia----

* I rephrase the original question as the following: Let say in Facebook,

* given two person A and B. Write a function to find out whether A is a friend or a friend

* of a friend of ... of B.

*/

import java.util.Stack;

/*

* Amazon---

* Consider any social networking website like facebook etc.

* Design an algorithm / function that calculates minimum degree of connection

* between given two users. Assume that you are have already written function that

* returns a list of friends of given user :

* getFriends(username/id) : its similar to getting no of edges for the given vertex.

*/

public class DegreeOfSeparation {

DiGraph.Vertex [] pathTo;

public DegreeOfSeparation(int size){

pathTo = new DiGraph.Vertex[size];

}

/*

* Traverse till target vertex t is not visited,once t is visited hence we have found

* the shortest path between given friend A and B.

*/

public void bfs(DiGraph g, DiGraph.Vertex v, DiGraph.Vertex t){

Queue<DiGraph.Vertex> queue = new ArrayDeque<>(g.getVertices().size());

queue.add(v);

v.setVisited(true);

DiGraph.Vertex w;

boolean found = false;

while (!queue.isEmpty() && !found) {

v = queue.remove();

for (DiGraph.Edge e : v.getEdges()) {

w = e.getTo();

if (!w.isVisited()) {

queue.add(w);

w.setVisited(true);

pathTo[g.getIndexOf(w)] = v;

}

if (t.isVisited()) {

found = true; // traverse till t is not visited

break;

}

}

}

}

public void printPath(DiGraph g, DiGraph.Vertex s, DiGraph.Vertex t){

//call bfs to prepare the path

bfs(g, s, t);

Stack<DiGraph.Vertex> stack = new Stack<DiGraph.Vertex>();

for (DiGraph.Vertex x = t; x != s; x = pathTo[g.getIndexOf(x)]) {

stack.add(x);

}

stack.add(s);

System.out.println("Shortest Path Between Source and Target");

while (!stack.isEmpty()) {

System.out.println(stack.pop());

}

//or if we want to print in format A is friend of a Friend of B

System.out.println("["+s+"] is friend");

for (DiGraph.Vertex x = t; x != s; x = pathTo[g.getIndexOf(x)]) {

System.out.println("of a friend");

}

System.out.println(" of ["+t+"] ");

}

public static void main(String[] args) {

List<DiGraph.Vertex> vertices = new ArrayList<DiGraph.Vertex>();

DiGraph.Vertex A = new DiGraph.Vertex("A");

/*

* If Inner class graph and edge were not static then

* First we have to instantiate Graph and then vertex/edge

* eg :

* Grapg g1 = new Graph();

* Graph.vertex A = g1.new Vertex('A');

*

*/

DiGraph.Vertex B = new DiGraph.Vertex("B");

DiGraph.Vertex C = new DiGraph.Vertex("C");

DiGraph.Vertex D = new DiGraph.Vertex("D");

DiGraph.Vertex E = new DiGraph.Vertex("E");

DiGraph.Vertex F = new DiGraph.Vertex("F");

DiGraph.Vertex G = new DiGraph.Vertex("G");

DiGraph.Vertex H = new DiGraph.Vertex("H");

vertices.add(A);

vertices.add(B);

vertices.add(C);

vertices.add(D);

vertices.add(E);

vertices.add(F);

vertices.add(G);

vertices.add(H);

List<DiGraph.Edge> edges = new ArrayList<DiGraph.Edge>();

edges.add(new DiGraph.Edge(0,A,B));

edges.add(new DiGraph.Edge(0,B,C));

edges.add(new DiGraph.Edge(0,H,B));

edges.add(new DiGraph.Edge(0,C,D));

edges.add(new DiGraph.Edge(0,C,E));

edges.add(new DiGraph.Edge(0,E,H));

edges.add(new DiGraph.Edge(0,E,F));

edges.add(new DiGraph.Edge(0,E,G));

DiGraph g = new DiGraph(DiGraph.TYPE.UNDIRECTED, vertices, edges);

DegreeOfSeparation dgs = new DegreeOfSeparation(g.getVertices().size());

dgs.printPath(g, A, G);

}

}

Assuming the following simple structure for the graph,

The following function will return the minimum length of the mutual friend chain needed to connect person A (pA) and person b(pB).

So, if result is 0 : A & B are friends

- likhitd1992 November 28, 2012if result is 1 : A is friend of friend of B

if result is 2 : A is friend of friend of friend of B

and so on.