## Expedia Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Assuming the following simple structure for the graph,

``````NODE = {
"name": str,
"friends": [NODE]
}``````

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

``````def friendshipDepth(pA, pB, visited = []):
visited.append(pA)
if pB in pA.friends:
return 0
else:
return min([1 + friendshipDepth(friend, pB, visited) for friend in pA.friends if friend not in visited] or [float("inf")])``````

So, if result is 0 : A & B are friends
if 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.

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@likhitd1992
Is your algo an implementation of Depth First Search?

Comment hidden because of low score. Click to expand.
0

*************************************************************************
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.

Comment hidden because of low score. Click to expand.
0

@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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

When I used the DFS approach, I was asked how to deal with looping.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be done using Union-Find Algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider a graph with two people as nodes. If the node are directly connected by an edge, they are friends. If there exists some other path between two,they are friends of friends. Otherwise, not connected

Comment hidden because of low score. Click to expand.
0
of 0 vote

This question has been asked before. See www .careercup. com/question?id=14087784 for one of my previous answers -- you can do better than just naive BFS or DFS.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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>();
while (queue.size() > 0) {
++iterations;
Node node = queue.remove();
if (node == node1) {
System.out.println("iterations=" + iterations);
return true;
}
for (Node friend : node.friendList) {
if (!visitedSet.contains(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>();
int depthTillNextIteration0 = 1;
int depthTillNextIteration1 = 1;
while (queue0.size() > 0 && queue1.size() > 0) {
while (depthTillNextIteration0 > 0) {
++iterations;
Node node00 = queue0.remove();
for (Node friend : node00.friendList) {
if (!visitedSet0.contains(friend)) {
}
}
--depthTillNextIteration0;
}
while (depthTillNextIteration1 > 0) {
++iterations;
Node node11 = queue1.remove();
for (Node friend : node11.friendList) {
if (!visitedSet1.contains(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;
}``````

Comment hidden because of low score. Click to expand.
0

By the way, the second solution was inspired by the post here:
www .careercup. com/question?id=14087784

Comment hidden because of low score. Click to expand.
0

I forgot to include the data structure.

``````class Node {
public int id;
public ArrayList<Node> friendList = new ArrayList<Node>();
public void befriend(Node node) {
}
public String toString() { return String.valueOf(id); }
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
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()) {
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)]) {
}

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");

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

DiGraph g = new DiGraph(DiGraph.TYPE.UNDIRECTED, vertices, edges);
DegreeOfSeparation dgs = new DegreeOfSeparation(g.getVertices().size());
dgs.printPath(g, A, G);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Output :
Shortest Path Between Source and Target
Vertex[A] -- Weight = 0
Vertex[B] -- Weight = 0
Vertex[C] -- Weight = 0
Vertex[E] -- Weight = 0
Vertex[G] -- Weight = 0
[Vertex[A] -- Weight = 0] is friend
of a friend
of a friend
of a friend
of a friend
of [Vertex[G] -- Weight = 0]

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.