Expedia Interview Question for Software Engineer / Developers


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.

- likhitd1992 November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- The Artist November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- likhitd1992 November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- The Artist November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Learner November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- fz November 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- likhitd1992 November 28, 2012 | Flag
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).

- Anonymous November 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- fz November 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Manoj Kumar November 29, 2012 | Flag Reply
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

- Megha Mantri December 05, 2012 | Flag Reply
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.

- eugene.yarovoi December 06, 2012 | Flag Reply
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>();
		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;
	}

- gudujarlson August 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gudujarlson August 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I forgot to include the data structure.

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

- gudujarlson August 13, 2013 | Flag
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());
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);
}
}

- rrohit March 05, 2014 | Flag Reply
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]

- rrohit March 05, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More