* *** Bastille Agency coding test Part 3.*** * provide URL recommendations given a start node and a desired "distance" from that node.

Node.java

package org.psk.playground;

/**
 * *** Bastille Agency coding test Part 3.***
 * Node class that holds references to 3 neighbours. Implements Comparable but this isn't currently used. 
 */
public class Node implements Comparable<Node> {
	
	@Override
	public String toString() {
		return String.join(" | ", "Hash " + hashCode(), "Has a link? " + HasLink(), Url);
	}
	
	/**
	 * Unused except in toString
	 * @return whether this node has a non-null link to another node
	 */
	public Boolean HasLink() {
		return A != null || B != null || C != null;
	}
	
	public Node(Node a, Node b, Node c, String url) {
		super();
		A = a;
		B = b;
		C = c;
		Url = url;
	}

	// Make the Nodes public & final. Java's best effort at read-only getters IMO.
	public final Node A;
	public final Node B;
	public final Node C;
	public final String Url;
	
	// Not currently used
	@Override
	public int compareTo(Node arg0) {
		if (this == arg0)
			return 0;
		
		return 1;
	}
	
}

Recommender.java

package org.psk.playground;

import java.util.HashSet;
import java.util.Set;

/**
 * *** Bastille Agency coding test Part 3.***
 * Class that provides URL recommendations given a start node and a desired "distance" from that node.
 */
public class Recommender {
	private static int DEFAULT_DESIRED_DISTANCE = 3;
	
	/**
	 * Pass in a root node and get recommendations DEFAULT_DESIRED_DISTANCE hops away.
	 *
	 * Main public interface for the Recommender. "Go and get all recommendations 3 hops away from here".
	 * See overload below for more discussion.
	 *  
	 * @param rootNode - node from which to start searching
	 * @return - list of URLs
	 */
	public Set<String> getRecs(Node rootNode) {
		return getRecs(rootNode, DEFAULT_DESIRED_DISTANCE);
	}

	/**
	 * Uses Set for maximal implementation flexibility i.e. we can change backing impl and not affect clients, 
	 * while still informing them that the strings will be unique. 
	 * Provide nice return value rather than having client having to new-up collection before calling. This also
	 * enables "fluent" syntax calls and hides recursive nature of adopted algorithm.
	 *  
	 * @param rootNode - node from which to start searching
	 * @return - list of URLs
	 */
	public Set<String> getRecs(Node node, int desiredDistance) {
		
		// TODO determine a sensible maximum for desiredDistance to protect from blowing through the Java stack size limit.
		
		//	 * Use HashSet for O(1) insertions whilst ensuring uniqueness
		Set<String> urls = new HashSet<String>();
		getRecs(urls, node, 0, desiredDistance);
		return urls;
	}
	
	/**
	 * Recurses through the graph in a breadth-first fashion. TBH I haven't done the analysis as to whether depth-first would
	 * be better or not.
	 * Yes, recursion is a dirty word in some eyes but we're only going 3 hops down the graph by default. See above TODO about protecting
	 * against excessive number of hops.
	 * 
	 * @param urls - must be a non-null, empty collection into which the recommended URLs will be put
	 * @param node - node in the graph from which to start
	 * @param currentDistance - how far we are from root
	 * @param desiredDistance - the number of hops away from root we're looking for
	 */
	private void getRecs(Set<String> urls, Node node, int currentDistance, int desiredDistance) {
		if (node == null)	// can't go any further through the graph
			return;

		// woo-hoo we found one exactly desiredDistance away. Stop recursion since we've either seen its neighbours before
		// (< desiredDistance) or we're not interested in ones further away (> desiredDistance)
		if (currentDistance == desiredDistance) {	
			urls.add(node.Url);
			return;
		}
		
		// we know that currentDistance is < desiredDistance so keep going to explore the graph
		getRecs(urls, node.A, currentDistance + 1, desiredDistance);
		getRecs(urls, node.B, currentDistance + 1, desiredDistance);
		getRecs(urls, node.C, currentDistance + 1, desiredDistance);
	}
}

RecommenderTest.java

package org.psk.playground;

import java.util.Collection;

public class RecommenderTest {

	public static void main(String[] args) {
		Recommender r = new Recommender();
		
		RecommenderTest t = new RecommenderTest();
		Node g = t.testBuildGraph();
		
		Collection<String> urls = r.getRecs(g);
		
		for (String u : urls) {
			System.out.println("Recommended URL: " + u);
		}
	}

	private Node testBuildGraph() {
		Node n1 = new Node(null, null, null, "www.google.com/1");
		Node n2 = new Node(n1, null, null, "www.google.com/2");
		Node n3 = new Node(n1, n2, null, "www.google.com/3");

		Node n4 = new Node(n3, null,null, "www.google.com/4");
		Node n5 = new Node(n3, n4, null, "www.google.com/5");
		Node n6 = new Node(n3, n4, n5, "www.google.com/6");

		Node n7 = new Node(n6, null, null, "www.google.com/7");
		Node n8 = new Node(n6, n7, null, "www.google.com/8");
		Node n9 = new Node(n6, n7, n8, "www.google.com/9");
		
//		Node root = new Node(n1, n4, n6, "www.google.com/root");
		Node root = new Node(n9, n8, n7, "www.google.com/root");
		return root;
	}
}

Karthik - TBH this solution took me several attempts to arrive at. I initially dismissed recursion out of a blend of misguided snobbery, familiarity with iterative designs and unfounded concerns about stack size. As long as "desired distance" is "reasonable", recursion is BY FAR the cleanest solution. All my other attempts were... frankly horrific!

As before, comments and discussion of design / implementation choices are in the code - thanks!

@sming - thanks so much for the time here and your solution. Yeah, there are a few different ways to skin the cat here, but recursion is the cleanest. Small comment here: you forgot to remove the URLs from the recommended set that the user has already saved, per the problem - but otherwise, looks good! Looking forward to working together!

gah yes - thanks.