* *** 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;
	}
}

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