CareerCup

+1 on the BFS approach.

Took me awhile to figure out that it was a Binary Tree and not a Binary Search Tree... irregardless, the solution works for both.

package amazon;

import java.util.LinkedList;

public class BSTCorners {
	public static void main(String[] args) {
		BSTCorners bst = new BSTCorners();
		bst.insertTestData();
		bst.print();
	}

	private Node _root;

	public void print() {
		LinkedList<Node> queue = new LinkedList<Node>();
		queue.add(_root);

		int direction = 1;
		int level = -1;
		while (!queue.isEmpty()) {
			Node n = queue.poll();

			if (n.getLeft() != null)
				queue.add(n.getLeft());

			if (n.getRight() != null)
				queue.add(n.getRight());

			if (level == -1) {
				System.out.println("START: " + n);
				level = n.getLevel();
			} else if (direction == 0 && level < n.getLevel()) {
				System.out.println("LEFT: " + n);
				level = n.getLevel();
				direction = 1;
			} else if (direction == 1 && level < n.getLevel() && (queue.peek() == null || queue.peek().getLevel() > n.getLevel())) {
				System.out.println("RIGHT: " + n);
				level = n.getLevel();
				direction = 0;
			}
		}
	}

	public void insertTestData() {
		_root = new Node(10);
		Node n5 = new Node(5);
		Node n11 = new Node(11);
		Node n9 = new Node(9);
		Node n20 = new Node(20);
		Node n15 = new Node(15);
		Node n14 = new Node(14);
		Node n25 = new Node(25);
		Node n30 = new Node(30);

		_root.setLeft(n5);
		_root.setRight(n11);
		
		n5.setLeft(n9);
		n5.setRight(n20);

		n9.setLeft(n14);

		n11.setRight(n15);

		n15.setLeft(n25);

		n25.setRight(n30);
	}

	public static class Node {
		private int _level;
		private int _weight;
		private Node _left;
		private Node _right;

		public Node(int weight) { _weight = weight;	}
		public int getLevel() {	return _level;	}
		public void setLevel(int level) {_level = level;}
		public Node getLeft() {	return _left;}
		public Node getRight() {return _right;}
		public int getWeight() {return _weight;	}
		public String toString() { return "W:" + _weight + ",L:" + _level;}
		
		public void setLeft(Node left) {
			left.setLevel(_level + 1);
			_left = left;
		}

		public void setRight(Node right) {
			right.setLevel(_level + 1);
			_right = right;
		}
	}
}

Based on two Strings (InputA and InputB) - create two Sets or ordered sequences.

Once I have two Sets of ordered sequences find the intersection. I'm using BST to build by ordered sequence since I still need to find the possible sequences. As I build the sequence I also expand the BST and essentially reset it once I'm working on the next set of sequences.

package amazon;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;

public class MatchingMutatedSequence {
	public static void main(String[] args) {
		new MatchingMutatedSequence().run();
	}

	private final String _inputA = "ABCDEFG";
	private final String _inputB = "DBCAPFG";

	/**
	 * Create two Sets containing all ordered sequences. From there just find
	 * the largest intersection.
	 * 
	 * @author MReyes
	 */
	public void run() {
		Set<String> _setA = createSet(_inputA);
		Set<String> _setB = createSet(_inputB);

		_setB.retainAll(_setA);

		String maxValue = "";
		Iterator<String> iter = _setB.iterator();
		while (iter.hasNext()) {
			String s = iter.next();
			if (s.length() > maxValue.length()) {
				maxValue = s;
			}
		}

		System.out.println(maxValue);
	}

	/**
	 * Create a Set of ordered sequences.
	 * 
	 * @param input
	 * @return
	 * @author MReyes
	 */
	public Set<String> createSet(String input) {
		Set<String> s = new HashSet<String>();
		for (int x = 0; x < input.length(); x++) {
			SortedChar sc = new SortedChar();
			for (int y = x; y < input.length(); y++) {
				sc.insert(input.charAt(y));
				s.add(sc.toString());
			}
		}
		return s;
	}

	/**
	 * Character based BST. Also supports duplicates.
	 * 
	 * @author MReyes
	 * 
	 */
	public static class SortedChar {
		private static class Node {
			private char _data;
			private Node _left;
			private Node _right;

			public Node(char data) {
				_data = data;
			}

			public Node getLeft() {
				return _left;
			}

			public void setLeft(Node left) {
				_left = left;
			}

			public Node getRight() {
				return _right;
			}

			public void setRight(Node right) {
				_right = right;
			}

			public char getData() {
				return _data;
			}
		}

		private Node _root;

		public String toString() {
			StringBuilder sb = new StringBuilder();
			_traverse(sb, _root);
			return sb.toString();
		}

		private void _traverse(StringBuilder sb, Node node) {
			if (node == null)
				return;

			_traverse(sb, node.getLeft());
			sb.append(node.getData());
			_traverse(sb, node.getRight());
		}

		public SortedChar insert(char data) {
			_root = _insert(_root, data);
			return this;
		}

		public Node _insert(Node node, char data) {
			if (node == null)
				return new Node(data);

			if (data < node.getData())
				node.setLeft(_insert(node.getLeft(), data));
			else
				node.setRight(_insert(node.getRight(), data));

			return node;
		}
	}

}

For the test case of:

{1, 2, 1, 1, 1, 1, 1, 1},
{0, 3, 4, 5, 1, 1, 1, 1},
{1, 2, 1, 6, 1, 1, 1, 1},
{1, 3, 4, 5, 1, 1, 1, 1},
{1, 4, 1, 1, 1, 1, 1, 1},
{1, 5, 6, 7, 8, 9, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1}

My solution actually found 19 as a sequence. The sequence is as follows.

121XXXXX
0345XXXX
12X6XXXX
X345XXXX
X4XXXXXX
X56789XX
XXXXXXXX

package amazon;

public class LongestMatrixSequence {
	public static void main(String[] args) {
		new LongestMatrixSequence().run();
	}

	private int[][] _data;
	private int _SIZE_X;
	private int _SIZE_Y;
	private int _max = 0;

	public LongestMatrixSequence() {

		_data = new int[][] { { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 1, 0, 1, 0, 1, 0, 1 },
				{ 1, 0, 1, 0, 1, 0, 1, 0 } };

		_SIZE_Y = _data.length;
		_SIZE_X = _data[0].length;
	}

	/**
	 * Main Loop
	 * 
	 * @author MReyes
	 */
	public void run() {
		boolean[][] flagRef = new boolean[_SIZE_Y][_SIZE_X];

		START: for (int y = 0; y < _SIZE_Y; y++) {
			for (int x = 0; x < _SIZE_X; x++) {
				_reset(flagRef);
				_process(flagRef, x, y, 0);
				if (this._found())
					break START;
			}
		}

		System.out.println("MAX=" + _max);
	}

	/**
	 * Check if it is still worth proceeding.
	 * @return
	 * @author MReyes
	 */
	private boolean _found() {
		return _SIZE_Y * _SIZE_X == _max;
	}

	/**
	 * Utility to reset the "AlreadyInspected" array.
	 * @param flagRef
	 * @author MReyes
	 */
	private void _reset(boolean[][] flagRef) {
		for (int y = 0; y < _data.length; y++) {
			for (int x = 0; x < _data[y].length; x++) {
				flagRef[y][x] = false;
			}
		}
	}

	/**
	 * Check if the position is accessible.
	 * @param flagRef
	 * @param originValue
	 * @param posX
	 * @param posY
	 * @return
	 * @author MReyes
	 */
	private boolean _isAccessible(boolean[][] flagRef, int originValue, int posX, int posY) {
		if (posX < _SIZE_X && posX > -1 && posY < _SIZE_Y && posY > -1)
			return !flagRef[posY][posX] && (_data[posY][posX] - 1 == originValue || _data[posY][posX] + 1 == originValue);

		return false;
	}

	/**
	 * Actual processing API which chooses to go in order: Right, Bottom, Left and then Top.
	 * @param flagRef
	 * @param posX
	 * @param posY
	 * @param counter
	 * @return
	 * @author MReyes
	 */
	private int _process(boolean[][] flagRef, int posX, int posY, int counter) {
		flagRef[posY][posX] = true;
		int value = _data[posY][posX];
		counter++;

		if (this._found())
			return counter;

		_processAccess(flagRef, value, posX + 1, posY, counter);
		_processAccess(flagRef, value, posX, posY + 1, counter);
		_processAccess(flagRef, value, posX - 1, posY, counter);
		_processAccess(flagRef, value, posX, posY - 1, counter);

		return counter;
	}

	/**
	 * Max inspection prior to going back.
	 * @param flagRef
	 * @param originValue
	 * @param posX
	 * @param posY
	 * @param counter
	 * @return
	 * @author MReyes
	 */
	private int _processAccess(boolean[][] flagRef, int originValue, int posX, int posY, int counter) {
		if (_isAccessible(flagRef, originValue, posX, posY)) {
			counter = _process(flagRef, posX, posY, counter);

			if (counter > _max) {
				_max = counter;
			}
			
			flagRef[posY][posX] = false;
		}
		return counter;
	}
}